西工大計(jì)算機(jī)考研操作系統(tǒng)4-13os memory3agenda

Zhang SchoolofComputerScienceNorthwesternPolytechnicalUniversity節(jié)省內(nèi)存技術(shù)（交換、可重入、覆蓋虛擬內(nèi)存（請(qǐng)求分頁(yè)、請(qǐng)求分段、頁(yè)面置換算法、請(qǐng)求分段/段頁(yè)交換（針對(duì)因其他進(jìn)程存在而導(dǎo)致的主存區(qū)不足問(wèn)題，稱(chēng)為主存暫時(shí)性短缺交換 進(jìn)程掛起（換出狀態(tài)）——swap進(jìn)程激活（換入狀態(tài)）——swap交從整體上調(diào)入進(jìn)程，使其運(yùn)行一段時(shí)間，然后把它存可重入 可重入代碼（reentrantcode）或純代碼覆蓋（若程序長(zhǎng)度超出物理內(nèi)存總和，則出現(xiàn)主存永久性短缺虛 缺點(diǎn)：程序員必須覆蓋結(jié)構(gòu)（駐留在主存的是哪個(gè)程序段，哪些是被覆虛擬內(nèi)存Virtual虛擬內(nèi)存的引：每個(gè)進(jìn)程在運(yùn)行前必 全部裝入內(nèi)大地址空間進(jìn)程無(wú)法運(yùn)行（無(wú)法裝入 駐留性：進(jìn)程裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至進(jìn)程運(yùn)進(jìn)程運(yùn)行時(shí)，不是所有程序模塊都始終在運(yùn)行（占用了寶貴的內(nèi)存資源Virtual程序程序當(dāng)前使用部分，保留在主John效果上，實(shí)現(xiàn)內(nèi)存容量的“Virtual基本特部分裝多次交

每個(gè)進(jìn)程不是全部一次裝入內(nèi)存，而是分成 分裝在進(jìn)程運(yùn)行期間，它所需全部程序和數(shù)據(jù)分成多次調(diào)入虛擬擴(kuò)離散分

Virtual 如 x86的地址線是32位，則程序的可尋址范圍是Linux和Windows都為應(yīng)用程序提供一個(gè)4GB

虛 局部性原1968年，Peter ：程序執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)程序執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過(guò)程調(diào)過(guò)程調(diào)用的嵌套深度一般不超過(guò)5，因此執(zhí)行的范圍會(huì)在一段時(shí)間這組嵌套過(guò)程程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多程序中存在相當(dāng)多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作（如，數(shù)組），它們往往局限小的范圍內(nèi)程序中有些部分的執(zhí)行是彼此互斥的，每次不是都要用到（如，異常處理Localityofreference（局部相關(guān)性原理（典型原因：程序中存在大量的循環(huán)操作（典型原因：程序的順序執(zhí)行Denning、Knuth、Tanenbaum、Patterson等人提供了實(shí)局部性原Virtual基于局部性原理，得出的重要結(jié)論程序在運(yùn)行之前，沒(méi)有必要全部裝入內(nèi)存部分頁(yè)面先裝入內(nèi)存便可運(yùn)行可將外存和內(nèi)存統(tǒng)一考慮，外存作為存放信息的主要場(chǎng)所，而內(nèi)存為CPU在一段時(shí)間內(nèi)需要存取的程序和數(shù)據(jù)的由于OS的作用，使得從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充，其邏輯容量取決于內(nèi)、外存容量之和，而其運(yùn)行速度接近于內(nèi)存速度，每位成本卻又接近于外存Virtual虛 是基于程序局部性原理的一種假想的而非物理存在 其主要任務(wù) Virtual 器VS.交換技雖然兩者都是在內(nèi)存和磁盤(pán)之間交換信息，但卻存在很虛擬器：以“頁(yè)或段”為單位，即使進(jìn)程所需內(nèi)存空間大于當(dāng)前系統(tǒng)Virtual >最早在20世紀(jì)60年代初，英國(guó)Atlas計(jì)算機(jī)較完整的虛 >20世紀(jì)60年代中期，分時(shí)系統(tǒng)MULTICS和IBM系列OS虛 器推>20世紀(jì)70年代，為廣大計(jì)算機(jī)研制者和用戶(hù)所 Virtual Virtualmemorywithpaging（虛擬分頁(yè)Virtualmemorywithsegmentation（虛擬分段Segmenteddvirtualmemory（虛擬段頁(yè)虛擬分頁(yè)VirtualVirtual硬件+軟件共同支VirtualIssuesinvirtual如何將邏輯地址轉(zhuǎn)換成物理地址，何時(shí)轉(zhuǎn)換Addresstranslationalgorithmappliedeverytimeamemoryreferenceis如何加快地址轉(zhuǎn)換速度如何調(diào)入虛P(yáng)agefault如 虛頁(yè)如何進(jìn)行頁(yè)面置換

是否需要將所有進(jìn)入內(nèi)存的虛頁(yè)都寫(xiě)回輔存NO,onlytheonesthatare從何處調(diào)入虛 如 內(nèi)存和管理內(nèi)存空間 -framelist,proc地址變CPU、MMU、Main地址變?cè)谔?系統(tǒng)中，物理內(nèi)存對(duì)程序員是透明的，程序員只有知道程序裝入到虛 器之 器的地址變換處理，由動(dòng)態(tài)地址變換機(jī)構(gòu)（DAT）地址變CPU、MMU、Main地址變換的硬件實(shí)Virtual頁(yè)表結(jié)PagePagePagePageTablePMOtherControlFrame頁(yè)表結(jié)頁(yè)面失缺頁(yè)中斷及處理（Pagefaulthandler缺頁(yè)中通常，CPU都是在一條指令執(zhí)行完后，才檢查是否有中斷請(qǐng)求到達(dá)有，便去響應(yīng)，否則，繼續(xù)執(zhí)行下一條缺頁(yè)中斷在指令執(zhí)行期間產(chǎn)生和進(jìn)行處理之后。所缺的頁(yè)面調(diào)入之后，重新執(zhí)行被中斷的指令 ，繼續(xù)執(zhí)行頁(yè)面失效分–pagefaultrate=缺頁(yè)次數(shù)/全 影響缺頁(yè)率主要因素Overhead=pagetablespace+internalpagetablepagetabled

最佳值應(yīng)在中間某個(gè)拐點(diǎn)，對(duì)p采用多種頁(yè)面大小

Optimized 頁(yè)面置換過(guò)置換算影響缺頁(yè)率主要因素—— cement不可實(shí)現(xiàn)，基準(zhǔn):

PBAPageBufferingAlgorithm現(xiàn)實(shí)有效算法（設(shè)置雙鏈表，設(shè)置修改位 現(xiàn)實(shí)算法，但移動(dòng)頁(yè)面開(kāi)銷(xiāo)大（設(shè) 位，鏈表 現(xiàn)實(shí)算法（設(shè) 位，環(huán)形鏈表 第二次機(jī)會(huì)置換算法與時(shí)鐘置換算法只是實(shí)現(xiàn)上的不LRULeastRecentlyUsed 淘汰沒(méi)有使用時(shí)間最長(zhǎng)的頁(yè)

基于工作集的置換算法WorkingSetClockFIFO：Belady’s第二次機(jī)會(huì)置換算Clock-basedStateofbufferjustpriortopage ..

nPageuse=

0Pageuse=

1Pageuse=

Stateofbufferjustthenextpage ..

Pageuse=

Pageuse=

1Pageuse=2next

Pageuse=

Pageuse=Page use=Pageuse=7

Pageuse=

Pageuse=

Pageuse= Pageuse=4

Page use=Pageuse=7

Pageuse=

Pageuse=

Pageuse= Pageuse=4 頁(yè)面失效分程序特性：總希望編出的程序具有較好的局實(shí)例一個(gè)程序要將A[128，128]數(shù)組設(shè)初值“0”，分頁(yè)時(shí)把數(shù)組中的每一行放在一頁(yè)中（假定：只能放一行元素128128page128page頁(yè)面失效分影響缺頁(yè)率主要因素OS給進(jìn)程分配的實(shí)頁(yè)數(shù)（residentset實(shí)頁(yè)分實(shí)頁(yè)分??msisize ofprocess Ssim of

s1a1064ai pi??

m

a12764 實(shí)頁(yè)分（進(jìn)程的駐留集在進(jìn)程生命周期內(nèi)不斷變化 缺頁(yè)率↑，給該進(jìn)程 缺頁(yè)率↓，給該進(jìn)程 虛擬分段Virtual在分段段表的基礎(chǔ)上添加若干項(xiàng)（存取權(quán)限，段增長(zhǎng)位等VirtualSegmentSegmentTablePMOtherControlSegment虛擬段頁(yè)CombinedPaging&虛