(C語言詳細(xì)版)第八章 動態(tài)存儲管理

重點(diǎn)：內(nèi)存空間的分配與回收算法，以及可利用空間表的結(jié)構(gòu)。難點(diǎn)：無用單元收集算法的理解與掌握。第八章動態(tài)存儲管理1/33第八章動態(tài)存儲管理8.1概述8.2可利用空間表及分配方法8.3邊界標(biāo)識法8.4伙伴系統(tǒng)8.5無用單元收集8.6存儲緊縮2/338.1概述(1)程序中的變量如何存儲管理？早期，由程序員自己完成：

在執(zhí)行程序之前，先需將用機(jī)器語言或匯編語言編寫的程序輸送到內(nèi)存的某個固定區(qū)域上，并預(yù)先給變量和數(shù)據(jù)分配好對應(yīng)的內(nèi)存地址(絕對或相對地址)有了高級語言后，程序員不需直接和內(nèi)存地址打交道：

變量對應(yīng)的內(nèi)存地址都是由編譯程序在編譯或執(zhí)行時進(jìn)行分配操作系統(tǒng)單用戶操作系統(tǒng)：內(nèi)存空間被劃分為系統(tǒng)區(qū)(供系統(tǒng)程序使用)和用戶區(qū)(供單一的用戶程序所使用)多道程序設(shè)計(jì)：多個用戶程序共享一個內(nèi)存區(qū)域，每個用戶程序使用的內(nèi)存就由操作系統(tǒng)來進(jìn)行分配。存儲管理是操作系統(tǒng)和編譯程序的一個復(fù)雜且重要的問題！3/338.1概述(2)動態(tài)存儲管理的基本問題系統(tǒng)如何用用戶提出的“請求”分配內(nèi)存？如何回收那些用戶不再使用而“釋放”的內(nèi)存，以備新的“請求”產(chǎn)生時重新進(jìn)行分配？用戶提出的“請求”：可能是進(jìn)入系統(tǒng)的一個作業(yè)也可能是程序執(zhí)行過程中的一個動態(tài)變量系統(tǒng)每次分配給用戶都是一個地址連續(xù)的內(nèi)存區(qū)。稱已分配給用戶使用的地址連續(xù)的內(nèi)存區(qū)為“占用塊”，稱未曾分配的地址連續(xù)的內(nèi)存區(qū)為“可利用空間塊”或“空閑塊”。4/338.1概述(3)U1U2U3U4U5U6U7U8系統(tǒng)運(yùn)行初期U1U3U4U6U8系統(tǒng)運(yùn)行若干時間之后占用塊空閑塊動態(tài)存儲管理系統(tǒng)剛開工時5/338.1概述(4)當(dāng)有新的用戶進(jìn)入系統(tǒng)請求分配內(nèi)存，系統(tǒng)將如何做呢？策略一：從高地址的空閑塊中進(jìn)行分配，當(dāng)分配無法進(jìn)行時，系統(tǒng)回收所有用戶不再使用的空閑塊，并重新組織內(nèi)存，將所有空閑的內(nèi)存區(qū)連接在一起成為一個大的空閑塊。策略二：從所有空閑塊中找出一個“合適”的空閑塊分配之。

系統(tǒng)需要建立一張記錄所有空閑塊的“可利用空間表”，它可以是“目錄表”，也可以是“鏈表”。U1U3U4U6U86/338.1概述(5)U60100002500031000390005900099999(a)內(nèi)存狀態(tài)(b)目錄表015,000av(c)鏈表08,000041,000^7/338.2可利用空間表及分配方法討論利用可利用空間表進(jìn)行動態(tài)存儲分配的方法.目錄表簡單，將在操作系統(tǒng)課程中介紹這里僅就鏈表的情況進(jìn)行討論8/338.2可利用空間表及分配方法(1)可利用空間表的表示——鏈表一個空閑塊一個結(jié)點(diǎn)用戶請求分配時，系統(tǒng)從表中刪除一個結(jié)點(diǎn)分配之用戶釋放所占內(nèi)存時，系統(tǒng)即回收并將它插入到表中根據(jù)系統(tǒng)運(yùn)行的不同情況，可利用空間表有不同的結(jié)構(gòu)形式系統(tǒng)運(yùn)行期間所有用戶請求分配的存儲量大小相同由于表中結(jié)點(diǎn)大小相同，則分配時無需查找可以用鏈棧實(shí)現(xiàn)——操作系統(tǒng)中的固定分區(qū)管理9/338.2可利用空間表及分配方法(2)系統(tǒng)運(yùn)行期間用戶請求分配的存儲量有若干種大小的規(guī)格建立若干個可利用空間表，同一鏈表中的結(jié)點(diǎn)大小相同每個結(jié)點(diǎn)的第一個字設(shè)有鏈域(link)：指向同一鏈表中下一結(jié)點(diǎn)的指針標(biāo)志域(tag)：0-空閑塊、1-占用塊結(jié)點(diǎn)類型域(type)：區(qū)分大小不同的結(jié)點(diǎn)tagtypelinkvalue00av20000^01av40101^02av80202^10/338.2可利用空間表及分配方法(3)系統(tǒng)運(yùn)行期間用戶請求分配的存儲量有若干種大小的規(guī)格分配從結(jié)點(diǎn)大小和請求分配的量相同的鏈表中查找結(jié)點(diǎn)并分配之若沒有，則從結(jié)點(diǎn)較大的鏈表中查找結(jié)點(diǎn)，將其中一部分分配給用戶，剩余的插入到相應(yīng)大小的鏈表中若各鏈表都沒有合適的結(jié)點(diǎn)，則要執(zhí)行“存儲緊縮”將小塊合并回收將釋放的空閑塊插入到相應(yīng)大小的鏈表的表頭11/338.2可利用空間表及分配方法(4)系統(tǒng)運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定開始時，整個內(nèi)存空間是一個空閑塊隨著分配和回收的進(jìn)行，可利用空間表中的結(jié)點(diǎn)大小和個數(shù)也隨之而變結(jié)點(diǎn)的結(jié)構(gòu)鏈域(link)：指向同一鏈表中下一結(jié)點(diǎn)的指針標(biāo)志域(tag)：0-空閑塊、1-占用塊大小域(size)：指示該空閑塊的存儲量space：地址連續(xù)的內(nèi)存空間——操作系統(tǒng)中的可變分區(qū)管理tagsizelinkspace12/338.2可利用空間表及分配方法(5)可利用空間表中的結(jié)點(diǎn)大小不同時的分配方法假設(shè)用戶需大小為n的內(nèi)存若鏈表中僅有一塊大小為m≥n的空閑塊：將其中大小為n的一部分分配給用戶，剩余大小為m-n的作為一個結(jié)點(diǎn)留在鏈表中若鏈表中有若干個不小于n的空閑塊：有三種分配策略首次擬合法：取第一個不小于n的空閑塊最佳擬合法：取表中一個不小于n且最接近n的空閑塊

表按空閑塊大小自小到大有序，適于大小范圍較廣的系統(tǒng)最差擬合法：取表中不小于n且是表中最大的空閑塊

表按空閑塊大小自大至小有序，適于大小范圍較窄的系統(tǒng)13/338.3邊界標(biāo)識法(1)邊界標(biāo)識法(Boundarytagmethod)可利用空間表：雙重循環(huán)鏈表分配：首次擬合或最佳擬合特點(diǎn)每個內(nèi)存區(qū)的頭部和底部兩個邊界上分別設(shè)有標(biāo)識，以標(biāo)識該區(qū)域?yàn)檎加脡K或空閑塊，使得在回收時易于判別在物理位置上與其相鄰的內(nèi)存區(qū)域是否為空閑塊，以便將所有地址連續(xù)的空閑存儲區(qū)組合成一個盡可能大的空閑塊。14/338.3邊界標(biāo)識法(2)可利用空間表的結(jié)構(gòu)llinktagsizerlinkspaceuplinktagheadfoottypedefstructWORD{//內(nèi)存字類型union{WORD*llink;

//指向前驅(qū)結(jié)點(diǎn)WORD*uplink;//指向本結(jié)點(diǎn)頭部};inttag;//0-空閑;1-占用intsize;//塊大小WORD*rlink;//指向后繼結(jié)點(diǎn)OtherTypeother;//字的其它部分}WORD,head,foot,*Space;//指向p所指結(jié)點(diǎn)的底部#defineFootLoc(p)p+p->size-115/338.3邊界標(biāo)識法(3)分配算法(算法8.1P200)假設(shè)用首次擬合法進(jìn)行分配，請求分配的存儲量為n。為使整個系統(tǒng)更有效地運(yùn)行，在邊界標(biāo)識法中作如下約定假設(shè)找到的待分配空閑塊的容量為m個字(包括頭部)，選定一個適當(dāng)?shù)某Ａ縠，當(dāng)m-n≤e時，就將容量為m的空閑塊整塊分配給用戶；否則只分配其中n個字的內(nèi)存塊。

為避免修改指針，約定將該結(jié)點(diǎn)中的高地址部分分配給用戶。

每次分配從不同的結(jié)點(diǎn)(如剛進(jìn)行分配的結(jié)點(diǎn)的后繼)開始進(jìn)行查找，使分配后剩余的小塊均勻地分布在鏈表中?！苊庑K集中在頭指針?biāo)附Y(jié)點(diǎn)附近，從而增加查詢較大空閑塊的時間16/338.3邊界標(biāo)識法(4)回收算法(P201~203)假設(shè)用戶釋放的內(nèi)存區(qū)的頭部地址為p要檢查剛釋放的占用塊M的左、右緊鄰是否為空閑塊與M低地址緊鄰的內(nèi)存區(qū)的底部地址為p-1與M高地址緊鄰的內(nèi)存區(qū)的頭部地址為p+p->sizeM的左、右鄰區(qū)均為占用塊：簡單插入M的左鄰區(qū)為空閑塊，右鄰區(qū)為占用塊：合并左鄰區(qū)和M，增加左鄰空閑塊結(jié)點(diǎn)的size域的值，重新設(shè)置結(jié)點(diǎn)的底部M的右鄰區(qū)為空閑塊，左鄰區(qū)為占用塊：合并M和右鄰區(qū)，結(jié)點(diǎn)的底部位置不變，頭部要變，鏈表的指針也要變M的左、右鄰區(qū)均為空閑塊：合并左鄰區(qū)、M和右鄰區(qū)，增加左鄰空閑塊的size值，在鏈表中刪除右鄰空閑塊結(jié)點(diǎn)，修改底部17/338.4伙伴系統(tǒng)(1)伙伴系統(tǒng)(buddysystem)與邊界標(biāo)識法類似不同點(diǎn)是：在伙伴系統(tǒng)中，無論是占用塊或空閑塊，其大小均為2的k次冪(k為某個正整數(shù))可利用空間表若可利用內(nèi)存容量為2m個字，則空閑塊的大小只能是20、21、…、2m所有大小相同的空閑塊建于一張子表中，每個子表是一個雙重循環(huán)鏈表，可能有m+1個子表將m+1個表頭指針用向量結(jié)構(gòu)組織成一個表18/338.4伙伴系統(tǒng)(2)可利用空間表的結(jié)構(gòu)llinktagkvalrlinkspacehead#definem16typedefstructWORD{//內(nèi)存字類型WORD*llink;

//指向前驅(qū)結(jié)點(diǎn)inttag;//0-空閑;1-占用intkval;//塊大小,值為2的冪次kWORD*rlink;//指向后繼結(jié)點(diǎn)OtherTypeother;//字的其它部分}WORD,head;

typedefstructHeadNode{intnodesize;//該鏈表的空閑塊的大小WORD*first;//該鏈表的表頭指針}FreeList[m+1];//表頭向量類型20…2k-12k…2m…19/338.4伙伴系統(tǒng)(3)分配算法(算法8.2P205)假設(shè)用請求分配的存儲量為n。若2k-1<n≤2k-1，即第k+1個子表不空，則只刪除此鏈表中第一個結(jié)點(diǎn)并分配給用戶即可若2k-2<n≤2k-1-1，結(jié)點(diǎn)大小為2k-1的子表為空，則從結(jié)點(diǎn)大小為2k的子表中取出一塊，將其中一半分配給用戶，剩余的一半作為一個新結(jié)點(diǎn)插入在結(jié)點(diǎn)大小為2k-1的子表中若2k-i-1<n≤2k-i-1(i為小于k的整數(shù))，并且所有結(jié)點(diǎn)小于2k的子表均為空，則同樣需從結(jié)點(diǎn)大小為2k的子表中取出一塊，將其中2k-i分配給用戶，剩余部分分割成若干個結(jié)點(diǎn)分別插入在結(jié)點(diǎn)大小為2k-i、2k-i+1、…、2k-1的子表中。20/338.4伙伴系統(tǒng)(4)回收算法(P205，206)假設(shè)用戶釋放的內(nèi)存區(qū)的起始地址為p，塊的大小為2k伙伴系統(tǒng)僅考慮互為“伙伴”的兩個空閑塊的歸并伙伴：兩個由同一大塊分裂出來的小塊就稱為“互為伙伴”。假設(shè)p為大小為2k的空閑塊的初始地址，且pMOD2k+1=0，則初始地址為p和p+2k的兩個空閑塊互為伙伴。21/338.4伙伴系統(tǒng)(5)判別其伙伴是否為空閑塊若是，則在相應(yīng)子表中找到其伙伴并刪除之，然后再判別合并后的空閑塊的伙伴是否是空閑塊若否，則只要將釋放的空閑塊簡單插入在相應(yīng)子表中即可伙伴塊的起始地址對伙伴系統(tǒng)的評價優(yōu)點(diǎn)：算法簡單、速度快缺點(diǎn)：由于只歸并伙伴而容易產(chǎn)生碎片22/338.5無用單元收集(1)8.2~8.4節(jié)討論的存儲管理系統(tǒng)中，用戶必須明確給出“請求”和“釋放”的信息

因?yàn)橛脩舻氖杪┗蚪Y(jié)構(gòu)本身的原因致使系統(tǒng)在不恰當(dāng)?shù)臅r候或沒有進(jìn)行回收而產(chǎn)生“無用單元”或“懸掛訪問”的問題。無用單元：那些用戶不再使用而系統(tǒng)沒有回收的結(jié)構(gòu)和變量。

例：p=malloc(size);….p=NULL;懸掛訪問：訪問已經(jīng)被釋放的結(jié)點(diǎn)

例：p=malloc(size);….q=p;free(p);a=*q;因結(jié)構(gòu)本身的特性，也會產(chǎn)生上述問題

例如廣義表的結(jié)構(gòu):共享子表(圖8.9P207)23/338.5無用單元收集(2)如何解決廣義表結(jié)構(gòu)中的“無用單元”或“懸掛訪問”問題？使用訪問計(jì)數(shù)器：在所有子表或廣義表上增加一個表頭結(jié)點(diǎn)，并設(shè)立一個“計(jì)數(shù)域”，它的值為指向該子表或廣義表的指針數(shù)目。當(dāng)該計(jì)數(shù)域的值為0時,此子表或廣義表中的結(jié)點(diǎn)才被釋放。收集無用單元：在程序運(yùn)行中，所有的鏈表結(jié)點(diǎn)不管是否還有用，都不被回收，直到整個可利用空間表為空。此時中斷執(zhí)行程序，收集無用單元，分兩步進(jìn)行:

1)對所有占用結(jié)點(diǎn)加上標(biāo)志(0-未用，1-占用)

2)對整個可利用存儲空間順序掃描一遍，將標(biāo)志為0的結(jié)點(diǎn)鏈成一個新的可利用空間表。困難24/338.5無用單元收集(3)標(biāo)志算法

加標(biāo)志的操作實(shí)質(zhì)上是遍歷廣義表，將廣義表中所有結(jié)點(diǎn)的標(biāo)志域賦值為“1”。遞歸算法：

基本項(xiàng)：1）表為空，則無須遍歷；

2）若是一個數(shù)據(jù)元素，則標(biāo)志元素結(jié)點(diǎn)

歸納項(xiàng)：首先標(biāo)志表結(jié)點(diǎn)，再分別遍歷表頭和表尾

評價：需要一個較大的實(shí)現(xiàn)遞歸用的棧的輔助內(nèi)存，該內(nèi)存不

能用于動態(tài)分配。由于表的層次不定，使得棧的容量不

易確定可能會棧溢出25/338.5無用單元收集(4)標(biāo)志算法非遞歸算法：程序中附設(shè)?；蜿?duì)列實(shí)現(xiàn)廣義表的遍歷。

類似于圖的深度優(yōu)先遍歷或廣度優(yōu)先遍歷

評價：?；蜿?duì)列的空間同樣是不確定的利用表結(jié)點(diǎn)本身的指針域標(biāo)記遍歷路徑的算法：

算法思想：假設(shè)p指向某個表結(jié)點(diǎn)時，t指向p的母表結(jié)點(diǎn)，q指向p的表頭或表尾。

當(dāng)q指向p的表頭結(jié)點(diǎn)時，

1）設(shè)p的表頭只是一個元素結(jié)點(diǎn)，則遍歷表頭僅需對該表頭

結(jié)點(diǎn)打上標(biāo)志后即令q指向p的表尾；

2）設(shè)p的表頭為空表或是已加上標(biāo)志的子表，則無需遍歷表

頭只要令q指向p的表尾；26/338.5無用單元收集(5)標(biāo)志算法利用表結(jié)點(diǎn)本身的指針域標(biāo)記遍歷路徑的算法：

算法思想：假設(shè)p指向某個表結(jié)點(diǎn)時，t指向p的母表結(jié)點(diǎn)，q指向p的表頭或表尾。

當(dāng)q指向p的表頭結(jié)點(diǎn)時，

3）設(shè)p的表頭為未加標(biāo)志的子表，則需先遍歷表頭子表，即

p應(yīng)賦q的值，t相應(yīng)往下移動改賦p的值；

為了記下t指針移動的路徑，以便在p退回原結(jié)點(diǎn)時同時找

到p的母表結(jié)點(diǎn)，則在修改這個指針的值之前，應(yīng)先記下t

移動的路徑，即令p所指結(jié)點(diǎn)的hp域的值為t，且tag域的

值為“0”。27/338.5無用單元收集(6)標(biāo)志算法利用表結(jié)點(diǎn)本身的指針域標(biāo)記遍歷路徑的算法：

算法思想：假設(shè)p指向某個表結(jié)點(diǎn)時，t指向p的母表結(jié)點(diǎn)，q指向p的表頭或表尾。

當(dāng)q指向p的表尾時，

1）p的表尾為未加標(biāo)志的子表，則需遍歷表尾子表，同樣p、

t指針要作相應(yīng)的移動。

為了記下t指針移動的路徑，以便在p退回原結(jié)點(diǎn)時同時找

到p的母表結(jié)點(diǎn)，則在修改這個指針的值之前，應(yīng)先記下t

移動的路徑，即令p所指結(jié)點(diǎn)的tp域的值為t。28/338.5無用單元收集(7)標(biāo)志算法利用表結(jié)點(diǎn)本身的指針域標(biāo)記遍歷路徑的算法：

算法思想：假設(shè)p指向某個表結(jié)點(diǎn)時，t指向p的母表結(jié)點(diǎn)，q指向p的表頭或表尾。

當(dāng)q指向p的表尾時，

2）p的表尾為“