前言

之前簡(jiǎn)單介紹過(guò)虛擬內(nèi)存是如何與物理內(nèi)存進(jìn)行地址映射的: 虛擬內(nèi)存分頁(yè)機(jī)制的地址映射, 但是僅僅地址映射是不夠的, 在地址映射說(shuō)過(guò)會(huì)有缺頁(yè)的情況, 此時(shí)就需要操作操作系統(tǒng)將缺少的頁(yè)加載到內(nèi)存中. 但是, 如果內(nèi)存滿了怎么辦呢? 畢竟虛擬內(nèi)存一般都要大于物理內(nèi)存的, 不可能將所有虛擬內(nèi)存中的內(nèi)容都加載到物理內(nèi)存中.

當(dāng)需要加載虛擬內(nèi)存中的內(nèi)容時(shí), 發(fā)現(xiàn)物理內(nèi)存已經(jīng)沒(méi)有空閑空間了. 腫么辦嘞? 淘汰一個(gè)舊頁(yè)面, 就可以騰出空間來(lái)加載新的頁(yè)面了. 既然涉及到淘汰, 那么淘汰哪一個(gè)頁(yè)面就是一個(gè)問(wèn)題了. 這篇文章就簡(jiǎn)單介紹一下幾個(gè)頁(yè)面置換的算法, 或者說(shuō)是頁(yè)面淘汰的算法.

頁(yè)面置換算法

什么樣的頁(yè)面置換算法是好的呢? 簡(jiǎn)單說(shuō), 就是盡可能的減少缺頁(yè)中斷的次數(shù). 在發(fā)生缺頁(yè)中斷的時(shí)候, 是要損失一部分性能的.

最優(yōu)頁(yè)面置換

如果有4個(gè)頁(yè)面已經(jīng)加載了, 現(xiàn)在要在它們之間選擇一個(gè)進(jìn)行淘汰, 選擇哪一個(gè)呢? 要想讓中斷發(fā)生的次數(shù)最少, 那么馬上就要用到的頁(yè)面是不能被淘汰的, 這么算下來(lái), 就應(yīng)該淘汰那個(gè)在訪問(wèn)序列中最后的頁(yè)面. 舉個(gè)例子:

為什么要在最開(kāi)始先將內(nèi)存填滿, 而不是用到的時(shí)候再進(jìn)行加載呢? 個(gè)人認(rèn)為, 有如下好處

根據(jù)順序執(zhí)行的原則, 連續(xù)的頁(yè)很可能馬上就要用到. 故可以減少未來(lái)缺頁(yè)的次數(shù)

即使加載的頁(yè)用不到, 缺頁(yè)中斷的時(shí)候被淘汰了也沒(méi)有帶來(lái)性能的損失.

程序啟動(dòng)的時(shí)候, 雖然不能占用全部物理內(nèi)存, 但還是會(huì)分配部分起始內(nèi)存的. 內(nèi)存空著也是空著, 不如先將程序加載進(jìn)去

因?yàn)槔拥木窒扌? 例子僅用作對(duì)置換規(guī)則的理解, 不用作各個(gè)算法優(yōu)劣的比較

但是, 別高興的太早, 這種情況太過(guò)于理想化了, 操作系統(tǒng)是無(wú)法預(yù)知未來(lái)的, 因此這個(gè)算法并不能在實(shí)際中應(yīng)用. 講話了, 不能用你提他干啥啊, 雖然不能實(shí)際實(shí)現(xiàn), 但可以作為一個(gè)評(píng)價(jià)其他算法的優(yōu)劣的標(biāo)準(zhǔn)呀, 越接近最優(yōu)頁(yè)面置換的就越好.

接下來(lái), 幾個(gè)實(shí)際應(yīng)用的置換算法將相繼登場(chǎng)(因?yàn)闊o(wú)法預(yù)測(cè)未來(lái), 他們都是基于歷史訪問(wèn)來(lái)判斷的):

先進(jìn)先出

既FIFO, 看名字就能看出來(lái), 那個(gè)頁(yè)面先進(jìn)來(lái), 哪個(gè)頁(yè)面就先淘汰. 還使用相同的序列進(jìn)行舉例:

但是, 注意看我標(biāo)記tip1的地方, 頁(yè)面b在上一次訪問(wèn)剛剛被淘汰, 馬上就又要用到了, 這這這…

實(shí)現(xiàn)

先進(jìn)先出的方式, 實(shí)現(xiàn)起來(lái)很簡(jiǎn)單, 只需要維護(hù)一個(gè)頁(yè)面換入的隊(duì)列即可. 淘汰時(shí)從隊(duì)首取出淘汰, 放入是添加到隊(duì)尾即可.

Belady 現(xiàn)象

提到了先進(jìn)先出, 那么就要說(shuō)一下這個(gè)算法反嘗試的Belady現(xiàn)象. 不用去找belady這個(gè)單詞的意思了, 他是首次發(fā)現(xiàn)這種顯得的前輩名字.

在常識(shí)中, 隨著物理頁(yè)容量增大, 那么缺頁(yè)中斷的頻率也會(huì)下降, 因?yàn)榭梢詫⒏嗟捻?yè)面放入內(nèi)存中了嘛. 但是, FIFO可能會(huì)出現(xiàn)這樣一種情況: 隨著物理頁(yè)容量增大, 缺頁(yè)中斷的頻率也隨之增大.

舉個(gè)例子: 有這樣一個(gè)訪問(wèn)序列: [a, b, c, d, a, b, e, a, b, c, d, e]. 此時(shí)物理也中數(shù)據(jù)為空, 依次將頁(yè)面讀入內(nèi)存. 過(guò)程就不說(shuō)了, 直接說(shuō)結(jié)果:

• 當(dāng)物理頁(yè)數(shù)量為3時(shí), 產(chǎn)生9次缺頁(yè)中斷
• 當(dāng)物理頁(yè)數(shù)量為4時(shí), 產(chǎn)生10次缺頁(yè)中斷

而這種Belady現(xiàn)象, 只有FIFO有, 其他算法都沒(méi)有, 我特意造了寫(xiě)訪問(wèn)序列, 想找到其他算法也存在這種現(xiàn)象的情況, 很可惜, 沒(méi)有找到. 不過(guò)已經(jīng)就這種現(xiàn)象寫(xiě)了論文描述, 有時(shí)間嘗試這看看.

最近最久未使用(LRU)

這就是大名鼎鼎的LRU了. 需要淘汰的時(shí)候, 剛剛被訪問(wèn)過(guò)的頁(yè)面不能被淘汰, 那就淘汰那個(gè)已經(jīng)很久沒(méi)有被訪問(wèn)過(guò)的頁(yè)面. 再次舉例:

有沒(méi)有發(fā)現(xiàn), 其實(shí)LRU是在仿最優(yōu)算法, 思路就是, 雖然我無(wú)法預(yù)測(cè)未來(lái), 但是過(guò)去我是知道的, 又根據(jù)程序的局部性原理, 如果一個(gè)頁(yè)剛剛被訪問(wèn)過(guò), 那么他很大概率馬上會(huì)再次訪問(wèn). 而已經(jīng)很久沒(méi)有被訪問(wèn)的頁(yè)面, 未來(lái)可能也不會(huì)訪問(wèn).

雖然過(guò)去不能完全預(yù)測(cè)未來(lái), 但好在程序的局部性原理又救了我們, 可以說(shuō)是最優(yōu)算法的一個(gè)近似解了. 但是別高興的太早, 思路再好也要拿出可行的方案才行.

實(shí)現(xiàn)

要找到哪一個(gè)頁(yè)面已經(jīng)很久沒(méi)有訪問(wèn)過(guò)了, 可以維護(hù)一個(gè)訪問(wèn)序列的鏈表, 首部是剛剛被訪問(wèn)的頁(yè)面, 尾部就是很久都沒(méi)有被訪問(wèn)的頁(yè)面. 這樣淘汰頁(yè)面的時(shí)候直接取尾部的頁(yè)面進(jìn)行淘汰.

要維護(hù)這樣的一個(gè)鏈表, 就需要在每次訪問(wèn)內(nèi)存, 從鏈表中找到這個(gè)頁(yè)面, 將其移動(dòng)到首部

為了維護(hù)這樣一個(gè)鏈表, 給每次內(nèi)存訪問(wèn)都增加了額外的負(fù)擔(dān), 操作系統(tǒng)占用的時(shí)間越久, 留給應(yīng)用程序的時(shí)間響應(yīng)的就越少. 可以說(shuō)得不償失, 開(kāi)銷(xiāo)太大了.

所以, 雖然LRU看上去很美好, 但是沒(méi)有一個(gè)高效的算法來(lái)實(shí)現(xiàn)它

時(shí)鐘頁(yè)面置換(二次機(jī)會(huì))

在之前介紹頁(yè)面的地址映射時(shí)說(shuō)過(guò), 頁(yè)表中的每一頁(yè)都存在著一些標(biāo)志位, 而其中的一個(gè)標(biāo)志位, 標(biāo)識(shí)當(dāng)前頁(yè)是否被訪問(wèn)過(guò), 當(dāng)頁(yè)面被訪問(wèn)時(shí), 會(huì)由硬件負(fù)責(zé)將此標(biāo)記為置為1, 注意是由硬件來(lái)完成的, 所以效率是很高的.

我們能不能利用這個(gè)標(biāo)志位來(lái)實(shí)現(xiàn)頁(yè)面置換呢? 參考LRU算法, 淘汰那個(gè)已經(jīng)很久沒(méi)有訪問(wèn)過(guò)的頁(yè)面. 如果說(shuō), 先將所有訪問(wèn)位置為0, 等到下一次需要淘汰頁(yè)面的時(shí)候, 找到一個(gè)訪問(wèn)位仍是0的頁(yè)面, 說(shuō)明在這期間這個(gè)頁(yè)面從來(lái)沒(méi)有被訪問(wèn)過(guò)不就可以了么

但是, 現(xiàn)實(shí)中的內(nèi)存動(dòng)輒幾個(gè) G, 如果每次都將所有的頁(yè)面標(biāo)識(shí)位修改一遍, 效率也是很慢的. 為了提高效率, 可以對(duì)這個(gè)算法再次進(jìn)行近似. 將所有的頁(yè)面連接為一個(gè)環(huán), 使用一個(gè)指針在環(huán)上遍歷, 每次需要淘汰頁(yè)面的時(shí)候, 指針就開(kāi)始遍歷, 找到第一個(gè)訪問(wèn)位為0的頁(yè)面淘汰, 同時(shí)在遍歷的期間, 順便把經(jīng)過(guò)的頁(yè)面訪問(wèn)位置為0. 這樣每次只掃描部分頁(yè)面, 最差情況掃描所有(將當(dāng)前置為0, 掃描一圈回來(lái)必定拿到0), 故此算法的步驟如下:

• 若指針當(dāng)前指向的頁(yè)面, 訪問(wèn)位為0, 直接淘汰并指向下一頁(yè). 否則進(jìn)入下一步
• 若當(dāng)前頁(yè)訪問(wèn)位為1, 將其改為0并指向下一頁(yè), 回到上一步.

對(duì)于被訪問(wèn)過(guò)的頁(yè)面, 會(huì)在第二次掃描的時(shí)候進(jìn)行淘汰, 算是給了兩次機(jī)會(huì)吧.

還用剛才的序列進(jìn)行舉例:

時(shí)鐘算法可以說(shuō)是對(duì)LRU的一個(gè)可實(shí)現(xiàn)的近似解了. 據(jù)說(shuō)在實(shí)際應(yīng)用中, 效率是比較接近LRU的.

增強(qiáng)版時(shí)鐘算法

在選擇頁(yè)面淘汰的時(shí)候, 如果兩個(gè)頁(yè)面都不會(huì)被訪問(wèn)了, 淘汰一個(gè)和淘汰另一個(gè)有區(qū)別么? 有的, 別忘了, 頁(yè)面置換的時(shí)候, 不光換入, 還有換出的操作, 也就還是會(huì)將淘汰頁(yè)的數(shù)據(jù)寫(xiě)回磁盤(pán), 當(dāng)然如果頁(yè)面沒(méi)有被修改就不需要寫(xiě)回的操作了, 數(shù)據(jù)都一樣嘛. 怎么知道頁(yè)面有沒(méi)有被修改呢? 巧了, 也有一個(gè)標(biāo)記頁(yè)面修改的標(biāo)記位.

剛剛的時(shí)鐘算法用到了標(biāo)志位中的訪問(wèn)位, 那么如何將修改位也加入到判斷標(biāo)準(zhǔn)中, 優(yōu)先淘汰沒(méi)有被修改的頁(yè)面, 就能夠提高頁(yè)面置換的效率了. 兩個(gè)標(biāo)志位的話, 就有如下四種情況, 分情況討論:

• (訪問(wèn)位1, 修改位0): 最近訪問(wèn)過(guò), 將訪問(wèn)位置為0
• (訪問(wèn)位1, 修改位1): 最近訪問(wèn)過(guò), 將訪問(wèn)位置為0
• (訪問(wèn)位0, 修改位0): 最近沒(méi)有訪問(wèn)且沒(méi)有修改, 可以直接置換
• (訪問(wèn)位0, 修改位1): 最近沒(méi)有訪問(wèn)但修改過(guò), 將修改位置為0, 等待下一輪訪問(wèn)

但是, 但是, 你有沒(méi)有想過(guò), 如果將標(biāo)志位中的修改位置為0了, 那么操作系統(tǒng)進(jìn)行頁(yè)面置換的時(shí)候, 依據(jù)什么來(lái)判斷當(dāng)前頁(yè)是否需要執(zhí)行回寫(xiě)磁盤(pán)的操作呢? 所以, 修改位是不能動(dòng)的. 如果不動(dòng)修改位, 又如何來(lái)實(shí)現(xiàn)呢? 那就要增加額外變量來(lái)記錄了:

• 第一圈掃描的時(shí)候, 淘汰(訪問(wèn)位0, 修改位0)的頁(yè)面
  • 同時(shí)在掃描的過(guò)程中將訪問(wèn)位改為0
• 如果第一圈沒(méi)找到, 那么第二圈淘汰(訪問(wèn)位0, 修改位1)的頁(yè)面

也就是說(shuō), 和時(shí)鐘算法對(duì)數(shù)據(jù)的處理規(guī)則相同, 唯一不同的是額外增加臨時(shí)變量記錄當(dāng)前是第幾圈, 第一圈淘汰(訪問(wèn)位0, 修改位0)的頁(yè)面, 第二圈才會(huì)淘汰(訪問(wèn)位0, 修改位1)的頁(yè)面. 也就是將修改過(guò)的頁(yè)面進(jìn)行降權(quán)操作.(當(dāng)然, 也可以有其他實(shí)現(xiàn)方式, 不過(guò)大體意思不變) 再次舉例:

如此操作, 使得被修改的頁(yè)面更不容易被換出去, 進(jìn)而提升頁(yè)面置換效率. 實(shí)現(xiàn)起來(lái)和時(shí)鐘算法相似. 是時(shí)鐘算法的增強(qiáng)版.

最不常用(LFU)

既LFU, 在淘汰的時(shí)候, 淘汰使用次數(shù)最少的頁(yè)面. 也是一種依據(jù)過(guò)去預(yù)測(cè)未來(lái)的思路, 過(guò)去使用較多的頁(yè), 很可能在未來(lái)也會(huì)多次訪問(wèn). LRU的考察緯度是時(shí)間, 而LFU的考察緯度是次數(shù). 再次上圖:

有這樣一種情況, 程序在初始的時(shí)候頻繁訪問(wèn)頁(yè)面 A, 等到程序平穩(wěn)運(yùn)行了, 就不會(huì)再訪問(wèn)頁(yè)面 A 了. 但是, 因?yàn)橛?jì)數(shù)的結(jié)果, 頁(yè)面 A 的訪問(wèn)次數(shù)及高, 導(dǎo)致一直沒(méi)有被淘汰, 長(zhǎng)期駐留在內(nèi)存中. 如何避免這樣的問(wèn)題呢? 其實(shí)也很簡(jiǎn)單, 出現(xiàn)問(wèn)題是因?yàn)樵黾恿藭r(shí)間緯度, 只需要每個(gè)一段時(shí)間將頁(yè)面的計(jì)數(shù)左移一位(除以2), 這種頁(yè)面的訪問(wèn)次數(shù)就會(huì)隨著時(shí)間推移降下來(lái)了.

實(shí)現(xiàn)

既然淘汰的依據(jù)是頁(yè)面的訪問(wèn)次數(shù), 那么我們就要知道哪個(gè)頁(yè)面訪問(wèn)次數(shù)多, 哪個(gè)頁(yè)面訪問(wèn)次數(shù)少. 最直觀的思路是, 記錄每一頁(yè)的訪問(wèn)次數(shù), 淘汰時(shí)找到值最小的就行了. 但是, 有一個(gè)與LRU相同的問(wèn)題, 你如何來(lái)實(shí)現(xiàn)這個(gè)算法? 在每一次訪問(wèn)頁(yè)面的時(shí)候執(zhí)行計(jì)數(shù)器加一的操作么? 代價(jià)太大.

全局頁(yè)面置換

前面介紹的幾個(gè)頁(yè)面置換算法, 都假設(shè)物理內(nèi)存容量固定且操作系統(tǒng)中只運(yùn)行一個(gè)進(jìn)程. 但這和實(shí)中是有區(qū)別的, 操作系統(tǒng)中運(yùn)行著很多進(jìn)程, 每個(gè)進(jìn)程被分配到的物理內(nèi)存容量都是不同的. 亦或者一個(gè)進(jìn)程剛開(kāi)始運(yùn)行的時(shí)候會(huì)在多個(gè)頁(yè)面之間切換訪問(wèn), 而隨著運(yùn)行平穩(wěn)之后訪問(wèn)的頁(yè)面集中在其中的幾個(gè).

這里考慮的是, 如何來(lái)確定給不同進(jìn)程分配的物理內(nèi)存大小以使得總體的缺頁(yè)中斷率較低. 甚至在進(jìn)程的不同階段分配不同大小的物理內(nèi)存.

全局頁(yè)面置換算法又有好多, 這里簡(jiǎn)單提幾個(gè), 就不展開(kāi)說(shuō)了

工作集頁(yè)面置換

工作集就是進(jìn)程在最近 t個(gè)時(shí)刻所訪問(wèn)過(guò)的頁(yè)面. 其運(yùn)行規(guī)則如下:

• 頁(yè)面淘汰時(shí), 有限淘汰不再工作集中的
• 若都在工作集中, 可通過(guò)上述的頁(yè)面置換處理
• 若頁(yè)面已經(jīng)不在工作集中, 會(huì)進(jìn)行釋放
  • 這里與前面的算法產(chǎn)生差異了, 即使沒(méi)有發(fā)生缺頁(yè)中斷, 也會(huì)進(jìn)行頁(yè)面的釋放
  • 從而可以將空閑內(nèi)存交給其他進(jìn)程使用

缺頁(yè)率頁(yè)面置換

基于工作集頁(yè)面置換的思想, 當(dāng)缺頁(yè)率變大時(shí)增加工作集大小, 以使得更多的頁(yè)面放到內(nèi)存中. 當(dāng)缺頁(yè)率變小時(shí)減小工作集大小, 以使得頁(yè)面得到釋放, 提高內(nèi)存整體利用率.

不過(guò)需要計(jì)算缺頁(yè)率的原因, 會(huì)導(dǎo)致額外開(kāi)銷(xiāo)的增加.

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的虚拟内存分页机制的页面置换的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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