页面置换算法OPT · 融合风（象牙 + Obsidian 入口）

速查

OPT（Optimal）淘汰将来最长时间不会被访问的页面：缺页率理论最优、不存在 Belady 异常，但因需预知未来而不可实现，只作为评价其他算法的性能基准。

速查 ▾

项目	值
全称	Optimal Page Replacement（最佳置换算法）
选择标准	淘汰将来最长时间不会被访问的页面
可实现性	不可实现（需要预知未来）
作用	作为性能基准（理论下界）

核心概念 ▾

OPT（最佳置换算法）选择在未来最长时间内不会被访问的页面进行淘汰。

算法思想

当需要置换页面时，查看所有在内存中的页面
选择在未来最长时间内不会被使用的页面淘汰
如果有多个页面同样长时间不会被使用，可任选一个

可实现性

OPT 需要预知未来的页面访问序列——这在实际中不可能实现
OPT 仅作为理论上的性能基准，用于评价其他算法的优劣
实际系统使用 LRU 等近似算法

形式化描述设当前时刻为 $t$，内存中页面集合为 $F$。对页面 $p \in F$ 定义其下次被访问的时刻为 $n(p) = \min\{ t' > t \mid r_{t'} = p \}$（若此后不再访问则 $n(p) = +\infty$）。OPT 淘汰 $\arg\max_{p \in F} n(p)$。

与其他算法的关系

算法	选择标准	可实现性	性能
OPT	将来最长时间不使用	不可实现	最优
LRU	过去最长时间未使用	可实现	接近 OPT
FIFO	最早进入内存	可实现	可能最差
CLOCK	最近未访问	可实现	接近 LRU

关键性质 ▾

性质	说明
缺页率	所有算法中最小（理论最优）
是否 Belady 异常	不存在（满足 stack property）
可实现性	不可实现（需预知未来）
作用	性能基准（其他算法与之比较）

栈式算法（stack property）若算法满足：对任意访问串，$m$ 个物理块时驻留集恒为 $m+1$ 个物理块时驻留集的子集，则增加物理块不可能使缺页数上升——OPT 与 LRU 均满足，FIFO 不满足。

常见考法 ▾

考法	解题套路
手算 OPT	找当前内存中将来最长时间不被访问的页面淘汰
OPT vs LRU	OPT 用未来信息（不可实现），LRU 用历史信息（可实现）
是否存在 Belady 异常	OPT 不存在（最优算法都没有）
性能比较	$OPT \leq LRU \leq FIFO$（缺页率）

手算口诀遇到缺页时，把内存中每一页向访问串右侧找它下一次出现的位置；先淘汰"以后再也不出现"的页，若都还会出现，则淘汰出现位置最靠右的那一页。

易错点 ▾

注意

OPT 是不可实现的——需要预知未来的访问序列。
OPT 不存在 Belady 异常——最优算法永远不存在 Belady 异常。
手算时需要往后看整个访问序列，找出最长时间不被访问的页面。
LRU 是 OPT 的近似实现——用历史信息代替未来信息。
OPT 的缺页率是所有算法中最小的——这是它的定义。

核心结论 ▾

必背

OPT 是理论最优的页面置换算法，但不可实现。
OPT 选择将来最长时间不被访问的页面淘汰。
OPT 不存在 Belady 异常（满足 stack property）。
LRU 是 OPT 的可实现近似，用"过去最久未访问"代替"将来最久不用"。
OPT 主要用作性能基准，评价其他算法的好坏。

记忆卡片 ▾

OPT 选择淘汰哪个页面？

将来最长时间不会被访问的页面。

OPT 为什么不可实现？

需要预知未来的页面访问序列，实际中无法做到。

OPT 的主要作用是什么？

作为性能基准（理论下界），评价其他算法。

OPT 存在 Belady 异常吗？

不存在——最优算法都不存在 Belady 异常。

LRU 和 OPT 的关系？

LRU 是 OPT 的近似实现——用"过去最久未访问"代替"将来最久不用"。

交互动画 · OPT 置换过程模拟 ▾

第 0/8 步

访问串 7 0 1 2 0 3 0 4 2 3 0 3 2，物理块数 3

缺页次数：0 / 已访问 0

示意图：每次缺页时，OPT 向右扫描访问串，为每个驻留页标出"下次使用"时刻，淘汰其中最靠右（或永不再用）的那一页。

速查 ▾

核心概念 ▾

算法思想

可实现性

与其他算法的关系

关键性质 ▾

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · OPT 置换过程模拟 ▾

相关知识点