第 7 章 · 页面置换与工作集

内存满时缺页要调入新页就必须淘汰旧页——选哪个？这就是页面置换，目标是缺页率最低。

7.1 置换算法

设访问串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1，3 个页框：

• OPT（最佳置换）：淘汰未来最久才用到的页。缺页率最低，但需预知未来——不可实现，只作理论下界。
• FIFO（先进先出）：淘汰最早调入的页。简单，但可能淘汰常访问的页，且伴随 Belady 异常。
• LRU（最近最久未使用）：淘汰最久没被访问的页。符合时间局部性，接近 OPT，但硬件开销大。
• CLOCK（时钟/NRU）：环形队列 + 访问位，指针扫一圈：位 0 淘汰，位 1 置 0 再找。LRU 的低成本近似，Linux 页回收常用。

7.2 Belady 异常

Belady 异常：页框增多，缺页反而增加。FIFO 独有（LRU、OPT 有栈性质，不出现）。

访问串 1 2 3 4 1 2 5 1 2 3 4 5
3 个页框：缺页 9 次
4 个页框：缺页 10 次   ← 页框变多，缺页反增

原因：FIFO 淘汰的「最早调入」与「将来最久使用」之间没有关联，淘汰决策盲目。

7.3 抖动与工作集

抖动（thrashing）：进程频繁缺页、忙于换页，CPU 利用率暴跌。根因：分配的页框数小于其工作集。

工作集（working set）：进程在时间窗口 Δ 内实际访问的页集合，W(t, Δ) 随 Δ 增大最终稳定。

$D=\sum_i W_i(t,\Delta)\ \ \text{应小于可用页框总数}$

• 工作集模型：给每个进程分配 ≥ 其工作集的页框，不足则挂起进程（中级调度，见第 3 章），防止抖动。
• PFF（缺页率控制）：缺页率太高就加页框，太低就减页框，动态调节。

一次缺页：陷入内核 → 查页表确认缺页 → 找空闲页框（无则按 7.1 置换）→ 从磁盘读入 → 更新页表 → 重启被中断指令。

$\text{EAT}=(1-p)\times\text{内存访问时间}+p\times\text{缺页处理时间}$

p 是缺页率，即使只有 1%，EAT 也可能慢几十倍。

7.4 各算法对比

同一访问串、3 页框。

算法	缺页次数	实现	硬件支持	异常
OPT	9（理论最低）	不可实现	—	无
LRU	12	栈/链表/计数器	高	无
CLOCK	14	访问位	低（1 bit）	无
FIFO	15	队列	无	有 Belady