第4章_存儲管理課件

1、第四章存儲管理Operating System第第4 4章章 存儲管理存儲管理第四章存儲管理Operating System4.1 概述4.2 重定位4.3 單用戶連續(xù)存儲管理4.4 固定分區(qū)存儲管理4.5 可變分區(qū)存儲管理4.6 頁式存儲管理4.7 虛擬存儲管理第四章存儲管理Operating System速度越快、容量速度越快、容量越小、價格越貴越小、價格越貴圖 計算機系統(tǒng)存儲層次示意 4.1 概述概述磁帶機磁帶機光盤存儲器光盤存儲器磁盤存儲器磁盤存儲器內(nèi)存儲器內(nèi)存儲器高速緩存高速緩存 寄存器寄存器第四章存儲管理Operating System4.1.1 信息的二級存儲信息的二級存儲輔存存

2、放準備運行的程序和數(shù)據(jù)當需要或內(nèi)存空間允許時，將程序和數(shù)據(jù)讀入內(nèi)存（課本P82頁圖4-1）第四章存儲管理Operating System4.1.2 4.1.2 存儲管理的功能存儲管理的功能（1）內(nèi)存空間的分配與回收 不同的存儲管理方式，采用的主存空間分配策略是不同的。 使用“主存空間分配表主存空間分配表”記錄主存空間的分配情況。（2）實現(xiàn)地址轉(zhuǎn)換 又稱地址重定位、地址映射 邏輯地址（相對地址，虛地址） 物理地址（絕對地址，實地址）第四章存儲管理Operating System（3）主存空間的共享與保護 多個作業(yè)共享主存儲器 多個作業(yè)共享某個主存區(qū)域 要實現(xiàn)共享，必須進行存儲保護（4）主存空間的

3、擴充 第四章存儲管理Operating System4.2 重定位重定位4.2.1 絕對地址和相對地址 絕對地址：主存空間的地址編號 與絕對地址對應(yīng)的主存空間稱為物理地址空間物理地址空間 相對地址：用戶程序中使用的地址 與相對地址對應(yīng)的存儲空間稱為邏輯地址空間邏輯地址空間把相對地址轉(zhuǎn)換成絕對地址的工作稱為“重定位”或“地址轉(zhuǎn)換”第四章存儲管理Operating System4.2.2 重定位的方式1、靜態(tài)重定位（課本P85頁圖4-2） 當用戶程序被裝入內(nèi)存時，一次性實現(xiàn)相對地址到絕對地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換。第四章存儲管理Operating System2、動態(tài)重定位（課本P85頁圖4-3）

4、-在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換 即在逐條指令執(zhí)行時完成地址映射。 （由硬件地址映射機制來完成。） -硬件上需要基址寄存器的支持 -支持“程序浮動”第四章存儲管理Operating System第四章存儲管理Operating System4.3 單用戶連續(xù)存儲管理單用戶連續(xù)存儲管理4.3.1 存儲空間的分配（課本P86頁圖4-4）-單用戶系統(tǒng)-內(nèi)存分為兩個區(qū)域(OS + 一個作業(yè))-在一段時間內(nèi)，只有一個作業(yè)在內(nèi)存-內(nèi)存分配管理十分簡單-處理器、內(nèi)存和外圍設(shè)備的利用率都低第四章存儲管理Operating System第四章存儲管理Operating System4.3.2 覆蓋技

5、術(shù)（課本P87圖4-5）如果作業(yè)的邏輯地址空間大于用戶區(qū)，如何把作業(yè)裝入主存？如果作業(yè)的邏輯地址空間大于用戶區(qū)，如何把作業(yè)裝入主存？首先：用戶把作業(yè)分成若干段（一個主段和多個其它段）然后：采用覆蓋技術(shù)控制作業(yè)的執(zhí)行 主段常駐內(nèi)存 其它段保留在磁盤上，需要時由OS裝入第四章存儲管理Operating System第四章存儲管理Operating System4.3.3 對換技術(shù) 分時系統(tǒng)中，可 用對換方式讓多個用戶的作業(yè)進入主存執(zhí)行。多個作業(yè)保存在大容量磁盤上；出現(xiàn)等待事件或時間片用完對換 （課本P88圖4-6）第四章存儲管理Operating System4.4 4.4 固定分區(qū)存儲管理固定分

6、區(qū)存儲管理4.4.1 基本原理 -預(yù)先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)域（分區(qū)） -每個分區(qū)的大小可以相同也可以不同 -系統(tǒng)中分區(qū)的數(shù)量和分區(qū)大小固定不變 -每個分區(qū)裝一個且只能裝一個作業(yè) -適用于多用戶系統(tǒng)（課本P89頁圖4-7）第四章存儲管理Operating System哪個分區(qū)已經(jīng)被作用占用，哪個分區(qū)是空閑的呢？哪個分區(qū)已經(jīng)被作用占用，哪個分區(qū)是空閑的呢？第四章存儲管理Operating System4.4.2 主存空間的分配與回收 -分區(qū)分配表：說明各個分區(qū)的分配和使用情況（課本P89頁表4-1） 假定作業(yè)隊列中有作業(yè)要裝入內(nèi)存？第四章存儲管理Operating System-內(nèi)

7、存分配算法：順序分配算法順序分配算法（課本P90頁圖4-8）-內(nèi)存回收：第四章存儲管理Operating System4.4.3 地址轉(zhuǎn)換和保護-地址轉(zhuǎn)換：作業(yè)執(zhí)行中不會被改變存放位置靜態(tài)重定位：-存儲保護：設(shè)置一對寄存器（下限和上限寄存器） 下限地址=絕對地址=上限地址第四章存儲管理Operating System4.5 4.5 可變分區(qū)存儲管理可變分區(qū)存儲管理基本原理:-內(nèi)存不是預(yù)先劃分好的-作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配-若有足夠的空間，則按需要分割一部分空間給該進程；否則令其等待內(nèi)存空間分區(qū)的長度和分區(qū)的數(shù)量都不固定.第四章存儲管理Operating Sy

8、stem 4.5.1 主存空間的分配與回收 1、分區(qū)的劃分 -分區(qū)的大小按照作業(yè)的需求量來定（課本P91頁圖4-9） -隨著作業(yè)不斷地被裝入和作業(yè)執(zhí)行結(jié)束后的撤離，主存空 間被分成許多分區(qū)。（課本P92頁圖4-10）第四章存儲管理Operating System第四章存儲管理Operating System第四章存儲管理Operating System2、主存空間的分配算法、主存空間的分配算法 1）分區(qū)分配表分區(qū)分配表包括兩張表：（課本P92頁圖4-11） 已分配區(qū)表 空閑區(qū)表 2）作業(yè)裝入內(nèi)存過程：1.裝入的作業(yè)=空閑區(qū)大小 2.裝入的作業(yè)空閑區(qū)大小第四章存儲管理Operating Syst

9、em主存分配算法主存分配算法（課本（課本P94P94頁圖頁圖4-124-12） （1）最先適應(yīng)分配算法 原理： -把空閑區(qū)按地址順序按地址順序從小到大登記在空閑區(qū)表中 -順序查找空閑區(qū)表，找到第一個第一個能滿足作業(yè)長度要求的 空閑區(qū)。優(yōu)點： -算法簡單 -高地址部分保持有較大的空閑區(qū)缺點： -容易形成碎片 -回收時需要按地址順序插入到空閑區(qū)的適當位置進 行登記。第四章存儲管理Operating System第四章存儲管理Operating System（2）最優(yōu)適應(yīng)分配算法 原理： -把空閑區(qū)容量容量以遞增遞增次序登記在空閑區(qū)表中 -從所有空閑區(qū)中挑選一個能滿足作業(yè)要求的最小空閑區(qū)。 優(yōu)點：避

10、免“大材小用” 缺點：會出現(xiàn)極小的空閑區(qū)無法利用第四章存儲管理Operating System第四章存儲管理Operating System（3）最壞適應(yīng)分配算法 原理： -空閑區(qū)表中的項目按空閑區(qū)長度遞減遞減排列 -查找空閑區(qū)表，挑選一個最大的空閑區(qū)分割一部分給作業(yè) 使用 -查找時只要看第一個分區(qū)能否滿足作業(yè)要求 優(yōu)點： -可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對 中、小作業(yè)有利 -查找效率很高。 缺點：會使存儲器中缺乏大的空閑分區(qū)。第四章存儲管理Operating System第四章存儲管理Operating System3. 3. 主存空間的回收算法主存空間的回收算法 當作業(yè)執(zhí)

11、行結(jié)束撤離后,應(yīng)回收主存空間,同時修改”已分配區(qū)表”和“空閑區(qū)表” 回收區(qū)與已存在的空閑區(qū)存在四種位置關(guān)系： -有上鄰空閑區(qū) -有下鄰空閑區(qū) -既有上鄰空閑區(qū)，又有下鄰空閑區(qū) -既無上鄰空閑區(qū)，又無下鄰空閑區(qū)第四章存儲管理Operating SystemF1回收區(qū)回收區(qū)F2F1回收區(qū)F2（a）（b）（c）回收分區(qū)與前面一個（低地址）空閑分區(qū)F1相鄰接，圖（a）回收分區(qū)與后面一個（高地址）空閑分區(qū)F2相鄰接，圖（b）回收分區(qū)與前、后兩個空閑分區(qū)F1和F2均相鄰，圖（c）回收分區(qū)不與其它空閑分區(qū)相鄰接 第四章存儲管理Operating System4.5.2 地址轉(zhuǎn)換與存儲保護 采用動態(tài)重定位動態(tài)

12、重定位方式裝入作業(yè) 硬件設(shè)置：基址和限長寄存器基址和限長寄存器 基址寄存器：作業(yè)所占分區(qū)的起始地址 限長寄存器：作業(yè)所占分區(qū)的最大地址 基址寄存器內(nèi)容=絕對地址=LB+頁號頁號P P 頁內(nèi)地址頁內(nèi)地址DPD絕對地址絕對地址頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器相對地址相對地址地址轉(zhuǎn)換地址轉(zhuǎn)換內(nèi)存塊號內(nèi)存塊號頁號頁號0P第四章存儲管理Operating System地址變換過程：1）分頁地址變換機構(gòu)會自動地將有效地址(相對地址)分為頁號和頁內(nèi)地址兩部分，再以頁號為索引去檢索頁表；2）在執(zhí)行檢索之前，先將頁號與頁表長度進行比較，如果頁號大于或等于頁表長度，則產(chǎn)生一地址越界中斷；3

13、）若未出現(xiàn)越界錯誤，則將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置，于是可從中得到該頁的物理塊號，將之裝入物理地址寄存器中；4）再將頁內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段中。第四章存儲管理Operating System 例：一個有3個頁面長的進程具有的邏輯頁面號為0、1、2，對應(yīng)的物理塊號為4、5、9，頁面長度為1K，指令為LOAD 2,2480的相對地址為200，如何進行相對地址到絕對地址的轉(zhuǎn)換？第四章存儲管理Operating System120第四章存儲管理Operating System2）具有快表的地址轉(zhuǎn)換塊表的引入： -普通地址轉(zhuǎn)換要兩次訪問內(nèi)存，增加了訪

14、問時間。 -引入塊表的目的就是減少訪問主存次數(shù)為了提高地址變換速度，可在地址變換機構(gòu)中增設(shè)一個具有并行查尋能力的特殊高速緩沖寄存器，又稱為“聯(lián)想寄存器”(Associative Memory)，或稱為“快表”，在IBM系統(tǒng)中又取名為TLB(Translation Lookaside Buffer)，用以存放當前訪問的那些頁表項。 第四章存儲管理Operating System圖 具有快表的地址變換機構(gòu) 頁表寄存器頁表始址頁表長度頁號頁內(nèi)地址邏輯地址L越界中斷塊號b頁表頁號頁號輸入寄存器塊號bb快表d物理地址第四章存儲管理Operating System地址變換過程：1）在CPU給出有效地址后，

15、由地址變換機構(gòu)自動地將頁號P送入塊表，并將此頁號與塊表中的所有頁號進行比較； 2）如在塊表中未找到對應(yīng)的頁表項，則還須再訪問內(nèi)存中的頁表，找到后，把從頁表項中讀出的物理塊號送地址寄存器；同時還需重新修改快表。3）但如果快表已滿，則OS必須找到一個老的且已被認為不再需要的頁表項，將它換出。第四章存儲管理Operating System 采用快表后，地址轉(zhuǎn)換時間大大下降： 假定訪問主存的時間為200納秒，訪問高速緩存的時間為40納秒，并且高速緩存為16個單元時，查快表的命中率可達90%。 用快表：用快表： T=(200+40)*90%+(200+200)*10%=256納秒 不用快表：不用快表：

16、T=200*2=400納秒第四章存儲管理Operating System優(yōu)點：優(yōu)點：（內(nèi)存利用率大大提高）（內(nèi)存利用率大大提高） 打破了程序和數(shù)據(jù)在內(nèi)存中的連續(xù)存放 (實現(xiàn)了離散分配方式） 內(nèi)存碎片大大減少缺點：缺點： 每個程序的最后一頁還有空間不能利用 不利于內(nèi)存代碼共享第四章存儲管理Operating System4.7 虛擬存儲管理虛擬存儲管理4.7.1 什么是虛擬存儲器 以往的存儲方式：當內(nèi)存空間不能滿足作業(yè)要求時，作業(yè)無法裝入內(nèi)存。 -作業(yè)部分裝入主存 好處：1）主存空間充分利用 2）用戶感覺計算機系統(tǒng)提供了容量很大的主存 （虛擬存儲器）第四章存儲管理Operating System

17、4.7.2 虛擬存儲器的工作原理 把作業(yè)信息保存在磁盤上，當要求裝入時，只將其中一部分先裝入主存，作業(yè)執(zhí)行過程中，若要訪問的信息不在主存中，則再設(shè)防把這些信息裝入主存。 在作業(yè)信息部分裝入主存的情況下，能否保證作業(yè)的正確執(zhí)行？（能） 1）程序執(zhí)行時，有些部分是互斥執(zhí)行的 2）程序的執(zhí)行具有局部性第四章存儲管理Operating System實現(xiàn)虛擬存儲要解決的三個關(guān)鍵問題：1）怎樣知道當前哪些信息已在主存，哪些尚未裝入2）如果要訪問的信息不在主存，怎樣找到這些信息并把他們裝入主存3）在把欲訪問的信息裝入主存時，主存無空間怎么辦？第四章存儲管理Operating System4.7.3 頁式虛擬

18、存儲器的實現(xiàn)1）實現(xiàn)原理 將作業(yè)的全部信息作為副本保存在磁盤上，作業(yè)調(diào)度選中一個作業(yè)時，至少把作業(yè)的第一頁裝入主存，在作業(yè)執(zhí)行過程中欲訪問不在主存中的頁時，再把他們調(diào)入。 -改造頁表改造頁表 頁號頁號標志標志內(nèi)存塊號內(nèi)存塊號 磁盤上的位置磁盤上的位置標志位為0：頁面不在內(nèi)存，需調(diào)入（課本P104頁圖4-22）第四章存儲管理Operating System2）頁面調(diào)度 -當預(yù)調(diào)入一頁時，主存已沒有空閑塊時，必須調(diào)出已在內(nèi)存中的某一頁，再將當前所需的頁調(diào)入，同時修改頁表。 -采用某種頁面調(diào)度算法使頁面在磁盤和主存之間掉進調(diào)出的這個過程稱為頁面調(diào)度。顛簸（抖動） 在虛擬頁時存儲管理中，頁面在內(nèi)存與外

19、存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導致系統(tǒng)崩潰。這種現(xiàn)象稱為“顛簸或抖動”第四章存儲管理Operating System3）頁面調(diào)度算法（1）最佳(Optimal)調(diào)度算法 選擇以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面淘汰。 特點： 1）通?？杀ＷC獲得最低的缺頁率。 2）無法實現(xiàn)，但可以利用它去評價其它算法利用它去評價其它算法。第四章存儲管理Operating System假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1第四章存儲

20、管理Operating System圖 利用最佳頁面置換算法時的置換圖 引用率70770170122010320304243230321201201770101頁框(物理塊）2430第四章存儲管理Operating System（2） 先進先出(FIFO)頁面置換算法 總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。 特點： 1）算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。 2）與進程實際運行的規(guī)律不相適應(yīng)。第四章存儲管理Operating System利用FIFO置換算法時的置換圖 引用率

21、70770170122010323104430230321013201770201頁框230420423023012712701第四章存儲管理Operating System（3）最近最久未使用(LRU)置換算法-根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策。 -選擇最近最久未使用的頁面予以淘汰。-賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。第四章存儲管理Operating System圖 LRU頁面置換算法 引用率707701701220103203044032303211322017701

22、01頁框40243203210217第四章存儲管理Operating System3）缺頁中斷率 f=F/A（1）分配給進程的物理頁面數(shù) 物理頁面數(shù)變多，缺頁率降低，反之缺頁率增加。 實驗結(jié)果表明:對一共有n頁的進程來說，只要能分到n/2塊內(nèi)存空間就可使系統(tǒng)獲得最高效率.（2）頁面本身的大小 頁面變大，缺頁率降低，反之，缺頁率升高。 第四章存儲管理Operating System（3）程序的編制方法例：把128*128的數(shù)組置初值0，數(shù)組中的每個 元素為一個字。現(xiàn)假定頁面的大小為每個頁128個字，數(shù)組的每一行放在一個頁中。該程序只有 一塊內(nèi)存塊可以使用，開始的時候第一頁裝入了內(nèi)存。方法1:(128-1次) For i:=1 to 128 For j:=1 to 128 Ai,j:=0;方法2:(128*128-1次) For j:=1 to 128 For i:=1 to 128 Ai,j:=0;缺頁次數(shù)與程序的局部化程度密切相關(guān)缺頁次數(shù)與程序的局部化程度密切相關(guān).通常希望編制的程通常希望編制的程序經(jīng)常集