第 24 讲：操作系统总复习与解题主线

这一讲不再重讲一遍所有定义，而是依照课程总复习的范围，把知识点放进几条可追踪的状态链。考试题看似分成分页、PV、调度、磁盘和文件系统，底层共同问题却是：一个请求当前处于什么状态，它缺什么，谁能使条件成立，成立后转到哪一态。

课程总图：四种资源，一个执行链

资源/抽象	关键状态	谁做决策	典型异常/等待
CPU/进程线程	就绪、运行、阻塞	调度器	时间片、I/O 阻塞、唤醒
内存/地址空间	映射、驻留、权限、脏页	MMU + 内存管理器	TLB miss、缺页、保护异常
设备/I/O 请求	排队、执行、完成、错误	I/O 子系统+驱动+控制器	中断、DMA 完成、超时
磁盘块/文件	空闲、已分配、缓存、脏、已持久	文件系统+块层	cache miss、日志恢复、空间不足

一个程序读文件可串起所有列：进程执行 read→陷入内核→VFS 用 fd 找打开文件和 inode→块 cache 未命中→驱动提交 DMA→进程阻塞，调度别人→设备完成中断→唤醒原进程→把数据交付用户缓冲→返回用户态。

概论要能回答的问题

批处理、多道和分时有什么差别

• 批处理用自动作业衔接减少人机空档；
• 多道程序让多个程序同时驻留，某个等 I/O 时 CPU 运行另一个，目标是利用率/吞吐；
• 分时再用时间片为多个交互用户提供较短响应，目标不只是 CPU 利用率。

多道是分时的基础之一，但两者不是同义词。

中断、陷入和缺页分别是什么

• 中断通常是 CPU 外部事件，与当前指令异步；
• 系统调用/陷入是程序主动通过受控入口请求内核服务；
• 缺页是当前指令地址转换时发现页未驻留/需特殊处理的同步异常，合法时可调页后重启原指令；
• 访问一个从未映射或权限不允许的地址，也可通过同一页异常入口进内核，但内核判断为非法后不会用“换入一页”修好。

内存管理复习骨架

功能

• 分配与回收；
• 地址转换/重定位；
• 越界和读写执行保护；
• 同一物理区的受控共享；
• 用覆盖、交换、虚拟存储从逻辑上扩大可用容量。

四种管理必须能对比

方式	分配单位	主要碎片	映射结构
动态分区	可变长连续区	外部碎片	基址+界限
分页	固定大小页	页内碎片	页表
分段	逻辑可变长段	外部碎片	段表（基址+段长）
段页式	逻辑段+物理页	页内碎片+表开销	段表→每段页表

地址转换必背不如必会

1. 由页大小确定 offset 位数；
2. 切出各级索引，从页表根逐级走；
3. 检查存在位和权限；
4. PFN 与原 offset 拼成物理地址；
5. 分清 TLB miss、合法缺页、保护异常。

总复习单列的“自映射”是页表管理技巧：让页目录的一项指回页目录自身，把页目录和各页表暴露在固定虚拟窗口中。做地址题仍按多级索引转换，区别只是某个索引对应的是页表结构本身。

虚拟内存不只是置换表格

要会解释局部性为什么支持按需调页，一次缺页如何验证地址、选页框、回写脏页、读入、更新页表和重启指令；再在此基础上模拟 OPT、FIFO、Clock 和 LRU。

页框不足以容纳工作集时，会抖动；解决方法不只是换一个更复杂的页算法，还可能必须增加驻留集或减少并发进程。

进程与同步复习骨架

进程概念

• 并发是生命周期重叠，并行是真正同时执行；
• 进程是资源/保护边界，线程是 CPU 调度执行流；
• 就绪只缺 CPU，阻塞即使给 CPU 也必须等事件；
• PCB 记身份、CPU 现场、调度、内存和资源状态；
• 系统调用的模式切换不必然改变当前进程，上下文切换才会换 PCB/地址空间。

同步题目的三张表

先列：

1. 共享数据/资源是什么；
2. 哪些操作必须互斥，哪些存在先后/数量条件；
3. 每个信号量的物理含义和初值。

再写 P/V。互斥锁初值 1，事件/数据尚未产生初值 0，容量 token 初值等于当初可用份数。检查：

• 有没有在持有 mutex 时等一个只能由拿同一 mutex 的人产生的条件；
• 数量不变式（如 empty+full=N）是否在所有路径保持；
• 是否可能死锁或让某类进程饥饿。

调度复习骨架

一道调度题的顺序：

1. 记录到达时间、服务时间、优先级和时间片；
2. 每个到达、完成、阻塞/唤醒和时间片到期都是决策点；
3. 在决策点先更新就绪集，再按算法选择；
4. 画 Gantt 图，从图算完成 $C_i$、周转 $C_i-A_i$、等待 $(C_i-A_i)-S_i$ 和首次响应；
5. 抢占式算法用剩余时间，RR 对同时到达/时间片到的入队顺序要按题设。

算法目标：FCFS 简单按到达公平；SJF/SRTF 照顾短任务和平均等待；HRRN 用等待时间防长任务无限延迟；RR 照顾交互响应；MLFQ 根据实际 CPU/I/O 行为动态归类。

死锁复习骨架

死锁四条必要条件：互斥、请求并保持、不可剥夺、循环等待。四种处理：

• 预防：静态破坏一个必要条件；
• 避免：银行家算法只批准仍保持安全序列的请求；
• 检测：从资源分配图/矩阵找不能化简的进程集；
• 解除：终止、剥夺或回滚，并以最小代价选牺牲者。

银行家题先独立验算：

$$Need=Max-Allocation,$$ $$Available=Total-\sum_i Allocation_i.$$

找安全序时用 Work=Available，每找到一个 Need_i <= Work 的进程，假想它完成并做 Work += Allocation_i。只列出一串进程名而不写 Work 变化，很难发现自己某一类资源已不足。

设备与磁盘复习骨架

控制方式的递进

轮询：CPU 等设备且常亲自搬数据
  ↓ 用中断告知就绪
中断驱动：CPU 不忙等，但小数据搬运/中断仍多
  ↓ 用 DMA 整块搬运
DMA：CPU 设起址/长度/方向，整块完成再中断
  ↓ 让专用 I/O 处理器执行程序
通道：进一步减少 CPU 对 I/O 序列的干预

软件分层是用户调用→设备无关层→驱动→中断/控制器。缓冲提高 CPU 与设备并行性、吸收速度抖动，但不会把长期生产速度变得超过最慢环节。

磁盘计算

$$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}.$$

先将 RPM 换成转/秒。磁盘调度用服务顺序画磁头路线，总移动是相邻柱面差绝对值之和。特别注明 SCAN 是否到物理端点，C-SCAN 回端点的路程也要算移动。

文件系统复习骨架

用一条路径层层追问：

1. 起点是根目录还是当前目录？
2. 每级目录项把名字映射到哪个 inode/FCB？
3. inode 如何将文件逻辑块映射到物理块？
4. 目标块在 block cache 吗？不在就如何发起设备 I/O？
5. 发生写入时，哪些数据块、位图、inode 和目录项都需改，如何保持崩溃一致？

连续分配随机访问快但增长难；链接分配增长易但随机访问慢；索引分配用索引空间换随机定位。硬链接是多个目录名指同一 inode，软链接是一个内容为路径的独立文件。VFS 用 superblock、inode/vnode、dentry 和 file 等通用对象，将统一系统调用分派给 FAT、Ext2 等具体实现。

五类必须会算的题

1. 分页地址

页大小→偏移位数→VPN/多级索引→查页表→PFN+原偏移。若有 TLB，分命中/未命中计内存访问次数；不要把 TLB miss 自动当 page fault。

2. 页面置换

画固定数页框，每个引用更新状态和缺页数。FIFO 命中不修改调入年龄；LRU 命中会更新最近使用顺序；Clock 命中要置访问位，置换扫描时遇 1 清 0 给第二次机会。

3. 信号量

先写每个信号量的句子含义，再写初值。用 token 守恒检查 P/V 是否成对，用锁等待图检查是否持锁等条件导致环。

4. 调度/银行家

调度画 Gantt 图；银行家写 Work 每一步增量。两者共同点是：不能跳过中间状态只写最终顺序。

5. 磁盘/文件索引

磁盘先列服务柱面顺序，再加绝对差；文件偏移先除块大小得逻辑块与块内偏移，再判直接/间接层级。

最后一次自检

• 我是在说资源的物理状态，还是进程看到的抽象？
• 这个进程缺 CPU 还是缺事件？是就绪还是阻塞？
• 这个地址是 TLB 里没有、页未驻留，还是根本无权访问？
• 这个 I/O 完成指设备已就绪，还是数据已经交付用户缓冲？
• 这个算法优化的是平均、尾延迟、吞吐、公平还是截止期？代价是什么？
• 我写的顺序是一个可验证的状态转换，还是只列了几个算法名？

如果这六个问题都能说清，操作系统就不再是一堆孤立的名词，而是一套把请求、资源和状态组织起来的因果网络。