page-replacement - 最佳页面替换 (OPT) 的证明

Question

我需要证明最优页面替换算法确实是最优的，我不确定如何开始。我想也许可以通过矛盾来证明，但是一旦我提出了一个替代声明，我就不确定如何证明它的页面错误会与 OPT 相同或更少。

Answer 1

这是明天的 CSE 330 决赛吗？

Answer 2

最长前进距离 (LFD)

• 替换下一个请求最远的页面（未来）

定理：

• LFD（最长前向距离）是一种最佳算法。

证明：

• 对于矛盾，假设 LFD 不是最优的
• 那么存在一个有限输入序列α，其LFD不是最优的（假设α的长度为|α|=n）
• 令 OPT 是 α 的最优解，使得

– OPT 以与 LFD 相同的方式处理请求 1,2, ..., i

– OPT 处理请求 i+1 的方式与 LFD 不同

– 任何其他最优策略处理第一个 i+1 请求的方式都不同于 LDF

• 因此，OPT 是尽可能长时间以与 LFD 相同的方式运行的最优解 --> 我们有 i < n

•目标：为req 构造与LFD 相同的OPT'。1, … , i+1

案例一：请求 i+1 不会导致缺页

• LFD 不会改变快速存储器的内容

• OPT 的行为与 LFD 不同 --> OPT 替换了快速内存中的某些页面

– 对于请求 i+1，两种算法的行为方式相同，它们也具有相同的快速内存内容

– OPT 因此不需要请求 i+1 的新页面

– 因此，OPT 也可以稍后加载该页面（无需额外费用）--> OPT'</p>

情况 2：请求 i+1 确实导致页面错误

• LFD 和 OPT 将同一页移入快速内存，但它们驱逐不同的页

– 如果 OPT 加载超过一页，则请求 i+1 不需要的所有页面也可以稍后加载

• 比如说，LFD 驱逐页面 p 和 OPT 驱逐页面 p'</p>

•根据 LFD 的定义，在页面 p 之前再次需要 p'

现在，有两种情况：-

a) OPT 将 p 保存在快速内存中，直到请求 ℓ</p>

– OPT 可以在请求 i+1 时驱逐 p，保留 p′，并在请求 ℓ 时将 p（而不是 p′）加载回快速内存，无需额外费用，类似于 LFD

b) OPT 应请求驱逐 p ℓ' < ℓ</p>

– OPT 可以在请求 i+1 时驱逐 p，保留 p' 并加载 p，同时在请求 ℓ' 驱逐 p'（切换 p 和 p' 的驱逐），再次类似于 LFD

因此，OPT 并不是比 LFD 更好的解决方案。

即，LFD 是最佳页面替换技术。

LFD也称为最佳页面替换技术（OPT）。

PS：在证明中，名称“OPT”仅用作“名称”，不要将其与最佳页面替换技术混淆。