算法與數(shù)據(jù)結(jié)構(gòu)：第八章 動態(tài)存儲管理

1、第八章 動態(tài)存儲管理8.1 概述8.2 邊界標(biāo)識法8.3 伙伴系統(tǒng)8.4 無用單元收集8.5 存儲緊縮習(xí)題1數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.1 概述動態(tài)存儲管理 指系統(tǒng)隨機(jī)地根據(jù)用戶程序申請空間的大小，進(jìn)行分配空間和回收不用空間所進(jìn)行的內(nèi)存管理。動態(tài)存儲管理的一種方法 建立可利用空間表(自由空間表/存儲池)，將所有可利用的空閑內(nèi)存塊鏈接起來。內(nèi)存空間的初始狀態(tài)系統(tǒng)運行一段時間后內(nèi)存的狀態(tài)2數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理三種基本分配策略首次擬合法：分配找到的第一個不小于n的空閑塊 的一部分。操作方便，查找快捷最佳擬合法：分配不小于n且最接近n的空閑塊的一部分。盡可能將大的空閑塊留給大程序使用最

2、差擬合法：分配不小于n且是最大的空閑塊的一部分。盡可能減少分配后無用碎片3數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.2 邊界標(biāo)識法雙向循環(huán)鏈表的應(yīng)用8.2.1 可利用空間表的結(jié)點結(jié)構(gòu) llink tag size rlink space uplink taghead(塊頭)foot(塊尾)size標(biāo)志位： tag= 1 占用塊 0 空閑塊塊尾的作用：簡化回收算法size以“字”為單位，head和foot各占一個字空間。4數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.2.2 分配算法 (申請容量為n的存儲空間)假設(shè)采用首次分配法，為避免過多碎片，設(shè)一常量e m-n e 將大小為m的塊全部分出 e 分出n大小，剩余留

3、下為使分配后剩余的小塊均勻分布在鏈表中，可利用空間鏈表的頭指針pav在每次分配之后，指向被分配塊的后繼塊pav5數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理算法思想 從p=pav開始查找一塊容量n的空閑塊，結(jié)果有三種情況1) p-size n且p-size -ne ：分配p整塊置tag=1從可利用空間表中刪除此塊pav指向被分配塊的后繼塊2) p-size n且p-size -ne ：分配p塊高地址部分大小為n的塊修改剩余塊的頭部設(shè)置剩余塊的尾部設(shè)置占用塊的頭部修改占用塊的尾部pav指向被分配塊的后繼塊3) 未找到，無法分配pn6數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.2.3 回收算法 設(shè)釋放塊的首地址指針為p，

4、大小為n，分四種情況：1) (p-1)-tag=1 且 (p+n)-tag=1 釋放塊的左右鄰塊均為占用塊 將釋放塊插入到pav所指的結(jié)點之后或之前；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 釋放塊的左右鄰塊均為空閑塊 從鏈表上刪除右鄰塊，將釋放塊和右鄰塊一起合并到左鄰塊的底部pn7數(shù)據(jù)結(jié)構(gòu)-第八

5、章 動態(tài)存儲管理比較邊界標(biāo)志法分別采用最佳適配和首次適配策略時，在數(shù)據(jù)結(jié)構(gòu)、分配算法和回收算法上有何不同。 最佳適配 首次適配 數(shù)據(jù)結(jié)構(gòu) 分配算法 回收算法 空閑塊應(yīng)由小到大順序鏈接，頭指針應(yīng)始終指向最小的空閑塊。采用單鏈表即可。無本質(zhì)區(qū)別。必須保持表的有序性要使大小不同的塊在分配時被隨機(jī)選擇，應(yīng)采用循環(huán)鏈表，并使頭指針經(jīng)常移動。進(jìn)行合并或在頭指針處插入即可邊界標(biāo)示法的問題 查找適合需要的塊，需要較多的時間 查找適合需要的塊的策略（最先/最佳/最壞），每種都有缺陷 碎片問題8數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.3 伙伴系統(tǒng)索引+雙循環(huán)鏈表伙伴系統(tǒng)原理伙伴系統(tǒng)的空閑塊大小以2k（k=0,1,2,m

6、） 標(biāo)定。按k值不同組織成多個雙循環(huán)鏈表。系統(tǒng)起始時只有一個空閑塊， 大小為 2m 。用戶申請內(nèi)存時，就將剛好滿足用戶需求的 2k大小的空閑塊分配給用戶；若不存在 2k 大小的空閑塊，就找到k值更大的空閑塊，將其分為兩半（互稱伙伴），按此直至分出2k大小給用戶，被分出的其它空閑塊加入對應(yīng)的循環(huán)鏈表中?；厥諘r，只有伙伴才合并，并將合并后的新空閑塊加入上一級大小的空閑塊鏈表中。9數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理“伙伴”的概念 當(dāng)把一個存儲塊分為大小相等的兩半時，則它們互為伙伴。大小為2k的伙伴的首地址之間的關(guān)系起始地址為p，大小為2k的內(nèi)存塊，其伙伴的起始地址為：buddy(p, k)= p+2k

7、=xx.x100.0 當(dāng) p mod 2k+1 =0 p-2k = xx.x000.0 當(dāng) p mod 2k+1 =2k(0)0000(8)10000000010010001100232322222222212100000010k個010數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.3.1 可利用空間表的結(jié)點結(jié)構(gòu) llink tag kval rlink space存儲管理方式按k值索引，相同k值的塊構(gòu)成子表(雙鏈表)header(塊頭)標(biāo)志位： tag= 1 占用塊 0 空閑塊202k2m0km 0 k 0 knodesize first11數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.3.2 分配算法 (申請容量

8、為n的存儲空間)算法思想1)計算k值：k=log2n2)從子表k開始找可用的塊 2.1)k子表有，取出分配，結(jié)束； 2.2)否則，若從k向下找到i (ik)子表有可用塊 (起始地址為p)，則取出2k分配，剩余的塊 大小 2i-1 2i-2 . . 2k 起始地址 p+2i-1 p+ 2i-2 . . p+2k 插入相應(yīng)的子表。p2i分配2k2i-1 2i-212數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.3.3 回收算法算法思想 考慮合并 設(shè)歸還塊的起始地址為p，大小為2k1)計算p的伙伴塊的地址q：q=buddy(p,k)2)若q空閑，合并出起始地址為p=minp，q， 大小為2k+1的塊； 將q從k

9、子表中刪除； 修改k：k=k+1，轉(zhuǎn)1)3)若q被占用，則將起始地址為p，大小為2k的塊插 入k子表中。ppqq2k 2k 2k2k13數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理8.3.4 Buddy算法分析多個空閑隊列，可以立即找到空閑塊避免了碎片問題申請內(nèi)存總是以2n字節(jié)滿足要求，塊內(nèi)浪費 例如：申請130字節(jié)，會分得256字節(jié);申請1514字節(jié)，會分得2048字節(jié)申請/釋放可能會導(dǎo)致連鎖切塊/合并，影響系統(tǒng)效率 例如：當(dāng)前只有一塊空閑，塊大小1M, 申請40字節(jié)，會導(dǎo)致12次切塊，用完立即歸還，導(dǎo)致12次合并。如果程序循環(huán)式申請40字節(jié)，然后歸還內(nèi)存，會導(dǎo)致系統(tǒng)頻繁忙碌。14數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理Lazy-Buddy 解決申請/釋放可能會導(dǎo)致連鎖切塊/合并。該合并時，通過一定“l(fā)azy”策略,暫時不合并，在合適的時機(jī)合并Slab 最早出現(xiàn)在Solaris, 在Linux中采用 避免了碎片問題，并且與內(nèi)存的分頁系統(tǒng)很好配合工作，分配歸還的效率很高。 基本思路：每次申請一個內(nèi)存頁面（4096字節(jié)）或者多個，切割成所需要的固定大小。不同大小的內(nèi)存申請，使用不同的空閑隊列。其它算法15數(shù)據(jù)結(jié)構(gòu)-第八章 動態(tài)存儲管理習(xí)題 假設(shè)利用邊界標(biāo)識法首次匹配策略分配，已知在某個時刻的可利用空間表如下： （1）請畫出當(dāng)系統(tǒng)回收一個起始地址為559、大小為4