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 个页框
下表「位置」按引用串下标从 0 开始计（首个 7 在位置 0、末个 1 在位置 19）。
| 位置 | 访问 | 页框状态 | 缺页? | 淘汰原因 |
|---|---|---|---|---|
| 0 | 7 | 缺页 | ||
| 1 | 0 | 缺页 | ||
| 2 | 1 | 缺页 | ||
| 3 | 2 | 缺页 | 淘汰7（下次出现在位置17，最远） | |
| 4 | 0 | 命中 | ||
| 5 | 3 | 缺页 | 淘汰1（下次出现在位置13，最远） | |
| 6 | 0 | 命中 | ||
| 7 | 4 | 缺页 | 淘汰0（下次位置10，比3的位置9、2的位置8都晚） | |
| 8 | 2 | 命中 | ||
| 9 | 3 | 命中 | ||
| 10 | 0 | 缺页 | 淘汰4（未来不再出现） | |
| 11 | 3 | 命中 | ||
| 12 | 2 | 命中 | ||
| 13 | 1 | 缺页 | 淘汰3（未来不再出现） | |
| 14 | 2 | 命中 | ||
| 15 | 0 | 命中 | ||
| 16 | 1 | 命中 | ||
| 17 | 7 | 缺页 | 淘汰2（未来不再出现） | |
| 18 | 0 | 命中 | ||
| 19 | 1 | 命中 |
缺页次数：9 次（位置 0、1、2、3、5、7、10、13、17）；淘汰序列依次为 7、1、0、4、3、2。
做题技巧
需要淘汰时，看引用串中后续部分，找内存中哪个页面离下次出现最远（或不再出现）。
⚠️ 易错点：比较「下次出现位置」时，必须把内存里的每个页面都比一遍。本例位置 7 访问 4 缺页时，内存是
{0, 2, 3}，三者下次出现分别在位置 10、8、9——最远的是 0（位置 10），所以淘汰 0，而不是只看 2、3 就淘汰 3。漏比内存中的某一页是手算 OPT 最常见的失误。
交互可视化
OPT 的意义
| 性质 | 说明 |
|---|---|
| 实际可行性 | 不可实现（需要预知未来） |
| 理论价值 | 作为其他算法的性能上界 |
| Belady 异常 | 不会出现 |
| 用途 | 评估其他算法的优劣（越接近 OPT 越好） |
三种算法的对比
以同一引用串和相同页框数为例：
| 算法 | 决策依据 | 缺页次数 | Belady异常 |
|---|---|---|---|
| OPT | 未来最久不用的 | 最少 | 无 |
| LRU | 过去最久没用的 | 接近 OPT | 无 |
| FIFO | 最早进入的 | 较多 | 有 |
考研高频考点
- 🔥🔥🔥 OPT 手算过程（看后续引用串选最远的）
- 🔥🔥🔥 OPT 不可实现但作为性能基准
- 🔥🔥 OPT、LRU、FIFO 的缺页次数对比
- 🔥 OPT 不会出现 Belady 异常
OPT 不可实现，LRU 实现开销又太大——有没有折中方案？下篇来看 CLOCK 算法，用一个访问位就能近似 LRU 的效果。