第7章 存儲(chǔ)器管理ppt課件

1、精選課件第第7章章 存儲(chǔ)器管理存儲(chǔ)器管理n存儲(chǔ)器管理的主要目標(biāo)是為用戶提供方便、安全和充分大的存儲(chǔ)器。n存儲(chǔ)器即主存、內(nèi)存，分為兩大部分：n系統(tǒng)區(qū)：供操作系統(tǒng)使用n用戶區(qū)：劃分為一個(gè)或多個(gè)區(qū)域，供用戶進(jìn)程使用。精選課件存儲(chǔ)器管理的功能存儲(chǔ)器管理的功能n存儲(chǔ)空間的分配和回收：n地址變換：將邏輯地址變換為物理地址n存儲(chǔ)保護(hù)：防止因用戶程序錯(cuò)誤破壞系統(tǒng)或其他用戶，防止程序之間的相互干擾n存儲(chǔ)擴(kuò)充：在邏輯上為用戶提供一個(gè)比實(shí)際內(nèi)存更大的存儲(chǔ)空間精選課件7.1 存儲(chǔ)器管理的基本概念存儲(chǔ)器管理的基本概念n邏輯地址：用戶編程時(shí)所使用的地址。又稱相對(duì)地址、虛地址。n地址空間：邏輯地址的集合。n物理地址：內(nèi)存中

2、的地址。又稱絕對(duì)地址、實(shí)地址。n主存空間：物理地址的集合。精選課件地址變換n地址變換：將邏輯地址轉(zhuǎn)換為物理地址。又稱地址映射、重定位。 n地址變換分為兩類：n靜態(tài)地址變換n動(dòng)態(tài)地址變換精選課件靜態(tài)地址變換n靜態(tài)地址變換：又稱靜態(tài)地址重定位，地址變換在程序裝入時(shí)一次完成，以后不再改變。n特點(diǎn)：不需硬件支持，但程序運(yùn)行時(shí)不能在內(nèi)存移動(dòng)，程序需要連續(xù)存儲(chǔ)空間，難以共享。精選課件靜態(tài)地址變換示意圖 mov ax,500 mov ax,500 54321 54321 mov ax,1000+500 mov ax,1000+500 54321 54321 0100500999 0 1000 1100 15

3、00 19991M-1作業(yè)的地址空間主存空間重定位裝入程序精選課件動(dòng)態(tài)地址變換n動(dòng)態(tài)地址變換：又稱動(dòng)態(tài)重定位，在程序執(zhí)行過(guò)程中，每次訪問(wèn)內(nèi)存之前將要訪問(wèn)程序地址轉(zhuǎn)換成內(nèi)存地址。n特點(diǎn)：需要硬件支持，不需連續(xù)空間，可以實(shí)現(xiàn)虛擬存儲(chǔ)。 精選課件動(dòng)態(tài)地址變換示意圖 mov ax,500mov ax,500 54321 54321 mov ax,500mov ax,500 54321 54321 0100500999 0 1000 1100 1500 19991M-1作業(yè)的地址空間存儲(chǔ)空間5001000邏輯地址重定位寄存器精選課件7.2 分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理n分區(qū)存儲(chǔ)管理是多道程序系統(tǒng)中采用的一種

4、最簡(jiǎn)單的方法。它把系統(tǒng)的內(nèi)存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占一個(gè)區(qū)域，其他區(qū)域由并發(fā)進(jìn)程共享，每個(gè)進(jìn)程占一個(gè)區(qū)域。n分區(qū)存儲(chǔ)管理分為：n固定分區(qū)n動(dòng)態(tài)分區(qū)精選課件7.2.1 固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理n固定分區(qū)存儲(chǔ)管理方法將內(nèi)存空間劃分為若干個(gè)固定大小的分區(qū)，每個(gè)分區(qū)中可以裝入一道程序。分區(qū)的位置及大小在運(yùn)行期間不能改變。n為了便于管理內(nèi)存，系統(tǒng)需要建立一張分區(qū)使用表，其中記錄系統(tǒng)中的分區(qū)數(shù)目、分區(qū)大小、分區(qū)起始地址及狀態(tài)。精選課件分區(qū)使用表例 操作系統(tǒng) 用戶作業(yè) 用戶作業(yè)分區(qū)號(hào) 大小 起始地址 狀態(tài) 1 8KB 20KB 已分配 2 32KB 28KB 已分配 3 32KB 60K

5、B 未分配 4 120KB 92KB 未分配 5 300KB 212KB 已分配 用戶作業(yè) 0 20KB 28KB 60KB 92KB 212KB512KB-1精選課件固定分區(qū)的內(nèi)存分配n分區(qū)分配：當(dāng)有用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索分區(qū)使用表，從中找出一個(gè)能滿足要求的空閑分區(qū)分配給該程序，然后修改分區(qū)說(shuō)明表中相應(yīng)表項(xiàng)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕分配內(nèi)存。n分區(qū)回收：當(dāng)程序執(zhí)行完畢不再需要內(nèi)存資源時(shí)，釋放程序占用的分區(qū)，管理程序只需將對(duì)應(yīng)分區(qū)的狀態(tài)置為未分配即可。n特點(diǎn)：最早的多道程序存儲(chǔ)管理方式，不能充分利用內(nèi)存，存在內(nèi)存碎片。精選課件7.2.2 動(dòng)態(tài)分區(qū)存儲(chǔ)管理動(dòng)態(tài)分區(qū)存儲(chǔ)管

6、理n動(dòng)態(tài)分區(qū)存儲(chǔ)管理又稱為可變分區(qū)存儲(chǔ)管理，這種存儲(chǔ)管理方法的實(shí)現(xiàn)思想是根據(jù)作業(yè)大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。精選課件動(dòng)態(tài)分區(qū)中的數(shù)據(jù)結(jié)構(gòu)n在動(dòng)態(tài)分區(qū)中常用的數(shù)據(jù)結(jié)構(gòu)有：n空閑分區(qū)表。用一個(gè)空閑分區(qū)表來(lái)登記系統(tǒng)中的空閑分區(qū)。其表項(xiàng)類似于固定分區(qū)。n空閑分區(qū)鏈。將內(nèi)存中的空閑分區(qū)以鏈表方式鏈接起來(lái)，構(gòu)成空閑分區(qū)鏈。精選課件空閑分區(qū)表示意圖分區(qū)號(hào) 大小 起始地址 1 8KB 24KB 2 12KB 128KB 3 8KB 248KB 4 5 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K)

7、空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1精選課件空閑分區(qū)鏈?zhǔn)疽鈭D 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1表頭指針精選課件分區(qū)分配算法n目前常用的分區(qū)分配算法有以下幾種：n首次適應(yīng)算法n循環(huán)首次適應(yīng)算法n最佳適應(yīng)算法n最壞適應(yīng)算法精選課件首次適應(yīng)算法

8、n首次適應(yīng)算法又稱最先適應(yīng)算法，該算法要求空閑分區(qū)按地址遞增的次序排列。n在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表（或空閑分區(qū)鏈）首開始順序查找，直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止。n然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件首次適應(yīng)算法的特點(diǎn)n特點(diǎn)：優(yōu)先利用內(nèi)存低地址端，高地址端有大空閑區(qū)。但低地址端有許多小空閑分區(qū)時(shí)會(huì)增加查找開銷。精選課件循環(huán)首次適應(yīng)算法n循環(huán)首次適應(yīng)算法又稱下次適應(yīng)算法，它是首次適應(yīng)算法的變形。n該算法在為進(jìn)程分配內(nèi)存空間時(shí)，從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到第一個(gè)能滿足

9、其大小要求的空閑分區(qū)為止。n然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件循環(huán)首次適應(yīng)算法的特點(diǎn)n特點(diǎn)：使存儲(chǔ)空間的利用更加均衡，但會(huì)使系統(tǒng)缺乏大的空閑分區(qū)。精選課件最佳適應(yīng)算法n最佳適應(yīng)算法要求空閑分區(qū)按容量大小遞增的次序排列。n在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表（或空閑分區(qū)鏈）首開始順序查找，直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止。n如果該空閑分區(qū)大于作業(yè)的大小，則從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，將剩余空閑區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件最佳適應(yīng)算法的特點(diǎn)n按最佳適應(yīng)算法為作業(yè)分配內(nèi)存，就

10、能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。n特點(diǎn)：保留了大的空閑區(qū)。但分割后的剩余空閑區(qū)很小。精選課件最壞適應(yīng)算法n最壞適應(yīng)算法要求空閑分區(qū)按容量大小遞減的次序排列。n在進(jìn)行內(nèi)存分配時(shí)，先檢查空閑分區(qū)表（或空閑分區(qū)鏈）中的第一個(gè)空閑分區(qū)，若第一個(gè)空閑分區(qū)小于作業(yè)要求的大小，則分配失??；n否則從該空閑分區(qū)中劃出與作業(yè)大小相等的一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中。精選課件最壞適應(yīng)算法的特點(diǎn)n特點(diǎn)：剩下的空閑區(qū)比較大，但當(dāng)大作業(yè)到來(lái)時(shí)，其存儲(chǔ)空間的申請(qǐng)往往得不到滿足。精選課件如何衡量分配算法的好壞n對(duì)于某一個(gè)作業(yè)序列來(lái)說(shuō)，若某種分配算法能將該

11、作業(yè)序列中所有作業(yè)安置完畢，則稱該分配算法對(duì)這一作業(yè)序列合適，否則稱為不合適。精選課件例n下表給出了某系統(tǒng)的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲(chǔ)管理策略?，F(xiàn)有以下作業(yè)序列：96K、20K、200K。若用首次適應(yīng)算法和最佳適應(yīng)算法來(lái)處理這些作業(yè)序列，試問(wèn)哪一種算法可以滿足該作業(yè)序列的請(qǐng)求?分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4218K220K596K530K精選課件例-采用最佳適應(yīng)算法分配1n申請(qǐng)96K，n選中5號(hào)分區(qū)，5號(hào)分區(qū)大小與申請(qǐng)空間大小一致，應(yīng)從空閑分區(qū)表中刪去該表項(xiàng)；分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4218K220K596

12、K530K分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4218K220K精選課件例-采用最佳適應(yīng)算法分配2n申請(qǐng)20K，n選中1號(hào)分區(qū)，分配后1號(hào)分區(qū)還剩下12K；分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4218K220K分區(qū)號(hào) 大小起始地址112K100K210K150K35K200K4218K220K精選課件例-采用最佳適應(yīng)算法分配3n申請(qǐng)200K，n選中4號(hào)分區(qū)，分配后剩下18K。分區(qū)號(hào) 大小起始地址112K100K210K150K35K200K4218K220K分區(qū)號(hào) 大小起始地址112K100K210K150K35K200K418K22

13、0K精選課件例-采用首次適應(yīng)算法分配1n申請(qǐng)96K，n選中4號(hào)分區(qū)，進(jìn)行分配后4號(hào)分區(qū)還剩下122K；分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4218K220K596K530K分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4122K220K596K530K精選課件例-采用首次適應(yīng)算法分配2n申請(qǐng)20K，n選中1號(hào)分區(qū)，分配后剩下12K；分區(qū)號(hào) 大小起始地址132K100K210K150K35K200K4122K220K596K530K分區(qū)號(hào) 大小起始地址112K100K210K150K35K200K4122K220K596K530K精選課件例-采用

14、首次適應(yīng)算法分配3n申請(qǐng)200K，n現(xiàn)有的五個(gè)分區(qū)都無(wú)法滿足要求，該作業(yè)等待。n顯然采用首次適應(yīng)算法進(jìn)行內(nèi)存分配，無(wú)法滿足該作業(yè)序列的需求。分區(qū)號(hào) 大小起始地址112K100K210K150K35K200K4122K220K596K530K精選課件分區(qū)分配n以首次適應(yīng)算法及空閑鏈表為例，申請(qǐng)分區(qū)大小為x， e是規(guī)定的不再分割的剩余區(qū)大小。將該分區(qū)從鏈中移出開始查表是鏈表尾？本次無(wú)法分配，返回YN空閑區(qū)容量x?N繼續(xù)檢查下一項(xiàng)容量xe?YYN從該分區(qū)中劃出x大小將分區(qū)分配給請(qǐng)求者，修改數(shù)據(jù)結(jié)構(gòu)精選課件程序示例1void cmalloc(node *head,int x)node *p, *q,

15、*t; p=head;while(p-sizelinkif(p!=null)p-size=p-size-x;if(p-sizelink=p-link;else t=p+p-size-x;elset=0; printf(“本次無(wú)法分配！n”);return(t);精選課件分區(qū)回收n回收分區(qū)時(shí)，應(yīng)將空閑區(qū)插入適當(dāng)位置，此時(shí)有以下四種：n回收分區(qū)r上面鄰接一個(gè)空閑分區(qū)n回收分區(qū)r下面鄰接一個(gè)空閑分區(qū)n回收分區(qū)r上面、下面各鄰接一個(gè)空閑分區(qū)n回收分區(qū)r不與任何空閑分區(qū)相鄰精選課件回收分區(qū)r上鄰接一個(gè)空閑分區(qū)n此時(shí)應(yīng)將回收區(qū)r與上鄰接分區(qū)F1合并成一個(gè)連續(xù)的空閑區(qū)。合并分區(qū)的首地址為空閑區(qū)F1的首地址，

16、其大小為二者之和。F1回收區(qū)精選課件回收分區(qū)r下鄰接一個(gè)空閑分區(qū)n此時(shí)應(yīng)將回收區(qū)r與下鄰接分區(qū)F2合并成一個(gè)連續(xù)的空閑區(qū)。合并分區(qū)的首地址為回收分區(qū)r的首地址，其大小為二者之和。回收區(qū)F2精選課件回收分區(qū)r上下鄰接空閑分區(qū)n此時(shí)應(yīng)將回收區(qū)r與上、下鄰接分區(qū)合并成一個(gè)連續(xù)的空閑區(qū)。合并分區(qū)的首地址為與r上鄰接空閑區(qū)F1的首地址，其大小為三者之和，且應(yīng)將與r下鄰接的空閑區(qū)F2從空閑分區(qū)表(或空閑分區(qū)鏈)中刪去。F1回收區(qū)F2精選課件回收分區(qū)r不與任何空閑分區(qū)相鄰n這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一個(gè)新表項(xiàng)，填寫分區(qū)大小及起始地址等信息，并將其加入到空閑分區(qū)表(或空閑分區(qū)鏈)中的適當(dāng)位置。n問(wèn)題：回收分區(qū)的個(gè)

17、數(shù)變化情況？精選課件程序示例2 void cfree(node *head, *s) /*head 為空閑鏈表的頭指針，s為釋放區(qū)*/ node *p,*q; int n; p=head; n=s-size; while(p!=null & plink; if(q+q-size=s) & (s+n=p) q-link=p-link; q-size=q-size+p-size+n; else if (s+n = p) s-link=p-link; q-link=s; s-size=p-size+n; else if (q+q-size=s)q-size=q-size+n; els

18、es-link=p; q-link=s;精選課件內(nèi)存保護(hù)內(nèi)存保護(hù)n存儲(chǔ)保護(hù)是防止一個(gè)作業(yè)有意或無(wú)意破壞操作系統(tǒng)或其他作業(yè)。n常用的存儲(chǔ)保護(hù)方法有：n上下界寄存器n基址限長(zhǎng)寄存器n除上述保護(hù)方案外，還有四種存取權(quán)限：n禁止做任何操作n只能執(zhí)行n只能讀n讀/寫精選課件上下界寄存器方法n上下界寄存器方法：n用上、下界寄存器分別存放作業(yè)存儲(chǔ)空間的結(jié)束地址和開始地址。n在作業(yè)運(yùn)行過(guò)程中，將每一個(gè)訪問(wèn)內(nèi)存的地址都同這兩個(gè)寄存器的內(nèi)容進(jìn)行比較，若超出了上下界寄存器的范圍則產(chǎn)生越界中斷。精選課件基址限長(zhǎng)寄存器方法n基址、限長(zhǎng)寄存器方法：n用基址和限長(zhǎng)寄存器分別存放作業(yè)存儲(chǔ)空間的起始地址及作業(yè)長(zhǎng)度。n當(dāng)作業(yè)執(zhí)行

19、時(shí)，將每一個(gè)訪問(wèn)內(nèi)存的相對(duì)地址和這個(gè)限長(zhǎng)寄存器比較，若邏輯地址超過(guò)限長(zhǎng)則產(chǎn)生越界中斷。精選課件7.2.3 碎片問(wèn)題及拼接技術(shù)碎片問(wèn)題及拼接技術(shù)n分區(qū)存儲(chǔ)管理中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間中。這種分配方法能滿足多道程序設(shè)計(jì)的需要，但存在碎片問(wèn)題。 n碎片也可稱為零頭，是指內(nèi)存中無(wú)法被利用的存儲(chǔ)空間。精選課件內(nèi)部碎片和外部碎片n內(nèi)部碎片是指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分n外部碎片是指系統(tǒng)中無(wú)法利用的小存儲(chǔ)塊。n前述分區(qū)存儲(chǔ)管理方法中存在什么碎片？精選課件解決碎片問(wèn)題的辦法n拼接：解決碎片問(wèn)題的辦法之一，即通過(guò)移動(dòng)把多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)，也可稱為緊縮或緊湊。n拼接的不足是要

20、耗費(fèi)大量處理機(jī)時(shí)間。精選課件拼接示意圖n拼接前 拼接后 操作系統(tǒng) 進(jìn)程5 空閑（10KB） 進(jìn)程4 空閑（30KB） 進(jìn)程3 空閑（26KB） 0 40KB 90KB 100KB 170KB 200KB 230KB256KB-1 操作系統(tǒng) 進(jìn)程5 進(jìn)程4 進(jìn)程3 空閑（66KB） 0 40KB 90KB 160KB 190KB 256KB-1精選課件拼接需要的技術(shù)支持拼接需要的技術(shù)支持n動(dòng)態(tài)重定位：拼接后程序在內(nèi)存的位置發(fā)生變化，因此需要?jiǎng)討B(tài)重定位技術(shù)支持。n空閑區(qū)放在何處：拼接后的空閑區(qū)放在何處不能一概而論，應(yīng)根據(jù)移動(dòng)信息量的多少來(lái)決定。n拼接的時(shí)機(jī)：n回收分區(qū)時(shí)拼接：只有一個(gè)空閑區(qū)，但拼接

21、頻率過(guò)高增加系統(tǒng)開銷。n找不到足夠大的空閑區(qū)且系統(tǒng)空閑空間總量能滿足要求：拼接頻率小于前者，空閑區(qū)管理稍復(fù)雜。也可以只拼接部分空閑區(qū)。精選課件7.3 伙伴系統(tǒng)n固定分區(qū)存儲(chǔ)管理限制了內(nèi)存中的進(jìn)程數(shù)，動(dòng)態(tài)分區(qū)的拼接需要大量時(shí)間，而伙伴系統(tǒng)是一種較為實(shí)用的動(dòng)態(tài)存儲(chǔ)管理辦法。n伙伴系統(tǒng)采用伙伴算法對(duì)空閑內(nèi)存進(jìn)行管理。該方法通過(guò)不斷對(duì)分大的空閑存儲(chǔ)塊來(lái)獲得小的空閑存儲(chǔ)塊。當(dāng)內(nèi)存塊釋放時(shí)，應(yīng)盡可能合并空閑塊。精選課件伙伴系統(tǒng)的內(nèi)存分配n設(shè)系統(tǒng)初始時(shí)可供分配的空間為2m個(gè)單元。n當(dāng)進(jìn)程申請(qǐng)大小為n的空間時(shí)，設(shè)2i-1n2i，則為進(jìn)程分配大小為2i的空間。n如系統(tǒng)不存在大小為2i的空閑塊，則查找系統(tǒng)中是否存

22、在大于2i的空閑塊，若找到則對(duì)其進(jìn)行對(duì)半劃分，直到產(chǎn)生大小為2i的空閑塊為止。精選課件伙伴系統(tǒng)的內(nèi)存回收n當(dāng)一塊被分成兩個(gè)大小相等的塊時(shí)，這兩塊稱為伙伴。n當(dāng)進(jìn)程釋放存儲(chǔ)空間時(shí)，應(yīng)檢查釋放塊的伙伴是否空閑，若空閑則合并。這個(gè)較大的空閑塊也可能存在空閑伙伴，此時(shí)也應(yīng)合并。重復(fù)上述過(guò)程，直至沒(méi)有可以合并的伙伴為止。精選課件伙伴地址公式n設(shè)某空閑塊的開始地址為d，長(zhǎng)度為2K，其伙伴的開始地址為：nBuddy（k，d）=d+2k，若d % 2k+1=0n =d-2k，若d % 2k+1= 2kn如果參與分配的2m個(gè)單元從a開始，則長(zhǎng)度為2K、開始地址為d的塊，其伙伴的開始地址為：nBuddy（k，d）

23、=d+2k，若（d-a）% 2k+1=0n =d-2k，若（d-a）% 2k+1= 2k精選課件伙伴系統(tǒng)分配及回收例n設(shè)系統(tǒng)中初始內(nèi)存空間大小為1MB，進(jìn)程請(qǐng)求和釋放空間的操作序列為：n進(jìn)程A申請(qǐng)200KB；B申請(qǐng)120KB；C申請(qǐng)240KB； D申請(qǐng)100KB；n進(jìn)程B釋放；E申請(qǐng)60KB；n進(jìn)程A、C釋放；n進(jìn)程D釋放；進(jìn)程E釋放。精選課件E A釋放分配過(guò)程示意圖n 0 128K 256K 384K 512K 640K 768K 896K 1M初始狀態(tài)A申請(qǐng)200B申請(qǐng)120C申請(qǐng)240D申請(qǐng)100 B釋放 E申請(qǐng)60 C釋放 D釋放 E釋放512K256KAA512K128KBAB256

24、KCAB256KCDA256KCD128KA256KCD64E256KCD64E256KD64256K512KE64256K512K128K128K精選課件伙伴系統(tǒng)的二叉樹表示n可以用二叉樹表示內(nèi)存分配情況。葉結(jié)點(diǎn)表示存儲(chǔ)器中的當(dāng)前分區(qū)，如果兩個(gè)伙伴是葉子，則至少有一個(gè)被分配。n右圖表示A（200）、B（120）、C（240）、D（100）分配之后的情況。ABDC1M512K256K128K精選課件伙伴系統(tǒng)的不足n分配和回收時(shí)需要對(duì)伙伴進(jìn)行分拆及合并。n存儲(chǔ)空間有浪費(fèi)。精選課件7.4 分頁(yè)存儲(chǔ)管理分頁(yè)存儲(chǔ)管理n分區(qū)管理中存在碎片，而緊湊技術(shù)開銷太大，若能取消作業(yè)對(duì)存儲(chǔ)區(qū)的連續(xù)性要求，則能較好地

25、解決碎片問(wèn)題。分頁(yè)存儲(chǔ)管理就是基于這一思想提出的。精選課件7.4.1 分頁(yè)存儲(chǔ)管理的基本原理n在分頁(yè)存儲(chǔ)管理中，將進(jìn)程的邏輯地址空間劃分成若干大小相等的頁(yè)（或稱頁(yè)面），相應(yīng)地將主存空間也劃分成與頁(yè)大小相等的塊（或稱物理塊）。在為進(jìn)程分配存儲(chǔ)空間時(shí)，總是以塊為單位來(lái)分配，可以將進(jìn)程中的某一頁(yè)存放到主存的某一空閑塊中。n分頁(yè)系統(tǒng)中是否有碎片？n頁(yè)內(nèi)碎片：由進(jìn)程最后一頁(yè)未裝滿而形成的碎片。精選課件頁(yè)表n為了在內(nèi)存中找到進(jìn)程的每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊，系統(tǒng)為每個(gè)進(jìn)程建立一張頁(yè)面映象表，簡(jiǎn)稱頁(yè)表。n頁(yè)表：記錄頁(yè)面在內(nèi)存中對(duì)應(yīng)物理塊的數(shù)據(jù)結(jié)構(gòu)。精選課件頁(yè)表的作用n頁(yè)表的作用是什么？?jī)?nèi)存空間作業(yè)的地址空間頁(yè)表

26、 0頁(yè)1頁(yè)2頁(yè)n頁(yè) 0 2 1 4 2 7 頁(yè)號(hào) 塊號(hào)01234567精選課件頁(yè)面大小的選擇n頁(yè)面的大小應(yīng)適中。若頁(yè)面太大，以至和一般進(jìn)程大小相差無(wú)幾，則頁(yè)面分配退化為：分區(qū)分配，同時(shí)頁(yè)內(nèi)碎片也較大。若頁(yè)面太小，雖然可減少頁(yè)內(nèi)碎片，但會(huì)導(dǎo)致頁(yè)表增長(zhǎng)。因此，頁(yè)面大小應(yīng)適中，通常為2的冪，一般在512B到4KB之間。n頁(yè)表一般存放在內(nèi)存中。也可以在頁(yè)表中設(shè)置存取控制字段，以實(shí)現(xiàn)存儲(chǔ)保護(hù)。精選課件存儲(chǔ)分塊表n存儲(chǔ)分塊表用來(lái)記錄內(nèi)存中各物理塊的使用情況及未分配物理塊總數(shù)。n存儲(chǔ)分塊表可用下述方式表示：n位示圖：利用二進(jìn)制的一位表示一個(gè)物理塊的狀態(tài)，1表示一分配，0表示未分配。所有物理塊狀態(tài)位的集合構(gòu)成

27、位示圖。n空閑存儲(chǔ)塊鏈：將所有的空閑存儲(chǔ)塊用鏈表鏈接起來(lái)，利用空閑物理塊中的單元存放指向下一個(gè)物理塊的指針。精選課件位示圖例n位示圖占用的存儲(chǔ)空間：物理塊數(shù)/8（字節(jié)） 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4精選課件請(qǐng)求表n請(qǐng)求表用來(lái)登記每個(gè)進(jìn)程的頁(yè)表在內(nèi)存中的物理位置及每個(gè)頁(yè)表的長(zhǎng)度、狀態(tài)等。如下圖所示。進(jìn)程號(hào) 請(qǐng)求頁(yè)面數(shù)頁(yè)表始址頁(yè)表長(zhǎng)度狀態(tài)1101

28、02410已分220103420已分315105415已分428未分 精選課件7.4.2 存儲(chǔ)空間的分配及回收n頁(yè)面分配：計(jì)算進(jìn)程所需頁(yè)面數(shù)，然后在請(qǐng)求表中登記進(jìn)程號(hào)、請(qǐng)求頁(yè)面數(shù)等。如存儲(chǔ)分塊表中有足夠的空閑塊可供進(jìn)程使用，則在系統(tǒng)中取得頁(yè)表始址，并在頁(yè)表中登記頁(yè)號(hào)及其對(duì)應(yīng)的物理塊號(hào)。否則無(wú)法分配。n頁(yè)面回收：將存儲(chǔ)分塊表中相應(yīng)的物理塊改為未分配，或?qū)⒒厥諌K加入到空閑存儲(chǔ)塊鏈中，并釋放頁(yè)表，修改請(qǐng)求表中的頁(yè)表始址及狀態(tài)。精選課件7.4.3 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)n地址變換機(jī)構(gòu)的任務(wù)是實(shí)現(xiàn)邏輯地址到物理地址的變換，即將邏輯地址中的頁(yè)號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。精選課件分頁(yè)的邏輯地址結(jié)構(gòu)n分頁(yè)存儲(chǔ)

29、管理系統(tǒng)中，邏輯地址由頁(yè)號(hào)和頁(yè)內(nèi)位移組成。其結(jié)構(gòu)如下所示：n若A為邏輯地址，L為頁(yè)面大小，則：n頁(yè)號(hào)： P=int(A/L)n頁(yè)內(nèi)位移：W=A % L31 12 11 0 頁(yè) 號(hào) P 頁(yè) 內(nèi) 位 移W精選課件基本地址變換機(jī)構(gòu)n頁(yè)表通常存放在內(nèi)存中，為了實(shí)現(xiàn)方便，系統(tǒng)中設(shè)置了一個(gè)頁(yè)表寄存器存放頁(yè)表在內(nèi)存的起始地址和頁(yè)表的長(zhǎng)度。n進(jìn)程未執(zhí)行時(shí)，頁(yè)表的起始地址和長(zhǎng)度存放在PCB中。當(dāng)進(jìn)程執(zhí)行時(shí)，才將頁(yè)表始址和長(zhǎng)度存入頁(yè)表寄存器中。精選課件地址變換過(guò)程n分頁(yè)地址變換機(jī)構(gòu)自動(dòng)地將邏輯地址分為頁(yè)號(hào)和頁(yè)內(nèi)位移；n將頁(yè)號(hào)與頁(yè)表長(zhǎng)度進(jìn)行比較，如果頁(yè)號(hào)超過(guò)了頁(yè)表長(zhǎng)度，則表示本次所訪問(wèn)的地址已超越進(jìn)程的地址空間，系

30、統(tǒng)產(chǎn)生地址越界中斷；n若未出現(xiàn)越界，則由頁(yè)表始址和頁(yè)號(hào)計(jì)算出相應(yīng)頁(yè)表項(xiàng)的位置，從中得到該頁(yè)的物理塊號(hào)；n將物理塊號(hào)與邏輯地址中的頁(yè)內(nèi)位移拼接在一起，就形成了訪問(wèn)主存的物理地址。精選課件分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)圖n注意這里的頁(yè)號(hào)字段？頁(yè)表寄存器頁(yè)表始址 頁(yè)表長(zhǎng)度越界中斷邏輯地址 頁(yè)號(hào)（2） 頁(yè)內(nèi)位移（452）頁(yè)號(hào) 塊號(hào)2385101234 8 452物理地址頁(yè)表精選課件分頁(yè)地址變換例1n設(shè)頁(yè)面大小為1K字節(jié)，作業(yè)的0、1、2頁(yè)分別存放在第2、3、8塊中。則邏輯地址2500的頁(yè)號(hào)及頁(yè)內(nèi)地址為：n2500/1024=2（頁(yè)號(hào)）；2500 %1024452（頁(yè)內(nèi)地址）；n查頁(yè)表可知第2頁(yè)對(duì)應(yīng)的物理塊號(hào)為

31、8；n將塊號(hào)8與頁(yè)內(nèi)地址452拼接得到物理地址為：n810244528644。精選課件地址變換例2n一分頁(yè)系統(tǒng)中邏輯地址長(zhǎng)度為16位，頁(yè)面大小為1KB，現(xiàn)有一邏輯地址0A6FH ，且第0、1、2、3頁(yè)依次存放在物理塊3、7、11、10中。n邏輯地址0A6FH的二進(jìn)制表示如下：頁(yè)號(hào) 頁(yè)內(nèi)地址000010 1001101111 n由此可知邏輯地址0A6FH的頁(yè)號(hào)為2，該頁(yè)存放在第11號(hào)物理塊中，用十六進(jìn)制表示塊號(hào)為B，所以物理地址為：n 1011 1001101111 ，即2E6FH。精選課件聯(lián)想存儲(chǔ)器聯(lián)想存儲(chǔ)器n因頁(yè)表放在主存中，故存取數(shù)據(jù)時(shí)CPU至少要訪問(wèn)兩次主存。降低了內(nèi)存訪問(wèn)速度。n為了提

32、高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查找能力的高速緩沖存儲(chǔ)器（又稱聯(lián)想存儲(chǔ)器或快表），用以存放當(dāng)前訪問(wèn)的那些頁(yè)表項(xiàng)。 精選課件引入快表后的地址變換過(guò)程n地址變換機(jī)構(gòu)自動(dòng)將頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行并行比較，若其中有與此匹配的頁(yè)號(hào)，則取出該頁(yè)對(duì)應(yīng)的塊號(hào)，與頁(yè)內(nèi)地址拼接形成物理地址。n若頁(yè)號(hào)不在快表中，則再到主存頁(yè)表中取出物理塊號(hào)，與頁(yè)內(nèi)地址拼接形成物理地址。n同時(shí)還應(yīng)將這次所查到的頁(yè)表項(xiàng)存入快表中，若快表已滿，則必須按某種原則淘汰出一個(gè)表項(xiàng)以騰出位置。精選課件具有聯(lián)想存儲(chǔ)器的地址變換n頁(yè)表與快表有何不同？頁(yè)表寄存器 頁(yè)表始址 頁(yè)表長(zhǎng)度越界中斷邏輯地址 頁(yè)號(hào) 頁(yè)內(nèi)位移頁(yè)號(hào) 塊號(hào) 01

33、234 物理地址頁(yè)表頁(yè)號(hào) 塊號(hào)快表精選課件聯(lián)想存儲(chǔ)器的大小n由于成本關(guān)系，快表大小一般由832個(gè)表項(xiàng)組成。由于局部性原理，聯(lián)想存儲(chǔ)器的命中率可達(dá)80%-90% 。精選課件7.4.4 多級(jí)頁(yè)表及反向頁(yè)表多級(jí)頁(yè)表及反向頁(yè)表n現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間，致使頁(yè)表很大，用連續(xù)空間存放頁(yè)表顯然不現(xiàn)實(shí)。n如邏輯地址32位，頁(yè)面大小4KB，則頁(yè)表項(xiàng)為1M，若每個(gè)頁(yè)表項(xiàng)占4字節(jié)，則頁(yè)表共需要4MB內(nèi)存空間。n解決方案：n用離散方式存儲(chǔ)頁(yè)表n僅將當(dāng)前需要的部分頁(yè)表項(xiàng)放在內(nèi)存，其余放在磁盤上，需要時(shí)調(diào)入。精選課件兩級(jí)頁(yè)表及多級(jí)頁(yè)表兩級(jí)頁(yè)表及多級(jí)頁(yè)表n將頁(yè)表再分頁(yè)，使每頁(yè)與內(nèi)存物理塊大小相同，并為它們

34、進(jìn)行編號(hào)0、1、，同時(shí)還為離散存放的頁(yè)表建立一張頁(yè)表。n例如：32位地址可以劃分為31 22 21 12 11 0 一級(jí)頁(yè)號(hào)p1 二級(jí)頁(yè)號(hào)p2 頁(yè)內(nèi)地址w精選課件兩級(jí)頁(yè)表結(jié)構(gòu)第0頁(yè)頁(yè)表內(nèi)存空間一級(jí)頁(yè)表 200020242700 2 7 0123456785901411012n 0 1 2 1023 85 90 第1頁(yè)頁(yè)表 0 1 21023 1411 0 1 21023第n頁(yè)頁(yè)表精選課件具有兩級(jí)頁(yè)表的地址變換過(guò)程具有兩級(jí)頁(yè)表的地址變換過(guò)程n利用邏輯地址中的一級(jí)頁(yè)號(hào)作為索引訪問(wèn)一級(jí)頁(yè)表，找到第二級(jí)頁(yè)表的起始地址，n再利用第二級(jí)頁(yè)號(hào)找到指定頁(yè)表項(xiàng)，從中取出塊號(hào)與頁(yè)內(nèi)地址拼接形成物理地址。精選課件具

35、有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu)具有兩級(jí)頁(yè)表的地址變換機(jī)構(gòu) 第一級(jí)頁(yè)表寄存器邏輯地址+二級(jí)頁(yè)表一級(jí)頁(yè)表 b w物理地址一級(jí)頁(yè)號(hào) 二級(jí)頁(yè)號(hào) 頁(yè)內(nèi)地址 p1 p2 wb精選課件多級(jí)頁(yè)表n對(duì)兩級(jí)頁(yè)表進(jìn)行擴(kuò)充，便可得到三級(jí)、四級(jí)或更多級(jí)的頁(yè)表。n多級(jí)頁(yè)表的實(shí)現(xiàn)方式與兩級(jí)頁(yè)表類似。精選課件反向頁(yè)表n現(xiàn)代操作系統(tǒng)一般允許大邏輯地址空間，如232，這使得頁(yè)表太大，為解決頁(yè)表占用大量存儲(chǔ)空間的問(wèn)題，引入了反向頁(yè)表。n反向頁(yè)表為每個(gè)物理塊設(shè)置一個(gè)頁(yè)表項(xiàng)，并將它們按物理塊號(hào)大小排序，表項(xiàng)內(nèi)容為頁(yè)號(hào)及其隸屬進(jìn)程的標(biāo)識(shí)號(hào)。精選課件反向頁(yè)表地址變換過(guò)程n利用進(jìn)程標(biāo)識(shí)號(hào)及頁(yè)號(hào)檢索反向頁(yè)表，若找到相應(yīng)的頁(yè)表項(xiàng)，則將其物理塊號(hào)與頁(yè)內(nèi)

36、地址拼接；否則請(qǐng)求調(diào)入該進(jìn)程相應(yīng)頁(yè)，在無(wú)調(diào)頁(yè)功能的系統(tǒng)中則出錯(cuò)。n由于反向頁(yè)表中沒(méi)有存放進(jìn)程中尚未調(diào)入頁(yè)，因此必須為每個(gè)進(jìn)程建立一張傳統(tǒng)頁(yè)表并存放在外存中，當(dāng)所訪問(wèn)頁(yè)不在內(nèi)存時(shí)使用這張頁(yè)表。頁(yè)表中包含各頁(yè)在外存的地址。精選課件反向頁(yè)表的地址變換邏輯地址邏輯地址進(jìn)程標(biāo)識(shí)號(hào)進(jìn)程標(biāo)識(shí)號(hào) 頁(yè)號(hào)頁(yè)號(hào)反向頁(yè)表反向頁(yè)表 b w物理地址物理地址 頁(yè)號(hào)頁(yè)號(hào) 頁(yè)內(nèi)地址頁(yè)內(nèi)地址 p w pid ppid p進(jìn)程標(biāo)識(shí)號(hào)進(jìn)程標(biāo)識(shí)號(hào)pid 0 1 2 bn n精選課件反向頁(yè)表的不足n反向頁(yè)表查找慢：因?yàn)檫M(jìn)程號(hào)及頁(yè)號(hào)不能作為索引，查找時(shí)必須在整個(gè)反向頁(yè)表中進(jìn)行。n解決辦法：n將常用頁(yè)表項(xiàng)存入快表n用散列函數(shù)存放反向頁(yè)表精選

37、課件7.4.5 存儲(chǔ)保護(hù)n分頁(yè)存儲(chǔ)管理采用兩種方式保護(hù)內(nèi)存：n地址越界保護(hù)：頁(yè)表長(zhǎng)度與邏輯地址中的頁(yè)號(hào)比較n存取控制保護(hù)：在頁(yè)表中增加保護(hù)位精選課件7.5 分段管理n由于分頁(yè)按物理單位進(jìn)行，沒(méi)有考慮程序段的邏輯完整性，給程序段的共享和保護(hù)帶來(lái)不便，另外動(dòng)態(tài)鏈接及段的動(dòng)態(tài)增長(zhǎng)也要求以邏輯上完整的程序段為單位管理。精選課件7.5.1 分段管理的原理n在分段存儲(chǔ)管理系統(tǒng)中，作業(yè)的地址空間由若干個(gè)邏輯分段組成，每個(gè)分段是一組邏輯意義相對(duì)完整的信息集合，每個(gè)分段都有自己的名字，每個(gè)分段都從0開始編址并采用一段連續(xù)的地址空間。n在進(jìn)行存儲(chǔ)分配時(shí)，以段為單位分配內(nèi)存，每段分配一個(gè)連續(xù)的內(nèi)存區(qū)，但各段之間不要

38、求連續(xù)。精選課件作業(yè)的地址空間是二維的n作業(yè)的地址空間分為多段，每段都從0開始編址，故地址是二維的。 01K 08000600分段MAIN（主程序）分段X（子程序）分段A（數(shù)據(jù)）精選課件分段系統(tǒng)的邏輯地址結(jié)構(gòu)n該地址結(jié)構(gòu)最多允許多少分段?每段最大長(zhǎng)度為多少?n該地址結(jié)構(gòu)允許作業(yè)最多有64K個(gè)段，每段的最大長(zhǎng)度為64KB。31 16 15 0 段 號(hào) S 段 內(nèi) 位 移 W精選課件7.5.2 分段存儲(chǔ)管理的實(shí)現(xiàn)n為了實(shí)現(xiàn)從邏輯地址到物理地址的變換，必須為每個(gè)進(jìn)程建立一個(gè)段表，用來(lái)記錄每段在內(nèi)存的起始地址及相關(guān)信息。其中每個(gè)表項(xiàng)描述一個(gè)分段的信息，至少包含：n段號(hào)n段長(zhǎng)n段在內(nèi)存的起始地址n其他信

39、息n段表一般存放在內(nèi)存。精選課件段表的作用內(nèi)存空間作業(yè)的地址空間段表 30K 40K 20K 80K 15K 120K 10K 150K段號(hào) 段長(zhǎng) 基址040K80K120K150K(MAIN)=0030K(X)=1020K(D)=2015K(S)=3020K0123 (MAIN)=0 30K (X)=1 20K (D)=2 15K (S)=3 15K精選課件地址變換n為實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長(zhǎng)度。n為了提高內(nèi)存的訪問(wèn)速度，也可以使用快表。精選課件地址變換過(guò)程n進(jìn)行地扯變換時(shí)，系統(tǒng)將邏輯地址中的段號(hào)S與段表長(zhǎng)度進(jìn)行比較，若段號(hào)超過(guò)了段表

40、長(zhǎng)度則產(chǎn)生越界中斷；n否則根據(jù)段表始址和段號(hào)計(jì)算出該段對(duì)應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存的起始地址，n然后再檢查段內(nèi)地址是否超過(guò)該段的段長(zhǎng)，若超過(guò)則同樣發(fā)出越界中斷信號(hào)；n若未越界，則將該段的起始地址與段內(nèi)位移相加，從而得到了要訪問(wèn)的物理地址。精選課件地址變換機(jī)構(gòu)圖段表寄存器 段表始址 段表長(zhǎng)度越界中斷邏輯地址 段號(hào)（2）段內(nèi)位移（100）段號(hào) 段長(zhǎng) 始址 1K 6K800 4K600 8K012物理地址段表8292精選課件分段地址變換例n設(shè)作業(yè)分為3段，0、1、2段長(zhǎng)度分別為1K、800、600，分別存放在內(nèi)存6K、4K、8K開始的內(nèi)存區(qū)域。n邏輯地址（2，100）的段號(hào)為2，段內(nèi)位移為1

41、00。n查段表可知第2段在內(nèi)存的起始地址8K。n將起始地址與段內(nèi)位移相加，8K1008292，物理地址為8292。精選課件分段與分頁(yè)的主要區(qū)別分段與分頁(yè)的主要區(qū)別n分頁(yè)管理與分段管理有許多相似之處，但兩者在概念上也有很多區(qū)別，主要表現(xiàn)在：n頁(yè)是信息的物理單位，是為了減少內(nèi)存碎片及提高內(nèi)存利用率，是系統(tǒng)管理的需要。段是信息的邏輯單位，它含有一組意義相對(duì)完整的信息，分段的目的是為了更好地滿足用戶的需要。n頁(yè)的大小固定且由系統(tǒng)決定，由硬件把邏輯地址劃分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分。段的長(zhǎng)度不固定且由用戶所編寫的程序決定，通常由編譯系統(tǒng)在對(duì)源程序進(jìn)行編譯時(shí)根據(jù)信息的性質(zhì)來(lái)劃分。n分頁(yè)系統(tǒng)中作業(yè)的地址空間是一維的，分段系統(tǒng)中作業(yè)的地址空間是二維的。精選課件7.5.3