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

1、2.4 存儲管理對主存儲器空間的管理內(nèi)存的分配與管理虛擬存儲技術(shù)地址變換存貯空間保護(hù)1存儲器層次結(jié)構(gòu)快速緩存：Cache內(nèi)存：DRAM, SDRAM, DRDRAM等；外存：軟盤、硬盤、光盤、磁帶等；22.4.1 存儲管理的功能內(nèi)存的分配與管理內(nèi)存的共享與保護(hù)地址變換主存的“擴(kuò)充”虛擬內(nèi)存覆蓋與交換技術(shù)3一、內(nèi)存分配與管理內(nèi)存分配就是為進(jìn)程分配內(nèi)存空間，涉及以下問題：管理內(nèi)存分配表：記錄分配情況、空閑情況等制定分配策略制定內(nèi)存劃分方式放置策略調(diào)入策略淘汰策略等分不等分4二、內(nèi)存共享與保護(hù)共 享保 護(hù)共享內(nèi)存資源，程序并發(fā)執(zhí)行；共享內(nèi)存中公共信息。避免并發(fā)執(zhí)行的程序相互干擾；避免用戶程序侵犯系統(tǒng)

2、區(qū)。5三、地址變換邏輯地址（程序空間）物理地址（內(nèi)存空間）重定位0000Memory地址是以字節(jié)為單位的存儲器編號內(nèi)存空間（絕對空間）：整個系統(tǒng)內(nèi)存從0開始以字節(jié)為單位編址物理地址程序空間（相對空間）：程序由機(jī)器代碼組成，以字節(jié)為單位，每個程序都從0開始編址邏輯地址6四、虛擬存儲技術(shù)引入原因：當(dāng)作業(yè)很大，超過內(nèi)存剩余時，無法裝入裝入的作業(yè)對內(nèi)存利用率不高：99%的指令在短時間內(nèi)都不會得到執(zhí)行解決方法不需一次全部裝入作業(yè)，程序部分裝入就可以執(zhí)行裝入內(nèi)存的程序在不需要訪問時暫時從內(nèi)存換出給用戶感覺比實(shí)際空間大的虛擬空間虛空間大小虛空間的邏輯大小 可尋址范圍虛空間的實(shí)際大小 內(nèi)存外存對換區(qū)例：32位

3、操作系統(tǒng)的可尋址范圍是232=4GByte78程序的裝入和鏈接從用戶源程序到內(nèi)存中可執(zhí)行的代碼將經(jīng)歷：編譯：完成源程序從高級語言到機(jī)器可理解代碼的轉(zhuǎn)換根據(jù)任務(wù)的需要可能形成若干相對獨(dú)立的目標(biāo)模塊鏈接：將目標(biāo)模塊鏈接起來，如標(biāo)準(zhǔn)庫、系統(tǒng)庫形成一個完整的裝入模塊裝入：由操作系統(tǒng)的裝入程序?qū)⒀b入模塊裝入內(nèi)存涉及：內(nèi)存空間的分配放到內(nèi)存什么地方地址空間的映射地址變換9（1）程序的裝入A、絕對裝入方式裝入模塊的地址與內(nèi)存實(shí)際地址完全相同系統(tǒng)裝入程序時工作最簡單，直接分配，不變換地址要求：用戶使用絕對地址編程用戶了解程序在內(nèi)存中的存放位置用戶控制內(nèi)存使用情況10B、靜態(tài)重定位裝入方式裝入模塊中使用從0開始

4、的相對地址裝入時，由系統(tǒng)分配內(nèi)存空間，并完成裝入模塊中相對地址變換為絕對地址重定位邏輯地址基地址+物理地址裝入模塊中的相對地址11裝入時的地址變換MOV ax , 2500365010002500100001100012500MOV ax , 2500365程序空間內(nèi)存空間01250012500 10000+2500物理地址基地址相對地址12C、動態(tài)重定位裝入方式裝入模塊中使用相對地址，裝入時不變換地址， 在執(zhí)行時才完成地址的變換方便了模塊的動態(tài)裝入動態(tài)重定位需特殊的硬件支持重定位寄存器利用硬件地址變換機(jī)構(gòu)13（2）程序的鏈接0000裝入模塊目標(biāo)模塊將任務(wù)所需的目標(biāo)模塊鏈接起來，形成一個完整的

5、裝入模塊目標(biāo)模塊使用的地址是相對的，都是從0開始形成統(tǒng)一地址空間的裝入模塊的過程鏈接14A、靜態(tài)鏈接裝入模塊是完整的，包含所有的目標(biāo)模塊C、運(yùn)行時動態(tài)鏈接裝入模塊不完整，裝入時也沒有裝入所有的模塊運(yùn)行時根據(jù)需要，找到所需模塊，裝入，鏈接，再執(zhí)行。需要動態(tài)重定位的支持裝入模塊并不包含所有目標(biāo)模塊由系統(tǒng)裝入程序在裝入同時找到需要的其它模塊，并鏈接B、裝入時動態(tài)鏈接15運(yùn)行時動態(tài)鏈接例printf( “ OK” );printf( “ OK” );主模塊庫模塊void printf()00裝入模塊void printf()編譯裝入printf( “ OK” );執(zhí)行33600Hcall 33600H

6、運(yùn)行時動態(tài)鏈接內(nèi)存162.4.2 連續(xù)分配存儲管理特點(diǎn)：為一個用戶程序分配一個連續(xù)的內(nèi)存空間程序空間本來就是連續(xù)的用連續(xù)的內(nèi)存裝入連續(xù)的程序，減少管理工作的難度可分為：單一連續(xù)區(qū)存儲管理分區(qū)存儲管理17單一連續(xù)區(qū)存儲管理內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。最簡單，適用于單用戶、單任務(wù)的OS。優(yōu)點(diǎn)：易于管理。缺點(diǎn)：對要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，很少使用的程序部分也占用內(nèi)存。18分區(qū)存儲管理把內(nèi)存分為一些大小相等或不等的分區(qū)(partition)，每個應(yīng)用進(jìn)程占用一個或幾個分區(qū)；操作系統(tǒng)占用其中一個分區(qū)。特點(diǎn)：適用于多道程序系統(tǒng)和分時

7、系統(tǒng)支持多個程序并發(fā)執(zhí)行可能存在內(nèi)零頭（分配給用戶但沒有被使用的空間）和外零頭（沒有分配但無法分配的空間）按不同分配方式，分為：固定分區(qū)可變分區(qū)19一、固定分區(qū)基本思想：將內(nèi)存區(qū)固定地劃分為大小相等或者不等的區(qū)域，每個分區(qū)裝入一道作業(yè)。分區(qū)劃分后，每個分區(qū)的長度和內(nèi)存中的分區(qū)總數(shù)將保持不變。內(nèi)存分配表分區(qū)號大小起始地址狀態(tài)14K0000H未分配28K4000H已分配312K12000H未分配20固定分區(qū)(大小相同)固定分區(qū)(多種大小)優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。缺點(diǎn)：內(nèi)零頭造成浪費(fèi)分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目21二、可變分區(qū)（動態(tài)分區(qū)）基本思想：根據(jù)作業(yè)任務(wù)的大小劃分分區(qū)，分區(qū)的大小和數(shù)

8、目不再固定。分配區(qū)控制塊空閑區(qū)控制塊AMCB (Allocation Memory Control Block)FMCB (Free Memory Control Block)22分配過程：10 K作業(yè) 1作業(yè) 2作業(yè) 3作業(yè) 12 K作業(yè) 21 K作業(yè) 34 K作業(yè) 1作業(yè) 3作業(yè) 4作業(yè) 43 K23分配算法（空白分區(qū)選擇）1、首次適應(yīng)FF ( First Fit )（1）將空白分區(qū)按地址遞增順序鏈接（2）從鏈?zhǔn)组_始查找適合的分區(qū)優(yōu)先分配內(nèi)存中低地址部分優(yōu)點(diǎn)：缺點(diǎn)：簡單在低地址部分會積累大量外零頭（3）從選中的分區(qū)中分出所需的大小，其余部分仍留在空白分區(qū)鏈表里24選取最適合的空白分區(qū)大分區(qū)

9、保證缺點(diǎn)：優(yōu)點(diǎn)：效率不高零頭更小（1）將空白分區(qū)按大小遞增順序鏈接（2）從鏈?zhǔn)组_始查找適合的分區(qū)2、最佳適應(yīng)BF ( Best Fit )253、最壞適應(yīng)WF ( Worst Fit )？選取分區(qū)中最大的一個最不適合的（1）將空白分區(qū)按大小遞減順序鏈接（2）從鏈?zhǔn)组_始分配分區(qū)優(yōu)點(diǎn)：查找效率顯著提高，一次就找到缺點(diǎn)：大作業(yè)容納能力會下降26“拼接”/“緊縮”技術(shù)多次分配、回收后，形成小空閑區(qū)無法使用。這時需要使用拼接或緊縮技術(shù)將已分配分區(qū)移動，使未分配分區(qū)合成較大分區(qū)。對占用分區(qū)進(jìn)行內(nèi)存數(shù)據(jù)搬移占用CPU時間如果對占用分區(qū)中的程序進(jìn)行浮動，則其重定位需要硬件支持。緊縮時機(jī)：每個分區(qū)釋放后，或內(nèi)存

10、分配找不到滿足條件的空閑分區(qū)時。272.4.3 覆蓋與交換技術(shù)引入原因：在分區(qū)管理技術(shù)中，程序的地址空間（邏輯地址空間）可能大于實(shí)際存儲器空間，使程序無法裝入（無法運(yùn)行）。覆蓋（Overlay）交換（S）28一、覆蓋（Overlay）一段內(nèi)存區(qū)可以先后被不同的程序段重復(fù)使用常駐區(qū)（非覆蓋區(qū)）覆蓋區(qū)初始段處理段輸出段程序員必須自己設(shè)計(jì)覆蓋結(jié)構(gòu)覆蓋斷劃分困難，不易實(shí)現(xiàn)29二、交換（S）在內(nèi)、外存之間進(jìn)行數(shù)據(jù)和程序的交換內(nèi) 存磁 盤交換技術(shù)一般與分區(qū)、分頁、分段管理技術(shù)結(jié)合使用。302.4.4 分頁存儲管理連續(xù)分配方式要求連續(xù)存放，產(chǎn)生大量的內(nèi)/外零頭，浪費(fèi)空間。引入離散分配方式程序在內(nèi)存中不一定連

11、續(xù)存放頁塊邏輯地址物理地址非連續(xù)地址映射31一、分頁管理的基本思想頁：將邏輯地址空間劃分為大小相同的塊，稱為頁或虛頁面（Page）塊：將實(shí)際物理空間劃分為與頁大小相等的塊，稱為存儲塊或頁框（Page Frame）沒有外零頭，僅有小于一個頁面的內(nèi)零頭優(yōu)點(diǎn):一個塊可以裝入一頁邏輯地址連續(xù)的頁可以通過地址變換機(jī)構(gòu)映射到不連續(xù)的內(nèi)存塊中32二、分頁管理的基本方法關(guān)鍵問題：如何實(shí)現(xiàn)頁到塊的地址變換？通過頁表實(shí)現(xiàn)。012m內(nèi)存012n用戶程序012n012n3m-21m-1頁表頁號塊號33頁面地址轉(zhuǎn)換頁面地址轉(zhuǎn)換通過下述3種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：（1）存儲分塊表（MBT）整個系統(tǒng)一個，記錄所有內(nèi)存塊的狀況。塊號作

12、業(yè)ID狀態(tài)01nOS作業(yè)1作業(yè)n忙閑忙34（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è)的頁表情況。35頁面地址到物理地址轉(zhuǎn)換過程：(1) 作業(yè)被調(diào)度時首先通過JT找到相應(yīng)頁表的起始地址及大小，并裝入PTCR(2)將頁號與PTCR中的頁表大小進(jìn)行比較，若頁號頁表大小則為非法訪問，產(chǎn)生越界中斷；否則為合法訪問，根據(jù)頁表起始地址和頁號找到該頁頁表表項(xiàng)(3)通過頁表表項(xiàng)找到邏

13、輯頁所對應(yīng)的物理塊號，然后將塊號與頁內(nèi)偏移地址結(jié)合形成物理地址36頁表始址頁表大小PTCR +塊號塊內(nèi)地址物理地址寄存器頁號頁內(nèi)地址邏輯地址寄存器越界？頁號塊號J1的頁表2404010作業(yè)號頁表大小頁表始址狀態(tài)J020已分配J1161024已分配JT21037 例：設(shè)塊大小為32，利用下面的頁表，將邏輯地址140變換為物理地址。解：1）邏輯地址有效地址頁號INT140/324頁內(nèi)地址140%32122）查頁表得到塊號為53）物理地址532+12172頁號塊號0617223445510382. 快表問題引入：兩次內(nèi)存訪問訪問頁表得到物理地址訪問物理地址得到數(shù)據(jù)快表：用于存放當(dāng)前頁表中最頻繁訪問表

14、項(xiàng)的高速緩存(Cache)?；诳毂淼姆猪撓到y(tǒng)：先查找快表，未成功再查找頁表（p.132 圖2.34）393.請求式分頁屬于虛擬存儲管理：部分裝入、請求調(diào)入、頁面置換需要的頁面是否已裝入內(nèi)存？當(dāng)需要訪問的頁面不在內(nèi)存中如何處理？當(dāng)發(fā)現(xiàn)將要用到的頁面不在主存中時產(chǎn)生缺頁中斷，由缺頁中斷來完成頁面的調(diào)入缺頁中斷將耗費(fèi)系統(tǒng)時間，缺頁率是影響系統(tǒng)性能的主要因素缺頁率：需要訪問的頁面不在內(nèi)存中次數(shù)在總頁面訪問次數(shù)的比率40如果要訪問的頁不在內(nèi)存中缺頁中斷處理頁號塊號存取控制狀態(tài)位引用位修改位外存地址引用位：0 未訪問過1 訪問過對頁表擴(kuò)充：讓系統(tǒng)了解頁面狀態(tài)修改位：0 未修改1 已修改過狀態(tài)位：0 不在

15、內(nèi)存1 在內(nèi)存41缺頁中斷的處理過程 ：相對地址頁號頁內(nèi)地址頁表始址頁表大小頁表控制寄存器+塊號塊內(nèi)地址物理地址寄存器邏輯地址寄存器越界？頁號塊號頁表狀態(tài)位缺頁中斷21503016042頁面淘汰算法若缺頁中斷處理時內(nèi)存已無空閑分塊？頁面置換(頁面淘汰)頁面淘汰算法抖動Thrashing頻繁地調(diào)進(jìn)和調(diào)出頁面，特別是被換出的頁面在短時間內(nèi)又要被換入，系統(tǒng)開銷顯著增加，以至于系統(tǒng)吞吐量大大下降43（1） FIFO算法 先進(jìn)先出算法最簡單的算法（2） LRU算法 最近最久不用頁面被淘汰（3） LFU算法 最近最少使用頁面被淘汰常用頁面淘汰算法：445. 分頁式存儲管理特點(diǎn)3重定位方便2保護(hù)功能好1存儲

16、效率高4易于共享5開銷稍微偏大452.4.5 分段存儲管理引入原因：按頁劃分程序的模塊化矛盾以段為內(nèi)存分配單位優(yōu)點(diǎn)：方便程序設(shè)計(jì)，便于內(nèi)存共享、保護(hù)、動態(tài)裝入。46分段實(shí)現(xiàn)思想作業(yè)按邏輯信息的完整性分段，段有段名和段號；段長度由程序決定，可動態(tài)延伸；各段都是從0開始編址的連續(xù)地址空間（二維）一個段是連續(xù)的，各段可以離散存放；472. 分段的地址轉(zhuǎn)換段表：每進(jìn)程一個，記錄進(jìn)程內(nèi)段與內(nèi)存實(shí)際段存放基地址的映射關(guān)系。段號段長02k11k240k主存始址1004000存取控制增補(bǔ)位010RWRW特征位110修改位100段表（ST）示意圖48地址變換機(jī)構(gòu)和過程：段表始址段表大小段表寄存器（JT）+物理地

17、址寄存器越界？段號基址段表4100段號邏輯地址寄存器段內(nèi)地址+絕對地址493. 段的共享與保護(hù)段的共享： 段表中同一起始地址段的保護(hù)：地址越界保護(hù)存取控制保護(hù)50分段方式的內(nèi)存共享共享段表段號基址進(jìn)程1段表進(jìn)程2段表段名1256始址內(nèi)存共享進(jìn)程數(shù)記錄共享段和進(jìn)程的信息，以便共享段的分配和回收514. 分段與分頁的比較（1）“分頁”是系統(tǒng)活動，用戶無法介入，頁的大小固定“分段”是用戶可見的，段大小可變（2）頁式信息的物理單位，不是完整的邏輯單位段是完整的邏輯信息單位（3）分頁的作業(yè)空間是一維的，是單一線性空間分段的作業(yè)空間是二維的。522.4.6 段頁式管理技術(shù)引入原因：分頁的優(yōu)點(diǎn)：分段的優(yōu)點(diǎn)：

18、存儲器利用率高符合程序的模塊結(jié)構(gòu)+段頁式存儲管理53段頁式實(shí)現(xiàn)思想有效地址 =段名段內(nèi)地址段內(nèi)頁號+頁內(nèi)地址用戶程序分段，段內(nèi)分頁（系統(tǒng)自動）系統(tǒng)內(nèi)存分塊（系統(tǒng)自動）每塊裝入一頁，各塊之間可以不連續(xù)123542. 段頁式地址轉(zhuǎn)換機(jī)構(gòu)段表 頁表實(shí)現(xiàn)地址轉(zhuǎn)換段表：記錄每一段段內(nèi)頁表地址240段號頁表長頁表始址段長段內(nèi)頁表頁號塊號0211頁號塊號01019220553. 段頁式地址轉(zhuǎn)換過程+物理地址寄存器邏輯地址段號段內(nèi)地址頁號頁內(nèi)地址段表始址段表大小段表寄存器段號頁表始址段表頁號塊號頁表塊號塊內(nèi)地址+！段頁式也可引入快表564. 段頁式的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：缺點(diǎn)：結(jié)合了分頁和分段的優(yōu)點(diǎn)，既有效利用了存儲器

19、，也符合邏輯習(xí)慣，便于保護(hù)、共享。由于程序分段，段內(nèi)分頁，造成地址轉(zhuǎn)換速度降低，系統(tǒng)結(jié)構(gòu)復(fù)雜。57Windows 的存儲管理NT使用的頁面大小為4KB（212）。每個NT進(jìn)程地址空間為4GB（232），其中：用戶存儲區(qū)：在用戶態(tài)和核心態(tài)都可訪問的用戶存儲區(qū)為2GB；用戶存儲區(qū)為頁交換區(qū)，可對換到外存；用戶存儲區(qū)的內(nèi)容包括：專用進(jìn)程地址空間：用戶代碼、數(shù)據(jù)和堆棧；線程環(huán)境塊（TEB）：用戶態(tài)代碼可修改的線程控制信息；進(jìn)程環(huán)境塊（PEB）：用戶態(tài)代碼可修改的進(jìn)程控制信息；共享用戶數(shù)據(jù)頁：系統(tǒng)存儲區(qū)映像，為用戶態(tài)可訪問的系統(tǒng)空間，目的在于避免用戶態(tài)與核心態(tài)的頻繁切換；如：系統(tǒng)時間。58有效狀態(tài)(active or valid)：某進(jìn)程正在使用該頁面，也可能不屬于任何進(jìn)程(如不可對換的內(nèi)核頁面)；過渡狀態(tài)(transition)：頁面處于不屬于任何進(jìn)程的過渡狀態(tài)，用于避免頁面沖突。如正在進(jìn)行頁面與I/O設(shè)備間的數(shù)據(jù)傳送。清零狀態(tài)(zeroed)：空閑且已被清零；空閑狀態(tài)(free)：空閑但尚未被清零；修改狀態(tài)(modified)：已標(biāo)記為無效，但對該頁面內(nèi)容的修改尚未寫入外存，可快