動(dòng)態(tài)儲(chǔ)存管理ppt課件

1、1本章內(nèi)容本章內(nèi)容8.1動(dòng)態(tài)存儲(chǔ)管理概述動(dòng)態(tài)存儲(chǔ)管理概述8.2 可利用空間表及分配方法可利用空間表及分配方法8.3 邊界標(biāo)識(shí)法邊界標(biāo)識(shí)法8.4 伙伴系統(tǒng)伙伴系統(tǒng)2+存儲(chǔ)管理每一種數(shù)據(jù)結(jié)構(gòu)都必須研究該結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)，但它是借助于某一高級(jí)語(yǔ)言中的變量說(shuō)明來(lái)加以描述的，并沒(méi)有涉及到具體的存儲(chǔ)分配。實(shí)際上，結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都占有一定的內(nèi)存位置，在程序執(zhí)行的過(guò)程中，數(shù)據(jù)元素的存取是通過(guò)對(duì)應(yīng)的存儲(chǔ)單元來(lái)進(jìn)行的。研究數(shù)據(jù)存儲(chǔ)與內(nèi)存單元對(duì)應(yīng)問(wèn)題，就是存儲(chǔ)管理問(wèn)題。3+動(dòng)態(tài)存儲(chǔ)管理的基本問(wèn)題1. 如何根據(jù)用戶提出的“請(qǐng)求”來(lái)分配內(nèi)存。2. 如何收回被用戶“釋放”的內(nèi)存，以備新的“請(qǐng)求”產(chǎn)生時(shí)重新進(jìn)行分配。4

2、+存儲(chǔ)原理計(jì)算機(jī)內(nèi)存在剛工作時(shí)，空閑部分是一個(gè)整塊的連續(xù)區(qū)域；不斷運(yùn)行程序，多次申請(qǐng)和釋放內(nèi)存以后，空閑內(nèi)存不再連續(xù)，形成多個(gè)不連續(xù)的空閑區(qū)。動(dòng)態(tài)存儲(chǔ)管理：指系統(tǒng)隨機(jī)地根據(jù)用戶程序申請(qǐng)空間的大小，進(jìn)行分配空間和回收不用空間所進(jìn)行的內(nèi)存管理。占用塊：將系統(tǒng)已分配給用戶使用的地址連續(xù)的內(nèi)存區(qū)域?yàn)椤罢加脡K”；空閑塊：稱未曾分配的地址連續(xù)的內(nèi)存區(qū)為“空閑塊”。 內(nèi)存的初始狀態(tài)內(nèi)存的初始狀態(tài)U2U4 系統(tǒng)運(yùn)行若干時(shí)后系統(tǒng)運(yùn)行若干時(shí)后U1U2U3U4 系統(tǒng)運(yùn)行初期系統(tǒng)運(yùn)行初期5+可利用空間表內(nèi)存空間的所有可利用的空閑空間的情況記錄表。有兩種結(jié)構(gòu)：1. 目錄表；2. 鏈表：一個(gè)結(jié)點(diǎn)表示一個(gè)空閑塊。av100

3、003100059000鏈表鏈表目錄表目錄表內(nèi)存狀態(tài)內(nèi)存狀態(tài)01000025000310003900059000999996本節(jié)主要討論利用可利用空間表進(jìn)行動(dòng)態(tài)存儲(chǔ)分配的方法。目錄表法比較簡(jiǎn)單，在操作系統(tǒng)課程中已詳細(xì)介紹。本節(jié)僅討論鏈表方法分配內(nèi)存。7+三種結(jié)構(gòu)形式： 第一種情況：系統(tǒng)運(yùn)行期間所有用戶請(qǐng)求分配的存儲(chǔ)量大小相同；具體作法是：開(kāi)始運(yùn)行時(shí)將內(nèi)存區(qū)分割成若干大小相同的塊，形成一可利用鏈表，分配和回收操作如同一般鏈表。 第二種情況：系統(tǒng)運(yùn)行期間用戶請(qǐng)求分配的存儲(chǔ)量有若干種大小的規(guī)格；具體作法是：先建立若干個(gè)可利用空間表，同一鏈表中的結(jié)點(diǎn)小相同，分配/回收情況：結(jié)點(diǎn)大小與請(qǐng)求分配量相同時(shí)；

4、 結(jié)點(diǎn)大小比請(qǐng)求量大時(shí)； 結(jié)點(diǎn)大小比請(qǐng)求量小時(shí)。8type = 0 節(jié)點(diǎn)大小為節(jié)點(diǎn)大小為2字節(jié)字節(jié)1 節(jié)點(diǎn)大小為節(jié)點(diǎn)大小為4字節(jié)字節(jié)2 節(jié)點(diǎn)大小為節(jié)點(diǎn)大小為8字節(jié)字節(jié)tag = 0 空閑塊空閑塊1 占用塊占用塊av2av4av8可利用空間表可利用空間表9 第三種情況：系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請(qǐng)求而變。+工作情況：系統(tǒng)剛開(kāi)始工作時(shí)，整個(gè)內(nèi)存空間是一個(gè)空閑塊，隨時(shí)著分配和回收的進(jìn)行，可利用空間表中的結(jié)點(diǎn)大小和個(gè)數(shù)也隨之而變。10+分配方法 若某用戶需大小為n的內(nèi)存，而可利用空間僅有一塊大小為 mn 的空閑塊，則只需將其中大小為n 的一部分分配給申請(qǐng)的用戶，同時(shí)將乘余的

5、m-n 的部分作為一個(gè)結(jié)點(diǎn)留在鏈表中即可。 若可利用空間表有若干個(gè)不小于n的空閑塊時(shí)，可有三種不同的分配方案：111.首次擬合法 分配找到的第一個(gè)不小于n的空閑塊的一部分。 操作方便，查找快捷；2.最佳擬合法 分配不小于n且最接近n的空閑塊的一部分。 盡可能將大的空閑塊留給大程序使用；3.最壞擬合法 分配不小于n且是最大的空閑塊的一部分。 盡可能減少分配后無(wú)用碎片；12+內(nèi)存的分配與回收 分配根據(jù)申請(qǐng)內(nèi)存大小利用相應(yīng)分配策略分配給用戶所需空間；若分配塊大小與申請(qǐng)大小相差不多，則將此塊全部分給用戶；否則，將分配塊分為兩部分，一部分給用戶使用，另一部分繼續(xù)留在可利用空間表中。 回收測(cè)試回收塊前后相

6、鄰內(nèi)存塊是否空閑；若是則需將回收塊與相鄰空閑塊合并成較大的空閑塊，再鏈入可利用空間表中。13+用以進(jìn)行動(dòng)態(tài)分區(qū)分配的一種管理方法+節(jié)點(diǎn)結(jié)構(gòu)可利用空間表中的節(jié)點(diǎn)結(jié)構(gòu)圖可利用空間表中的節(jié)點(diǎn)結(jié)構(gòu)圖p 可利用空間表中的節(jié)點(diǎn)結(jié)構(gòu)定義可利用空間表中的節(jié)點(diǎn)結(jié)構(gòu)定義type struct WORD /WORD,內(nèi)存數(shù)據(jù)類型內(nèi)存數(shù)據(jù)類型 union /head 和和 foot 分別是節(jié)點(diǎn)的第一個(gè)和最后一個(gè)字分別是節(jié)點(diǎn)的第一個(gè)和最后一個(gè)字 WORD *llink; /頭部域，指向前趨節(jié)點(diǎn)頭部域，指向前趨節(jié)點(diǎn) WORD *rlink; /底部域，指向本節(jié)點(diǎn)頭部底部域，指向本節(jié)點(diǎn)頭部 ; int tag; /塊標(biāo)志塊

7、標(biāo)志: 0空閑空閑,1占用占用.頭部和尾部均頭部和尾部均有有 int size; /頭部域，塊大小頭部域，塊大小 WORD *rlink; /頭部域，指向后繼節(jié)點(diǎn)頭部域，指向后繼節(jié)點(diǎn) otherType other; /字的其他部分字的其他部分 WORD, head, foot, *Space; /*Space: 可利用空間指針類型可利用空間指針類型#define FootLoc(p) p+p-size-1 /指向指向p所指節(jié)點(diǎn)的底部所指節(jié)點(diǎn)的底部+分配算法：采取首次擬合法進(jìn)行分配。有兩個(gè)約定：1. 假設(shè)待分配的內(nèi)存空閑塊容量為m 個(gè)字，若每次分配只從中分配n個(gè)字(nm)給用戶，剩余m-n個(gè)字

8、的節(jié)點(diǎn)仍留在表中，若干次分配后，鏈表中存在大量容量極小，總分配不出去的空閑塊。解決的辦法是：確定一個(gè)常量e，當(dāng)m-nsizerlink!=pav; p=p-rlink;) /如果查找不小于如果查找不小于n的空閑塊，找不到返回的空閑塊，找不到返回NULL if (!p | p-sizerlink; /pav指向指向*p節(jié)點(diǎn)的后繼節(jié)點(diǎn)的后繼 if (p-size-n=e) /整塊分配，不保留整塊分配，不保留llink=p-llink;p-llink-rlink =pav; p-tg=f-tag=1; /修改分配節(jié)點(diǎn)的頭部和底部標(biāo)志修改分配節(jié)點(diǎn)的頭部和底部標(biāo)志 else /分配該塊后的分配該塊后的n

9、個(gè)字個(gè)字 f-tag=1; /修改分配塊的底部標(biāo)志修改分配塊的底部標(biāo)志 p-size - =n; /修改剩余塊大小修改剩余塊大小 f=FootLoc(p); /指向剩余塊底部指向剩余塊底部 f-tag=0; f-uplink=p; /設(shè)置剩余塊底部設(shè)置剩余塊底部 p=f+1; /指向分配塊頭部指向分配塊頭部 p-tag=1; p-size=n; /設(shè)置分配塊頭部設(shè)置分配塊頭部 return p; /返回分配塊的首地址返回分配塊的首地址 16+回收算法用戶釋放占用塊后，系統(tǒng)需立即回收以備新的請(qǐng)求產(chǎn)生時(shí)進(jìn)行再分配。為了使物理地址毗鄰的空閑塊結(jié)合成一個(gè)盡可能大的結(jié)點(diǎn)，則首先需要檢查剛釋放的占用塊的左

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

11、llink;prlink = pav;pllink = q;qrlink = pavllink = p;pav = p; /令剛釋放的結(jié)點(diǎn)為下次分配時(shí)的最先查詢的結(jié)點(diǎn)令剛釋放的結(jié)點(diǎn)為下次分配時(shí)的最先查詢的結(jié)點(diǎn)18b)釋放塊的左鄰區(qū)為空閑塊，而右鄰區(qū)為占用塊由于釋放塊的頭部和左鄰空閑塊的底部毗鄰，因此只要改變左鄰空閑塊的結(jié)點(diǎn)：增加結(jié)點(diǎn)的size域的值且重新設(shè)置結(jié)點(diǎn)的底部即可。描述如下n = psize; /釋放塊的大小釋放塊的大小s = (p1)uplink; /左鄰空閑塊的頭部地址左鄰空閑塊的頭部地址ssize + = n; /設(shè)置新的空閑塊大小設(shè)置新的空閑塊大小f = p + n1; /設(shè)置

12、新的空閑塊底部設(shè)置新的空閑塊底部fuplink = s;ftag = 0;19c)釋放塊的右鄰區(qū)為空閑塊，而左鄰區(qū)為占用塊由于釋放塊的底部和右鄰區(qū)空閑塊的頭部毗鄰，因此，當(dāng)表中結(jié)點(diǎn)由原來(lái)的右鄰空閑塊變成合并后的大空閑塊時(shí)，結(jié)點(diǎn)的底部位置不變,但頭部要變,由此,鏈表中的指針也要變。描述如下：t = 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)在可利用空間表中的前驅(qū)結(jié)點(diǎn)的頭部地址pllink = q;/q指向指向*p的前驅(qū)的前驅(qū)qrli

13、nk = 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)的頭部20d)釋放塊的左、右鄰區(qū)均為空閑塊為使3個(gè)空閑塊連接在一起成為一個(gè)大結(jié)點(diǎn)留在可利用空間表中，只要增加左鄰空閑塊的space容量，同時(shí)在鏈表中刪去右鄰空閑塊結(jié)點(diǎn)即可。所作改變可描述如下：n = psize; /釋放塊的大小釋放塊

14、的大小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;FootLoc (t)uplink = s; /新結(jié)點(diǎn)底部指針指向其頭部新結(jié)點(diǎn)底部指針指向其頭部21例如，在上述情況下可利用空間表的變化如圖例如，在上述情況下可利用空間表的變化如圖8.6所示。所示。30 0001 20 000120 00000 30 000

15、左鄰區(qū)左鄰區(qū)釋放塊釋放塊(a) 釋放的存儲(chǔ)塊釋放的存儲(chǔ)塊(b) 左鄰區(qū)是空閑塊的情況左鄰區(qū)是空閑塊的情況(c) 右鄰區(qū)是空閑塊的情況右鄰區(qū)是空閑塊的情況00 35 0000 15 000右鄰區(qū)右鄰區(qū)釋放塊釋放塊右鄰區(qū)右鄰區(qū)釋放塊釋放塊22(d) 左、右鄰區(qū)均是空閑塊的情況左、右鄰區(qū)均是空閑塊的情況回收存儲(chǔ)塊后的可利用空間表回收存儲(chǔ)塊后的可利用空間表00 15 0000 45 000右鄰區(qū)右鄰區(qū)釋放塊釋放塊右鄰區(qū)右鄰區(qū)左鄰區(qū)左鄰區(qū)23+邊界表示法的問(wèn)題 查找適合需要的塊，需要較多的時(shí)間 查找適合需要的塊的策略（最先/最佳/最壞），每種都有缺陷 碎片問(wèn)題24+伙伴系統(tǒng)(buddy system)：

16、是操作系統(tǒng)中用到的一種動(dòng)態(tài)存儲(chǔ)管理方法。它和邊界標(biāo)識(shí)法類似，在用戶提出申請(qǐng)時(shí)，分配一塊大小“恰當(dāng)”的內(nèi)存區(qū)給用戶；反之，在用戶釋放內(nèi)存區(qū)時(shí)即收回。+伙伴系統(tǒng)的特點(diǎn)：無(wú)論是占用塊或空閑塊，其大小均為2的k次冪（k為某個(gè)正整數(shù)）。25+結(jié)點(diǎn)結(jié)構(gòu)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)headllink tag kval rlinkspacenodesize firstn 結(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： 鏈域，指

17、向同一鏈表中的后繼結(jié)點(diǎn)。鏈域，指向同一鏈表中的后繼結(jié)點(diǎn)。 tag： 標(biāo)志域，值為標(biāo)志域，值為“0”表示空閑塊，值為表示空閑塊，值為“1”表示占用塊。表示占用塊。 kval： 其值為其值為2的冪次的冪次k。 space：數(shù)據(jù)域，是一個(gè)大小為：數(shù)據(jù)域，是一個(gè)大小為2k1個(gè)字的連續(xù)內(nèi)存空間。個(gè)字的連續(xù)內(nèi)存空間。n 表頭結(jié)點(diǎn)：由兩個(gè)域組成。表頭結(jié)點(diǎn)：由兩個(gè)域組成。 nodesize：表示該鏈表中空閑塊的大小。：表示該鏈表中空閑塊的大小。 first：該鏈表的表頭指針。：該鏈表的表頭指針。26+可利用空間表的結(jié)構(gòu)C語(yǔ)言描述#define m 16 /可利用空間總?cè)萘靠衫每臻g總?cè)萘?4k字的字的2的冪次

18、，子表的個(gè)數(shù)為的冪次，子表的個(gè)數(shù)為m+1typedef struct WORD_b WORD_b *llink; /頭部域，指向前驅(qū)結(jié)點(diǎn)頭部域，指向前驅(qū)結(jié)點(diǎn) int tag; /塊標(biāo)志，塊標(biāo)志，0：空閑，：空閑，1：占用。：占用。 int skval; /塊大小，值為塊大小，值為2的冪次的冪次k WORD_b *rlink; /頭部域，指向后繼結(jié)點(diǎn)頭部域，指向后繼結(jié)點(diǎn) OtherType other; /字的其他部分字的其他部分 WORD_b, head; /WORD：內(nèi)存字類型，結(jié)點(diǎn)的第一個(gè)字也稱：內(nèi)存字類型，結(jié)點(diǎn)的第一個(gè)字也稱headtypedef struct HeadNode int

19、nodesize; /該鏈表的空閑塊的大小該鏈表的空閑塊的大小 WORD_b *first; /該鏈表的表頭指針該鏈表的表頭指針 FreeListm + 1; /表頭向量類型表頭向量類型27+示例：可利用空間表的初始狀態(tài)如下圖所示，其中m個(gè)子表都為空表，只有大小為2m的鏈表中有一個(gè)結(jié)點(diǎn)，即整個(gè)存儲(chǔ)空間。(a) 表的初始狀態(tài)表的初始狀態(tài)nodesize first20212k2m0 m伙伴系統(tǒng)中的可利用空間表伙伴系統(tǒng)中的可利用空間表28+分配算法當(dāng)用戶提出大小為n的內(nèi)存請(qǐng)求時(shí)，首先在可利用表上尋找結(jié)點(diǎn)大小與n相匹配的子表，若此子表非空，則將子表中任意一個(gè)結(jié)點(diǎn)分配之即可；若此子表為空，則需從結(jié)點(diǎn)更

20、大的非空子表中去查找，直至找到一個(gè)空閑塊，則將其中一部分分配給用戶，而將剩余部分插入相應(yīng)的子表中29+算法實(shí)現(xiàn)WORD_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) /分配失敗返回分配失敗返回NULL return NULL; else /進(jìn)行分配進(jìn)

21、行分配 pa = availk.first; /指向可分配子表的第一個(gè)結(jié)點(diǎn)指向可分配子表的第一個(gè)結(jié)點(diǎn) pre = pallink; /分別指向前驅(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; for (i=1; availk-i.nodesize=n+1; +i) pi = pa + 2k-i; pirlink = pi; pillink = pi; pitag = 0; pikval = ki; availk-i.first = pi; /將剩余塊插入相應(yīng)子表將剩余塊插入相應(yīng)子表 patag = 1; pakval = k(i); / else return pa; / AllocBuddy30+例子： 假設(shè)分配前的可利用空間表的狀態(tài)如下圖所示。若2k-1n2k-1，又第k1個(gè)子表不空，