五大页面置换算法详解

页面置换算法内存满了到底该踢谁出去先搞清楚场景虚拟内存技术让进程可以跑在比物理内存还大的地址空间里但有个前提——你得把正在用的那一小部分留在物理内存中。那问题来了物理内存装不下所有页面发生缺页中断时必须把谁换出去选谁出去就是页面置换算法的事。目标是尽可能减少缺页次数让换出去的页面以后最好别再访问了。五个经典选手一个一个说。OPT开天眼但没法用OPTOptimal Page Replacement最佳页面置换算法。规则很简单置换出未来最长时间内不会再被访问的页面。缺页率最低效果最好是所有算法里理论上限。问题是没法实现——CPU 不会预知未来不知道程序接下来要访问哪个页面。那它有什么用当衡量标准。拿 OPT 和其他算法对比差多少就是优化空间知道最好的情况什么样才能知道你写的算法离天花板有多远。FIFO先来先走简单但坑FIFOFirst In First Out先进先出。规则也很直白谁在内存里待得最久就踢谁。实现起来就一个队列新页面进来排到队尾缺页时从队头踢出去。简单是真的简单。但它完全不考虑这个页面是不是热点——可能你把一个高频访问的页面踢出去了它马上又要进来。最离谱的是Belady 异常物理内存页数增加了缺页次数反而变多了。直觉上内存越大越好对吧但 FIFO 就是会出现这种反直觉的情况。原因是踢出去的页面可能是马上要用的内存多了反而把一些原本不会踢的页面留住了导致后续缺页更多。所以 FIFO 现在基本不用在正经场景里。LRU用历史预测未来效果好但贵LRULeast Recently Used最近最久未使用。规则置换最近最久没有被访问的页面。逻辑是如果某个页面很久没被访问了那未来被访问的概率也低。反过来刚才被访问过的很可能马上又要访问——这就是局部性原理。性能接近 OPT因为它用过去的行为来近似未来的行为比 FIFO 那种机械的先进先出靠谱得多。但代价很高每次页面被访问都要更新它在链表里的位置要么移到队尾要么移到链表头多线程场景下这个链表的并发保护是个大麻烦频繁的链表节点移动光这个操作本身就能吃掉不少 CPU所以虽然 LRU 效果好但在实际操作系统里很少直接用它——不是因为不好用而是太贵了。ClockLRU 的平替实际系统的最爱Clock 算法也叫 NRUNot Recently Used是 LRU 的一个近似实现也是对 FIFO 的改进。数据结构环形链表 每个页面一个访问位。一个指针指向当前最老的页面像个时钟一样按一个方向扫。规则发生缺页中断时检查指针指向页面的访问位如果是0淘汰它新页面放进来指针前移一位如果是1改成 0指针前移一位继续检查下一个这就相当于给 FIFO 加了一个免死金牌——最近被访问过的页面指针扫到你的时候给你一次机会但下次再扫到你就乖乖走人。为什么实际系统都爱用它不用像 LRU 那样频繁移动链表节点只有缺页时才扫一圈性能接近 LRU但实现简单得多开销低适合内核这种对性能敏感的场景很多现代操作系统包括 Linux的页置换算法核心思想就是在 Clock 的基础上做各种改进。LFU看频率但容易翻车LFULeast Frequently Used最不常用算法。规则置换访问次数最少的页面。听起来很有道理——用得少的就该被踢用得多的留下。问题出在哪第一计数器成本高。每个页面要维护一个计数器记录总访问次数还要遍历链表找最小值。页面一多就慢。第二只看频率不看时间。这就出大问题了某个页面启动时被高频访问了一波计数器蹭蹭涨后来再也没用过。但它的计数器值太高了很难被淘汰。而那些最近才变成热点的页面因为计数器值小反而容易被换出去。这叫历史包袱——LFU 对过气热点没有遗忘机制。怎么解决一个常见的改进发生缺页中断时把所有页面的计数器除以 2。这样一来以前高频访问但现在已经过气的页面计数器值会慢慢衰减最终被置换出去。这个技巧本质上是给 LFU 加了一个时间衰减的因素。一张表说清楚算法核心规则能不能实现缺页率主要问题OPT换未来最久不用的❌ 不能最低天花板需要预知未来FIFO换待最久的✅ 能高Belady 异常性能差LRU换最近没用过的✅ 能但贵接近 OPT实现开销大实际很少用Clock环形扫描 访问位✅ 能接近 LRU近似算法不如 LRU 精准LFU换访问次数最少的✅ 能中等历史偏见需配合衰减一句话总结FIFO最弱Belady 异常直接判死刑LRU效果最好但太贵实际系统用不起Clock是 LRU 的务实平替性价比最高工业界最爱LFU看频率不看时间需要加衰减机制才能凑合用OPT是理论天花板只存在于教科书里用来给你比一比差距学页面置换本质上就是学在成本和效果之间做权衡——这和操作系统的设计哲学是一回事。我是小饼干如果对你有帮助那就点点赞吧