Appearance
OPT 最佳置换算法
考情分析
OPT 常作为性能基准与其他算法对比，手算过程也是考试重点。🔥🔥🔥 高频。
页面置换的最优策略其实很简单：如果能预知未来，把"以后最久才会用到"的那个页面换出去就行了。OPT 正是这个思路——虽然没法真正实现，但它划出了性能的理论天花板。
算法规则
OPT（Optimal Page Replacement）：淘汰未来最长时间不会被访问的页面。
OPT 是理论最优的页面置换算法，产生的缺页次数最少。但因为需要预知未来的访问序列，无法在实际系统中实现，仅作为性能基准。
置换示例
页面引用串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1，分配 3 个页框
| 访问 | 页框状态 | 缺页? | 淘汰原因 |
|---|---|---|---|
| 7 | 缺页 | ||
| 0 | 缺页 | ||
| 1 | 缺页 | ||
| 2 | 缺页 | 淘汰7（未来最晚出现在位置17） | |
| 0 | 命中 | ||
| 3 | 缺页 | 淘汰1（未来最晚出现在位置13） | |
| 0 | 命中 | ||
| 4 | 缺页 | 淘汰3（未来在位置9，2在位置8，选更晚的3） | |
| 2 | 命中 | ||
| 3 | 缺页 | 淘汰4（未来不再出现） |
缺页次数：9 次（后续不再详细列出）
做题技巧
需要淘汰时，看引用串中后续部分，找内存中哪个页面离下次出现最远（或不再出现）。
交互可视化
OPT 的意义
| 性质 | 说明 |
|---|---|
| 实际可行性 | 不可实现（需要预知未来） |
| 理论价值 | 作为其他算法的性能上界 |
| Belady 异常 | 不会出现 |
| 用途 | 评估其他算法的优劣（越接近 OPT 越好） |
三种算法的对比
以同一引用串和相同页框数为例：
| 算法 | 决策依据 | 缺页次数 | Belady异常 |
|---|---|---|---|
| OPT | 未来最久不用的 | 最少 | 无 |
| LRU | 过去最久没用的 | 接近 OPT | 无 |
| FIFO | 最早进入的 | 较多 | 有 |
考研高频考点
- 🔥🔥🔥 OPT 手算过程（看后续引用串选最远的）
- 🔥🔥🔥 OPT 不可实现但作为性能基准
- 🔥🔥 OPT、LRU、FIFO 的缺页次数对比
- 🔥 OPT 不会出现 Belady 异常
OPT 不可实现，LRU 实现开销又太大——有没有折中方案？下篇来看 CLOCK 算法，用一个访问位就能近似 LRU 的效果。