操作系統(tǒng)chapter(5)課件

1、第三章存儲(chǔ)管理存儲(chǔ)管理是指主存管理(外存管理見(jiàn)文件系統(tǒng))， 包括給進(jìn)程分配主存片段，收回進(jìn)程釋放的主 存片段，為分配出去的主存片段提供保護(hù)與共 享，以及為作業(yè)提供一個(gè)虛擬的存儲(chǔ)空間 第三章存儲(chǔ)管理3.1 物理主存 物理主存簡(jiǎn)稱主存，它是計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)裝置 個(gè)人計(jì)算機(jī)上通常都配有128MB的RAM，除了操作系 統(tǒng)代碼占用一部分外，余者皆為用戶區(qū)域，由用戶進(jìn) 程瓜分 存儲(chǔ)管理3.2 存儲(chǔ)概念和虛存管理 鏈接工作的實(shí)質(zhì)是按照各個(gè)程序段之間的調(diào)用關(guān)系把各段的地址統(tǒng)一成從0開(kāi)始的一維線性地址。鏈接既可在作業(yè)運(yùn)行之前，也可在作業(yè)的程序段執(zhí)行過(guò)程中依調(diào)用關(guān)系動(dòng)態(tài)地進(jìn)行。前者稱為靜態(tài)鏈接，由link程序完

2、成；后者稱為動(dòng)態(tài)鏈接 第三章存儲(chǔ)管理3.2 存儲(chǔ)概念和虛存管理 從0開(kāi)始的指令地址和數(shù)據(jù)段地址組成作業(yè) 的地址空間，它是邏輯上的，與主存地址 毫不相干，因此稱為虛擬空間或虛擬存儲(chǔ) 器。虛存的容量與主存大小無(wú)關(guān)，它是由 計(jì)算機(jī)系統(tǒng)的地址結(jié)構(gòu)和尋址方式確定的 第三章存儲(chǔ)管理3.2 存儲(chǔ)概念和虛存管理 Windows API控制進(jìn)程的虛擬地址空間 (1)私用堆 用戶使用HeapCreate()來(lái)產(chǎn)生私用堆空間 HANDLE HeapCreate(flOptions, dwInitialSize, dwMaximumSize) DWORD flOptions; / 堆的分配標(biāo)記 DWORD dwIni

3、tialSize; / 堆的初始長(zhǎng)度 DWORD dwMaximumSize; / 堆的最大長(zhǎng)度 第三章存儲(chǔ)管理3.2 存儲(chǔ)概念和虛存管理 (2)保留虛空間 LPVOID VirtualAlloc(lpvAddress, cbSize, fdwAllocationType, fdwProtect) LPVOID lpvAddress;/ 該區(qū)虛地址 DWORD cbSize;/ 該區(qū)域的長(zhǎng)度 DWORD fdwAllocationType;/ 該區(qū)域被指定的類(lèi)型 DWORD fdwProtect;/ 該區(qū)域的訪問(wèn)保護(hù)即訪問(wèn)權(quán)限 第三章存儲(chǔ)管理3.2 存儲(chǔ)概念和虛存管理 (3)存儲(chǔ)映射文件.最主

4、要的虛存管理特性是 通過(guò)存儲(chǔ)映射支持共享虛存區(qū)域 LPVOID MapViewOfFile(hmapObect, fdwAccess,OffsetHigh, dwOffsetlow, cbMap) HANDLE hmapObject;/ 存儲(chǔ)映射對(duì)象的句柄 DWORD fdwAccess;/ 訪問(wèn)模式 DWORD dwOffsetHigh;/ 32位地址的高位部分 DWORD dwOffsetLow;/ 32位地址的低位部分 DWORD cbMap;/ 映射的字節(jié)數(shù) 第三章存儲(chǔ)管理3.3 地址變換 物理主存空間地址是一維線性排列的，不妨記作 M=0,1,2,2m-1, 表示主存容量為2m。例如

5、，當(dāng)m=23時(shí)，主存的容 量為8MB。虛存的一維線性空間和二維線性空間 分別記為： V1=0,1,2,2v-1 V2=0段0,1,2,n0,1段0,1,2,n1,，s段0,1,2,ns 第三章存儲(chǔ)管理3.3 地址變換 所謂地址變換(又稱地址映射)就是把多個(gè)V空間映射到M空間上去，或者說(shuō)是把虛存地址變換成物理主存地址 第三章存儲(chǔ)管理3.4 進(jìn)程空間不大于主存空間的管理 圖3-2圖3-2 固定分區(qū)原理圖第三章存儲(chǔ)管理3.4.1 固定分區(qū) 由于進(jìn)程空間(PS)的虛地址是從0開(kāi)始遞增編址的， 因此裝入模塊在把它裝入到分區(qū)時(shí)，必須把所有 虛地址變換成從分區(qū)始址為起點(diǎn)的物理地址，其 變換公式是 ： 物理地

6、址=虛地址+分區(qū)的始址 第三章存儲(chǔ)管理3.4.1 固定分區(qū) 靜態(tài)重定位(static address relocation) 動(dòng)態(tài)重定位(dynamic address relocation) 如圖3-3 圖3-3 動(dòng)態(tài)重定位過(guò)程示意圖第三章存儲(chǔ)管理3.4.1 固定分區(qū) 固定分區(qū)的保護(hù)是指各進(jìn)程空間在主存內(nèi)運(yùn)行時(shí)保證其每個(gè)物理地址都不超越自己的上下界限 2種保護(hù)法（見(jiàn)圖3-4） 對(duì)上下界保護(hù)法滿足：(UR)物理地址(LR) 對(duì)基址/限長(zhǎng)保護(hù)法滿足：(BR)物理地址(BR)+(LR) 第三章存儲(chǔ)管理3.4.2 可變分區(qū) 根據(jù)進(jìn)程空間的實(shí)際大小按需分配主存空間 這種管理方法下，主存分區(qū)的個(gè)數(shù)，各區(qū)

7、域的大小，在主存內(nèi)活動(dòng)的進(jìn)程個(gè)數(shù)等都是隨時(shí)間而變化的。所以，可變分區(qū)又稱為動(dòng)態(tài)分區(qū) 圖3-5 圖3-6圖3-5 可變分區(qū)管理初始狀態(tài)示例 第三章存儲(chǔ)管理3.4.2.1 數(shù)據(jù)結(jié)構(gòu) 有2種數(shù)據(jù)結(jié)構(gòu)，即自由區(qū)表FBT(Free Block Table)和自由區(qū)鏈FBC(Free Block Chain)供可變分區(qū)管理選用 （圖3-7） FBC的設(shè)計(jì)技巧在于，它利用自由區(qū)本身的空間記錄自由區(qū)的大小及前后自由區(qū)的位置 第三章存儲(chǔ)管理3.4.2.2 分區(qū)分配算法 首次適應(yīng)法(First Fit) 找到第1個(gè)能滿足長(zhǎng)度要求的自由區(qū)，從中截取所需空間 最佳適應(yīng)法(Best Fit) 從自由區(qū)鏈中挑選能滿足申請(qǐng)

8、長(zhǎng)度的最小自由區(qū) 最壞適應(yīng)法(Worst Fit) 總是挑選最大的自由區(qū)分割給申請(qǐng)者 第三章存儲(chǔ)管理3.4.2.3分配/回收程序與優(yōu)先級(jí)考慮 以首次適應(yīng)算法和FBC結(jié)構(gòu)為例，請(qǐng)求大小為x的自由存儲(chǔ)區(qū)分配程序如下： PROCEDURE get_block(x, p); BEGIN i:=1; WHILE (FBCi.size0) AND (FBCi.size= THEN BEGIN FBCi.size:=y; FBCi.adder:=FBCi.adder+x: END END END 第三章第三章存儲(chǔ)管理3.4.2.3分配/回收程序與優(yōu)先級(jí)考慮 回收過(guò)程(free_block) 回收時(shí)要考慮回收

9、的自由區(qū)是否與原自由區(qū)鄰接 圖3-8第三章存儲(chǔ)管理3.4.2.3分配/回收程序與優(yōu)先級(jí)考慮 get_block算法越快，系統(tǒng)的性能越好 要研制快速get_block算法并且給予它以高的優(yōu)先級(jí)以便盡快得到CPU響應(yīng) 第三章存儲(chǔ)管理3.4.2.4 地址變換與保護(hù)圖3-9 地址變換與保護(hù)第三章存儲(chǔ)管理3.4.2.5 分區(qū)共享 只要2個(gè)進(jìn)程空間包含相同的虛地址 (如Windows 95)，物理主存分區(qū)即被2 進(jìn)程所共享。同理，允許多進(jìn)程共享 分區(qū) 第三章存儲(chǔ)管理3.4.3 頁(yè)式管理把進(jìn)程空間劃分成較小的片段(稱為頁(yè)面)，把主存 也劃分成較小的片段(稱為塊)，使頁(yè)長(zhǎng)等于塊長(zhǎng)， 恰好1頁(yè)能占用主存的1塊

10、（圖3-10）3.4.3.1 數(shù)據(jù)結(jié)構(gòu) 圖3-11 圖3-12圖3-10 頁(yè)式管理示意圖進(jìn)程空間分頁(yè)頁(yè)012塊01234567主存分塊圖3-11 虛空間表與各頁(yè)表的關(guān)系 圖3-12 主存空閑塊表的數(shù)據(jù)結(jié)構(gòu) N-1N-20 head(a) 空閑塊鏈00110(b) 位示圖圖3-12 主存空閑塊表的數(shù)據(jù)結(jié)構(gòu) 狀態(tài)進(jìn)程號(hào) 頁(yè)號(hào) n=當(dāng)前空閑塊數(shù)塊號(hào)01N-1(c) 主存分塊表第三章存儲(chǔ)管理3.4.3.2 主存的分配與回收PROCEDURE cmalloc(x, p); BEGIN K:=x/Block_size; IF N=K THEN BEGIN p:=get a PT;/ 申請(qǐng)一個(gè)頁(yè)表區(qū) FOR

11、 i=1 TO K DO PTi:=get a free block END/ 申請(qǐng)一個(gè)空閑塊，把塊號(hào)添入頁(yè)表 ELSE p:=0/ 分配失敗，返回零 END. 其中x為進(jìn)程所申請(qǐng)的主存空間大小，p為指向頁(yè)表的指針。回收算法留給讀者 第三章存儲(chǔ)管理3.4.3.3 地址變換和保護(hù)措施圖3-13圖3-14圖3-13 頁(yè)式地址變換控制寄存器有效地址寄存器頁(yè)表長(zhǎng)度頁(yè)表始址pwB12345塊號(hào)塊Bw主存頁(yè)表密碼權(quán)限密鑰現(xiàn)行PSW2 正確訪問(wèn)：(密鑰=密碼）LOAD1塊：不違反寫(xiě)保護(hù)STORE1塊：不違反讀保護(hù)非法訪問(wèn)STORE2塊：違反寫(xiě)保護(hù)LOAD1塊：密鑰=密碼塊塊塊101112圖3-14 存儲(chǔ)鍵保

12、護(hù)法 第三章存儲(chǔ)管理3.4.3.4 性能研究通常在CPU和主存之間增設(shè)高速小型的聯(lián)想寄 存器組，稱之為“快表”，用它存放現(xiàn)行進(jìn)程頁(yè)表 中最近常用的部分表目 圖3-15圖3-15 快表的使用 頁(yè)號(hào)塊號(hào)pwBw頁(yè)號(hào)塊號(hào)第三章存儲(chǔ)管理3.4.3.4 性能研究設(shè)置快表后訪問(wèn)主存的流程如下： (1)CPU給出虛地址 (2)按p值聯(lián)查快表，若找到塊號(hào)B則轉(zhuǎn)否則轉(zhuǎn) (3)按p值找頁(yè)表得號(hào)B，把p指向的頁(yè)表表目讀入快表， 置換“舊表目” (4)由B、w形成物理地址 (5)訪問(wèn)主存 (6)結(jié)束本次訪問(wèn) 第三章存儲(chǔ)管理3.4.3.5 頁(yè)面共享圖3-16 共享例程的頁(yè)面 附接的共享頁(yè)進(jìn)程乙的原有頁(yè)進(jìn)程甲的原有頁(yè)附接

13、的共享頁(yè)主存主存塊號(hào)塊號(hào)頁(yè)號(hào)塊5（共享例程第0頁(yè)）塊7（共享例程第1頁(yè)）塊9（共享例程第2頁(yè)）頁(yè)表第三章存儲(chǔ)管理3.4.4 段式管理 所謂“段(segment)”是指在邏輯上有完整意義的一組 連續(xù)編址的代碼段由程序員定義、能用引用段 內(nèi)的信息經(jīng)編譯后，轉(zhuǎn)換成第三章存儲(chǔ)管理3.4.4 段式管理每個(gè)分段必須分配在主存的一片地址連 續(xù)的 區(qū)域內(nèi)，但各段之間不強(qiáng)求連續(xù)主存 同一作業(yè)內(nèi)的各段組成二維地址空間V2圖3-17圖3-17 二維進(jìn)程空間 主 段子 段其他段01K -1001K -1i01K -1m-iS 0 S i S m-i 第三章存儲(chǔ)管理3.4.4.1 段式管理的實(shí)現(xiàn)段式管理的存儲(chǔ)分配的描述

14、性程序如下： PROCEDURE cmalloc(k; s1, s2, , Sk; p)； BEGIN p=get a ST;/ 獲得一個(gè)存放段表的空間 FOR i:=1 To k DO BEGIN STi:=get a region; IF no success THEN p:=0 END END 圖3-18 段式地址變換第三章存儲(chǔ)管理3.5 進(jìn)程空間大于主存空間有2種主要的方法能“擴(kuò)充”主存，第1種 是覆蓋，第2種是虛擬存儲(chǔ)器 請(qǐng)求頁(yè)式和請(qǐng)求段頁(yè)式管理是實(shí)現(xiàn)虛存 的2個(gè)具體方案 3.5.1 請(qǐng)求頁(yè)式管理3.5.1.1 請(qǐng)求頁(yè)式的實(shí)現(xiàn)圖3-20 請(qǐng)求頁(yè)式下指令執(zhí)行過(guò)程 P標(biāo)記位，該頁(yè)在主存置

15、1，否則置0 D修改標(biāo)記位，對(duì)該頁(yè)內(nèi)容修改時(shí)置1，否則置0 A引用標(biāo)記位，任何一次對(duì)該頁(yè)的引用，包括讀、寫(xiě)、 執(zhí)行，都置1 U/S“用戶/管理員”標(biāo)記位 R/W權(quán)限標(biāo)記位 第三章存儲(chǔ)管理3.5.1.1 請(qǐng)求頁(yè)面實(shí)現(xiàn)根據(jù)MBT可以回答“主存有空閑塊嗎” 一條指令的執(zhí)行有可能產(chǎn)生多次缺頁(yè)中斷 對(duì)換區(qū)管理問(wèn)題 第三章存儲(chǔ)管理3.5.1.2 頁(yè)面置換算法 FIFO(First In First Out )即先進(jìn)先出算法 頁(yè)面訪問(wèn)序列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 頁(yè)面失效()： 圖3-22 當(dāng)M=3時(shí)，F(xiàn)IFO算法示例 但FIFO有異?，F(xiàn)象(Belad

16、ys anomaly)，即M增加時(shí) 不能下降反而增加 第三章存儲(chǔ)管理3.5.1.2 頁(yè)面置換算法 OPT(Optimal)即最優(yōu)置換算法 NUR(Not Used Recently)算法 LRU(Least Recently Used)算法 記時(shí)法 寄存器法 第三章存儲(chǔ)管理3.5.1.3 性能研究 M與的關(guān)系 頁(yè)面尺寸與的關(guān)系 與主存有效存取時(shí)間的關(guān)系 EAT頁(yè)面?zhèn)鬏敃r(shí)間ta 第三章存儲(chǔ)管理3.5.1.3 性能研究?jī)H在本進(jìn)程空間發(fā)生的顛簸稱局部顛簸當(dāng)系統(tǒng)內(nèi)進(jìn)程總數(shù)超過(guò)一定數(shù)額時(shí)，CPU的利用率反而急劇下降系統(tǒng)進(jìn)入顛簸 程序的局部性 第三章存儲(chǔ)管理3.5.1.3 性能研究工作集WS(workin

17、g set)是指在進(jìn)程運(yùn)行中距時(shí)刻ti最近的次訪問(wèn)主存所涉及到的那些頁(yè)面的集合 圖3-23 工作集第三章存儲(chǔ)管理3.5.1.4 對(duì)換區(qū)管理磁盤(pán)頁(yè)表對(duì)換文件 第三章存儲(chǔ)管理3.5.1.5 頁(yè)面共享圖3-24 請(qǐng)求頁(yè)市式下的頁(yè)面共享12100其它共享計(jì)數(shù)塊號(hào)12100其它共享計(jì)數(shù)塊號(hào)進(jìn)程甲的頁(yè)表進(jìn)程乙的頁(yè)表共享頁(yè)主頁(yè)塊號(hào)100第三章存儲(chǔ)管理3.5.1.6 實(shí)例-UNIX系統(tǒng)V的存儲(chǔ)管理 圖3-25 圖3-26 圖3-25 虛存布局、地址結(jié)構(gòu)與頁(yè)表項(xiàng)格式圖3-26 主存布局系統(tǒng)數(shù)據(jù)系統(tǒng)頁(yè)表進(jìn)程i的P0區(qū)頁(yè)表進(jìn)程i的P1區(qū)頁(yè)表主存位示圖進(jìn)程0的頁(yè)表進(jìn)程0的棧區(qū)進(jìn)程空間主存空閑快I/O專用第三章存儲(chǔ)管理3.5.2 請(qǐng)求段頁(yè)式管理3.5.2.1 實(shí)現(xiàn)原理虛擬地址是二維的： 圖3-27 請(qǐng)求段頁(yè)式管理的地址變換 第三章存儲(chǔ)管理3.5.2.1 實(shí)現(xiàn)原理越界中斷處理 越權(quán)中斷處理 缺頁(yè)中斷處理 鏈接中斷處理 鏈接中斷處理 第三章存儲(chǔ)管理3.5.2.2 分段動(dòng)態(tài)鏈接 MULTICS方法 （圖）圖3-28 MULTICS的動(dòng)態(tài)鏈接 load 1 3 100L 3 104load 1 3 1000 5 120M段 內(nèi)部段號(hào)3(編譯后鏈接前)內(nèi)部段號(hào)3（