《操作系統(tǒng)》第九章：虛擬內(nèi)存

9.1背景（1）內(nèi)存不夠用怎么辦？（2）內(nèi)存管理視圖（3）用戶眼中的內(nèi)存（4）虛擬內(nèi)存的優(yōu)點9.2虛擬內(nèi)存實現(xiàn)--按需調(diào)頁（請求調(diào)頁）（1）交換與調(diào)頁（2）頁表的改造（3）請求調(diào)頁過程9.3頁面置換（1）FIFO頁面置換（2）OPT（最優(yōu)）頁面置換（3）LRU頁面置換（準(zhǔn)確實現(xiàn)：計數(shù)器法、頁碼棧法）（4）近似LRU頁面置換（附加引用位法、時鐘法）9.4其他相關(guān)問題（1）寫時復(fù)制（2）頁置換策略：全局置換和局部置換（3）系統(tǒng)顛簸現(xiàn)象和Belady異常現(xiàn)象主要內(nèi)容第9章虛擬內(nèi)存內(nèi)存不夠用怎么辦？內(nèi)存管理視圖用戶眼中的內(nèi)存虛擬內(nèi)存的優(yōu)點9.1背景內(nèi)存不夠怎么辦？頁0頁1頁2頁m虛擬內(nèi)存物理內(nèi)存內(nèi)存映射輔存（磁盤）代碼數(shù)據(jù)堆棧0最大用戶虛擬地址空間內(nèi)存管理視圖cs:ip邏輯地址0x00345008線性地址物理內(nèi)存04G操作系統(tǒng)段用戶代碼段用戶數(shù)據(jù)段用戶棧段線性地址空間物理地址0x7008對用戶是透明的用戶眼里的內(nèi)存!cs:ip邏輯地址04G操作系統(tǒng)段用戶代碼段用戶數(shù)據(jù)段用戶棧段線性地址空間1個4GB(很大)的地址空間用戶可隨意使用該地址空間，就象單獨擁有4G內(nèi)存該地址空間就被稱為“虛擬內(nèi)存”這個地址空間怎么映射到物理內(nèi)存，用戶全然不知必須映射，否則不能用!虛擬內(nèi)存的優(yōu)點物理內(nèi)存04G地址空間優(yōu)點1:地址空間>物理內(nèi)存用戶可以編寫比內(nèi)存大的程序

4G空間可以使用，簡化編程

優(yōu)點2:部分程序或程序的部分放入物理內(nèi)存內(nèi)存中可以放更多進(jìn)程，并發(fā)度好，效率高將需要的部分放入內(nèi)存，有些用不到的部分從來不放入內(nèi)存，內(nèi)存利用率高

如一些處理異常的代碼!程序開始執(zhí)行、響應(yīng)時間等更快

虛擬內(nèi)存思想既有利于系統(tǒng)，又有利于用戶

如何實現(xiàn)虛擬內(nèi)存？

（1）交換與調(diào)頁

（2）頁表的改造

（3）請求調(diào)頁過程9.2按需調(diào)頁（請求調(diào)頁）（1）整個程序裝入內(nèi)存執(zhí)行，內(nèi)存不夠不能運行

（2）內(nèi)存不足時以進(jìn)程為單位在內(nèi)外存之間交換

（3）調(diào)頁，也稱惰性交換，以頁為單位在內(nèi)外存

之間交換

（4）請求調(diào)頁，也稱按需調(diào)頁，即對不在內(nèi)存中

的“頁”，當(dāng)進(jìn)程執(zhí)行時要用時才調(diào)入，否則

有可能到程序結(jié)束時也不會調(diào)入從交換到調(diào)頁早期現(xiàn)在從段頁式內(nèi)存管理開始頁框號保護(hù)5R1R/W3R/W7R基址長度保護(hù)段號0x40000x0800R00x48000x1400R/W10xF0000x1000R/W20x00000x3000R3段號+偏移(cs:ip)邏輯地址頁號偏移偏移物理地址物理頁號線性地址部分邏輯地址對應(yīng)段表項，發(fā)現(xiàn)缺段后調(diào)入部分線性地址對應(yīng)頁表項，發(fā)現(xiàn)缺頁后調(diào)入分頁易于硬件實現(xiàn)、對用戶透明，適合請求調(diào)入磁盤頁表物理內(nèi)存虛擬內(nèi)存中的頁面映射關(guān)系部分線性地址(邏輯頁)對應(yīng)物理頁，那其它頁呢?如何記錄頁是否在內(nèi)存？改造頁表，頁表項增加“有效/無效位”vvvviii….幀號有效/無效位改造后的頁表邏輯內(nèi)存頁表物理內(nèi)存輔存（磁盤）幀號有效-無效位某些頁不在內(nèi)存中時的頁表磁盤頁表物理內(nèi)存請求調(diào)頁過程當(dāng)訪問沒有映射的線性地址時…load[addr]i頁錯誤處理程序(1)(2)(3)(4)(5)(6)但完成這個過程很費時間(有時候一條指令會引起幾次調(diào)頁)!顯然是一個很好理解的過程為什么請求調(diào)頁仍是可行的?分配給一個進(jìn)程的物理頁框數(shù)應(yīng)該足夠多!頁面應(yīng)該足夠大!這又違背了分頁和請求調(diào)頁的原則，又需要折衷!如何設(shè)計這些參數(shù)?再從計算機的基本特征開始!

內(nèi)存地址訪問頻率物理內(nèi)存程序的局部性：90/10原則!90%的程序訪問10%的地址!頁面4K，調(diào)入一頁后許多指令不出現(xiàn)頁錯誤這些參數(shù)從實踐中獲得!

請求調(diào)頁的具體實現(xiàn)細(xì)節(jié)(1):load[addr]，而addr沒有映射到物理內(nèi)存物理內(nèi)存磁盤頁表load[addr]i頁錯誤處理程序(1)(2)(3)(4)(5)(6)根據(jù)addr查頁表(MMU)，頁表項的P位為0，引起缺頁中斷(pagefault)(2):

設(shè)置“缺頁中斷”即可(3):“缺頁中斷處理程序”需要讀磁盤(4):

選一個空閑頁框?qū)W過磁盤處理后自然就明白了!(5):

修改頁表(6):

重新開始指令異常處理寄存器如何重新開始指令?在指令執(zhí)行過程中出現(xiàn)頁錯誤addr1,r2,r3mov+(sp),(r2)頁錯誤分配頁面從磁盤讀入設(shè)置映射OS指令重執(zhí)行顯然這一切應(yīng)該對用戶透明!需要一點硬件支持Fault:epc=0xffdd0頁錯誤處理程序jmp0xffdd00xffdcc:addr1,r2,r30xffdd0:ldr1,0(sp)如何選一個空閑頁框?沒有空閑頁框怎么辦?分配的頁框數(shù)是有限的頁面淘汰(置換)需要選擇一頁淘汰有多種淘汰選擇。如果某頁剛淘汰出去馬上又要用…FIFO，最容易想到，怎么評價?有沒有最優(yōu)的淘汰方法，OPT(MIN)（OPT-Optimal）最優(yōu)淘汰方法能不能實現(xiàn)，能否借鑒思想，LRU再來學(xué)習(xí)幾種經(jīng)典方法，它可以用在許多需要淘汰(置換)的場合…（1）FIFO頁面置換

（2）OPT（最優(yōu)）頁面置換

（3）LRU頁面置換

準(zhǔn)確實現(xiàn)：計數(shù)器法、頁碼棧法

（4）近似LRU頁面置換

附加引用位法、時鐘法9.3頁面置換FIFO頁面置換FIFO算法:先入先出，即淘汰最早調(diào)入的頁面一實例:分配了3個頁框(frame)，頁面引用序列為ABCABDADBCBCBADCBABCBDADBACBA321Ref:Page:評價準(zhǔn)則:缺頁次數(shù)；本實例，F(xiàn)IFO導(dǎo)致7次缺頁D換A不太合適!選A、B、C中未來最遠(yuǎn)將使用的，是理想辦法！OPT(MIN)頁面置換OPT(MIN)算法:選未來最遠(yuǎn)將使用的頁淘汰。是一種最優(yōu)的方案，可以證明缺頁數(shù)最小!繼續(xù)上面的實例:(3frame)ABCABDADBCBCDCBABCBDADBACBA321Ref:Page:本實例，MIN導(dǎo)致5次缺頁可惜，MIN需要知道將來發(fā)生的事…怎么辦?LRU頁面置換(OPT的可實現(xiàn)的近似算法)用過去的歷史預(yù)測將來。LRU算法:選最近最長時間沒有使用的頁淘汰(也稱最近最少使用)。繼續(xù)上面的實例:(3frame)ABCABDADBCBCDCBABCBDADBACBA321Ref:Page:本實例，LRU也導(dǎo)致5次缺頁LRU是公認(rèn)的很好的頁置換算法，怎么實現(xiàn)?本例和OPT完全一樣!Least-Recently-UsedLRU的準(zhǔn)確實現(xiàn)方法1:計數(shù)器法每頁維護(hù)一個時間戳(timestamp)，即計數(shù)器繼續(xù)上面的實例:(3frame)ABCABDADBCBBCBDADBACBAtimestampA1BC0D001200123042304530選具有最小時間戳的頁!453675367538793879108選A淘汰!711108每次地址訪問都需要修改時間戳，需維護(hù)一個全局時鐘(該時鐘溢出怎么辦?)，需要找到最小值

…這樣的實現(xiàn)代價較大

幾乎沒人用具體方法：設(shè)1個時鐘(計數(shù))寄存器，每次頁引用時，計數(shù)器加1，并將該值復(fù)制到相應(yīng)頁表項中。當(dāng)需要置換頁時，選則計數(shù)值最小的頁。LRU準(zhǔn)確實現(xiàn)方法2:頁碼棧法維護(hù)一個頁碼棧繼續(xù)上面的實例:(3frame)ABCABDADBCBBCBDADBACBA頁碼棧每次地址訪問都需要修改棧(修改10次左右棧指針)…實現(xiàn)代價仍然較大

LRU準(zhǔn)確實現(xiàn)用的少AABCABABCBCA選棧底頁淘汰!DABABDDBABADCDBBDC具體方法：建立一個容量為有效幀數(shù)的頁碼棧。每當(dāng)引用一個頁時，該頁號就從棧中上升到棧的頂部，棧底為LRU頁。當(dāng)需要置換頁時，直接置換棧底頁即可。LRU近似實現(xiàn)

將時間計數(shù)變?yōu)槭呛头衩總€頁加一個引用位(referencebit)每次訪問一頁時，硬件自動設(shè)置該位為1選擇淘汰頁：掃描該位，是1時清0，并繼續(xù)掃描；直到碰到是0時淘汰該頁，記錄該位置，下次繼續(xù)再給一次機會(SecondChanceReplacement)組織成循環(huán)隊列較合適！R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=0SCR實現(xiàn)方法稱為ClockAlgorithmCA*D*CA*D*CBD*Clock算法實例繼續(xù)上面的實例:(3frame)ABCABDADBCB（1）將可用幀按順序組成環(huán)形隊列，引用位初始置0，并置指針初始位置；（2）缺頁時從指針位置掃描引用位，將1變0，直到找到引用位為0的頁；（3）當(dāng)某頁被替換，則指針移到該頁的下1頁。B*AC*BAC*B*A*D*C*B*A*C*B*A*C*B*A*B*A*A*BCBDADBACBA本實例，Clock算法也導(dǎo)致7次缺頁Clock算法是公認(rèn)的很好的近似LRU的算法引用位！掃描指針！321Ref:Page:321Ref:Page:321Ref:Page:Clock算法分析的改造如果缺頁很少，會?R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1所有的R=1handscan一圈后淘汰當(dāng)前頁，將調(diào)入頁插入hand位置，hand前移一位退化為FIFO!原因:記錄了太長的歷史信息…怎么辦?定時清除R位…再來一個掃描指針!R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1用來清除R位，移動速度要快!用來選擇淘汰頁，移動速度慢!更像Clock吧!清除R位的hand如何定速度，若太快?又成了FIFO!指針1用來選擇淘汰頁，缺頁時用；指針2根據(jù)設(shè)定的時間間隔定時清楚R位Solaris實際做法設(shè)定值嗎?在slowscan和fastscan之間調(diào)整系統(tǒng)負(fù)載并不固定…slowsacnfastsacn空閑內(nèi)存比率lotsfreeminfree空閑內(nèi)存比率高于lotsfree時，掃描速度設(shè)為slowscan,并往大調(diào)穩(wěn)定在這個區(qū)間上!清除指針和掃描指針的距離:handspread參數(shù)R=1R=1R=0R=1R=1R=1R=0R=0R=1R=0R=0R=1一個夾角scanrate=100,handspread=1000

兩針間隔=10s（1）寫時復(fù)制

（2）頁置換策略：全局置換和局部置換

（3）系統(tǒng)顛簸現(xiàn)象和Belady異?，F(xiàn)象9.4其他相關(guān)問題寫時復(fù)制為了更快創(chuàng)建進(jìn)程，子進(jìn)程共享父進(jìn)程的地址空間，僅當(dāng)某進(jìn)程要寫某些頁時，才為其復(fù)制產(chǎn)生一個新頁兩種置換策略使用freelist回收DBBCADAB全局置換局部置換只能淘汰進(jìn)程自己的頁面可以淘汰別的進(jìn)程的頁面全局置換:實現(xiàn)簡單但全局置換不能實現(xiàn)公平、保護(hù):一個經(jīng)過巧妙優(yōu)化的程序里會出現(xiàn)大量goto，則…局部置換需要考慮的關(guān)鍵問題給進(jìn)程分配多少頁框(幀frame)分配的多，請求調(diào)頁的意義就沒了!一定要少?至少是多少?

可執(zhí)行任意一條指令，如mov[a],[b]是不是就選該下界值?最壞情況需要6幀!來看一個實例:操作系統(tǒng)監(jiān)視CPU使用率，發(fā)現(xiàn)CPU使用率太低時，向系統(tǒng)載入新進(jìn)程。會發(fā)生什么?多道程序程度CPU利用率急劇下降CPU利用率急劇下降的原因系統(tǒng)內(nèi)進(jìn)程增多

每個進(jìn)程的缺頁率增大

缺頁率增大到一定程度，進(jìn)程總等待調(diào)頁完成

CPU利用率降低

進(jìn)程進(jìn)一步增多，缺頁率更大…多道程序程度CPU利用率急劇下降此時:進(jìn)程調(diào)入一頁，需將一頁淘汰出去，剛淘汰出去的頁馬上要需要調(diào)入，就這樣……稱這一現(xiàn)象為顛簸(thrashing)顯然，防止的根本手段給進(jìn)程分配足夠多的幀問題時怎么確定進(jìn)程需要多少幀才能不顛簸?Belady異常來看一個例子!

引用序列1，2，3，4，1，2，5，1，2，3，4，5FIFO頁置換13frame121234234134125125325349faults4frame112123123452345134512451234123452310faultsBelady異常現(xiàn)象：對有的頁面置換算法，頁錯誤率可能會隨著分配幀數(shù)增加而增加。什么樣的頁置換沒有Belady異?？磦€模型!

引用序列1，2，3，4，1，2，5，1，2，3，4，5結(jié)論：棧式算法無Belady異常，LRU屬于棧式算法!12132143211