这一章要解决什么

上一章（第 21 章）搭好了机制：present 位、页错误、交换空间。机制只回答"怎么把页换进换出"，却没回答最要命的问题：内存满了，该牺牲谁？选错了，程序会以磁盘速度（比内存慢上万倍）运行。

本章把物理内存看成"虚拟页的缓存"，依次研究最优策略 OPT（作为标尺）、FIFO、Random、LRU，再看工作负载如何决定策略优劣、LRU 如何用 use 位和时钟算法近似实现、脏页如何影响决策，最后讨论内存彻底不够时的抖动（thrashing）。下一章（第 23 章）会看到 VAX/VMS 和 Linux 在真实系统里如何落地这些思想。

核心概念速览

内存是页的缓存：用 AMAT 衡量

主存只能装下系统所有页的一个子集，所以它就是虚拟内存页的缓存。替换策略的目标是最小化缓存未命中次数（等价地，最大化命中次数）。有了命中与未命中，就可以计算平均内存访问时间（Average Memory Access Time，AMAT）：

原书的例子：4KB 地址空间、256 字节页（4 位 VPN + 8 位偏移），进程依次访问 0x000, 0x100, …, 0x900（前 10 个页各一次），除了 VPN 3 以外的页都已在内存。于是得到"命中、命中、命中、未命中、命中×6"，命中率 90%，P_Miss = 0.1。取 T_M = 100ns、T_D = 10ms：AMAT = 100ns + 0.1·10ms ≈ 1.0001 ms，大约 1 毫秒；若命中率为 99.9%，AMAT 变成 10.1 µs，快了约 100 倍。自己拖一拖滑块感受一下：

最优替换策略（OPT / MIN）

Belady 很早就证明：踢出将来最晚才会被访问的那个页，得到的未命中次数最少。直觉很简单——既然必须扔掉一个，就扔掉"离下次被需要最远"的那个；其他页都会比它先被用到，所以都比它重要。

原书用的访问序列是 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1，缓存能放 3 页。前 3 次访问是冷启动未命中（cold-start / compulsory miss）；随后 0、1 命中；访问 3 时缓存已满，必须替换。OPT 往未来看：

结果（原书 Figure 22.1）：6 次命中、5 次未命中，命中率 6/11 = 54.5%；如果不计冷启动未命中（每个页的第一次访问），命中率是 6/7 = 85.7%。第 9 次访问页 2 时，0 和 3 将来都不再被访问，踢谁都行，原书踢了 3。

两个简单策略：FIFO 与 Random

FIFO（先进先出）

页进入内存时排进队列，替换时踢掉最先进入的那个。优点只有一个：实现极其简单。同一序列下 FIFO 只有 4 次命中，命中率 36.4%（不计冷启动 57.1%）。问题出在第 5 次访问：页 0 已经被访问过好几次，FIFO 仍然因为它"来得最早"把它踢掉，紧接着访问 0 就又未命中。FIFO 无法判断页的重要性。

Random（随机）

内存吃紧时随机挑一个踢掉。和 FIFO 一样简单，一样不"聪明"，表现完全取决于运气。原书 Figure 22.3 那一次运气不错，拿到 5 次命中。原书把这个实验重复了 10,000 次（不同随机种子）：略多于 40% 的情况下 Random 和 OPT 一样好（6 次命中），有时却只有 2 次甚至更少。下面在浏览器里现场重做这个实验：

Belady 异常（Belady's Anomaly）

直觉上缓存变大，命中率只会变好或不变。可 Belady 和同事找到一个序列：1,2,3,4,1,2,5,1,2,3,4,5，用 FIFO 时，缓存从 3 页增加到 4 页，命中率反而下降了！LRU 则没有这个问题，因为它具有栈特性（stack property）：大小为 N+1 的缓存内容总是包含大小为 N 的缓存内容，所以缓存变大时命中只增不减。FIFO 和 Random 没有栈特性。用下面的模拟器亲手验证：

利用历史：LRU

FIFO、Random 的通病是可能踢掉一个马上就要用到的重要页。和调度一章一样，我们再次用过去预测未来。两种历史信息：

• 频率（frequency）：被访问很多次的页可能有价值 → LFU（Least-Frequently-Used），踢出访问最少的页。
• 近期性（recency）：越近被访问的页越可能再次被访问 → LRU（Least-Recently-Used），踢出最久没被访问的页。

这类策略都建立在局部性原理（principle of locality）上：程序倾向于反复访问某些代码（如循环）和数据结构（如循环里访问的数组）。

在同一序列上，LRU 第一次替换时踢掉 2（0、1 更近被用过），第二次踢掉 0（1、3 更近）。两次决定都正确，结果 6 次命中，与 OPT 持平（原书脚注坦白：这个例子是"特意挑的"）。与之相反的 MFU、MRU 在大多数情况下表现很差，因为它们与局部性背道而驰。

替换策略模拟器（仿 paging-policy.py）

这是本章的核心模拟器。输入页访问序列和缓存大小，选择策略，逐步观察：每次访问是否命中、踢掉了谁、为什么踢它（OPT 显示每页的"下次使用位置"，LRU 显示最近使用顺序，Clock 显示指针和 use 位）。在页号后加 w 表示写（例如 3w），被写过的页成为脏页，踢出时要写回磁盘。

说明：Random 用本站可复现的伪随机数（mulberry32），种子 12 恰好复现原书 Figure 22.3 那一次的选择（依次踢掉 0、1、3，共 5 次命中）；它与 paging-policy.py 用的 Python 随机数不同，所以同一种子下的具体选择不必与官方工具一致。Clock 用的是经典"转圈指针"版本。

工作负载决定一切（复刻 Figure 22.6–22.9）

小序列只能说明机制，要比较策略还得看更大的工作负载。原书用了三种（都是 100 个不同页附近、共 10,000 次访问），横轴是缓存大小（1～100 页），纵轴是命中率：

• 无局部性（no-locality）：每次在 100 个页中均匀随机挑一个。
• 80-20：80% 的访问落在 20% 的"热"页（20 个），其余 20% 的访问落在 80 个"冷"页。
• 循环顺序（looping-sequential）：依次访问 0,1,…,49，然后从头循环，共 10,000 次访问 50 个页。

下面的曲线由你的浏览器用固定随机种子现场计算（每种负载 × 5 种策略 × 22 个缓存大小），数值每次都可复现。

从这三张图可以读出原书的结论：

1. 无局部性时，LRU、FIFO、Random 表现几乎一样，命中率就等于"缓存大小 / 100"；缓存能装下全部页时，所有策略（包括 Random）都收敛到 100%；OPT 明显更好——偷看未来确实有用。
2. 80-20 负载下，Random 和 FIFO 还算不错，LRU 更好，因为它更可能留住热页；OPT 仍然更好，说明 LRU 的历史信息并不完美。Clock 介于 LRU 和 FIFO/Random 之间（Figure 22.9）。
3. 循环顺序是 LRU 和 FIFO 的最坏情况：它们总踢掉最老的页，而循环下最老的页恰恰马上要用。缓存 49 页、循环 50 页，命中率竟是 0%！Random 反而好得多——Random 的一个优点就是没有奇怪的极端行为。这类访问在数据库等重要应用中很常见。

LRU 比 Random/FIFO 高出的那几个百分点重要吗？"看情况"：如果每次未命中代价巨大（这很常见），一点点命中率提升也能带来巨大的性能差异。

实现历史算法：LRU 太贵，用 Clock 近似

完美的 LRU 要在每一次内存访问（取指、load、store）时更新数据结构，把该页移到 MRU 端。FIFO 只在装入和淘汰时操作队列，LRU 却要为每次访问记账，没有精心设计就会严重拖慢性能。

一种思路是硬件辅助：每次访问时硬件把当前时间写进该页的"时间字段"，替换时 OS 扫描所有时间字段找最小者。可是 4GB 内存、4KB 页就有 100 万个页，每次替换都扫一百万项，太慢了。

答案是可以。需要一点硬件支持：use 位（又叫 reference bit，引用位），最早出现在第一个分页系统 Atlas 上。每个页一个 use 位；页被读或写时，硬件把它置 1；硬件从不清零，清零是 OS 的事。

时钟算法（clock algorithm，Corbató 提出）：把所有页排成一个环，一根"表针"指向某一页。需要替换时：

1. 看表针指向的页 P：若 use = 1，说明 P 最近被用过，不是好的牺牲者 → 把 use 清 0，表针前进到 P+1；
2. 重复，直到遇到 use = 0 的页，把它踢掉（最坏情况下转一整圈，把所有位都清掉后回到起点）。

这不是唯一的做法：任何"定期清 use 位、然后区分 1 和 0 来决定踢谁"的方案都可以。Clock 的好处是不需要反复扫描全部内存。原书 Figure 22.9 里的 Clock 变体是"随机挑页扫描"，遇到 use=1 就清零，遇到 use=0 就选它；它不如完美 LRU，但比完全不看历史的策略好——上面曲线图里的 Clock 线正是如此。

考虑脏页

Corbató 也提出了对时钟算法的一个常见改进：考虑页在内存中是否被修改过。被修改过的页叫脏页（dirty page），踢出前必须写回磁盘，代价高；没修改过的干净页（clean page）可以直接重用页框，不需要额外 I/O。硬件为此提供修改位（modified bit，又叫 dirty bit），页被写时置 1。

于是时钟算法可以改成：先找既没被使用又干净的页踢；找不到，再找没被使用但脏的页；以此类推。在上面的模拟器里勾选"Clock 优先踢干净页"、载入"带写操作"预设，对比写回次数（本站的实现：第一圈只找 (use=0, 干净) 且不清位；找不到就第二圈找 (use=0, 脏)，途中把 use=1 清零；再不行重复）。

其他虚拟内存策略

替换不是 VM 子系统唯一的策略：

• 页选择策略（page selection policy，Denning 的叫法）：何时把页调入内存？大多数页用按需分页（demand paging）——被访问时才调入。OS 也可以猜测某页即将被用到而提前调入，这叫预取（prefetching），只有在成功概率较大时才值得做。例如代码页 P 被调入时，很可能 P+1 也快要用到，一起调入。
• 写出策略：可以一页一页地写回，但很多系统会在内存里攒一批待写页，一次性写到磁盘，这叫聚集（clustering）或分组写（grouping）。磁盘做一次大写比很多次小写高效得多。

抖动与准入控制

最后一个问题：如果内存被超额订阅（oversubscribed），正在运行的进程们的内存需求之和超过了物理内存，怎么办？系统会不停地换页，这种状况叫抖动（thrashing）。

早期一些系统有相当复杂的机制来检测和应对抖动。例如给定一组进程，系统可以决定暂时不运行其中一部分，希望剩下进程的工作集（working set，正在活跃使用的页）能装进内存，从而取得进展。这叫准入控制（admission control）：有时候把少量工作做好，胜过把所有工作一起做砸。

一些现代系统的做法更"粗暴"：某些版本的 Linux 在内存超额时运行OOM killer（out-of-memory killer），挑一个吃内存的进程杀掉。它确实能缓解内存压力，但如果杀掉的是 X server，所有需要显示的应用都会无法使用。

模型说明：每个进程一次运行 50 次访问后轮转；命中耗时 1、未命中耗时 D（真实系统中磁盘比内存慢 10⁴～10⁵ 倍，这里取较小的 D 以便看清曲线）；"有效吞吐量" = 访问次数 / 总耗时，1.0 表示全速运行。准入控制下，被挂起的进程在排队，内存里同时只有 ⌊M/W⌋ 个进程的工作集。

先预测再验证

动手实验

cd labs/22-swap-policies && make
./paging-policy -p ALL -c 3 -a 0,1,2,0,1,3,0,3,1,2,1
./paging-policy -p FIFO -c 3 -a 1,2,3,4,1,2,5,1,2,3,4,5 -v
./workload

$ ./paging-policy -p ALL -c 3 -a 0,1,2,0,1,3,0,3,1,2,1
policy  hits  misses  hitrate  hitrate(excl. cold)
OPT        6       5    54.5%    85.7%
FIFO       4       7    36.4%    57.1%
LRU        6       5    54.5%    85.7%
CLOCK      4       7    36.4%    57.1%

$ ./paging-policy -p FIFO -c 3 -a 1,2,3,4,1,2,5,1,2,3,4,5 -v
Access: 1  MISS  FirstIn -> [1] <- LastIn  Replaced:-  [Hits:0 Misses:1]
Access: 2  MISS  FirstIn -> [1 2] <- LastIn  Replaced:-  [Hits:0 Misses:2]
Access: 3  MISS  FirstIn -> [1 2 3] <- LastIn  Replaced:-  [Hits:0 Misses:3]
Access: 4  MISS  FirstIn -> [2 3 4] <- LastIn  Replaced:1  [Hits:0 Misses:4]
Access: 1  MISS  FirstIn -> [3 4 1] <- LastIn  Replaced:2  [Hits:0 Misses:5]
Access: 2  MISS  FirstIn -> [4 1 2] <- LastIn  Replaced:3  [Hits:0 Misses:6]
Access: 5  MISS  FirstIn -> [1 2 5] <- LastIn  Replaced:4  [Hits:0 Misses:7]
Access: 1  HIT   FirstIn -> [1 2 5] <- LastIn  Replaced:-  [Hits:1 Misses:7]
Access: 2  HIT   FirstIn -> [1 2 5] <- LastIn  Replaced:-  [Hits:2 Misses:7]
Access: 3  MISS  FirstIn -> [2 5 3] <- LastIn  Replaced:1  [Hits:2 Misses:8]
Access: 4  MISS  FirstIn -> [5 3 4] <- LastIn  Replaced:2  [Hits:2 Misses:9]
Access: 5  HIT   FirstIn -> [5 3 4] <- LastIn  Replaced:-  [Hits:3 Misses:9]
FINALSTATS hits 3   misses 9   hitrate 25.00

$ ./paging-policy -p FIFO -c 4 -a 1,2,3,4,1,2,5,1,2,3,4,5
FINALSTATS hits 2   misses 10   hitrate 16.67

$ ./workload        （节选：80-20 与循环顺序）
== 80-20 workload ==
cache   OPT    LRU   FIFO   RAND  CLOCK
   10  60.0%  30.7%  29.6%  29.6%  30.2%
   20  79.8%  57.6%  51.8%  51.4%  55.1%
   30  87.4%  75.8%  65.8%  66.2%  72.5%
   50  93.4%  87.1%  80.4%  81.4%  86.4%
== looping workload ==
   40  79.2%   0.0%   0.0%  62.3%   0.0%
   49  97.5%   0.0%   0.0%  95.5%   0.0%
   50  99.5%  99.5%  99.5%  99.5%  99.5%

自测题

常见误区与小结