怎麼理解頁面置換演算法

瞭解頁面置換演算法：當發生缺頁中斷時，如果作業系統記憶體中沒有空閒頁面，則作業系統必須在記憶體選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間，而用來選擇淘汰哪一頁的規則叫做頁面置換演算法。

在位址對映過程中，若在頁面中發現所要存取的頁面不在記憶體中，則產生缺頁中斷。當發生缺頁中斷時，如果作業系統記憶體中沒有空閒頁面，則作業系統必須在記憶體選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換演算法。

最佳置換演算法（OPT）

這是一種理想情況下的頁面置換演算法，但實際上是不可能實現的。這個演算法的基本想法是：發生缺頁時，有些頁面在記憶體中，其中有一頁將很快被存取（也包含緊接著的下一條指令的那頁），而其他頁面則可能要到10、100或1000條指令後才會被訪問，每個頁面都可，以用在該頁面首次被訪問前所要執行的指令數進行標記。最佳頁面置換演算法只是簡單地規定：標記最大的頁面應該被置換。這個演算法唯一的一個問題就是它無法實現。當缺頁發生時，作業系統無法知道各個頁面下一次是在什麼時候被存取。雖然這個演算法不可能實現，但是最佳頁面置換演算法可以用來對可實現演算法的效能進行衡量比較。

先進先出置換演算法（FIFO）

最簡單的頁面置換演算法是先入先出（FIFO）法。這種演算法的實質是，總是選擇在主記憶體中停留時間最長（即最老）的一頁置換，即先進入記憶體的頁，先退出記憶體。理由是：最早調入記憶體的頁，其不再被使用的可能性比剛調入記憶體的可能性大。建立一個FIFO隊列，收容所有在記憶體中的頁。被置換頁面總是在佇列頭上進行。當一個頁面被放入記憶體時，就把它插在隊尾上。

這種演算法只是在以線性順序存取位址空間，時才是理想的，否則效率不高。因為那些常被造訪的頁，往往在主記憶體中也停留得最久，結果它們因變成「老」而不得不被置換出去。

FIFO的另一個缺點是，它有一種異常現象，即在增加儲存區塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。

相關免費學習推薦：php程式設計#（影片）

以上是怎麼理解頁面置換演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！