[[398509]]

本文轉(zhuǎn)載自微信公眾號「景禹」，作者景禹。轉(zhuǎn)載本文請聯(lián)系景禹公眾號。

頁面替換算法

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

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

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

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

這只是一種理想情況，在實(shí)際中無法實(shí)現(xiàn)，因?yàn)椴僮飨到y(tǒng)無法知道每一個(gè)頁面要等待多長時(shí)間以后才會被再次訪問。

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

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

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

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

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

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

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

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

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

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

模擬實(shí)現(xiàn)一個(gè)最優(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} 為例進(jìn)行說明。

首先我們創(chuàng)建一個(gè)空的數(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 )，則需要找到要替換的頁面，此時(shí)選擇替換在將來最長時(shí)間內(nèi)不需要的頁面 。這里的將來最長時(shí)間不需要的頁面，我們可以使用頁面數(shù)組 pg[] 的下標(biāo)進(jìn)行表示。

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

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

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

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

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

參考實(shí)現(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; 
            } 
        } 
 
        // 如果某個(gè)頁面將來從未被引用過，請將其返回。 
        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)建一個(gè)數(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ù)大家可以換成哈?；蛘叨植檎业龋渲凶铌P(guān)鍵的是 predict() 函數(shù)，用于查找在將來最長時(shí)間內(nèi)不會使用到的頁面，其實(shí)也就是兩層 for 循環(huán)嵌套。

先進(jìn)先出算法

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

基本思路：選擇在內(nèi)存中駐留時(shí)間最長的頁面并淘汰。具體來說，系統(tǒng)維護(hù)著一個(gè)鏈表，記錄了所有位于內(nèi)存當(dāng)中的邏輯頁面。從鏈表的排列順序來看，鏈?zhǔn)醉撁娴鸟v留時(shí)間最長，鏈尾頁面的駐留時(shí)間最短。當(dāng)發(fā)生一個(gè)缺頁中斷時(shí)，把鏈?zhǔn)醉撁嫣蕴鼍?，并把新的頁面添加到鏈表的末尾?/p>

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

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

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

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

訪問頁面 0 時(shí)，命中;

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

頁面 0 命中;

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

訪問頁面 2 和 3 時(shí)，均命中;

訪問頁面 0 時(shí)，缺頁異常，淘汰頁面 1 ，插入頁面 0 ;

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

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

最近最少使用算法

關(guān)于最近最少頁面替換是算法的詳細(xì)信息可以參考：最近最少使用 LRU 算法

時(shí)鐘頁面置換算法

Clock 頁面置換算法，LRU 的近似，對 FIFO 的一種改進(jìn);

基本思路：

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

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

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

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

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

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

請求頁面 3 時(shí)，發(fā)生缺頁中斷，此時(shí)指針?biāo)赶虻捻撁?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)一個(gè)缺頁中斷發(fā)生時(shí)，選擇訪問次數(shù)最少的那個(gè)頁面，并淘汰之。

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

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

本文轉(zhuǎn)載自微信公眾號「景禹」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系景禹公眾號。