數(shù)結(jié)構(gòu)邊界標(biāo)識(shí)法

1、19:13:258.1 概述概述8.2 可利用空間表及分配方法可利用空間表及分配方法8.3 邊界標(biāo)識(shí)法邊界標(biāo)識(shí)法8.3.1 可利用空間表的結(jié)構(gòu)可利用空間表的結(jié)構(gòu)8.3.2 分配算法分配算法8.4 伙伴系統(tǒng)伙伴系統(tǒng)8.4.1 可利用空間表的結(jié)構(gòu)可利用空間表的結(jié)構(gòu)8.4.2 分配算法分配算法8.4.3 回收算法回收算法第八章第八章動(dòng)態(tài)存儲(chǔ)管理動(dòng)態(tài)存儲(chǔ)管理19:13:25 邊界標(biāo)識(shí)法（邊界標(biāo)識(shí)法（boundary tag method）是操作系統(tǒng)中用以進(jìn)）是操作系統(tǒng)中用以進(jìn)行動(dòng)態(tài)分區(qū)分配的一種存儲(chǔ)管理方法。系統(tǒng)將所有的空閑塊鏈行動(dòng)態(tài)分區(qū)分配的一種存儲(chǔ)管理方法。系統(tǒng)將所有的空閑塊鏈接在一個(gè)雙重循環(huán)鏈表

2、結(jié)構(gòu)的可利用空間表中；分配可按首次接在一個(gè)雙重循環(huán)鏈表結(jié)構(gòu)的可利用空間表中；分配可按首次擬合進(jìn)行，也可按最佳擬合進(jìn)行。擬合進(jìn)行，也可按最佳擬合進(jìn)行。 采用邊界標(biāo)識(shí)法系統(tǒng)的特點(diǎn)：在每個(gè)內(nèi)存區(qū)的頭部和底部采用邊界標(biāo)識(shí)法系統(tǒng)的特點(diǎn)：在每個(gè)內(nèi)存區(qū)的頭部和底部?jī)蓚€(gè)邊界上分別設(shè)有標(biāo)識(shí)，以標(biāo)識(shí)該區(qū)域?yàn)檎加脡K或空閑塊，兩個(gè)邊界上分別設(shè)有標(biāo)識(shí)，以標(biāo)識(shí)該區(qū)域?yàn)檎加脡K或空閑塊，使得在回收用戶釋放的空閑塊時(shí)易于判別在物理位置上與其相使得在回收用戶釋放的空閑塊時(shí)易于判別在物理位置上與其相鄰的內(nèi)存區(qū)域是否為空閑塊，以便將所有地址連續(xù)的空閑存儲(chǔ)鄰的內(nèi)存區(qū)域是否為空閑塊，以便將所有地址連續(xù)的空閑存儲(chǔ)區(qū)組合成一個(gè)盡可能大的空閑

3、塊。區(qū)組合成一個(gè)盡可能大的空閑塊。 8.3 邊界標(biāo)識(shí)法邊界標(biāo)識(shí)法19:13:25（1）結(jié)點(diǎn)結(jié)構(gòu)）結(jié)點(diǎn)結(jié)構(gòu)uplink tagheadllink tag size rlinkspacefoot結(jié)點(diǎn)由結(jié)點(diǎn)由3部分組成：頭部部分組成：頭部head域、域、space域和底部域和底部foot域。域。space：為一組地址連續(xù)的存儲(chǔ)單元，是可以分配給用戶使用的：為一組地址連續(xù)的存儲(chǔ)單元，是可以分配給用戶使用的 內(nèi)存區(qū)域。其大小有內(nèi)存區(qū)域。其大小有head中的中的size域指示域指示,并以頭部并以頭部head 和底部和底部foot作為它的兩個(gè)邊界。作為它的兩個(gè)邊界。 tag：標(biāo)志域：標(biāo)志域,在在head和和

4、foot中都設(shè)有該域中都設(shè)有該域,值為值為“0”表示空閑塊表示空閑塊, 值為值為“1”表示占用塊。表示占用塊。 size：整個(gè)結(jié)點(diǎn)的大小，包括頭部：整個(gè)結(jié)點(diǎn)的大小，包括頭部head和底部和底部foot所占空間。所占空間。llink：鏈域，位于頭部：鏈域，位于頭部head域，指向前驅(qū)結(jié)點(diǎn)。域，指向前驅(qū)結(jié)點(diǎn)。rlink：鏈域，位于頭部：鏈域，位于頭部head域，指向后繼結(jié)點(diǎn)。域，指向后繼結(jié)點(diǎn)。 foot：位于結(jié)點(diǎn)底部：位于結(jié)點(diǎn)底部,它的地址是隨結(jié)點(diǎn)中它的地址是隨結(jié)點(diǎn)中space空間的大小而變的空間的大小而變的. uplink：鏈域，位于尾部：鏈域，位于尾部foot域，指向本結(jié)點(diǎn)頭部，其值即為該空域

5、，指向本結(jié)點(diǎn)頭部，其值即為該空 閑塊的首地址。閑塊的首地址。 8.3.1 可利用空間表的結(jié)構(gòu)可利用空間表的結(jié)構(gòu)19:13:25（2）c語(yǔ)言描述語(yǔ)言描述 typedef struct word /word：內(nèi)存字類型：內(nèi)存字類型union /head和和foot分別是結(jié)點(diǎn)的第一個(gè)字和最后的字分別是結(jié)點(diǎn)的第一個(gè)字和最后的字 word*llink;/頭部域，指向前驅(qū)結(jié)點(diǎn)頭部域，指向前驅(qū)結(jié)點(diǎn) word*uplink; /底部域，指向本結(jié)點(diǎn)頭部底部域，指向本結(jié)點(diǎn)頭部;inttag;/塊標(biāo)志塊標(biāo)志,0:空閑空閑,1:占用占用,頭部和尾部均有。頭部和尾部均有。intsize;/頭部域，塊大小頭部域，塊大小w

6、ord*rlink;/頭部域，指向后繼結(jié)點(diǎn)頭部域，指向后繼結(jié)點(diǎn)othertypeother;/字的其他部分字的其他部分 word, head, foot, *space;/*space:可利用空間指針類型可利用空間指針類型 #define footloc (p) p + psize-1/指向指向p所指結(jié)點(diǎn)的底部所指結(jié)點(diǎn)的底部19:13:25（3）例子）例子 例如，圖例如，圖8.5(a)是一個(gè)占有是一個(gè)占有100kb內(nèi)存空間的系統(tǒng)在有序開(kāi)始內(nèi)存空間的系統(tǒng)在有序開(kāi)始時(shí)的可利用空間表。時(shí)的可利用空間表。(a) 初始狀態(tài)初始狀態(tài)pav0 10 0000(b)運(yùn)行若干時(shí)間后的狀態(tài)運(yùn)行若干時(shí)間后的狀態(tài)pa

7、v10 000 31 000 59 0000 15 000 0 8 000 0 41 00000019:13:2510 000 31 000 59 0000 8 000 0 8 000 0 41 000000pav (c)進(jìn)行再分配后的狀態(tài)進(jìn)行再分配后的狀態(tài)圖圖8.5 某系統(tǒng)的可利用空間表某系統(tǒng)的可利用空間表19:13:25（1）算法描述）算法描述 假設(shè)采用首次擬合法進(jìn)行分配，則只要從表頭指針假設(shè)采用首次擬合法進(jìn)行分配，則只要從表頭指針pav所所指結(jié)點(diǎn)起，在可利用空間表中進(jìn)行查找，找到第一個(gè)容量不小指結(jié)點(diǎn)起，在可利用空間表中進(jìn)行查找，找到第一個(gè)容量不小于請(qǐng)求分配的存儲(chǔ)量于請(qǐng)求分配的存儲(chǔ)量(n)

8、的空閑塊時(shí)，即可進(jìn)行分配。為了使整的空閑塊時(shí)，即可進(jìn)行分配。為了使整個(gè)系統(tǒng)更有效地運(yùn)行，在邊界標(biāo)識(shí)法中還作了如下兩條約定：個(gè)系統(tǒng)更有效地運(yùn)行，在邊界標(biāo)識(shí)法中還作了如下兩條約定： 假設(shè)找到的此塊待分配的空閑塊的容量為假設(shè)找到的此塊待分配的空閑塊的容量為m個(gè)字（包括個(gè)字（包括頭部和底部）頭部和底部）,若每次分配只是從中分配若每次分配只是從中分配n個(gè)字給用戶個(gè)字給用戶,剩余剩余m-n個(gè)字大小的結(jié)點(diǎn)任留在鏈表中，則在若干次分配之后，鏈表中個(gè)字大小的結(jié)點(diǎn)任留在鏈表中，則在若干次分配之后，鏈表中會(huì)出現(xiàn)一些容量極小總也分配不出去的空閑塊，這就大大減慢會(huì)出現(xiàn)一些容量極小總也分配不出去的空閑塊，這就大大減慢了分

9、配（查找）的速度。彌補(bǔ)的辦法是：選定一個(gè)適當(dāng)?shù)某Ａ苛朔峙洌ú檎遥┑乃俣?。彌補(bǔ)的辦法是：選定一個(gè)適當(dāng)?shù)某Ａ縠，當(dāng)，當(dāng)mne時(shí)，就將容量為時(shí)，就將容量為m的空閑塊整塊分配給用戶；反的空閑塊整塊分配給用戶；反之，只分配其中之，只分配其中n個(gè)字的內(nèi)存塊。同時(shí)，為了避免修改指針個(gè)字的內(nèi)存塊。同時(shí)，為了避免修改指針,約約定將該結(jié)點(diǎn)中的高地址部分分配給用戶。定將該結(jié)點(diǎn)中的高地址部分分配給用戶。8.3.2 分配算法分配算法19:13:25 如果每次分配都從同一個(gè)結(jié)點(diǎn)開(kāi)始查找的話，勢(shì)必造成存如果每次分配都從同一個(gè)結(jié)點(diǎn)開(kāi)始查找的話，勢(shì)必造成存儲(chǔ)量小的結(jié)點(diǎn)密集在頭指針儲(chǔ)量小的結(jié)點(diǎn)密集在頭指針pav所指結(jié)點(diǎn)附近，這同

10、樣會(huì)增加查所指結(jié)點(diǎn)附近，這同樣會(huì)增加查詢較大空閑塊的時(shí)間。反之，如果每次分配從不同的結(jié)點(diǎn)開(kāi)始進(jìn)詢較大空閑塊的時(shí)間。反之，如果每次分配從不同的結(jié)點(diǎn)開(kāi)始進(jìn)行查找，使分配后剩余的小塊均勻的分布在鏈表中，則可避免上行查找，使分配后剩余的小塊均勻的分布在鏈表中，則可避免上述弊病。實(shí)現(xiàn)的方法是，在每次分配之后，令指針述弊病。實(shí)現(xiàn)的方法是，在每次分配之后，令指針pav指向剛進(jìn)指向剛進(jìn)行過(guò)分配的結(jié)點(diǎn)的后繼結(jié)點(diǎn)。行過(guò)分配的結(jié)點(diǎn)的后繼結(jié)點(diǎn)。 （2）算法實(shí)現(xiàn)）算法實(shí)現(xiàn) space allocboundtag (space &pav, int n) /若有不小于若有不小于n的空閑塊，則分配相應(yīng)的存儲(chǔ)塊，并返回

11、的空閑塊，則分配相應(yīng)的存儲(chǔ)塊，并返回/其首地址；否則返回其首地址；否則返回null。若分配后可利用空間表不。若分配后可利用空間表不/空，則空，則pav指向表中剛分配過(guò)的結(jié)點(diǎn)的后繼結(jié)點(diǎn)。指向表中剛分配過(guò)的結(jié)點(diǎn)的后繼結(jié)點(diǎn)。for (p = pav; p & psize rlink != pav; p = prlink);/查找不小于查找不小于n的空閑塊的空閑塊if (!p | | psize rlink;/pav指向指向*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)結(jié)點(diǎn)的后繼結(jié)點(diǎn)if (psizen = e) /整塊分配，不保留整塊分配，不保留llink = pllink;pllinkrlink = pav; / e

12、lse ptag = ftag = 1;/修改分配結(jié)點(diǎn)的頭部和底部標(biāo)志修改分配結(jié)點(diǎn)的頭部和底部標(biāo)志 / if19:13:25（3）例子）例子 例如，圖例如，圖8.5(b)所示可利用空間表在進(jìn)行分配之后的狀態(tài)所示可利用空間表在進(jìn)行分配之后的狀態(tài)如圖如圖8.5(c)所示。所示。 else /分配該塊的后分配該塊的后n個(gè)字個(gè)字 ftag = 1;/修改分配塊的底部標(biāo)志修改分配塊的底部標(biāo)志 psize = n;/置剩余塊大小置剩余塊大小 f = footloc (p);/指向剩余塊底部指向剩余塊底部 ftag = 0;fuplink = p;/設(shè)置剩余塊底部設(shè)置剩余塊底部 p = f + 1;/指向分

13、配塊頭部指向分配塊頭部 ptag = 1; psize = n;/甚至分配塊頭部甚至分配塊頭部return p; / else / allocboundtag19:13:25 用戶釋放占用塊后，系統(tǒng)需立即回收以備新的請(qǐng)求產(chǎn)生時(shí)用戶釋放占用塊后，系統(tǒng)需立即回收以備新的請(qǐng)求產(chǎn)生時(shí)進(jìn)行再分配。為了使物理地址毗鄰的空閑塊結(jié)合成一個(gè)盡可能進(jìn)行再分配。為了使物理地址毗鄰的空閑塊結(jié)合成一個(gè)盡可能大的結(jié)點(diǎn)，則首先需要檢查剛釋放的占用塊的左、右緊鄰是否大的結(jié)點(diǎn)，則首先需要檢查剛釋放的占用塊的左、右緊鄰是否為空閑塊。為空閑塊。假設(shè)用戶釋放的內(nèi)存區(qū)的頭部地址為假設(shè)用戶釋放的內(nèi)存區(qū)的頭部地址為p，則，則 p-1=與其

14、低地址緊鄰的內(nèi)存區(qū)的底部地址，即左鄰區(qū)；與其低地址緊鄰的內(nèi)存區(qū)的底部地址，即左鄰區(qū)； p+psize=與其高地址緊鄰的內(nèi)存區(qū)的頭部地址與其高地址緊鄰的內(nèi)存區(qū)的頭部地址,即右鄰區(qū)。即右鄰區(qū)。 （1）釋放塊的左、右鄰區(qū)均為占用塊。）釋放塊的左、右鄰區(qū)均為占用塊。 此時(shí)只要作簡(jiǎn)單插入即可。由于邊界標(biāo)識(shí)法在按首次擬合此時(shí)只要作簡(jiǎn)單插入即可。由于邊界標(biāo)識(shí)法在按首次擬合進(jìn)行分配時(shí)對(duì)可利用空間表的結(jié)構(gòu)沒(méi)有任何要求，則新的空進(jìn)行分配時(shí)對(duì)可利用空間表的結(jié)構(gòu)沒(méi)有任何要求，則新的空閑塊插入在表中任何位置均可。簡(jiǎn)單的做法就是插入在閑塊插入在表中任何位置均可。簡(jiǎn)單的做法就是插入在pav指指針?biāo)附Y(jié)點(diǎn)之前（之后），描述如

15、下：針?biāo)附Y(jié)點(diǎn)之前（之后），描述如下：8.3.3 回收算法回收算法19:13:25ptag = 1= 0;footloc (p)uplink = p;footloc (p)tag = 0;if (!pav)pav = pllink = prlink = p;else q = pavllink;prlink = pav;pllink = q;qrlink = pavllink = p;pav = p; /令剛釋放的結(jié)點(diǎn)為下次分配時(shí)的最先查詢的結(jié)點(diǎn)令剛釋放的結(jié)點(diǎn)為下次分配時(shí)的最先查詢的結(jié)點(diǎn)19:13:25n = psize;/釋放塊的大小釋放塊的大小s = (p1)uplink;/左鄰空閑塊的頭部

16、地址左鄰空閑塊的頭部地址ssize + = n;/設(shè)置新的空閑塊大小設(shè)置新的空閑塊大小f = p + n1;/設(shè)置新的空閑塊底部設(shè)置新的空閑塊底部fuplink = s;ftag = 0;（2）釋放塊的左鄰區(qū)為空閑塊，而右鄰區(qū)為占用塊。）釋放塊的左鄰區(qū)為空閑塊，而右鄰區(qū)為占用塊。 由于釋放塊的頭部和左鄰空閑塊的底部毗鄰，因此只要改變由于釋放塊的頭部和左鄰空閑塊的底部毗鄰，因此只要改變左鄰空閑塊的結(jié)點(diǎn)：增加結(jié)點(diǎn)的左鄰空閑塊的結(jié)點(diǎn)：增加結(jié)點(diǎn)的size域的值且重新設(shè)置結(jié)點(diǎn)的底域的值且重新設(shè)置結(jié)點(diǎn)的底部即可。描述如下：部即可。描述如下：（3）釋放塊的右鄰區(qū)為空閑塊，而左鄰區(qū)為占用塊。）釋放塊的右鄰區(qū)為

17、空閑塊，而左鄰區(qū)為占用塊。 由于釋放塊的底部和右鄰區(qū)空閑塊的頭部毗鄰，因此，當(dāng)表由于釋放塊的底部和右鄰區(qū)空閑塊的頭部毗鄰，因此，當(dāng)表中結(jié)點(diǎn)由原來(lái)的右鄰空閑塊變成合并后的大空閑塊時(shí)，結(jié)點(diǎn)的底中結(jié)點(diǎn)由原來(lái)的右鄰空閑塊變成合并后的大空閑塊時(shí)，結(jié)點(diǎn)的底部位置不變部位置不變,但頭部要變但頭部要變,由此由此,鏈表中的指針也要變。描述如下：鏈表中的指針也要變。描述如下：19:13:25t = p + psize;/右鄰空閑塊的頭部地址右鄰空閑塊的頭部地址ptag = 0;/p為合并后的結(jié)點(diǎn)頭部地址為合并后的結(jié)點(diǎn)頭部地址q = tllink; /q為為*t結(jié)點(diǎn)在可利用空間表中的前驅(qū)結(jié)點(diǎn)的頭部地址結(jié)點(diǎn)在可利用空

18、間表中的前驅(qū)結(jié)點(diǎn)的頭部地址pllink = q;/q指向指向*p的前驅(qū)的前驅(qū)qrlink = p;q1 = trlink; /q1為為*t結(jié)點(diǎn)在可利用空間表中的后繼結(jié)點(diǎn)的頭部地址結(jié)點(diǎn)在可利用空間表中的后繼結(jié)點(diǎn)的頭部地址prlink = q1;/q1指向指向*p的后繼的后繼q1llink = p;psize + = tsize;/新的空閑塊的大小新的空閑塊的大小footloc (t)uplink = p;/底部指針指向新結(jié)點(diǎn)的頭部底部指針指向新結(jié)點(diǎn)的頭部19:13:25（4）釋放塊的左、右鄰區(qū)均為空閑塊。）釋放塊的左、右鄰區(qū)均為空閑塊。 為使為使3個(gè)空閑塊連接在一起成為一個(gè)大結(jié)點(diǎn)留在可利用空間個(gè)

19、空閑塊連接在一起成為一個(gè)大結(jié)點(diǎn)留在可利用空間表中，只要增加左鄰空閑塊的表中，只要增加左鄰空閑塊的space容量，同時(shí)在鏈表中刪去右容量，同時(shí)在鏈表中刪去右鄰空閑塊結(jié)點(diǎn)即可。所作改變可描述如下：鄰空閑塊結(jié)點(diǎn)即可。所作改變可描述如下：n = psize;/釋放塊的大小釋放塊的大小s = (p1)uplink;/指向左鄰塊指向左鄰塊t = p + psize;/指向右鄰塊指向右鄰塊ssize + = n + trlink;/設(shè)置新結(jié)點(diǎn)的大小設(shè)置新結(jié)點(diǎn)的大小q = tllink;/q != q1q1 = trlink;qrlink = q1;/刪去右鄰空閑塊結(jié)點(diǎn)刪去右鄰空閑塊結(jié)點(diǎn)q1llink = q

20、;footloc (t)uplink = s;/新結(jié)點(diǎn)底部指針指向其頭部新結(jié)點(diǎn)底部指針指向其頭部19:13:25例如，在上述情況下可利用空間表的變化如圖例如，在上述情況下可利用空間表的變化如圖8.6所示。所示。30 0001 20 000120 00000 30 000左鄰區(qū)左鄰區(qū)釋放塊釋放塊(a) 釋放的存儲(chǔ)塊釋放的存儲(chǔ)塊(b) 左鄰區(qū)是空閑塊的情況左鄰區(qū)是空閑塊的情況(c) 右鄰區(qū)是空閑塊的情況右鄰區(qū)是空閑塊的情況00 35 0000 15 000右鄰區(qū)右鄰區(qū)釋放塊釋放塊右鄰區(qū)右鄰區(qū)19:13:25(d) 左、右鄰區(qū)均是空閑塊的情況左、右鄰區(qū)均是空閑塊的情況圖圖8.6回收存儲(chǔ)塊后的可利用空

21、間表回收存儲(chǔ)塊后的可利用空間表00 15 0000 45 000右鄰區(qū)右鄰區(qū)釋放塊釋放塊右鄰區(qū)右鄰區(qū)左鄰區(qū)左鄰區(qū)19:13:25 伙伴系統(tǒng)（伙伴系統(tǒng)（buddy system）是操作系統(tǒng)中用到的一種動(dòng)）是操作系統(tǒng)中用到的一種動(dòng)態(tài)存儲(chǔ)管理方法。它和邊界標(biāo)識(shí)法類似，在用戶提出申請(qǐng)時(shí)，態(tài)存儲(chǔ)管理方法。它和邊界標(biāo)識(shí)法類似，在用戶提出申請(qǐng)時(shí)，分配一塊大小分配一塊大小“恰當(dāng)恰當(dāng)”的內(nèi)存區(qū)給用戶；反之，在用戶釋放內(nèi)的內(nèi)存區(qū)給用戶；反之，在用戶釋放內(nèi)存區(qū)時(shí)即收回。存區(qū)時(shí)即收回。 伙伴系統(tǒng)的特點(diǎn)：無(wú)論是占用塊或空閑塊，其大小均為伙伴系統(tǒng)的特點(diǎn)：無(wú)論是占用塊或空閑塊，其大小均為2的的k次冪（次冪（k為某個(gè)正整數(shù)）

22、。為某個(gè)正整數(shù)）。8.4 伙伴系統(tǒng)伙伴系統(tǒng)19:13:25（1）結(jié)點(diǎn)結(jié)構(gòu)）結(jié)點(diǎn)結(jié)構(gòu)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)headllink tag kval rlinkspacenodesize first結(jié)點(diǎn)：右頭部結(jié)點(diǎn)：右頭部head和和space域組成。域組成。 head：為結(jié)點(diǎn)頭部，是一個(gè)由：為結(jié)點(diǎn)頭部，是一個(gè)由4個(gè)域組成的記錄。個(gè)域組成的記錄。 llink：鏈域，指向同一鏈表中的前驅(qū)結(jié)點(diǎn)。：鏈域，指向同一鏈表中的前驅(qū)結(jié)點(diǎn)。 rlink：鏈域，指向同一鏈表中的后繼結(jié)點(diǎn)。：鏈域，指向同一鏈表中的后繼結(jié)點(diǎn)。 tag：標(biāo)志域，值為：標(biāo)志域，值為“0”表示空閑塊，值為表示空閑塊，值為“1”表示占用塊。表示占用塊。

23、kval：其值為：其值為2的冪次的冪次k。 space：數(shù)據(jù)域，是一個(gè)大小為：數(shù)據(jù)域，是一個(gè)大小為2k1個(gè)字的連續(xù)內(nèi)存空間。個(gè)字的連續(xù)內(nèi)存空間。表頭結(jié)點(diǎn)：由兩個(gè)域組成。表頭結(jié)點(diǎn)：由兩個(gè)域組成。 nodesize：表示該鏈表中空閑塊的大小。：表示該鏈表中空閑塊的大小。 first：該鏈表的表頭指針。：該鏈表的表頭指針。 8.4.1 可利用空間表的結(jié)構(gòu)可利用空間表的結(jié)構(gòu)19:13:25 （2）c語(yǔ)言描述語(yǔ)言描述#define m16 /可利用空間總?cè)萘靠衫每臻g總?cè)萘?4k字的字的2的冪次，子表的個(gè)數(shù)為的冪次，子表的個(gè)數(shù)為m+1typedef struct word_b word_b*llink;

24、/頭部域，指向前驅(qū)結(jié)點(diǎn)頭部域，指向前驅(qū)結(jié)點(diǎn) inttag;/塊標(biāo)志，塊標(biāo)志，0：空閑，：空閑，1：占用。：占用。 intskval;/塊大小，值為塊大小，值為2的冪次的冪次k word_b*rlink;/頭部域，指向后繼結(jié)點(diǎn)頭部域，指向后繼結(jié)點(diǎn) othertypeother;/字的其他部分字的其他部分 word_b, head;/word：內(nèi)存字類型，結(jié)點(diǎn)的第一個(gè)字也稱：內(nèi)存字類型，結(jié)點(diǎn)的第一個(gè)字也稱headtypedef struct headnode intnodesize;/該鏈表的空閑塊的大小該鏈表的空閑塊的大小 word_b*first;/該鏈表的表頭指針該鏈表的表頭指針 freel

25、istm + 1;/表頭向量類型表頭向量類型 19:13:25（3）例子）例子 例如，可利用空間表的初始狀態(tài)如圖例如，可利用空間表的初始狀態(tài)如圖8.7(a)所示，其中所示，其中m個(gè)個(gè)子表都為空表，只有大小為子表都為空表，只有大小為2m的鏈表中有一個(gè)結(jié)點(diǎn)，即整個(gè)存的鏈表中有一個(gè)結(jié)點(diǎn)，即整個(gè)存儲(chǔ)空間。儲(chǔ)空間。(a) 表的初始狀態(tài)表的初始狀態(tài)nodesize first20212k2m0 m19:13:25(b) 分配前的表分配前的表(c) 分配后的表分配后的表圖圖8.7 伙伴系統(tǒng)中的可利用空間表伙伴系統(tǒng)中的可利用空間表202k-12m0 k2k0 k0 k202k-12m2k0 k0 k0 k-1

26、19:13:25（1）算法思想）算法思想 當(dāng)用戶提出大小為當(dāng)用戶提出大小為n的內(nèi)存請(qǐng)求時(shí)，首先在可利用表上尋找的內(nèi)存請(qǐng)求時(shí)，首先在可利用表上尋找結(jié)點(diǎn)大小與結(jié)點(diǎn)大小與n相匹配的子表，若此子表非空，則將子表中任意一相匹配的子表，若此子表非空，則將子表中任意一個(gè)結(jié)點(diǎn)分配之即可；若此子表為空，則需從結(jié)點(diǎn)更大的非空子表個(gè)結(jié)點(diǎn)分配之即可；若此子表為空，則需從結(jié)點(diǎn)更大的非空子表中去查找，直至找到一個(gè)空閑塊，則將其中一部分分配給用戶，中去查找，直至找到一個(gè)空閑塊，則將其中一部分分配給用戶，而將剩余部分插入相應(yīng)的子表中。而將剩余部分插入相應(yīng)的子表中。（2）算法實(shí)現(xiàn)）算法實(shí)現(xiàn) 算法算法8.2如下：如下： word

27、_b allocbuddy (frelist &avail, int n) /avail0.m為可利用空間表，為可利用空間表，n為申請(qǐng)分配量，若有不為申請(qǐng)分配量，若有不/小于小于n的空閑塊，則分配相應(yīng)的存儲(chǔ)塊，并返回其首的空閑塊，則分配相應(yīng)的存儲(chǔ)塊，并返回其首/地址；否則返回地址；否則返回null。for (k = 0; k = m & (availk.nodesize m)/分配失敗返回分配失敗返回nullreturn null; else /進(jìn)行分配進(jìn)行分配pa = availk.first;/指向可分配子表的第一個(gè)結(jié)點(diǎn)指向可分配子表的第一個(gè)結(jié)點(diǎn)pre = pallink;

28、/分別指向前驅(qū)和后繼分別指向前驅(qū)和后繼suc = parlink;if (pa = = suc)/分配后該子表變成空表分配后該子表變成空表 availk.first = null; else /從子表中刪去從子表中刪去*pa結(jié)點(diǎn)結(jié)點(diǎn) prerlink = suc; sucllink = pre; availk.first = suc;19:13:25for (i = 1; availk-i.nodesize = n + 1; + i) pi = pa + 2k-i; pirlink = pi; pillink = pi; pitag = 0; pikval = ki; availk-i.fir

29、st = pi; /將剩余塊插入相應(yīng)子表將剩余塊插入相應(yīng)子表patag = 1;pakval = k(i); / else return pa; / allocbuddy19:13:25（3）例子）例子 例如，假設(shè)分配前的可利用空間表的狀態(tài)如圖例如，假設(shè)分配前的可利用空間表的狀態(tài)如圖8.7(b)所示。所示。若若2k-1 n 2k1，又第，又第k1個(gè)子表不空，則只要?jiǎng)h除此鏈表個(gè)子表不空，則只要?jiǎng)h除此鏈表中第一個(gè)結(jié)點(diǎn)并分配給用戶即可；中第一個(gè)結(jié)點(diǎn)并分配給用戶即可； 若若2k-2 n 2k-11，此時(shí)由于結(jié)點(diǎn)大小為，此時(shí)由于結(jié)點(diǎn)大小為2k-1的子表為空，的子表為空，則需從結(jié)點(diǎn)大小為則需從結(jié)點(diǎn)大小為2k的子表中取出一塊，將其中一半分配給用的子表中取出一塊，將其中一半分配給用戶