操作系统

Ch1-2 · 进程

1. OS 概念 / 特征 / 分类
2. 用户态核心态 / 系统调用
3. 中断 / 异常 / 陷阱
4. 进程 / PCB / 组织
5. 状态机 + 进程控制
6. 线程 / 用户级内核级
7. 三层调度 / 切换
8. FCFS / SJF / SRTN
9. RR / 优先级 / MLFQ

Ch2-3 · 同步内存

1. 同步互斥 / 临界区
2. 信号量 PV
3. P-C 经典
4. R-W + 哲学家
5. 死锁四条件
6. 银行家算例
7. IPC 进程通信
8. 内存分配 + 装入
9. 分页 + TLB

Ch4-6 · 虚存文件IO

1. 多级 / 反置页表
2. 分段 / 段页式
3. 虚拟内存 / 缺页
4. 置换算法对比
5. 工作集 / 抖动
6. 文件 / FCB / inode
7. 文件分配方式
8. 空闲管理
9. 磁盘调度
10. IO 控制方式

四大特征

• 并发 · 宏观同时多任务（vs 并行：物理同时）
• 共享 · 互斥共享 / 同时共享
• 虚拟 · 时分（虚拟 CPU）/ 空分（虚拟内存）
• 异步 · 推进速度不可预知

OS 发展史

• 手工 → 单道批 → 多道批（提高 CPU 利用率）
• 分时（交互）→ 实时（响应严格）→ 通用
• 网络 / 分布式 / 嵌入式 / 个人机 / 手机

四种 OS 体系结构

OS 目标

1. 资源利用率（吞吐率）
2. 响应速度 / 公平
3. 方便、可靠、可扩展
4. 提供良好的用户接口

区别

典型特权指令

• 启动 / 停止 IO
• 开 / 关中断
• 修改 PSW、时钟
• 切换页表 / 设置时钟
• 装入 PSW / DAR

系统调用 System Call

用户程序请求 OS 服务的唯一合法入口。

1. 用户程序把参数 + 系统调用号放入寄存器
2. 执行陷入指令 trap → 进入核心态
3. 跳到对应的系统调用处理程序
4. 执行服务（如 read 文件）
5. iret / sysret 返回用户态

5 类系统调用

分类

中断 / 异常都涉及"保护现场 → 跳服务程序 → 恢复"。

中断屏蔽

• 不可屏蔽 NMI：硬件故障、电源失效
• 可屏蔽 INTR：可由 PSW.IF 位关闭
• 同优先级 / 低优先级时屏蔽

中断处理流程

1. 当前指令结束
2. 检查 INTR；有 → 入核心态
3. 关中断，硬件保护 PC、PSW
4. 识别中断源（向量表）
5. 由中断服务程序：保存通用寄存器现场
6. 开中断（允许嵌套）
7. 处理中断
8. 关中断 + 恢复现场 + iret

多重中断

在服务中允许更高优先级中断。每级有中断屏蔽字规定能屏蔽哪些级别。同级总是屏蔽，且需自屏。

进程的特征

• 动态：执行的活动（程序是静态的指令集合）
• 并发：可以同时存在多个进程
• 独立：独立地址空间和资源
• 异步：推进速度不可预知
• 结构：PCB + 数据段 + 程序段

PCB 进程控制块

// 进程在系统中存在的唯一标识
struct PCB {
  PID, UID, GID;           // 标识符
  PSW, PC, GPR[];           // 处理机状态
  state, priority, queue;   // 调度信息
  PageTableBase, ASID;      // 内存
  OpenFileTable;            // 文件
  IPC channels;             // 通信
  CPU/IO usage;             // 记账
};

进程组织

• 链接方式：同状态的 PCB 串成队列；OS 维护多个就绪队列 / 阻塞队列
• 索引方式：每种状态一张索引表，表项指向 PCB

5 状态进程模型

新建（创建中）→ 就绪（等 CPU）→ 运行（在 CPU 上）→ 阻塞（等事件）→ 终止（资源回收中）。
+ 挂起状态（被换出内存）：就绪挂起 / 阻塞挂起。

引入"挂起"是为了腾出内存给其他进程。挂起 ≠ 阻塞：挂起是用户/OS 主动换出。

四种进程控制原语

原语：用关 / 开中断保证执行不可中断；必在核心态执行。

易错点

• 就绪 → 阻塞 不存在（必先运行）
• 阻塞 → 运行 不存在（必先就绪）
• "阻塞"是进程自己执行 P 操作或 IO 请求"主动"造成的

线程 vs 进程

线程独占的部分

PC、寄存器组、栈、线程局部存储 TLS。

线程共享（来自进程）

代码段、堆、全局变量、文件描述符、信号处理器。

三种实现

多线程模型

• 多对一：多 ULT 映射到 1 KLT（不能并行）
• 一对一：一 ULT 一 KLT（Windows、Linux 默认）
• 多对多：M:N 映射（Solaris 早期）

不能切换的时机

• 关中断时
• 处理中断 / 异常 / 系统调用过程中（部分实现可抢占）
• 在内核临界区
• 原子操作执行中

调度评价指标

周转时间 = 完成 - 提交
带权周转 = 周转 / 服务
等待时间 = 周转 - 服务
响应时间 = 首次响应 - 请求
CPU 利用率 = 忙 / 总
吞吐率 = 完成数 / 单位时间

抢占 vs 非抢占

• 非抢占：进程主动让出 CPU（FCFS、SJF 非抢占）
• 抢占：更高优先 / 时间片到 → 强行剥夺（SRTN、RR、抢占优先级）

饥饿 Starvation

低优先级 / 长任务一直不被调度。解决：老化 aging — 等待时间越长优先级越高。

典型甘特图（4 进程）

进程到达：A(0,7) B(2,4) C(4,1) D(5,4)

SJF 在选 B 时 C 还没到；SRTN 一旦更短的来，立即抢占。

三大特点对比

SJF 在 burst 已知或可预测（指数平均 τ_{n+1} = α·t_n + (1-α)τ_n）。
SRTN 在新进程到达时再判断一次。

时间片轮转 RR

• 就绪队列 FIFO，每进程 q 单位 CPU
• q 太大 → 退化 FCFS；q 太小 → 切换开销大
• 典型 q = 10~100 ms
• 响应快、公平，但平均周转不一定最小

优先级调度

• 静态优先级：进程创建时定，简单但低优先饥饿
• 动态优先级：随运行/等待时间调整（老化）
• 抢占式：每当更高优先到达 / 唤醒立即抢占
• 非抢占式：当前完成或主动让

多级反馈队列 MLFQ

1. 设 k 个就绪队列，优先级由高到低，时间片由短到长
2. 新进程进队列 1（最高优先）
3. 该队空才调度下一队列
4. 用完时间片仍未结束 → 降到下一级
5. 队列 k（最低）通常用 RR

Unix/Linux 早期调度器使用类似 MLFQ。

同步 vs 互斥

临界区四原则

1. 空闲让进：空闲时任一申请可进
2. 忙则等待：已有进程在内，其他等
3. 有限等待：不无限等（防饥饿）
4. 让权等待：等待时让 CPU（防忙等）

三种互斥实现

TestAndSet (硬件原语)

bool TS(bool *lock) {
  bool old = *lock;
  *lock = true;
  return old;       // 原子读改写
}

// 自旋锁
while(TS(&lock)) ;
进入临界区; ...
lock = false;

整型信号量 vs 记录型

// 整型: 忙等
P(S): while(S <= 0) ;  // 自旋
       S--;
V(S): S++;

// 记录型: 让权 (考试用)
typedef { int value; queue L; } sem;

P(sem &S):
  S.value--;
  if(S.value < 0) block(S.L, self);

V(sem &S):
  S.value++;
  if(S.value <= 0) wakeup(S.L);

信号量含义

• S.value > 0：还有 S.value 个资源可用
• S.value = 0：无空闲资源，下一次 P 操作会阻塞
• S.value < 0：|S.value| 个进程在等

P / V 的正确使用

"P 资源 → P 互斥 → 临界区 → V 互斥 → V 资源"。
顺序错（先 P 互斥再 P 资源）易死锁。

原子性

PV 由 OS 实现，内部用关中断 / 硬件原语保证原子；用户层只看到不可分割的操作。

问题约束

• 生产者不能往满缓冲区放
• 消费者不能从空缓冲区取
• 缓冲区共享 → 互斥访问
• 共需三个信号量：mutex / empty / full

信号量定义

mutex = 1  // 缓冲互斥
empty = N  // 空槽位数
full = 0  // 已填槽数

producer():
  while(true) {
    produce(item);
    P(empty);          // 等空槽
    P(mutex);          // 互斥
    put(item);
    V(mutex);
    V(full);           // 多了一份产品
  }

consumer():
  while(true) {
    P(full);
    P(mutex);
    item = get();
    V(mutex);
    V(empty);
    consume(item);
  }

⚠️ 互换 P 顺序：
P(mutex); P(empty); 若 empty=0 → 持锁阻塞 → 消费者拿不到 mutex → 死锁。

读优先 R-W

sem mutex=1, w=1; int rc=0;

reader():
  P(mutex); rc++;
  if(rc==1) P(w);     // 第一个读阻塞写
  V(mutex);
  read(); ...
  P(mutex); rc--;
  if(rc==0) V(w);     // 最后一个读放写
  V(mutex);

writer():
  P(w); write(); V(w);

读者优先：只要有读，写就一直等 → 写饥饿。
写优先需另加 mutex2 阻塞后续读。

哲学家进餐 5 解

1. 限制并发：room 信号量 = 4，最多 4 人同时拿筷
2. 原子拿两筷：检查时同时持有 mutex，两支都空才拿
3. 奇偶：奇数先左，偶数先右 → 必有一人拿不到任何 → 不死锁
4. 资源分级：给筷子编号，必从小到大拿
5. 仲裁：用一信号量当门卫

本质：哲学家是死锁的"循环等待"原型。任意打破 4 条件之一都能解决。

4 个必要条件（同时满足 = 死锁）

1. 互斥：资源不可共享
2. 占有并请求：已占有的同时请求新的
3. 不可剥夺：资源只能自愿释放
4. 循环等待：进程 → 资源 → 进程 形成环

三种应对策略

预防 · 4 条件分别破坏

• 破互斥：让所有资源可共享（一般做不到）
• 破占有并请求：进程开始前一次性申请所有资源
• 破不可剥夺：申请新资源失败时主动释放已有资源
• 破循环等待：资源编号，必须按号递增申请

检测算法（资源分配图化简）

把进程节点的"未被阻塞"的边都消除：所有边都能消则无死锁。残留环 = 死锁进程。

解除

• 剥夺资源：抢一个进程的资源给另一个
• 撤销进程：按代价从低到高
• 回滚：让进程退到之前的某个安全点

数据结构

Available[m]      // 各类资源现有数
Max[n][m]         // 进程最大需求
Allocation[n][m]  // 已分配
Need = Max - Allocation
Request[i]        // 进程 i 当前请求

// 1. 请求合法性
if(Request > Need || Request > Available)
  reject 或 阻塞;

// 2. 试探分配
Available -= Request;
Allocation += Request;
Need -= Request;

// 3. 安全性检查
若安全 → 真分配
否则  → 回退试探

安全性算法

Work = Available;
Finish[i] = false;

repeat:
  找 i : Finish[i]=false &&
         Need[i] <= Work
  if(找到):
    Work += Allocation[i]
    Finish[i] = true
    continue
  break;

if(forall Finish[i]=true)
  → 安全 (Work 序列即安全序列)
else
  → 不安全

实战例

5 进程 3 类资源，Total=(10,5,7)，Allocation/Need 给定 → 找 Need[i] ≤ Available 的进程逐步释放，直到所有进程 Finish。常见题：给一个新 Request，判断是否安全。

程序装入方式

链接方式

• 静态链接：装入前合并目标模块
• 装入时动态：装入时按需链接
• 运行时动态：用到时才链（如 .dll / .so）

连续分配 4 种 (已淘汰但要会)

动态分区分配算法

• 首次适应 FF：按地址升序找第一块合适 → 简单、低地址碎片
• 最佳适应 BF：找最小够用 → 易产生大量小碎片
• 最坏适应 WF：找最大块切 → 大块快用尽
• 邻近适应 NF：从上次结束处开始找

"碎片紧凑"compaction 可以整理外部碎片 → 但需要动态重定位支持。

地址变换

访存次数

基本分页：2 次访存（取页表项 + 取数据）。
有 TLB 时：命中只需 1 次（TLB 内含目标页表项）。

TLB 快表

• 位于 MMU，相联存储器
• 缓存近期使用的页表项（数十到数百条）
• 命中率通常 > 90%
• EAT（有效访问时间）= h(t_tlb + t_mem) + (1-h)(t_tlb + 2t_mem)

页内碎片

每个进程最后一页可能不满 → 内部碎片，平均损失半页。页越大碎片越多，但页表越小。

典型页大小：4 KB、8 KB（Linux x86 默认 4 KB）。

页表项标志位

V 有效位 / D 修改位（dirty）/ A 访问位 / U 用户权限 / R/W 读写位 / G 全局位。

问题

32 位虚拟地址，4 KB 页：页表项数 = 2³²/2¹² = 2²⁰ = 1M 项。每项 4 字节 → 4 MB 页表 / 进程。100 个进程就要 400MB。

二级页表

反置页表 IPT

每个物理页框一项，全 OS 共一张表（不再按进程）。

表项 = <PID, 页号 P, 控制位>
地址变换：(PID, P) → hash → 表项 i → 物理帧 i

• 表大小：与物理内存正比，与虚拟空间无关
• 查找慢 → 配 TLB 弥补
• 共享页较难表达
• Power、UltraSPARC 用

64 位 → 4 级或 5 级

x86_64：48 位地址，4 KB 页 → 4 级页表（9+9+9+9+12 位）。Intel 5 级页表支持 56/57 位虚拟地址。

分段

分页 vs 分段

段页式

既保留分段的逻辑独立 / 共享 / 保护，又用分页解决碎片。
每段单独分页，段内的页表起址在段表中。

保护与共享

• 分段共享：在段表中指向同一段（共享代码段）
• 分页共享：两个进程的页表项指向同一物理帧（写时拷贝）
• 分页保护：页表项的 R/W、U/S 位

基础

利用程序的局部性原理：只调入当前真用到的页；缺页时再从磁盘换入。

• 时间局部性：刚访问的近期还会用
• 空间局部性：附近地址会被一起用
• 虚拟地址空间可以远大于物理内存

页表项扩展

物理块号 | V 有效 | D 修改 | A 访问 | U/S 权限

V=0 表示该页不在内存中。

缺页中断处理 8 步

1. CPU 取页表项发现 V=0
2. 触发缺页中断 → 进入核心态
3. OS 找空闲物理块（无则调置换算法）
4. 若被换出页的 D=1 → 先写回磁盘
5. 把目标页从磁盘读入物理块
6. 更新页表：V=1，填入物理块号
7. 更新 TLB
8. 重启被中断的指令

驻留集 + 分配策略

• 固定 / 可变驻留集
• 局部置换：只在本进程范围内换
• 全局置换：可以挑别的进程的页
• 固定+局部 / 可变+全局 / 可变+局部

Belady 异常

FIFO 算法下，物理块数增加反而缺页率上升的反常现象。LRU、OPT 不会出现。

LRU 模拟例

页面引用串：7,0,1,2,0,3,0,4,2,3

3 个物理块：

Clock 算法描述

页框组成环形链表，扫描指针顺序前进；访问位 A：1→清零并跳过；0→替换并新页 A=1。

抖动 Thrashing

物理块过少 → 缺页频繁 → CPU 大量时间在换页而非计算 → 系统吞吐反而下降。

原因：进程数太多、驻留集太小。

两种解决思路

• 工作集模型 Working Set：W(t,Δ) = 时刻 t 之前 Δ 时间窗口内访问过的页集合。给每个进程的驻留集 ≥ W。
• 缺页频率 PFF：监控缺页率，过高 → 加分配；过低 → 减分配

程序结构与缺页

同样的逻辑，按行 vs 按列访问 NxM 数组缺页次数可相差 N 倍（行优先存储时按行访问最佳）。

// 假设页大小 4KB, int 4B, 1页=1024个int
// 二维数组 1024×1024 行优先

// 好: 按行访问
for(i=0; i<1024; i++)
  for(j=0; j<1024; j++)
    a[i][j] = 0;    // 缺页 1024 次

// 差: 按列访问
for(j=0; j<1024; j++)
  for(i=0; i<1024; i++)
    a[i][j] = 0;    // 缺页 1024×1024 次!

文件控制块 FCB

每个文件对应一个 FCB（也叫 inode），存元信息。

inode 内容：
类型 / 大小 / 时间戳
权限 (r/w/x × user/group/other)
链接计数
数据块指针（12 直接 + 1/2/3 级间接）

三种目录结构

• 单级：一张表，名字必须全局唯一
• 两级：每用户一目录
• 树形：路径唯一标识；分相对路径 / 绝对路径
• 图形：允许硬链接（共享 inode）

软链接 vs 硬链接

文件保护

• 访问控制表 ACL
• 访问权限：r / w / x / append
• Unix 权限：rwxrwxrwx（owner/group/other）
• 口令 / 加密

三种文件分配

Unix 混合索引

空闲管理

• 空闲表：连续区段，类似分区
• 空闲链：所有空闲块串成链
• 位示图：1 bit/块；1=分配，0=空闲
  n 块磁盘需 n bit = ⌈n/8⌉ 字节
• 成组链接：每 100 块为一组，组首块存指向下一组的指针

位示图计算

字号 i, 位号 j, 每字 32 bit
块号 b = 32·i + j
反过来 i = b / 32, j = b % 32

磁盘访问时间

T = T_寻道 + T_旋转 + T_传输
// 寻道占主导，调度优化的就是这一项

5 种调度算法

4 种 IO 控制方式

缓冲 + SPOOLing

• 单缓冲：完成 IO 时 CPU 才能继续
• 双缓冲：CPU 与 IO 可并行
• 循环缓冲：多个缓冲区轮换
• SPOOLing：用磁盘虚拟独占设备（打印机），输入井 / 输出井，提交即返回