页面置换算法：内存满了，到底该踢谁出去

先搞清楚场景

虚拟内存技术让进程可以跑在比物理内存还大的地址空间里，但有个前提——你得把正在用的那一小部分留在物理内存中。

那问题来了：物理内存装不下所有页面，发生缺页中断时，必须把谁换出去？

选谁出去就是页面置换算法的事。目标是：尽可能减少缺页次数，让换出去的页面以后最好别再访问了。

五个经典选手，一个一个说。

---

OPT：开天眼，但没法用

OPT（Optimal Page Replacement），最佳页面置换算法。

规则很简单：置换出未来最长时间内不会再被访问的页面。

缺页率最低，效果最好，是所有算法里理论上限。

问题是没法实现——CPU 不会预知未来，不知道程序接下来要访问哪个页面。

那它有什么用？当衡量标准。 拿 OPT 和其他算法对比，差多少就是优化空间，知道最好的情况什么样，才能知道你写的算法离天花板有多远。

---

FIFO：先来先走，简单但坑

FIFO（First In First Out），先进先出。

规则也很直白：谁在内存里待得最久，就踢谁。

实现起来就一个队列，新页面进来排到队尾，缺页时从队头踢出去。简单是真的简单。

但它完全不考虑"这个页面是不是热点"——可能你把一个高频访问的页面踢出去了，它马上又要进来。

最离谱的是 Belady 异常：物理内存页数增加了，缺页次数反而变多了。

直觉上内存越大越好对吧？但 FIFO 就是会出现这种反直觉的情况。原因是踢出去的页面可能是马上要用的，内存多了反而把一些原本不会踢的页面留住了，导致后续缺页更多。

所以 FIFO 现在基本不用在正经场景里。

---

LRU：用历史预测未来，效果好但贵

LRU（Least Recently Used），最近最久未使用。

规则：置换最近最久没有被访问的页面。

逻辑是：如果某个页面很久没被访问了，那未来被访问的概率也低。反过来，刚才被访问过的，很可能马上又要访问——这就是局部性原理。

性能接近 OPT，因为它用"过去的行为"来近似"未来的行为"，比 FIFO 那种机械的先进先出靠谱得多。

但代价很高：

• 每次页面被访问，都要更新它在链表里的位置（要么移到队尾，要么移到链表头）
• 多线程场景下，这个链表的并发保护是个大麻烦
• 频繁的链表节点移动，光这个操作本身就能吃掉不少 CPU

所以虽然 LRU 效果好，但在实际操作系统里很少直接用它——不是因为不好用，而是太贵了。

---

Clock：LRU 的平替，实际系统的最爱

Clock 算法（也叫 NRU，Not Recently Used），是 LRU 的一个近似实现，也是对 FIFO 的改进。

数据结构

环形链表 + 每个页面一个访问位。

一个指针指向当前最老的页面，像个时钟一样按一个方向扫。

规则

发生缺页中断时：

1. 检查指针指向页面的访问位
2. 如果是 0：淘汰它，新页面放进来，指针前移一位
3. 如果是 1：改成 0，指针前移一位，继续检查下一个

这就相当于给 FIFO 加了一个"免死金牌"——最近被访问过的页面，指针扫到你的时候给你一次机会，但下次再扫到你就乖乖走人。

为什么实际系统都爱用它

• 不用像 LRU 那样频繁移动链表节点，只有缺页时才扫一圈
• 性能接近 LRU，但实现简单得多
• 开销低，适合内核这种对性能敏感的场景

很多现代操作系统（包括 Linux）的页置换算法，核心思想就是在 Clock 的基础上做各种改进。

---

LFU：看频率，但容易翻车

LFU（Least Frequently Used），最不常用算法。

规则：置换访问次数最少的页面。

听起来很有道理——用得少的就该被踢，用得多的留下。

问题出在哪

第一，计数器成本高。
每个页面要维护一个计数器记录总访问次数，还要遍历链表找最小值。页面一多就慢。

第二，只看频率不看时间。
这就出大问题了：某个页面启动时被高频访问了一波，计数器蹭蹭涨，后来再也没用过。但它的计数器值太高了，很难被淘汰。

而那些最近才变成热点的页面，因为计数器值小，反而容易被换出去。

这叫"历史包袱"——LFU 对"过气热点"没有遗忘机制。

怎么解决

一个常见的改进：发生缺页中断时，把所有页面的计数器除以 2。

这样一来，以前高频访问但现在已经过气的页面，计数器值会慢慢衰减，最终被置换出去。这个技巧本质上是给 LFU 加了一个"时间衰减"的因素。

---

一张表说清楚

算法	核心规则	能不能实现	缺页率	主要问题
OPT	换未来最久不用的	❌ 不能	最低（天花板）	需要预知未来
FIFO	换待最久的	✅ 能	高	Belady 异常，性能差
LRU	换最近没用过的	✅ 能但贵	接近 OPT	实现开销大，实际很少用
Clock	环形扫描 + 访问位	✅ 能	接近 LRU	近似算法，不如 LRU 精准
LFU	换访问次数最少的	✅ 能	中等	历史偏见，需配合衰减

---

一句话总结

• FIFO 最弱，Belady 异常直接判死刑
• LRU 效果最好但太贵，实际系统用不起
• Clock 是 LRU 的务实平替，性价比最高，工业界最爱
• LFU 看频率不看时间，需要加衰减机制才能凑合用
• OPT 是理论天花板，只存在于教科书里，用来给你比一比差距

学页面置换，本质上就是学"在成本和效果之间做权衡"——这和操作系统的设计哲学是一回事。

---

我是小饼干，如果对你有帮助，那就点点赞吧！