第8章-虛擬內(nèi)存

第八章虛擬內(nèi)存2本章主要內(nèi)容背景請求頁面調(diào)度寫時復(fù)制進程創(chuàng)建頁面置換幀分配系統(tǒng)顛簸內(nèi)存映射文件內(nèi)核內(nèi)存的分配其他考慮38.1背景虛擬內(nèi)存將用戶看到的邏輯內(nèi)存與物理內(nèi)存分開；只要部分程序放在內(nèi)存中就能使程序執(zhí)行；邏輯地址空間可以比物理地址空間大。許多情況下，整個程序不是必需的：錯誤代碼；數(shù)組、鏈表和表分配的空間比實際所需要的大；程序的某些選項或功能很少使用。48.1背景（cont.）優(yōu)點程序能夠比實際內(nèi)存空間大程序員不必關(guān)心內(nèi)存空間限制允許地址空間被多個進程共享所需I/O更少，程序運行更快多個進程之間共享文件更加容易允許更多進程被創(chuàng)建虛擬內(nèi)存可以用以下方式來實現(xiàn)請求頁式調(diào)度（按需調(diào)頁）請求段式調(diào)度5虛擬內(nèi)存大于物理內(nèi)存的示意圖6虛擬地址空間進程如何在內(nèi)存中存放的邏輯視圖稀地址空間(holes)7使用虛擬地址的共享庫LibrarycanbesharedCommunicationFork()systemcall88.2按需調(diào)頁（demandpaging）只在頁面需要時，才載入內(nèi)存需要更少的輸入輸出更小的內(nèi)存更快的響應(yīng)更多的用戶懶惰交換（Lazyswapper）只有到需要時，才把它調(diào)入內(nèi)存；調(diào)頁程序（pager）處理單個頁的交換。9分頁的內(nèi)存到連續(xù)的磁盤空間之間的傳遞10有效/無效位頁表中的每一條目與一有效/無效位與之關(guān)聯(lián)。（v表示該頁在內(nèi)存中，i表示不在內(nèi)存）有效/無效位初始為i當(dāng)進程試圖訪問那些尚未調(diào)入到內(nèi)存的頁時，對標(biāo)記為無效的頁面的訪問會產(chǎn)生頁錯誤陷阱（faulttrap）vvvvii….Frame#valid-invalidbitpagetable11當(dāng)有些頁不在內(nèi)存中時的頁表12頁錯誤第一次引用頁將陷入操作系統(tǒng)檢查進程的頁表，如果引用非法，那么終止進程如果引用有效但是尚未調(diào)入頁面，那么現(xiàn)在應(yīng)調(diào)入。找到一個空閑幀（從空閑幀鏈表中取一個）調(diào)度一個磁盤操作，以便將所需要的頁調(diào)入剛分配的幀當(dāng)磁盤讀操作完成后，修改進程的內(nèi)部表和頁表，以表示該頁已在內(nèi)存中。重新開始因非法地址陷阱而中斷的指令。13處理頁錯誤的步驟14頁錯誤（cont.）重啟指令C=A+B獲取并編譯指令（ADD）提取A提取BA與B相加將和存儲到C中 (C不在內(nèi)存中)可以忽略的問題重復(fù)一條指令導(dǎo)致N個頁錯誤15頁錯誤（cont.）一條指令修改N個位置例.MVC(movecharacter),能夠移動256B塊可能跨越頁邊界；移動部分字符后出現(xiàn)頁錯誤；如果源和目的塊有重疊；源塊可能已被修改解決方案試圖存取兩個塊的兩端；使用臨時寄存器保存被覆蓋位置的值。16按需調(diào)頁的性能設(shè)P為頁錯誤的概率（0≤P≤1）如果P等于0，則不存在頁錯誤如果Ｐ等于１，則每次訪問都存在頁錯誤，純粹按需調(diào)頁（puredemandpaging）有效訪問時間ＥＡＴ＝（1－P）×內(nèi)存訪問時間+P×頁錯誤時間（頁錯誤準(zhǔn)備時間+頁換出時間（可選）+頁換入時間+重啟指令時間）17按需調(diào)頁的例子內(nèi)存存取時間=200納秒；平均頁錯誤服務(wù)時間=8毫秒；EAT=(1–p)x200+p(8milliseconds) =(1–px200+px8,000,000=200+px7,999,800如果每1000次訪問中有1次頁錯誤，則EAT=8.2微秒即因按需調(diào)頁而慢40倍。如果需要性能降低不超過10%，則220〉200+px7,999,800，即p<0.0000025188.3進程創(chuàng)建虛擬內(nèi)存也能在進程創(chuàng)建時，提供其他好處：寫時復(fù)制內(nèi)存映射文件19寫時復(fù)制(Copyonwrite)寫時復(fù)制父進程和子進程開始時共享同一頁面，這些頁面標(biāo)記為寫時復(fù)制。任何一個進程需要對頁進行寫操作，那么就創(chuàng)建一個共享頁的副本。只標(biāo)記那些能夠被修改的頁；創(chuàng)建進程更有效率；寫時復(fù)制時所需的空閑頁來自一個空閑緩沖池。按需填零（zero-fill-on-demand）。20進程2修改頁C之前21進程2修改頁C之后22沒有空閑幀時該如何處理？頁替換：在內(nèi)存中找到一些不使在用的頁，將它換出。算法性能：希望找到一個算法導(dǎo)致最小的的頁錯誤的發(fā)生一些頁可能被多次載入到內(nèi)存238.4頁面置換防止內(nèi)存的過度分配（over-allocating）給原有的頁錯誤服務(wù)程序增加頁置換。修改位（臟位）降低頁傳輸?shù)拈_銷－只有被修改過的頁才寫回至磁盤。分開了邏輯內(nèi)存與物理內(nèi)存小的物理內(nèi)存能為程序員提供巨大的虛擬內(nèi)存。頁幀分配和頁置換算法是實現(xiàn)按需調(diào)頁的基礎(chǔ)。24需要頁置換的情況25頁置換的基本方法查找所需頁在磁盤上的位置查找一空閑幀如果有空閑幀，那么就使用它如果沒有空閑幀，那么就使用頁置換算法以選擇一個“犧牲”幀（victimframe）。將“犧牲”幀的內(nèi)容寫到磁盤上；改變頁表和幀表。將所需頁讀入（新）空閑幀；改變頁表和幀表重啟用戶進程。26頁置換27頁置換算法標(biāo)準(zhǔn)：最低的頁錯誤率通過運行一特殊字符串（引用串，referencestring）來檢驗算法，計算其頁錯誤率針對某一特定引用串和頁轉(zhuǎn)換算法，為了確定頁錯誤的數(shù)量，還需要知道可用幀的數(shù)量。為了討論頁轉(zhuǎn)換算法，將采用以下引用串，而可用幀的數(shù)量為37,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,128頁錯誤與幀數(shù)量關(guān)系圖29FIFO頁置換引用頁：1,2,3,4,1,2,5,1,2,3,4,5。3個幀（每個進程最多只有3個頁面同時在內(nèi)存）1234125349pagefaults21342151324512330FIFO頁置換（cont.）引用頁：1,2,3,4,1,2,5,1,2,3,4,5。4個幀Belady異常：幀越多，頁錯誤越多。10pagefaults1235124543213421513245123431FIFO頁置換（cont.）32一個采用FIFO置換引用串的頁錯誤曲線33最優(yōu)頁置換（OptimalAlgorithm）置換那些在最長時間中不會被使用的頁。4個頁幀問題：如何獲得頁的引用情況？用途：評估頁置換算法的優(yōu)劣。6pagefaults45213421513245432134最優(yōu)頁置換（cont.）35LRU頁置換使用離過去最近作為不遠將來的近似，置換最長時間沒有使用的頁。引用頁：1,2,3,4,1,2,5,1,2,3,4,5。4個頁幀5123412512342134215132458Pagefaults36LRU頁置換（cont.）計數(shù)器實現(xiàn)每頁入口有一個計數(shù)器，每次引用頁都通過該入口，把時鐘值拷到計數(shù)器；每次需要換頁時，檢查計數(shù)器決定換出相應(yīng)的頁。37LRU頁置換（cont.）棧實現(xiàn)維護一個用雙向鏈表實現(xiàn)的棧。頁被引用時：將它移到棧頂；最壞情形下需要修改6個指針；每次更新可能有些費時；但是置換不需要搜索。38用堆棧來記錄最近使用的頁39LRU近似頁置換算法引用位每頁關(guān)聯(lián)一個引用位，初始為0當(dāng)頁被引用時，該位設(shè)為1替換引用位為0的頁（如果存在）不知道使用順序，只知道是否使用過40LRU近似頁置換算法41LRU近似頁置換算法二次機會算法當(dāng)要選擇一個頁時，檢查其引用位。如果其值為0那么就直接置換該頁。如果該引用位為1,那么就給該頁第二次機會，并選擇下一個FIFO頁。當(dāng)一個頁獲得第二次機會時，其引用位清零，且其到達時間設(shè)為當(dāng)前時間。42二次機會（時鐘）頁置換算法43基于計數(shù)的頁置換算法為每個頁保留一個用于記錄其引用次數(shù)的計數(shù)器。最不經(jīng)常使用頁置換算法（leastfrequentlyusedpagereplacementalgorithm,LFU）置換引用次數(shù)最少的頁；問題：開始使用很多，以后再也不使用。定期將計數(shù)器的值減半。最常使用頁置換算法（mostfrequentlyusedreplacementalgorithm,MFU）具有最小次數(shù)的頁可能剛調(diào)入，且還沒有使用448.5幀分配每個進程需要最低數(shù)量的頁例如：IBM370至少需要6頁用來處理MVC指令指令是6字節(jié)指令，可能跨越2頁；要移動的字符的塊，可能跨越2頁；要移動到目的區(qū)域也可能要跨2頁。兩種主要的分配方案固定分配優(yōu)先級分配45固定分配平均分配：如100幀，5個進程，則給每個進程20幀比例分配：根據(jù)進程的大小按比例分配。46固定分配特點每個進程所分配的數(shù)量會隨著多道程序的級別而有所變化。多道程序程度增加，那么每個進程會失去一些幀以提供給新來進程使用。反之，原來分配給離開進程的幀可以分配給剩余進程。高優(yōu)先級進程與低優(yōu)先級進程在這種分配方式下沒有任何區(qū)別。47優(yōu)先級分配按優(yōu)先級比例而非進程的大小來分配如果進程Pi產(chǎn)生了一個頁錯誤，那么從自身的幀中選擇用于替換從比自身優(yōu)先級低的進程中選取幀用于替換48全局分配與局部分配全局置換允許一個進程從所有幀集合中選擇一個置換幀，而不管該幀是否已分配給其他進程；一個進程可以從另一個進程中取幀。問題：進程不能控制其頁錯誤率局部置換要求每個進程僅從其自己的分配幀中進行選擇問題：內(nèi)存頁更少被使用。498.6系統(tǒng)顛簸（Thrashing）如果一個進程沒有足夠的頁，這會導(dǎo)致頁錯誤率就會非常高；CPU使用率低；這時OS認為必須提高多道程序的程度；因此，新的進程會加入到系統(tǒng)中來。顛簸：進程一直忙于將頁面換進換出?；ǜ嗟臅r間用于換頁，而不是用于執(zhí)行任務(wù)。50顛簸51按需調(diào)頁和顛簸為什么要進行按需調(diào)頁？局部模型（localitymodel）進程“需要”多少幀？從一個局部移向另一個局部；一個程序通常由多個不同局部組成，它們可能重疊。為什么會出現(xiàn)顛簸？所有局部的總合>內(nèi)存的大小等價于活動頁面>分配的幀。52內(nèi)存引用模式中的局部性53工作集模型工作集窗口（Workingsetwindow）：最近Δ個頁面引用最近Δ個引用的頁集合稱為工作集合（Workingset）WSSi(進程Pi的工作集)=最近所引用的所有頁面的總數(shù)（不同時刻值不同）如果Δ太小，則不能包含整個局部；如果Δ太大，則可能包含多個局部；如果Δ=∞，則包含了整個程序。54工作集模型（cont.）D＝∑WSSi表示總的幀需求量m=可分配的頁幀如果D大于m，那么有的進程就得不到足夠幀，從而會出現(xiàn)顛簸策略：可以懸掛某些進程，以消除顛簸現(xiàn)象55跟蹤工作集（困難）通過固定定時器中斷和引用位，能近似工作集模型例：假設(shè)Δ＝10,000每5000個引用會產(chǎn)生定時中斷。每個頁在內(nèi)存中保留2位。當(dāng)出現(xiàn)定時中斷時，先復(fù)制再清除所有頁的引用位。如果在內(nèi)存中有一位為1,那么就可以認為處于工作集中。56跟蹤工作集（困難）這種計算并不完全準(zhǔn)確，這是因為并不知道在5000個引用的什么位置出現(xiàn)了引用。通過增加歷史位的位數(shù)和中斷頻率，能夠降低這一不確定性。如，10位，1000個引用就產(chǎn)生中斷57頁錯誤頻率建立可接受的頁錯誤率如果錯誤率太低，則進程可能有太多的幀，因此應(yīng)丟棄一些幀如果錯誤率太高，則為進程分配更多幀588.7內(nèi)存映射文件內(nèi)存映射文件將磁盤塊映射成內(nèi)存頁；將文件I/O作為普通內(nèi)存訪問；機制最初采用按需調(diào)頁讀入文件；文件按頁大小比例讀入物理頁；隨后的讀/寫作為普通的內(nèi)存訪問。598.7內(nèi)存映射文件（cont.）簡化文件訪問和使用。寫內(nèi)存映射文件的方式同步寫異步寫多個進程可以同時映射同一個文件允許內(nèi)存頁共享；一個進程的寫可以看成是多個進程的寫；支持寫時復(fù)制。608.7內(nèi)存映射文件（cont.）61Windows中使用內(nèi)存映射I/O共享內(nèi)存進程1創(chuàng)建文件映射，并建立視圖進程2在自己的虛擬空間中打開并創(chuàng)建文件視圖628.8內(nèi)核內(nèi)存的分配處理方式與用戶態(tài)內(nèi)存不同。通常從空閑內(nèi)存池中獲取內(nèi)核需要為不同大小的數(shù)據(jù)結(jié)構(gòu)分配內(nèi)存。許多OS的內(nèi)核代碼和數(shù)據(jù)不受分頁系統(tǒng)控制。一些內(nèi)核內(nèi)存需要連續(xù)分配有的硬件要直接與物理內(nèi)存打交道，而不需要經(jīng)過虛擬內(nèi)存接口。63Buddy系統(tǒng)從物理上連續(xù)的大小固定的段上進行分配內(nèi)存按2的冪的大小進行分配滿足單元為2的冪的請求；需要調(diào)整到下一個更大的2的冪；當(dāng)需要分配的小于可利用的內(nèi)存塊時將當(dāng)前塊均分成兩塊；將其中的一塊類似進行直到大小合適為止。聚合相鄰的伙伴可以很快聚合起來。64Buddy系統(tǒng)分配65Slab分配Slab由一個或多個物理上連續(xù)的頁組成Cache含有一個或多個slab每個內(nèi)核數(shù)據(jù)結(jié)構(gòu)都有一個cache每個cache含有內(nèi)核數(shù)據(jù)結(jié)構(gòu)的對象實例，如,信號量，文件對象等；創(chuàng)建cache時包含若干個標(biāo)記為“空閑”的對象存儲內(nèi)核數(shù)據(jù)結(jié)構(gòu)的對象時，對象標(biāo)記為“使用”；如果slab中所有對象標(biāo)記為“使用”，則下一個對象從空的slab開始如果沒有空slab，則分配新的slab。66Slab分配（cont.）優(yōu)點沒有碎片；內(nèi)存請求可以快速滿足。67Slab分配（cont.）688.9其他考慮預(yù)調(diào)頁減少進程初啟時頁錯誤的次數(shù)；在頁被引用前，預(yù)先調(diào)入全部/部分頁面；如果預(yù)調(diào)入的頁是沒用的，則造成I/O和內(nèi)存的浪費；假設(shè)預(yù)調(diào)入s頁，其中使用率為α節(jié)省s*α頁錯誤的成本是大于還是小于預(yù)調(diào)入其他s*(1-α)頁不必要的頁面開銷?α

接近于0預(yù)調(diào)頁是失敗的；α

接近于1預(yù)調(diào)頁是成功的。698.9其他考慮（cont.）頁大小的選擇（有許多因素影響頁面大小）碎片需要小頁頁表大小需要大頁I/O開銷需要大頁局部性更小頁？更大頁？（矛盾）更小的頁應(yīng)用導(dǎo)致更少的I/O和更少的總的分配內(nèi)存為了降低頁錯誤數(shù)量，需要大頁。708.9其他考慮（cont.）TLB范圍：指通過TLB可訪問的內(nèi)存量TLBReach=(TLBSize)×(PageSize)理想狀況下，一個進程所有的工作集合應(yīng)位于TBL中，否則會帶來較高的頁錯誤率增加TLB范圍的兩種方法增加TBL大小代價較大增加頁的大小或提供多種頁大小增加頁的大小，可能導(dǎo)致碎片的增加提供多種頁，要求OS管理TLB718.9其他考慮（cont.）程序結(jié)構(gòu)假設(shè)頁大小為128個字，分配給進程一個幀intA[][]=newint[128][128];每一行存