页面替换算法：最优化，FIFO和LRU

Question

我有一个问题，我不确定它。

总共有三个物理页面和页面参考序列的计算机存储器： 1,2,3,2,1,4,3,5,6,4,3,5,3,5,6 ，7，2，1，5，7。使用最优化，FIFO和LRU页面替换算法。

我有尝试，但我不知道我的答案。 此外，在这种情况下，哪一个是一个很好的算法？为什么？

我的回答：

优化：PF 10

FIFO：PF 12

LRU：PF 16

Answer 1

如果我们从理论上分析，然后最优页面置换算法是最好的。 原因：

• 它最小化（所有页面置换算法中最小页面错误）的页面错误
• 它克服Belady的异常

但是这个算法的问题，它需要未来所需页面的知识，即哪些页面将被要求在存储器中获取，这是不可能的。

如果页面已知，那么您必须使用OPR算法。否则，根据所需的页面，分析每个算法的成本，并实现导致最小页面错误的页面替换策略。

Answer 2

任何页面替换的主要内容是访问模式/页面顺序。该访问权限随操作系统的运行时工作负载而变化。

如果我们可以清楚地看到访问模式并可以预测未来需要的页面，那么'最优页面替换'是最好的。正如Sanjay在其他答案中提到的那样，它可以最大限度地减少页面错误。

如果模式无法预测，那么LRU对于大多数真实世界的工作负载来说可能是体面的。但是一些工作负载可能表现出优于LRU的FIFO。你可以在这里找到discussion。