圖解：頁面替換算法

頁面替換算法

功能：當缺頁中斷髮生，需要調入新的頁面而內存已滿時，選擇內存當中哪個物理頁面被置換。

目標：儘可能地減少頁面的換進換出次數（即缺頁中斷的次數）。具體來說，把未來不再使用的或短期內較少使用的頁面換出，通常只能在局部原理指導下依據過去的統計數據來進行預測。

最優頁面替換算法

基本思路：當一個缺頁中斷髮生時，對於保存在內存當中的每一個邏輯頁面，計算在它的下一次訪問之前，還需等待多長時間，從中選擇等待時間最長的那個作爲被置換的頁面。

這只是一種理想情況，在實際中無法實現，因爲操作系統無法知道每一個頁面要等待多長時間以後纔會被再次訪問。

可用作其它算法的性能評價的依據 (在一個模擬器上運行某個程序，並記錄每一次的頁面訪問情況，在第二遍運行時即可使用最優算法)。

簡單一句話，最優頁面替換算法就是替換在將來最長時間內不需要的頁面。

假設頁幀（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 次。

時鐘頁面置換算法

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 考慮的是訪問次數或頻度，訪問次數越多越好。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/-S3xiu7YPn6ZhYQRsBndpQ