軟件技術(shù)基礎(chǔ)存儲管理

軟件技術(shù)基礎(chǔ)存儲管理第一頁，共六十三頁，編輯于2023年，星期三存儲器層次結(jié)構(gòu)快速緩存：Cache內(nèi)存：DRAM,SDRAM,DRDRAM等；外存：軟盤、硬盤、光盤、磁帶等；第二頁，共六十三頁，編輯于2023年，星期三2.4.1存儲管理的功能內(nèi)存的分配與管理內(nèi)存的共享與保護地址變換主存的“擴充”——虛擬內(nèi)存覆蓋與交換技術(shù)第三頁，共六十三頁，編輯于2023年，星期三一、內(nèi)存分配與管理內(nèi)存分配就是為進程分配內(nèi)存空間，涉及以下問題：管理內(nèi)存分配表：記錄分配情況、空閑情況等制定分配策略制定內(nèi)存劃分方式放置策略調(diào)入策略淘汰策略等分不等分第四頁，共六十三頁，編輯于2023年，星期三二、內(nèi)存共享與保護共享保護共享內(nèi)存資源，程序并發(fā)執(zhí)行；共享內(nèi)存中公共信息。避免并發(fā)執(zhí)行的程序相互干擾；避免用戶程序侵犯系統(tǒng)區(qū)。第五頁，共六十三頁，編輯于2023年，星期三三、地址變換邏輯地址（程序空間）物理地址（內(nèi)存空間）重定位0000Memory地址是以字節(jié)為單位的存儲器編號內(nèi)存空間（絕對空間）：整個系統(tǒng)內(nèi)存從0開始以字節(jié)為單位編址——物理地址程序空間（相對空間）：程序由機器代碼組成，以字節(jié)為單位，每個程序都從0開始編址——邏輯地址第六頁，共六十三頁，編輯于2023年，星期三四、虛擬存儲技術(shù)引入原因：當作業(yè)很大，超過內(nèi)存剩余時，無法裝入裝入的作業(yè)對內(nèi)存利用率不高：99%的指令在短時間內(nèi)都不會得到執(zhí)行解決方法不需一次全部裝入作業(yè)，程序部分裝入就可以執(zhí)行裝入內(nèi)存的程序在不需要訪問時暫時從內(nèi)存換出給用戶感覺比實際空間大的虛擬空間虛空間大小虛空間的邏輯大小＝可尋址范圍虛空間的實際大?。絻?nèi)存＋外存對換區(qū)例：32位操作系統(tǒng)的可尋址范圍是232=4GByte第七頁，共六十三頁，編輯于2023年，星期三第八頁，共六十三頁，編輯于2023年，星期三程序的裝入和鏈接從用戶源程序到內(nèi)存中可執(zhí)行的代碼將經(jīng)歷：編譯：完成源程序從高級語言到機器可理解代碼的轉(zhuǎn)換根據(jù)任務(wù)的需要可能形成若干相對獨立的目標模塊鏈接：將目標模塊鏈接起來，如標準庫、系統(tǒng)庫形成一個完整的裝入模塊裝入：由操作系統(tǒng)的裝入程序?qū)⒀b入模塊裝入內(nèi)存涉及：內(nèi)存空間的分配——放到內(nèi)存什么地方地址空間的映射——地址變換第九頁，共六十三頁，編輯于2023年，星期三（1）程序的裝入A、絕對裝入方式裝入模塊的地址與內(nèi)存實際地址完全相同系統(tǒng)裝入程序時工作最簡單，直接分配，不變換地址要求：用戶使用絕對地址編程用戶了解程序在內(nèi)存中的存放位置用戶控制內(nèi)存使用情況第十頁，共六十三頁，編輯于2023年，星期三B、靜態(tài)重定位裝入方式裝入模塊中使用從0開始的相對地址裝入時，由系統(tǒng)分配內(nèi)存空間，并完成裝入模塊中相對地址變換為絕對地址重定位邏輯地址基地址+物理地址裝入模塊中的相對地址第十一頁，共六十三頁，編輯于2023年，星期三裝入時的地址變換MOVax,[2500]365010002500100001100012500MOVax,[2500]365程序空間內(nèi)存空間0[12500]12500＝10000+2500物理地址基地址相對地址第十二頁，共六十三頁，編輯于2023年，星期三C、動態(tài)重定位裝入方式裝入模塊中使用相對地址，裝入時不變換地址，在執(zhí)行時才完成地址的變換方便了模塊的動態(tài)裝入動態(tài)重定位需特殊的硬件支持——重定位寄存器利用硬件地址變換機構(gòu)第十三頁，共六十三頁，編輯于2023年，星期三（2）程序的鏈接0000裝入模塊目標模塊將任務(wù)所需的目標模塊鏈接起來，形成一個完整的裝入模塊目標模塊使用的地址是相對的，都是從0開始形成統(tǒng)一地址空間的裝入模塊的過程——鏈接第十四頁，共六十三頁，編輯于2023年，星期三A、靜態(tài)鏈接裝入模塊是完整的，包含所有的目標模塊C、運行時動態(tài)鏈接裝入模塊不完整，裝入時也沒有裝入所有的模塊運行時根據(jù)需要，找到所需模塊，裝入，鏈接，再執(zhí)行。需要動態(tài)重定位的支持裝入模塊并不包含所有目標模塊由系統(tǒng)裝入程序在裝入同時找到需要的其它模塊，并鏈接B、裝入時動態(tài)鏈接第十五頁，共六十三頁，編輯于2023年，星期三運行時動態(tài)鏈接例printf(“OK”);printf(“OK”);主模塊庫模塊voidprintf(…){}00裝入模塊voidprintf(…){}編譯裝入printf(“OK”);執(zhí)行33600Hcall33600H運行時動態(tài)鏈接內(nèi)存第十六頁，共六十三頁，編輯于2023年，星期三2.4.2連續(xù)分配存儲管理特點：為一個用戶程序分配一個連續(xù)的內(nèi)存空間程序空間本來就是連續(xù)的用連續(xù)的內(nèi)存裝入連續(xù)的程序，減少管理工作的難度可分為：單一連續(xù)區(qū)存儲管理分區(qū)存儲管理第十七頁，共六十三頁，編輯于2023年，星期三單一連續(xù)區(qū)存儲管理內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡單，適用于單用戶、單任務(wù)的OS。優(yōu)點：易于管理。缺點：對要求內(nèi)存空間少的程序，造成內(nèi)存浪費；程序全部裝入，很少使用的程序部分也占用內(nèi)存。第十八頁，共六十三頁，編輯于2023年，星期三第十九頁，共六十三頁，編輯于2023年，星期三分區(qū)存儲管理把內(nèi)存分為一些大小相等或不等的分區(qū)(partition)，每個應用進程占用一個或幾個分區(qū)；操作系統(tǒng)占用其中一個分區(qū)。特點：適用于多道程序系統(tǒng)和分時系統(tǒng)支持多個程序并發(fā)執(zhí)行可能存在內(nèi)零頭（分配給用戶但沒有被使用的空間）和外零頭（沒有分配但無法分配的空間）按不同分配方式，分為：固定分區(qū)可變分區(qū)第二十頁，共六十三頁，編輯于2023年，星期三一、固定分區(qū)基本思想：將內(nèi)存區(qū)固定地劃分為大小相等或者不等的區(qū)域，每個分區(qū)裝入一道作業(yè)。分區(qū)劃分后，每個分區(qū)的長度和內(nèi)存中的分區(qū)總數(shù)將保持不變。內(nèi)存分配表分區(qū)號大小起始地址狀態(tài)14K0000H未分配28K4000H已分配312K12000H未分配第二十一頁，共六十三頁，編輯于2023年，星期三固定分區(qū)(大小相同)固定分區(qū)(多種大小)優(yōu)點：易于實現(xiàn)，開銷小。缺點：內(nèi)零頭造成浪費分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目第二十二頁，共六十三頁，編輯于2023年，星期三二、可變分區(qū)（動態(tài)分區(qū)）基本思想：根據(jù)作業(yè)任務(wù)的大小劃分分區(qū)，分區(qū)的大小和數(shù)目不再固定。分配區(qū)控制塊空閑區(qū)控制塊AMCB(AllocationMemoryControlBlock)FMCB(FreeMemoryControlBlock)第二十三頁，共六十三頁，編輯于2023年，星期三分配過程：10K作業(yè)1作業(yè)2作業(yè)3作業(yè)12K作業(yè)21K作業(yè)34K作業(yè)1作業(yè)3作業(yè)4作業(yè)43K第二十四頁，共六十三頁，編輯于2023年，星期三分配算法（空白分區(qū)選擇）1、首次適應FF(FirstFit)（1）將空白分區(qū)按地址遞增順序鏈接（2）從鏈首開始查找適合的分區(qū)優(yōu)先分配內(nèi)存中低地址部分優(yōu)點：缺點：簡單在低地址部分會積累大量外零頭（3）從選中的分區(qū)中分出所需的大小，其余部分仍留在空白分區(qū)鏈表里第二十五頁，共六十三頁，編輯于2023年，星期三選取最適合的空白分區(qū)大分區(qū)保證缺點：優(yōu)點：效率不高零頭更小（1）將空白分區(qū)按大小遞增順序鏈接（2）從鏈首開始查找適合的分區(qū)2、最佳適應BF(BestFit)第二十六頁，共六十三頁，編輯于2023年，星期三3、最壞適應WF(WorstFit)？選取分區(qū)中最大的一個——最不適合的（1）將空白分區(qū)按大小遞減順序鏈接（2）從鏈首開始分配分區(qū)優(yōu)點：查找效率顯著提高，一次就找到缺點：大作業(yè)容納能力會下降第二十七頁，共六十三頁，編輯于2023年，星期三“拼接”/“緊縮”技術(shù)多次分配、回收后，形成小空閑區(qū)無法使用。這時需要使用拼接或緊縮技術(shù)將已分配分區(qū)移動，使未分配分區(qū)合成較大分區(qū)。對占用分區(qū)進行內(nèi)存數(shù)據(jù)搬移占用CPU時間如果對占用分區(qū)中的程序進行"浮動"，則其重定位需要硬件支持。緊縮時機：每個分區(qū)釋放后，或內(nèi)存分配找不到滿足條件的空閑分區(qū)時。第二十八頁，共六十三頁，編輯于2023年，星期三2.4.3覆蓋與交換技術(shù)引入原因：在分區(qū)管理技術(shù)中，程序的地址空間（邏輯地址空間）可能大于實際存儲器空間，使程序無法裝入（無法運行）。覆蓋（Overlay）交換（Swapping）第二十九頁，共六十三頁，編輯于2023年，星期三一、覆蓋（Overlay）一段內(nèi)存區(qū)可以先后被不同的程序段重復使用常駐區(qū)（非覆蓋區(qū)）覆蓋區(qū)初始段處理段輸出段程序員必須自己設(shè)計覆蓋結(jié)構(gòu)覆蓋斷劃分困難，不易實現(xiàn)第三十頁，共六十三頁，編輯于2023年，星期三二、交換（Swapping）在內(nèi)、外存之間進行數(shù)據(jù)和程序的交換內(nèi)存磁盤交換技術(shù)一般與分區(qū)、分頁、分段管理技術(shù)結(jié)合使用。第三十一頁，共六十三頁，編輯于2023年，星期三2.4.4分頁存儲管理連續(xù)分配方式要求連續(xù)存放，產(chǎn)生大量的內(nèi)/外零頭，浪費空間。引入離散分配方式——程序在內(nèi)存中不一定連續(xù)存放頁塊邏輯地址物理地址非連續(xù)地址映射第三十二頁，共六十三頁，編輯于2023年，星期三一、分頁管理的基本思想頁：將邏輯地址空間劃分為大小相同的塊，稱為頁或虛頁面（Page）塊：將實際物理空間劃分為與頁大小相等的塊，稱為存儲塊或頁框（PageFrame）沒有外零頭，僅有小于一個頁面的內(nèi)零頭優(yōu)點:一個塊可以裝入一頁邏輯地址連續(xù)的頁可以通過地址變換機構(gòu)映射到不連續(xù)的內(nèi)存塊中第三十三頁，共六十三頁，編輯于2023年，星期三二、分頁管理的基本方法關(guān)鍵問題：如何實現(xiàn)頁到塊的地址變換？——通過頁表實現(xiàn)。…012m內(nèi)存012n用戶程序012n012n3m-21m-1頁表頁號塊號第三十四頁，共六十三頁，編輯于2023年，星期三頁面地址轉(zhuǎn)換頁面地址轉(zhuǎn)換通過下述3種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)：（1）存儲分塊表（MBT）整個系統(tǒng)一個，記錄所有內(nèi)存塊的狀況。塊號作業(yè)ID狀態(tài)01…nOS作業(yè)1…作業(yè)n忙閑…忙第三十五頁，共六十三頁，編輯于2023年，星期三（2）頁表（PT）頁號塊號0211024每個作業(yè)一個，記錄作業(yè)的頁與內(nèi)存塊的關(guān)系頁表在作業(yè)裝入時創(chuàng)建，作業(yè)撤銷時撤銷。作業(yè)被調(diào)度時，頁表存放在頁表控制寄存器PTCR中（3）作業(yè)表（JT）作業(yè)號頁表大小頁表始址狀態(tài)020已分配116未分配240已分配整個系統(tǒng)一個，記錄所有作業(yè)的頁表情況。第三十六頁，共六十三頁，編輯于2023年，星期三頁面地址到物理地址轉(zhuǎn)換過程：(1)作業(yè)被調(diào)度時首先通過JT找到相應頁表的起始地址及大小，并裝入PTCR(2)將頁號與PTCR中的頁表大小進行比較，若頁號>頁表大小則為非法訪問，產(chǎn)生越界中斷；否則為合法訪問，根據(jù)頁表起始地址和頁號找到該頁頁表表項(3)通過頁表表項找到邏輯頁所對應的物理塊號，然后將塊號與頁內(nèi)偏移地址結(jié)合形成物理地址第三十七頁，共六十三頁，編輯于2023年，星期三頁表始址頁表大小PTCR

+塊號塊內(nèi)地址物理地址寄存器頁號頁內(nèi)地址邏輯地址寄存器>越界？頁號塊號J1的頁表2404010作業(yè)號頁表大小頁表始址狀態(tài)J020已分配J1161024已分配JT210第三十八頁，共六十三頁，編輯于2023年，星期三

例：設(shè)塊大小為32，利用下面的頁表，將邏輯地址140變換為物理地址。解：1）邏輯地址——有效地址頁號＝INT[140/32]＝4頁內(nèi)地址＝140%32＝122）查頁表得到塊號為53）物理地址＝5×32+12＝172頁號塊號0617223445510第三十九頁，共六十三頁，編輯于2023年，星期三2.請求式分頁屬于虛擬存儲管理：部分裝入、請求調(diào)入、頁面置換需要的頁面是否已裝入內(nèi)存？當需要訪問的頁面不在內(nèi)存中如何處理？當發(fā)現(xiàn)將要用到的頁面不在主存中時產(chǎn)生缺頁中斷，由缺頁中斷來完成頁面的調(diào)入缺頁中斷將耗費系統(tǒng)時間，缺頁率是影響系統(tǒng)性能的主要因素缺頁率：需要訪問的頁面不在內(nèi)存中次數(shù)在總頁面訪問次數(shù)的比率第四十頁，共六十三頁，編輯于2023年，星期三如果要訪問的頁不在內(nèi)存中

——缺頁中斷處理頁號塊號存取控制狀態(tài)位引用位修改位外存地址引用位：0未訪問過1訪問過對頁表擴充：讓系統(tǒng)了解頁面狀態(tài)修改位：0未修改1已修改過狀態(tài)位：0不在內(nèi)存1在內(nèi)存第四十一頁，共六十三頁，編輯于2023年，星期三缺頁中斷的處理過程：相對地址頁號頁內(nèi)地址頁表始址頁表大小頁表控制寄存器+塊號塊內(nèi)地址物理地址寄存器邏輯地址寄存器>越界？頁號塊號頁表狀態(tài)位缺頁中斷215030160第四十二頁，共六十三頁，編輯于2023年，星期三頁面淘汰算法若缺頁中斷處理時內(nèi)存已無空閑分塊？頁面置換(頁面淘汰)頁面淘汰算法抖動Thrashing頻繁地調(diào)進和調(diào)出頁面，特別是被換出的頁面在短時間內(nèi)又要被換入，系統(tǒng)開銷顯著增加，以至于系統(tǒng)吞吐量大大下降第四十三頁，共六十三頁，編輯于2023年，星期三（1）FIFO算法先進先出算法——最簡單的算法（2）LRU算法最近最久不用頁面被淘汰（3）LFU算法最近最少使用頁面被淘汰常用頁面淘汰算法：第四十四頁，共六十三頁，編輯于2023年，星期三3.快表問題引入：兩次內(nèi)存訪問訪問頁表得到物理地址訪問物理地址得到數(shù)據(jù)快表：用于存放當前頁表中最頻繁訪問表項的高速緩存(Cache)?；诳毂淼姆猪撓到y(tǒng)：先查找快表，未成功再查找頁表（p.132圖2.34）第四十五頁，共六十三頁，編輯于2023年，星期三4.分頁式存儲管理特點3重定位方便2保護功能好1存儲效率高4易于共享5開銷稍微偏大第四十六頁，共六十三頁，編輯于2023年，星期三2.4.5分段存儲管理引入原因：按頁劃分程序的模塊化矛盾以段為內(nèi)存分配單位優(yōu)點：方便程序設(shè)計，便于內(nèi)存共享、保護、動態(tài)裝入。第四十七頁，共六十三頁，編輯于2023年，星期三分段實現(xiàn)思想作業(yè)按邏輯信息的完整性分段，段有段名和段號；段長度由程序決定，可動態(tài)延伸；各段都是從0開始編址的連續(xù)地址空間（二維）一個段是連續(xù)的，各段可以離散存放；第四十八頁，共六十三頁，編輯于2023年，星期三2.分段的地址轉(zhuǎn)換段表：每進程一個，記錄進程內(nèi)段與內(nèi)存實際段存放基地址的映射關(guān)系。段號段長02k11k240k主存始址1004000－－存取控制增補位010RWRW特征位110修改位100段表（ST）示意圖第四十九頁，共六十三頁，編輯于2023年，星期三地址變換機構(gòu)和過程：段表始址段表大小段表寄存器（JT）+物理地址寄存器>越界？段號基址段表4100段號邏輯地址寄存器段內(nèi)地址+絕對地址第五十頁，共六十三頁，編輯于2023年，星期三3.段的共享與保護段的共享：段表中同一起始地址段的保護：地址越界保護存取控制保護第五十一頁，共六十三頁，編輯于2023年，星期三分段方式的內(nèi)存共享共享段表段號基址進程1段表進程2段表段名1256始址內(nèi)存共享進程數(shù)記錄共享段和進程的信息，以便共享段的分配和回收第五十二頁，共六十三頁，編輯于2023年，星期三4.分段與分頁的比較（1）“分頁”是系統(tǒng)活動，用戶無法介入，頁的大小固定“分段”是用戶可見的，段大小可變（2）頁式信息的物理單位，不是完整的邏輯單位段是完整的邏輯信息單位（3）分頁的作業(yè)空間是一維的，是單一線性空間分段的作業(yè)空間是二維的。第五十三頁，共六十三頁，編輯于2023年，星期三2.4.6段頁式管理技術(shù)引入原因：分頁的優(yōu)點：分段的優(yōu)點：存儲器利用率高符合程序的模塊結(jié)構(gòu)+段頁式存儲管理第五十四頁，共六十三頁，編輯于2023年，星期三段頁式實現(xiàn)思想有效地址=段名＋段內(nèi)地址段內(nèi)頁號+頁內(nèi)地址用戶程序分段，段內(nèi)分頁（系統(tǒng)自動）系統(tǒng)內(nèi)存分塊（系統(tǒng)自動）每塊裝入一頁，各塊之間可以不連續(xù)123第五十五頁，共六十三頁，編輯于2023年，星期三2.

段頁式地址轉(zhuǎn)換機構(gòu)段表＋頁表實現(xiàn)地址轉(zhuǎn)換段表：記錄每一段段內(nèi)頁表地址240段號頁表長頁表始址段長段內(nèi)頁表頁號塊號0211頁號塊號01019220第五十六頁，共六十三頁，編輯于2023年，星期三3.段頁式地址轉(zhuǎn)換過程+物理地址寄存器邏輯地址段號段內(nèi)地址頁號頁內(nèi)地址段表始址段表大小段表寄存器段號頁表始址段表頁號塊號頁表塊號塊內(nèi)地址+！段頁式也可引入快表第五十七頁，共六十三頁，編輯于2023年，星期三4.段頁式的優(yōu)缺點優(yōu)點：缺點：結(jié)合了分頁和分段的優(yōu)點，既有效利用了存儲器，也符合邏輯習慣，便于保護、共享。由于程序分段，段內(nèi)分頁，造成地址轉(zhuǎn)換速度降低，系統(tǒng)結(jié)構(gòu)復雜。第五十八頁，共六十三頁，編輯于2023年，星期三Windows的存儲管理NT使用的頁面大小為4KB（212）。每個NT進程地址空間為4GB（232），其中：用戶存儲區(qū)：在用戶態(tài)和核心態(tài)都可訪問的用戶存儲區(qū)為2GB；用戶存儲區(qū)為頁交換區(qū)，可對換到外存；用戶存儲區(qū)的內(nèi)容包括：專用進程地址空間：用戶代碼、數(shù)據(jù)和堆棧；線程環(huán)境塊（TEB）：用戶態(tài)代碼可修改的線程控制信息；進程環(huán)境塊（PEB）：用戶態(tài)代碼可修改的進程控制信息；共享用戶數(shù)據(jù)頁：系統(tǒng)存儲區(qū)映像，為用戶態(tài)可訪問的系統(tǒng)空間，目的在于避免用戶態(tài)與核心態(tài)的頻繁切換；如：系統(tǒng)時間。第五十九頁，共六十三頁，編輯于2023年，星期三有效狀態(tài)(activeorvalid)：某進程正在使用該頁面，也可能不屬于任何進程(如不可對換的內(nèi)核頁面)；過渡狀態(tài)(transition)：頁面處于不屬于任何進程的過渡狀態(tài)，用于避免頁面沖突。如正在進行頁面與I/O設(shè)備間的數(shù)據(jù)傳送。清零狀態(tài)(zer