Appearance
408
操作系统
OS-03-09 页面置换算法（FIFO/LRU/CLOCK/OPT）
一、定位信息
- 所属圈层：核心层
- 前置知识回顾：理解请求页式管理和缺页中断的基本流程，知道页面置换是在内存无空闲页框时选择一个页面换出。了解驻留集和页框分配策略的基本概念。
- 知识网络位置：本单元是虚拟内存实现的核心算法，直接决定系统性能。页面置换算法与抖动（OS-03-10）密切相关——好的置换算法能降低缺页率，减少抖动风险。
- 考点热度等级：H级（高频重点）——页面置换算法是408操作系统部分最高频的考点之一，几乎每年都有计算题。
二、知识点讲解
2.1 最佳置换算法（OPT）
OPT（Optimal）：选择未来最长时间内不会被访问的页面作为牺牲页。
- 理论上最优，缺页率最低
- 无法实现：因为无法预知未来的页面访问序列
- 用途：作为评价其他算法的标杆（Benchmark）
2.2 先进先出算法（FIFO）
FIFO（First In, First Out）：选择最早进入内存的页面作为牺牲页。
- 实现简单：用队列维护页面进入顺序
- Belady异常：增加物理页框数反而可能导致缺页率上升（反直觉现象）
- 性能较差：最早进入的页面可能是仍然活跃的页面
2.3 最近最久未使用算法（LRU）
LRU（Least Recently Used）：选择最近最长时间未被访问的页面作为牺牲页。
- 基于时间局部性原理：最近不被访问的页面，未来也不太可能被访问
- 无Belady异常
- 性能接近OPT
- 实现开销较大：需要记录每个页面的最后访问时间
实现方式：
- 计数器法：每个页表项维护一个时间戳，每次访问时更新。置换时选择时间戳最小的页面。
- 栈法：维护一个栈，每次访问页面时将其移到栈顶。栈底的页面就是最近最久未使用的。
2.4 时钟置换算法（CLOCK）
CLOCK（Clock），也称最近未使用算法（NRU, Not Recently Used）：是LRU的近似算法，实现更简单。
简单CLOCK：
- 每个页表项有一个访问位（A）
- 所有页面组成一个循环链表，有一个指针（时钟指针）指向下一个候选页面
- 置换时：指针扫描，若A=0，选中该页；若A=1，将A置为0，指针前移
- 直到找到A=0的页面
改进型CLOCK（考虑修改位）：
- 优先选择（A=0, M=0）的页面（最近未访问且未修改）
- 其次选择（A=0, M=1）的页面（最近未访问但已修改）
- 再次选择（A=1, M=0）的页面（最近访问但未修改）
- 最后选择（A=1, M=1）的页面（最近访问且已修改）
三、记忆与理解辅助
1. 类比记忆：
- OPT：算命先生，知道未来，选最不用的淘汰（但现实中不存在）
- FIFO：排队买票，先来的先走（不管还用不用）
- LRU：看谁最久没来上班，淘汰谁（合理但记录成本高）
- CLOCK：转盘扫描，标记了就清零继续转，没标记的淘汰（LRU的简化版）
2. 口诀："OPT看未来，FIFO看先来；LRU看最近，CLOCK转圈找；FIFO有Belady，LRU没有异常。"
3. 四种算法全面对比（★高频考点）：
| 对比项 | OPT | FIFO | LRU | CLOCK |
|---|---|---|---|---|
| 选择依据 | 未来最久不用 | 最早进入 | 最近最久未用 | 访问位=0 |
| 可否实现 | 不可 | 可 | 可（开销大） | 可（开销小） |
| Belady异常 | 无 | 有 | 无 | 无 |
| 性能 | 最优 | 较差 | 接近OPT | 接近LRU |
| 实现复杂度 | - | 低 | 高 | 中 |
| 硬件支持 | 无 | 无 | 计数器/栈 | 访问位 |
4. Belady异常：只在FIFO算法中出现。增加页框数后，缺页次数反而增加。这是一个重要的反直觉现象，考试中常以判断题形式出现。
四、例题与精解
例题1（基础巩固）
题目：某系统有 个物理页框，页面访问序列为：。分别用FIFO和LRU算法计算缺页次数。
命题意图：考查FIFO和LRU算法的手工模拟过程。
精解：
1. 审题分析：3个页框，20次页面访问，需要逐一模拟两个算法的执行过程。
2. 解题思路：维护当前在内存中的页面集合，每次访问时判断是否缺页，缺页时按规则选择淘汰页面。
3. 完整步骤：
FIFO算法（淘汰最早进入的页面）：
| 访问 | 页面 | 内存状态 | 是否缺页 |
|---|---|---|---|
| 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,3,1}（淘汰0） | 是 |
| 7 | 0 | {2,3,0}（淘汰1） | 是 |
| 8 | 4 | {4,3,0}（淘汰2） | 是 |
| 9 | 2 | {4,2,0}（淘汰3） | 是 |
| 10 | 3 | {4,2,3}（淘汰0） | 是 |
| 11 | 0 | {0,2,3}（淘汰4） | 是 |
| 12 | 3 | {0,2,3} | 否 |
| 13 | 2 | {0,2,3} | 否 |
| 14 | 1 | {0,1,3}（淘汰2） | 是 |
| 15 | 2 | {0,1,2}（淘汰3） | 是 |
| 16 | 0 | {0,1,2} | 否 |
| 17 | 1 | {0,1,2} | 否 |
| 18 | 7 | {7,1,2}（淘汰0） | 是 |
| 19 | 0 | {7,0,2}（淘汰1） | 是 |
| 20 | 1 | {7,0,1}（淘汰2） | 是 |
FIFO缺页次数 = 15次
LRU算法（淘汰最近最久未使用的页面）：
| 访问 | 页面 | 内存状态（最近→最久） | 是否缺页 |
|---|---|---|---|
| 1 | 7 | {7} | 是 |
| 2 | 0 | {0,7} | 是 |
| 3 | 1 | {1,0,7} | 是 |
| 4 | 2 | {2,1,0}（淘汰7） | 是 |
| 5 | 0 | {0,2,1} | 否 |
| 6 | 3 | {3,0,2}（淘汰1） | 是 |
| 7 | 0 | {0,3,2} | 否 |
| 8 | 4 | {4,0,3}（淘汰2） | 是 |
| 9 | 2 | {2,4,0}（淘汰3） | 是 |
| 10 | 3 | {3,2,4}（淘汰0） | 是 |
| 11 | 0 | {0,3,2}（淘汰4） | 是 |
| 12 | 3 | {3,0,2} | 否 |
| 13 | 2 | {2,3,0} | 否 |
| 14 | 1 | {1,2,3}（淘汰0） | 是 |
| 15 | 2 | {2,1,3} | 否 |
| 16 | 0 | {0,2,1}（淘汰3） | 是 |
| 17 | 1 | {1,0,2} | 否 |
| 18 | 7 | {7,1,0}（淘汰2） | 是 |
| 19 | 0 | {0,7,1} | 否 |
| 20 | 1 | {1,0,7} | 否 |
LRU缺页次数 = 12次
4. 方法反思：LRU缺页次数（12次）少于FIFO（15次），说明LRU性能更好。手工模拟时，LRU需要注意"最近最久未使用"的判断——被淘汰的页面是最后一次被访问距今最久的页面。可以用"时间戳法"辅助判断。
例题2（中等提升）
题目：某系统有 个物理页框，页面访问序列为：。分别用FIFO和LRU算法计算缺页次数，并验证FIFO是否存在Belady异常（比较页框数为4时的情况）。
命题意图：考查FIFO的Belady异常现象。
精解：
1. 审题分析：需要分别用3个和4个页框运行FIFO算法，比较缺页次数。
2. 解题思路：模拟FIFO在3和4个页框下的执行过程。
3. 完整步骤：
FIFO，3个页框：
- 1→缺页{1}，2→缺页{1,2}，3→缺页{1,2,3}，4→缺页{4,2,3}淘汰1
- 1→缺页{4,1,3}淘汰2，2→缺页{4,1,2}淘汰3，5→缺页{5,1,2}淘汰4
- 1→不缺{5,1,2}，2→不缺{5,1,2}，3→缺页{5,3,2}淘汰1
- 4→缺页{5,3,4}淘汰2，5→不缺{5,3,4}
- 缺页次数 = 9次
FIFO，4个页框：
- 1→缺页{1}，2→缺页{1,2}，3→缺页{1,2,3}，4→缺页{1,2,3,4}
- 1→不缺{1,2,3,4}，2→不缺{1,2,3,4}，5→缺页{5,2,3,4}淘汰1
- 1→缺页{5,1,3,4}淘汰2，2→缺页{5,1,2,4}淘汰3，3→缺页{5,1,2,3}淘汰4
- 4→缺页{4,1,2,3}淘汰5，5→缺页{4,5,2,3}淘汰1
- 缺页次数 = 10次
Belady异常验证：3个页框缺页9次，4个页框缺页10次。增加页框数后缺页次数反而增加，存在Belady异常！
LRU，3个页框（供对比）：
- 1→缺页{1}，2→缺页{1,2}，3→缺页{1,2,3}，4→缺页{4,2,3}淘汰1
- 1→缺页{4,1,3}淘汰2，2→缺页{4,1,2}淘汰3，5→缺页{5,1,2}淘汰4
- 1→不缺{5,1,2}，2→不缺{5,1,2}，3→缺页{3,1,2}淘汰5
- 4→缺页{3,4,2}淘汰1，5→缺页{3,4,5}淘汰2
- 缺页次数 = 10次
4. 方法反思：Belady异常是FIFO算法的特有现象，LRU和OPT都不会出现。这是因为FIFO的淘汰依据是"进入时间"而非"使用情况"，增加页框可能改变页面的进入顺序，导致淘汰决策变差。这也是为什么FIFO在实际系统中很少单独使用。
五、考情分析
- 考查频次：页面置换算法在近5年真题中出现频率极高，几乎每年至少1道题。
- 常见题型：选择题（判断缺页次数、算法比较）、综合题（手工模拟置换过程、计算缺页率）。
- 分值占比：选择题2分，综合题5-10分。
- 命题趋势：近年来倾向于给出特定页面访问序列，要求用多种算法计算缺页次数并比较。CLOCK算法（改进型）的考查频率增加。基于大纲与命题规律推测。
六、易错点提醒
错误表现：LRU算法中，将"最久未使用"理解为"进入内存最久"。 错误原因：混淆了LRU和FIFO的淘汰依据。 正确理解/做法：LRU淘汰的是"最后一次被访问距今最久"的页面，不是"最早进入内存"的页面。一个页面可能很早就进入内存，但一直在被访问，LRU不会淘汰它。
错误表现：CLOCK算法中，访问位被置为1后就一直保持不变。 错误原因：不理解CLOCK算法的"扫描-清零"机制。 正确理解/做法：CLOCK算法中，扫描到A=1的页面时，将其A置为0，然后继续扫描。这意味着页面被"第二次扫描"时就会被选中。这是一种"给页面第二次机会"的机制。
错误表现：认为增加物理页框数一定能减少缺页次数。 错误原因：不知道Belady异常的存在。 正确理解/做法：对于OPT和LRU算法，增加页框数一定不会增加缺页次数。但FIFO算法存在Belady异常，增加页框数反而可能增加缺页次数。
错误表现：改进型CLOCK算法中，扫描顺序混乱。 错误原因：对优先级规则记忆不清。 正确理解/做法：优先级顺序为 (0,0) → (0,1) → (1,0) → (1,1)。先找"没访问没修改"的，最后找"有访问有修改"的。第一轮扫描不清访问位，第二轮才清。
七、来源标注
- 依据2026考研统考408大纲
- 依据《操作系统概念》（Operating System Concepts, Silberschatz）第10章
- 依据汤小丹《计算机操作系统》第4版第3章