之前幾篇部落格記錄了OS記憶體管理的一些知識和技術，接下來将繼續深入，介紹一些頁面置換算法，這裡包括一些我們大家都略有耳聞的算法。
置換算法
當出現缺頁故障時，需要從外存調入新的頁面到記憶體中去，而如果此時記憶體已滿，于是就要按照一定政策置換一些實體頁幀出來，這就是置換算法的目的。而置換算法的目标就是
盡量減少頁面的調入調出次數
頁面置換算法主要可分為兩大類：
- 局部頁面置換算法
置換頁面的選擇範圍僅限于目前程序占用的實體頁面内。比較有代表性的算法有
最優置換算法
、
FIFO算法
、
最近最久未使用算法
、
時鐘算法
、
最不常用算法
- 全局頁面置換算法
全局頁面置換算法的選擇範圍是所有可換出的實體頁，比較有代表性的算法有
工作集算法
、
缺頁率算法
1. 局部頁面置換算法
所謂局部頁面置換，就是說，如果OS給一個程式固定配置設定了5個實體頁幀，當這些頁幀滿了後，如何進行頁面置換。
最優置換算法（opt算法）
思路就是，當産生缺頁時，計算每個邏輯頁面的下一次通路時間，選擇未來最長時間不通路的頁面進行置換。
比如現在記憶體裡面有a、b、c三個實體頁幀，現在來了一個d頁面，又知道a在未來的第3個頁面後又會重新需要通路、b在未來的第2個頁面後又會重新需要通路，c則是未來的第5個時間。那麼這樣的話，按照opt算法，我們就将c實體頁面換出，将d頁面放置在原來c頁面的位置即可。
細心的筒子可以發現一個問題，我這裡說在未來的第幾個頁面又會重新需要，那真的運作一個程式的時候，OS哪裡可能知道未來那個頁面會被重新使用 ？是以說，這是一個
純理想
的算法，無法實作，隻能作為置換算法的一個性能評估依據。
再舉個栗子，大家可以自己在腦子裡模拟一下執行過程，這裡假設在0時刻，abcd四個頁都已經在記憶體中了。紫色的圈表示在該時刻出現了缺頁異常，紅色的箭頭表示置換的是哪個頁。
FIFO算法
FIFO即First-In-First-out，先入先出算法，思想就是将那個在記憶體中駐留時間最長的頁面進行置換。這裡實作的方法可以是通過維護一個連結清單，按照頁面的到來順序，依次插傳入連結表尾部，每次要置換頁的時候，就對鍊首繼續置換，新頁插入到連結清單尾。
但是，這個算法的性能比較差，因為它不知道未來頁面的到來情況（畢竟它隻看到的是已經駐留的頁面），有可能頻繁的将一些再次會用到的頁進行置換。此外，FIFO還有可能出現
belady現象
（變成女人??? exm??? 開個玩笑。。 ）這個現象闡述的是這樣一種情況，若OS給程序配置設定的實體頁面數量增加，缺頁次數并不一定因為實體頁面數量的增加而減少，反而會更多。
是以，總的來說，FIFOF很少單獨使用，會配合一些其他算法使用，例如後面會講到的時鐘算法。
FIFO也來個栗子，假設在0時刻之前，abcd四個頁面的到來順序為abcd，可見，出現頁面置換的次數較多。
值得注意的是，在FIFO算法中，會存在
Belady現象
，這個現象就是說，随着OS給每一個程序所配置設定的實體頁數量增加，出現缺頁異常的次數非但沒有減少，反而增加了。
注意：這裡并不是說，一直增加實體頁面數量，缺頁異常一直增加，這顯然是不對的，假設一個程序被配置設定到的實體頁面數量無窮大，那缺頁異常肯定是0. Belady現象
最近最久未使用算法 （Least Recently Used, LRU）
這個算法從英文的字面意思上就可以了解它在幹什麼了。其實還是一個模拟未來頁面到來情況的思想，算是對
OPT算法
的一個近似，LRU算法認為，最近那個最近一直沒被使用的頁，在未來也最有可能不會被使用，是以将它置換出去（實際上，這也是基于我們程式有較好局部性的特征基礎之上的）。
缺頁時，計算記憶體中每個邏輯頁面的上一次通路時間，置換上一次通路時間距離現在最遠的那個頁面（即時間最小） 。
栗子如下，假設在0時刻abcd四個頁面已經駐留在記憶體中了。
LRU的實作方法大緻有兩種：
- 基于連結清單的實作
OS維護一個按最近一次通路時間排序的頁面連結清單，其中，連結清單首節點是最近剛剛使用過的頁面，而連結清單尾結點是最久未使用的頁面，按照上圖所示例子的話，在t=5時刻之前，連結清單的狀态如下：
每次缺頁的适合，就将連結清單尾部的頁面進行置換，并把它移到連結清單的首部去。t=5時刻置換頁動作完成後，連結清單的狀态如下：
2. 基于棧的實作
思路和連結清單的實作差不多，如下圖：
時鐘算法（clock）
像上面的LRU算法，性能其實是不錯的，唯一的缺點就是維護連結清單或棧相對來說要麻煩一些，于是出現了時鐘算法，它的思路是對頁面的訪做大緻的統計，不一定是完全嚴格按照LRU的思路，比如，在t=1時刻的頁面a和t=2時刻的頁面b，時鐘算法有可能第一個換頁面b而不是a。
時鐘算法采用了一種特殊的資料結構——
環形清單
，且在頁表項中增加了一個通路位（還記得嗎？之前的部落格虛存管理中提到過，當時說這個位是為了頁面置換時用的），環形清單的指針指向最先調入的頁面。
算法的思想是，通路頁面時，在頁表項紀錄頁面的通路情況，缺頁時，從指針出開始順序地、循環地查找未被通路的頁面進行置換。時鐘算法其實是LRU和FIFO的折中。
算法實作的pseudo code如下：
while(目标頁面不存在)
{
if(目前指針所指的頁表項的通路位為0)
{
替換目前頁；
指派目前頁表項的通路位為1；
}
else
{
指派目前指針所指的頁表項的通路位為1;
}
指針下移一位；
}
例子如下，假設在0時刻，時鐘算法的目前指針指向第一項，藍色的那一項就是目前指針所指項：
在上圖中，需要注意的是，如果存在頁表項，隻是其對應的通路位為0的時候，在通路該頁時，隻會将通路位置為1。而出現頁面置換時，操作完後，指針要下移一位。
關于clock算法，還有其改進算法，稱為二次機會法，由于筆者表達能力有限，這裡給個視訊講解連結。 >>二次機會算法<<，其思路和clock算法是很相似的。
最不常用算法（Least Frequently Used，LFU）
最不常用算法并不是說這個算法不常用。。。
其實，這也是對未來将出現的頁面的另一種模拟。該算法認為，目前通路次數較少的頁面，在未來也有較大機率不會被通路，于是，每次出現缺頁異常時，選擇通路次數最少的那個頁面，并将之淘汰。
舉例如下，上标表示該頁的通路次數：
2. 全局頁面置換算法
所謂全局頁面置換算法，就是指OS基于多個程序之間的考慮（即全局的思想），為程序配置設定
可變數目
的實體頁幀。最終目的還是為了減少出現缺頁異常的數量。
下面介紹幾個概念：
工作集（working set）
工作集指的是一個程序目前正在使用的邏輯頁面的集合，可表示為一個二進制函數 W ( t , △ ) W(t,\triangle) W(t,△),其中 t t t是程序目前執行的時刻， △ \triangle △稱為工作集視窗（working-set window），即一個定長的頁面通路時間視窗。
則：
W ( t , △ ) W(t,\triangle) W(t,△)是指目前時刻t前的 △ \triangle △時間視窗中的所有通路頁面組成的集合。
∣ W ( t , △ ) ∣ |W(t,\triangle)| ∣W(t,△)∣是指工作集大學，即頁面數量。
一般來說，程序的初始階段，随着通路新頁面的逐漸建立，工作集的數量會增加，然後程序中間階段會比較平穩，一旦又有新的頁通路，工作集會産生一定波動，然後再保持平穩，整體呈以下圖示狀态：
常駐集
常駐集指的是在目前某個時刻，程序實際駐留在記憶體當中的頁面集合。
常駐集和工作集的差別是，前者指在記憶體中的實體頁，而工作集是指邏輯頁。
工作集置換算法
該算法的思路是，在訪存時，換出不在工作集中的頁面；而在缺頁時，換入缺失的頁面。
如上圖所示，稍加解釋一下。在t=1時刻，由于缺頁C，于是将之換入，在t=2時刻，由于C頁面已經存在，是一次訪存操作，因為工作集的視窗大小為4，是以目前的工作集為 { d , a , c } \{d,a,c\} {d,a,c}，于是需要将頁面e替換出去，後面的操作同理。
缺頁率置換算法（page fault frequency，PFF）
該算法中，需要記錄兩個時間 t c u r r e n t 和 t l a s t t_{current}和t_{last} tcurrent和tlast，分别表示目前缺頁時間和上一次産生缺頁異常的時間。算法思路是：
如果 t c u r r e n t − t l a s t > T t_{current}-t_{last}>T tcurrent−tlast>T,則置換所有在 [ t l a s t , t c u r r e n t ] [t_{last},t_{current}] [tlast,tcurrent]間沒有被通路過的頁
如果 t c u r r e n t − t l a s t ≤ T t_{current}-t_{last} \le T tcurrent−tlast≤T,則增加缺失的頁到工作集中。
這裡的T指的是視窗大小。
直覺的一個了解是，當 t c u r r e n t − t l a s t > T t_{current}-t_{last}>T tcurrent−tlast>T，這說明距離上一次産生缺頁異常的時間較遠，即在較長一段時間内沒有發生缺頁異常，于是将一些自上一次發生缺頁異常以來，存在于工作集中又從未被通路過的頁置換出去（因為它們很有可能不再會被通路了）；而當 t c u r r e n t − t l a s t ≤ T t_{current}-t_{last} \le T tcurrent−tlast≤T時，這說明距離上一次産生缺頁異常的時間較近，，需要把缺失的頁放進來。