頁面置換演算法是什麼

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

常見的置換演算法

#最佳置換演算法（OPT）

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

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

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

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

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

最近最久未使用（LRU）演算法

FIFO演算法和OPT演算法之間的主要差異是，FIFO演算法利用頁面進入記憶體後的時間長短作為置換依據，而OPT演算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似，那麼就可以把過去最長一段時間裡不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在之前一段時間裡最久沒有使用過的頁面予以置換。這種演算法就稱為最久未使用演算法（Least Recently Used，LRU）。 

LRU演算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時，LRU演算法選擇過去一段時間最久未被使用的頁面。

LRU演算法是經常採用的頁面置換演算法，並被認為是相當好的，但是存在如何實現它的問題。

LRU演算法需要實際硬體的支援。

其問題是怎麼確定最後使用時間的順序，對此有兩種可行的辦法： 

1.計數器。

最簡單的情況是使每個頁表項對應一個使用時間字段，並為CPU增加一個邏輯時鐘或計數器。每次儲存訪問，該時鐘都加1。每當造訪一個頁面時，時脈暫存器的內容就會複製到對應頁表項的使用時間欄位。這樣我們就可以始終保留著每個頁面最後造訪的「時間」。在置換頁面時，選擇該時間值最小的頁面。這樣做， 不僅要查頁表，而且當頁表改變時（因CPU調度）要維護這個頁表中的時間，還要考慮到時鐘值溢出的問題。

2.堆疊。

用一個堆疊保留頁號。每當造訪一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從堆疊的中間移走一項，所以要用具有頭尾指標的雙向鏈連起來。在最壞的情況下，移走一頁並把它放在棧頂上需要改變6個指標。每次修改都要有開銷，但需要置換哪個頁面卻可直接取得，用不著查找，因為尾指標指向棧底，其中有被置換頁。 

因為實作LRU演算法必須有大量硬體支持，還需要一定的軟體開銷。所以實際實現的都是一個簡單有效的LRU近似演算法。 

一種LRU近似演算法是最近未使用演算法（Not Recently Used，NUR）。

它在儲存分塊表的每一個表項中增加一個引用位，作業系統定期地將它們置為0。當某一頁被存取時，由硬體將該位置1。過一段時間後，檢查這些位元可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間裡它未被訪問過。

4）Clock置換演算法（LRU演算法的近似實作） 

5）最少使用（LFU）置換演算法

在採用最少使用置換演算法時，應為在記憶體中的每個頁面設定一個移位暫存器，用來記錄該頁面被存取的頻率。此置換演算法選擇在先前時期使用最少的頁面作為淘汰頁。

由於記憶體具有較高的存取速度，例如100 ns，在1 ms時間內可能對某頁連續存取成千上萬次，因此，通常無法直接利用計數器來記錄某頁被存取的次數，而是採用移位暫存器方式。每次造訪某頁時，便將該移位暫存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。

LFU置換演算法的頁面存取圖與LRU置換演算法的存取圖完全相同；或者說，利用這樣一套硬體既可實現LRU演算法，又可實現LFU演算法。應該指出，LFU演算法並不能真正反映出頁面的使用情況，因為在每一時​​間間隔內，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。

6）工作集演算法

7）工作集時脈演算法

8）老化演算法（非常類似LRU的有效演算法）

#9）NRU (最近未使用）演算法

10）第二次機會演算法

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，檢查它的存取位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的存取位就清為0，它的到達時間就置為目前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總是保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形佇列。用一個指針指示哪一頁是下面要淘汰的。當需要一個儲存區塊時，指標就會前進，直至找到存取位元是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。 

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