常用的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，表示對應頁自上次檢查之後還未使用過，我們就把這種在最近一段時間裡未被通路過的頁淘汰出去。
NRU算法