最佳頁面置換算法

最佳頁面置換算法是Belady於1966年提出的一種理論上的算法。是一種保證最少的缺頁率的理想化算法。

基本介紹

• 中文名：最佳頁面置換算法
• 外文名：optimal page replacement algorithm

頁面置換算法評價標準

一個好的頁面置換算法，應具有較低的頁面更換頻率。從理論上講，應該保留最近重複訪問的頁面，將以後都不再訪問或者很長時間內不再訪問的頁面調出。

算法描述

當產生缺頁中斷時，利用相應的淘汰頁面的算法選擇需要淘汰的頁面。

頁面置換算法在淘汰頁面時的算法：

輸入：頁面號引用串P1,P2...Pn；

輸出：淘汰頁面Pt

實現：

1、如果頁框中的某個頁面P以後永不使用，則該頁面為淘汰頁面Pt。

2、如果每個P都會再次被訪問，那么其中最長未來時間內不再被訪問的頁面為淘汰頁面Pt。

舉例

假定系統為進程分配的物理塊數為3，訪問以下頁面：4,2,9,6,2,6,9,4,9,2.採用最佳置換算法時的置換圖。