页面置换算法怎么理解

当缺页发生时，如果物理内存里已经没有空闲页框，就必须先把当前某个页换出去，才能把新页装进来。这个“淘汰谁”的问题，就是页面置换算法要解决的核心。

一、为什么需要页面置换算法

当程序访问一个当前不在内存中的页时，会触发缺页中断。

这时如果内存里还有空闲页框，问题很简单，直接分一个空闲页框给新页即可。但如果物理内存已经满了，就必须先腾位置，也就是从现有内存页中挑一个淘汰出去。

页面置换算法要解决的就是：

到底换掉哪一页，才能尽量减少后续缺页次数。

二、页面置换算法的目标

一个好的页面置换算法，希望做到：

• 尽量少发生缺页
• 把未来暂时不用的页换出去
• 把很快还会访问的页尽量保留在内存中

本质上，这其实是在“猜未来”。但操作系统无法真正预知未来访问序列，所以只能根据过去的行为做近似判断。

三、FIFO：先进先出

FIFO 的思路最简单：

谁最早进入内存，就优先淘汰谁。

优点

• 简单
• 容易实现

缺点

它只看进入内存的时间，不看最近是否还在被使用。

所以某个页虽然很早进入内存，但如果它最近依然很活跃，FIFO 仍然可能把它淘汰，这会影响效果。

四、LRU：最近最久未使用

LRU 的思想是：

把最近最长时间没有被访问的页换出去。

它基于局部性原理：如果一个页很久没被访问，那么短时间内再访问它的概率通常也比较低。

优点

• 更符合程序局部性
• 实际效果通常优于 FIFO

缺点

• 精确实现代价高
• 需要记录最近访问情况

实际系统中往往使用 LRU 的近似算法，而不是完全精确实现。

五、LFU：最不经常使用

LFU 的思想是：

把访问次数最少的页换出去。

优点

• 能反映长期热度

缺点

• 它更关注“历史总访问次数”，不够关注“最近变化”
• 某页可能以前很热，但现在已经很少再访问，LFU 仍可能不愿意淘汰它

因此 LFU 在很多场景下不如 LRU 直观。

六、OPT：最佳置换算法

OPT 的思想是：

淘汰未来最长时间内不会再被访问的页。

它从理论上是最优的，因为总能选出对未来影响最小的页。

为什么最优

因为它真正做到了“淘汰未来最不重要的页”，所以缺页次数理论最少。

为什么不能真正实现

因为操作系统无法预知未来的访问序列，所以 OPT 只能作为理论对照标准，不能真实落地。

七、这几种算法怎么记

可以用一句话概括：

• FIFO：谁先来谁先走
• LRU：谁最近最久没用就淘汰谁
• LFU：谁历史使用次数最少就淘汰谁
• OPT：谁未来最久不用就淘汰谁

八、现实系统真的直接用这些算法吗

严格来说，现实操作系统通常不会完全照搬教科书上的理想算法，而是会采用：

• Clock
• Second Chance
• 各种近似 LRU 的方案

因为它们需要在实现成本和效果之间做平衡。

九、总结

页面置换算法是在缺页且没有空闲页框时，用来决定淘汰哪一页的策略。FIFO 只看进入顺序，简单但可能误杀热点页；LRU 基于最近访问情况，通常更符合局部性；LFU 看历史访问次数，但容易被旧热点误导；OPT 理论上最优，但因为无法预知未来而不能真正实现。页面置换算法本质上是在用过去的访问信息，近似预测未来谁最不重要。