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

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

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

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