面试知识库
中 进阶

页面置换算法#

一句话答案#

物理内存满时选择换出哪个页：LRU（最近最少使用，最优但复杂）、FIFO（简单但有 Belady 异常）、Clock（近似 LRU）。

核心要点

当物理内存不足时，OS 需要将某些页面换出到磁盘，腾出空间给新页面。页面置换算法决定换出哪个页面。

算法全称原理优缺点
OPTOptimal替换未来最长时间不再被访问的页面理论最优，但无法实现（无法预知未来访问序列），仅作为基准
FIFOFirst In First Out替换最早进入内存的页面实现简单；但可能换出频繁使用的页面；存在 Belady 异常（增加物理帧数反而缺页率上升）
LRULeast Recently Used替换最近最久未使用的页面性能接近 OPT，符合局部性原理；实现需要硬件支持（时间戳或栈），开销较大
ClockClock / Second Chance环形链表 + 引用位：扫描到引用位为 0 则替换，为 1 则清零并跳过LRU 的近似实现，开销远小于 LRU；实际 OS 中广泛使用
NRUNot Recently Used使用 R（引用位）和 M（修改位）将页面分为 4 类，优先替换 R=0,M=0 的页面简单高效；优先保留”脏页”避免不必要的磁盘写入

FIFO 的 Belady 异常示例：

访问序列：1,2,3,4,1,2,5,1,2,3,4,5
3 个物理帧 → 9 次缺页
4 个物理帧 → 10 次缺页（反而更多！）
plaintext

这是因为 FIFO 没有利用局部性原理，与”最近常用的页面以后也可能常用”的假设相悖。

LRU 的实现方式：

  • 栈实现：维护一个栈，每次访问将对应页面移到栈顶，替换时淘汰栈底。
  • 计数器实现：每个页面维护最后一次访问时间，替换时间最小的。
  • 两种方式硬件开销都较大，实际 OS 多采用 Clock 算法近似。

LRU 页面置换具体示例：

页面引用序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3（3 个物理帧）

Step  引用  帧1  帧2  帧3  缺页?
 1     7    [7]   -    -    缺页 ✗
 2     0    [7]  [0]   -    缺页 ✗
 3     1    [7]  [0]  [1]   缺页 ✗
 4     2    [2]  [0]  [1]   缺页 ✗ (淘汰 7，最久未使用)
 5     0    [2]  [0]  [1]   命中 ✓
 6     3    [2]  [0]  [3]   缺页 ✗ (淘汰 1，最久未使用)
 7     0    [2]  [0]  [3]   命中 ✓
 8     4    [4]  [0]  [3]   缺页 ✗ (淘汰 2，最久未使用)
 9     2    [4]  [2]  [3]   缺页 ✗ (淘汰 0，最久未使用)
10     3    [4]  [2]  [3]   命中 ✓

LRU 总缺页次数：7 次
plaintext

面试补充： Redis 的内存淘汰策略中的 allkeys-lru 使用的是近似 LRU 算法（随机采样 + 淘汰最久未使用的），思想与操作系统的页面置换一脉相承。

面试回答（2分钟版）

页面置换算法解决的是物理内存满时决定换出哪个页面的问题。主要有几种算法：OPT是理论最优，替换未来最长时间不会被访问的页面，但因为无法预知未来所以只能作为性能基准；FIFO按进入内存的先后顺序换出最早的页面，实现简单但可能换出频繁访问的热页，而且存在Belady异常即增加物理帧数反而缺页率上升；LRU替换最近最久未使用的页面，符合时间局部性原理性能接近OPT，但实现需要维护时间戳或栈开销较大；Clock算法是LRU的近似实现，用环形链表加引用位，扫描时引用位为0就换出，为1就清零给一次”第二次机会”，开销小效果好，是实际操作系统中广泛使用的算法。这个思想在工程中非常常见，Redis的allkeys-lru淘汰策略用的就是近似LRU（随机采样取最久未使用的），MySQL InnoDB Buffer Pool用的是改进版LRU（将链表分为young和old区），本质都是同一个思想在不同层面的应用。

追问与易错

追问方向：

  • “LRU 实际实现困难？”→ 严格 LRU 需要每次访问都更新时间戳或移动栈元素，硬件开销大；实际 OS 用 Clock 算法近似 LRU，Redis 用随机采样近似 LRU
  • “Linux 用什么算法？”→ Linux 使用改进的 Clock 算法（双链表 active/inactive list），结合引用位和 PG_referenced 标志做二次机会淘汰
  • “Belady 异常是什么？”→ FIFO 算法中增加物理帧数反而导致缺页率上升的反直觉现象；LRU 和 OPT 不存在此异常，因为它们是栈算法（帧数多时包含帧数少的子集）

易错点：

  • ❌ LRU 是最好的——实现复杂 Clock 更实用
  • ❌ 页面置换和缓存淘汰无关——Redis LRU 就是同源思想