memory-management - 为什么在 LRU 和 Optimal Page Replacement Algorithm 中，引用字符串及其反向页面错误是相同的？

Question

我在看 虚拟内存 来自 Operating System Concepts by Galvin并遇到了一份声明，它说:

" 我们可以将 LRU 策略视为在时间上向后看而不是向前看的最佳页面替换算法。 "

然后在另一行，它说:

" 如果我们让 Sr 成为引用字符串 S 的反向，那么 S 上的 OPT 算法(最佳页面替换)的页面错误率与Sr 上的 OPT 算法。类似地，S 上的 LRU 算法(最近最少使用)的页面错误率与 Sr 上的 LRU 算法的页面错误率相同。"

所以如果 LRU是 OPT回顾过去，字符串和它的反向缺页错误是一样的，因为根据我对第一条语句的理解:如果 LRU 的字符串 S 上的缺页错误是 x和 OPT 是 y ，然后 LRU 和 OPT 必须通过 y 在它的反向字符串 Sr 上出现页面错误和 x分别。

为什么他们必须每个字符串集每次都相同，并且相反？

LRU:最近最少使用的页面替换

OPT:最佳页面替换

Answer 1

措辞令人困惑，但并不是说pfr(LRU(S))==pfr(OPT(S)) ，因为这显然不是真的。据说它们显示相同的特征，因为 LRU(S)有效 OPT(Sr) , 所以 pfr(LRU(S))==pfr(LRU(Sr)) .

所以你的分析是正确的:它们有不同的页面错误率。