圖解：頁面替換算法
本文轉載自微信公眾號「景禹」，作者景禹。轉載本文請聯系景禹公眾號。
頁面替換算法
功能：當缺頁中斷發生，需要調入新的頁面而內存已滿時，選擇內存當中哪個物理頁面被置換。
目標：盡可能地減少頁面的換進換出次數(即缺頁中斷的次數)。具體來說，把未來不再使用的或短期內較少使用的頁面換出，通常只能在局部原理指導下依據過去的統計數據來進行預測。
最優頁面替換算法
基本思路：當一個缺頁中斷發生時，對于保存在內存當中的每一個邏輯頁面，計算在它的下一次訪問之前，還需等待多長時間，從中選擇等待時間最長的那個作為被置換的頁面。
這只是一種理想情況，在實際中無法實現，因為操作系統無法知道每一個頁面要等待多長時間以后才會被再次訪問。
可用作其它算法的性能評價的依據(在一個模擬器上運行某個程序，并記錄每一次的頁面訪問情況，在第二遍運行時即可使用最優算法)。
簡單一句話，最優頁面替換算法就是替換在將來最長時間內不需要的頁面。
假設頁幀(Page Frames)的大小為 4， 請求頁面序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2，采用最優頁面替換算法的缺頁異常(Page Fault)的次數為多少?
初始時，頁槽均為空，所以請求頁面 7 0 1 2 被分配到空的頁槽，產生 4 次缺頁異常。
緊接著，請求頁面 0 時，發現已經存在頁幀中，0 次缺頁異常;
當請求頁面 3 時，頁面 7 由于為在將來最長時間內不需要訪問，所以被 3 替換，1 次缺頁異常。
0 號頁面命中，0 次頁面異常;
請求頁面 4 不存在頁幀中，替換頁面 1 ，1 次缺頁異常;
對之后的請求頁面序列 2，3，0，3，2 而言，均命中，固無缺頁異常。
所以總共發生了 6 次缺頁異常，即圖中的 Miss 狀態，其中的 Hit 表示命中，無缺頁異常產生。
模擬實現一個最優頁面替換算法：
輸入 : 頁幀數 fn = 3
頁面 pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
輸出 : 命中次數 hits = 11 缺頁異常 miss = 9
輸入 : 頁幀數 fn = 4 頁面 pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
輸出 : 命中次數 hits = 7 缺頁異常 miss = 6
我們以頁幀數 4 ，請求序列 {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2} 為例進行說明。
首先我們創建一個空的數組 fr 模擬頁幀：
請求頁面 7，發現不在數組 fr 當中且數組 fr 的大小 fr.size() < fn 頁幀大小，則直接將請求頁面 7 插入數組 fr中：
請求頁面 {0,1,2} 與請求頁面 7 情況類似，則依次將其添加到數組當中：
緊接著請求頁面 0，遍歷數組 fr ，發現 0 號頁面已經在其中了，則命中次數 hit 加 1。
請求 3 號頁面，遍歷數組 fr ，發現不在其中且數組已滿(fr.size == fn )，則需要找到要替換的頁面，此時選擇替換在將來最長時間內不需要的頁面 。這里的將來最長時間不需要的頁面，我們可以使用頁面數組 pg[] 的下標進行表示。
遍歷數組 fr[] ，并結合請求頁面數組 pg[] 找到在將來最長時間內不需要的頁面。
fr[0] = 7 ，我們從 3 號頁面開始在數組 pg[] 中向后查找 7 號頁面，發現其根本不存在，也就說 7 號頁面就是在將來最長時間內不需要的頁面。所以 3 號頁面替換 7 號頁面。
再訪問 0 號頁面，發現存在，則跳過;
訪問 4 號頁面，發現不在頁幀數組 fr 當中，則替換掉在將來最長時間內不需要的頁面 1：
之后訪問頁面 {2, 3, 0, 3, 2} 均為命中，總共命中 6 次。
參考實現
- #include <bits/stdc++.h>
- using namespace std;
- // 用于檢查頁幀中是否存在當前要訪問的頁 key
- bool search(int key, vector<int>& fr)
- {
- for (int i = 0; i < fr.size(); i++)
- if (fr[i] == key)
- return true;
- return false;
- }
- // 用于預測將來
- int predict(int pg[], vector<int>& fr, int pn, int index)
- {
- // 存儲在將來最近要使用的頁面的索引
- int res = -1, farthest = index;
- for (int i = 0; i < fr.size(); i++) {
- int j;
- for (j = index; j < pn; j++) {
- if (fr[i] == pg[j]) {
- if (j > farthest) {
- farthest = j;
- res = i;
- }
- break;
- }
- }
- // 如果某個頁面將來從未被引用過，請將其返回。
- if (j == pn)
- return i;
- }
- // 如果 fr 中的所有頁在將來都沒出現過，則返回其中任何頁，我們返回 0。否則我們將返回 res。
- return (res == -1) ? 0 : res;
- }
- /**
- * pg[] 請求頁面序列
- * pn 請求頁面數
- * fn 頁幀數
- */
- 。
- void optimalPage(int pg[], int pn, int fn)
- {
- // 為給定數量的幀創建一個數組，并將其初始化為空。
- vector<int> fr;
- // 遍歷頁面引用數組并檢查未命中和命中。
- int hit = 0;
- for (int i = 0; i < pn; i++) {
- // 在內存中命中頁面 : HIT
- if (search(pg[i], fr)) {
- hit++;
- continue;
- }
- // 頁面在內存中不存在 : MISS
- // 如果頁幀中有可用的空間，則直接將缺失頁加入其中。
- if (fr.size() < fn) {
- fr.push_back(pg[i]);
- }
- else { // 找到要替換的頁
- int j = predict(pg, fr, pn, i + 1);
- fr[j] = pg[i];
- }
- }
- cout << "命中次數 = " << hit << endl;
- cout << "未命中次數 = " << pn - hit << endl;
- }
- int main()
- {
- int pg[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 };
- int pn = sizeof(pg) / sizeof(pg[0]);
- int fn = 4;
- optimalPage(pg, pn, fn);
- return 0;
- }
其中的 search 函數大家可以換成哈希或者二分查找等，其中最關鍵的是 predict() 函數，用于查找在將來最長時間內不會使用到的頁面，其實也就是兩層 for 循環嵌套。
先進先出算法
FIFO(First In，First Out)就是先進先出算法。
基本思路：選擇在內存中駐留時間最長的頁面并淘汰。具體來說，系統維護著一個鏈表，記錄了所有位于內存當中的邏輯頁面。從鏈表的排列順序來看，鏈首頁面的駐留時間最長，鏈尾頁面的駐留時間最短。當發生一個缺頁中斷時，把鏈首頁面淘汰出局，并把新的頁面添加到鏈表的末尾。
性能較差，調出的頁面可能是經常要訪問的頁面，并且產生 Belady 現象，FIFO 算法很少單獨使用。
假設頁幀(Page Frames)的大小為 4， 請求頁面序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2，采用 FIFO 算法的缺頁異常的次數為多少?
如上圖所示，FIFO，先進先出，類似隊列的特性。
對于請求頁面 7，0，1，2 ，發生 4 次缺頁中斷，分別為其分配頁;
訪問頁面 0 時，命中;
訪問頁面 3 時，缺頁異常，此時會淘汰掉位于隊列頭的頁面 7 ，將頁面 3 插入到隊尾，即選擇在內存中駐留時間最長的頁面并淘汰。
頁面 0 命中;
訪問頁面 4 時，發生缺頁異常，此時淘汰頁面 0 ;
訪問頁面 2 和 3 時，均命中;
訪問頁面 0 時，缺頁異常，淘汰頁面 1 ，插入頁面 0 ;
最后訪問頁面 3 和 2 均命中。
共發生缺頁異常次數為 7 次。
最近最少使用算法
關于最近最少頁面替換是算法的詳細信息可以參考：最近最少使用 LRU 算法
時鐘頁面置換算法
Clock 頁面置換算法，LRU 的近似，對 FIFO 的一種改進;
基本思路：
- 需要用到頁表頂當中的訪問位(Access Bit)，當一個頁面被裝入內存時，把該位初始化為 0。然后如果這個頁面被訪問(讀寫)，則把該位置置為 1。
- 把各個頁面組織成環形鏈表(類似鐘表面)，把指針指向最老的頁面(最先進來的頁面);
- 當發生一個缺頁中斷時，考察指針所指向的最老頁面，若它的訪問位為 0 ，立即淘汰;若訪問位為 1，則把該位置置為 0，然后指針向下移動一格。如此下去，直到找到被淘汰的頁面，然后把指針移動到它的下一格。
假設頁幀(Page Frames)的大小為 4， 請求頁面序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2，采用 時鐘頁面替換算法的缺頁異常的次數為多少?
初始時，頁幀為空，如下圖所示的一個環形鏈表，是不是很想一個時鐘：
請求頁面 7，產生缺頁中斷，則將其裝入內存，把該頁面的訪問位初始化為 0：
依次訪問頁面 0、1 和 2，與前面的方法類似：
緊接著請求頁面 0 ，發現頁面 0 已經在內存中了，則硬件會把訪問位置為 1，并將指針下移：
請求頁面 3 時，發生缺頁中斷，此時指針所指向的頁面 7 的訪問位為 0，則立即淘汰掉并替換為頁面 3，訪問位為 1：
請求頁面 0，已存在內存中，硬件將其訪問位置為 1，與上圖一樣，沒有變化;
請求頁面 4，發生缺頁中斷，首先將 3號頁面的訪問位置為 0， 0 號頁面的訪問位置為 0，指針下移，發現 1 號頁面的訪問位為0，則淘汰頁面 1，替換為 4，訪問位置 1 并下移指針：
請求頁面 2 ，已存在內存中，硬件將其訪問位置 1：
請求 3 號頁面，將 3 號頁面的訪問位置為 1，將指針下移：
請求 0 號頁面，將 0 號頁面的訪問位置 1，指針下移：
總的缺頁中斷次數為 5 次。
最不常用算法 LFU
基本思路：當一個缺頁中斷發生時，選擇訪問次數最少的那個頁面，并淘汰之。
實現方法：對每一個頁設置一個訪問計數器，每當一個頁面被訪問時，該頁面的訪問計數器加 1。在發生缺頁中斷時，淘汰計數值最小的那個頁面。如果所有頁具有相同的頻率，則對該頁采取 LRU 方法并刪除該頁。
LRU 和 LFU 的區別：LRU 考察的是多久未訪問，時間越短越好;而 LFU 考慮的是訪問次數或頻度，訪問次數越多越好。
本文轉載自微信公眾號「景禹」，可以通過以下二維碼關注。轉載本文請聯系景禹公眾號。
