操作系統將記憶體按照頁的進行管理，在需要的時候才把進程相應的部分調入記憶體。當產生缺頁中斷時，需要選擇一個頁面寫入。如果要換出的頁面在記憶體中被修改過，變成了“臟”頁面，那就需要先寫會到磁碟。頁面置換演算法，就是要選出最合適的一個頁面，使得置換的效率最高。頁面置換演算法有很多，簡單介紹幾個，重點介紹比較重要的 ...
操作系統將記憶體按照頁的進行管理，在需要的時候才把進程相應的部分調入記憶體。當產生缺頁中斷時，需要選擇一個頁面寫入。如果要換出的頁面在記憶體中被修改過，變成了“臟”頁面，那就需要先寫會到磁碟。頁面置換演算法，就是要選出最合適的一個頁面，使得置換的效率最高。頁面置換演算法有很多，簡單介紹幾個，重點介紹比較重要的LRU及其實現演算法。
一、最優頁面置換演算法
最理想的狀態下，我們給頁面做個標記，挑選一個最遠才會被再次用到的頁面。當然，這樣的演算法不可能實現，因為不確定一個頁面在何時會被用到。
二、最近未使用頁面置換演算法（NRU）
系統為每一個頁面設置兩個標誌位：當頁面被訪問時設置R位，當頁面（修改）被寫入時設置M位。當發生缺頁中斷時，OS檢查所有的頁面，並根據它們當前的R和M位的值，分為四類：
（1）！R&！M（2）！R&M（3）R&！M（4）R&M編號越小的類，越被優先換出。即在最近的一個時鐘滴答內，淘汰一個沒有被訪問但是已經被修改的頁面，比淘汰一個被頻繁使用但是“clean”的頁面要好。
三、先進先出頁面置換演算法（FIFO）及其改進
這種演算法的思想和隊列是一樣的，OS維護一個當前在記憶體中的所有頁面的鏈表，最新進入的頁面在尾部，最久的在頭部，每當發生缺頁中斷，就替換掉表頭的頁面並且把新調入的頁面加入到鏈表末尾。
這個演算法的問題，顯然是太過於“公正了”，沒有考慮到實際的頁面使用頻率。
一種合理的改進，稱為第二次機會演算法。即給每個頁面增加一個R位，每次先從鏈表頭開始查找，如果R置位，清除R位並且把該頁面節點放到鏈表結尾；如果R是0，那麼就是又老又沒用到，替換掉。
四、時鐘頁面置換演算法（clock）
這種演算法只是模型像時鐘，其實就是一個環形鏈表的第二次機會演算法，表針指向最老的頁面。缺頁中斷時，執行相同的操作，包括檢查R位等。
五、最近最少使用頁面置換演算法（LRU）
缺頁中斷發生時，置換未使用時間最長的頁面，稱為LRU（least recently used）。
LRU是可以實現的，需要維護一個包含所有頁面的鏈表，並且根據實時使用情況更新這個鏈表，代價是比較大的。
於是，需要對這個演算法進行一些改進，也可以說是簡化。將每一個頁面與一個計數器關聯，每次時鐘終端，掃描所有頁面，將每個頁面的R位加到計數器上，這樣就大致跟蹤了每個頁面的使用情況。這種方法稱為NFU（not frequently used，最不常用）演算法。
這樣還是存在一個問題，即很久之前的一次使用，與最近的使用權重相等。
所以，再次改進，將計數器在每次時鐘滴答時，右移一位，並把R位加在最高位上。這種演算法，稱為老化（aging）演算法，增加了最近使用的比重。
老化演算法只能採用有限的位數，所以可能在一定程度上精度會有所損失。
六、工作集演算法
簡單來說，工作集就是在最近k次記憶體訪問所使用過的頁面的集合。原始的工作集演算法同樣代價很大，對它進行簡化：在過去Nms的北村訪問中所用到的頁面的集合。
所以，在實現的時候，可以給每個頁面一個計時器。需要置換頁面時，同實際時間進行對比，R為1，更新到現在時間；R為0，在規定閾值之外的頁面可以被置換。
同樣，這個演算法也可以用時鐘的思想進行改進。
七、Linux使用的頁面置換演算法
Linux區分四種不同的頁面：不可回收的、可交換的、可同步的、可丟棄的。
不可回收的：保留的和鎖定在記憶體中的頁面，以及內核態棧等。
可交換的：必須在回收之前寫回到交換區或者分頁磁碟分區。
可同步的：若為臟頁面，必須要先寫回。
可丟棄的：可以被立即回收的頁面。
Linux並沒有像我們之前單純討論演算法時那樣，在缺頁中斷產生的時候才進行頁面回收。Linux有一個守護進程kswapd，比較每個記憶體區域的高低水位來檢測是否有足夠的空閑頁面來使用。每次運行時，僅有一個確定數量的頁面被回收。這個閾值是受限的，以控制I/O壓力。
每次執行回收，先回收容易的，再處理難的。回收的頁面會加入到空閑鏈表中。
演算法是一種改進地LRU演算法，維護兩組標記：活動/非活動和是否被引用。第一輪掃描清除引用位，如果第二輪運行確定被引用，就提升到一個不太可能回收的狀態，否則將該頁面移動到一個更可能被回收的狀態。
處於非活動列表的頁面，自從上次檢查未被引用過，因而是移除的最佳選擇。被引用但不活躍的頁面同樣會被考慮回收，是因為一些頁面是守護進程訪問的，可能很長時間不再使用。
另外，記憶體管理還有一個守護進程pdflush，會定期醒來，寫回臟頁面；或者可用記憶體下降到一定水平後被內核喚醒。
