OPT 最佳置换算法

2026 大纲 三（二）4 页置换算法的 OPT 部分（另三种见 FIFO、LRU、CLOCK）。

好 10% 是相对什么说的

FIFO 只记"谁先来"，LRU 多记了"谁最近用过"。看起来后者更聪明，可上一节刚给出反例： 在某些引用串上 LRU 反而比 FIFO 缺页更多。

那到底谁好？说"LRU 平均更好"是可以的，但这就带出一个更基本的问题—— 好，是相对什么说的？ 如果没有一个"最好能到什么程度"的参照， "某算法优 10%"这句话就是悬空的。

这一节的 OPT 就是那把尺子。它的规则简单到近乎耍赖：淘汰未来最长时间不会被访问的页面。 它直接读未来，所以在线根本不可实现——运行中的系统看不见还没发生的访问。

但它有两个别的算法都没有的性质，正好使它适合当基准。

第一，它的最优性是逐串成立的。 "对任意引用串、任意页框数，OPT 的缺页次数 不超过任何其他算法"——这是可以论证的定理，比"平均更好"强得多。 LRU 优于 FIFO 只是平均意义上的经验，OPT 优于所有算法则一条串都不会例外。

第二，它不依赖局部性。 LRU、CLOCK 都建立在"程序有局部性"这个经验事实上， 局部性一失效就失灵；OPT 直接读未来，引用串再反常也仍然最优。

所以它的用法是离线的：把真实运行的引用序列录成 trace，事后跑一遍 OPT， 就得到"理论上最少缺多少次页"。没有这把尺子，任何"某算法好多少"的说法都没有基准。

交互可视化

加载可视化中...

一、算法规则

OPT（Optimal Page Replacement）：淘汰未来最长时间不会被访问的页面，产生的缺页次数最少。因为需要预知未来的访问序列，无法在实际系统中在线实现，只作为性能基准。

串乙 3 个页框的完整淘汰走查，含缺页次数统计（想核对自己手算的每一步时展开）

页面引用串 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1（下称串乙，模拟器指南用的也是它），分配 3 个页框。下表「位置」按下标从 0 起计。

位置	访问	页框状态	缺页?	淘汰原因
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。

前 3 次缺页是把 7、0、1 装进空页框、不涉及淘汰，因此发生的置换只有 6 次——这也是教材给这个例子时记的数。两个口径都可能被问到，看清题干问的是哪一个。

换一组页框数看"置换次数 = 缺页次数 − m"何时失效（想搞清这条公式的前提时展开）

引用串 1, 2, 3, 2, 4, 1, 3, 2, 4, 1（数据自造），采用 OPT，分别取 $m=3、4、5$。串里只涉及 4 个不同页面，即 $d=4$。

$m=3$（位置按下标从 0 起计）

位置	访问	框0	框1	框2	结果	淘汰理由
0	1	1			缺页（装空框）
1	2	1	2		缺页（装空框）
2	3	1	2	3	缺页（装空框）
3	2	1	2	3	命中
4	4	1	4	3	缺页（置换）	1→位置5、2→∞、3→位置6，淘汰 2
5	1	1	4	3	命中
6	3	1	4	3	命中
7	2	1	4	2	缺页（置换）	1→位置9、4→位置8、3→∞，淘汰 3
8	4	1	4	2	命中
9	1	1	4	2	命中

缺页 5 次，其中前 3 次是装空框、后 2 次才是置换 ⇒ 置换 2 次，$5-3=2$ ✓。把"装空框"和"置换"分开标是要害：两者都算缺页，但只有后者淘汰了一个页面。

$m=4$：4 个页框恰好装得下全部 4 个页面，位置 0、1、2 装入 1、2、3，位置 4 装入 4 填满最后一个空框，此后全部命中。缺页 4 次、置换 0 次，$4-4=0$ ✓——公式仍成立，因为最后一次缺页正好把页框装满了。

$m=5$：仍是缺页 4 次、置换 0 次，但第 5 个页框从头到尾空着。$4-5=-1$ ❌，公式失效。

一般结论：设引用串涉及的不同页面数为 $d$，则

$$\text{置换次数}=\{\begin{array}{ll}\text{缺页次数}-m,& d\ge m(\text{页框会被装满})\\ 0,& d<m(\text{页框永远装不满，缺页次数恒为 }d)\end{array}$$

拿到题先看一眼 $d$ 与 $m$ 谁大：$d<m$ 时根本不会发生任何置换。

二、最优性：不是断言，是可以论证的

OPT 是四种算法里唯一一个"逐串成立"的最优性结论，所以它值得被论证一次，而不是当口诀背。

一句话记住这个论证：OPT 换出去的那一页，是所有候选里"再要回来"最不着急的那一页；任何别的选择都只会让"要回来"这件事更早发生。

把任意算法一步步改造成 OPT 的完整证明（想知道"最优"凭什么能证明时展开）

设 $A$ 是任意置换算法。找到 $A$ 与 OPT 第一次做出不同决策的那一步，设发生在时刻 $t$：此时两者驻留集完全相同（因为之前决策都一样），OPT 淘汰页 $p$，而 $A$ 淘汰页 $q\ne p$。

构造新算法 $A^{\prime }$：第 $t$ 步改成和 OPT 一样淘汰 $p$，之后尽量照抄 $A$。只需证明 $A^{\prime }$ 的缺页次数不多于 $A$。反复施行这个改造，$A$ 就被逐步改成了 OPT，而缺页次数一路不增——于是 OPT 最优。

关键不变量：第 $t$ 步之后，两者的驻留集只差一页：$A$ 手里有 $p$、$A^{\prime }$ 手里有 $q$，其余完全相同。设 $p$ 下次被访问的位置是 $j$，$q$ 下次被访问的位置是 $i$。因为 OPT 挑的 $p$ 是"下次访问最晚"的那一页，必有 $j\ge i$。 这一句就是全部要害。往下逐位看引用串：

遇到的引用	$A$	$A^{\prime }$	差距变化
两者都持有的页	命中	命中	不变
两者都没有的页	缺页	缺页（淘汰同一页，或淘汰 $q$ 使两者合并）	不变
页 $q$（位置 $i$）	缺页	命中	$A^{\prime }$ 赚一次
页 $p$（位置 $j$）	命中	缺页	$A^{\prime }$ 亏一次

因为 $i\le j$，"$A^{\prime }$ 赚一次"那一行一定先发生。而 $A$ 在位置 $i$ 缺页时必须换入 $q$、换出某一页，这一步之后两者的驻留集就重新合并了（差异被抹平），后面 $A^{\prime }$ 完全照抄 $A$。所以那个"$A^{\prime }$ 亏一次"的情形根本轮不到发生。结论：$A^{\prime }$ 的缺页次数 $\le A$ 的缺页次数。

三、同串同页框数下四种算法的数字

只有把同一串、同一页框数下的数字并列，比较才有意义；不同引用串之间的缺页次数不能互相对照——缺页次数是"算法 + 引用串 + 页框数"三者共同的函数。

两套引用串上四种算法的缺页次数对照（想核对自己手算结果、或想看清"平均更优不等于逐串更优"时展开）

串甲 = 3,2,1,0,3,2,4,3,2,1,0,4（FIFO 篇、LRU 篇用它），串乙 = 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（本篇与模拟器指南用它）。

算法	决策依据	判断"该淘汰谁"的可操作方法	串甲 3 框	串甲 4 框	串乙 3 框	串乙 4 框
OPT	未来最久不用	每页向后扫，取下次出现位置最大者	7	6	9	8
LRU	过去最久没用	每页向前看，取最后访问时刻最早者	10	8	12	8
FIFO	最早进入内存	取队头（调入时刻最早者）	9	10	15	10

三处值得停下来看：

• OPT 在每一格都是最小的——这正是 §二 证明的内容，它不是"平均最小"，是逐格最小。
• 串甲 3 框里 FIFO（9）反而少于 LRU（10），串甲 4 框里 FIFO（10）又反超回去。所以"LRU 比 FIFO 好"只在平均意义上成立，成因见 LRU 篇。
• FIFO 那一行从 3 框到 4 框，串甲是 9 → 10（上升），这就是 Belady 异常；而 OPT 与 LRU 两行在两串上都是不增的，因为它们是栈算法。

考点速记

1. 规则：淘汰未来最长时间不会被访问的页面（未来不再出现的页面同属这一类）。
2. 手算三步：① 列出内存中全部 $m$ 页 → ② 每页向引用串后方扫，记下下次出现的位置（扫到串尾没出现记 $+\mathrm{\infty }$）→ ③ 淘汰位置最大者。
3. ⚠️必须比全部 $m$ 页——只在"看上去要用的那几页"里挑，是手算 OPT 会翻车的地方。
4. 平局怎么办：多页同为 $+\mathrm{\infty }$ 时任选一页，总缺页次数不受影响（它们此后都不再被引用）；有限位置不可能相同，因为同一位置只有一个页号。⇒ 缺页次数唯一，淘汰序列不一定唯一。
5. 最优性是逐串成立的："对任意引用串、任意页框数，OPT 缺页次数不超过任何其他算法"。这比"平均更好"强得多——LRU 只是平均优于 FIFO，在具体串上可能更差。
6. 它也不依赖局部性：LRU、CLOCK 建立在"程序有局部性"之上，局部性失效就失灵；OPT 直接读未来，引用串再反常也最优。
7. 不会 Belady 异常：排序依据是"下次访问的位置"，只由引用串决定、与 $m$ 无关 ⇒ 是栈算法。
8. 缺页次数 ≠ 置换次数：前 $m$ 次缺页只调入不淘汰，$\text{置换次数}=\text{缺页次数}-m$。⚠️前提是页框最终会被装满（引用串涉及的不同页面数 $d\ge m$）；$d<m$ 时置换次数恒为 0，套公式会算出负数。
9. 不可实现，但可离线用：把真实运行的引用序列录成 trace，离线跑一遍得到"理论上最少缺多少次页"。没有这把尺子，"某算法好 10%" 就没有基准。

这一节在真题里被考过的形式：

OPT 至今不单独成题——本页下方的练习区渲染的是整个 page-replacement 标签下的题， 它们分别在 FIFO、LRU、 CLOCK 三篇里讲，范围比本节宽，这是正常的。

不单独成题不等于不考。OPT 在真题里以两种方式出现：

• 作为 Belady 异常判断题的一个选项（2014-30）。问"哪些算法可能出现 Belady 异常"时， OPT 是必须被排除的那一个——理由是速记第七条：它按"下次访问位置"排序，与页框数无关，是栈算法。
• 作为算法对比题的上界。凡出现"某算法的缺页次数最少"这类表述，OPT 都是那个答案； 而"某算法在所有引用串上都优于另一个"这句话，只有 OPT 说得成立（速记第五条）。

复习优先级：手算要会，性质要记，但不必单独刷题。 手算三步在任何一道 "四种算法对比"的题里都可能用到，而且它是四种里最简单的（不需要维护任何状态， 只要向后数）。真正会被设问的是第五、七、八条——逐串最优、不会 Belady、 以及缺页次数与置换次数的换算，后者在 LRU 的手算题里已经考过。

易错：手算时只在"感觉会用到的几页"里挑。必须把内存中全部 $m$ 页都向后扫一遍。

易错：把缺页次数当成置换次数。置换次数 = 缺页次数 − 页框数，且只在页框被装满时成立。

易错：认为 OPT 的淘汰序列唯一。多页同为"以后不再访问"时任选一页，缺页次数唯一但序列不唯一。

易错：认为"LRU 优于 FIFO"和"OPT 优于所有算法"是同一强度的结论。前者是平均意义，后者逐串成立。

易错：认为 OPT 也依赖局部性原理。它直接读未来，引用串再反常也最优。

易错：认为 OPT 可能出现 Belady 异常。它是栈算法，不会。

教材出处

• 最佳置换算法由 Belady 于 1966 年提出、所选淘汰页是"以后永不使用或最长时间内不再被访问"的页、以及本篇串乙的走查与"发生了 6 次页面置换"这一结论：汤小丹《计算机操作系统》5.3.1 节「最佳(Optimal)置换算法」及图 5-3，p163
• 同一引用串下 FIFO"进行了 12 次页面置换，比最佳置换算法正好多一倍"（即缺页 15 次）：同书 5.3.1 节及图 5-4，p164

相关知识

FIFO 页面置换算法｜LRU 页面置换算法｜CLOCK 与改进 CLOCK 算法｜请求页式管理｜页面置换模拟器

真题练习

相关真题（10题）

2025Q262分2022Q292分2021Q282分2019Q292分2016Q262分2015Q272分2014Q302分2013Q302分2012Q457分2010Q468分

上一篇LRU 页面置换算法下一篇CLOCK 与改进 CLOCK 算法

相关文章

• 内存管理基本概念
• 连续分配（首次/最佳/最坏适应）
• 基本分页（地址变换）
• 基本分段
• 段页式管理
• 虚拟内存基本概念
• 请求页式管理
• FIFO 页面置换算法
• LRU 页面置换算法
• CLOCK 与改进 CLOCK 算法
• 页面置换算法对比模拟器
• 页框分配与回收
• 内存映射文件
• 虚拟存储性能与改进