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

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

?。╢etch）

放（placement）

替換（replacement）請(qǐng)調(diào)、預(yù)調(diào)連續(xù)、不連續(xù)35.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界地址寄存器主存A＞acputruefalse地址A終止程序運(yùn)行越界檢查機(jī)構(gòu)：用戶程序每訪問(wèn)一次主存，越界檢查機(jī)構(gòu)將訪問(wèn)的地址與界地址寄存器中的值比較。若越界，則終止其執(zhí)行。5BCEDF

(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注意：(i)每次僅放入作業(yè)的一個(gè)部分(ii)覆蓋結(jié)構(gòu)需由程序員事先確定(iii)可與其內(nèi)存分配方法結(jié)合使用缺點(diǎn)：對(duì)用戶不透明，增加了用戶負(fù)擔(dān)。8YN按換入算法在外存查找換入進(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交換要花費(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

覆蓋與交換的區(qū)別:覆蓋由用戶解決空間不足，要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)。交換由系統(tǒng)解決空間不足。交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)，且只能覆蓋那些與覆蓋段無(wú)關(guān)的程序段。12特點(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)重定位用戶空間13CPU主存下界寄存器上界寄存器><TT地址A程序性異常1.上下界寄存器和地址檢查機(jī)構(gòu)。當(dāng)作業(yè)被調(diào)度運(yùn)行時(shí)，作業(yè)在內(nèi)存中的上下界地址送上下界寄存器，每次內(nèi)存訪問(wèn)時(shí)，地址檢查機(jī)構(gòu)作越界檢查。作業(yè)程序須是絕對(duì)地址或靜態(tài)可浮動(dòng)的。地址訪問(wèn)保護(hù)有兩種方式：FF14操作系統(tǒng)長(zhǎng)度基址位移量或偏移量?jī)蓚€(gè)概念：基址寄存器長(zhǎng)度寄存器2.基址寄存器、長(zhǎng)度寄存器和動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)。15二、作業(yè)調(diào)度OS4k6k12kOS4k6k12k...7k3k4k5k...3k4k1k2k...5k6k...7k10k11k8k多隊(duì)列法單隊(duì)列法17三、存儲(chǔ)碎片

存儲(chǔ)碎片：未得到利用的空間，有兩種類型：1)內(nèi)部碎片：內(nèi)存某存儲(chǔ)區(qū)間大于其存放作業(yè)空間的部分2)外部碎片：內(nèi)存某存儲(chǔ)區(qū)間容不下要運(yùn)行的作業(yè)時(shí)。OS12KB4KB3KB內(nèi)部碎片OS4KB6KB12KB作業(yè)長(zhǎng)度：5KB，8KB，12KB外部碎片18一、管理方法5.1.3多道連續(xù)可變分區(qū)法特點(diǎn)：多道、連續(xù)、但不固定劃分內(nèi)存。

系統(tǒng)設(shè)置一個(gè)張表，用于登記用戶區(qū)域中未占用的空閑塊。作業(yè)到達(dá)后，即可在空閑塊中分配空間。20舉例：假設(shè)任一時(shí)間段內(nèi)，內(nèi)存中每一作業(yè)獲得CPU時(shí)間相等。作業(yè)到來(lái)次序所需存儲(chǔ)量運(yùn)行時(shí)間160KB10s2100KB5s330KB20s470KB8s550KB15sOS040256J1J2J3J4J521（1）分配存儲(chǔ)空間假設(shè)F是空閑塊集合;size(k)為塊k的大小;size(v)為用戶所需空間，則分配算法可表示為：1.如果所有屬于F的k，均有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（2）分配策略

1、首次滿足(FirstFit)法：最好且最快的算法；2、最佳滿足(BestFit)法；3、最大滿足(WorstFit)法；23例子：設(shè)系統(tǒng)空閑鏈表為指針7k3k10k8k20k5kabcdef用戶先后申請(qǐng)7.5k，4k，最小剩余空間size=0.3，試用3種算法，求出分配塊。24首次滿足法:c,a3k3k2.5k8k20k5kabcdef指針7k3k10k8k20k5kabcdef先后申請(qǐng)7.5k，4k2512.5k10k8k7k5k3kecdafb最大:e,e20k10k8k7k5k3kecdafb指針7k3k10k8k20k5kabcdef先后申請(qǐng)7.5k，4k8.5k10k8k7k5k3kecdafb27僅下相鄰區(qū)都為空閑區(qū)僅上相鄰區(qū)都為空閑區(qū)查找鏈表，找到相應(yīng)記錄進(jìn)程使用內(nèi)存的節(jié)點(diǎn)分四種情況回收空間合并上下相鄰區(qū)和回收區(qū)，即修改相應(yīng)參數(shù)，刪除相應(yīng)表項(xiàng)和指針?；厥諈^(qū)與上相鄰區(qū)合并，即修改相應(yīng)參數(shù)?；厥諈^(qū)與下相鄰區(qū)合并，即修改相應(yīng)參數(shù)，回收該節(jié)點(diǎn)，即修改有關(guān)參數(shù)回收結(jié)束上下相鄰區(qū)都為空閑區(qū)直接插入該回收區(qū)兩相鄰區(qū)都不為空閑區(qū)（3）回收合并有四種方式。28緊致：通過(guò)移動(dòng)作業(yè)位置可以將零散的空閑塊連接成大塊。要求作業(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）鏈表303種方法的比較：31一、空間安排

用戶進(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分配：初始時(shí)，所有頁(yè)幀都在空閑隊(duì)列中，當(dāng)用戶進(jìn)程被創(chuàng)建時(shí)，系統(tǒng)按需要量從空閑隊(duì)列獲得相應(yīng)量的頁(yè)幀。頁(yè)幀進(jìn)程頁(yè)頁(yè)幀進(jìn)程頁(yè)釋放分配回收：33二、動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)因頁(yè)式方法中邏輯地址與物理地址之間失去自然聯(lián)系，故要通過(guò)頁(yè)表，并由硬件動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)將邏輯地址映射成物理地址才能正確訪存。3418530498765432103210邏輯空間物理空間頁(yè)表

(一)頁(yè)表

頁(yè)號(hào)頁(yè)表放在系統(tǒng)空間的頁(yè)表區(qū)，存放邏輯頁(yè)與物理頁(yè)幀的對(duì)應(yīng)關(guān)系。PCB表中有指針指向頁(yè)表。35(二)地址結(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例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例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(三)頁(yè)面大小的考慮P=LA/頁(yè)面大小，d=LA-P*頁(yè)面大小頁(yè)表始地f邏輯地址LAf*頁(yè)面大小++物理地址PA一般方法：39頁(yè)面大小的選擇：將頁(yè)面大小取成2的k次冪(k是正整數(shù)),獲取p和d的除法或乘法只要通過(guò)位移實(shí)現(xiàn)。頁(yè)面大小為2的k次冪的地址轉(zhuǎn)換原理如下：一般情況，頁(yè)面大小為512，1024，2048，4096Pd頁(yè)表始地fn

k-1 0fdn

k-1 0+頁(yè)表402452頁(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(四)快表（聯(lián)想存儲(chǔ)器，高速存儲(chǔ)體）頁(yè)面大小為2k的缺點(diǎn)：要查表，兩次訪問(wèn)主存，使程序速度下降一半。解決辦法：快表(快速存儲(chǔ)器)快表：一種高速存儲(chǔ)體，每一項(xiàng)由兩步分組成：關(guān)鍵字和值；還有一個(gè)比較裝置。具體方法：當(dāng)信息到達(dá)后，與關(guān)鍵字進(jìn)行比較，匹配成功則輸出該項(xiàng)值，否則輸出一個(gè)特殊符號(hào)表示匹配不成功。42轉(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優(yōu)點(diǎn)：訪問(wèn)時(shí)間短，接近一次訪問(wèn)主存的時(shí)間缺點(diǎn)：昂貴；快表匹配成功嗎形成物理地址到主存頁(yè)表中查找形成物理地址yesno解決辦法：只放一部分頁(yè)表項(xiàng)；轉(zhuǎn)換過(guò)程為：44地址轉(zhuǎn)換的一般過(guò)程：(聯(lián)想存儲(chǔ)器可以看成是頁(yè)表的cache)Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfmf頁(yè)表始地+頁(yè)表快表45快表（聯(lián)想存儲(chǔ)器）的地址變換過(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)想存儲(chǔ)器46實(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)?shù)奶鎿Q策略，在快表中匹配成功的可能性可達(dá)80%～90%。等效訪問(wèn)時(shí)間：設(shè)訪存時(shí)間為750ns，搜索快表的時(shí)間為50ns，命中率為80%，則：80%×(750+50)+20%×(750+50+750）＝950ns4748三、可用空間管理可用數(shù)組或空閑頁(yè)幀鏈來(lái)管理可用頁(yè)幀，工作如下：若可用頁(yè)幀總數(shù)小于作業(yè)總頁(yè)數(shù)，則拒絕分配取作業(yè)的下一頁(yè)P(yáng)，分配一可用頁(yè)幀f，并將p的內(nèi)容抄到f中去；將f抄到頁(yè)P(yáng)的頁(yè)表中；若所有頁(yè)表已