[!info] related notes 操作系统 MOC 虚拟内存 / 缺页中断 / TLB OPT（最佳置换） FIFO（先进先出） LRU（最近最久未使用） Clock / Second Chance（第二次机会）

页面置换算法（OPT/FIFO/LRU/Clock）

速记结论（背就够用）

• OPT：理论最优（不可实现）
• FIFO：实现最简单；可能 Belady 异常
• LRU：效果好；实现成本高
• Clock：LRU 的近似（引用位第二次机会）

笔试常考两类：

• 选择题：特性/优缺点
• 计算题：给引用串 + 页框数，手算缺页次数

1) OPT（最佳置换）

原子笔记：页面置换：OPT（最佳置换）

• 淘汰未来最长时间不再访问的页
• 理论最优，但无法实际实现（需要“未来信息”）

2) FIFO

原子笔记：页面置换：FIFO（先进先出）

• 淘汰最早进入内存的页
• 可能出现 Belady 异常：页框更多，缺页反而更多

3) LRU

原子笔记：页面置换：LRU（最近最久未使用）

• 淘汰最近最久未使用的页
• 利用局部性；实现代价较大

4) Clock / Second Chance

原子笔记：页面置换：Clock / Second Chance（第二次机会）

• 近似 LRU
• 用引用位给页第二次机会

手算题怎么做（通用步骤）

给：引用串 + 页框数 k。

1. 画表格：每一步一个引用页
2. 标记：命中/缺页
3. 缺页且满：按算法选“淘汰页”
4. 统计缺页次数

建议把“当前页框内容”写成一列，别在脑子里算。

高频陷阱

• Belady 异常只是在某些算法里可能出现（典型 FIFO）；LRU/OPT 通常不会
• Clock 不是“严格 LRU”，只是近似：引用位在被访问时置 1

手算例题（FIFO vs LRU）

引用串：1 2 3 2 4 1 2 5 2 4 5

页框数：k = 3

做法：按“手算题通用步骤”画表格分别模拟 FIFO 和 LRU。

记忆点：

• FIFO：淘汰最早进入的页
• LRU：淘汰最久未使用的页

建议你做完后顺手观察：相同引用串下，LRU 通常不会比 FIFO 更差。