OS考点总结

总体结论

这些卷子的重点非常稳定。几乎每年都会围绕下面几类题展开：

1. UNIX 进程与系统调用：fork、wait、sleep、open、read、write、dup、管道、I/O 重定向、文件描述符和打开文件表。
2. 作业/进程调度与内存管理混合题：FCFS、SJF、优先级、RR、多级反馈队列，常和主存分配、设备静态分配一起考平均周转时间。
3. 死锁：银行家算法、安全序列、资源请求能否满足、死锁检测、死锁必要条件。
4. 请求分页：页表规模、二级页表地址划分、反置页表、页表项字段、缺页异常、NRU/LFU/LRU/Aging/Clock/FIFO。
5. UNIX 文件系统：inode 直接/间接索引、目录项、open 内核路径、硬链接/软链接、文件描述符复制、逻辑块到物理块、读写物理块数。
6. 磁盘调度与同步编程：FCFS/SSTF/SCAN/C-SCAN/电梯调度、读者写者、管程、信号量、匿名管道。

复习优先级建议：

优先级	内容	原因
必拿	fork 进程树、管道重定向、文件描述符共享	2016、2017、2018、2020、2021、2022 都考
必拿	银行家算法/死锁检测	2016、2017、2018、2019、2020、2021、2022 都考
必拿	请求分页和页面置换	2016、2017、2018、2020、2021、2022 都考
必拿	inode 索引计算、open/read/write/dup/link	2016、2017、2018、2020、2021、2022 都考
高频	作业调度、平均周转时间、RR 平分 CPU	2016、2017、2018、2020、2021、2022 都考
高频	磁盘调度与容量/旋转延迟	2016、2017、2018、2019、2020、2021、2022 都考
高频	管程/信号量编程	每年第二大题常考

一、进程调度

1. 基本指标

常用时间定义：

• 到达时间：作业/进程到达系统或就绪队列的时间。
• 开始时间：第一次获得 CPU 或进入主存创建进程的时间，题目要看语境。
• 完成时间：运行结束时间。
• 周转时间 = 完成时间 - 到达时间。
• 带权周转时间 = 周转时间 / 实际运行时间。
• 平均周转时间 = 所有作业周转时间之和 / 作业数。
• 平均带权周转时间 = 所有带权周转时间之和 / 作业数。

易错点：

• “进入主存时间”和“开始运行时间”不是同一个概念。多道程序设计系统中，作业进入主存后可能与其他作业 RR 平分 CPU。
• RR 题如果说“时间片远小于各作业运行时间”，通常表示多个驻留作业近似平均分享 CPU。
• 作业调度决定谁进入内存；进程调度决定内存中的进程谁占 CPU。卷子常把两层调度混在一题里。

2. FCFS

先来先服务，按到达顺序运行。

特点：

• 实现简单。
• 对长作业有利，对短作业不利。
• 容易产生 convoy effect，短作业排在长作业后面会等待很久。

计算套路：

1. 按到达时间排序。
2. 当前时间小于下一作业到达时间时，CPU 空闲到该作业到达。
3. 完成时间逐个累加运行时间。
4. 计算周转时间和带权周转时间。

3. SJF/SPF

短作业优先，选择估计运行时间最短的作业。

特点：

• 在所有作业同时到达、运行时间已知时，平均周转时间最短。
• 可能导致长作业饥饿。
• 实际系统难点是预测运行时间。

证明思路：

若两个相邻作业运行时间分别为 a 和 b，且 a > b。把顺序从 a,b 交换为 b,a，后续作业完成时间不变，这两个作业总等待/周转时间减少 a-b。不断交换逆序长短作业，可得按运行时间升序时平均周转时间最小。

4. RR

时间片轮转，适合分时系统。

特点：

• 公平，响应时间较好。
• 时间片过短，调度开销大；时间片过长，退化为 FCFS。
• 考题常问调度开销百分比。

例：时钟中断每秒 100 次，每次中断处理 1ms；RR 以 10 个时钟中断为 1 个时间片；一次调度 2ms，分派 CPU 1ms。时间片长度 10 * 10ms = 100ms，每个时间片内开销为 10 * 1 + 2 + 1 = 13ms，CPU 调度相关开销为 13%。

5. 优先级调度

注意题目会说明“优先数越小优先级越高”或相反。不要按常识假设。

抢占式：

• 高优先级进程到达后可抢占 CPU。
• 响应紧急任务好。
• 调度频繁，开销大，低优先级可能饥饿。

非抢占式：

• 已运行进程不主动让出 CPU 前不会被抢占。
• 开销较小。
• 高优先级任务可能等待长作业结束。

6. MLFQ

多级反馈队列的核心思想：

• 多个优先级队列，高优先级队列时间片短，低优先级队列时间片长。
• 新进程通常先进高优先级队列。
• 用完时间片仍未结束则降级。
• I/O 密集型进程经常阻塞并让出 CPU，容易保持较高优先级；CPU 密集型进程会逐步降级。
• 为避免饥饿，需要周期性提升优先级或 aging。

答题要点：

• 它是对进程行为的动态预测：过去经常很快让出 CPU 的进程更可能是 I/O 密集型，应给予较好响应。
• 设计关键是预测进程行为和避免长期饥饿。

二、请求分页与页面置换

1. 地址划分与页表大小

基本公式：

• 页内偏移位数 = log2(页面大小)。
• 虚页号位数 = 逻辑地址位数 - 页内偏移位数。
• 一级页表项数 = 逻辑地址空间 / 页面大小 = 2^虚页号位数。
• 一级页表最大大小 = 页表项数 * 页表项大小。
• 页框号位数 = log2(物理内存 / 页面大小)。

二级页表划分：

1. 每个页表页能放的页表项数 = 页面大小 / 页表项大小。
2. 页表页内索引位数 = log2(每页表项数)。
3. 页目录位数 = 虚页号位数 - 页表页内索引位数。

常见例子：

• 32 位逻辑地址，4KB 页面，4B 页表项：偏移 12 位；一个页表页有 4096/4 = 1024 = 2^10 项；二级页表为 10 位页目录 + 10 位页表页索引 + 12 位偏移。
• 32 位逻辑地址，1KB 页面，4B 页表项：偏移 10 位；一个页表页有 1024/4 = 256 = 2^8 项；虚页号 22 位，所以二级页表为 14 位页目录 + 8 位页表页索引 + 10 位偏移。
• 32 位逻辑地址，2KB 页面，4B 页表项：偏移 11 位；一个页表页有 2048/4 = 512 = 2^9 项；二级页表为 12 位页目录 + 9 位页表页索引 + 11 位偏移。

多级页表优缺点：

• 优点：页表不需要连续存放；没有使用的虚拟地址范围不必分配页表页，节省内存。
• 缺点：地址转换需要多次访存，若无 TLB 会明显变慢。

反置页表：

• 表项数按物理页框数算：物理内存 / 页面大小。
• 表项至少要包含进程号和虚页号，用来说明该物理页框属于哪个进程的哪个虚页。
• 优点：全系统维护一张与物理内存大小相关的表，节省内存。
• 缺点：地址转换查找复杂；未调入内存的页面仍需其他结构记录，缺页处理可能更慢。

2. 页表项字段

常考字段：

• 页框号：该页在物理内存中的位置。
• 存在位/驻留位/有效位：是否在内存中，不在则触发缺页异常。
• 访问位/引用位 R：最近是否被访问，常由硬件置 1，由 OS 周期性清 0。
• 修改位/脏位 W/M：是否被写过，脏页淘汰前必须写回磁盘。
• 保护位：读/写/执行权限。
• 锁定位：某些关键页面暂时不能被替换，2022 卷在 CALL 指令多次缺页中考过。
• 外存地址：不在内存时页面所在的磁盘位置。

易错点：

• R=0 且 W=1 是可能的：页面以前被写过，尚未写回磁盘；之后 OS 清零了 R 位，但不会因此清零 W 位。
• 写访问一定会置 R 和 W；读访问只置 R。
• 脏页不是不能淘汰，而是淘汰成本更高，需要写回。

3. 缺页异常处理

标准流程：

1. CPU 访问虚拟地址，查页表/TLB。
2. 有效位为 0，触发缺页异常，陷入内核。
3. OS 检查地址是否合法、权限是否允许。
4. 找空闲页框；若没有空闲页框，运行页面置换算法选牺牲页。
5. 若牺牲页是脏页，先写回磁盘。
6. 从外存调入目标页，更新页表项。
7. 恢复被中断指令，重新执行。

4. 页面置换算法

FIFO：

• 淘汰最早进入内存的页。
• 实现简单。
• 可能有 Belady 异常。

LRU：

• 淘汰最长时间未被访问的页。
• 理论效果好，但精确实现代价大，需要维护全序访问历史或特殊硬件。
• 常用近似算法：NRU、Clock、Aging、NFU。

NRU：

• 根据 R/M 位分类。
• 优先淘汰 (R=0, M=0)；其次 (0,1)；再 (1,0)；最后 (1,1)。
• 周期性清 R 位，才有“最近未使用”的信息。

Clock：

• FIFO 环形队列 + R 位。
• 指针扫描；遇到 R=1 清 0 并跳过；遇到 R=0 淘汰。
• 增强版 Clock 会结合 M 位，优先干净页。

NFU：

• 每个页面维护计数器，每次时钟中断把 R 位加到计数器。
• 淘汰计数最小者。
• 缺点：早期频繁访问的页面即使后来不用，计数仍很大。

Aging：

• 每个页面维护 n 位寄存器。
• 每次时钟中断右移一位，把当前 R 位放到最高位，然后清 R。
• 寄存器值越小，越久未使用，优先淘汰。
• 要接近 LRU：采样周期要合适，寄存器位数要足够，且每次采样后清 R 位。

OPT：

• 淘汰未来最长时间不会被访问的页。
• 实际不可实现，但可作为评价其他算法的理论下界。

5. 颠簸与工作集

颠簸：系统频繁缺页，大量时间用于换入换出，CPU 利用率下降。

避免条件：

• 同时运行进程的工作集总大小不能超过可用物理内存。
• 页面分配不能过少。
• 页面置换算法应利用局部性，减少不必要淘汰。

三、死锁与银行家算法

1. 死锁四个必要条件

1. 互斥：资源一次只能被一个进程使用。
2. 占有并等待：进程已占有资源，同时还等待其他资源。
3. 不可剥夺：资源不能被强制抢走。
4. 循环等待：存在进程等待环。

破坏策略：

• 静态分配所有资源：破坏“占有并等待”。
• 资源有序申请：破坏“循环等待”。
• 可抢占资源：破坏“不可剥夺”。

2. 银行家算法

常用矩阵：

• Available：当前可用资源。
• Max 或 Claim：最大需求。
• Allocation：已分配。
• Need = Max - Allocation：尚需资源。

安全性检测：

1. Work = Available。
2. Finish[i] = false。
3. 找一个 Finish[i] == false 且 Need[i] <= Work 的进程。
4. 假设它能完成，令 Work = Work + Allocation[i]，Finish[i] = true，加入安全序列。
5. 重复直到所有进程完成，或找不到可完成进程。
6. 全部完成则安全；否则不安全。

资源请求判断：

1. 检查 Request[i] <= Need[i]，否则超过最大声明，拒绝。
2. 检查 Request[i] <= Available，否则暂不能分配。
3. 试分配：
   • Available -= Request[i]
   • Allocation[i] += Request[i]
   • Need[i] -= Request[i]
4. 再做安全性检测。
5. 试分配后安全才真正分配；否则回滚并拒绝。

易错点：

• “不安全”不等于“已经死锁”。不安全表示未来可能死锁。
• 死锁检测用的是当前 Request，银行家算法用的是最大需求 Max/Claim 和 Need。
• 题目中 Claim 有时表示最大需求，有时表头会同时给 Request。先看题干定义。
• 向量比较是逐项比较，不能只比较总数。

3. 死锁检测

检测算法通常用当前请求矩阵：

1. Work = Available。
2. 没有资源分配的进程可直接 Finish=true，因为它不参与死锁。
3. 找 Request[i] <= Work 的进程，假设它完成并释放资源。
4. 最后仍 Finish=false 的进程就是死锁进程。

资源分配图：

• 有环不一定死锁，若每类资源多个实例，需要继续检测。
• 若每类资源只有一个实例，有环就是死锁。

四、进程管理与系统调用

1. API 与系统调用

系统调用：

• OS 提供给用户程序进入内核态请求服务的接口。
• 一定会陷入内核态。
• 例：fork、exec、wait、open、read、write、close、dup。

API 函数：

• 程序库提供的接口。
• 可能直接在用户态完成，也可能封装一个或多个系统调用。
• 例：printf 是 C 库函数，可能最终触发 write；getpid 可封装系统调用。

直接使用系统调用的弊端：

• 代码复杂，可读性差。
• 平台差异大，可移植性差。
• 需要自己处理更多细节和错误码。

2. fork

核心语义：

• 调用一次，返回两次。
• 父进程返回子进程 pid。
• 子进程返回 0。
• 失败返回负数。
• 父子进程拥有独立地址空间，普通变量互不影响。
• 文件描述符表会复制，但指向同一个系统打开文件表项，因此共享文件偏移量。

进程数计算：

• 遇到无条件 fork()，当前已有多少个进程，就会新增多少个子进程，总数翻倍。
• 遇到条件分支，要分别追踪父子返回值。
• wait 只改变执行顺序/回收子进程，不会创建进程。

输出不确定性：

• 父子进程调度顺序不确定。
• 多个进程 printf 的行顺序不确定。
• 如果没有关闭缓冲或没有换行，输出还可能受缓冲影响。

3. exec

语义：

• 用新程序替换当前进程的用户态地址空间。
• pid 不变。
• 成功后不返回到原程序；失败才返回错误。
• 常和 fork 配合：子进程 exec 新程序，父进程 wait。

4. wait/waitpid

作用：

• 父进程等待子进程结束。
• 回收子进程退出状态，避免僵尸进程。
• 若没有已结束子进程，调用者进入等待态。

常考表述：

• 内核把调用进程从运行态转为等待态。
• 子进程结束后产生唤醒，父进程回到就绪态。

5. 管道与 I/O 重定向

管道：

• Shell 先创建管道，再 fork 出命令进程。
• 前一个命令的标准输出重定向到管道写端。
• 后一个命令的标准输入重定向到管道读端。
• 匿名管道常用于有亲缘关系的进程。
• 有名管道可通过文件系统路径让无亲缘关系进程通信。

常见 IPC：

• 管道
• 消息队列
• 共享内存
• 信号
• 套接字

I/O 重定向：

• 本质是修改文件描述符表，让 fd 0/1/2 指向文件或管道。
• dup/dup2 常用于把某个文件描述符复制到标准输入或标准输出。
• > 是标准输出重定向到文件。
• < 是标准输入从文件读取。
• cmd1 | cmd2 中 cmd1 的 stdout 到管道，cmd2 的 stdin 从管道。

五、文件系统结构

1. inode 与目录项

inode 保存：

• 文件类型、权限、属主、时间戳、大小。
• 链接计数。
• 数据块地址索引：直接索引、一级间接、二级间接、三级间接。

目录文件保存：

• 目录项：文件名 + inode 号。
• 目录本身也是文件，内容是目录项。

普通文件与目录文件区别：

• 普通文件内容是用户数据。
• 目录文件内容是目录项，描述该目录下有哪些名字以及对应 inode。

2. 文件最大尺寸

若：

• 物理块大小为 B 字节。
• 每个索引项大小为 e 字节。
• 直接索引项数为 d。
• 每个索引块可存索引项数 n = B/e。

则最大文件大小：

(d + n + n^2 + n^3) * B

例：

• inode 有 10 个直接索引，1KB 块，4B 索引项，n=256。
• 最大大小 = (10 + 256 + 256^2 + 256^3) * 1KB。

2022 变体：

• 12 个直接索引，1KB 块，4B 索引项。
• 最大大小 = (12 + 256 + 256^2 + 256^3) * 1KB。
• inode 中文件物理结构信息占 15 * 4 = 60B，因为 12 个直接 + 1 个一级 + 1 个二级 + 1 个三级，共 15 个索引项。

3. 目录大小与磁盘空间

目录文件大小：

目录项数量 * 每个目录项大小

占用磁盘空间：

• 至少按物理块取整。
• 若目录数据块数超过直接索引范围，还要额外占用间接索引块。

例：

• 每个目录项 16B，目录下 610 个文件 + 40 个子目录，共 650 项。
• 目录大小 650 * 16 = 10400B。
• 物理块 1KB，则目录数据需要 11 个物理块。
• 若直接索引只有 10 个，还需要 1 个一级间接索引块，所以共占 12 个物理块。

4. open 内核过程

标准答法：

1. 用户态调用 open，陷入内核。
2. 根据路径逐级查目录，找到目标文件目录项和 inode 号。
3. 若 inode 已在活动 inode 表中，增加引用；否则从磁盘读入 inode，建立活动 inode 表项。
4. 检查权限和打开方式。
5. 建立系统打开文件表项，记录读写方式、当前文件偏移量、指向活动 inode 的指针、引用计数等。
6. 在当前进程用户打开文件表中找空项，指向系统打开文件表项。
7. 返回该用户打开文件表下标，即文件描述符 fd。

5. read/write 内核过程

read(fd, buf, n)：

1. 通过 fd 查当前进程用户打开文件表。
2. 找到系统打开文件表项，获得当前偏移量和活动 inode。
3. 检查打开方式是否允许读。
4. 根据 inode 索引把逻辑块号转换为物理块号。
5. 从磁盘或缓存读入数据到内核缓冲，再复制到用户缓冲区。
6. 更新文件偏移量。
7. 返回实际读入字节数。

write(fd, buf, n)：

1. 同样通过 fd 找系统打开文件表和 inode。
2. 检查是否以写方式打开。
3. 根据偏移量定位或分配数据块。
4. 把用户数据写入缓存/磁盘。
5. 更新偏移量、文件大小、inode 修改时间等。
6. 若打开方式不允许写，返回错误码。

易错点：

• fork 后父子进程复制用户打开文件表，但指向同一个系统打开文件表项，所以共享偏移量。
• 分别 open 同一文件会产生不同系统打开文件表项，偏移量独立。
• dup 复制的是文件描述符，使两个 fd 指向同一个系统打开文件表项，偏移量共享，引用计数增加。

6. 硬链接与软链接

硬链接：

• 新目录项指向同一个 inode。
• inode 链接计数加一。
• 不新增目标文件 inode。
• 通常不能跨文件系统，通常不链接目录。
• 访问快，实现简单。

软链接/符号链接：

• 新建一个特殊文件，内容是目标路径。
• 有自己的 inode。
• 可跨文件系统，可链接目录。
• 访问时需要解析路径，开销较大；目标删除后可能悬空。

六、历年试卷考点总结

2016-2017

题型概况：

• Q1 UNIX 代码：open("data.txt", O_RDONLY)、两次 fork、read(fd, buffer, 2)、getpid、printf、waitpid。考进程树、输出结果、open 系统调用过程。
• Q2 调度理论：所有作业同时到达，FCFS 平均周转时间/平均带权周转时间公式；证明 SJF 平均周转时间最短；SJF 导致长作业饥饿。
• Q3 死锁：给资源总量、已分配、申请、最大需求；用死锁检测判断是否死锁；讨论银行家算法实际困难。
• Q4 请求分页：32 位、1GB 物理内存、2KB 页面、4B 页表项；一级页表项数、二级页表地址划分、反置页表项数；给地址序列和 3 个页框，用 LRU 求页号序列、页框变化和物理地址。
• Q5 文件系统：目录树、目录项大小、目录文件块结构；按链接结构/顺序结构读取文件第 15 块的最少/最多启动磁盘次数。
• Q6 磁盘：位图管理空闲块、磁盘容量、C-SCAN 调度、寻道时间/旋转延迟/传输时间。
• 编程题：按进程间优先关系图，用信号量 P/V 写并发程序。

注意点：

• fork 后共享打开文件表偏移，所以四个进程依次读到 ab、cd、ef、gh，但输出行顺序由调度决定。
• SJF 最优证明要写“相邻交换”或“短作业在前使加权累加项最小”，不能只写结论。
• 死锁检测和银行家算法要区分：检测当前是否已死锁；银行家避免未来进入不安全状态。

2017-2018

题型概况：

• Q1 Shell 管道：cat file1 file2 | sort，考输出、两个子进程关系、管道特点、IPC。
• Q2 调度：两道批处理系统；作业调度按优先数，进程调度 RR；求进入主存时间、结束时间、平均周转和平均带权周转；比较批处理和分时系统。
• Q3 银行家算法：判断安全序列；判断 P1 请求能否满足；若满足后再给一组请求，用死锁检测找死锁进程。
• Q4 请求分页：32 位、1GB、4KB 页面、4B 页表项；一级/二级页表；访问逻辑地址 12300；NRU/LFU/Aging 选牺牲页；颠簸和最佳页面大小。
• Q5 UNIX 文件系统：inode 直接/间接索引，open 过程磁盘读取次数，父子进程读文件物理块数，文件占用空间和最大文件大小，link 硬链接过程。
• Q6 磁盘：容量、读写速率、平均旋转等待、位示图大小、FCFS/SSTF/电梯调度。
• 编程题：管程实现读者写者问题。

注意点：

• 二级页表计算必须写出页内偏移 12 位、页表页索引 10 位、页目录 10 位。
• 12300/4096 = 3，所以访问 3 号页；题中驻留 1、2、4、5，因此缺页。
• 最佳页面大小公式：f(p)=se/p+p/2，这里最优为 8KB，所以 4KB 不合理。

2018-2019

题型概况：

• Q1 UNIX 代码：API 与系统调用区别；fork 实现；进程树；getpid/getppid/sleep/printf 输出。
• Q2 作业调度与内存：Buddy 伙伴系统、FCFS 作业调度、RR 平分 CPU，列进入主存/结束时间和关键内存状态。
• Q3 死锁：进程-资源分配图检测；线程使用锁是否可能死锁，OS 能否检测应用内部锁死锁。
• Q4 请求分页：分页缺点、多级页表/TLB；反置页表；给逻辑地址序列和 3 页框，用 LRU 求页框变化和后续物理地址；LRU 实现困难、NRU/Aging 近似；OPT 意义。
• Q5 文件系统：根目录最多文件数、inode 区最多文件数、目录文件占块数、硬链接/软链接、open 内核过程。
• Q6 磁盘：CHS 请求、电梯调度、同柱面扇区优化、读请求和写请求区别。
• 编程题：用管程实现匿名管道，容量 K 的环形队列，read/write 阻塞条件。

注意点：

• 反置页表项数按物理页框算：2GB/4KB = 2^19。
• LRU 精确实现通常不可行，理由是维护精确最近访问顺序代价大。
• 目录文件数据块超过直接索引数时，要额外算间接索引块。

2019-2020

题型概况：

• Q1 中断与 RR 调度开销：时钟中断频率、中断处理、调度、分派 CPU 的时间比例。
• Q2 SPOOLing：比较采用/不采用 SPOOLing 的总运行时间。
• Q3 银行家算法：状态是否安全；P2 请求能否分配；证明满足某个最大需求条件时不会死锁。
• Q4 可变分区：首次适应、最佳适应能否装入作业序列，画内存队列。
• Q5 文件系统一致性：空闲块/分配块不一致、丢失盘块、重复分配等。
• Q6 磁盘 I/O：SSTF、SCAN、C-SCAN 移动臂总量；用信号量或管程实现 SCAN 调度。
• 编程题：猴子过峡谷问题，用信号量避免相反方向同时通过产生死锁。

注意点：

• RR 调度开销题不要漏掉引起调度的多个时钟中断处理时间。
• SPOOLing 的关键是预输入、缓输出和 CPU 处理可重叠。
• 文件系统一致性题要区分“空闲表重复”“分配表重复”“既空闲又分配”“既不空闲也不分配”。

2020-2021

题型概况：

• Q1 Shell：cat fileA.txt fileB.txt | sort > sorted.txt，考输出文件、进程数、管道、IPC、输入/输出重定向。
• Q2 调度：作业调度 SJF，进程调度抢占式优先级；求进入主存/结束时间和平均周转；列常见调度算法；讨论 I/O 密集型和 CPU 密集型平衡；抢占/非抢占优缺点。
• Q3 银行家算法：安全性、P1 请求、P4 请求。
• Q4 请求分页：32 位、1GB、4KB 页面；二级页表划分；页表项字段；W 位从 1 到 0 的原因；访问地址 2000 缺页；LFU/Aging 选牺牲页；Aging 如何接近 LRU。
• Q5 文件系统：inode 最大文件大小、目录文件大小和磁盘占用、用户打开文件表/系统打开文件表/活动 inode 引用关系、read 过程和物理块数。
• Q6 磁盘调度：FCFS、电梯、SCAN、SSTF。
• 编程题：Hoare/Mesa 风格管程语义转换，用信号量模拟。

注意点：

• 地址 2000 在 4KB 页面下属于 0 号页，不是 2 号页。
• 选择牺牲页时，若计数相同，优先淘汰干净页，避免写回脏页。
• 管道和重定向题要指出：cat stdout 到管道，sort stdin 从管道，sort stdout 到 sorted.txt。

2021-2022

题型概况：

• Q1 UNIX 代码：产生 3 个进程，进程树，输出 Count: 20 多行；fork/sleep/printf；sleep 使进程等待。
• Q2 多道程序设计：可变分区、低地址优先、FCFS 作业调度、RR、设备静态分配；平均周转时间；列作业/进程调度算法；死锁四条件和静态分配破坏占有并等待。
• Q3 银行家与死锁：安全序列；P3 请求能否满足；修改分配和可用资源后检测死锁进程。
• Q4 请求分页：32 位、1GB、1KB 页面、4B 页表项；页表项理论最大数、页框号最大值、页表项信息；从页面大小合理性推断进程平均大小；R 位清零；NRU 替换；TLB 和缺页开销。
• Q5 文件系统：inode 区最多文件数、目录文件不同 inode 号/大小/占用空间；write 因只读打开失败；read 涉及间接索引块，共读几个物理块。
• Q6 磁盘调度：FCFS/SSTF/电梯顺序和移动量，SSTF 饥饿。
• 编程题：读者写者问题变体，同时读进程编号总数不大于 N，用 PV 操作实现。

注意点：

• 普通变量在 fork 后独立，所以每个进程自己的 count 不互相影响。
• 静态设备分配不是破坏互斥，而是一次性申请资源，破坏占有并等待。
• 最近未使用 NRU 题要结合 R 位和 W 位，优先淘汰未引用且干净的页。

2022-2023

题型概况：

• Q1 UNIX 代码：8 个进程、进程树、多种输出可能；setbuf/printf 与 I/O；fork/wait/getpid/getppid 与进程控制/同步；直接系统调用的弊端。
• Q2 可变分区：最优适应与最坏适应；作业创建/结束时间；内存用户区变化；内碎片和外碎片。
• Q3 自旋锁：单核关中断为何可实现临界区互斥；多核为何失效；基于 XCHG 实现 lock/unlock。
• Q4 死锁检测：给 Allocation、Request、Available，判断当前死锁进程；讨论死锁避免需要何时决策和掌握最大需求。
• Q5 请求分页：32 位、2GB、1KB 页面；页表理论最大尺寸；二级页表划分；多级页表优缺点；反置页表项数；R=0/W=1 原因；CALL 指令访问栈和目标页，FIFO/Clock/NRU 缺页次数；锁定位减少多次缺页。
• Q6 文件系统：inode 中物理结构信息大小；最大文件尺寸；fd 值含义和能否为 0；dup 用途与引用计数；缓存下逻辑块到物理块转换和实际读块数；程序输出。
• Q7 磁盘：FCFS/SSTF/电梯/SCAN 顺序和移动柱面数；同柱面请求归并和扇区循环排序。
• 编程题：管程实现最多 K 个读者的读者写者问题。

注意点：

• fd 一般从 0、1、2 之后开始分配，所以普通 open 常返回 3；如果先关闭 0，再 exec，新程序里 open 可能返回 0。
• dup 后多个 fd 指向同一系统打开文件表项，引用计数增加，共享偏移。
• 2022 分页题的二级划分是 14 + 8 + 10，不是常见的 10 + 10 + 12。

七、高频易错点清单

调度

• 优先数大小方向必须看题干。
• RR 平分 CPU 时，要动态统计同一时间在内存中的作业数。
• 平均周转时间用到达时间，不是进入主存时间，除非题目明确要求“作业驻留后”的指标。
• SJF 最短平均周转时间成立的前提是运行时间已知，且同一批作业可重新排序。
• 抢占式优先级中，新高优先级作业到达会打断当前进程。

分页

• 地址页号 = floor(逻辑地址 / 页面大小)，页内偏移 = 逻辑地址 mod 页面大小。
• 页表项大小影响二级页表划分，不影响页内偏移。
• 反置页表按物理页框数算，不按虚拟页数算。
• R 位会被 OS 周期性清零；W 位表示脏页，不会因为 R 清零而清零。
• Aging 寄存器是数值比较，值越小越久未访问。
• 脏页淘汰前要写回，所以同等条件下优先淘汰干净页。

死锁

• Need = Max - Allocation，不要把 Request 当 Need。
• 银行家算法的“请求可满足”必须试分配后仍安全。
• 不安全不等于死锁。
• 死锁检测最后未完成的进程才是死锁进程。
• 静态分配破坏占有并等待，不是破坏互斥。

UNIX 进程/系统调用

• fork 后普通变量各自独立，文件偏移可能共享。
• printf 是 API，不是系统调用；底层可能触发 write。
• exec 成功不返回，pid 不变。
• wait/sleep 会使调用进程进入等待态。
• Shell 管道命令通常创建两个命令子进程，Shell 是它们的父进程。
• 输出顺序不确定时，应说明由调度顺序决定。

文件系统

• 文件最大尺寸要把直接、一级、二级、三级全部算上。
• 目录文件大小按目录项数算，占磁盘空间按物理块向上取整。
• 数据块超过直接索引范围时，读数据可能还要读间接索引块。
• 硬链接不新增目标文件 inode，只新增目录项并增加链接计数。
• 软链接新增 inode，文件内容是路径。
• dup 和 fork 都可能增加系统打开文件表项引用计数，但一般不新增活动 inode。

八、例题

例题 1：SJF 与 FCFS

题目：三个作业同时到达，运行时间分别为 J1=8, J2=4, J3=2。分别用 FCFS 和 SJF 求平均周转时间。

解：

• FCFS 顺序 J1,J2,J3：完成时间分别为 8、12、14，平均周转时间 (8+12+14)/3 = 34/3。
• SJF 顺序 J3,J2,J1：完成时间分别为 2、6、14，平均周转时间 (2+6+14)/3 = 22/3。

注意：

• 同时到达时，完成时间就是周转时间。
• 若题目还要带权周转时间，要再除以各自运行时间。

例题 2：二级页表划分

题目：32 位逻辑地址，页面大小 1KB，页表项 4B，求二级页表地址划分。

解：

• 1KB = 2^10，页内偏移 10 位。
• 虚页号位数 = 32 - 10 = 22 位。
• 一个页表页能放 1KB/4B = 256 = 2^8 个页表项，所以页表页索引 8 位。
• 页目录位数 = 22 - 8 = 14 位。
• 划分：14 位页目录 + 8 位页表页索引 + 10 位页内偏移。

注意：

• 不要把 1KB 页面套成 4KB 的 10+10+12。

例题 3：Aging 页面置换

题目：某时刻 4 个驻留页的 Aging 寄存器为：页 1=1100，页 2=0111，页 3=1001，页 4=0111。页 2 是脏页，页 4 是干净页。发生缺页时淘汰谁？

解：

• Aging 值越小越久未访问。
• 页 2 和页 4 都是 0111，同为最小。
• 页 2 是脏页，淘汰需写回；页 4 干净。
• 因此优先淘汰页 4。

注意：

• 页面置换不只看算法主指标，参考答案常要求“结合 W 位考虑”。

例题 4：银行家算法请求能否满足

题目：某进程 P1 当前 Need=(1,2,0)，系统 Available=(1,1,1)。若 P1 请求 (1,1,0)，是否一定能分配？

解：

• 先看请求是否超过 Need：(1,1,0) <= (1,2,0)，通过。
• 再看请求是否超过 Available：(1,1,0) <= (1,1,1)，通过。
• 但不能直接说可以。必须试分配后运行安全性算法。
• 若试分配后仍存在安全序列，才可以；否则拒绝。

注意：

• 很多题的坑就在“资源够”但“分配后不安全”。

例题 5：fork 与打开文件表

题目：父进程 fd=open("data.txt") 后执行两次 fork()，然后每个进程执行 read(fd, buf, 2)。文件内容为 abcdefghijkl。如果读操作依次由 pid 2、3、4、5 执行，各自读到什么？

解：

• open 在 fork 前执行，所有子进程复制 fd，但 fd 指向同一个系统打开文件表项。
• 该系统打开文件表项的文件偏移量共享。
• 第一个进程读 ab，偏移变 2。
• 第二个读 cd，偏移变 4。
• 第三个读 ef，偏移变 6。
• 第四个读 gh，偏移变 8。

注意：

• 读到的内容由实际调度顺序决定，不一定按 pid 顺序。
• 如果每个进程分别 open 文件，则偏移量独立，结果不同。

例题 6：inode 最大文件大小

题目：inode 有 10 个直接索引项，一级/二级/三级间接索引各 1 个；物理块 512B；索引项 4B。求单个文件理论最大大小。

解：

• 每个索引块可存 512/4 = 128 个索引项。
• 直接索引可寻址 10 个数据块。
• 一级间接可寻址 128 个数据块。
• 二级间接可寻址 128^2 个数据块。
• 三级间接可寻址 128^3 个数据块。
• 最大大小 = (10 + 128 + 128^2 + 128^3) * 512B。

注意：

• 题目若问“占多少磁盘空间”，还可能要把间接索引块本身也算进去；若问“文件最大尺寸”，通常只算可存用户数据的大小。

例题 7：硬链接过程

题目：执行 link /test/demo.dat /demo.dat，文件系统主要做什么？

答题模板：

1. 查找 /test/demo.dat，得到目标文件 inode 号。
2. 查找新路径 /demo.dat 的父目录，即根目录。
3. 在父目录中增加目录项：名字 demo.dat + 目标 inode 号。
4. 将目标 inode 的链接计数 i_nlink 加一。
5. 不复制文件数据，不新增目标文件 inode。

注意：

• 硬链接是多个目录项指向同一个 inode。

九、考前速记

• 32 位 + 4KB + 4B PTE：二级页表 10/10/12。
• 32 位 + 1KB + 4B PTE：二级页表 14/8/10。
• 32 位 + 2KB + 4B PTE：二级页表 12/9/11。
• 反置页表项数 = 物理内存 / 页面大小。
• Need = Max - Allocation。
• 银行家：先检查 Request，再试分配，再安全性检测。
• fork：变量独立，打开文件表偏移可能共享。
• exec：成功不返回，pid 不变。
• dup：复制 fd，指向同一系统打开文件表项。
• 硬链接：同 inode，链接计数加一。
• 软链接：新 inode，内容是路径。
• SJF：平均周转时间优，但长作业可能饥饿。
• RR：时间片太小开销大，太大退化 FCFS。
• Aging：右移寄存器，R 放最高位，值越小越先淘汰。
• NRU：优先 (R=0,M=0)，再 (0,1)，再 (1,0)，最后 (1,1)。