页面置换算法：OPT、FIFO、LRU 与 Clock
上一篇讲缺页处理时，我们在流程图里埋了一个关键岔路：当缺页发生、而物理内存已经装满、没有空闲页框时，操作系统必须踢掉一个已经在内存里的页，腾出位置给新页。
问题来了——踢谁？
这看起来是个小决定，实则性能攸关。物理内存就那么多页框，每次缺页都要做一次"踢谁"的选择。选得好，被踢的页以后很久都用不到，几乎没损失；选得差，刚踢出去的页转头就又要用，于是立刻再缺页、再调入，白白多了一次昂贵的磁盘 I/O。在高缺页率下，这个选择的优劣会被放大成几个数量级的性能差异。
页面置换算法的本质，是一道预测题：在所有在内存里的页中，猜出哪一个"未来最久都不会再用"，把它换出去。
这一篇我们把四个经典算法——OPT、FIFO、LRU、Clock——逐个讲清它们的运转过程：每个算法靠什么数据结构、遇到缺页时一步步怎么挑牺牲页。看清机制后，再比较它们的优劣，以及为什么工程上最终落在了 Clock。我们全程用同一个访问序列手算，让差异看得见。
一、先统一战场：一个贯穿全篇的例子
为了让四个算法可比，我们固定一组条件，后面每个算法都用它推演。
- 物理页框数 = 3（内存最多同时装 3 个页）；
- 页面访问序列：
7 0 1 2 0 3 0 4 2 3（程序依次要访问这些页号）。
衡量好坏的指标是缺页次数——访问某个页时它不在内存，就记一次缺页（需要调入，可能伴随换出）。次数越少越好。注意：内存一开始是空的，所以前几次访问必然缺页（这叫冷启动缺页，无法避免），重点看后面算法怎么处理"满了之后踢谁"。
记住这个序列 7 0 1 2 0 3 0 4 2 3，下面四个算法我们都拿它开刀。
二、OPT：上帝视角的最优解
OPT（最优置换，Optimal） 的规则是：
发生缺页且内存已满时，换出"未来最长时间内不会再被访问"的那个页。
我们推演（页框数 3，序列 7 0 1 2 0 3 0 4 2 3）：
- 访问
7 0 1：依次装入，三个页框填满 → 缺页 3 次，内存[7,0,1]； - 访问
2：缺页，内存满，要踢一个。看未来：7之后再不出现、0在第 5 位出现、1之后不出现。7和1都不再出现，挑最久不用的，踢7→ 内存[2,0,1]（注：标准 OPT 踢未来最久不用者，此处7和1均不再现，踢任一即可，按"最远"取7）； - 访问
0：在内存，命中，不缺页； - 访问
3：缺页，内存满。看未来：2在第 9 位、0在第 7 位、1不再出现。1最久不用，踢1→[2,0,3]； - 访问
0：命中； - 访问
4：缺页。看未来：2第 9 位、0之后不再、3第 10 位。0最久不用，踢0→[2,4,3]； - 访问
2：命中；3：命中。
总缺页：7 0 1 2 3 4 = 6 次。OPT 永远是同条件下缺页最少的。
但它有一个致命问题：它需要预知未来——必须知道每个页后续何时被访问。真实系统当然不可能知道未来。所以：
OPT 无法实现，它的唯一用途是当"标尺"：拿其他算法的缺页次数和它对比，衡量差距有多大。
三、FIFO：最朴素，却可能很糟
FIFO（先进先出） 放弃预测，用最简单的规则：
换出"最早进入内存"的那个页，不管它最近用得多频繁。
实现也最简单：维护一个队列，页调入时入队尾，需要换出时踢队头。
推演（页框数 3，序列 7 0 1 2 0 3 0 4 2 3）：
7 0 1：装满，队列[7,0,1]，缺页 3 次；2：缺页，踢最早的7→[0,1,2]；0：命中（在内存）；3：缺页，踢最早的0→[1,2,3]；0：缺页！（0刚被踢出去）踢最早的1→[2,3,0]；4:缺页，踢2→[3,0,4]；2：缺页，踢3→[0,4,2]；3：缺页，踢0→[4,2,3]。
总缺页：9 次，比 OPT 的 6 次差不少。问题出在哪？FIFO 只看"进来多久"，完全不管"最近有没有在用"。 像 0 这种频繁访问的热页，只因为进来得早就被踢了，结果转头又要用、又缺页。
FIFO 还有个臭名昭著的反常现象——Belady 异常：给它更多的页框，缺页次数有时反而增加。这违反直觉（内存越大不该越差吗），却真实存在，根源就是 FIFO 的淘汰逻辑和"页的实际价值"完全脱节。这也成了判断一个算法好坏的一条线：好的算法不该有 Belady 异常。
四、LRU：用"最近最久未用"逼近 OPT
OPT 要看未来，没法实现。但有一个聪明的近似思路——用过去预测未来：
既然程序有时间局部性（最近用过的很可能马上再用），那就换出"最近最久没被使用"的页。这就是 LRU（Least Recently Used）。
LRU 把 OPT 的"未来最久不用"替换成"过去最久没用"，赌的就是局部性。推演（序列 7 0 1 2 0 3 0 4 2 3）：
7 0 1：装满[7,0,1]，缺页 3 次（最近使用顺序：7 旧 → 1 新）；2：缺页，踢最久没用的7→[0,1,2]；0：命中，0变成最近使用 → 最久没用的现在是1；3：缺页，踢1→[2,0,3]（注意2在0之前用过，比0旧）；0：命中，0刷新为最新 → 最久没用的是2；4：缺页，踢2→[0,3,4]；2：缺页，踢最久没用的3（0刚用过、4刚用过）→[0,4,2]；3：缺页，踢0？看最近使用：0在第 7 位用过、4第 8、2第 9，最久的是0，踢0→[4,2,3]。
总缺页：7 0 1 2 3 4 2 3 = 8 次，明显优于 FIFO 的 9 次，接近 OPT 的 6 次。LRU 抓住了局部性，把热页保护得很好。
但 LRU 的麻烦在实现成本。要精确知道"谁最近最久没用"，理论上每次访存都要更新这个页的"最近使用时间"或在某个链表里把它移到最前——这意味着每一次内存访问都要伴随一次数据结构维护。无论是用时间戳（每次访存写时间、换出时找最小）还是用链表（每次访存移动节点），开销都压在了最高频的访存路径上，纯软件做代价高到无法接受，纯硬件做又太复杂。
LRU 的思想（局部性近似）非常好，但精确实现的代价太高——它的开销压在每一次访存上。这就逼出了"近似 LRU"。
五、Clock：用一个标志位，把 LRU 的成本压下来
工程上真正广泛使用的，是 LRU 的廉价近似——Clock 算法（时钟算法，也叫 Second Chance 二次机会）。它的目标是：用极小的成本，达到接近 LRU 的效果。
它的关键设计是给每个页框配一个访问位（reference bit，1 个比特），并把所有页框组织成一个环形队列，配一根像钟表指针一样的"表针"。机制如下：
- 访问位的维护极便宜：每当一个页被访问，硬件自动把它的访问位置 1。这是硬件顺手做的，几乎零成本——这正是它比 LRU 便宜的根本；
- 选牺牲页时，表针沿环转动，对指向的页框做判断：
- 如果访问位 = 1：说明它最近被用过，给它一次机会——把访问位清 0，表针继续往前走，不踢它；
- 如果访问位 = 0：说明从上次表针扫过到现在它都没被用过，就踢它，新页装入这个位置，表针停在下一格。
我们把这个判断逻辑画出来：
这张图的精髓在那个"给二次机会"的环：一个页如果在表针上次扫过后又被访问了（访问位被重新置 1），它就能躲过这一轮淘汰；只有连续一圈都没被再次访问的页，才会被换出。这恰好近似了"最近没怎么用的页优先被淘汰"——也就是 LRU 的核心精神，但代价只是每页一个比特 + 一个环形扫描，比 LRU 维护精确顺序便宜太多了。
实际系统（如 Linux）还会把访问位和**修改位（dirty bit，是不是脏页）**结合起来分级：优先淘汰"没用过且干净"的页（换出零成本，不用写磁盘），最后才动"用过且脏"的页。这是 Clock 的增强版，思路一脉相承——在置换决策里顺便考虑写回成本。
六、看清机制后，把四个算法摆在一起比
现在四个算法的运转都清楚了，我们从"预测准不准"和"实现贵不贵"两个维度收束：
| 算法 | 核心规则 | 缺页(本例) | 能否实现 | 实现成本 |
|---|---|---|---|---|
| OPT | 换出未来最久不用的 | 6（最优） | 不能（要预知未来） | —— |
| FIFO | 换出最早进来的 | 9（差） | 能 | 极低（一个队列） |
| LRU | 换出过去最久没用的 | 8（好） | 能 | 高（每次访存都要维护） |
| Clock | 用访问位近似 LRU | 接近 LRU | 能 | 低（每页一比特） |
从这张表能读出一条清晰的设计主线：
OPT 给出理论上限但不可实现；FIFO 可实现但预测太差；LRU 预测好但太贵；Clock 在"预测质量"和"实现成本"之间找到了甜点。工程的最终选择，几乎总是 Clock 这类"足够好又足够便宜"的方案。
这正是上一篇段页式那条哲学的又一次印证：真实系统要的不是某个指标的理论最优，而是多维度的"足够好"。OPT 漂亮但用不了，LRU 理想但太贵，最后胜出的是能落地的折中。
七、和工程实践 / 后端开发的联系
页面置换的思想，几乎原封不动地出现在你每天打交道的系统里——因为它们面对的是同一个问题：有限的快速空间，装不下全部数据，该淘汰谁？
- 缓存淘汰策略：Redis、本地缓存、CDN 的淘汰策略 LRU、LFU、近似 LRU，和这一篇完全同源。Redis 的
maxmemory-policy里的allkeys-lru用的就是近似 LRU（采样若干 key 挑最旧的），原因和操作系统一样——精确 LRU 太贵。 - 数据库 Buffer Pool：MySQL InnoDB 的缓冲池用的是改良版 LRU（分 young/old 两段，新页先进 old 区，防止全表扫描把热页全冲掉），本质是在对抗 FIFO/朴素 LRU 在特定访问模式下的退化。
- Belady 异常的现实警示：缓存不是越大越一定好，淘汰策略和访问模式不匹配时，加资源未必提升命中率。理解 FIFO 的 Belady 异常，能让你对"加内存就能解决问题"保持警惕。
- 冷热分层：对象存储、日志系统的冷热数据分层，本质也是在判断"哪些数据近期不会再访问"，和置换算法的预测目标一致。
一句话：页面置换不是操作系统的专属知识，它是一切"分层缓存"系统的共同内核。
八、动手做一个小实验：用访问序列手工比较
理解置换算法最扎实的方式，是拿同一个序列，亲手把几个算法各走一遍，数缺页次数。
- 取页框数 = 3，访问序列
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1（比正文更长，差异更明显）； - 分别用 FIFO、LRU、Clock 推演，每一步写出内存里的三个页和访问位（Clock），记录每次是否缺页；
- 统计三者的总缺页次数，对比差距，并特意观察：有没有"刚踢出去的页马上又要用"的情况（FIFO 最容易出现）；
- 进阶：把页框数从 3 改成 4，重新跑 FIFO，看看缺页次数会不会反而增加——亲手撞一次 Belady 异常。
走完这一圈，你对"为什么 FIFO 差、LRU 好、Clock 便宜又够用"的理解，会比看十遍结论都牢。
学习这一部分最容易踩的坑
1. 以为 OPT 可以实现
OPT 要预知每个页未来何时被访问，现实中不可能做到。它只是衡量其他算法好坏的"标尺",不是可部署的算法。
2. 以为 LRU 既好又能直接用
LRU 的思想很好，但精确实现要在每一次访存上维护使用顺序，代价极高。所以工程上用的几乎都是 Clock 这类近似 LRU，而非精确 LRU。
3. 以为"内存越大缺页一定越少"
LRU、OPT 满足这个直觉（栈式算法），但 FIFO 存在 Belady 异常——加页框反而可能增加缺页。"加资源必然变好"不是普适规律。
4. 脱离访问模式谈算法优劣
没有一种算法对所有访问模式都最优。LRU 在有局部性时很好，但面对"全表扫描"这种一次性顺序访问反而会冲掉热页（所以 InnoDB 要改良 LRU）。算法好坏强依赖访问模式。
总结
页面置换算法看似是技巧题，本质却是在问：系统如何在有限内存里尽量留下未来最有价值的内容。把机制和结论一起带走：
- 置换的本质是预测——猜哪个页"未来最久不用"，缺页时把它换出；
- OPT 换出未来最久不用者，最优但不可实现，只作标尺；
- FIFO 换出最早进来者，简单但预测差，且有 Belady 异常（加页框反而更糟）；
- LRU 换出过去最久没用者，靠局部性逼近 OPT，效果好但每次访存都要维护、代价高；
- Clock 用每页一个访问位 + 环形表针近似 LRU，给最近用过的页"二次机会"，便宜又够用，是工程主流；
- 这套思想直接复用于 Redis 近似 LRU、InnoDB 改良 LRU、CDN/冷热分层等一切分层缓存系统。
当你能拿一个访问序列把 FIFO、LRU、Clock 手算出来、并说清各自踢错或踢对的原因，这一篇就真正属于你了。但置换算法只能在"内存大体够用"时发挥作用——一旦活跃页根本装不下，再聪明的置换也救不了场，系统会陷入"越忙越慢"的抖动。这正是下一篇《抖动与工作集》要直面的问题。
参考资源：
- 《现代操作系统》（Andrew S. Tanenbaum）页面置换算法章节
- 《操作系统导论》（Operating Systems: Three Easy Pieces）Swapping: Policies
- OSTEP - Beyond Physical Memory: Policies
- 《深入理解计算机系统》虚拟内存章节