页面置换算法有哪些？FIFO、LRU 和 Clock 有什么区别？

知识点详解：缺页以后，系统怎样选一个旧页面

先明确什么时候需要置换

咱们假设进程访问一个不在内存中的页面，需要把它调入。若有空闲页框，可以直接安排；没有足够可用页框时，才需要选择候选换出。

换出不是简单删除所有数据。干净页可能能够从已有来源重新读取，脏页还可能需要写回，具体由系统管理。

OSTEP 的页面置换教材比较了多种策略。下面用简化模型理解选择规则，不把它当成某个 Linux 版本完整实现。

FIFO 只记入场顺序，不记最近使用

假设页框里依次进入 A、B、C。即使 A 此后频繁访问，FIFO 遇到需要置换时，仍可能先淘汰 A，因为它最早进入。

这就是它简单却可能不符合局部性的原因。访问一次旧页面，通常不会把它在 FIFO 队列中的位置刷新。

FIFO 还可能出现 Belady 异常：同一访问序列中，增加页框反而导致更多缺页。经典序列 1、2、3、4、1、2、5、1、2、3、4、5，在简化 FIFO 模拟中，3 个页框和 4 个页框就会出现这种差异。

这个例子说明算法性质，不意味着增加内存通常会让实际系统变慢。

LRU 记录最近使用，代价是要维护

LRU 根据上次访问时间或等价顺序，选出最久未使用的页面。假设刚刚访问 A，它就不再是最旧的候选。

这种策略利用时间局部性：近期使用过的内容，可能还会继续使用。但它仍然不能知道未来，某些访问模式下也会表现不好。

精确维护每次内存访问的完整顺序成本较高，所以操作系统会采用硬件支持和近似策略。不要把应用中的 Map 加链表实现，直接说成操作系统能在每次指令访问时廉价运行的方案。

Clock 用引用位提供第二次机会

把页框看成一个环，指针逐个查看候选。页面被访问时，相应引用位设置为已访问。

简化 Clock 规则是：看到引用位为 1，就清零并把指针往后移，暂时保留；看到引用位为 0，就选它换出。新调入页面和指针后续位置，需要按所采用的规则维护。

这样不必保存精确的访问排序，但也可能在一轮扫描中查看多个页面。它只是近似近期使用情况，不保证淘汰对象与 LRU 相同。

如果还把脏页状态、扫描节奏等考虑进去，方案会更加复杂。面试中先说明基础 Clock，再补充实际系统有其他策略，不要一开始把所有变体混在一起。

怎样比较三种算法

固定同一访问序列和页框数量，记录缺页、换出对象和写回，再比较元数据与维护成本。

只有缺页次数还不够。一个策略减少了一次缺页，却增加大量扫描或写回，实际收益需要结合环境判断。

对于程序员，这也提示我们优化访问局部性：减少大范围随机触碰和不必要工作集，可能比单纯期待置换算法更聪明有效。应用缓存的 LRU 与操作系统页置换有共同思路，但对象、硬件和成本不同。

面试官继续追问

LRU 会有 FIFO 那种 Belady 异常吗？

理想 LRU 具有相应的栈性质，不会以同样方式出现这种异常。实际近似方案不能直接继承所有理论结论。

Clock 的指针转一圈是不是只做一次操作？

不是。它可能逐个检查并清除多个引用位，直到找到候选。不能把平均表现与每次固定常数工作混为一谈。

页面置换和缓存淘汰是同一题吗？

有相似策略，但页置换还涉及缺页、硬件引用信息、页框和写回。不能把应用缓存代码直接当成操作系统实现。

面试速记卡

• FIFO：按进入顺序，维护简单，不刷新近期使用。
• LRU：按最近使用顺序，精确维护有成本。
• Clock：引用位加环形扫描，提供第二次机会。
• 理论边界：Clock 不是精确 LRU，FIFO 可能有 Belady 异常。
• 比较维度：缺页率、维护、扫描与写回共同考虑。