動態(tài)儲存管理ppt課件

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

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

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

4、 結(jié)點(diǎn)大小比請求量大時； 結(jié)點(diǎn)大小比請求量小時。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)存塊的大小不固定，可以隨請求而變。+工作情況：系統(tǒng)剛開始工作時，整個內(nèi)存空間是一個空閑塊，隨時著分配和回收的進(jìn)行，可利用空間表中的結(jié)點(diǎn)大小和個數(shù)也隨之而變。10+分配方法 若某用戶需大小為n的內(nèi)存，而可利用空間僅有一塊大小為 mn 的空閑塊，則只需將其中大小為n 的一部分分配給申請的用戶，同時將乘余的

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

6、鄰內(nèi)存塊是否空閑；若是則需將回收塊與相鄰空閑塊合并成較大的空閑塊，再鏈入可利用空間表中。13+用以進(jìn)行動態(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)的第一個和最后一個字分別是節(jié)點(diǎn)的第一個和最后一個字 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)行分配。有兩個約定：1. 假設(shè)待分配的內(nèi)存空閑塊容量為m 個字，若每次分配只從中分配n個字(nm)給用戶，剩余m-n個字

8、的節(jié)點(diǎn)仍留在表中，若干次分配后，鏈表中存在大量容量極小，總分配不出去的空閑塊。解決的辦法是：確定一個常量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、個字個字 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)需立即回收以備新的請求產(chǎn)生時進(jìn)行再分配。為了使物理地址毗鄰的空閑塊結(jié)合成一個盡可能大的結(jié)點(diǎn)，則首先需要檢查剛釋放的占用塊的左

10、、右緊鄰是否為空閑塊。假設(shè)用戶釋放的內(nèi)存區(qū)的頭部地址為p，則p-1=與其低地址緊鄰的內(nèi)存區(qū)的底部地址，即左鄰區(qū)；p+psize=與其高地址緊鄰的內(nèi)存區(qū)的頭部地址,即右鄰區(qū)。17a)釋放塊的左、右鄰區(qū)均為占用塊此時只要作簡單插入即可。由于邊界標(biāo)識法在按首次擬合進(jìn)行分配時對可利用空間表的結(jié)構(gòu)沒有任何要求，則新的空閑塊插入在表中任何位置均可。簡單的做法就是插入在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)為下次分配時的最先查詢的結(jié)點(diǎn)令剛釋放的結(jié)點(diǎn)為下次分配時的最先查詢的結(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)由原來的右鄰空閑塊變成合并后的大空閑塊時，結(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個空閑塊連接在一起成為一個大結(jié)點(diǎn)留在可利用空間表中，只要增加左鄰空閑塊的space容量，同時在鏈表中刪去右鄰空閑塊結(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) 釋放的存儲塊釋放的存儲塊(b) 左鄰區(qū)是空閑塊的情況左鄰區(qū)是空閑塊的情況(c) 右鄰區(qū)是空閑塊的情況右鄰區(qū)是空閑塊的情況00 35 0000 15 000右鄰區(qū)右鄰區(qū)釋放塊釋放塊右鄰區(qū)右鄰區(qū)釋放塊釋放塊22(d) 左、右鄰區(qū)均是空閑塊的情況左、右鄰區(qū)均是空閑塊的情況回收存儲塊后的可利用空間表回收存儲塊后的可利用空間表00 15 0000 45 000右鄰區(qū)右鄰區(qū)釋放塊釋放塊右鄰區(qū)右鄰區(qū)左鄰區(qū)左鄰區(qū)23+邊界表示法的問題 查找適合需要的塊，需要較多的時間 查找適合需要的塊的策略（最先/最佳/最壞），每種都有缺陷 碎片問題24+伙伴系統(tǒng)(buddy system)：

16、是操作系統(tǒng)中用到的一種動態(tài)存儲管理方法。它和邊界標(biāo)識法類似，在用戶提出申請時，分配一塊大小“恰當(dāng)”的內(nèi)存區(qū)給用戶；反之，在用戶釋放內(nèi)存區(qū)時即收回。+伙伴系統(tǒng)的特點(diǎn)：無論是占用塊或空閑塊，其大小均為2的k次冪（k為某個正整數(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)頭部，是一個由：為結(jié)點(diǎn)頭部，是一個由4個域組成的記錄。個域組成的記錄。 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ù)域，是一個大小為：數(shù)據(jù)域，是一個大小為2k1個字的連續(xù)內(nèi)存空間。個字的連續(xù)內(nèi)存空間。n 表頭結(jié)點(diǎn)：由兩個域組成。表頭結(jié)點(diǎn)：由兩個域組成。 nodesize：表示該鏈表中空閑塊的大小。：表示該鏈表中空閑塊的大小。 first：該鏈表的表頭指針。：該鏈表的表頭指針。26+可利用空間表的結(jié)構(gòu)C語言描述#define m 16 /可利用空間總?cè)萘靠衫每臻g總?cè)萘?4k字的字的2的冪次

18、，子表的個數(shù)為的冪次，子表的個數(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)的第一個字也稱：內(nèi)存字類型，結(jié)點(diǎn)的第一個字也稱headtypedef struct HeadNode int

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

20、大的非空子表中去查找，直至找到一個空閑塊，則將其中一部分分配給用戶，而將剩余部分插入相應(yīng)的子表中29+算法實現(xiàn)WORD_b AllocBuddy (FreList &avail, int n) /avail0.m為可利用空間表，為可利用空間表，n為申請分配量，若有不小于為申請分配量，若有不小于n的空的空 /閑閑/塊，則分配相應(yīng)的存儲塊，并返回其首地址；否則返回塊，則分配相應(yīng)的存儲塊，并返回其首地址；否則返回NULL for (k = 0; k = m & (availk.nodesize m) /分配失敗返回分配失敗返回NULL return NULL; else /進(jìn)行分配進(jìn)

21、行分配 pa = availk.first; /指向可分配子表的第一個結(jié)點(diǎn)指向可分配子表的第一個結(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個子表不空，