前面我們提到了關于記憶體管理的一些知識，交換技術和虛拟記憶體是兩種常用的處理記憶體過載的辦法。對于虛拟記憶體，進行換入換出的基本機關是頁面。當程序通路的頁面沒有被映射到記憶體時，作業系統必須在記憶體中選擇一個頁面換出記憶體，以便為即将要換入的頁面提供空間。并且如果被換出的頁面被修改過，還需要重寫到磁盤上。然後把需要映射的頁面換入到記憶體中，并修改程序的頁表，然後再重新執行失敗的指令。那麼在作業系統決定換出那個頁面是有講究的，這就是我們接下來要讨論主題。
當發生缺頁中斷時，我們可以随機挑選一個頁面進行置換，但如果每次都選擇不經常使用的頁面會提升系統的性能。如果選擇一個經常被通路的頁面來進行置換，可能在不久後程序又通路了該頁面，該頁面就又需要從磁盤中被置換回記憶體中，是以置換經常通路頁面會造成一些不必要的性能開銷（我們完全可以通過妥善的安排作業系統來避免這種不必要的開銷）。接下來我們就展開讨論集中目前比較成熟的頁面置換算法。需要指出的是，“頁面置換"問題在計算機設計的其他領域也有應用。在多數計算機中會把最近使用的32位元組或者64位元組緩存在高速緩存中來提升性能。當高速緩存存滿之後就會出現”頁面置換“。在Web伺服器中會緩存最近被通路的頁面，資料庫伺服器會緩存最近通路的資料庫記錄所在的頁面，當這些頁面存滿緩存空間後，如果還需要存入新的頁面，就會出現”頁面置換“ 。
- 最優頁面置換算法
很容易想象的一種高效的頁面置換算法是最優頁面置換算法，雖然這個頁面不可能實作。該算法是這樣工作的：有些頁面可能在接下來的幾個指令就會被通路，而有些頁面可能會經過1000/10000條指令後才會被通路，每個頁面都有一個在下一次被通路時需要執行的指令數作為标記。很顯然，标記數越大說明該頁面越晚被通路到。當發生缺頁中斷，選擇标記數最大的頁面進行置換，因為這樣的頁面最晚被使用到。這個算法的想法是十分出色的，但不足在于無法實作，因為在發生缺頁中斷時，作業系統無法得知每個頁面在多少條指令後會被通路到（在程序排程算法時也遇到類似的難題，對于最短作業優先排程算法，作業系統無法那個程序的執行時間最短）。雖然這個頁面置換算法在實際系統中無法使用，但是用它作為參照來評價其他的頁面置換算法的優劣是很有用的。
- 最近未使用頁面置換算法
在前面介紹頁表表項的結構時我們講到有兩個狀态位對于作業系統進行頁面置換時非常有幫助：通路位(R)和修改位(M)。當頁面被通路時（讀或寫）修改通路位，當頁面被修改(寫)設定修改位。每次通路記憶體時都由硬體更新這些位。是以當某位被設定為1時，他就一直保持為1直到作業系統将它複位。可以利用M位（修改位）和R位（通路位）來構造一個簡單的頁面置換算法。當一個程序啟動時，起初所有的頁面都沒有被通路，所有頁面的M位和R位都為0。R位被周期性的清零(每個時鐘周期清零)來區分最近一個時鐘周期被通路的頁面和未被通路的頁面。當發生缺頁中斷時，作業系統檢查頁面的R位和M位的值，并把它們分為四類：
- 第0類：沒有被通路，沒有被修改。R=0，M=0
- 第1類：沒有被通路，已被修改。R=0，M=1
- 第2類：已被通路，沒有被修改。R=1，M=0
- 第3類：已被通路，已被修改。R=1，M=1
第1類，看起來不太可能，但是它是确實存在的，在每個時鐘周期對R位進行清零時，第3類就變為了第1類。每個時鐘周期到來時，清零R位用于區分開最近一個時鐘周期被通路的頁面和未被通路的頁面，但是不會清零M位，因為M位決定了頁面被換出時是否需要寫回到磁盤交換區。
NRU （Not Recently Used，最近未使用）算法 随機從類編号最小的非空類中挑選一個頁面進行頁面置換。算法思路：在最近一個時鐘滴答中（典型的時間為20ms），淘汰一個既沒有被通路也沒有被修改的頁面比淘汰一個頻繁使用的頁面好。
優點：易于了解并且易于實作，雖然該算法不是性能最好的，但已經能夠滿足大多數場景。
- 先進先出頁面置換算法
一種比較簡單的且易實作的算法是FIFO（First-In First-out，先進先出）。由系統維護一個頁面進入記憶體的順序連結清單，可以是單獨某個程序一個連結清單，也可以是整個系統一個連結清單。最新進入記憶體的頁面放到連結清單的尾部，最早進入記憶體的頁面放在連結清單的頭部。當發生缺頁中斷時，淘汰連結清單頭部的頁面，并把新調入的頁面加入到連結清單尾部。
缺點： FIFO算法會置換掉一些經常使用的頁面，是以在系統中很少使用純粹的FIFO算法。
- 第二次機會頁面置換算法
FIFO算法可能會把經常通路的頁面換出，為了避免這種情況，可以對FIFO算法進行改進：當發生缺頁中斷時，檢查連結清單頭部的頁面，如果該頁面的R位為0，表示該頁面進入記憶體時間最長并且在最近時間周期内未被通路，直接選擇該頁面進行頁面置換。如果連結清單表頭頁面的R位為1，那麼将該頁面的R位清零同時把該頁面由連結清單表頭移動到連結清單尾部，并繼續考察下一個連結清單頭部頁面。這種算法稱之為二次機會（second chance）算法。第二次機會算法就是在尋找最近一個時鐘間隔沒有被通路的頁面，如果所有的頁面都被通路了，那麼該算法就簡化成了FIFO算法。
- 時鐘頁面置換算法
考慮第二次機會頁面置換算法，它雖然是一個合理的算法，但是需要在連結清單中移動大量的頁面，既降低了效率又不是很必要。是以對于第二次機會頁面置換算法進行改進：把所有的連結清單元素都保持在類似于鐘面的環形連結清單中，用一個指針指向最老的頁面。當發生缺頁中斷時，首先檢查指針指向的頁面。如果該頁面的R位為0，那麼直接淘汰該頁面，并把新加入的頁面放入到該位置，指針指向下一個頁面。如果R位為1，那麼将R位清零，同時指針移向下一個頁面。
- 最近最少使用頁面置換算法
LRU（Least Recently Used,最近最少使用）頁面置換算法 是對最優頁面置換算法的一種近似的實作，該算法是基于如下的一種觀察得出的：在前面幾條指令頻發通路的頁面很可能在後面的若幹指令也可能會通路到（與轉換檢測緩沖區TLB相似）。反過來，最近幾條指令沒有通路的頁面可能在接下來很長一段時間内也不會被通路。基于這種觀察，我們可以在發生缺頁中斷時，置換最近最少使用的頁面。雖然這種LRU算法在理論上很好，但是實作的代價非常大，通常需要特殊的硬體支援，但大多數計算機卻并不包含這樣的硬體，是以我們可以使用一種軟體的解決方案。NFU（Not Frequently Used，最不常用）算法，該算法将每個頁面和一個軟體計數器相關聯，計數器的初始值為0。每當時鐘中斷時，由作業系統掃描記憶體中的所有頁面，并把每個頁面的R位加到計數器上，計數器大體上反映了頁面的通路頻率。每當發生缺頁中斷時，淘汰計數器較小的頁面。NFU這種直接将Ｒ位的值加到計數器上的做法是不妥當的，需要使用老化（aging）算法 對NFU算法進行改進：首先在将頁面的R位加到計數器之前現将計數器向右移一位 ，然後再把R位的值加到計數器的最左端而不是最右端。下圖說明了老化算法是如何工作的。假設第一個時鐘滴答後，頁面0~5的R值為1、0 、1 、0 、1 、1。也就是說在時鐘滴答0到時鐘滴答1之間通路了頁面0、 2 、4、 5，這些頁面的R位被設定為1，其他頁面的R位被設定為0。6個頁面各自對應的計數器初始狀态都為0，在第一個時鐘滴答後各個計數器通過老化算法後的值如(a)所示，後面的(b),(c)......分别為第2,3,4......個時鐘周期的計數器值。當發生缺頁中斷時，選擇值最小的計數器對應的頁面淘汰。
該算法和LRU存在些許不同：在圖(e)中的頁面3和頁面5，他們都已經兩個時鐘滴答沒有被通路，而在兩個時鐘滴答前，兩個頁面都被通路了過。根據LRU，如果必須置換一個頁面，就需要從頁面3和頁面5中選擇一個。現在的問題是我們不知道時鐘滴答1間和時鐘滴答2間那個頁面别通路了，因為每個時鐘滴答隻記錄了一位，是以無法從一個時鐘滴答中區分那個頁面在較早的時間被通路和那個頁面在較晚的時間被通路。而使用老化算法就可以知道應該置換頁面3而不是頁面5，因為頁面5在更往前的幾個時鐘滴答間（時鐘滴答1間）也被通路了而頁面3卻沒有，對應到計數器的展現是頁面5的計數器比頁面3的計數器更大。同時老化算法的計數器是有限位的（如果計數器為8位，那就隻能記錄8個時鐘滴答間的通路情況），這就限制了對以往的頁面使用情況的記錄。
- 工作集頁面置換算法
一個程序目前正在使用的頁面集合稱之為它的工作集。如果整個工作集都被轉入到記憶體，那麼程序運作将不會産生太多的缺頁中斷。若記憶體太小不能容納程序的的整個工作集，那麼程序運作時會産生很多的缺頁中斷，原本可能隻需要幾納秒就能執行完的指令現在可能需要10毫秒才能完成。如果程式執行幾條指令就發生一次缺頁中斷，稱程式發生了颠簸。有不少的分頁系統都試圖跟蹤程序的工作集，確定再程序運作時，它的工作集頁面就已經在記憶體中了。這種方法稱之為工作集模型，其目的在于大大減少缺頁中斷率。在程序運作前預先将程序的工作集裝入到記憶體的方法稱之為預先調用，另一種方式是程序運作前工作集沒有在記憶體中，當程序運作時再調入工作集到記憶體中，稱之為請求調頁。
為了實作工作集模型，作業系統必須跟蹤那些頁面在工作集中，并可根據這些資訊推導出一個合理的頁面置換算法：在發生缺頁中斷時，淘汰一個不在工作集中的頁面。為了實作該算法，就需要一種方法來确定那些頁面在工作集中。根據定義，工作集就是最近k次記憶體通路使用過的頁面集合。為了實作該算法，就必須事先确定k的值，一旦k的值确定了，每次通路記憶體後，最近k次記憶體通路通路過的頁面也就确定了。但是不是有了工作集的定義就能夠在程式運作期間高效的計算出工作集，理論上，可以通過特殊的寄存器記錄過去k次記憶體通路使用過的頁面，在發生缺頁中斷時，讀取寄存器中記錄的頁面号，進行排序去重得到頁面工作集，然而這種方式的開銷極大，是以該技術幾乎沒有被采用過。作為一種替代，不再考慮最近k次的記憶體通路，而是考慮頁面的執行時間。過去定義的工作集可能是：在過去的1000w次記憶體通路所使用的頁面集合，而現在的定義可能是：在過去的10ms記憶體通路使用過的頁面集合。例如對于某個程序從Tms時刻到T+100ms期間真正使用CPU的時間為40ms，對于工作集而言，這40ms稱之為目前實際運作時間，是以我們在進行工作集模拟時也應該考慮在過去的τ秒内程序在目前實際運作時間使用過的頁面。
現在考慮該算法，該算法的基本思想是找出不在工作集中的頁面并進行淘汰。因為隻有在記憶體中的頁面才可以作為被淘汰的候選者，是以該算法不考慮不在記憶體中的頁面。對于程序的頁表，每個表項包含一個R位、M位和一個上次使用該頁面的時間，可以使用硬體來設定R位和M位，并且在每個時鐘周期清零R位。算法進行如下的工作，當發生缺頁中斷時，掃描頁表尋找一個合适的頁面進行淘汰。對于每一個表項，如果R位為1，那麼就把目前實際時間寫入到表項的“上次使用時間”域，以表示缺頁中斷發生時該頁面正在被使用。該頁面在目前時鐘滴答中被使用過，表面該頁面應在工作集中，不應該被淘汰。當表項的R位為0時，那麼就表明該表項對應的頁面在目前的時鐘滴答中沒有被通路，可以作為被淘汰的候選頁面。為了确定該頁面是否能夠被淘汰，需要計算頁面的生存時間（目前實際時間-上次被通路的時間）并和τ進行比較，如果生存時間大于τ，表示該頁面不在工作集中，該頁面可以被淘汰。同時，掃描整個程序頁表表項的的工作繼續進行以更新剩餘的表項。還有一種情況是生存時間小于等于τ，則說明該頁面仍然在工作集中，這樣的頁面應該被儲存起來，但是要記錄生存時間最長的頁面号。在掃描完程序頁表的所有表項後，如果發現所有頁面的生存時間都小于等于τ(所有頁面都在工作集中)，那麼此時就應該淘汰生存時間最長的頁面。更極端的情況，在目前時鐘滴答中 ，所有的頁面都被通路了（R位都為1），是以就随機選擇頁面進行淘汰，如果有可能的話，淘汰一個幹淨的頁面。
- 工作集時鐘頁面置換算法
上面介紹的工作集頁面置換算法中，當發生缺頁中斷時，需要掃描程序的整個頁表一遍後才能決定淘汰那個頁面，是以工作集算法是比較費時的。有一中改進的算法，它是一種時鐘算法，同時又使用了工作集資訊，稱為WSClock算法，該算法實作簡單，性能好，在實際的工作中有廣泛的應用，接下來一起探讨該算法。
與時鐘算法一樣，所需要的資料結構是一個包含頁框資訊的循環表。起初該表是空表，随着許多頁面被通路，漸漸地，循環表中加入了許多表項，最終形成了一個環。每個表項包含來自工作集算法的上次通路時間、R位、M位等資訊。該算法的工作流程：當發生缺頁中斷時，首先檢測指針指向的表項。如果R位被設定為1，表明在過去的這個時鐘滴答中該頁面被通路了，該頁面在工作集中。将該表項的R位置為0，指針指向下一個頁面，并重複該過程。如果發現指針指向的表項的R位為0，同樣需要計算該頁面的生成時間，如果生存時間大于τ，表明該頁面不出在工作集中，可以被被淘汰，然後再根據M位判斷是否需要将頁面寫回到磁盤交換區中。如果M位為0，可以淘汰該頁面，直接用新調入的頁面覆寫該頁面所對應的頁框。如果M位為1，表示該頁面被修改過，是以此頁面在磁盤上沒有有效的副本。為了避免由于寫磁盤操作而引起程序的切換，指針移動到下一個表項，算法對下一個 表項所對應的頁面進行檢查，畢竟後面可能存在一個舊的且幹淨的頁面可以使用。
-
頁面置換算法小結
| 算法 | 注釋 |
| 最優算法 | 不能實作，可作為其他算法性能的參照标準 |
| NRU算法 | LRU的粗糙的近似實作 |
| FIFO算法 | 可能會淘汰頻繁通路的頁面 |
| 第二次機會算法 | 在FIFO基礎上改進，有很大的提升 |
| 時鐘算法 | 是對第二次算法的改進，一種現實可行的算法 |
| LRU算法 | 很優秀，缺點是難以實作 |
| NFU算法 | 對于LRU相對粗糙的近似實作 |
| 老化算法 | 非常近似于LRU的有效算法 |
| 工作集算法 | 實作起來開銷很大 |
| 工作集時鐘算法 | 在工作集算法中引入時鐘的概念，一種有效的算法 |
在所有算法中，最優算法無疑是最完美的，在缺頁中斷時它選擇最晚被通路的頁面作為被淘汰的頁面。但該算法卻難以實作，因為作業系統無法知道程序在記憶體中的頁面将在什麼時候被通路。
NRU（Not Recently Used，最近未使用）算法：使用頁表項中的M位和R位作為算法的支撐，并根據R位和M位的值将程序的頁面劃分為四類，在發生缺頁中斷時淘汰分類編号最小且不為空的分類中的頁面。該算法的優點在于簡單且容易實作（雖然性能不一定最優）。
FIFO算法 / 第二次機會算法 / 時鐘算法：這三中算法有着一些聯系，第二次機會算法是在FIFO算法的基礎上進行改進的，時鐘算法又是在第二次機會算法的基礎上進行改進，是以時鐘算法經過一些改進後是一個現實可行的算法。FIFO算法中，作業系統維護一個連結清單，連結清單記錄了頁面進入記憶體的順序。當發生缺頁中斷時就直接淘汰最先進入記憶體的頁面。FIFO算法的優缺點十分明顯：該算法容易實作，但同時該頁面也會淘汰掉經常被通路的頁面，帶來不必要的性能開銷。
第二次機會算法對FIFO算法提出改進：在發生缺頁中斷時，檢查連結清單頭部的頁面的R位的值。如果R位為1表示該頁面通路過，将該頁面的R位清零，并把頁面從連結清單頭部摘除移動到連結清單尾部。如果連結清單頭部的頁面的R位為0，則可以直接淘汰掉該頁面。第二次機會算法算法相對于FIFO算法能夠避免一些被經常通路的頁面被淘汰。但如果在發生缺頁中斷時，所有的頁面的R位都為1，那麼此時第二次機會算法就退化成了FIFO算法。
時鐘算法是在第二次機會算法進行改進，提出使用指針指向頁面而不是在連結清單中移動頁面節點的方式來減少性能開銷。
LRU算法 / NFU算法 / 老化算法：LRU（Least Recently Used）算法是指最近最少使用的算法，當發生缺頁中斷時置換最近最長時間未被使用的頁面。但該算法實作起來代價很高。
NFU（Not Frequently Used）算法作為LRU算法的一種軟體實作，該算法将每個頁面和一個計數器相關聯，每次時鐘中斷時，作業系統掃描所有頁面的R位（0 or 1）并把它們累加到計數器，該計數器就大緻展現了頁面的被通路的頻率程度。在發生缺頁中斷時就置換計數器值最小的算法。NFU算法的缺點：對于一些頁面，在過去的幾個時鐘周期内(0-T1)可能被頻繁通路，而在最近幾個時鐘周期内(T1-T2)可能很少被通路，那麼在發生缺頁中斷時，這些頁面的計數器值就不能反映在最近幾個時鐘周期内(T1-T2)頁面通路的頻繁程度，因為計數器反映的是過去整個時間的通路頻率(0-T2)而非某個時間段的通路頻率(T1-T2)。
老化（aging）算法：作為對NFU算法的改進，在每次掃描頁面的R位并累計到計數器時做出一些改動。在将頁面的R位的值加到計數器之前現将頁面的計數器向右移一位，然後把頁面的R位的值加到計數器的最左一位上。這樣，通過改動後的計數器就能夠反映過去n（n的值取決于計數器使用多少位進行表示，如果計數器使用16bit進行表示，則n=16）個時鐘周期裡頁面的通路頻率。計數器值越大表明頁面在最近n個時鐘周期内通路的頻繁程度越高，計數器值越小表明頁面在最近n個時鐘周期内通路的頻繁程度越低。當發生缺頁中斷時，比較各個頁面的計數器的值，然後将計數器值最小的頁面淘汰。
工作集算法/工作集時鐘算法：工作集算法引入了工作集模型，一個程序目前正在使用的頁面集合稱之為工作集。該算法在發生缺頁中斷時，淘汰不在程序工作集中的頁面。為了實作該算法需要通過一種方式确定到底哪些頁面在工作集中。一種可以采用的方法是在過去執行的k次記憶體通路中，被通路到的頁面就是工作集。當k的值确定了，每次發生記憶體通路時，過去k次記憶體通路的頁面也就随即确定了。另一種方式是考慮考慮頁面執行時間，例如工作集定義為在過去10ms内通路過的頁面。在該算法的實作中，每個頁表表項都包含M位、R位和上次使用該頁面時間等資訊。在發生缺頁中斷時，以此掃描每個表項，如果R位為1，那麼表示在該頁面在目前時鐘周期内被通路了，該頁面應該在程序的工作集中，不應被淘汰，是以将目前時間寫入到表項的頁面上次使用時間域。如果R位為0，則計算頁面的生存時間（目前時間時間-上次頁面使用時間），并與時間間隔τ進行比較。如果生存時間大于τ則可以淘汰該頁面，如果所有頁面的生存時間都小于等于τ則選擇生存時間最長的頁面進行淘汰。工作集算法的缺點是需要掃描完整個頁表才能确定要被淘汰的頁面。
工作集時鐘算法是在工作集算法的基礎上加入了時鐘的概念，該算法使用了循環表，并用指針指向表中的元素。當發生缺頁中斷時檢測指針指向的元素是否滿足被淘汰的條件，如果滿足則淘汰指針執行的頁面，指針移動到下一個表項。如果不滿足淘汰條件，指針移動到下一個表項并重複該工作。