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

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

?。╢etch）

放（placement）

替換（replacement）請調(diào)、預(yù)調(diào)連續(xù)、不連續(xù)35.1連續(xù)空間分配特點：易理解，訪問率高，空間利用率低。5.1.1單道連續(xù)分配特點：任一時刻內(nèi)存只有一道作業(yè)，該作業(yè)連續(xù)存放于內(nèi)存中。一、管理方法0內(nèi)存空間安排操作系統(tǒng)用戶程序aa+1n界地址寄存器4界地址寄存器主存A＞acputruefalse地址A終止程序運行越界檢查機構(gòu)：用戶程序每訪問一次主存，越界檢查機構(gòu)將訪問的地址與界地址寄存器中的值比較。若越界，則終止其執(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覆蓋段編號用(i,j)表征i指覆蓋段號j覆蓋段中的覆蓋號E覆蓋D7注意：(i)每次僅放入作業(yè)的一個部分(ii)覆蓋結(jié)構(gòu)需由程序員事先確定(iii)可與其內(nèi)存分配方法結(jié)合使用缺點：對用戶不透明，增加了用戶負(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交換要花費較長的時間：如：輔存采用磁鼓，平均延遲時間為8ms，傳輸速度為250000B/s，用戶空間為20KB，則一次交換活動需要時間至少為：2×(8+103×20KB/250000)=179ms交換時機：在進(jìn)行I/O活動時不能進(jìn)行交換，但如果開辟了I/O緩沖區(qū)就例外11

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

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

系統(tǒng)設(shè)置一個張表，用于登記用戶區(qū)域中未占用的空閑塊。作業(yè)到達(dá)后，即可在空閑塊中分配空間。20舉例：假設(shè)任一時間段內(nèi)，內(nèi)存中每一作業(yè)獲得CPU時間相等。作業(yè)到來次序所需存儲量運行時間160KB10s2100KB5s330KB20s470KB8s550KB15sOS040256J1J2J3J4J521（1）分配存儲空間假設(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用戶先后申請7.5k，4k，最小剩余空間size=0.3，試用3種算法，求出分配塊。24首次滿足法:c,a3k3k2.5k8k20k5kabcdef指針7k3k10k8k20k5kabcdef先后申請7.5k，4k2512.5k10k8k7k5k3kecdafb最大:e,e20k10k8k7k5k3kecdafb指針7k3k10k8k20k5kabcdef先后申請7.5k，4k8.5k10k8k7k5k3kecdafb27僅下相鄰區(qū)都為空閑區(qū)僅上相鄰區(qū)都為空閑區(qū)查找鏈表，找到相應(yīng)記錄進(jìn)程使用內(nèi)存的節(jié)點分四種情況回收空間合并上下相鄰區(qū)和回收區(qū)，即修改相應(yīng)參數(shù)，刪除相應(yīng)表項和指針?；厥諈^(qū)與上相鄰區(qū)合并，即修改相應(yīng)參數(shù)。回收區(qū)與下相鄰區(qū)合并，即修改相應(yīng)參數(shù)，回收該節(jié)點，即修改有關(guān)參數(shù)回收結(jié)束上下相鄰區(qū)都為空閑區(qū)直接插入該回收區(qū)兩相鄰區(qū)都不為空閑區(qū)（3）回收合并有四種方式。28緊致：通過移動作業(yè)位置可以將零散的空閑塊連接成大塊。要求作業(yè)動態(tài)可浮動。Bitmap數(shù)組{1,1,1,0,0,1,0,0,0,0,1,0,0}321412空閑隊列頭二、可用空間管理（1）數(shù)組，數(shù)組項=用戶空間總量/基本分配單位。缺點：沒有內(nèi)部碎片，但有外部碎片（2）鏈表303種方法的比較：31一、空間安排

用戶進(jìn)程空間(地址)叫邏輯空間(地址);

內(nèi)存空間(地址)叫物理空間(地址);

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

(一)頁表

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

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

k-1 0fdn

k-1 0+頁表402452頁頁幀012238頁表長頁表始址8452實地址虛地址(頁)d(偏移)P(頁)9k8644…設(shè)內(nèi)存頁幀大小為1024字節(jié)，即1K。則物理地址＝8×1024＋452＝8644地址轉(zhuǎn)換實例:頁表41(四)快表（聯(lián)想存儲器，高速存儲體）頁面大小為2k的缺點：要查表，兩次訪問主存，使程序速度下降一半。解決辦法：快表(快速存儲器)快表：一種高速存儲體，每一項由兩步分組成：關(guān)鍵字和值；還有一個比較裝置。具體方法：當(dāng)信息到達(dá)后，與關(guān)鍵字進(jìn)行比較，匹配成功則輸出該項值，否則輸出一個特殊符號表示匹配不成功。42轉(zhuǎn)換原理:將頁表存入快表的地址，頁號設(shè)為關(guān)鍵字，頁幀號為值，其轉(zhuǎn)換原理如下：Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfm關(guān)鍵字值43優(yōu)點：訪問時間短，接近一次訪問主存的時間缺點：昂貴；快表匹配成功嗎形成物理地址到主存頁表中查找形成物理地址yesno解決辦法：只放一部分頁表項；轉(zhuǎn)換過程為：44地址轉(zhuǎn)換的一般過程：(聯(lián)想存儲器可以看成是頁表的cache)Pdn

k-1 0fdn

k-1 0P2f2P1f1......Pf......Pmfmf頁表始地+頁表快表45快表（聯(lián)想存儲器）的地址變換過程頁表始址B頁表長度L3>L?+頁表寄存器越界中斷邏輯地址V＝（3，d）頁框號頁面號物理地址頁表2648…0123…是否（8，d）A0A2A1A30頁框號123456789…偏移d查快表否是讀快表頁號聯(lián)想存儲器46實現(xiàn)方法：在進(jìn)程被調(diào)度占用CPU時，將進(jìn)程頁表始址裝入頁表始地址寄存器，同時用新的頁表內(nèi)容替換快表中的原內(nèi)容。命中率：選用8～12項組成的快表，并采用適當(dāng)?shù)奶鎿Q策略，在快表中匹配成功的可能性可達(dá)80%～90%。等效訪問時間：設(shè)訪存時間為750ns，搜索快表的時間為50ns，命中率為80%，則：80%×(750+50)+20%×(750+50+750）＝950ns4748三、可用空間管理可用數(shù)組或空閑頁幀鏈來管理可用頁幀，工作如下：若可用頁幀總數(shù)小于作業(yè)總頁數(shù)，則拒絕分配取作業(yè)的下一頁P，分配一可用頁幀f，并將p的內(nèi)容抄到f中去；將f抄到頁P的頁表中；若所有頁表已