一句话答案

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

核心要点

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

算法	全称	原理	优缺点
OPT	Optimal	替换未来最长时间不再被访问的页面	理论最优，但无法实现（无法预知未来访问序列），仅作为基准
FIFO	First In First Out	替换最早进入内存的页面	实现简单；但可能换出频繁使用的页面；存在 Belady 异常（增加物理帧数反而缺页率上升）
LRU	Least Recently Used	替换最近最久未使用的页面	性能接近 OPT，符合局部性原理；实现需要硬件支持（时间戳或栈），开销较大
Clock	Clock / Second Chance	环形链表 + 引用位：扫描到引用位为 0 则替换，为 1 则清零并跳过	LRU 的近似实现，开销远小于 LRU；实际 OS 中广泛使用
NRU	Not 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 次缺页（反而更多！）

这是因为 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 次

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

追问与易错

追问方向：

• LRU 实际实现困难？
• Linux 用什么算法？
• Belady 异常是什么？

易错点：

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

💡 记忆锚点

内存满了要踢人：OPT是先知（踢未来最久不来的，理想但做不到），LRU靠历史（踢最久没来的，准但贵），FIFO靠先来后到（简单但可能踢常客，还有Belady异常），Clock是LRU的平价版（转圈扫描引用位，给一次"第二机会"）。实际OS用Clock，Redis用近似LRU（随机采样）。