頁面替換算法：最優化，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。