操作系統(tǒng)存儲(chǔ)管理設(shè)備管理文件系統(tǒng)知識(shí)點(diǎn)介紹

第5章存放管理主要內(nèi)容：連續(xù)空間分配，覆蓋與交換技術(shù)，頁(yè)式管理，段式管理，段頁(yè)式存放管理，虛存管理。重點(diǎn)：多道固定劃分法，頁(yè)式管理，請(qǐng)求頁(yè)式存放管理。難點(diǎn)：覆蓋與交換技術(shù)，頁(yè)面替換策略1第1頁(yè)高速緩存(cache)主存輔存CPU幾百k~nM幾百M(fèi)~nGnG~nTcache—主存主存—輔存存放層次結(jié)構(gòu)：2第2頁(yè)研究三方面問(wèn)題：

?。╢etch）放（placement）替換（replacement）請(qǐng)調(diào)、預(yù)調(diào)連續(xù)、不連續(xù)3第3頁(yè)5.1連續(xù)空間分配特點(diǎn)：易了解，訪問(wèn)率高，空間利用率低。5.1.1單道連續(xù)分配特點(diǎn)：任一時(shí)刻內(nèi)存只有一道作業(yè)，該作業(yè)連續(xù)存放于內(nèi)存中。一、管理方法0內(nèi)存空間安排操作系統(tǒng)用戶程序aa+1n界地址存放器4第4頁(yè)界地址存放器主存A＞acputruefalse地址A終止程序運(yùn)行越界檢驗(yàn)機(jī)構(gòu)：用戶程序每訪問(wèn)一次主存，越界檢驗(yàn)機(jī)構(gòu)將訪問(wèn)地址與界地址存放器中值比較。若越界，則終止其執(zhí)行。5第5頁(yè)二、覆蓋（overlay）

操作系統(tǒng)固定區(qū)(4k)覆蓋區(qū)0(6k)覆蓋區(qū)1(10k)A(4k)E(10k)D(6k)C(4k)B(6k)F(8k)引入原因：因內(nèi)存小于作業(yè)程序空間。基本思想：將用戶空間劃分成一個(gè)固定區(qū)和多個(gè)覆蓋區(qū)。主程序放固定區(qū)，依次調(diào)用子程序則放在同一個(gè)覆蓋區(qū)。操作系統(tǒng)提供覆蓋系統(tǒng)調(diào)用函數(shù)，由用戶編程時(shí)考慮調(diào)用。6第6頁(yè)BCEDF

(0,0)(0,1)(1,0)(1,1)(1,2)D(6k)C(4k)A(4k)操作系統(tǒng)4k6k10kE(10k)C(4k)A(4k)操作系統(tǒng)4k6k10kDE覆蓋段編號(hào)用(i,j)表征i指覆蓋段號(hào)j覆蓋段中覆蓋號(hào)E覆蓋D7第7頁(yè)注意：(i)每次僅放入作業(yè)一個(gè)部分(ii)覆蓋結(jié)構(gòu)需由程序員事先確定(iii)可與其內(nèi)存分配方法結(jié)合使用缺點(diǎn)：對(duì)用戶不透明，增加了用戶負(fù)擔(dān)。8第8頁(yè)引入原因：采取時(shí)間片輪轉(zhuǎn)法或可剝奪調(diào)度基本思想：將處于等候狀態(tài)(等I/O)或就緒(等CPU)狀態(tài)進(jìn)程從主存換出到輔存，把將要執(zhí)行進(jìn)程移入主存。兩個(gè)概念：換出，換入。三、交換(Swapping)9第9頁(yè)YN按換入算法在外存查找換入進(jìn)程查到嗎？Y調(diào)用swapin(p)函數(shù)換入進(jìn)程換入成功？按換出算法尋找可換出進(jìn)程找到嗎？設(shè)置runout進(jìn)程睡眠sleep(&runin，PSWP)調(diào)用xswap函數(shù)換出指定進(jìn)程runin++進(jìn)程睡眠sleep(&runout，PSWP)NYN函數(shù)Sched流程圖10第10頁(yè)交換要花費(fèi)較長(zhǎng)時(shí)間：如：輔存采取磁鼓，平均延遲時(shí)間為8ms，傳輸速度為250000B/s，用戶空間為20KB，則一次交換活動(dòng)需要時(shí)間最少為：2×(8+103×20KB/250000)=179ms交換時(shí)機(jī)：在進(jìn)行I/O活動(dòng)時(shí)不能進(jìn)行交換，但假如開(kāi)辟了I/O緩沖區(qū)就例外11第11頁(yè)

覆蓋與交換區(qū)分:覆蓋由用戶處理空間不足，要求用戶給出程序段之間邏輯覆蓋結(jié)構(gòu)。交換由系統(tǒng)處理空間不足。交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)，且只能覆蓋那些與覆蓋段無(wú)關(guān)程序段。12第12頁(yè)特點(diǎn)：任一時(shí)刻內(nèi)存可有多道作業(yè)，每道作業(yè)連續(xù)存放于內(nèi)存。操作系統(tǒng)U1...Un5.1.2多道固定劃分區(qū)法一、管理方法將用戶內(nèi)存空間分成長(zhǎng)度固定若干塊。地址重定位：靜態(tài)重定位，動(dòng)態(tài)重定位用戶空間13第13頁(yè)CPU主存下界存放器上界存放器><TT地址A程序性異常1.上下界存放器和地址檢驗(yàn)機(jī)構(gòu)?？闯蓸I(yè)被調(diào)度運(yùn)行時(shí)，作業(yè)在內(nèi)存中上下界地址送上下界存放器，每次內(nèi)存訪問(wèn)時(shí)，地址檢驗(yàn)機(jī)構(gòu)作越界檢驗(yàn)。作業(yè)程序須是絕對(duì)地址或靜態(tài)可浮動(dòng)。地址訪問(wèn)保護(hù)有兩種方式：FF14第14頁(yè)操作系統(tǒng)長(zhǎng)度基址位移量或偏移量?jī)蓚€(gè)概念：基址存放器長(zhǎng)度存放器2.基址存放器、長(zhǎng)度存放器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。15第15頁(yè)2.基址存放器、長(zhǎng)度存放器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。CPU主存基地址存放器長(zhǎng)度存放器<+T地址AF 程序性中止16第16頁(yè)二、作業(yè)調(diào)度OS4k6k12kOS4k6k12k...7k3k4k5k...3k4k1k2k...5k6k...7k10k11k8k多隊(duì)列法單隊(duì)列法17第17頁(yè)三、存放碎片

存放碎片：未得到利用空間，有兩種類型：1)內(nèi)部碎片：內(nèi)存某存放區(qū)間大于其存放作業(yè)空間部分2)外部碎片：內(nèi)存某存放區(qū)間容不下要運(yùn)行作業(yè)時(shí)。OS12KB4KB3KB內(nèi)部碎片OS4KB6KB12KB作業(yè)長(zhǎng)度：5KB，8KB，12KB外部碎片18第18頁(yè)4.特點(diǎn)每道程序占一個(gè)分區(qū)可放多道程序存在零頭（即存在內(nèi)部碎片和外部碎片）缺點(diǎn)：因?yàn)榇嬖谒槠档土酥鞔胬寐?，而且存在一個(gè)大作業(yè)找不到適當(dāng)存放區(qū)情況。19第19頁(yè)一、管理方法5.1.3多道連續(xù)可變分區(qū)法特點(diǎn)：多道、連續(xù)、但不固定劃分內(nèi)存。

系統(tǒng)設(shè)置一個(gè)張表，用于登記用戶區(qū)域中未占用空閑塊。作業(yè)抵達(dá)后，即可在空閑塊中分配空間。20第20頁(yè)舉例：假設(shè)任一時(shí)間段內(nèi)，內(nèi)存中每一作業(yè)取得CPU時(shí)間相等。作業(yè)到來(lái)次序所需存放量運(yùn)行時(shí)間160KB10s2100KB5s330KB20s470KB8s550KB15sOS040256J1J2J3J4J521第21頁(yè)（1）分配存放空間假設(shè)F是空閑塊集合;size(k)為塊k大小;size(v)為用戶所需空間，則分配算法可表示為：1.假如全部屬于Fk，都有size(k)<size(v),則失敗。2.不然按某一策略選出k，使得size(k)>size(v)3.F=F–{k};

4.假如size(k)-size(v)＜ε，則將k分給用戶。5.不然將k分成k1,k2，其中size(k1)=size(v)，F(xiàn)=F+{k2}22第22頁(yè)（2）分配策略

1、首次滿足(FirstFit)法：最好且最快算法；2、最正確滿足(BestFit)法；3、最大滿足(WorstFit)法；23第23頁(yè)例子：設(shè)系統(tǒng)空閑鏈表為指針7k3k10k8k20k5kabcdef用戶先后申請(qǐng)7.5k，4k，最小剩下空間size=0.3，試用3種算法，求出分配塊。24第24頁(yè)首次滿足法:c,a3k3k2.5k8k20k5kabcdef指針7k3k10k8k20k5kabcdef先后申請(qǐng)7.5k，4k25第25頁(yè)指針7k3k10k8k20k5kabcdefd,f最正確:3k5k7k8k10k20kbfadce0.5k3k5k7k10k20kdbface0.5k1k3k7k10k20kdbface先后申請(qǐng)7.5k，4k26第26頁(yè)12.5k10k8k7k5k3kecdafb最大:e,e20k10k8k7k5k3kecdafb指針7k3k10k8k20k5kabcdef先后申請(qǐng)7.5k，4k8.5k10k8k7k5k3kecdafb27第27頁(yè)僅下相鄰區(qū)都為空閑區(qū)僅上相鄰區(qū)都為空閑區(qū)查找鏈表，找到對(duì)應(yīng)統(tǒng)計(jì)進(jìn)程使用內(nèi)存節(jié)點(diǎn)分四種情況回收空間合并上下相鄰區(qū)和回收區(qū)，即修改對(duì)應(yīng)參數(shù)，刪除對(duì)應(yīng)表項(xiàng)和指針?；厥諈^(qū)與上相鄰區(qū)合并，即修改對(duì)應(yīng)參數(shù)?；厥諈^(qū)與下相鄰區(qū)合并，即修改對(duì)應(yīng)參數(shù)，回收該節(jié)點(diǎn)，即修改相關(guān)參數(shù)回收結(jié)束上下相鄰區(qū)都為空閑區(qū)直接插入該回收區(qū)兩相鄰區(qū)都不為空閑區(qū)（3）回收合并有四種方式。28第28頁(yè)4K內(nèi)存表作業(yè)空間合并6K內(nèi)存表4K2K內(nèi)存表4K2K6K內(nèi)存表分配資源釋放資源29第29頁(yè)緊致：經(jīng)過(guò)移動(dòng)作業(yè)位置能夠?qū)⒘闼榭臻e塊連接成大塊。要求作業(yè)動(dòng)態(tài)可浮動(dòng)。Bitmap數(shù)組{1,1,1,0,0,1,0,0,0,0,1,0,0}321412空閑隊(duì)列頭二、可用空間管理（1）數(shù)組，數(shù)組項(xiàng)=用戶空間總量/基本分配單位。缺點(diǎn)：沒(méi)有內(nèi)部碎片，但有外部碎片（2）鏈表30第30頁(yè)3種方法比較：31第31頁(yè)一、空間安排

用戶進(jìn)程空間(地址)叫邏輯空間(地址);內(nèi)存空間(地址)叫物理空間(地址);用相同長(zhǎng)度為單位對(duì)邏輯空間等分出每個(gè)區(qū)域叫頁(yè)，對(duì)物理空間等分出區(qū)域叫頁(yè)幀，輔存所劃出每個(gè)區(qū)域叫塊。5.2不連續(xù)空間分配5.2.1頁(yè)式管理特點(diǎn)：作業(yè)(進(jìn)程)分成頁(yè)面，內(nèi)存也劃分成頁(yè)面，將作業(yè)(進(jìn)程)頁(yè)面不連續(xù)地分布到內(nèi)存頁(yè)面。32第32頁(yè)分配：初始時(shí)，全部頁(yè)幀都在空閑隊(duì)列中，當(dāng)用戶進(jìn)程被創(chuàng)建時(shí)，系統(tǒng)按需要量從空閑隊(duì)列取得對(duì)應(yīng)量頁(yè)幀。頁(yè)幀進(jìn)程頁(yè)頁(yè)幀進(jìn)程頁(yè)釋放分配回收：33第33頁(yè)二、動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)因頁(yè)式方法中邏輯地址與物理地址之間失去自然聯(lián)絡(luò)，故要經(jīng)過(guò)頁(yè)表，并由硬件動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)將邏輯地址映射成物理地址才能正確訪存。34第34頁(yè)18530498765432103210邏輯空間物理空間頁(yè)表

(一)頁(yè)表

頁(yè)號(hào)頁(yè)表放在系統(tǒng)空間頁(yè)表區(qū)，存放邏輯頁(yè)與物理頁(yè)幀對(duì)應(yīng)關(guān)系。PCB表中有指針指向頁(yè)表。35第35頁(yè)(二)地址結(jié)構(gòu)

邏輯地址=(p(頁(yè)號(hào)),d(頁(yè)內(nèi)位移))物理地址=(f(頁(yè)幀號(hào)),d(頁(yè)內(nèi)位移))p=INT[線性邏輯地址A/頁(yè)面大小L]d=線性邏輯地址A–p×頁(yè)面大小L43210頁(yè)號(hào)36第36頁(yè)例1、設(shè)虛地址為8305，每頁(yè)為1KB，求頁(yè)號(hào)和頁(yè)內(nèi)地址。解：設(shè)線性邏輯地址(虛地址）為AA＝8305L＝1024頁(yè)號(hào)P=INT[A/L]=[8305/1024]=8頁(yè)內(nèi)地址d=A-P*L=8305-8*1024=11337第37頁(yè)例2：設(shè)虛地址為(357101)8，每頁(yè)為128，求頁(yè)號(hào)和頁(yè)內(nèi)地址。解：128＝27(邏輯地址低7位為頁(yè)內(nèi)位移)1 6 7 4 1 0 1偏移為(101)8,頁(yè)號(hào)為(1674)8(357101)8＝(011,101,111,001,000,001)2轉(zhuǎn)成十進(jìn)制：偏移為：(65)10,頁(yè)號(hào)為：1×83＋6×82＋7×8＋438第38頁(yè)(三)頁(yè)面大小考慮P=LA/頁(yè)面大小，d=LA-P*頁(yè)面大小頁(yè)表始地f邏輯地址LAf*頁(yè)面大小++物理地址PA普通方法：39第39頁(yè)頁(yè)面大小選擇：將頁(yè)面大小取成2k次冪(k是正整數(shù)),獲取p和d除法或乘法只要經(jīng)過(guò)位移實(shí)現(xiàn)。頁(yè)面大小為2k次冪地址轉(zhuǎn)換原理以下：普通情況，頁(yè)面大小為512，1024，2048，4096Pd頁(yè)表始地fn

k-1 0fdn

k-1 0+頁(yè)表40第40頁(yè)2452頁(yè)頁(yè)幀012238

頁(yè)表長(zhǎng)頁(yè)表始址8452實(shí)地址虛地址(頁(yè))d(偏移)P(頁(yè))9k8644…設(shè)內(nèi)存頁(yè)幀大小為1024字節(jié)，即1K。則物理地址＝8×1024＋452＝8644地址轉(zhuǎn)換實(shí)例:頁(yè)表41第41頁(yè)(四)快表（聯(lián)想存放器，高速存放體）頁(yè)面大小為2k缺點(diǎn)：要查表，兩次訪問(wèn)主存，使程序速度下降二分之一。處理方法：快表(快速存放器)快表：一個(gè)高速存放體，每一項(xiàng)由兩步分組成：關(guān)鍵字和值；還有一個(gè)比較裝置。詳細(xì)方法：當(dāng)信息抵達(dá)后，與關(guān)鍵字進(jìn)行比較，匹配成功則輸出該項(xiàng)值，不然輸出一個(gè)特殊符號(hào)表示匹配不成功。42第42頁(yè)轉(zhuǎn)換原理:將頁(yè)表存入快表地址，頁(yè)號(hào)設(shè)為關(guān)鍵字，頁(yè)幀號(hào)為值，其轉(zhuǎn)換原理以下：Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfm關(guān)鍵字值43第43頁(yè)優(yōu)點(diǎn)：訪問(wèn)時(shí)間短，靠近一次訪問(wèn)主存時(shí)間缺點(diǎn)：昂貴；快表匹配成功嗎形成物理地址到主存頁(yè)表中查找形成物理地址yesno處理方法：只放一部分頁(yè)表項(xiàng)；轉(zhuǎn)換過(guò)程為：44第44頁(yè)地址轉(zhuǎn)換普通過(guò)程：(聯(lián)想存放器能夠看成是頁(yè)表cache)Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfmf頁(yè)表始地+頁(yè)表快表45第45頁(yè)快表（聯(lián)想存放器）地址變換過(guò)程頁(yè)表始址B頁(yè)表長(zhǎng)度L3>L?+頁(yè)表存放器越界中止邏輯地址V＝（3，d）頁(yè)框號(hào)頁(yè)面號(hào)物理地址頁(yè)表2648…0123…是否（8，d）A0A2A1A30頁(yè)框號(hào)123456789…偏移d查快表否是讀快表頁(yè)號(hào)聯(lián)想存放器46第46頁(yè)實(shí)現(xiàn)方法：在進(jìn)程被調(diào)度占用CPU時(shí)，將進(jìn)程頁(yè)表始址裝入頁(yè)表始地址存放器，同時(shí)用新頁(yè)表內(nèi)容替換快表中原內(nèi)容。命中率：選取8～12項(xiàng)組成快表，并采取適當(dāng)替換策略，在快表中匹配成功可能性可達(dá)80%～90%。等效訪問(wèn)時(shí)間：設(shè)訪存時(shí)間為750ns，搜索快表時(shí)間為50ns，命中率為80%，則：80%×(750+50)+20%×(750+50+750）＝950ns47第47頁(yè)48第48頁(yè)三、可用空間管理可用數(shù)組或空閑頁(yè)幀鏈來(lái)管理可用頁(yè)幀，工作以下：若可用