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

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

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

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

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

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

如何實現虛擬內存？

（1）交換與調頁

（2）頁表的改造

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

（2）內存不足時以進程為單位在內外存之間交換

（3）調頁，也稱惰性交換，以頁為單位在內外存

之間交換

（4）請求調頁，也稱按需調頁，即對不在內存中

的“頁”，當進程執(zhí)行時要用時才調入，否則

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

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

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

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

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

修改頁表(6):

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

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

（3）LRU頁面置換

準確實現：計數器法、頁碼棧法

（4）近似LRU頁面置換

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

…這樣的實現代價較大

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

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

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

兩針間隔=10s（1）寫時復制

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

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

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

每個進程的缺頁率增大

缺頁率增大到一定程度，進程總等待調頁完成

CPU利用率降低

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

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

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