最近最少使用（LRU）的分頁算法總是比FIFO更有效率？

Question

我正在爲我的操作系統課程做一個項目模擬頁面替換。我有一個模擬器，而不是在1200個參考文件上運行所有三種算法。然而，我得到頁錯誤率，其中LRU算法在大多數時間只比FIFO獲得相等或更低的分數。偶爾會有一個輸入運行，LRU的頁面錯誤率比FIFO稍高。這是不正確的？

我正在使用計數器爲每個頁碼增加每一輪來執行LRU。正在使用的頁面將其計數器重置爲0.當我交換幀時，我使用具有最大計數器值的幀。我覺得我的實施應該是正確的。

Answer 1

它肯定會發生，LRU不是最優的，FIFO甚至可能會更好地工作。

例如，考慮一個應用程序，它總是從一開始就開始重複順序地掃描大型數組（太大以至於無法放入內存），但通常不足以強制頁面替換，但通常不會結束。

我認爲一個最佳策略是保持數組中的早期頁面，這將在每次掃描時使用，優先於最近訪問的頁面，而這些頁面可能在一段時間內不再需要。這種策略比LRU更類似於FIFO。