考前 P0 必默写清单

用法

铁律：不看资料、不看本笔记，手写默出每道题完整推演。 不能默出来 = 没学会，回头再过对应章节。

推荐时间安排： - D-3：默 #1-#5（调度 + 银行家） - D-2：默 #6-#9（地址转换 + EAT + LRU + Belady） - D-1：默 #10（磁盘调度）+ 全部回扫错题

每题给两份内容：题面 + 标准答案。先盖住答案做题，做完对照。

#1 FCFS 调度（Ch2）

题面

求：执行顺序、每个作业的 tf/ti/wi、平均周转 T、平均带权 W。

答案

执行顺序：P1 → P2 → P3 → P4（按到达顺序）

T = (4+6+10+11)/4 = 31/4 = 7.75 W = (1+2+2+5.5)/4 = 10.5/4 = 2.625

易错点

• wi = ti / tk（实际花时 / 理论运行时间），永远 ≥ 1
• P4 wi = 5.5 体现 FCFS 致命缺陷：短作业被长作业拖累

#2 SJF 调度（Ch2）

题面

同 #1 的作业表，用 SJF 非抢占 算法。

答案

关键易错点：时刻 0 时只有 P1 到达，必须先跑 P1（即使知道 P4 是最短的）——OS 没有未卜先知的能力。

执行顺序：P1 → P4 → P2 → P3

推演： - 时刻 0：只有 P1 到达 → 跑 P1 [0, 4] - 时刻 4：P2/P3/P4 都到达，运行时间 P2=3, P3=5, P4=2 → 选 P4 - 时刻 6：P2/P3 等待，P2=3 < P3=5 → 选 P2 - 时刻 9：只剩 P3，跑 [9, 14]

T = (4+8+12+3)/4 = 27/4 = 6.75（比 FCFS 7.75 优） W = (1 + 8/3 + 12/5 + 1.5)/4 ≈ 1.89（比 FCFS 2.625 优 28%）

易错点

• 短作业 P4 的 wi 从 5.5 (FCFS) 降到 1.5——SJF 让短作业获益
• 长作业 P3 的 wi 从 2 升到 2.4——SJF 牺牲长作业
• SJF 致命缺点：长作业可能饥饿（短作业源源不断时永远轮不到）

#3 RR 时间片轮转（Ch2）

题面

同 #1 的作业表，时间片 q = 2，用 RR 算法。

答案

执行流程（约定：新到达 vs 时间片到期同时发生时，新到达先入队）：

时刻 0-2：P1 跑 2，剩 2，期间 P2(t=1), P3(t=2) 到达
   时刻 2 队列：[P2, P3, P1]
时刻 2-4：P2 跑 2，剩 1，期间 P4(t=3) 到达
   时刻 4 队列：[P3, P1, P4, P2]
时刻 4-6：P3 跑 2，剩 3
   时刻 6 队列：[P1, P4, P2, P3]
时刻 6-8：P1 跑 2，剩 0 → P1 完成
时刻 8-10：P4 跑 2，剩 0 → P4 完成
时刻 10-11：P2 跑 1（剩 1 ≤ q，跑完结束）→ P2 完成
时刻 11-13：P3 跑 2，剩 1
时刻 13-14：P3 跑 1 → P3 完成

T = 37/4 = 9.25（比 FCFS、SJF 都差！） W = ≈ 2.81

易错点

• 反直觉：RR 的 T 和 W 比 FCFS、SJF 都差——因为频繁切换损失了”让短作业快速结束”的机会
• RR 的真正价值：响应时间最优，适合分时系统不适合批处理
• 时间片 q 选择：太大退化为 FCFS，太小切换开销大

#4 HRRF 高响应比优先（Ch2）

题面

3 个作业，当前时刻 = 10：

求：每个作业当前的响应比 R，谁最优先？

答案

响应比公式：R = 1 + 等待时间 / 运行时间

A 和 C 平局（都 3）→ 平局规则按 FCFS 思路（早到优先）→ A 的 ts=2 < C 的 ts=8 → A 优先

易错点

• ❌ 公式漏 “1+”：写成 R = 等/运行 → R 可能小于 1（物理不可能）
• ❌ R sanity check：R 永远 ≥ 1，因为 R = 等待/运行 + 1，等待 ≥ 0
• 平局时按 FCFS 处理（早到优先）

#5 银行家算法（Ch3）

题面

系统资源 = 12，3 个进程：

求：Need、Available、是否安全、安全序列。

答案

Need：
  P1 = 10 - 5 = 5
  P2 = 4 - 2 = 2
  P3 = 9 - 2 = 7

Available = 12 - (5+2+2) = 12 - 9 = 3

推演：
  Work = 3,  找 Need ≤ 3：P2.Need=2 ✓ → P2 完成，Work = 3+2 = 5
  Work = 5,  找 Need ≤ 5：P1.Need=5 ✓ → P1 完成，Work = 5+5 = 10
  Work = 10, 找 Need ≤ 10：P3.Need=7 ✓ → P3 完成，Work = 10+2 = 12

全部完成 → 安全
安全序列 = P2 → P1 → P3

易错点

• ❌ 方向反：Need ≤ Work（需求 ≤ 供给），不是 Work > Need
• ❌ 缺初始化：必须明示 Work ← Available, Finish[i] ← false
• ❌ 只写”成功路径”：必须写”找不到 Need ≤ Work 进程 → 不安全”分支
• 抽象算法描述模板：找得到就走、找不到就停、停下后看完没完

#6 分页地址转换（Ch4）

题面

• 页大小 = 4KB = 4096 字节
• 逻辑地址 A = 8500
• 页表：页 0 → 页框 6，页 1 → 页框 2，页 2 → 页框 9

求物理地址。

答案

页号 p = ⌊8500 / 4096⌋ = 2
页内偏移 d = 8500 - 2 × 4096 = 8500 - 8192 = 308

sanity check：d = 308 < 4096 ✓

查页表：页 2 → 页框 9

物理地址 = 9 × 4096 + 308 = 36864 + 308 = 37172

易错点

• ❌ 物理地址停在表达式：9 × 4096 + 308 必须算成 37172，否则”答案不完整”扣分
• ❌ 偏移没检查 < L：sanity check 必做
• ❌ 页大小单位混乱：4KB 不等于 4000，是 4096

#7 TLB EAT（Ch4）

题面

• TLB 命中率 p = 90%
• TLB 访问时间 T_t = 10 ns
• 内存访问时间 T_m = 100 ns

求 EAT。

答案

公式：EAT = p × (T_t + T_m) + (1 - p) × (T_t + 2 × T_m)

EAT = 0.9 × (10 + 100) + 0.1 × (10 + 200)
    = 0.9 × 110 + 0.1 × 210
    = 99 + 21
    = 120 ns

或用化简版：EAT = T_t + (2 - p) × T_m = 10 + (2 - 0.9) × 100 = 10 + 110 = 120 ns ✓

易错点

• ❌ 公式两版混淆：含 TLB（这道）vs 含缺页（#8）是两个公式
• ❌ 题面命中率 vs 未命中率：题面给哪个，公式相应调整
• sanity check：p=1（全命中）时 EAT = T_t + T_m，p=0 时 EAT = T_t + 2T_m

#8 缺页 EAT（Ch4）

题面

• 内存访问时间 T_m = 200 ns
• 缺页中断处理时间 T_缺页 = 8 ms
• 缺页率 f = 0.0001（万分之一）

求 EAT，并算”相比无缺页时变慢了几倍”。

答案

T_缺页 = 8 ms = 8 × 10⁶ ns

EAT = (1 - f) × T_m + f × T_缺页
    = 0.9999 × 200 + 0.0001 × 8 × 10⁶
    = 199.98 + 800
    = 999.98 ns

变慢倍数 = 999.98 / 200 ≈ 5 倍

反直觉震撼

万分之一缺页率 = 慢 5 倍——所以现代 OS 拼命把缺页率压到 0.001% 以下。

#9 LRU 页面置换 + Belady 验证（Ch4）

题面

序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

求： - ① LRU 算法 m=3 时的缺页次数 - ② FIFO 算法 m=3 vs m=4 的缺页次数（验证 Belady 异常）

答案

LRU m=3 推演：

t=1: 1 → F, [1]
t=2: 2 → F, [1, 2]
t=3: 3 → F, [1, 2, 3]
t=4: 4 → F, 淘汰 1 (最久没用), [2, 3, 4]
t=5: 1 → F, 淘汰 2, [3, 4, 1]
t=6: 2 → F, 淘汰 3, [4, 1, 2]
t=7: 5 → F, 淘汰 4, [1, 2, 5]
t=8: 1 → H, 移到最新, [2, 5, 1]
t=9: 2 → H, 移到最新, [5, 1, 2]
t=10: 3 → F, 淘汰 5 (上次 t=7), [1, 2, 3]
t=11: 4 → F, 淘汰 1 (上次 t=8), [2, 3, 4]
t=12: 5 → F, 淘汰 2 (上次 t=9), [3, 4, 5]

缺页 = 10

FIFO m=3 推演：

t=1-7: 同上结构，但 FIFO 命中不更新顺序
t=7 后：[1, 2, 5]
t=8: 1 → H ★ (在内存)
t=9: 2 → H ★ (在内存)
t=10: 3 → F, 淘汰 1 (最早进 t=5), [2, 5, 3]
t=11: 4 → F, 淘汰 2, [5, 3, 4]
t=12: 5 → H (在内存)

缺页 = 9（t=1,2,3,4,5,6,7,10,11）

FIFO m=4 推演（验证 Belady）：

t=1-4: 4 块装满，[1, 2, 3, 4]
t=5: 1 → H
t=6: 2 → H
t=7: 5 → F, 淘汰 1 (最早进), [2, 3, 4, 5]
t=8: 1 → F, 淘汰 2, [3, 4, 5, 1]
t=9: 2 → F, 淘汰 3, [4, 5, 1, 2]
t=10: 3 → F, 淘汰 4, [5, 1, 2, 3]
t=11: 4 → F, 淘汰 5, [1, 2, 3, 4]
t=12: 5 → F, 淘汰 1, [2, 3, 4, 5]

缺页 = 10

对比：

易错点

• ❌ LRU 命中时忘了把页移到最新——常错把 FIFO 当 LRU 用
• ❌ Belady 通用化：只 FIFO 有，OPT/LRU 没有
• 本特殊序列下 LRU 比 FIFO 还差（10 vs 9）——一般序列 LRU 优于 FIFO，这是反例

#10 磁盘调度 SSTF（Ch5）

题面

• 磁头当前位置：100
• 当前方向：向外（朝 200）
• 请求队列：55, 58, 39, 18, 90, 160, 150, 38, 184

求：SSTF 算法的访问顺序、总移动柱面数、平均寻道长度。

答案

每次从当前位置选最近的：

访问顺序：100 → 90 → 58 → 55 → 39 → 38 → 18 → 150 → 160 → 184

总距离 = 10+32+3+16+1+20+132+10+24 = 248

或用快速算法（折线两段）： - 100 → 18 一路向内：100 - 18 = 82 - 18 → 184 一路向外：184 - 18 = 166 - 总 = 82 + 166 = 248 ✓

平均寻道长度 = 248 / 9 ≈ 27.56

4 算法对比（同题）

易错点

• ❌ 平均寻道停在 248/9：必须算成 27.56
• ❌ SSTF 没饥饿问题：远端请求可能永远等
• SCAN/LOOK 通过扫描方向避免饥饿——每个请求都会被”扫到”

默写检查清单（D-1 必过）

考前最后一天，下面 10 项必须能脱稿默写：

• [ ] #1 FCFS 6 步推演
• [ ] #2 SJF 非抢占注意”时刻 0 必跑 P1”
• [ ] #3 RR 时间片用完和新到达的入队顺序
• [ ] #4 HRRF 公式 R = 1 + 等/运行（不能漏 1+）
• [ ] #5 银行家算法 3 步法 + 两个出口
• [ ] #6 分页地址转换 + 算到具体数值
• [ ] #7 TLB EAT 公式两版本（化简和未化简）
• [ ] #8 缺页 EAT + 反直觉震撼数字
• [ ] #9 LRU 命中要更新 + Belady 异常验证
• [ ] #10 磁盘调度 SSTF + 4 算法对比

任何一项默不出来，立刻回到对应章节复习。考场没有第二次机会。