計(jì)算機(jī)操作系統(tǒng)（第二版）課件：連續(xù)存儲(chǔ)器管理方式

算法基本概念？空閑分區(qū)鏈如何建立？如何分配？性能特點(diǎn)？4.2.1分區(qū)分配1、固定分區(qū)分配：概念、數(shù)據(jù)結(jié)構(gòu)、分配與回收、地址映射、性能分析2、動(dòng)態(tài)分區(qū)分配的概念及數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3、分配算法

首次適應(yīng)算法

最佳適應(yīng)算法

最壞適應(yīng)算法4、動(dòng)態(tài)分區(qū)的回收方法：若采用首次適應(yīng)算法，每種情況如何修改數(shù)據(jù)結(jié)構(gòu)？5、地址映射機(jī)制和存儲(chǔ)保護(hù)機(jī)制6、碎片問題及拼接技術(shù)

連續(xù)存儲(chǔ)管理方式如何改善碎片問題？最大的性能缺點(diǎn)是什么？產(chǎn)生內(nèi)部碎片4.2.1固定分區(qū)分配1.概念：將內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只裝入一道作業(yè)。2.分區(qū)的劃分：分區(qū)大小相等；分區(qū)大小不等4.2連續(xù)存儲(chǔ)管理方式第4分區(qū)第3分區(qū)第2分區(qū)第1分區(qū)區(qū)號(hào)分區(qū)大小起始地址狀態(tài)OS進(jìn)程C（20K）

進(jìn)程A（6K）

內(nèi)部碎片4.2.1固定分區(qū)分配3.數(shù)據(jù)結(jié)構(gòu)：分區(qū)使用表0：已分配1：未分配1 8K 20K 未使用2 32K 28K 未使用3 64K 60K 未使用4 132K 124K 未使用進(jìn)程B（25K）20K28K60K124K256K-10K已使用已使用已使用進(jìn)程A申請(qǐng)6K空間進(jìn)程B申請(qǐng)25K空間進(jìn)程C申請(qǐng)20K空間進(jìn)程B釋放25K空間4.內(nèi)存分配與回收4.2.1固定分區(qū)分配5.地址轉(zhuǎn)換

靜態(tài)重定位優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。缺點(diǎn)：內(nèi)碎片造成浪費(fèi)分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。6.固定分區(qū)分配的特點(diǎn)空閑分區(qū)鏈20KB0

52KB66KB130KB230KB256KB1主存os程序1程序3程序452KBm-rib

空閑區(qū)隊(duì)列230KB014KB026KB

4.2.2動(dòng)態(tài)分區(qū)分配1.分區(qū)分配數(shù)據(jù)結(jié)構(gòu)每個(gè)鏈表節(jié)點(diǎn)中需要記錄哪些信息？（1）分區(qū)分配思路①

尋找空閑塊依申請(qǐng)者所要求的主存區(qū)的大小，分區(qū)分配程序在空閑分區(qū)鏈表中按一定算法尋找一個(gè)滿足用戶需要的空閑分區(qū)；②

若找到了所需的空閑區(qū)，有兩種情況ⅰ空閑區(qū)與要求的大小相等，將該空閑區(qū)分配并從隊(duì)列中摘除；ⅱ空閑區(qū)大于所要求的的大小，將空閑區(qū)分為兩部分：一部分成為已分配區(qū)，建立已分配區(qū)的描述器；剩下部分仍為空閑區(qū)。返回所分配區(qū)域的首址；③否則，告之不能滿足要求。2.分區(qū)分配4.2.2動(dòng)態(tài)分區(qū)分配程序1申請(qǐng)

32KB0

256KB1主存20KBos20KB0

52KB256KB1主存os程序1程序2申請(qǐng)

14KB20KB0

52KB66KB256KB1主存os程序1程序2程序3申請(qǐng)

64KB20KB0

52KB66KB130KB256KB1主存os程序1程序2程序3程序4申請(qǐng)

100KB20KB0

52KB66KB130KB230KB256KB1主存os程序1程序2程序3程序4程序5申請(qǐng)

50KB（2）動(dòng)態(tài)分區(qū)的分配過程2.分區(qū)分配4.2.2動(dòng)態(tài)分區(qū)分配①首次適應(yīng)算法：是將程序裝入到主存中足夠裝入且地址最低的空閑區(qū)中。

空閑分區(qū)鏈按分區(qū)起始地址遞增的順序鏈接。2.分區(qū)分配（1）分區(qū)分配算法考慮到分配效率，應(yīng)如何建立空閑分區(qū)鏈？算法概念？4.2.2動(dòng)態(tài)分區(qū)分配20K256K-1100K160K210K0OS

在使用

在使用

在使用首次適應(yīng)算法舉例：有一作業(yè)序列：作業(yè)A要求18K，作業(yè)B要求25K，作業(yè)C要求30K。5K46K30K20K鏈?zhǔn)?0K30k100K20k160K5k210K46k∧始址大小B12K21KA特點(diǎn)：內(nèi)存低端會(huì)留下小的空閑區(qū)（外部碎片），高端有大的空閑區(qū)。作業(yè)A、B、C會(huì)分別從哪個(gè)空閑分區(qū)中分配？作業(yè)C分配失?。、谧罴堰m應(yīng)算法是將程序裝入到主存中與其大小最接近的空閑區(qū)中。

空閑分區(qū)按大小遞增的次序排列。2.分區(qū)分配（1）分區(qū)分配算法考慮到分配效率，應(yīng)如何建立空閑分區(qū)鏈？算法概念？4.2.2動(dòng)態(tài)分區(qū)分配20K256K-1100K160K210K0OS

在使用

在使用

在使用最佳適應(yīng)算法舉例：有一作業(yè)序列：作業(yè)A要求18K，作業(yè)B要求25K，作業(yè)C要求30K。5K46K30K20KBAC特點(diǎn)：盡量利用存儲(chǔ)器中小的空閑區(qū)，而盡量保存大的空閑區(qū)。會(huì)留下大量小碎片作業(yè)A、B、C會(huì)分別從哪個(gè)空閑分區(qū)中分配？③最壞適應(yīng)算法：是將程序裝入到主存中與其大小差距最大的空閑區(qū)中?？臻e分區(qū)按大小遞減的次序排列2.分區(qū)分配（1）分區(qū)分配算法考慮到分配效率，應(yīng)如何建立空閑分區(qū)鏈？4.2.2動(dòng)態(tài)分區(qū)分配256K-120K100K160K210K05K46KOS30K20K

在使用

在使用

在使用210k210K46k20k20K30k100k100K20k160k160K5k∧

最壞適應(yīng)算法舉例：有一作業(yè)序列：作業(yè)A要求18K，作業(yè)B要求25K，作業(yè)C要求30K。

特點(diǎn)：盡量利用存儲(chǔ)器中的大空閑區(qū)，使剩余空閑區(qū)較大。不容易留下大分區(qū)。作業(yè)A、B、C會(huì)分別從哪個(gè)空閑分區(qū)中分配？（1）分區(qū)回收思路①

檢查釋放分區(qū)(即為回收分區(qū))在主存中的鄰接情況若上、下鄰接空閑區(qū)，則合并，成為一個(gè)連續(xù)的空閑區(qū)②若回收分區(qū)不與任何空閑區(qū)相鄰接

建立一個(gè)新的空閑區(qū)，并加入到空閑區(qū)隊(duì)列中。③修改相關(guān)數(shù)據(jù)結(jié)構(gòu)3.分區(qū)回收4.2.2動(dòng)態(tài)分區(qū)分配（2）分區(qū)回收算法：①回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)相鄰接，兩者合并；回收作業(yè)F1

R作業(yè)F2F1作業(yè)作業(yè)F23.分區(qū)回收需要修改哪些數(shù)據(jù)結(jié)構(gòu)？4.2.2動(dòng)態(tài)分區(qū)分配②回收區(qū)與插入點(diǎn)的后一個(gè)空閑分區(qū)相鄰接，兩者合并；作業(yè)RF2作業(yè)回收作業(yè)F2作業(yè)F1F1需要修改哪些數(shù)據(jù)結(jié)構(gòu)？（2）分區(qū)回收算法：3.分區(qū)回收4.2.2動(dòng)態(tài)分區(qū)分配③回收區(qū)與插入點(diǎn)的前后兩個(gè)空閑分區(qū)相鄰接，三者合并；回收作業(yè)F1作業(yè)作業(yè)F1RF2作業(yè)需要修改哪些數(shù)據(jù)結(jié)構(gòu)？（2）分區(qū)回收算法：3.分區(qū)回收4.2.2動(dòng)態(tài)分區(qū)分配④回收區(qū)不與任何一個(gè)空閑分區(qū)相鄰接，插入一個(gè)新節(jié)點(diǎn)；F1作業(yè)F3作業(yè)F2F1作業(yè)R作業(yè)F2回收需要修改哪些數(shù)據(jù)結(jié)構(gòu)？（2）分區(qū)回收算法：3.分區(qū)回收4.2.2動(dòng)態(tài)分區(qū)分配20分區(qū)的回收過程舉例：程序2

完成程序4完成20KB0

52KB66KB130KB230KB256KB1主存程序1程序2程序3程序4os20KB0

52KB66KB130KB230KB256KB1主存程序1程序3程序4os20KB0

52KB66KB130KB230KB256KB1主存os程序1程序33.分區(qū)回收4.2.2動(dòng)態(tài)分區(qū)分配碎片問題在已分配區(qū)之間存在著的一些太小而難以利用的空閑區(qū)，稱為碎片。碎片影響主存的利用率。拼接技術(shù)是指移動(dòng)主存中已分配區(qū)，使分散的小空閑區(qū)連成一個(gè)大的空閑區(qū)。20KB

54KB58KB135KB254KB256KB1主存138KB程序20os程序3程序1拼接前20KB0

54KB131KB247KB256KB1主存os程序1程序2程序3拼接后分區(qū)分配中的存儲(chǔ)區(qū)拼接4.碎片問題及拼接技術(shù)4.2.2動(dòng)態(tài)分區(qū)分配外部碎片是指（）存儲(chǔ)分配完后所剩的空閑區(qū)沒有被使用的存儲(chǔ)區(qū)不能被使用的存儲(chǔ)區(qū)未被使用，而又不容易滿足用戶大小要求的存儲(chǔ)區(qū)ABCD提交單選題10分當(dāng)內(nèi)存外部碎片總?cè)萘看笥谀骋蛔鳂I(yè)所申請(qǐng)的內(nèi)存容量時(shí)，（）可以為該作業(yè)直接分配內(nèi)存不可以為該作業(yè)分配內(nèi)存拼接后，可以為該作業(yè)分配內(nèi)存一定能為該作業(yè)分配內(nèi)存ABCD提交單選題10分若某系統(tǒng)采用伙伴系統(tǒng)管理內(nèi)存，假設(shè)某進(jìn)程申請(qǐng)300B內(nèi)存空間，則它實(shí)際分配到的空間大小是（）。300B512B1024B不確定ABCD提交單選題10分三.伙伴系統(tǒng)（Buddy)4.2連續(xù)存儲(chǔ)管理方式所有分區(qū)的大小均為2k(l

≤k≤m):2l表示最小分區(qū)的大??；

2m表示最大分區(qū)的大?。ㄍǔＪ钦麄€(gè)可分配內(nèi)存的大小）。

系統(tǒng)中共有m個(gè)空閑分區(qū)鏈，空閑分區(qū)按其大小2k位于對(duì)應(yīng)的空閑分區(qū)鏈中。分配時(shí)，搜索最接近要求的、大小為2i的空閑分區(qū)鏈，如果有空閑分區(qū)，則將其中的一個(gè)分配出去；否則，搜索大小為2i+1的空閑分區(qū)鏈，如果有，則將一個(gè)分區(qū)分成一對(duì)伙伴，其中的一個(gè)分配出去，另一個(gè)插到大小為2i的空閑分區(qū)鏈中；……回收時(shí)，如果回收區(qū)的伙伴不在空閑分區(qū)鏈中，則只需將它插入相應(yīng)大小的空閑分區(qū)鏈中；否則，需要將該分區(qū)及其伙伴合并成一個(gè)大分區(qū)；……1.概念2.分配舉例：設(shè)內(nèi)存可分配的空間為128KB，現(xiàn)有進(jìn)程A申請(qǐng)20KB的空間。128K-10K64K32KAfree[]01…0K64K32K17128K64K32K2l16K分區(qū)大小161514三.伙伴系統(tǒng)（Buddy)4.2連續(xù)存儲(chǔ)管理方式實(shí)際要給A分配多大的空間？空閑塊起始地址3.回收舉例：依次釋放分區(qū)B，C，D:free[]01…16K96Km-l128K64K32K2l16K分區(qū)大小128K0K64K32KBC16K48K96K32K32K96KE伙伴