考研數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理1第八章動(dòng)態(tài)存儲(chǔ)管理8.1概述8.2邊界標(biāo)識(shí)法8.3伙伴系統(tǒng)8.4例題解析數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理28.1概述[動(dòng)態(tài)存儲(chǔ)管理]

指系統(tǒng)隨機(jī)地根據(jù)用戶程序申請(qǐng)空間的大小，進(jìn)行分配空間和回收不用空間所進(jìn)行的內(nèi)存管理。[動(dòng)態(tài)存儲(chǔ)管理的一種方法]

建立可利用空間表(自由空間表/存儲(chǔ)池)，將所有可利用的空閑內(nèi)存塊鏈接起來。內(nèi)存空間的初始狀態(tài)系統(tǒng)運(yùn)行一段時(shí)間后內(nèi)存的狀態(tài)數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理3[三種基本分配策略]首次擬合法：分配找到的第一個(gè)不小于n的空閑塊的一部分。操作方便，查找快捷最佳擬合法：分配不小于n且最接近n的空閑塊的一部分。盡可能將大的空閑塊留給大程序使用最差擬合法：分配不小于n且是最大的空閑塊的一部分。盡可能減少分配后無用碎片數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理48.2邊界標(biāo)識(shí)法—雙向循環(huán)鏈表的應(yīng)用8.2.1可利用空間表的結(jié)點(diǎn)結(jié)構(gòu)

llinktagsizerlink

spaceuplinktagheader(塊頭)footer(塊尾)size標(biāo)志位：

tag=1占用塊

0空閑塊塊尾的作用：簡(jiǎn)化回收算法數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理5TYPEblkptr=^blk;blk=RECORDheader:RECORDllink,rlink:blkptr;tag:0..1;size:integerEND;space:ARRAY[1..size-2]OFdatatype;footer:RECORDuplink:blkptr;tag:0..1ENDEND;數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理68.2.2分配算法(申請(qǐng)容量為n的存儲(chǔ)空間)假設(shè)采用首次分配法，為避免過多碎片，設(shè)一常量em-ne將大小為m的塊全部分出

>e分出n大小，剩余留下為使分配后剩余的小塊均勻分布在鏈表中，可利用空間鏈表的頭指針pav在每次分配之后，指向被分配塊的后繼塊假設(shè)header和footer各占一個(gè)字的空間[算法思想]

從p=pav開始查找一塊容量n的空閑塊，結(jié)果有三種情況1)p^.sizen且p^.size-ne：分配p整塊置tag=1從可利用空間表中刪除此塊pav指向被分配塊的后繼塊數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理72)p^.sizen且p^.size-n>e：分配p塊高地址部分大小為n的塊修改剩余塊的頭部設(shè)置剩余塊的尾部設(shè)置占用塊的頭部修改占用塊的尾部pav指向被分配塊的后繼塊3)未找到，無法分配pnpav數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理88.2.3回收算法

設(shè)釋放塊的首地址指針為p，大小為n，分四種情況：1)(p-1)^.tag=1且(p+n)^.tag=1

釋放塊的左右鄰塊均為占用塊將釋放塊插入到pav所指的結(jié)點(diǎn)之后或之前；2)(p-1)^.tag=0且(p+n)^.tag=1

釋放塊的左鄰塊為空閑塊，右鄰塊為占用塊將釋放塊合并到左鄰塊的底部，并修改相應(yīng)的信息；3)(p-1)^.tag=1且(p+n)^.tag=0

釋放塊的左鄰塊為占用塊，右鄰塊為空閑塊將釋放塊合并到右鄰塊的頂部，并修改相應(yīng)的信息4)(p-1)^.tag=0且(p+n)^.tag=0

釋放塊的左右鄰塊均為空閑塊從鏈表上刪除右鄰塊，將釋放塊和右鄰塊一起合并到左鄰塊的底部pn數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理9比較邊界標(biāo)志法分別采用最佳適配和首次適配策略時(shí)，在數(shù)據(jù)結(jié)構(gòu)、分配算法和回收算法上有何不同。最佳適配首次適配數(shù)據(jù)結(jié)構(gòu)

分配算法回收算法空閑塊應(yīng)由小到大順序鏈接，頭指針應(yīng)始終指向最小的空閑塊。采用單鏈表即可。無本質(zhì)區(qū)別。必須保持表的有序性要使大小不同的塊在分配時(shí)被隨機(jī)選擇，應(yīng)采用循環(huán)鏈表，并使頭指針經(jīng)常移動(dòng)。進(jìn)行合并或在頭指針處插入即可數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理108.3伙伴系統(tǒng)—索引+雙循環(huán)鏈表[伙伴系統(tǒng)原理]伙伴系統(tǒng)的空閑塊大小以2k（k=0,1,2,…,m）標(biāo)定。按k值不同組織成多個(gè)雙循環(huán)鏈表。系統(tǒng)起始時(shí)只有一個(gè)空閑塊，大小為2m

。用戶申請(qǐng)內(nèi)存時(shí)，就將剛好滿足用戶需求的2k大小的空閑塊分配給用戶；若不存在2k大小的空閑塊，就找到k值更大的空閑塊，將其分為兩半（互稱伙伴），按此直至分出2k大小給用戶，被分出的其它空閑塊加入對(duì)應(yīng)的循環(huán)鏈表中。回收時(shí)，只有伙伴才合并，并將合并后的新空閑塊加入上一級(jí)大小的空閑塊鏈表中。數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理11[“伙伴”的概念]

當(dāng)把一個(gè)存儲(chǔ)塊分為大小相等的兩半時(shí)，則它們互為伙伴。[大小為2k的伙伴的首地址之間的關(guān)系]起始地址為p，大小為2k的內(nèi)存塊，其伙伴的起始地址為：buddy(p,k)=p+2k=xx..x100...0

當(dāng)pmod2k+1=0

p-2k=xx..x000...0當(dāng)pmod2k+1=2k(0)0000(8)10000000010010001100232322222222212100000010k個(gè)0數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理128.3.1可利用空間表的結(jié)點(diǎn)結(jié)構(gòu)llinktagkvalrlink

space[存儲(chǔ)管理方式]按k值索引，相同k值的塊構(gòu)成子表(雙鏈表)header(塊頭)標(biāo)志位：

tag=1占用塊

0空閑塊202k2m0km0k0knodesizefirst數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理13TYPEfreeptr=^freenodefreenode=RECORDheader:RECORDllink,rlink:freeptr;tag:0..1;kval:integerEND;space:ARRAY[1..nodesize-1]OFdatatype;END;headnode=RECORDnodesize:integer;first:freeptr;END;

freelist=ARRAY[0..m]OFheadnode;數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理148.3.2分配算法

(申請(qǐng)容量為n的存儲(chǔ)空間)[算法思想]1)計(jì)算k值：k=log2n2)從子表k開始找可用的塊

2.1)k子表有，取出分配，結(jié)束；

2.2)否則，若從k向下找到i(i>k)子表有可用塊

(起始地址為p)，則取出2k分配，剩余的塊

大小2i-12i-2......2k

起始地址p+2i-1p+2i-2......p+2k

插入相應(yīng)的子表。p2i分配2k2i-12i-2數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理158.3.3回收算法[算法思想]

考慮合并設(shè)歸還塊的起始地址為p，大小為2k1)計(jì)算p的伙伴塊的地址q：q=buddy(p,k)2)若q空閑，合并出起始地址為p=min{p，q}，大小為2k+1的塊；將q從k子表中刪除；修改k：k=k+1，轉(zhuǎn)1)3)若q被占用，則將起始地址為p，大小為2k的塊插入k子表中。ppqq2k2k2k2k數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理168.4例題解析1.二進(jìn)制地址為，作為大小為16的塊時(shí)，其伙伴的二進(jìn)制地址是什么？（）mod24+1=24其伙伴地址為：-24=-10000=數(shù)據(jù)結(jié)構(gòu)---第八章動(dòng)態(tài)存儲(chǔ)管理172.假設(shè)利用邊界標(biāo)識(shí)法首次匹配策略分配，已知在某個(gè)時(shí)刻的可利用空間表如下：（1）請(qǐng)畫出當(dāng)系統(tǒng)回收一個(gè)起始地址為559、大小為45的空閑塊之后的鏈表狀態(tài)；（2）請(qǐng)畫出系統(tǒng)在之后接受大小為100的請(qǐng)求后又回收地址為515、大小為44的空閑塊后的鏈表狀態(tài)。注：存儲(chǔ)塊頭部