功能：置換算法是指當出現缺頁異常時，需要調入新頁面而內存已滿時，置換算法選擇被置換的物理頁面。

設計目標：

• 盡可能減少頁面的調入調出次數；
• 把未來不再訪問或短期內不訪問的頁面調出。

頁面鎖定：

了解具體的置換算法之前，先了解一個概念，頁面鎖定。頁面鎖定是用來描述某些必須常駐內存的邏輯頁面，比如操作系統的關鍵部分，再比如一些要求響應速度的代碼和數據。頁面鎖定是通過頁表中的鎖定標志位實現的。

分類：

1. 局部置換算法：置換頁面的選擇范圍僅限于當前進程占用的物理頁面內。具體又有一系列算法：最優算法、先進先出算法、最近最久未使用算法，最近最久未使用算法又衍生出兩種近似算法：時鐘算法、最不常用算法，
2. 全局置換算法：置換頁面的選擇范圍是所有可換出的物理頁面。具體有工作集算法、缺頁率算法。

最優界面置換算法：?

• 基本思路：選擇內存中等待時間最長（未來最長時間不訪問）的頁作為置換頁面。?
• 算法實現：缺頁時，計算內存中每個邏輯頁面的下一次訪問時間；選擇未來最長時間不訪問的頁面。
• 算法特征：

1. 只能是理想情況，OS無法實現（不知道未來情況）。?
2. 可以作為最佳的標準，在第二遍運行時利用第一次的訪問軌跡使用最優算法。其他算法應盡量逼近。

先進先出算法（ first-in first-out FIFO）

• 思路：選擇在內存中駐留時間最長的頁面并淘汰之。OS維護著一個隊列鏈表，淘汰首位，添加末位。
• 實現：維護一個記錄所有位于內存中的邏輯頁面；鏈表元素按駐留內存時間排序，鏈首最長，鏈尾最短；出現缺頁時，選擇鏈首頁面進行置環，新頁面加到鏈尾。
• 特征：性能較差，調出的頁面可能是常用頁面（駐留時間長，本身就說明可能常用），有belady現象（給的物理頁幀越多反而缺頁越頻繁）。因此該算法很少單獨使用。

最近最久未使用算法（least recently used LRU）

• 思路：選擇最長時間沒有被引用的頁面進行置換。是對最優置換算法的近似，以過去推未來。根據程序的局部性原理，如果最近一段時間內某些頁面被頻繁訪問，那么在將來還可能被頻繁訪問。反之，未被訪問的將來也不會被訪問。 程序應具有較好的局部性。
• 實現：缺頁時，計算內存中每個邏輯頁面上一次訪問時間；選擇上一次使用到當前時間最長的頁面
• 特征：最優置換算法的一種近似，但仍然很復雜，很難實現。下面是LRU算法的兩種可能的實現算法：

1. 頁面鏈表：系統維護一個按最近一次訪問時間排序的頁面鏈表，鏈表首節點是最近使用的頁面，尾節點是最久未使用的頁面，訪問內存時找到相應頁面，并把它移到鏈表之首，缺頁時，置換鏈表尾節點的頁面。
2. 活動頁面堆棧：訪問頁面時將此頁號壓入棧頂，并將棧內相同的頁號抽出，缺頁時置換棧底的頁面。（棧是先進后出，只有棧頂開口，怎么push棧底？）
3. 可以看到這兩種方式存在一個問題就是平時不缺頁時開銷較大，每次訪問頁面都需要遍歷鏈表或棧，找到相同的元素進行處理。

時鐘置換算法（Clock）：

時鐘置換算法是最近最久未使用算法的優化。先進先出是完全不考慮最近訪問情況，最近最久未使用算法是將所有頁面在整個運行過程中的訪問情況都進行考慮。而時鐘置換算法是這兩者的折中，即僅對頁面的訪問情況進行大致統計。具體實現

• 思路：僅對頁面的訪問情況進行大致統計
• 數據結構：在頁表項中增加訪問位，描述頁面在過去一段時間內的訪問情況；各頁面組織成環形鏈表；指針指向最先調入的頁面；
• 算法實現：頁面裝入內存時，訪問位初始化為0；訪問頁面（讀/寫）時，訪問位置1；缺頁時，從指針當前位置順序檢查環形鏈表【訪問位為0，則置環該頁；訪問位為1，則訪問位置0，并指針移動到下一個頁面，直到找到可置換得頁面】
• 特征：是FIFO和LRU的折中

?

時鐘置換算法實際還有一些改進。比如減少修改頁的缺頁處理開銷。因為被修改的頁如果要被置換，需要先寫到外存，再將需要的頁寫入內存，開銷至少乘2。因此為了減小修改過的頁被置換，可以遇到被修改過的頁指針就跳過。而在系統空閑時定期地將內存寫入外存。實現通過在頁面中增加修改位，并在訪問時進行相應修改，缺頁掃描時跳過有修改的頁面。

改進的Clock算法

• 思路：減少修改頁得缺頁處理開銷
• 算法：在頁面增加修改位，并在訪問時進行相應修改；缺頁時，修改頁面標志位，以跳過有修改得頁面

最不常用置換算法（Least Frequently Used, LFU）：

• 思路：選擇置換訪問次數最少的那個頁面?
• 實現：對每個頁面設置訪問計數器，當一個頁面被訪問時加1。置換數值最小的那個。?
• 特征：存在的問題就是統計開銷大，并且新拿進來的頁面可能因為計數較少馬上又被置換出去，對于后面這個問題的一個解決方法是已經計的數定期地衰減
• 最不常用置換算法頁式最近最久未使用算法的優化。可以看到LFU與LRU的區別。LRU關注多久未被訪問，時間越短越好，LFU關注訪問次數，次數越多越好。

LFU與時鐘算法都是對LRU算法的一種簡化近似，開銷減小，同時精度下降。LFU是比較難實現的，因此在內存管理中基本不會采用，但是在讀硬盤文件的時候對時間要求不高的場景中還是可以使用的。

Belady現象

當一個進程頻繁出現缺頁異常時，應該分配給進程更多的物理頁面，分配完后按照常理，缺頁異常出現的頻率應該降低。但是如果算法不好，很可能不會降低，我們把這種現象稱為Belady現象。

比如FIFO算法，因為置換出去的頁面不一定是進程近期不會訪問的頁面，如下圖：

但是LRU算法是沒有Belady現象的。時鐘算法和改進的時鐘算法也都是沒有Belady現象的。分配更多的頁面以為這更大的緩存，緩存越大命中率肯定升高。

綜合比較局部頁替換算法

LRU和FIFO的比較：LRU和FIFO本質都是先進先出，但LRU是頁面的最近訪問時間而不是進入內存的時間，有動態調整，符合棧算法的特性，空間越大缺頁越少。如果程序局部性，則LRU會很好。如果內存中所有頁面都沒有被訪問過會退化為FIFO。

Clock 和enhanced clock也是類似于FIFO的算法，但用了硬件的BIT來模擬了訪問時間和順序，近似了LRU，綜合起來較好，但也會退化為FIFO。

都對程序的訪問次序有局部性的要求，不然都會退化。

LRU、FIFO和Clock的比較：開銷上，LRU開銷大，FIFO開銷小但BELADY，折中的是Clock算法，開銷較小。對內存中還未被訪問的頁面，Clock效果等同LRU。Clock對曾經被訪問過的則不能記住其準確位置，而LRU算法可以。

全局置換算法：

局部置換算法沒有考慮進程訪問的差異，有時候給一個進程多分配一個物理頁面可以大幅度降低它的缺頁率。全局置換算法就是要為進程分配可變數目的物理頁面。它需要解決以下幾個問題：

• 進程在不同階段的內存需求是變化的
• 分配各進程的內存也需要在不同階段有所變化。
• 全局置換算法需要確定分配給進程的物理頁面數

首先我們需要知道CPU利用率與并發進程數之間的關系。隨著并發進程數從0增加，CPU的利用率也不斷增大；當進程數越來越多，內存訪問的局部性特征越來越被破壞，內存變的越來越緊張，利用率增長速度開始放緩，當增加到某個臨界點，CPU利用率開始下降。也就是CPU利用率與并發進程數存在相互促進和制約的關系。

工作集

一個進程當前使用的邏輯頁面集合，可以用一個二元函數W(t,Δ)，t是當前執行時刻，Δ是工作集窗口（working-set window），一個定長的頁面訪問的時間窗口。t+Δ構成了一個時間段，W(t,Δ)就是在當前時刻t之前的Δ時間內所有訪問頁面組成的集合，在隨t不斷更新。| W(t,Δ)|是工作集的大小即頁面數目。

工作集的變化：進程開始后，隨著訪問新頁面逐步建立較穩定的工作集，當內存訪問的局部性區域的位置大致穩定時| W(t,Δ)|波動很小，在過渡階段，則會快速擴張和收縮過渡到下一個穩定值。有波峰，有波谷。

常駐集

定義：在當前時刻，進程實際駐留在內存當中的頁面集合。

工作集與常駐集的關系：工作集是固有性質，常駐集取決于系統分配給進程的物理頁面數目和所采用的置換算法。

缺頁率與常駐集的關系：當常駐集包含了工作集，也就是工作集都在內存中，缺頁較少；工作集發生劇烈變動時，缺頁較多；當常駐集大小達到某個數目后，再分配物理頁幀也不會有明顯下降的缺頁率——可以把多出來的物理頁幀分給其他程序了

工作集置換算法：

• 思路：換出不在工作集中的頁面
• 窗口大小：當前時刻前τ個內存訪問的頁引用是工作集，τ被稱為窗口大小
• 實現方法：訪存鏈表：維護窗口內的訪存頁面鏈表；在訪存時，換出不在工作集的頁面；缺頁時，換入頁面，更新訪存鏈表。

工作集置換算法的思路是換出不在工作集中的頁面。局部置換算法是在缺頁異常發生時才決定置換哪個頁面，但是工作集置換算法不一定是在缺頁時才做這件事，而是在訪存時就進行處理。工作集置換算法中有一個窗口大小?τ，當前時刻前 τ?個內存訪問的頁引用是工作集。

可以看到，缺頁處理很簡單，但是每次訪存都要進行判斷，開銷還是很大的。這與LRU算法是類似的。

缺頁率置換算法（Page-Fault-Frequency, PFF）

缺頁率=缺頁次數/內存訪問次數 =1/缺頁的平均時間間隔

影響因素有：頁面置換算法，分配給進程的物理頁面數目(越多越小)，頁面本身的大小（頁面大則會小），編程方法（局部性好就會小）

缺頁率置換算法是依據缺頁率來決定哪些頁面放到內存哪些被置換出去。其中我們能夠控制的是頁面置換算法。

正常情況下，隨著分配給進程的物理頁面數增多，缺頁率會下降，缺頁率置換算法通過調節常駐集的大小，使每個進程的缺頁率保持在一個合理的范圍內。如果缺頁率過高，則增加物理頁面數，如果缺頁率過低，則降低物理頁面數。

• 思路：動態調整常駐集的大小。性能較好，但增加了系統開銷?
• 具體機制：

1. 訪存時設置引用位標志
2. 缺頁時，計算從上次缺頁時間?tlast?到現在的時間?tcurrent 間隔，如果時間間隔?tcurrent -?tlast 大于常量 T，則置換所有在 [tlast ,? tcurrent]??時間內沒有被引用的頁，以減少常駐集的大小；如果時間間隔?tcurrent -?tlast?小于等于常量 T，則增加缺失頁到常駐集。

對比缺頁率置換算法與工作集置換算法，缺頁率置換算法是在缺頁異常時進行處理，工作集置換算法是在訪存時進行處理，缺頁的出現頻率是遠小于訪存的，開銷降下來了。

抖動

• 抖動：如果分配給一個進程的物理頁面太少，常駐集遠小于工作集，則缺頁率會很大，頻繁在內外存之間替換頁面，使進程的運行慢，這種狀態成為”抖動”。
• 產生抖動的原因：隨著駐留內存的進程數目增加，分配給每個進程的物理頁面數不斷減少，缺頁率上升。因此OS要選擇一個適當的進程數目和進程需要的幀數，在并發水平和缺頁率中達到平衡。

負載控制

我們希望平均缺頁間隔時間（MTBF）大于等于缺頁異常處理時間（PFST）。因此如下圖右側虛線以左是CPU滿負荷工作也滿足平均缺頁間隔時間大于等于缺頁異常處理時間的區域。