功能：置換算法是指當(dāng)出現(xiàn)缺頁(yè)異常時(shí)，需要調(diào)入新頁(yè)面而內(nèi)存已滿時(shí)，置換算法選擇被置換的物理頁(yè)面。

設(shè)計(jì)目標(biāo)：

• 盡可能減少頁(yè)面的調(diào)入調(diào)出次數(shù)；
• 把未來(lái)不再訪問或短期內(nèi)不訪問的頁(yè)面調(diào)出。

頁(yè)面鎖定：

了解具體的置換算法之前，先了解一個(gè)概念，頁(yè)面鎖定。頁(yè)面鎖定是用來(lái)描述某些必須常駐內(nèi)存的邏輯頁(yè)面，比如操作系統(tǒng)的關(guān)鍵部分，再比如一些要求響應(yīng)速度的代碼和數(shù)據(jù)。頁(yè)面鎖定是通過頁(yè)表中的鎖定標(biāo)志位實(shí)現(xiàn)的。

分類：

局部置換算法：置換頁(yè)面的選擇范圍僅限于當(dāng)前進(jìn)程占用的物理頁(yè)面內(nèi)。具體又有一系列算法：最優(yōu)算法、先進(jìn)先出算法、最近最久未使用算法，最近最久未使用算法又衍生出兩種近似算法：時(shí)鐘算法、最不常用算法，

全局置換算法：置換頁(yè)面的選擇范圍是所有可換出的物理頁(yè)面。具體有工作集算法、缺頁(yè)率算法。

最優(yōu)界面置換算法：?

• 基本思路：選擇內(nèi)存中等待時(shí)間最長(zhǎng)（未來(lái)最長(zhǎng)時(shí)間不訪問）的頁(yè)作為置換頁(yè)面。?
• 算法實(shí)現(xiàn)：缺頁(yè)時(shí)，計(jì)算內(nèi)存中每個(gè)邏輯頁(yè)面的下一次訪問時(shí)間；選擇未來(lái)最長(zhǎng)時(shí)間不訪問的頁(yè)面。
• 算法特征：

只能是理想情況，OS無(wú)法實(shí)現(xiàn)（不知道未來(lái)情況）。?

可以作為最佳的標(biāo)準(zhǔn)，在第二遍運(yùn)行時(shí)利用第一次的訪問軌跡使用最優(yōu)算法。其他算法應(yīng)盡量逼近。

先進(jìn)先出算法（ first-in first-out FIFO）

• 思路：選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)面并淘汰之。OS維護(hù)著一個(gè)隊(duì)列鏈表，淘汰首位，添加末位。
• 實(shí)現(xiàn)：維護(hù)一個(gè)記錄所有位于內(nèi)存中的邏輯頁(yè)面；鏈表元素按駐留內(nèi)存時(shí)間排序，鏈?zhǔn)鬃铋L(zhǎng)，鏈尾最短；出現(xiàn)缺頁(yè)時(shí)，選擇鏈?zhǔn)醉?yè)面進(jìn)行置環(huán)，新頁(yè)面加到鏈尾。
• 特征：性能較差，調(diào)出的頁(yè)面可能是常用頁(yè)面（駐留時(shí)間長(zhǎng)，本身就說明可能常用），有belady現(xiàn)象（給的物理頁(yè)幀越多反而缺頁(yè)越頻繁）。因此該算法很少單獨(dú)使用。

最近最久未使用算法（least recently used LRU）

• 思路：選擇最長(zhǎng)時(shí)間沒有被引用的頁(yè)面進(jìn)行置換。是對(duì)最優(yōu)置換算法的近似，以過去推未來(lái)。根據(jù)程序的局部性原理，如果最近一段時(shí)間內(nèi)某些頁(yè)面被頻繁訪問，那么在將來(lái)還可能被頻繁訪問。反之，未被訪問的將來(lái)也不會(huì)被訪問。 程序應(yīng)具有較好的局部性。
• 實(shí)現(xiàn)：缺頁(yè)時(shí)，計(jì)算內(nèi)存中每個(gè)邏輯頁(yè)面上一次訪問時(shí)間；選擇上一次使用到當(dāng)前時(shí)間最長(zhǎng)的頁(yè)面
• 特征：最優(yōu)置換算法的一種近似，但仍然很復(fù)雜，很難實(shí)現(xiàn)。下面是LRU算法的兩種可能的實(shí)現(xiàn)算法：

頁(yè)面鏈表：系統(tǒng)維護(hù)一個(gè)按最近一次訪問時(shí)間排序的頁(yè)面鏈表，鏈表首節(jié)點(diǎn)是最近使用的頁(yè)面，尾節(jié)點(diǎn)是最久未使用的頁(yè)面，訪問內(nèi)存時(shí)找到相應(yīng)頁(yè)面，并把它移到鏈表之首，缺頁(yè)時(shí)，置換鏈表尾節(jié)點(diǎn)的頁(yè)面。

活動(dòng)頁(yè)面堆棧：訪問頁(yè)面時(shí)將此頁(yè)號(hào)壓入棧頂，并將棧內(nèi)相同的頁(yè)號(hào)抽出，缺頁(yè)時(shí)置換棧底的頁(yè)面。（棧是先進(jìn)后出，只有棧頂開口，怎么push棧底？）

可以看到這兩種方式存在一個(gè)問題就是平時(shí)不缺頁(yè)時(shí)開銷較大，每次訪問頁(yè)面都需要遍歷鏈表或棧，找到相同的元素進(jìn)行處理。

時(shí)鐘置換算法（Clock）：

時(shí)鐘置換算法是最近最久未使用算法的優(yōu)化。先進(jìn)先出是完全不考慮最近訪問情況，最近最久未使用算法是將所有頁(yè)面在整個(gè)運(yùn)行過程中的訪問情況都進(jìn)行考慮。而時(shí)鐘置換算法是這兩者的折中，即僅對(duì)頁(yè)面的訪問情況進(jìn)行大致統(tǒng)計(jì)。具體實(shí)現(xiàn)

• 思路：僅對(duì)頁(yè)面的訪問情況進(jìn)行大致統(tǒng)計(jì)
• 數(shù)據(jù)結(jié)構(gòu)：在頁(yè)表項(xiàng)中增加訪問位，描述頁(yè)面在過去一段時(shí)間內(nèi)的訪問情況；各頁(yè)面組織成環(huán)形鏈表；指針指向最先調(diào)入的頁(yè)面；
• 算法實(shí)現(xiàn)：頁(yè)面裝入內(nèi)存時(shí)，訪問位初始化為0；訪問頁(yè)面（讀/寫）時(shí)，訪問位置1；缺頁(yè)時(shí)，從指針當(dāng)前位置順序檢查環(huán)形鏈表【訪問位為0，則置環(huán)該頁(yè)；訪問位為1，則訪問位置0，并指針移動(dòng)到下一個(gè)頁(yè)面，直到找到可置換得頁(yè)面】
• 特征：是FIFO和LRU的折中

?

時(shí)鐘置換算法實(shí)際還有一些改進(jìn)。比如減少修改頁(yè)的缺頁(yè)處理開銷。因?yàn)楸恍薷牡捻?yè)如果要被置換，需要先寫到外存，再將需要的頁(yè)寫入內(nèi)存，開銷至少乘2。因此為了減小修改過的頁(yè)被置換，可以遇到被修改過的頁(yè)指針就跳過。而在系統(tǒng)空閑時(shí)定期地將內(nèi)存寫入外存。實(shí)現(xiàn)通過在頁(yè)面中增加修改位，并在訪問時(shí)進(jìn)行相應(yīng)修改，缺頁(yè)掃描時(shí)跳過有修改的頁(yè)面。

改進(jìn)的Clock算法

• 思路：減少修改頁(yè)得缺頁(yè)處理開銷
• 算法：在頁(yè)面增加修改位，并在訪問時(shí)進(jìn)行相應(yīng)修改；缺頁(yè)時(shí)，修改頁(yè)面標(biāo)志位，以跳過有修改得頁(yè)面

最不常用置換算法（Least Frequently Used, LFU）：

• 思路：選擇置換訪問次數(shù)最少的那個(gè)頁(yè)面?
• 實(shí)現(xiàn)：對(duì)每個(gè)頁(yè)面設(shè)置訪問計(jì)數(shù)器，當(dāng)一個(gè)頁(yè)面被訪問時(shí)加1。置換數(shù)值最小的那個(gè)。?
• 特征：存在的問題就是統(tǒng)計(jì)開銷大，并且新拿進(jìn)來(lái)的頁(yè)面可能因?yàn)橛?jì)數(shù)較少馬上又被置換出去，對(duì)于后面這個(gè)問題的一個(gè)解決方法是已經(jīng)計(jì)的數(shù)定期地衰減
• 最不常用置換算法頁(yè)式最近最久未使用算法的優(yōu)化。可以看到LFU與LRU的區(qū)別。LRU關(guān)注多久未被訪問，時(shí)間越短越好，LFU關(guān)注訪問次數(shù)，次數(shù)越多越好。

LFU與時(shí)鐘算法都是對(duì)LRU算法的一種簡(jiǎn)化近似，開銷減小，同時(shí)精度下降。LFU是比較難實(shí)現(xiàn)的，因此在內(nèi)存管理中基本不會(huì)采用，但是在讀硬盤文件的時(shí)候?qū)r(shí)間要求不高的場(chǎng)景中還是可以使用的。

Belady現(xiàn)象

當(dāng)一個(gè)進(jìn)程頻繁出現(xiàn)缺頁(yè)異常時(shí)，應(yīng)該分配給進(jìn)程更多的物理頁(yè)面，分配完后按照常理，缺頁(yè)異常出現(xiàn)的頻率應(yīng)該降低。但是如果算法不好，很可能不會(huì)降低，我們把這種現(xiàn)象稱為Belady現(xiàn)象。

比如FIFO算法，因?yàn)橹脫Q出去的頁(yè)面不一定是進(jìn)程近期不會(huì)訪問的頁(yè)面，如下圖：

但是LRU算法是沒有Belady現(xiàn)象的。時(shí)鐘算法和改進(jìn)的時(shí)鐘算法也都是沒有Belady現(xiàn)象的。分配更多的頁(yè)面以為這更大的緩存，緩存越大命中率肯定升高。

綜合比較局部頁(yè)替換算法

LRU和FIFO的比較：LRU和FIFO本質(zhì)都是先進(jìn)先出，但LRU是頁(yè)面的最近訪問時(shí)間而不是進(jìn)入內(nèi)存的時(shí)間，有動(dòng)態(tài)調(diào)整，符合棧算法的特性，空間越大缺頁(yè)越少。如果程序局部性，則LRU會(huì)很好。如果內(nèi)存中所有頁(yè)面都沒有被訪問過會(huì)退化為FIFO。

Clock 和enhanced clock也是類似于FIFO的算法，但用了硬件的BIT來(lái)模擬了訪問時(shí)間和順序，近似了LRU，綜合起來(lái)較好，但也會(huì)退化為FIFO。

都對(duì)程序的訪問次序有局部性的要求，不然都會(huì)退化。

LRU、FIFO和Clock的比較：開銷上，LRU開銷大，FIFO開銷小但BELADY，折中的是Clock算法，開銷較小。對(duì)內(nèi)存中還未被訪問的頁(yè)面，Clock效果等同LRU。Clock對(duì)曾經(jīng)被訪問過的則不能記住其準(zhǔn)確位置，而LRU算法可以。

全局置換算法：

局部置換算法沒有考慮進(jìn)程訪問的差異，有時(shí)候給一個(gè)進(jìn)程多分配一個(gè)物理頁(yè)面可以大幅度降低它的缺頁(yè)率。全局置換算法就是要為進(jìn)程分配可變數(shù)目的物理頁(yè)面。它需要解決以下幾個(gè)問題：

• 進(jìn)程在不同階段的內(nèi)存需求是變化的
• 分配各進(jìn)程的內(nèi)存也需要在不同階段有所變化。
• 全局置換算法需要確定分配給進(jìn)程的物理頁(yè)面數(shù)

首先我們需要知道CPU利用率與并發(fā)進(jìn)程數(shù)之間的關(guān)系。隨著并發(fā)進(jìn)程數(shù)從0增加，CPU的利用率也不斷增大；當(dāng)進(jìn)程數(shù)越來(lái)越多，內(nèi)存訪問的局部性特征越來(lái)越被破壞，內(nèi)存變的越來(lái)越緊張，利用率增長(zhǎng)速度開始放緩，當(dāng)增加到某個(gè)臨界點(diǎn)，CPU利用率開始下降。也就是CPU利用率與并發(fā)進(jìn)程數(shù)存在相互促進(jìn)和制約的關(guān)系。

工作集

一個(gè)進(jìn)程當(dāng)前使用的邏輯頁(yè)面集合，可以用一個(gè)二元函數(shù)W(t,Δ)，t是當(dāng)前執(zhí)行時(shí)刻，Δ是工作集窗口（working-set window），一個(gè)定長(zhǎng)的頁(yè)面訪問的時(shí)間窗口。t+Δ構(gòu)成了一個(gè)時(shí)間段，W(t,Δ)就是在當(dāng)前時(shí)刻t之前的Δ時(shí)間內(nèi)所有訪問頁(yè)面組成的集合，在隨t不斷更新。| W(t,Δ)|是工作集的大小即頁(yè)面數(shù)目。

工作集的變化：進(jìn)程開始后，隨著訪問新頁(yè)面逐步建立較穩(wěn)定的工作集，當(dāng)內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時(shí)| W(t,Δ)|波動(dòng)很小，在過渡階段，則會(huì)快速擴(kuò)張和收縮過渡到下一個(gè)穩(wěn)定值。有波峰，有波谷。

常駐集

定義：在當(dāng)前時(shí)刻，進(jìn)程實(shí)際駐留在內(nèi)存當(dāng)中的頁(yè)面集合。

工作集與常駐集的關(guān)系：工作集是固有性質(zhì)，常駐集取決于系統(tǒng)分配給進(jìn)程的物理頁(yè)面數(shù)目和所采用的置換算法。

缺頁(yè)率與常駐集的關(guān)系：當(dāng)常駐集包含了工作集，也就是工作集都在內(nèi)存中，缺頁(yè)較少；工作集發(fā)生劇烈變動(dòng)時(shí)，缺頁(yè)較多；當(dāng)常駐集大小達(dá)到某個(gè)數(shù)目后，再分配物理頁(yè)幀也不會(huì)有明顯下降的缺頁(yè)率——可以把多出來(lái)的物理頁(yè)幀分給其他程序了

工作集置換算法：

• 思路：換出不在工作集中的頁(yè)面
• 窗口大小：當(dāng)前時(shí)刻前τ個(gè)內(nèi)存訪問的頁(yè)引用是工作集，τ被稱為窗口大小
• 實(shí)現(xiàn)方法：訪存鏈表：維護(hù)窗口內(nèi)的訪存頁(yè)面鏈表；在訪存時(shí)，換出不在工作集的頁(yè)面；缺頁(yè)時(shí)，換入頁(yè)面，更新訪存鏈表。

工作集置換算法的思路是換出不在工作集中的頁(yè)面。局部置換算法是在缺頁(yè)異常發(fā)生時(shí)才決定置換哪個(gè)頁(yè)面，但是工作集置換算法不一定是在缺頁(yè)時(shí)才做這件事，而是在訪存時(shí)就進(jìn)行處理。工作集置換算法中有一個(gè)窗口大小?τ，當(dāng)前時(shí)刻前 τ?個(gè)內(nèi)存訪問的頁(yè)引用是工作集。

可以看到，缺頁(yè)處理很簡(jiǎn)單，但是每次訪存都要進(jìn)行判斷，開銷還是很大的。這與LRU算法是類似的。

缺頁(yè)率置換算法（Page-Fault-Frequency, PFF）

缺頁(yè)率=缺頁(yè)次數(shù)/內(nèi)存訪問次數(shù) =1/缺頁(yè)的平均時(shí)間間隔

影響因素有：頁(yè)面置換算法，分配給進(jìn)程的物理頁(yè)面數(shù)目(越多越小)，頁(yè)面本身的大小（頁(yè)面大則會(huì)小），編程方法（局部性好就會(huì)小）

缺頁(yè)率置換算法是依據(jù)缺頁(yè)率來(lái)決定哪些頁(yè)面放到內(nèi)存哪些被置換出去。其中我們能夠控制的是頁(yè)面置換算法。

正常情況下，隨著分配給進(jìn)程的物理頁(yè)面數(shù)增多，缺頁(yè)率會(huì)下降，缺頁(yè)率置換算法通過調(diào)節(jié)常駐集的大小，使每個(gè)進(jìn)程的缺頁(yè)率保持在一個(gè)合理的范圍內(nèi)。如果缺頁(yè)率過高，則增加物理頁(yè)面數(shù)，如果缺頁(yè)率過低，則降低物理頁(yè)面數(shù)。

• 思路：動(dòng)態(tài)調(diào)整常駐集的大小。性能較好，但增加了系統(tǒng)開銷?
• 具體機(jī)制：

訪存時(shí)設(shè)置引用位標(biāo)志

缺頁(yè)時(shí)，計(jì)算從上次缺頁(yè)時(shí)間?tlast?到現(xiàn)在的時(shí)間?tcurrent 間隔，如果時(shí)間間隔?tcurrent -?tlast 大于常量 T，則置換所有在 [tlast ,? tcurrent]??時(shí)間內(nèi)沒有被引用的頁(yè)，以減少常駐集的大小；如果時(shí)間間隔?tcurrent -?tlast?小于等于常量 T，則增加缺失頁(yè)到常駐集。

對(duì)比缺頁(yè)率置換算法與工作集置換算法，缺頁(yè)率置換算法是在缺頁(yè)異常時(shí)進(jìn)行處理，工作集置換算法是在訪存時(shí)進(jìn)行處理，缺頁(yè)的出現(xiàn)頻率是遠(yuǎn)小于訪存的，開銷降下來(lái)了。

抖動(dòng)

• 抖動(dòng)：如果分配給一個(gè)進(jìn)程的物理頁(yè)面太少，常駐集遠(yuǎn)小于工作集，則缺頁(yè)率會(huì)很大，頻繁在內(nèi)外存之間替換頁(yè)面，使進(jìn)程的運(yùn)行慢，這種狀態(tài)成為”抖動(dòng)”。
• 產(chǎn)生抖動(dòng)的原因：隨著駐留內(nèi)存的進(jìn)程數(shù)目增加，分配給每個(gè)進(jìn)程的物理頁(yè)面數(shù)不斷減少，缺頁(yè)率上升。因此OS要選擇一個(gè)適當(dāng)?shù)倪M(jìn)程數(shù)目和進(jìn)程需要的幀數(shù)，在并發(fā)水平和缺頁(yè)率中達(dá)到平衡。

負(fù)載控制

我們希望平均缺頁(yè)間隔時(shí)間（MTBF）大于等于缺頁(yè)異常處理時(shí)間（PFST）。因此如下圖右側(cè)虛線以左是CPU滿負(fù)荷工作也滿足平均缺頁(yè)間隔時(shí)間大于等于缺頁(yè)異常處理時(shí)間的區(qū)域。

總結(jié)

以上是生活随笔為你收集整理的清华大学《操作系统》（八）：置换算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。