點擊上方“程序員大白”，選擇“星標”公眾號

重磅干貨，第一時間送達

頁面替換算法

功能：當(dāng)缺頁中斷發(fā)生，需要調(diào)入新的頁面而內(nèi)存已滿時，選擇內(nèi)存當(dāng)中哪個物理頁面被置換。

目標：盡可能地減少頁面的換進換出次數(shù)（即缺頁中斷的次數(shù)）。具體來說，把未來不再使用的或短期內(nèi)較少使用的頁面換出，通常只能在局部原理指導(dǎo)下依據(jù)過去的統(tǒng)計數(shù)據(jù)來進行預(yù)測。

最優(yōu)頁面替換算法

基本思路：當(dāng)一個缺頁中斷發(fā)生時，對于保存在內(nèi)存當(dāng)中的每一個邏輯頁面，計算在它的下一次訪問之前，還需等待多長時間，從中選擇等待時間最長的那個作為被置換的頁面。

這只是一種理想情況，在實際中無法實現(xiàn)，因為操作系統(tǒng)無法知道每一個頁面要等待多長時間以后才會被再次訪問。

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

簡單一句話，最優(yōu)頁面替換算法就是替換在將來最長時間內(nèi)不需要的頁面。

假設(shè)頁幀（Page Frames）的大小為 4，請求頁面序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2，采用最優(yōu)頁面替換算法的缺頁異常（Page Fault）的次數(shù)為多少？

初始時，頁槽均為空，所以請求頁面 7 0 1 2 被分配到空的頁槽，產(chǎn)生 4 次缺頁異常。

緊接著，請求頁面 0 時，發(fā)現(xiàn)已經(jīng)存在頁幀中，0 次缺頁異常；

當(dāng)請求頁面 3 時，頁面 7 由于為在將來最長時間內(nèi)不需要訪問，所以被 3 替換，1 次缺頁異常。

0 號頁面命中，0 次頁面異常；

請求頁面 4 不存在頁幀中，替換頁面 1 ，1 次缺頁異常；

對之后的請求頁面序列 2，3，0，3，2 而言，均命中，固無缺頁異常。

所以總共發(fā)生了 6 次缺頁異常，即圖中的 Miss 狀態(tài)，其中的 Hit 表示命中，無缺頁異常產(chǎn)生。

模擬實現(xiàn)一個最優(yōu)頁面替換算法：

輸入 : 頁幀數(shù) fn = 3
頁面 pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
輸出 : 命中次數(shù) hits = 11 缺頁異常 miss = 9
輸入 : 頁幀數(shù) fn = 4 頁面 pg[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
輸出 : 命中次數(shù) hits = 7 缺頁異常 miss = 6

我們以頁幀數(shù) 4 ，請求序列 {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2} 為例進行說明。

首先我們創(chuàng)建一個空的數(shù)組 fr 模擬頁幀：

請求頁面 7，發(fā)現(xiàn)不在數(shù)組 fr 當(dāng)中且數(shù)組 fr 的大小 fr.size() < fn 頁幀大小，則直接將請求頁面 7 插入數(shù)組 fr中：

請求頁面 {0,1,2} 與請求頁面 7 情況類似，則依次將其添加到數(shù)組當(dāng)中：

緊接著請求頁面 0，遍歷數(shù)組 fr ，發(fā)現(xiàn) 0 號頁面已經(jīng)在其中了，則命中次數(shù) hit 加 1。

請求 3 號頁面，遍歷數(shù)組 fr ，發(fā)現(xiàn)不在其中且數(shù)組已滿（fr.size == fn ），則需要找到要替換的頁面，此時選擇替換在將來最長時間內(nèi)不需要的頁面 。這里的將來最長時間不需要的頁面，我們可以使用頁面數(shù)組 pg[] 的下標進行表示。

遍歷數(shù)組 fr[] ，并結(jié)合請求頁面數(shù)組 pg[] 找到在將來最長時間內(nèi)不需要的頁面。

fr[0] = 7 ，我們從 3 號頁面開始在數(shù)組 pg[] 中向后查找 7 號頁面，發(fā)現(xiàn)其根本不存在，也就說 7 號頁面就是在將來最長時間內(nèi)不需要的頁面。所以 3 號頁面替換 7 號頁面。

再訪問 0 號頁面，發(fā)現(xiàn)存在，則跳過；

訪問 4 號頁面，發(fā)現(xiàn)不在頁幀數(shù)組 fr 當(dāng)中，則替換掉在將來最長時間內(nèi)不需要的頁面 1：

之后訪問頁面 {2, 3, 0, 3, 2} 均為命中，總共命中 6 次。

參考實現(xiàn)

#include <bits/stdc++.h>
using namespace std;

// 用于檢查頁幀中是否存在當(dāng)前要訪問的頁 key
bool search(int key, vector<int>& fr)
{
     for (int i = 0; i < fr.size(); i++)
        if (fr[i] == key)
           return true;
     return false;
}

// 用于預(yù)測將來
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 中的所有頁在將來都沒出現(xiàn)過，則返回其中任何頁，我們返回 0。否則我們將返回 res。
     return (res == -1) ? 0 : res;
}

/**
 * pg[] 請求頁面序列
 * pn 請求頁面數(shù)
 * fn 頁幀數(shù)
 */
。
void optimalPage(int pg[], int pn, int fn)
{
    // 為給定數(shù)量的幀創(chuàng)建一個數(shù)組，并將其初始化為空。
   vector<int> fr;

   // 遍歷頁面引用數(shù)組并檢查未命中和命中。
   int hit = 0;
   for (int i = 0; i < pn; i++) {
      // 在內(nèi)存中命中頁面 : HIT
      if (search(pg[i], fr)) {
         hit++;
         continue;
      }
      // 頁面在內(nèi)存中不存在 : MISS
      // 如果頁幀中有可用的空間，則直接將缺失頁加入其中。
      if (fr.size() < fn) {
           fr.push_back(pg[i]);
      }
      else { // 找到要替換的頁
           int j = predict(pg, fr, pn, i + 1);
           fr[j] = pg[i];
        }
     }
     cout << "命中次數(shù) = " << hit << endl;
     cout << "未命中次數(shù) = " << 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 函數(shù)大家可以換成哈希或者二分查找等，其中最關(guān)鍵的是 predict() 函數(shù)，用于查找在將來最長時間內(nèi)不會使用到的頁面，其實也就是兩層 for 循環(huán)嵌套。

先進先出算法

FIFO（First In，F(xiàn)irst Out）就是先進先出算法。

基本思路：選擇在內(nèi)存中駐留時間最長的頁面并淘汰。具體來說，系統(tǒng)維護著一個鏈表，記錄了所有位于內(nèi)存當(dāng)中的邏輯頁面。從鏈表的排列順序來看，鏈首頁面的駐留時間最長，鏈尾頁面的駐留時間最短。當(dāng)發(fā)生一個缺頁中斷時，把鏈首頁面淘汰出局，并把新的頁面添加到鏈表的末尾。

性能較差，調(diào)出的頁面可能是經(jīng)常要訪問的頁面，并且產(chǎn)生 Belady 現(xiàn)象，F(xiàn)IFO 算法很少單獨使用。

假設(shè)頁幀（Page Frames）的大小為 4，請求頁面序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2，采用 FIFO 算法的缺頁異常的次數(shù)為多少？

如上圖所示，F(xiàn)IFO，先進先出，類似隊列的特性。

對于請求頁面 7，0，1，2 ，發(fā)生 4 次缺頁中斷，分別為其分配頁；

訪問頁面 0 時，命中；

訪問頁面 3 時，缺頁異常，此時會淘汰掉位于隊列頭的頁面 7 ，將頁面 3 插入到隊尾，即選擇在內(nèi)存中駐留時間最長的頁面并淘汰。

頁面 0 命中；

訪問頁面 4 時，發(fā)生缺頁異常，此時淘汰頁面 0 ；

訪問頁面 2 和 3 時，均命中；

訪問頁面 0 時，缺頁異常，淘汰頁面 1 ，插入頁面 0 ；

最后訪問頁面 3 和 2 均命中。

共發(fā)生缺頁異常次數(shù)為 7 次。

時鐘頁面置換算法

Clock 頁面置換算法，LRU 的近似，對 FIFO 的一種改進；

基本思路：

需要用到頁表頂當(dāng)中的訪問位（Access Bit），當(dāng)一個頁面被裝入內(nèi)存時，把該位初始化為 0。然后如果這個頁面被訪問（讀寫），則把該位置置為 1。
把各個頁面組織成環(huán)形鏈表（類似鐘表面），把指針指向最老的頁面（最先進來的頁面）；
當(dāng)發(fā)生一個缺頁中斷時，考察指針所指向的最老頁面，若它的訪問位為 0 ，立即淘汰；若訪問位為 1，則把該位置置為 0，然后指針向下移動一格。如此下去，直到找到被淘汰的頁面，然后把指針移動到它的下一格。

假設(shè)頁幀（Page Frames）的大小為 4，請求頁面序列為：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2，采用時鐘頁面替換算法的缺頁異常的次數(shù)為多少？

初始時，頁幀為空，如下圖所示的一個環(huán)形鏈表，是不是很想一個時鐘：

請求頁面 7，產(chǎn)生缺頁中斷，則將其裝入內(nèi)存，把該頁面的訪問位初始化為 0：

依次訪問頁面 0、1 和 2，與前面的方法類似：

緊接著請求頁面 0 ，發(fā)現(xiàn)頁面 0 已經(jīng)在內(nèi)存中了，則硬件會把訪問位置為 1，并將指針下移：

請求頁面 3 時，發(fā)生缺頁中斷，此時指針所指向的頁面 7 的訪問位為 0，則立即淘汰掉并替換為頁面 3，訪問位為 1：

請求頁面 0，已存在內(nèi)存中，硬件將其訪問位置為 1，與上圖一樣，沒有變化；

請求頁面 4，發(fā)生缺頁中斷，首先將 3號頁面的訪問位置為 0， 0 號頁面的訪問位置為 0，指針下移，發(fā)現(xiàn) 1 號頁面的訪問位為0，則淘汰頁面 1，替換為 4，訪問位置 1 并下移指針：

請求頁面 2 ，已存在內(nèi)存中，硬件將其訪問位置 1：

請求 3 號頁面，將 3 號頁面的訪問位置為 1，將指針下移：

請求 0 號頁面，將 0 號頁面的訪問位置 1，指針下移：

總的缺頁中斷次數(shù)為 5 次。

最不常用算法 LFU

基本思路：當(dāng)一個缺頁中斷發(fā)生時，選擇訪問次數(shù)最少的那個頁面，并淘汰之。

實現(xiàn)方法：對每一個頁設(shè)置一個訪問計數(shù)器，每當(dāng)一個頁面被訪問時，該頁面的訪問計數(shù)器加 1。在發(fā)生缺頁中斷時，淘汰計數(shù)值最小的那個頁面。如果所有頁具有相同的頻率，則對該頁采取 LRU 方法并刪除該頁。

LRU 和 LFU 的區(qū)別：LRU 考察的是多久未訪問，時間越短越好；而 LFU 考慮的是訪問次數(shù)或頻度，訪問次數(shù)越多越好。

推薦閱讀
國產(chǎn)小眾瀏覽器因屏蔽視頻廣告，被索賠100萬（后續(xù)）
年輕人“不講武德”：因看黃片上癮，把網(wǎng)站和786名女主播起訴了
中國聯(lián)通官網(wǎng)被發(fā)現(xiàn)含木馬腳本，可向用戶推廣色情APP
張一鳴：每個逆襲的年輕人，都具備的底層能力

關(guān)于程序員大白

程序員大白是一群哈工大，東北大學(xué)，西湖大學(xué)和上海交通大學(xué)的碩士博士運營維護的號，大家樂于分享高質(zhì)量文章，喜歡總結(jié)知識，歡迎關(guān)注[程序員大白]，大家一起學(xué)習(xí)進步！

圖解：頁面替換算法