目录
架构
CPU
内存管理
进程线程
文件系统
0 架构
0.1 OS功能
从资源管理角度划分：
- 进程/线程管理
- 内存管理
- 文件管理
- 设备管理
- 用户接口
0.2 OS特征
- 并发
- 共享
- 虚拟
- 随机：不可预测的事件，状态随机
0.3 OS结构
整体架构：
- 应用程序
- 系统调用
- OS内核
- 硬件
0.4 OS分类
- 批处理OS：任务串行
- 分时OS：任务时间片
- 实时OS：外部请求及时响应
- 个人计算机OS：任务通信、资源共享
- 网络操作OS：
- 分布式OS：
- 嵌入式OS：
1 CPU
1.1 CPU 结构
- CPU
- 构成
- 运算器
- 控制器
- 寄存器：控制寄存器、状态寄存器
- 高速缓存
- 寄存器（8086 14个寄存器）
- 段寄存器（4）：CS, DS, SS, ES
- CS: 代码段寄存器
- IP：指令寄存器 （CS + IP -> 代码地址）
- DS: 数据段寄存器 （DS + 地址 -> 数据地址）
- SS：栈寄存器
- SP：栈顶寄存器 （SS + SP -> 栈顶寄存器）
- ES:
- CS: 代码段寄存器
- 指针寄存器：IP, SP
- 段寄存器（4）：CS, DS, SS, ES
- CPU寻址方式
- 直接寻址 : [1]
- 寄存器间接寻址 [bx]
- 寄存器相对寻址 [bx + 1]
- 基址变址寻址 [bx + si]
- 相对基址变址寻址 [bx + si + 1]
- CPU特权级别（x86架构支持4个cpu特权级别，不同级别支持的指令集不同）
- R0：内核态
- R1:
- R2:
- R3: 用户态
- CPU执行状态
- 状态分类
- 内核态：操作系统程序
- 用户态：用户程序
- 状态转换
- 转换类型
- 用户态 -> 内核态：中断，异常，陷入（操作系统提供给用户的接口）
- 内核态 -> 用户态：设置程序状态字PSW
- 中断：来自IO设备、其他硬件设备（硬件异步）
- 分类
- IO中断
- 时钟中断
- 硬件故障
- 中断行为：保存当前进度，处理中断，返回下一条指令
- cpu 取下一条指令
- cpu 执行指令
- cpu 执行一条指令后，扫描中断寄存器，查看是否有中断信号
- 如果有中断，中断硬件保存现场
- 中断硬件将触发器的内容送入PSW对应位置，查找中断向量表，调用中断处理程序
- 中断向量表
- 0-19：不可屏蔽中断和异常
- 0 除0
- 1 单步调试
- 4 算数溢出
- 6 非法操作数
- 12 栈异常
- 13 保护性错误
- 14 缺页异常
- 20-31：保留
- 32-127：外部中断
- 128：系统调用异常 <– （重要）
- 129-238：外部中断
- 239：本地APIC时钟中断
- …
- 255 本地APIC伪中断
- 0-19：不可屏蔽中断和异常
- 多核CPU处理中断
- 中断控制器 GIC Generic Interrupt Controller：全局中断的分发与管理，判断中断交给哪个CPU
- 分类
- 异常（软件同步）
- 分类
- 陷入：有意识安排，返回下一条指令：系统调用
- 故障：可恢复错误，返回当前指令：缺页异常、段错误
- 终止：不可恢复错误、算术溢出、除0、…
- 异常处理
- 1.进入异常时：
- 保存处理器状态
- 准备高特权级执行环境
- 选择并执行合适的异常处理代码
- 2.处理异常时：
- 获取异常信息（调用参数、原因等）
- 3.结束异常时：
- 恢复处理器状态
- 返回低优先级
- 继续执行流
- 1.进入异常时：
- 分类
- 转换类型
- CPU指令类型
- 特权指令：启动IO、内存清0、修改程序状态字、设置时钟、允许/禁止中断
- 非特权指令：控制转移、算数运算、取数指令
- 状态分类
- 构成
1.2 寄存器
单位：
- 1 word 字 = 16位 = 2b
8086有14个寄存器，每个CPU 1 word
- 通用寄存器（4）：AX,BC,CX,DX
寄存器功能：
/* 1. 16位CPU 8086 */
typedef int WORD; /* WORD = 16 */
/* 2. CPU */ WORD _memory_[110240] = {0};
/*--------------------------------------*/
/* ---------------------* */
WORD AX; /* */
WORD BX; /* */
WORD CX; /* */
WORD DX; /* */
/* */
WORD SI; //字符串复制 /* */
WORD DI; /* */
/* */
WORD SS; WORD BP; WORD SP; /* ========= */ WORD stack_segment[1024]
WORD CS; WORD IP; /* ========= */ WORD code_segment[4096];
WORD DS; /* [] */ /* */ WORD data_segment[4096];
WORD ES; /* */
/**************************/
BP是SS栈偏移
mv [bp] -> mv [ss + bp]
/* ---------------------* */
/*-------------------------------------*/
1.3 汇编指令
#define SP__ (stack_segment[SP])
#define IP__ (code_segment[IP])
/* 取地址 mov ax [0x0f] */
#define l_l(a) (data_segment[DS + a]) /* [a], [a + 1]处理数组 */
/* decleare */
#define dw(a, ...) (code_segment[0] = a; code_segment[1] = b) /* decleare word */
#define db(str) (code_segment[0] = str[0]; code_segment[1] = str[1]) /* decleare bytes */
/* 汇编指令 */
#define mov(a, b) (a = b)
#define add(a, b) (a += b)
#define sub(a, b) (a -= b)
#define push(a) {SP -= 2; SP__ = a;}
#define pop(a) {a = SP__; SP += 2;} // a 用于接收出栈的数据
#define inc(a) (a++)
#define loop(pos) (CX--; if CX != 0 goto pos) /* see func doloop() */
#define and(a, b)
#define or(a, b)
#define _int(a)
1.4 程序
从代码到执行的流程
- 编写
- 编译
- 链接（可执行文件）
- 执行
编译过程
int main()
{
int b = 2 * 2 * 2;
return 0;
}
编译结果
assume cs:abc ; 声明代码段
abc segment
mov ax, 2
add ax, ax
add ax, ax
mov ax, 4c00h ; 程序返回值
int 21H ; 中断
abc ends
end
循环
assume cs:abc ; 声明代码段
abc segment
mov ax, 2
mov cx, 11 ; cx 用于计算循环
s: add ax, ax
loop s
mov ax, 4c00h ; 程序返回值
int 21H ; 中断
abc ends
end
代码段中存放数据
assume cs:codesg
codesg segment
dw 1, 2, 3, 4 /* 这四个数存放在代码段中，位置在代码段起始位置 */
start mov ax,0 /* 使用start关键字，设置代码段指令起始位置，防止CPU将上述数据读为code */
codesg ends
end start /* end可声明代码从哪开始执行 */
代码段，数据段，栈段
assume cs:code1, ds:data1, ss:stack1 ; 声明
data1 segment
dw 1,2,3,4
data1 ends
stack1 segment
dw 0,0,0,0
stack1 ends
code1 segment
start mov ax, stack1
mov ss, ax
mov ax, data1
mov ds, ax
code1 ends
end start
寻址：
reg : 通用寄存器
sreg : 段寄存器
ip是特殊寄存器
reg：ax bx cx sp bp si di
sreg: ds ss cs es
可用于内存单元寻址：bx bp si di
单独或4种组合出现：bx,si bx,di bp,si bp,di
mov [bp] = mov ss:[bp]
cpu寻址方式：
- 直接寻址 : [1]
- 寄存器间接寻址 [bx]
- 寄存器相对寻址 [bx + 1]
- 基址变址寻址 [bx + si]
- 相对基址变址寻址 [bx + si + 1]
强制类型转换：
mv word ptr ax 1
div [除数]
参数长度（位）
除数 被除数
8 16 (存放在ax中)
16 32 (存放在dx和ax中)
ax放商，dx放余数
8086转移指令：
- 无条件转移 jmp
- 条件转移
- 循环指令 loop
- 过程 即函数
- 中断
编译器指令offset
以一段代码段为例：
start: mov ax,offset start ; 等价于 mov ax 0
s: mov ax,offset s ; 等价于mov ax,3
jmp 无条件转移
- 实现：修改ip，或修改 cp 和 ip
jmp short 标号
段内段转移，IP修改范围为[-128, 127]
示例：
start: mov ax,0
jmp short s ; 无条件转移到s （内部实现：从当前位置开始算，按偏移地址转移）
add ax,1
s: inc ax
(内部实现：ip += offset s - offset MYSELF)
1.5 操作系统
- CPU状态：
- 内核态：操作系统程序
- 用户态：用户程序
- CPU指令类型：
- 特权指令：启动IO、内存清0、修改程序状态字、设置时钟、允许/禁止中断
- 非特权指令：控制转移、算数运算、取数指令
- CPU特权级别：x86架构支持4个cpu特权级别，不同级别支持的指令集不同
- R0：内核态
- R1:
- R2:
- R3: 用户态
- CPU状态转换：
- 用户态 -> 内核态：中断，异常，陷入（操作系统提供给用户的接口）
- 内核态 -> 用户态：设置程序状态字PSW
- 中断类型：来自IO设备、其他硬件设别（）
- IO中断
- 时钟中断
- 硬件故障
- 中断行为：保存当前进度，处理中断，返回下一条指令
- cpu 取下一条指令
- cpu 执行指令
- cpu 执行一条指令后，扫描中断寄存器，查看是否有中断信号
- 如果有中断，中断硬件保存现场
- 中断硬件将触发器的内容送入PSW对应位置，查找中断向量表，调用中断处理程序
- 中断向量表：
- 0-19：不可屏蔽中断和异常
- 0 除0
- 1 单步调试
- 4 算数溢出
- 6 非法操作数
- 12 栈异常
- 13 保护性错误
- 14 缺页异常
- 20-31：保留
- 32-127：外部中断
- 128：系统调用异常 <– （重要）
- 129-238：外部中断
- 239：本地APIC时钟中断
- …
- 255 本地APIC伪中断
- 0-19：不可屏蔽中断和异常
- 异常分类：
- 陷入：有意识安排，返回下一条指令
- 故障：可恢复错误，返回当前指令
- 终止：不可恢复错误
- 异常举例：
- 系统调用
- 页故障/页错误
- 断点指令
- 程序性异常：算术溢出、除0、…
- 系统调用功能：用户调用操作系统功能，包括进程管理、文件管理、设备管理等
- 系统调用方式：c函数库封装系统调用，用户调用c函数库。每个系统调用都有系统调用号。
- 系统调用执行流程：
- 中断/异常机制：硬件保护现场，查找中断向量表，调用系统调用入口程序
- 系统调用入口程序：保存现场，参数压栈，查找系统调用表，调用系统调用例程或内核函数
- 执行系统调用例程
- 恢复线程，返回用户程序
2 内存管理
结构
- 分段
设计
- 虚拟地址分为若干大小的段
- 段表存储分段信息
- 每个进程1个段表，操作系统1个全局段表
实现
- 虚拟地址为：[段号 + 段内偏移]（段号->段基址 + 段内偏移）
- 物理地址：以段为单位分配
- 段表 --------+--------+-------- 段号 | 段基址 | 段长度 --------+--------+-------- 0 | 0x... | 2k 1 | 0x... | 5k --------+--------+---------优点
- 逻辑连续
缺点
- 分段粒度粗，容易产生外部碎片
- 分页
设计
- 物理内存划分为连续、等长的物理页
- 虚拟页与物理页大小相等
- 虚拟页可映射至任意物理页
- 每个进程1个页表（或1级页表）
实现
- [虚拟页号 + 页内偏移]
- 页表 --------+---------- 虚拟页号 | 物理页号 --------+---------- 0 | 10 1 | 13 --------+----------优点
- 解决外部碎片
- 应用程序时空局限性：执行时，使用的数据或代码是连续的
缺点
- 页表过大（解决：多级页表 -> 剪枝）
- 多级页表：[虚拟页号_0:虚拟页号_1:虚拟页号_2:虚拟页号_3 + 页内偏移]
- 页表过大（解决：多级页表 -> 剪枝）
优化
TLB （性能）
- 位置：位于CPU内部
- 功能：缓存虚拟页号到物理页号的映射关系
- 作用：先查TLB，如果TLB未命中，再查缓存
- 刷新：切换页表时，刷新全部TLB（优化：TLB缓存项记录页表标签，切换页表时无需全部刷新）
[CPU] --> [TLB] --> [页表] [p3] [p9] [p5]- 结构：根据CPU缓存 L1 L2 L3 分级结构 -> TLB 也是分级结构
swapping （大小）
- 功能：虚拟内存 > 物理内存时，将内存页存放到磁盘
- 算法：FIFO、LRU/MRU、Clock
缺页异常 （稳定）
- 原因：物理内存需求过大
- 处理：等待磁盘IO，将物理页读取至内存
伙伴系统（利用率）
- 问题：外部碎片：空闲但不连续；内部碎片：分配空间过大
- 实现：分裂与合并
- 伙伴系统 时间1： [ ] 时间2： [ ] [ ] 时间3： [ ] [ ]空闲链表：较大空间分裂时，将多余的部分移入上一空间数组链表
- 空闲数组链表 [ 2^0 ] [ 2^1 ] -> [] -> [] [ 2^2 ] -> []
写时复制（共享）
3 进程线程
1.1 概述
- 进程
定义：Process/Task/Job 定义：某个数据集合上一次运行活动。资源分配单位。
实现：进程控制块 Process Control Block PCB：进程描述符，进程属性
- 基本信息：pid, 进程名，userid
- CPU现场：寄存器，程序计数器，状态字PSW，栈指针，页表指针
- 控制信息：状态，优先级，代码执行入口，程序磁盘地址，运行统计信息（执行时间，页面调度），进程同步与通信，进程队列指针，进程消息队列指针
- 资源信息：虚拟地址空间，打开的文件
状态：
分类：
- 就绪态：CPU不空闲
- -> 运行：被调度程序选中
- 运行态：
- -> 就绪：时间片用完，高优先级抢占
- -> 等待：系统调用、IO、进程通信、…
- 等待态：阻塞
- -> 就绪：等待事件发生
- 创建态：
- 终止态：进程结束，统计运行信息，资源回收
- 挂起态：调节负载）（进程映像交换到磁盘）
- 就绪态：CPU不空闲
linux 进程状态：
fork() -> 就绪态 -> 运行态 +--> 浅度睡眠 --+ | | +--> 深度睡眠 --+ | |--> 就绪态 （wake_up / 信号） +--> 暂停 --+ | | +--> 僵尸 --+ 就绪->运行：schedule() 运行->就绪：时间片结束 运行->浅度睡眠：等待资源，interruptible_sleep_on()，schedule() 运行->深度睡眠：等待资源，sleep_on()，schedule() 运行->暂停：ptrace调试，schedule()
进程队列
进程状态改变：从一个队列出队，进入另一个队列
等待队列：等待事件不同，有多个等待队列进程生命周期
- 创建 fork/exec：分配pid，分配pcb，复制父进程地址空间（linux优化：当子进程要写父进程地址时，才复制地址空间），继承父进程共享资源(打开的文件，工作目录)，设置队列指针
- 阻塞 wait 等待子进程：自己执行阻塞原语
- 唤醒
- 挂起
- 激活
- 撤销 exit：关闭文件，回收内存，撤销pcb
进程切换
进程地址空间
--------- 用户地址空间 栈 . . . 堆 --------- 数据段 --------- 代码段 --------- ... ----------- 操作系统地址空间 内核栈 ----------- 内核代码 ------------上下文切换：将cpu硬件状态从一个进程换到另一个进程
- 直接开销：保护和恢复寄存器、切换地址空间
- 间接开销：高速缓存失效、缓冲区缓存失效、TLB失效
进程通信
- 信号
- 信号量 （锁）
- 消息队列 （传递数据 + 阻塞）
- 管道 （传递数据 + 阻塞）
- 共享内存 （传递数据 + 阻塞）
- 套接字 （传递数据 + 阻塞）
线程
进程问题
- 创建进程开销大：数据段、代码段、堆、栈段
- 进程隔离性强：IPC开销大
- 进程内部无法支持并行
线程优点
- 构成：执行所需最小状态：寄存器和栈（每个线程有自己的栈，共享数据、代码、堆）
- 线程id，线程状态，线程上下文，线程栈和栈指针
- 开销小：创建和销毁，切换，通信
- 性能高：多处理器并发执行
- 构成：执行所需最小状态：寄存器和栈（每个线程有自己的栈，共享数据、代码、堆）
线程模型（用户线程 与 内核线程）
- 多对一
- 一对一：内核线程数量大
- 多对多
线程调度
调度场景
[t1] [CPU1] [t2] -> [调度器] -> [t3] [CPU2]调度算法
衡量标准
吞吐量
周转时间：请求 -> 运行
响应时间：请求 -> 第一次回应
CPU利用率
等待时间：就绪 -> 运行
算法分类
算法类型
算法 实现 优点 缺点 批处理系统 先来先服务 FCFS - 公平、简单 长任务不友好 最短作业优先 SJF - 最短平均周转 长任务不友好 最短剩余时间优先 SRTN 最高响应比优先 HRRN 响应时间 = （处理时间 + 等待时间） / 处理时间 交互式系统 时间片轮转 RR - 公平、响应快 进程切换开销高、IO进程不友好 （IO进程进入优先级高、独立就绪队列） 最高优先级 HPF 优先级动态或静态 - 低优先级饥饿、优先级反转（低优先级进程持有锁，高优先级进程抢占，低优先级无法执行） 多级反馈队列 MFQ 多个就绪队列，优先级依次降低，时间片依次增加，时间片轮转调度，高优先级优先调度 最短进程优先 操作系统
OS 策略 unix 动态优先 BSD 多级反馈 Linux 抢占 Windows 32优先级抢占（优先级进入就绪队列） Solaris 综合调度
调度问题
- 优先级反转
使用临界区资源时：- 优先级上限：优先级临时设为最高
- 优先级继承：临时继承最高优先级
- 禁止中断：禁止被抢占
- 优先级反转
线程通信
- 临界区
- 要求
- 互斥访问
- 有限等待
- 空闲让进
- 算法
皮特森算法 (?)
// 进程 0 while (1) { flag[0] = true; turn = 1; while (flag[1] == true && turn == 1) { /* 临界区 */ flag[0] = false; } } // 进程 1 while (1) { flag[1] = true; turn = 0; while (flag[0] == true && turn == 0) { /* 临界区 */ flag[1] = false; } }硬件原子
- 概念
- 不可被打断的操作集合
- 其他核心不会看到中间状态
- 实现
- intel 锁总线
- arm LL/SC
- 概念
- 要求
- 线程锁
- 自旋锁
- 读写锁
- 线程死锁
- 预防
- 避免互斥访问
- 不允许持有并等待
- 不允许资源抢占
- 打破循环等待（按特定顺序获取资源）
- 解决
- 银行家算法
- 获取资源需管理者同意
- 管理者预演不会造成死锁
- 银行家算法
- 预防
- 临界区
多核缓存
[ cpu 0 ] [ cpu 1 ] [ cpu 2 ] [ cpu 3 ] [l1 cache] [l1 cache] [l1 cache] [l1 cache] [ l2 cache ] [ l2 cache ] [ l3 cache ] [ 内存 ]- 缓存一致性
原则
- 独占修改
- cpu核独占缓存行：本地可读可写
- 其他核读需迁移到共享
- 其他核写需迁移到失效
- 共享
- 多核拷贝缓存行
- 本地可读
- 本地写迁移到独占修改，使其他核缓存行失效
- 其他核写需迁移到失效
- 失效
- 本地缓存行失效
- 本地不能读/写缓存行
- 本地读需迁移到共享，其他核需迁移到共享
- 本地写需迁移到独占修改，其他核该行失效
- 独占修改
通知其他核
全局缓存：记录缓存行拥有者信息 | dirty cpu1 cpu2 cpu3 | |0 1 1 1 | | 状态 内容 | | 状态 内容 | | 状态 内容 | cpu1 cpu2 cpu3
- 缓存一致性
pthread_yield：让出cpu
进程优先级：动态优先级，静态优先级
2 进程通信
2.1 分类
2.1 代码
一 信号
// 发送
kill(pid_t pid, int signum)
// 接收
signal(int signum, sig_handle_func()) /* 不阻塞，先恢复信号，再处理 */
sigaction(int signum, ...) /* 阻塞，先处理，再恢复信号 */
二 信号量 （Posix）
#include <semaphore.h>
// 初始化
int sem_init(sem_t *sem, int pshared, unsigned int value); /* 0：进程内线程同步 */
int sem_destroy(sem_t *sem);
// 上锁
int sem_wait(sem_t *sem);
// 解锁
int sem_post(sem_t *sem);
// 创建 （有名信号量）
sem_t *sem_open(const char *name, int flag);
int sem_close(sem_t *sem);
int sem_unlink(const char *name);
// 其他
int sem_trywait(sem_t *sem);
int sem_timewait(sem_t *sem);
三 消息队列
// 创建
int msgget(key_t key, int msgflg); /* flag: 访问权限 */
key_t ftok(const char *pathname int projid);
// 发送
int msgsnd(int msqid, const void *data, size_t datasz, int msgflag);
// 接收
ssize_t msgrcv(int msqid, void *data, size_t datasz, long msgtype, int msgflag); /* msgtype: 接收指定类型消息 */
// 删除、赋值、查询
msgctl(int msqid, int cmd, struct msqid_ds *buf);
四 管道
// 创建（匿名管道）
int pipe(inf fd[2]); /* 0读1写 */
// 关闭
void close(int fd);
// 发送
int write(int fd, void *data, size_t datasz);
// 接收
int read(int fd, void *data, size_t datasz); /* 阻塞 */
// 创建 （命名管道: 对应真实文件） + open()
int mkfifo(const char *file, mode_t mode);
int mknode(const char *path, mode_t mode, dev_t device_type); /* 较老 */
五 共享内存
六 套接字
2.3 命令
# 信号: 查看
kill -l
# 命名管道
mkfifo FILE
mkfifo FILE p
4 文件系统
- 文件系统
ext2
架构
磁盘 | 引导 | | 块组1 | 块组 (数据存储在block中) | 块组2 | < | 超级块 | | 快组. | | 组描述符 * n | | 块组n | | 块位图 | | inode位图 | inode （大小：128 / 256bytes，block数据可能会超过记录至） | inode * n | < | 文件类型 | | block * n | | 文件大小 | | 链接数 | 有多少文件名指向此inode | 文件权限 | | 时间 | (创建、修改、访问) | 1级指针 * 12 | -> block （block 为 4k时，最大单一文件为2T，文件系统容量为16T） | 2级指针 * 1 | | 3级指针 * 1 | | 4级指针 * 1 |
文件系统崩溃一致性
- 一致性属性
- 持久化
- 原子性
- 有序性
- 一致性实现
- 日志
- 缺点：日志多次读写占用IO
- 改进：批量写日志 + 检查点
- 日志
- 一致性属性
- 设备管理
- 分类
- 字符设备：LED、键盘、串口
- 顺序访问：内次读取一个字符
- 通过驱动与设备交互
- 块设备：内存、磁盘、u盘
- 随机访问：以块粒度进行读写
- 系统层增加缓冲区，避免与慢设备频繁交互
- 网络设备：网卡
- 面向格式化报文的收发
- 驱动以上维护多种协议
- 字符设备：LED、键盘、串口
- 设备管理
- 字符抽象：文件系统：open/read/write/close
- 块抽象：文件系统、mmap
- 网络抽象：socket、文件系统：sockent/send/recv/close
- CPU与设备交互
- 可编程IO：cpu的in/out load/store指令
- 特点
- 消耗CPU时钟周期 与 数据量成正比
- 适合于小型设备
- 分类
- PIO (port IO)
- IO设备具备独立的地址空间
- 使用特殊指令 in/out
- MMIO (Memory-mapped IO)
- 将设备映射到连续物理内存中
- 使用内存访问指令
- 行为与内存不完全一样，读写有副作用
- PIO (port IO)
- 特点
- 直接内存访问 DMA：外设可直接访问总线
特点
- DMA与内存交互传输数据，无需CPU参与
- 适合与高吞吐量IO
结构
[CPU] | [高速缓存] | ----+---------------+--------------+--------- 系统总线 | | [DMA控制器] [内存] | ----+---------------------------------------- PCI总线 | [外设]读取步骤
- 1.CPU中驱动发出请求，将设备数据读取至内存地址x
- 2.外设初始化DMA传递，将数据传送到数据DMA控制器
- 3.DMA将数据传送至内存地址x
- 4.DMA传输完成后，向CPU发出中断
- 5.PU执行每条指令后，检查中断是否到来
- 可编程IO：cpu的in/out load/store指令
- 分类