操作系統(tǒng) ch9-虛擬內(nèi)存學(xué)習(xí)專業(yè)課件

E-mail：fgx@

軟件學(xué)院教研室

2015.05

操作系統(tǒng)9.1背景（1）內(nèi)存不夠用怎么辦？（2）內(nèi)存管理視圖（3）用戶眼中的內(nèi)存（4）虛擬內(nèi)存的優(yōu)點(diǎn)9.2虛擬內(nèi)存實(shí)現(xiàn)--按需調(diào)頁(yè)（請(qǐng)求調(diào)頁(yè)）（1）交換與調(diào)頁(yè)（2）頁(yè)表的改造（3）請(qǐng)求調(diào)頁(yè)過程9.3頁(yè)面置換（1）FIFO頁(yè)面置換（2）OPT（最優(yōu)）頁(yè)面置換（3）LRU頁(yè)面置換（準(zhǔn)確實(shí)現(xiàn)：計(jì)數(shù)器法、頁(yè)碼棧法）（4）近似LRU頁(yè)面置換（附加引用位法、時(shí)鐘法）9.4其他相關(guān)問題（1）寫時(shí)復(fù)制（2）頁(yè)置換策略：全局置換和局部置換（3）系統(tǒng)顛簸現(xiàn)象和Belady異常現(xiàn)象主要內(nèi)容第9章虛擬內(nèi)存內(nèi)存不夠用怎么辦？?jī)?nèi)存管理視圖用戶眼中的內(nèi)存虛擬內(nèi)存的優(yōu)點(diǎn)9.1背景內(nèi)存不夠怎么辦？頁(yè)0頁(yè)1頁(yè)2頁(yè)m虛擬內(nèi)存物理內(nèi)存內(nèi)存映射輔存（磁盤）代碼數(shù)據(jù)堆棧0最大用戶虛擬地址空間內(nèi)存管理視圖cs:ip邏輯地址0x00345008線性地址物理內(nèi)存04G操作系統(tǒng)段用戶代碼段用戶數(shù)據(jù)段用戶棧段線性地址空間物理地址0x7008對(duì)用戶是透明的用戶眼里的內(nèi)存!cs:ip邏輯地址04G操作系統(tǒng)段用戶代碼段用戶數(shù)據(jù)段用戶棧段線性地址空間1個(gè)4GB(很大)的地址空間用戶可隨意使用該地址空間，就象單獨(dú)擁有4G內(nèi)存該地址空間就被稱為“虛擬內(nèi)存”這個(gè)地址空間怎么映射到物理內(nèi)存，用戶全然不知必須映射，否則不能用!虛擬內(nèi)存的優(yōu)點(diǎn)物理內(nèi)存04G地址空間優(yōu)點(diǎn)1:地址空間>物理內(nèi)存用戶可以編寫比內(nèi)存大的程序4G空間可以使用，簡(jiǎn)化編程優(yōu)點(diǎn)2:部分程序或程序的部分放入物理內(nèi)存內(nèi)存中可以放更多進(jìn)程，并發(fā)度好，效率高將需要的部分放入內(nèi)存，有些用不到的部分從來不放入內(nèi)存，內(nèi)存利用率高如一些處理異常的代碼!程序開始執(zhí)行、響應(yīng)時(shí)間等更快虛擬內(nèi)存思想既有利于系統(tǒng)，又有利于用戶

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

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

（2）頁(yè)表的改造

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

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

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

之間交換

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

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

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

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

這又違背了分頁(yè)和請(qǐng)求調(diào)頁(yè)的原則，又需要折衷!請(qǐng)求調(diào)頁(yè)的具體實(shí)現(xiàn)細(xì)節(jié)(1)load[addr]，而addr沒有映射到物理內(nèi)存物理內(nèi)存磁盤頁(yè)表load[addr]i頁(yè)錯(cuò)誤處理程序(1)(2)(3)(4)(5)(6)根據(jù)addr查頁(yè)表(MMU)，頁(yè)表項(xiàng)的P位為0，引起缺頁(yè)中斷(pagefault)(2)

設(shè)置“缺頁(yè)中斷”(3)

“缺頁(yè)中斷處理程序”需要讀磁盤(4)

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

修改頁(yè)表(6)

重新開始指令如何重新開始指令?在指令執(zhí)行過程中出現(xiàn)頁(yè)錯(cuò)誤addr1,r2,r3mov+(sp),(r2)頁(yè)錯(cuò)誤分配頁(yè)面從磁盤讀入設(shè)置映射表OS指令重執(zhí)行顯然這一切應(yīng)該對(duì)用戶透明!需要一點(diǎn)硬件支持Fault:CR2

=0xffdd0頁(yè)錯(cuò)誤處理程序jmp0xffdd00xffdcc:addr1,r2,r30xffdd0:mov+(sp),(r2)異常處理寄存器保存缺頁(yè)時(shí)刻的線性地址如何選一個(gè)空閑頁(yè)框?沒有空閑頁(yè)框怎么辦?分配的頁(yè)框數(shù)是有限的頁(yè)面淘汰(置換)需要選擇一頁(yè)淘汰有多種淘汰選擇FIFO，最容易想到，怎么評(píng)價(jià)?有沒有最優(yōu)的淘汰方法，OPT(MIN)（OPT-Optimal）最優(yōu)淘汰方法能不能實(shí)現(xiàn)，能否借鑒思想，LRU再來學(xué)習(xí)幾種經(jīng)典方法，它可以用在許多需要淘汰(置換)的場(chǎng)合…但如果某頁(yè)剛淘汰出去馬上又要用…（1）FIFO頁(yè)面置換

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

（3）LRU頁(yè)面置換

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

（4）近似LRU頁(yè)面置換

附加引用位法、時(shí)鐘法9.3頁(yè)面置換FIFO頁(yè)面置換FIFO算法：先入先出，即淘汰最早調(diào)入的頁(yè)面實(shí)例：分配了3個(gè)頁(yè)框(frame)，頁(yè)面引用序列為ABCABDADBCBCBADCBABCBDADBACBA評(píng)價(jià)準(zhǔn)則:缺頁(yè)次數(shù)；本實(shí)例，F(xiàn)IFO導(dǎo)致7次缺頁(yè)D換A不太合適!選A、B、C中未來最遠(yuǎn)將使用的，是理想辦法！321

請(qǐng)求頁(yè)物理幀OPT(MIN)頁(yè)面置換OPT(MIN)算法：選未來最遠(yuǎn)將使用的頁(yè)淘汰。這是一種最優(yōu)的方案，可以證明缺頁(yè)數(shù)最小!繼續(xù)上面的實(shí)例:(3frame)ABCABDADBCBCDCBABCBDADBACBA本實(shí)例，MIN導(dǎo)致5次缺頁(yè)可惜，MIN需要知道將來發(fā)生的事…怎么辦?321

請(qǐng)求頁(yè)物理幀LRU頁(yè)面置換(OPT的可實(shí)現(xiàn)的近似算法)用過去的歷史預(yù)測(cè)將來。LRU算法：選最近最長(zhǎng)時(shí)間沒有使用的頁(yè)淘汰(也稱最近最少使用)。繼續(xù)上面的實(shí)例:(3frame)ABCABDADBCBCDCBABCBDADBACBA本實(shí)例，LRU也導(dǎo)致5次缺頁(yè)LRU是公認(rèn)的很好的頁(yè)置換算法，怎么實(shí)現(xiàn)?Least-Recently-Used321

請(qǐng)求頁(yè)物理幀本例和OPT完全一樣!LRU的準(zhǔn)確實(shí)現(xiàn)方法1：計(jì)數(shù)器法每頁(yè)維護(hù)一個(gè)時(shí)間戳(timestamp)，即計(jì)數(shù)器繼續(xù)上面的實(shí)例:(3frame)ABCABDADBCBBCBDADBACBAtimestampA1BC0D001200123042304530選具有最小時(shí)間戳的頁(yè)!453675367538793879108選A淘汰!711108每次地址訪問都需要修改時(shí)間戳，需維護(hù)一個(gè)全局時(shí)鐘(該時(shí)鐘溢出怎么辦?)，需要找到最小值

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

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

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

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

（2）頁(yè)置換策略：全局置換和局部置換

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

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

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

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

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

引用序列：A，B，C，D，A，B，E，A，B，C，D，EFIFO頁(yè)置換A3frameABABCDBCDACDABEABECBECD9faults4frameAABABCABCDEBCDEACDEABDEABCDABCDEBC10faultsBelady異常現(xiàn)象：對(duì)有的頁(yè)面置換算法，頁(yè)錯(cuò)誤率可能會(huì)隨著分配幀數(shù)增加而增加！什么樣的頁(yè)置換沒有Belady異常？看個(gè)模型!

引用序列：A，B，C，D，A，B，E，A，B，C，D，E