Appearance
页面置换算法对比模拟器
考情分析
页面置换算法的对比分析是选择题和计算题的常客。给定同一引用串，比较不同算法的缺页次数是经典考法。🔥🔥🔥 高频核心。
光看文字描述容易混淆各算法的差异，把它们放在同一组数据上跑一遍，谁优谁劣一目了然。
算法速查表
| 算法 | 淘汰策略 | 可实现性 | Belady 异常 | 性能 |
|---|---|---|---|---|
| OPT | 未来最久不用的页面 | 不可实现 | 无 | 最优（理论上界） |
| FIFO | 最先进入内存的页面 | 队列 | 有 | 最差 |
| LRU | 最近最久没用的页面 | 计数器/栈 | 无 | 接近 OPT |
| CLOCK | 访问位为 0 的页面 | 循环链表 | 可能有 | 接近 LRU |
经典对比：同一引用串下的缺页次数
引用串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，3 个页框
| 算法 | 缺页次数 | 缺页率 |
|---|---|---|
| OPT | 9 | 45% |
| LRU | 12 | 60% |
| FIFO | 15 | 75% |
交互模拟器
在下方模拟器中，你可以自定义引用串和页框数，同时运行多种算法并对比结果：
关键对比维度
1. 栈算法 vs 非栈算法
栈算法：n 个页框时驻留在内存中的页面集合，一定是 n+1 个页框时的子集。
| 栈算法 | 非栈算法 |
|---|---|
| OPT、LRU | FIFO |
| 不会出现 Belady 异常 | 可能出现 Belady 异常 |
2. 过去 vs 未来
| 算法 | 决策依据 |
|---|---|
| OPT | 看未来（不可实现） |
| LRU | 看过去（近似 OPT 的思路） |
| FIFO | 看进入时间（不关心使用情况） |
| CLOCK | 看近期是否访问过（近似 LRU） |
3. 实现开销
| 算法 | 每次访问的开销 | 淘汰时的开销 |
|---|---|---|
| FIFO | 无 | O(1) 队头出队 |
| CLOCK | 硬件置访问位 | O(n) 扫描一圈 |
| LRU | 更新计数器/移动栈 | O(1) 或 O(n) |
Belady 异常详解
FIFO 的经典反例：引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
| 页框数 | FIFO 缺页次数 |
|---|---|
| 3 | 9 |
| 4 | 10（增加页框，缺页反而增多） |
OPT 和 LRU 由于是栈算法，绝对不会出现这种情况。
做题策略
- 计算题：逐步模拟每次访问，画表格记录页框状态
- 选择题：记住关键结论——OPT 最优、LRU 次优、FIFO 最差；只有 FIFO 有 Belady 异常
- 对比题：同一引用串下 OPT 缺页 ≤ LRU 缺页 ≤ FIFO 缺页
考研高频考点
- 🔥🔥🔥 给定引用串，分别用不同算法计算缺页次数并对比
- 🔥🔥🔥 Belady 异常的定义及只出现在 FIFO 中
- 🔥🔥🔥 栈算法不会出现 Belady 异常
- 🔥🔥 各算法的实现方式与开销比较
- 🔥 OPT 不可实现但作为性能基准
置换算法决定了"淘汰谁"，但还有一个问题：每个进程该分多少页框？分配策略和置换范围怎么搭配？下篇来看页框分配与回收。