動態(tài)儲存管理

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

第八章 動態(tài)存儲管理1本章內(nèi)容8.1

動態(tài)存儲管理概述8.2

可利用空間表及分配方法8.3

邊界標(biāo)識法8.4

伙伴系統(tǒng)2整理課件28.1動態(tài)存儲管理概述存儲管理——每一種數(shù)據(jù)結(jié)構(gòu)都必須研究該結(jié)構(gòu)的存儲結(jié)構(gòu)，但它是借助于某一高級語言中的變量說明來加以描述的，并沒有涉及到具體的存儲分配。 實(shí)際上，結(jié)構(gòu)中的每個數(shù)據(jù)元素都占有一定的內(nèi)存位置，在程序執(zhí)行的過程中，數(shù)據(jù)元素的存取是通過對應(yīng)的存儲單元來進(jìn)行的。 研究數(shù)據(jù)存儲與內(nèi)存單元對應(yīng)問題，就是存儲管理問題。3整理課件38.1動態(tài)存儲管理概述動態(tài)存儲管理的根本問題如何根據(jù)用戶提出的“請求〞來分配內(nèi)存。如何收回被用戶“釋放〞的內(nèi)存，以備新的“請求〞產(chǎn)生時重新進(jìn)行分配。4整理課件48.1動態(tài)存儲管理概述存儲原理計算機(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ū)域?yàn)椤罢加脡K〞；空閑塊：稱未曾分配的地址連續(xù)的內(nèi)存區(qū)為“空閑塊〞。

內(nèi)存的初始狀態(tài)U2U4

系統(tǒng)運(yùn)行若干時后U1U2U3U4

系統(tǒng)運(yùn)行初期5整理課件58.1動態(tài)存儲管理概述可利用空間表 內(nèi)存空間的所有可利用的空閑空間的情況記錄表。有兩種結(jié)構(gòu)：目錄表；鏈表：一個結(jié)點(diǎn)表示一個空閑塊。av150000100008000031000^41000059000鏈表目錄表空閑4100059000空閑800031000空閑1500010000內(nèi)存狀態(tài)01000025000310003900059000999996整理課件68.2可利用空間表及分配方法 本節(jié)主要討論利用可利用空間表進(jìn)行動態(tài)存儲分配的方法。目錄表法比較簡單，在?操作系統(tǒng)?課程中已詳細(xì)介紹。本節(jié)僅討論鏈表方法分配內(nèi)存。7整理課件78.2可利用空間表及分配方法三種結(jié)構(gòu)形式：第一種情況：系統(tǒng)運(yùn)行期間所有用戶請求分配的存儲量大小相同；具體作法是：開始運(yùn)行時將內(nèi)存區(qū)分割成假設(shè)干大小相同的塊，形成一可利用鏈表，分配和回收操作如同一般鏈表。第二種情況：系統(tǒng)運(yùn)行期間用戶請求分配的存儲量有假設(shè)干種大小的規(guī)格；具體作法是：先建立假設(shè)干個可利用空間表，同一鏈表中的結(jié)點(diǎn)小相同，分配/回收情況：結(jié)點(diǎn)大小與請求分配量相同時；結(jié)點(diǎn)大小比請求量大時；結(jié)點(diǎn)大小比請求量小時。8整理課件88.2可利用空間表及分配方法節(jié)點(diǎn)結(jié)構(gòu)tagtypelinkValuetype=0節(jié)點(diǎn)大小為2字節(jié)1節(jié)點(diǎn)大小為4字節(jié)2節(jié)點(diǎn)大小為8字節(jié)tag=0空閑塊1占用塊000000…av2101010…av4000000…av8可利用空間表9整理課件98.2可利用空間表及分配方法第三種情況：系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請求而變。工作情況：系統(tǒng)剛開始工作時，整個內(nèi)存空間是一個空閑塊，隨時著分配和回收的進(jìn)行，可利用空間表中的結(jié)點(diǎn)大小和個數(shù)也隨之而變。10整理課件108.2可利用空間表及分配方法分配方法假設(shè)某用戶需大小為n的內(nèi)存，而可利用空間僅有一塊大小為m≥n的空閑塊，那么只需將其中大小為n的一局部分配給申請的用戶，同時將乘余的m-n的局部作為一個結(jié)點(diǎn)留在鏈表中即可。假設(shè)可利用空間表有假設(shè)干個不小于n的空閑塊時，可有三種不同的分配方案：11整理課件118.2可利用空間表及分配方法首次擬合法分配找到的第一個不小于n的空閑塊的一局部。操作方便，查找快捷；最正確擬合法分配不小于n且最接近n的空閑塊的一局部。盡可能將大的空閑塊留給大程序使用；最壞擬合法分配不小于n且是最大的空閑塊的一局部。盡可能減少分配后無用碎片；12整理課件128.2可利用空間表及分配方法內(nèi)存的分配與回收分配根據(jù)申請內(nèi)存大小利用相應(yīng)分配策略分配給用戶所需空間；假設(shè)分配塊大小與申請大小相差不多，那么將此塊全局部給用戶；否那么，將分配塊分為兩局部，一局部給用戶使用，另一局部繼續(xù)留在可利用空間表中。回收測試回收塊前后相鄰內(nèi)存塊是否空閑；假設(shè)是那么需將回收塊與相鄰空閑塊合并成較大的空閑塊，再鏈入可利用空間表中。13整理課件138.3邊界標(biāo)識法用以進(jìn)行動態(tài)分區(qū)分配的一種管理方法節(jié)點(diǎn)結(jié)構(gòu)headllinktagsizerlinkspacefootuplinktag可利用空間表中的節(jié)點(diǎn)結(jié)構(gòu)圖可利用空間表中的節(jié)點(diǎn)結(jié)構(gòu)定義typestructWORD{//WORD,內(nèi)存數(shù)據(jù)類型union{//head和foot分別是節(jié)點(diǎn)的第一個和最后一個字WORD*llink;//頭部域，指向前趨節(jié)點(diǎn)WORD*rlink;//底部域，指向本節(jié)點(diǎn)頭部};inttag;//塊標(biāo)志:0空閑,1占用.頭部和尾部均有intsize;//頭部域，塊大小WORD*rlink;//頭部域，指向后繼節(jié)點(diǎn)otherTypeother;//字的其他局部}WORD,head,foot,*Space;//*Space:可利用空間指針類型#defineFootLoc(p)p+p->size-1//指向p所指節(jié)點(diǎn)的底部整理課件1414141414

8.3邊界標(biāo)識法分配算法：采取首次擬合法進(jìn)行分配。有兩個約定：假設(shè)待分配的內(nèi)存空閑塊容量為m個字，假設(shè)每次分配只從中分配n個字(n<m)給用戶，剩余m-n個字的節(jié)點(diǎn)仍留在表中，假設(shè)干次分配后，鏈表中存在大量容量極小，總分配不出去的空閑塊。解決的方法是：確定一個常量e，當(dāng)m-n<e時，就將容量為m的空閑塊整塊分配給用戶，否那么只分配其中n個字的塊，同時為了防止修改指針，約定將該節(jié)點(diǎn)中的高地址局部分配給用戶。假設(shè)每次分配都從同一節(jié)點(diǎn)開始查找，會使存儲量小的節(jié)點(diǎn)密集在頭指針pav所指節(jié)點(diǎn)附近，這會增大尋找到較大空間塊的時間。防止的方法是，每次從不同的節(jié)點(diǎn)開始查找，使剩余小塊均勻地分布在鏈表中。實(shí)現(xiàn)方法是，每次分配后，令指針pav指向剛進(jìn)行過分配的節(jié)點(diǎn)的后繼節(jié)點(diǎn)。15整理課件158.3邊界標(biāo)識法分配算法(見教材第200頁)SpaceAlloctionBoundTag(Space&pav,intn){//假設(shè)有不小于n的空閑塊，那么分配之，//并返回首地址；否那么返回NULL.//假設(shè)分配后可利用的空間表不空，//那么pav指向表中剛分配過的節(jié)點(diǎn)后繼節(jié)點(diǎn)for(p=pav;p&&p->size<n&&p->rlink!=pav;p=p->rlink;)//如果查找不小于n的空閑塊，找不到返回NULLif(!p||p->size<n)pav=NULL;else//p指向找到的空閑塊{f=FootLoc(p);//指向底部pav=p->rlink;//pav指向*p節(jié)點(diǎn)的后繼if(p->size-n<=e)//整塊分配，不保存<e的剩余量{if(pav==p)pav=NULL;//可利用空間表為空else//在表中刪除分配的節(jié)點(diǎn){pav->llink=p->llink;p->llink->rlink=pav;}p->tg=f->tag=1;//修改分配節(jié)點(diǎn)的頭部和底部標(biāo)志}

else

//分配該塊后的n個字

{f->tag=1;//修改分配塊的底部標(biāo)志

p->size-=n;//修改剩余塊大小

f=FootLoc(p);//指向剩余塊底部

f->tag=0;f->uplink=p;//設(shè)置剩余塊底部

p=f+1;//指向分配塊頭部

p->tag=1;p->size=n;//設(shè)置分配塊頭部

}returnp;//返回分配塊的首地址

}}16整理課件168.3邊界標(biāo)識法回收算法 用戶釋放占用塊后，系統(tǒng)需立即回收以備新的請求產(chǎn)生時進(jìn)行再分配。為了使物理地址毗鄰的空閑塊結(jié)合成一個盡可能大的結(jié)點(diǎn)，那么首先需要檢查剛釋放的占用塊的左、右緊鄰是否為空閑塊。 假設(shè)用戶釋放的內(nèi)存區(qū)的頭部地址為p，那么p-1=與其低地址緊鄰的內(nèi)存區(qū)的底部地址，即左鄰區(qū)；p+p－>size=與其高地址緊鄰的內(nèi)存區(qū)的頭部地址,即右鄰區(qū)。17整理課件178.3邊界標(biāo)識法釋放塊的左、右鄰區(qū)均為占用塊 此時只要作簡單插入即可。由于邊界標(biāo)識法在按首次擬合進(jìn)行分配時對可利用空間表的結(jié)構(gòu)沒有任何要求，那么新的空閑塊插入在表中任何位置均可。簡單的做法就是插入在pav指針?biāo)附Y(jié)點(diǎn)之前〔之后〕，描述如下：p－>tag=1=0; FootLoc(p)－>uplink=p;FootLoc(p)－>tag=0;if(!pav) pav=p－>llink=p－>rlink=p;else{ q=pav－>llink; p－>rlink=pav; p－>llink=q; q－>rlink=pav－>llink=p; pav=p;//令剛釋放的結(jié)點(diǎn)為下次分配時的最先查詢的結(jié)點(diǎn)}18整理課件188.3邊界標(biāo)識法釋放塊的左鄰區(qū)為空閑塊，而右鄰區(qū)為占用塊 由于釋放塊的頭部和左鄰空閑塊的底部毗鄰，因此只要改變左鄰空閑塊的結(jié)點(diǎn)：增加結(jié)點(diǎn)的size域的值且重新設(shè)置結(jié)點(diǎn)的底部即可。描述如下n=p－>size; //釋放塊的大小s=(p－1)－>uplink;//左鄰空閑塊的頭部地址s－>size+=n; //設(shè)置新的空閑塊大小f=p+n－1; //設(shè)置新的空閑塊底部f－>uplink=s;f－>tag=0;19整理課件198.3邊界標(biāo)識法釋放塊的右鄰區(qū)為空閑塊，而左鄰區(qū)為占用塊 由于釋放塊的底部和右鄰區(qū)空閑塊的頭部毗鄰，因此，當(dāng)表中結(jié)點(diǎn)由原來的右鄰空閑塊變成合并后的大空閑塊時，結(jié)點(diǎn)的底部位置不變,但頭部要變,由此,鏈表中的指針也要變。描述如下：t=p+p－>size; //右鄰空閑塊的頭部地址p－>tag=0; //p為合并后的結(jié)點(diǎn)頭部地址q=t－>llink;//q為*t結(jié)點(diǎn)在可利用空間表中的前驅(qū)結(jié)點(diǎn)的頭部地址p－>llink=q; //q指向*p的前驅(qū)q－>rlink=p;q1=t－>rlink;//q1為*t結(jié)點(diǎn)在可利用空間表中的后繼結(jié)點(diǎn)的頭部地址p－>rlink=q1; //q1指向*p的后繼q1－>llink=p;p－>size+=t－>size; //新的空閑塊的大小FootLoc(t)－>uplink=p; //底部指針指向新結(jié)點(diǎn)的頭部20整理課件208.3邊界標(biāo)識法釋放塊的左、右鄰區(qū)均為空閑塊 為使3個空閑塊連接在一起成為一個大結(jié)點(diǎn)留在可利用空間表中，只要增加左鄰空閑塊的space容量，同時在鏈表中刪去右鄰空閑塊結(jié)點(diǎn)即可。所作改變可描述如下：n=p－>size; //釋放塊的大小s=(p－1)－>uplink; //指向左鄰塊t=p+p－>size; //指向右鄰塊s－>size+=n+t－>rlink; //設(shè)置新結(jié)點(diǎn)的大小q=t－>llink; //q!=q1q1=t－>rlink;q－>rlink=q1; //刪去右鄰空閑塊結(jié)點(diǎn)q1－>llink=q;FootLoc(t)－>uplink=s; //新結(jié)點(diǎn)底部指針指向其頭部21整理課件218.3邊界標(biāo)識法例如，在上述情況下可利用空間表的變化如圖8.6所示。300001200001200000030000左鄰區(qū)釋放塊(a)釋放的存儲塊(b)左鄰區(qū)是空閑塊的情況(c)右鄰區(qū)是空閑塊的情況0035000015000右鄰區(qū)釋放塊右鄰區(qū)釋放塊22整理課件228.3邊界標(biāo)識法(d)左、右鄰區(qū)均是空閑塊的情況回收存儲塊后的可利用空間表0015000045000右鄰區(qū)釋放塊右鄰區(qū)左鄰區(qū)23整理課件238.3邊界標(biāo)識法邊界表示法的問題查找適合需要的塊，需要較多的時間查找適合需要的塊的策略〔最先/最正確/最壞〕，每種都有缺陷碎片問題24整理課件248.4

伙伴系統(tǒng)伙伴系統(tǒng)(buddysystem)：是操作系統(tǒng)中用到的一種動態(tài)存儲管理方法。它和邊界標(biāo)識法類似，在用戶提出申請時，分配一塊大小“恰當(dāng)〞的內(nèi)存區(qū)給用戶；反之，在用戶釋放內(nèi)存區(qū)時即收回?；锇橄到y(tǒng)的特點(diǎn)：無論是占用塊或空閑塊，其大小均為2的k次冪〔k為某個正整數(shù)〕。25整理課件258.4

伙伴系統(tǒng)結(jié)點(diǎn)結(jié)構(gòu)表頭結(jié)點(diǎn)headllinktagkvalrlinkspacenodesizefirst結(jié)點(diǎn)：右頭部head和space域組成。head：為結(jié)點(diǎn)頭部，是一個由4個域組成的記錄。llink：鏈域，指向同一鏈表中的前驅(qū)結(jié)點(diǎn)。rlink：鏈域，指向同一鏈表中的后繼結(jié)點(diǎn)。tag：標(biāo)志域，值為“0〞表示空閑塊，值為“1〞表示占用塊。kval：其值為2的冪次k。space：數(shù)據(jù)域，是一個大小為2k－1個字的連續(xù)內(nèi)存空間。表頭結(jié)點(diǎn)：由兩個域組成。nodesize：表示該鏈表中空閑塊的大小。first：該鏈表的表頭指針。26整理課件268.4

伙伴系統(tǒng)可利用空間表的結(jié)構(gòu)C語言描述#definem16//可利用空間總?cè)萘?4k字的2的冪次，子表的個數(shù)為m+1typedefstructWORD_b{ WORD_b*llink;//頭部域，指向前驅(qū)結(jié)點(diǎn)inttag;//塊標(biāo)志，0：空閑，1：占用。intskval;//塊大小，值為2的冪次kWORD_b*rlink;//頭部域，指向后繼結(jié)點(diǎn) OtherTypeother;//字的其他局部}WORD_b,head;//WORD：內(nèi)存字類型，結(jié)點(diǎn)的第一個字也稱headtypedefstructHeadNode{ intnodesize;//該鏈表的空閑塊的大小WORD_b*first;//該鏈表的表頭指針}FreeList[m+1];//表頭向量類型27整理課件278.4

伙伴系統(tǒng)例如：可利用空間表的初始狀態(tài)如以下圖所示，其中m個子表都為空表，只有大小為2m的鏈表中有一個結(jié)點(diǎn)，即整個存儲空間。(a)表的初始狀態(tài)nodesizefirst20212k2m0m伙伴系統(tǒng)中的可利用空間表28整理課件288.4

伙伴系統(tǒng)分配算法 當(dāng)用戶提出大小為n的內(nèi)存請求時，首先在可利用表上尋找結(jié)點(diǎn)大小與n相匹配的子表，假設(shè)此子表非空，那么將子表中任意一個結(jié)點(diǎn)分配之即可；假設(shè)此子表為空，那么需從結(jié)點(diǎn)更大的非空子表中去查找，直至找到一個空閑塊，那么將其中一局部分配給用戶，而將剩余局部插入相應(yīng)的子表中29整理課件298.4

伙伴系統(tǒng)算法實(shí)現(xiàn)WORD_bAllocBuddy(FreList&avail,intn){//avail[0..m]為可利用空間表，n為申請分配量，假設(shè)有不小于n的空//閑/塊，那么分配相應(yīng)的存儲塊，并返回其首地址；否那么返回NULLfor(k=0;k<=m&&(avail[k].nodesize<n+1||!avail[k].first);++k);//查找滿足分配要求的子表if(k>m)//分配失敗返回NULLreturnNULL; else//進(jìn)行分配{pa=avail[k].first;//指向可分配子表的第一個結(jié)點(diǎn)pre=pa－>llink;//分別指向前驅(qū)和后繼suc=pa－>rlink;if(pa==suc)//分配后該子表變成空表avail[k].first=NULL;else{//從子表中刪去*pa結(jié)點(diǎn)pre－>rlink=suc;suc－>llink=pre;avail[k].first=suc; }for(i=1;avail[k-i].nodesize>=n+1;++i){pi=pa+2k-i;pi－>rlink=pi;pi－>llink=pi;pi－>tag=0;pi－>kval=k－i;avail[k-i].first=pi;}//將剩余塊插入相應(yīng)子表

pa－>tag=1;pa－>kval=k－(――i);}//elsereturnpa;}//AllocBuddy30整理課件308.4

伙伴系統(tǒng)例子：假設(shè)分配前的可利用空間表的狀態(tài)如以下圖