常用的4種頁面置換算法：先進先出法、最佳置換法、最近最少使用置換法和最近未使用置換法

（一）頁面置換概念

如果被訪問的頁不在內存，則產生缺頁中斷。操作系統進行中斷處理，把該頁從外存調入內存，這就是頁面置換。如果內存中有空閑塊，則可把該頁裝入任何空閑塊中，調整頁表項及存儲分塊表。如果當前內存空間已裝滿，此時必須先淘汰已在內存的一頁，騰出空間，再把所需頁面裝入，這個淘汰頁面的算法就是頁面置換算法。

（1）頁面置換過程

頁面置換的工作流程如圖所示，主要包括以下4個步驟：

第1步：找出所需頁面在磁盤上的位置。

第2步：找出一個空閑內存塊。如果有空閑塊，就用它；如果沒有空閑塊，就用頁面置換算法選擇一個可置換的內存塊，把該頁寫到磁盤上，并相應地修改頁表和存儲塊表。

第3步：把所需頁面讀入剛剛得到的內存空閑塊，修改頁表和存儲塊表。

第4步：重新啟動該用戶進程。

（2）頁面走向

置換算法的好壞直接影響系統的性能。若采用的置換算法不合適，可能出現這樣的現象：剛被換出的頁，很快又被訪問，為把它調入而換出另一頁，之后又訪問剛被換出的頁，……如此頻繁地更換頁面，以致系統的大部分時間花費在頁面的調度和傳輸上。此時，系統好像很忙，但實際效率卻很低。這種現象稱為“抖動”。

好的頁面置換算法能夠適當降低頁面更換頻率（減少缺頁率），盡量避免系統“抖動”。

為評價一個算法的優劣，可將該算法應用于一個特定的存儲訪問序列（也叫頁面走向）上，并且計算缺頁數量。

（二）先進先出法

實現思想：這是最簡單的頁面置換算法。這種算法總是淘汰在內存中停留時間最長的一頁，即先進入內存的頁，先被換出。理由是最早調入內存的頁不再被使用的可能性要大于剛調入內存的頁。這種算法把一個進程所有在內存中的頁按進入內存的次序排隊，淘汰頁面總是在隊首進行。如果一個頁面剛被放入內存，就把它插在隊尾。

優點：容易理解且方便程序設計。

缺點：一是性能不好。僅當按線性順序訪問地址空間時，這種算法才是理想的；否則，效率不高。因為那些常被訪問的頁，往往在內存中停留最久，結果它們因變“老”而不得不被淘汰出去。

二是缺頁率隨內存塊增加而增加。導致這種異常現象的頁面走向實際上是很罕見的，稱為Belady現象。

（三）最佳置換法

實現思想：最佳置換算法是1966年由Belady提出的一種算法。其實質是：為調入新頁面而必須預先淘汰某個老頁面時，所選擇的老頁面應在將來不被使用，或者是在最遠的將來才被訪問。采用這種算法，能保證有最小缺頁率。

優點：這種算法使得缺頁中斷次數最小。

缺點：在實現上有困難，因為它需要預先知道一個進程整個運行過程中頁面走向的全部情況。

（四）最近最少使用置換法

實現思想：先進先出算法FIFO和最佳置換算法OPT之間的主要差別是，FIFO算法將頁面進入內存后的時間長短作為淘汰依據，而OPT算法是依據今后使用頁面的時間。如果以“最近的過去”作為“不久將來”的近似，就可以把最近最長一段時間里不曾使用的頁面淘汰掉。

它的實質是：當需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰。這種算法稱為最近最少使用算法。

LRU算法與每個頁面最后使用的時間有關。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間t，當必須淘汰一個頁面時，LRU算法選擇現有頁面中t值最大的那個頁面。

優點：LRU算法經常被采用，被認為是相當好的頁面置換算法。

缺點：LRU算法需要實際硬件的支持，如計算器、棧等，來記錄頁面的最后訪問時間，同時也需要一定的軟件開銷。

（五）最近未使用置換法

實現思想：最近未使用算法是LRU算法的近似方法，它比較易于實現，開銷也比較少。

其基本思想是：它在存儲塊表的每一表項中增加一個“引用位”，標示該頁最近的使用情況：1表示被訪問過；0表示未被訪問過。當某一頁被訪問時，由硬件將該位置1。操作系統定期地檢查這些位，如果是1，表示對應頁最近被使用過，不被淘汰，但是要把它置為0；如果是0，表示對應頁自上次檢查之后還未使用過，我們就把這種在最近一段時間里未被訪問過的頁淘汰出去。