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

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

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

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

思想：在簡單頁式存儲管理的基礎上，增加請求調(diào)頁和頁面置換功能

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

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

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

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

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

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

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

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

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

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

在簡單段式存儲管理的基礎上，增加請求調(diào)段和段置換功能。段表：需要在進程段表中添加若干項：標志位：存在位(presentbit)

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