操作系統(tǒng)第九章

第9章虛擬內(nèi)存9.1虛擬內(nèi)存-研究背景第8章內(nèi)存管理（實(shí)存）要求：將整個(gè)進(jìn)程放在內(nèi)存中（雖然覆蓋和交換可以減輕這一限制，但需額外操作）。但下列情況下并不需要將整個(gè)程序放入內(nèi)存中:程序中通常的處理異常錯(cuò)誤條件的代碼數(shù)組、鏈表和表通常分配了比實(shí)際所需要更多的內(nèi)存程序的某些選項(xiàng)或特點(diǎn)可能很少使用允許執(zhí)行只有部分在內(nèi)存中的程序程序不再受現(xiàn)有的物理內(nèi)存空間限制。用戶(hù)只有對(duì)一個(gè)大的虛擬地址空間寫(xiě)程序，簡(jiǎn)化了編程操作提高了程序執(zhí)行的并發(fā)性、CPU利用率9.1虛擬內(nèi)存-局部性原理局部性原理(principleoflocality)：指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。還可以表現(xiàn)為：時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)都集中在一個(gè)較短時(shí)期內(nèi)（一條指令被執(zhí)行了，則在不久的將來(lái)它可能再被執(zhí)行）空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。（

若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該存儲(chǔ)單元相鄰的單元可能被使用)9.1虛擬內(nèi)存--局部性原理局部性原理的具體體現(xiàn)程序在執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過(guò)程調(diào)用指令。過(guò)程調(diào)用的嵌套深度一般不超過(guò)5，因此執(zhí)行的范圍不超過(guò)這組嵌套的過(guò)程。程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。程序中存在相當(dāng)多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。9.1虛擬內(nèi)存--概念虛擬內(nèi)存將內(nèi)存看成一個(gè)巨大的、統(tǒng)一的存儲(chǔ)數(shù)組；總?cè)萘坎怀^(guò)物理內(nèi)存和外存交換區(qū)容量之和虛擬內(nèi)存的實(shí)現(xiàn)途徑請(qǐng)求頁(yè)面調(diào)度（Demandpaging）請(qǐng)求分段調(diào)度（Demandsegmentation）9.1虛擬內(nèi)存—原理在程序裝入時(shí)，不必將其全部讀入到內(nèi)存，而只需將當(dāng)前需要執(zhí)行的部分頁(yè)或段讀入到內(nèi)存，就可讓程序開(kāi)始執(zhí)行。在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存（稱(chēng)為缺頁(yè)或缺段），則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序。另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)或段調(diào)出保存在外存上，從而騰出空間存放將要裝入的程序以及將要調(diào)入的頁(yè)或段。只需程序所需的一部分在內(nèi)存就可執(zhí)行。9.1虛擬內(nèi)存—技術(shù)特征大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶(hù)程序；大的用戶(hù)空間：提供給用戶(hù)可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(realmemory)，將用戶(hù)看到的邏輯內(nèi)存與物理內(nèi)存分開(kāi)；并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；易于開(kāi)發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)部分裝入：允許部分程序代碼裝入內(nèi)存就可以執(zhí)行；9.1虛擬內(nèi)存—好處不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的；大空間：通過(guò)物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間總?cè)萘坎怀^(guò)物理內(nèi)存和外存交換區(qū)容量之和虛擬內(nèi)存大于物理內(nèi)存示意圖9.1虛擬內(nèi)存—實(shí)現(xiàn)方法(種類(lèi))

虛擬頁(yè)式-請(qǐng)求頁(yè)面調(diào)度虛擬段式-請(qǐng)求段式調(diào)度虛擬段頁(yè)式9.2請(qǐng)求頁(yè)面調(diào)度－基本思想

思想：在簡(jiǎn)單頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能

在程序裝入時(shí)，不必將其全部讀入到內(nèi)存，而只需將當(dāng)前需要執(zhí)行的部分頁(yè)讀入到內(nèi)存（一個(gè)或零個(gè)頁(yè)面，就可讓程序開(kāi)始執(zhí)行。之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存（稱(chēng)為缺頁(yè)），則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序。另一方面，當(dāng)內(nèi)存空間已滿(mǎn)，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面（將內(nèi)存中暫時(shí)不使用的頁(yè)或段調(diào)出保存在外存上），而騰出空間存放將要裝入的程序的頁(yè)。分頁(yè)的內(nèi)存：頁(yè)在內(nèi)存與磁盤(pán)間的傳遞9.2請(qǐng)求頁(yè)面調(diào)度－示例9.2請(qǐng)求頁(yè)面調(diào)度－對(duì)進(jìn)程頁(yè)表的修改頁(yè)表：每個(gè)進(jìn)程有一個(gè)，與簡(jiǎn)單分頁(yè)相比，增加了如下位：P：表示該頁(yè)是否在內(nèi)存中。如果在主存，則頁(yè)表中還包括該頁(yè)的幀號(hào)。（或稱(chēng)“有效－無(wú)效位”：“有效”時(shí)：頁(yè)既合法、也在內(nèi)存中；“無(wú)效”時(shí)：頁(yè)不在進(jìn)程的邏輯地址空間、或者在磁盤(pán)上）M：修改位，表示相應(yīng)頁(yè)的內(nèi)容從上次裝入主存到現(xiàn)在是否已經(jīng)改變。如果沒(méi)有改變，則該頁(yè)換出時(shí)，不需要重新寫(xiě)回到磁盤(pán)上如果改變了，則該頁(yè)換出時(shí)，需要重新寫(xiě)回到磁盤(pán)上還有其它一些用于保護(hù)和共享的位。虛地址頁(yè)表項(xiàng)9.2請(qǐng)求頁(yè)面調(diào)度－對(duì)進(jìn)程頁(yè)表的修改有些頁(yè)不在內(nèi)存中時(shí)的頁(yè)表9.2請(qǐng)求頁(yè)面調(diào)度－地址轉(zhuǎn)換9.2請(qǐng)求頁(yè)面調(diào)度－缺頁(yè)中斷處理在地址映射過(guò)程中，在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷(pageFault)。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被修改過(guò)，則要將其寫(xiě)回外存9.2請(qǐng)求頁(yè)面調(diào)度－缺頁(yè)中斷處理分頁(yè)硬件，在通過(guò)頁(yè)表轉(zhuǎn)換地址時(shí)，如果發(fā)現(xiàn)非法位，則陷入到OS中，執(zhí)行下列過(guò)程：

檢查進(jìn)程的頁(yè)表，以確定該引用是合法還是非法的地址訪問(wèn)；如果應(yīng)用非法，則終止進(jìn)程；如果引用有效但是尚未調(diào)入頁(yè)面，那么現(xiàn)在應(yīng)調(diào)入；找到一個(gè)空閑幀；執(zhí)行一個(gè)磁盤(pán)操作，以便將所需頁(yè)調(diào)入剛分配的幀中當(dāng)磁盤(pán)讀操作結(jié)束后，修改進(jìn)程頁(yè)表，表示該頁(yè)已在內(nèi)存中恢復(fù)程序的執(zhí)行缺頁(yè)中斷處理缺頁(yè)中斷的特殊性缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和進(jìn)行處理，而不是在一條指令執(zhí)行完畢之后。所缺的頁(yè)面調(diào)入之后，重新執(zhí)行被中斷的指令。一條指令的執(zhí)行可能產(chǎn)生多次缺頁(yè)中斷，如：swapA,B,指令本身和兩個(gè)操作數(shù)A,B都跨越相鄰?fù)獯骓?yè)的分界處，則產(chǎn)生6次缺頁(yè)中斷。9.3頁(yè)面置換算法（Replacement）定義：在必須取進(jìn)一個(gè)頁(yè)時(shí)，應(yīng)該選擇替換主存中的哪個(gè)頁(yè)。當(dāng)主存中的所有頁(yè)都被占據(jù)，并且需要取進(jìn)一個(gè)新頁(yè)以滿(mǎn)足一次缺頁(yè)時(shí)，替換策略決定當(dāng)前在主存中的哪個(gè)頁(yè)將被置換。目標(biāo)：把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面調(diào)出。通常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)（移出最近最不可能訪問(wèn)的頁(yè)。）由于局部性原理，最近的訪問(wèn)歷史和最近將要訪問(wèn)的模式間是有很大的相關(guān)性。大多數(shù)策略都基于過(guò)去的行為力圖預(yù)測(cè)將來(lái)的行為。查找所需頁(yè)在磁盤(pán)上的位置查找一個(gè)空閑幀（frame）

-如果有空閑幀，就使用它；

-如果沒(méi)有空閑幀，就使用一個(gè)替換算法以選擇一個(gè)“犧牲”幀（victimframe）；

3.將“犧牲”幀的內(nèi)容寫(xiě)到磁盤(pán)上；改變頁(yè)表和空閑頁(yè)表.

4.將所需頁(yè)讀入（新）空閑幀，改變頁(yè)表和幀表.

5.重啟用戶(hù)進(jìn)程.9.3頁(yè)面置換－基本工作過(guò)程9.3頁(yè)面置換－基本工作過(guò)程9.4置換策略－基本算法最佳算法（OPT）先進(jìn)先出算法(FirstinFirstOut，F(xiàn)IFO)最近最久未使用算法(LRU,LeastRecentlyUsed)Clock算法近似LRU算法9.4替換策略－最佳算法OPT最佳算法（Optimal，OPT）選擇替換下次訪問(wèn)距當(dāng)前時(shí)間最長(zhǎng)的那些頁(yè)。特點(diǎn)缺頁(yè)錯(cuò)誤率最低，沒(méi)有Belady現(xiàn)象；要求OS必須知道引用串的未來(lái)知識(shí)，不可能實(shí)現(xiàn)。OPT僅能作為一種標(biāo)準(zhǔn)，用于測(cè)試其他算法的性能。Belady異常（BeladyAnomaly）：有些情況下，頁(yè)故障率（缺頁(yè)率）可能會(huì)隨著所分配的幀數(shù)的增加而增加。示例：最佳算法（Optimal，OPT）9.4替換策略－最佳算法OPT9.4替換策略－先進(jìn)先出算法FIFO先進(jìn)先出算法（FIFO）替換駐留在主存中時(shí)間最長(zhǎng)的頁(yè)。實(shí)現(xiàn)將分配給進(jìn)程的頁(yè)幀看作是一個(gè)FIFO隊(duì)列，按循環(huán)方式移動(dòng)頁(yè):置換隊(duì)列的首頁(yè)，當(dāng)需要調(diào)入新頁(yè)時(shí)，將它加入到隊(duì)列的尾部。存在問(wèn)題FIFO策略實(shí)現(xiàn)簡(jiǎn)單，但性能相對(duì)較差。Belady異常（BeladyAnomaly）：有些情況下，頁(yè)故障率（缺頁(yè)率）可能會(huì)隨著所分配的幀數(shù)的增加而增加。9.4替換策略－先進(jìn)先出算法FIFO示例：FIFO算法9.4替換策略－LRU最近最久未使用算法（LRU－LeastRecentlyUsed)）替換主存中上次使用距離當(dāng)前最遠(yuǎn)的頁(yè)（最長(zhǎng)時(shí)間沒(méi)有使用的頁(yè)）?？梢岳斫鉃橄蚝罂醋顑?yōu)置換算法。根據(jù)局部性原理，這也是最近最不可能訪問(wèn)到的頁(yè)。LRU性能接近于OPT，被認(rèn)為是比較好的算法問(wèn)題：是如何確定最后訪問(wèn)以來(lái)所經(jīng)歷時(shí)間的順序。LRU頁(yè)置換算法9.4替換策略－LRU實(shí)現(xiàn)方法2種：計(jì)數(shù)器：給每個(gè)頁(yè)添加一個(gè)最后一次訪問(wèn)的時(shí)間標(biāo)簽，為CPU增加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器,每進(jìn)行一次訪問(wèn)存儲(chǔ)器時(shí)，該時(shí)鐘都加1。時(shí)鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁(yè)表項(xiàng)的使用時(shí)間字段中。在淘汰時(shí)，選擇該時(shí)間值最小的頁(yè)面。開(kāi)銷(xiāo)大。堆棧：維護(hù)一個(gè)關(guān)于訪問(wèn)頁(yè)的棧，很昂貴。每當(dāng)引用一個(gè)頁(yè)，該頁(yè)就從堆棧中刪除并放在頂部。棧底是目前最少使用的頁(yè)（LRU頁(yè)）。堆棧需要是雙向鏈表。9.4替換策略－LRU實(shí)現(xiàn)9.4替換策略－

LRU實(shí)現(xiàn)堆棧法9.4替換策略－輪轉(zhuǎn)算法Clock簡(jiǎn)單時(shí)鐘算法：將所有內(nèi)存中的頁(yè)面保存在一個(gè)類(lèi)似時(shí)鐘表盤(pán)的循環(huán)鏈表中，由一個(gè)指針指向最老的頁(yè)面，置換時(shí)從當(dāng)前指針位置開(kāi)始按地址先后檢查各頁(yè)，尋找引用位=0的頁(yè)面作為被置換頁(yè)。當(dāng)發(fā)生缺頁(yè)時(shí)，首先檢查指針指向的頁(yè)面：如果它的引用位為0則淘汰該頁(yè)，且將新頁(yè)插入到此位置，然后將指針向前移動(dòng)一個(gè)位置。如果引用位為1，則清0，且將指針前移一個(gè)位置；重復(fù)這個(gè)過(guò)程，直到找到引用位為0的頁(yè)面為止。（指針經(jīng)過(guò)的userbit=1的頁(yè)都修改userbit=0，最后指針停留在被置換頁(yè)的下一個(gè)頁(yè)。）優(yōu)點(diǎn)是：在進(jìn)行頁(yè)面比較時(shí)不發(fā)生頁(yè)面移動(dòng)，而只是移動(dòng)指針，可以提高檢測(cè)效率。當(dāng)頁(yè)727要進(jìn)入時(shí)，在從緩沖區(qū)中替換一頁(yè)之前，下一幀指針指向含有頁(yè)45的幀。替換前：替換后：9.4替換策略－基于計(jì)數(shù)的方法LFU和MFU最不經(jīng)常使用頁(yè)面置換算法LFU要求：置換計(jì)數(shù)最小的頁(yè)問(wèn)題：一個(gè)頁(yè)在進(jìn)程開(kāi)始時(shí)使用得很多，但以后就不再使用解決方法：定期將次數(shù)寄存器右移一位，形成指數(shù)衰減的平均使用次數(shù)最常使用頁(yè)面置換算法MFU具有最小次數(shù)的頁(yè)可能剛剛調(diào)進(jìn)來(lái)，且還沒(méi)有使用9.5系統(tǒng)顛簸（抖動(dòng)）Thrashing系統(tǒng)顛簸：剛剛被淘汰出去的頁(yè)很快又被訪問(wèn)，需要重新調(diào)入；但是，調(diào)入不久又再次被淘汰出去。如此反復(fù)，使得整個(gè)系統(tǒng)的頁(yè)面替換非常頻繁，使大部分機(jī)器時(shí)間都用在來(lái)回進(jìn)行的頁(yè)面調(diào)度上，這種局面稱(chēng)為系統(tǒng)顛簸（thrashing)結(jié)果：缺頁(yè)率急劇增加，內(nèi)存有效存取時(shí)間加長(zhǎng)，系統(tǒng)吞吐量驟減；系統(tǒng)已基本不能完成什么任務(wù)。產(chǎn)生原因：如果CPU利用率太低，調(diào)度程序就會(huì)增加多道程序度，將新進(jìn)程引入系統(tǒng)中。新進(jìn)程啟動(dòng)運(yùn)行，導(dǎo)致缺頁(yè)，從其他進(jìn)程中取幀，進(jìn)行換入換出。防止系統(tǒng)顛簸(抖動(dòng))方法：采用局部置換策略：如果一個(gè)進(jìn)程出現(xiàn)抖動(dòng)，它不能從另外的進(jìn)程取幀,不會(huì)引發(fā)其它進(jìn)程出現(xiàn)抖動(dòng)，使抖動(dòng)局限于一個(gè)小范圍內(nèi)。利用工作集策略防止抖動(dòng)掛起某些進(jìn)程：優(yōu)先級(jí)低、缺頁(yè)進(jìn)程、最大的進(jìn)程等

9.5系統(tǒng)顛簸（抖動(dòng)）－工作集（駐留集）工作集:就是一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問(wèn)頁(yè)面的集合。如用WS(ti)表示在ti－到ti之間所訪問(wèn)的不同頁(yè)面，則它就是進(jìn)程在時(shí)間ti的工作集。如果頁(yè)面正在使用，它就落在工作集中；如果不再使用，它將不出現(xiàn)在相應(yīng)的工作集中，所以，工作集是程序局部性的近似表示。

…261577775162341234443434441323444344…對(duì)于給定的頁(yè)面走向，如果＝10次存儲(chǔ)訪問(wèn)，在t1時(shí)刻的工作集是WS(t1)=(1,2,5,6,7)，在t2時(shí)刻，工作集是WS(t2)=(3,4)t1t29.5系統(tǒng)顛簸（抖動(dòng)）－工作集頁(yè)面置換法工作集精確度與的選擇有關(guān)。如果太小，那么它不能包含整個(gè)局部；如果為無(wú)窮大，那么工作集合是進(jìn)程執(zhí)行所碰到的所有頁(yè)的集合。利用工作集模型可以進(jìn)行頁(yè)面置換。工作集頁(yè)面置換法基本思想：找出一個(gè)不在工作集中的頁(yè)面，把它淘汰。利用工作集模型可以防止抖動(dòng)。OS監(jiān)視每個(gè)進(jìn)程的工作集，并且給它分配工作集所需的內(nèi)存塊。若有足夠多的額外內(nèi)存塊，就可裝入另一個(gè)進(jìn)程。如果所有工作集之和增加以至于超過(guò)了可用內(nèi)存塊的總數(shù)，則OS就會(huì)選擇掛起一個(gè)進(jìn)程，把它的頁(yè)寫(xiě)出去，將它的內(nèi)存塊分配給其它其它進(jìn)程。掛起的進(jìn)程可以在以后重啟。9.6請(qǐng)求分段技術(shù)

在簡(jiǎn)單段式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)段和段置換功能。段表：需要在進(jìn)程段表中添加若干項(xiàng)：標(biāo)志位：存在位(presentbit)

修改位(modifiedbit/dirtybit)訪問(wèn)統(tǒng)計(jì)：如使用位(usebit)存取權(quán)限：如讀R，寫(xiě)W，執(zhí)行X外存地址動(dòng)態(tài)地址變換和缺段中斷：指令和操作數(shù)必定不會(huì)跨越在段邊界上段號(hào)始址長(zhǎng)度存取方式內(nèi)外訪問(wèn)位原理：