美團暑期實習一面：頁面置換算法

1. 在程序執(zhí)行過程中，當 CPU 所需要的信息不在內存中的時候，由操作系統(tǒng)負責將所需信息從外存（磁盤）調入內存，然后繼續(xù)執(zhí)行程序
2. 如果調入內存的時候內存空間不夠，由操作系統(tǒng)負責將內存中暫時用不到的信息換出到外存

整個請求調頁的過程大概是這樣的：

那么，到底哪些頁面該被從內存中換出來，哪些頁面又該被從磁盤中調入內存呢？

這就是『頁面置換算法』干的事兒。

考慮這樣一種情況：剛剛從內存中換出到磁盤的頁面馬上又要被重新?lián)Q入到內存中，剛剛從磁盤中換入到內存的頁面馬上就要被換出來。這種頻繁的頁面調度行為稱為抖動。這是頁面置換過程中一種最糟糕的情形。

所以，一個好的頁面置換算法應有較低的頁面更換頻率，也就是說，應將『以后不會再訪問或者以后較長時間內不會再訪問的頁面』先調出。

常見的置換算法有以下五種：

1. 最佳(Optimal, OPT)頁面置換算法
2. 先進先出(First-In First-Out, FIFO)頁面置換算法
3. 最近最久未使用(Least Recently Used, LRU)頁面置換算法
4. 時鐘(CLOCK)頁面置換算法
5. 最少使用(Least Frequently Used, LFU)頁面置換算法

最佳(Optimal, OPT)頁面置換算法

最佳置換算法所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時間內不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。

假定系統(tǒng)為某進程分配了三個物理塊，并假設先后訪問了以下這些頁面號：

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

1）進程運行時，先將 7, 0, 1 三個頁面依次裝入內存（下圖中的『缺頁』表示內存中沒有該頁面，需要從磁盤中調入）

2）進程要訪問頁面 2 時，頁面 2 不在內存中，需要從磁盤中裝入內存，但是此時內存不夠了，于是產生缺頁中斷。根據(jù)最佳置換算法，選擇第 18 次訪問才需調入的頁面 7 予以淘汰（最長時間內不再被訪問的頁面）

3）然后，訪問頁面 0 時，因為已在內存中所以不必產生缺頁中斷。訪問頁面 3 時又會根據(jù)最佳置換算法將頁面 1 淘汰

4）......

依此類推，釆用最佳置換算法時的情況如下圖所示，可以看到，發(fā)生缺頁中斷的次數(shù)為 9，頁面置換的次數(shù)為 6（圖中 【】 標識的即為發(fā)生了頁面置換）

這個算法的問題就是，誰能提前預知進程在內存下的若千頁面中哪個是未來最長時間內不再被訪問的？我自己都不知道我接下來會干什么你一個程序都能知道了？

所以這算法目前也就是說說而已，一個理想情況，當前無法實現(xiàn)。現(xiàn)階段呢咱們可以用最佳置換算法的結果來評價其他算法。

先進先出(First-In First-Out, FIFO)頁面置換算法

優(yōu)先淘汰最早進入內存的頁面，亦即在內存中駐留時間最久的頁面。

該算法實現(xiàn)簡單，只需把調入內存的頁面根據(jù)先后次序鏈接成隊列，設置一個指針總指向最早的頁面。但該算法與進程實際運行時的規(guī)律不適應，因為在進程中，有的頁面經常被訪問。

還是上面的例子：

• 進程訪問頁面 2 時，把最早進入內存的頁面 7 換出
• 然后訪問頁面 3 時，再把 2, 0, 1 中最先進入內存的頁 0 換出
• .......

利用 FIFO 置換算法時的置換圖如下，可以看出，利用 FIFO 算法時進行了 12 次頁面置換，比最佳置換算法正好多一倍。

FIFO 算法還會產生當所分配的物理塊數(shù)增大而缺頁次數(shù)不減反增的異常現(xiàn)象，這是由 ?Belady 于 1969 年發(fā)現(xiàn)，故稱為 Belady 異常，如下圖所示：

頁面訪問順序為 1、2、3、4、1、2、5、1、2、3、4、5。當分配的物理塊為 3 個時，缺頁次數(shù)為 9 次；而當分配的物理塊增加為 4 個時，缺頁次數(shù)反而增加到了 10 次

最近最久未使用(Least Recently Used, LRU)頁面置換算法

選擇最近最長時間未訪問過的頁面予以淘汰，它認為過去一段時間內未訪問過的頁面，在最近的將來可能也不會被訪問。

和 OPT 算法相比，LRU 算法根據(jù)各頁以前的情況，是 “向前看” 的，而 OOT 算法則根據(jù)各頁以后的使用情況，是 “向后看” 的。

對上面的實例釆用 LRU 算法進行頁面置換，如下圖所示：

• 進程第一次對頁面 2 訪問時，內存已滿，包含 7、0、1 三個頁面，將最近最久未被訪問的頁面 7 置換出去
• 然后訪問頁面 3 時，內存已滿，包含 2、0、1 三個頁面，將最近最久未使用的頁面 1 換出
• ......

OPT 算法向前看是無法實現(xiàn)了，那 LRU 這個向后看的算法具體該怎么實現(xiàn)呢？換句話說，這個過去一段時間內最久未被訪問過的頁面，操作系統(tǒng)是如何找出來的呢？

此處參考百度百科：https://baike.baidu.com/item/LRU

LRU 的具體實現(xiàn)需要有兩類硬件之一的支持：寄存器或棧，這兩種硬件也就對應著兩種不同的方法：

方法一（使用寄存器）：

為了記錄某進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為

當進程訪問某物理塊時，要將相應寄存器的 位置成 1，隨后，定時信號將每隔一定時間 (例如 100 ms) 將寄存器右移一位。

舉個例子，假設內存中有 8 個物理塊，能夠裝 8 個頁面，假設這 8 個內存頁面的序號分別定為 1～8，操作系統(tǒng)需要為每個內存頁面配置一個 8 位寄存器 ，初始化為 0000 0000

• 假設某個進程訪問了頁面 2，那么就把 即 寄存器的值設置為 1，得到 0000 0010
• 隨后一段時間內，如果頁面 2 沒被訪問，那么定時信號會將寄存器右移一位 ?0000 0001
• 如果隨后頁面 2 又被訪問了，那么寄存器的值就會由 0000 0001 變成 0000 0011

所以如果某個頁面最近一段時間一直不再被訪問，那么這個頁面對應的寄存器的值就會越來越小，具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。

看下面這張圖，第 3 個內存頁面的 R 值 0000 0100 最小，當發(fā)生缺頁時，首先將它置換出去。

方法二（使用棧）：

還可以利用一個特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進程所訪問的頁面的頁面號序列為：

4，7，0，7，1，0，1，2，1，2，6

隨著進程的訪問， 棧中頁面號的變化情況如下圖所示。在訪問頁面 6 時發(fā)生了缺頁，此時頁面 4 是最近最久未被訪問的頁，應將它置換出去

總結下，LRU 性能較好，但實現(xiàn)起來較為困難，需要寄存器和棧的硬件支持 ，屬于堆棧類的算法，開銷較大

時鐘(CLOCK)置換算法

對比下上面 3 種頁面置換算法：OPT、FIFO ?和 LRU

• OPT 算法性能（效果）最好，但無法實現(xiàn)
• FIFO 算法實現(xiàn)簡單，但性能差
• LRU 算法的性能接近于 OPT，但是實現(xiàn)起來比較困難，且開銷大

所以操作系統(tǒng)的設計者嘗試了很多算法，試圖用比較小的開銷接近 LRU 的性能，這類算法都是 CLOCK 算法的變體

簡單的 CLOCK 算法

回顧下請求分頁管理的頁表：

其中：

• 狀態(tài)位：該頁面是否已調入內存（0 表示不在內存中，訪問該頁面會引起缺頁中斷；1 表示已在內存中）
• 訪問位（也稱為參考位/引用位，referenced bit，簡寫 R）：該頁面是否被訪問過（0 表示被訪問過；1 表示未被訪問過），不論是讀還是寫，操作系統(tǒng)都會在該頁面被訪問時將其訪問位設為 1
• 修改位（modified bit，簡寫 M）：該頁面調入內存后是否被修改過（0 表示未被修改過；1 表示已經被修改過，被修改過的頁面必須被寫回磁盤）
• 外存地址：該頁面在外存中的存放地址（通常是物理塊號，供調入該頁時使用）

簡單的 CLOCK 算法就和這個『訪問位』息息相關，也有書中稱之為『使用位』（use bit）

所謂簡單的 CLOCK 算法到底有多簡單，其實就是盡可能地淘汰掉未被訪問過的頁面，如下。

將內存中的頁面都鏈接成一個『循環(huán)隊列』：

1）當某頁被訪問時，其訪問位置為 1

2）當需要從內存中換出一個頁面時，只需遍歷這個循環(huán)隊列，依次檢查頁的訪問位：

• 如果是 0，就選擇該頁換出
• 如果是 1，則將它置為 0，暫不換出，繼續(xù)檢查下一個頁面

由于該算法循環(huán)地遍歷檢查各頁面的情況，所以就形象地被稱為 CLOCK 算法

另外，

• 如果在遍歷過程開始時，緩沖區(qū)中所有頁面的訪問位均為 0，則選擇遇到的第一個頁面替換
• 如果所有頁面的訪問位均為 1，則指針會在循環(huán)隊列中完整地循環(huán)一周，把所有使用位都置為 0，并且停留在最初的位置上，替換該頁面

改進型的 CLOCK 算法

上述只使用了『訪問位』的簡單的 CLOCK 算法的性能比較接近 LRU，我們還可以進一步地通過『修改位』使得 CLOCK 算法更加高效。

這樣，每一個頁面都處于以下四種情況之一：

第 0 類：未被訪問，未被修改 (Referenced bit = 0，Modified bit = 0)（最佳替換頁面）

第 1 類：未被訪問，被修改 (Referenced bit = 0，Modified bit = 1)（第二考慮的替換頁面）

第 2 類：被訪問，未被修改 (Referenced bit = 1，Modified bit = 0)（該頁面可能再次被訪問）

第 3 類：被訪問，被修改 (Referenced bit = 1，Modified bit = 1)（該頁面很有可能再次被訪問）

其實

可能有小伙伴會困惑怎么會有第 1 類 “未被訪問，被修改 (Referenced bit = 0，Modified bit = 1)” 這種情況，其實是這樣的，一個第 3 類 “被訪問，被修改 (Referenced bit = 1，Modified bit = 1)” 的頁面在它的 Referenced bit 位被時鐘中斷清零后就成了第 1 類。時鐘中斷不會清除 Modified bit，因為一個被修改過的頁面是需要被寫回磁盤的，這就需要 Modified bit 這個信息。

改進型的 CLOCK 算法步驟如下：

1）從指針的當前位置開始，掃描循環(huán)隊列。在這次掃描過程中，對訪問位不做任何修改。選擇遇到的第一個是第 0 類 “未被訪問，未被修改 (Referenced bit = 0，Modified bit = 0)” 的頁面用于替換

2）如果第 1) 步失敗，則重新掃描，查找第一個是第 1 類 “未被訪問，被修改 (Referenced bit = 0，Modified bit = 1)” 的頁面用于替換。在這次掃描過程中，對每個跳過的頁面，和簡單的 CLOCK 算法一樣，把它的訪問位設置成 0

3）如果第 2) 步失敗，指針將回到它的最初位置，并且集合中所有頁面的訪問位都已經被設置為 0 了。重復第 1 步，并且如果有必要，重復第 2 步。這樣一定可以找到供替換的頁面。

流程圖如下：

總結起來也很簡單，簡單 CLOCK 算法不就是盡可能地淘汰掉未被訪問過的頁面嘛，那改進的 CLOCK 算法就是在此基礎上，對未被訪問過的頁面進一步細分，修改過和未被修改過，優(yōu)先替換『未被修改過的頁面』。因為修改過的頁在被替換之前必須寫回，因而這樣做會節(jié)省時間。

最少使用(Least Frequently Used, LFU)頁面置換算法

LFU 核心思想就是對每個頁面設置一個訪問計數(shù)器，每當一個頁面被訪問時，該頁面的訪問計數(shù)器就累加 1。在發(fā)生缺頁中斷時，淘汰計數(shù)器值最小的那個頁面。

看起來很簡單，但是操作系統(tǒng)為此需要為每個頁面設定一個『計數(shù)寄存器』，顯然成本是非常高的。

另外還有個問題，就是有些頁在開始時使用次數(shù)很多，但最近一段時間就沒有使用過了，這類頁面由于計數(shù)較大，會長時間留在內存中。而當前頻繁訪問的頁面由于沒有這些頁面總共訪問的次數(shù)高，在發(fā)生缺頁中斷時，就可能會被淘汰掉

因此可以參考 LRU 的做法，定時將引用計數(shù)寄存器右移一位，形成指數(shù)衰減的平均使用次數(shù)，也就說，隨著時間的增加，以前的高訪問次數(shù)的頁面的計數(shù)寄存器對應的值會慢慢減少，相當于加大了被淘汰的概率