動(dòng)脈存儲(chǔ)管理答案

1、第八章          動(dòng)態(tài)存儲(chǔ)管理一選擇題 1C二判斷題 1錯(cuò)誤 2正確三填空題1（1）480+8=488（480 %23+1=0） （2）480-32=448 3用戶(hù)不再使用而系統(tǒng)沒(méi)有回收的結(jié)構(gòu)和變量。例如，p=malloc(size)；，p=null；四應(yīng)用題1 在伙伴系統(tǒng)中，無(wú)論占用塊或空閑塊，其大小均為2的k(k為0的正整數(shù))次冪。若內(nèi)存容量為2m，則空閑塊大小只能是20，21，22，2m。由同一大塊分裂而得的兩個(gè)小塊互稱(chēng)“伙伴空間”，如內(nèi)存大小為210的塊分裂成兩個(gè)大小為29的塊。只有兩個(gè)“

2、伙伴空間”才能合并成一個(gè)大空間。起始地址為p，大小為2k的內(nèi)存塊，其伙伴的起始地址為：buddy(p,k)=p+2k (若p % 2k+1=0),或buddy(p,k)=p-2k (若p % 2k+1=2k)2首次擬合法；從鏈表頭指針開(kāi)始查找，找到第一個(gè)所需空間的結(jié)點(diǎn)即分配。最佳擬合法：鏈表結(jié)點(diǎn)大小增序排列，找到第一個(gè)所需空間的結(jié)點(diǎn)即分配。最差擬合法：鏈表結(jié)點(diǎn)大小逆序排列，總從第一個(gè)結(jié)點(diǎn)開(kāi)始分配，將分配后結(jié)點(diǎn)所?？臻g插入到鏈表適當(dāng)位置。首次擬合法適合事先不知道請(qǐng)求分配和釋放信息的情況,分配時(shí)需查詢(xún),釋放時(shí)插在表頭。 最佳擬合法適用于請(qǐng)求分配內(nèi)存大小范圍較寬的系統(tǒng),釋放時(shí)容易產(chǎn)生存儲(chǔ)量很小難以利

3、用的內(nèi)存碎片,同時(shí)保留那些很大的內(nèi)存塊以備將來(lái)可能發(fā)生的大內(nèi)存量的需求，分配與回收均需查詢(xún)。 最差擬合法適合請(qǐng)求分配內(nèi)存大小范圍較窄的系統(tǒng),分配時(shí)不查詢(xún),回收時(shí)查詢(xún),以便插入適當(dāng)位置。5（1）buddy(1664,7)=1664-128=1536 （2）buddy(2816,6)=2816+64=28806動(dòng)態(tài)存儲(chǔ)分配伙伴系統(tǒng)的基本思想請(qǐng)參見(jiàn)上面題1。邊界標(biāo)識(shí)法在每塊的首尾均有“占用”/“空閑”標(biāo)志，空閑塊合并方便。伙伴系統(tǒng)算法簡(jiǎn)單，速度快，但只有互為伙伴的兩個(gè)空閑塊才可合并，因而易產(chǎn)生雖空閑但不能歸并的碎片。7組織成循環(huán)鏈表的可利用空間表的結(jié)點(diǎn)大小按遞增序排列時(shí), 首次適配策略就轉(zhuǎn)變?yōu)樽罴堰m

4、配策略。8因?yàn)?12=29,可利用空間表的初始狀態(tài)圖如8-1所示。當(dāng)用戶(hù)申請(qǐng)大小為23的內(nèi)存塊時(shí),因24<23<=25,但沒(méi)有大小為25的塊,只有大小為29的塊,故將29的塊分裂成兩個(gè)大小為28的塊,其中大小為28的一塊掛到可利用空間表上,另一塊再分裂成兩個(gè)大小為27的塊。又將其中大小為27的一塊掛到可利用空間表上,另一塊再分裂成兩個(gè)大小為26的塊,一塊26的塊掛到可利用空間表上,另一塊分裂成兩個(gè)大小為25的塊,其中一塊掛到可利用空間表上,另一塊分給用戶(hù)(地址031)。如此下去,最后每個(gè)用戶(hù)得到的存儲(chǔ)空間的起始地址如圖8-2, 6個(gè)用戶(hù)分配所需要的存儲(chǔ)空間后可利用空間表的狀態(tài)如圖8

5、-3。在回收時(shí),因?yàn)榻o申請(qǐng)45的用戶(hù)分配了26,其伙伴地址是0,在占用中,不能合并,只能掛到可利用空間表上。在回收大小為52的占用塊時(shí),其伙伴地址是192,也在占用。回收大小為11的占用塊時(shí),其伙伴地址是48,可以合并為大小25的塊, 掛到可利用空間表上?；厥?個(gè)占用塊之后可利用空間表的狀態(tài)如圖8-4。存儲(chǔ)大小起始地址 23 0 45 64 52 128 100 256 11 32 19 192圖8-2 圖8-1“可利用空間表”中。） 圖8-3 圖8-49 因?yàn)?68 % 27+1=0，所以768和768+27=896互為伙伴, 伙伴合并后,首址為768,塊大小為28。因?yàn)?68 % 28+1=28,所以,所以首址768大小為28的塊和首址512大小為28的塊合并,成為首址512大小為29的空閑塊。因?yàn)?28 % 27+1=27，其伙伴地址為128-27=0, 將其插入可利用空間表中?；厥蘸笤摶锇橄到y(tǒng)的狀態(tài)圖如下。10（1）系統(tǒng)回收一個(gè)起始地址為559，大小為45的空閑塊后，因右側(cè)起始地址604為空閑塊，應(yīng)與之合并。合并后，起始地址為559，大小為167的空閑塊。鏈表狀態(tài)如圖10（1）所示。10（1）（2）系統(tǒng)在接受存儲(chǔ)塊大小為100的請(qǐng)求后，將大小為117的空閑塊分出100給予用戶(hù)。在回收一個(gè)起始地址為515，大小為4