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

1、算法與數(shù)據(jù)結(jié)構(gòu)Algorithms and Data Structures 第八章 動(dòng)態(tài)存儲(chǔ)管理8.1 概述概述 內(nèi)存是很重要的、很昂貴的資源，如何合理高效內(nèi)存是很重要的、很昂貴的資源，如何合理高效地使用這一資源是一個(gè)比較復(fù)雜的問(wèn)題。地使用這一資源是一個(gè)比較復(fù)雜的問(wèn)題。 早期使用低級(jí)語(yǔ)言編程，內(nèi)存管理是由程序員自早期使用低級(jí)語(yǔ)言編程，內(nèi)存管理是由程序員自己負(fù)責(zé)。程序員負(fù)擔(dān)重，管理水平因人而異，管理效己負(fù)責(zé)。程序員負(fù)擔(dān)重，管理水平因人而異，管理效率低，容易出錯(cuò)。率低，容易出錯(cuò)。 隨著操作系統(tǒng)和高級(jí)語(yǔ)言的發(fā)展，情況不斷改善。隨著操作系統(tǒng)和高級(jí)語(yǔ)言的發(fā)展，情況不斷改善。內(nèi)存管理分別由操作系統(tǒng)、高級(jí)語(yǔ)

2、言的編譯系統(tǒng)和程內(nèi)存管理分別由操作系統(tǒng)、高級(jí)語(yǔ)言的編譯系統(tǒng)和程序員分工合作管理。通常編譯系統(tǒng)負(fù)責(zé)靜態(tài)儲(chǔ)存管理，序員分工合作管理。通常編譯系統(tǒng)負(fù)責(zé)靜態(tài)儲(chǔ)存管理，操作系統(tǒng)負(fù)責(zé)整個(gè)內(nèi)存管理和動(dòng)態(tài)儲(chǔ)存管理。操作系統(tǒng)負(fù)責(zé)整個(gè)內(nèi)存管理和動(dòng)態(tài)儲(chǔ)存管理。 程序員級(jí)的管理：程序員級(jí)的管理： 用戶程序中所用的儲(chǔ)存結(jié)構(gòu)有兩種，用戶程序中所用的儲(chǔ)存結(jié)構(gòu)有兩種，靜態(tài)結(jié)構(gòu)靜態(tài)結(jié)構(gòu) ：空間量在編譯后，即可確定空間量在編譯后，即可確定 動(dòng)態(tài)結(jié)構(gòu)：動(dòng)態(tài)結(jié)構(gòu)：程序運(yùn)行中申請(qǐng)空間，編譯時(shí)無(wú)法確定。程序運(yùn)行中申請(qǐng)空間，編譯時(shí)無(wú)法確定。靜態(tài)儲(chǔ)存由編譯系統(tǒng)管理。靜態(tài)儲(chǔ)存由編譯系統(tǒng)管理。動(dòng)態(tài)儲(chǔ)存由程序員和操作系統(tǒng)管理，但程序員的管理動(dòng)態(tài)儲(chǔ)

3、存由程序員和操作系統(tǒng)管理，但程序員的管理非常簡(jiǎn)單。程序員的工作就是在需要的時(shí)候向系統(tǒng)申非常簡(jiǎn)單。程序員的工作就是在需要的時(shí)候向系統(tǒng)申請(qǐng)空間，在不需要時(shí)釋放要來(lái)的動(dòng)態(tài)儲(chǔ)存空間：請(qǐng)空間，在不需要時(shí)釋放要來(lái)的動(dòng)態(tài)儲(chǔ)存空間： C語(yǔ)言中：語(yǔ)言中：malloc(size), 申請(qǐng)申請(qǐng)size字節(jié)的內(nèi)存；字節(jié)的內(nèi)存； free(p), 釋放釋放p，歸還給系統(tǒng)；，歸還給系統(tǒng)； C+中：中： new objectType(), 申請(qǐng)空間；申請(qǐng)空間； free(p), 釋放釋放p，歸還給系統(tǒng)；，歸還給系統(tǒng)； Java語(yǔ)言中：語(yǔ)言中： new objectType(), 申請(qǐng)空間；申請(qǐng)空間； 用戶程序：用戶程序：#

4、 include iostd.libInt main() *r=new int100; free (r);操作系統(tǒng)操作系統(tǒng)分配分配 OS_AllocMemory(r,size,flags)回收回收 OS_ReclaimMemory(r) FreeMemFreeMem rFreeMem編譯系統(tǒng)級(jí)管理編譯系統(tǒng)級(jí)管理 在編譯中，編譯系統(tǒng)為程序設(shè)置了一個(gè)虛擬在編譯中，編譯系統(tǒng)為程序設(shè)置了一個(gè)虛擬空間，它管理的是虛擬空間?？臻g，它管理的是虛擬空間。用戶程序：int x,y;float r,s;char str10; 虛擬空間：虛擬空間：x: 4bytesy: 4bytesstr: 10bytesr: 4

5、bytess: 4bytes048121626內(nèi)存程序裝入時(shí)，重定位程序裝入時(shí)，重定位編譯原理與技術(shù)中將做介紹。編譯原理與技術(shù)中將做介紹。操作系統(tǒng)級(jí)管理：操作系統(tǒng)級(jí)管理： 存儲(chǔ)管理是操作系統(tǒng)的重要部分之一，操作存儲(chǔ)管理是操作系統(tǒng)的重要部分之一，操作系統(tǒng)對(duì)儲(chǔ)存的管理是才是真實(shí)的管理，而且這一系統(tǒng)對(duì)儲(chǔ)存的管理是才是真實(shí)的管理，而且這一管理是很復(fù)雜的。管理是很復(fù)雜的。操作系統(tǒng)的存儲(chǔ)管理操作系統(tǒng)的存儲(chǔ)管理為程序代碼和靜態(tài)數(shù)為程序代碼和靜態(tài)數(shù)據(jù)分配空間據(jù)分配空間為程序動(dòng)態(tài)分配空間為程序動(dòng)態(tài)分配空間回收不用的動(dòng)態(tài)空間回收不用的動(dòng)態(tài)空間回收空間程序代碼和回收空間程序代碼和靜態(tài)數(shù)據(jù)空間靜態(tài)數(shù)據(jù)空間分分配配回回

6、收收?qǐng)?zhí)行程序執(zhí)行程序執(zhí)行完畢或撤消執(zhí)行程序執(zhí)行完畢或撤消執(zhí)行程序程序New Otype()Free(p) 從外部來(lái)看，操作系統(tǒng)存儲(chǔ)管理系統(tǒng)就是提從外部來(lái)看，操作系統(tǒng)存儲(chǔ)管理系統(tǒng)就是提供存儲(chǔ)空間分配和回收服務(wù)，但內(nèi)部實(shí)現(xiàn)方法卻供存儲(chǔ)空間分配和回收服務(wù)，但內(nèi)部實(shí)現(xiàn)方法卻十分復(fù)雜，不同的操作系統(tǒng)采用不同的策略和方十分復(fù)雜，不同的操作系統(tǒng)采用不同的策略和方法，這些問(wèn)題將在后續(xù)課程操作系統(tǒng)中詳細(xì)介紹。法，這些問(wèn)題將在后續(xù)課程操作系統(tǒng)中詳細(xì)介紹。 這里我們只是站在數(shù)據(jù)結(jié)構(gòu)的角度來(lái)討論動(dòng)這里我們只是站在數(shù)據(jù)結(jié)構(gòu)的角度來(lái)討論動(dòng)態(tài)存儲(chǔ)管理的基本方法，即存儲(chǔ)空間的分配和回態(tài)存儲(chǔ)管理的基本方法，即存儲(chǔ)空間的分配和回

7、收基礎(chǔ)技術(shù)、存儲(chǔ)空間的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。收基礎(chǔ)技術(shù)、存儲(chǔ)空間的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。 8.2 可利用空間表可利用空間表 初試狀態(tài)初試狀態(tài)OS bootOS 占用空間占用空間freetagsizelink一個(gè)連續(xù)的存儲(chǔ)空間稱為一個(gè)連續(xù)的存儲(chǔ)空間稱為“塊塊” blockTag：標(biāo)記空間是否分配：標(biāo)記空間是否分配Size：空間大?。嚎臻g大小Link：指向下一個(gè)空閑塊：指向下一個(gè)空閑塊初試狀態(tài)：除了操作系統(tǒng)占用的空間初試狀態(tài)：除了操作系統(tǒng)占用的空間外，其它空間形成一個(gè)空閑塊。當(dāng)空外，其它空間形成一個(gè)空閑塊。當(dāng)空閑塊多時(shí)，用閑塊多時(shí)，用link 鏈成一個(gè)鏈表，該鏈成一個(gè)鏈表，該鏈表就是可利用空間表。初試

8、此表中鏈表就是可利用空間表。初試此表中只有一個(gè)空閑塊。表指針是只有一個(gè)空閑塊。表指針是free。經(jīng)過(guò)多次分配、回收之后，形成了多個(gè)空閑塊，它們之間經(jīng)過(guò)多次分配、回收之后，形成了多個(gè)空閑塊，它們之間不連續(xù)，如圖所示：不連續(xù)，如圖所示：Free used1used2used3used4used523456Free 1136542可利用空間表的鏈接順序有：可利用空間表的鏈接順序有： （1）按塊的首地址有低到高鏈接；）按塊的首地址有低到高鏈接； （2）按塊的大小有小到大鏈接；）按塊的大小有小到大鏈接； （3）按塊的大小有大到小鏈接；）按塊的大小有大到小鏈接；分配：分配： 一般有一般有3種策略，設(shè)申請(qǐng)空

9、間的大小為種策略，設(shè)申請(qǐng)空間的大小為n （1）首次擬合法：首次擬合法：從表頭開始搜索，遇到第一從表頭開始搜索，遇到第一個(gè)尺寸等于大于個(gè)尺寸等于大于n的塊進(jìn)行分配；的塊進(jìn)行分配； （2）最佳擬合法：最佳擬合法：搜索整個(gè)表，將最小的等于搜索整個(gè)表，將最小的等于大于大于n的塊進(jìn)行分配；的塊進(jìn)行分配； （3）最差擬合法：最差擬合法：搜索整個(gè)表，將最大塊進(jìn)行搜索整個(gè)表，將最大塊進(jìn)行分配（等于大于分配（等于大于n ）；）；分配過(guò)程：分配過(guò)程： 找到合適的空閑塊找到合適的空閑塊p； P.size等于等于n或比或比n大少許（一般設(shè)定一個(gè)量大少許（一般設(shè)定一個(gè)量s），），則將則將p從表中刪除，進(jìn)行分配；從表中刪

10、除，進(jìn)行分配； 若若p.sizen+s，從，從p的下部切割的下部切割size為為n的一塊進(jìn)的一塊進(jìn)行分配，如圖所示：行分配，如圖所示：n=16k064kp116k48k回收回收: 程序釋放空間程序釋放空間(如如free(p)、程序運(yùn)行結(jié)束后、程序運(yùn)行結(jié)束后將占用的塊歸還系統(tǒng)，如果收回的塊的相鄰塊將占用的塊歸還系統(tǒng)，如果收回的塊的相鄰塊是空閑的，需要合并它們。是空閑的，需要合并它們?；厥者^(guò)程：設(shè)釋放塊是回收過(guò)程：設(shè)釋放塊是p，大小為，大小為size。（1） 設(shè)置設(shè)置p .tag=0；（2）判斷）判斷p的下相鄰塊的下相鄰塊q是否空閑是否空閑 若空閑：從可利用空間表摘出若空閑：從可利用空間表摘出q，

11、置，置p.size=p.size+q.size(合并合并)；（3）判斷）判斷p的上相鄰塊的上相鄰塊r是否空閑是否空閑 若空閑：合并若空閑：合并r和和p，r.size=r.size+p.size 否則：將否則：將p插入可利用空間表。插入可利用空間表。例如：例如：Free used1used2used3used4used523456Free 1136542釋放used104k11k null06k12used104k07k null12used10 11k12used1 有時(shí)也不必馬上合并，如果釋放塊有時(shí)也不必馬上合并，如果釋放塊p的大小恰的大小恰好符合下次申請(qǐng)空間的要求，可以將好符合下次申請(qǐng)空間

12、的要求，可以將p分配，而不分配，而不必從可利用空間表中切割分配。必從可利用空間表中切割分配。Free 136542used1例如，一個(gè)使用單鏈表的程序，它會(huì)不斷地申請(qǐng)例如，一個(gè)使用單鏈表的程序，它會(huì)不斷地申請(qǐng)和釋放同類型的結(jié)點(diǎn)（塊大小相等），和釋放同類型的結(jié)點(diǎn)（塊大小相等），1 回收時(shí)不進(jìn)行合并，而是放在另一個(gè)鏈表回收時(shí)不進(jìn)行合并，而是放在另一個(gè)鏈表avail中；中；2 分配時(shí)首先從分配時(shí)首先從avail取一個(gè)塊分配，當(dāng)取一個(gè)塊分配，當(dāng)avail中沒(méi)中沒(méi)有空閑塊時(shí)在從有空閑塊時(shí)在從free表里分配。表里分配。這樣就省去了不斷地合并切割的麻煩，可以提高這樣就省去了不斷地合并切割的麻煩，可以提高效

13、率。效率。 對(duì)于一些小的操作系統(tǒng)，內(nèi)存管理相對(duì)簡(jiǎn)單些。對(duì)于一些小的操作系統(tǒng)，內(nèi)存管理相對(duì)簡(jiǎn)單些。在許多專用設(shè)備、智能儀表和家用電器等都使用在許多專用設(shè)備、智能儀表和家用電器等都使用一種小型的、高效的、簡(jiǎn)單的操作系統(tǒng)，一般稱一種小型的、高效的、簡(jiǎn)單的操作系統(tǒng)，一般稱之為之為“嵌入式操作系統(tǒng)嵌入式操作系統(tǒng)”。下面介紹一些實(shí)用而簡(jiǎn)單的動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)。下面介紹一些實(shí)用而簡(jiǎn)單的動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)。8.3 伙伴系統(tǒng)（伙伴系統(tǒng)（Buddy system）特點(diǎn)：特點(diǎn)：（1）分配塊的大小均是）分配塊的大小均是2k ;（2）分配和回收簡(jiǎn)單）分配和回收簡(jiǎn)單 可利用空間表結(jié)構(gòu)：可利用空間表結(jié)構(gòu)：202122.2k2m

14、0 k0 k0 k內(nèi)存最大空間是內(nèi)存最大空間是2m空閑塊按其大小鏈入各自的鏈表；空閑塊按其大小鏈入各自的鏈表；該數(shù)組是各鏈表的表頭接點(diǎn)該數(shù)組是各鏈表的表頭接點(diǎn)同尺寸的空閑塊構(gòu)成雙向循環(huán)鏈表；有同尺寸的空閑塊構(gòu)成雙向循環(huán)鏈表；有4個(gè)域：個(gè)域：tag標(biāo)記，標(biāo)記，0空閑，空閑，1占用，占用，k: 塊的大小塊的大小2k , llink:q前驅(qū)指針，前驅(qū)指針，rlingk:后繼指針后繼指針 伙伴系統(tǒng)抽象數(shù)據(jù)類型伙伴系統(tǒng)抽象數(shù)據(jù)類型ADT BoddySystem Data : int m/ 可用內(nèi)存可用內(nèi)存2m FreeHeadList / m個(gè)表頭結(jié)點(diǎn)構(gòu)成的線性表個(gè)表頭結(jié)點(diǎn)構(gòu)成的線性表 BlockScr

15、pt/ 塊描述塊描述 Memory/ 整個(gè)內(nèi)存空間整個(gè)內(nèi)存空間 opration: BS_malloc(size)/ 分配內(nèi)存分配內(nèi)存 BS_reclaim(BlockScrpt bp) / 回收內(nèi)存回收內(nèi)存End BlockSystemClass FreeHeadNode int sizePower; / k 2k BlockScrpt first; / 鏈表指針鏈表指針 / Class FreeHeadNode Class FreeHeadList int m; / FreeHeadNode list; public FreeHeadList(int n) m=n; list=new Fr

16、eeHeadNodem ; for (k=0; k=m; k+) listk.sizePower=k; first=null; / Class FreeHeadList kfirst0123.m-1m塊描述塊描述Class BlockScrpt int sizePower; boolean used; BlockScrpt llink, rlink; int add; public BlockScrpt(int k, boolean b, int addr) sizePower=k; used=b; add=addr; / BlockScrpt/ Class BlockScrpt 伙伴系統(tǒng)結(jié)構(gòu)

17、伙伴系統(tǒng)結(jié)構(gòu)Class BuddySystem int m;/ 最大可用內(nèi)存最大可用內(nèi)存2m BlockHeadList headList/ 表頭向量表頭向量 BlockScrpt blkScrpt;/ 塊描述塊描述 Byte mem;/ 內(nèi)存內(nèi)存 public BuddySystem(int k) / 構(gòu)造函數(shù)構(gòu)造函數(shù) m=k; headList=new BlockHeadList(m); blkScrpt=new BlockScrpt(m,false,0); blkScrpt.llink=blkscrpt; blkScrpt.rlink=blkscrpt; headListm.first=

18、 blkScrpt mem=new Byte2m; / BlockScrpt BS_malloc(int k) void BS_reclaim(BlockScrpt bp) / Class BuddySystem 初始狀態(tài)初始狀態(tài)012.k.mfalse m00122m-1headListmemBlockScrpt分配分配 26 之后之后.67.k.m-1mfalsem-12m-102m-12m-1headListmemfalse k2kfalse 727true 60false 626分配算法思想：分配算法思想：申請(qǐng)空間量為申請(qǐng)空間量為2k；1 從從k到到m依次搜尋非空鏈表依次搜尋非空鏈表若

19、無(wú)：內(nèi)存不夠，結(jié)束；若無(wú)：內(nèi)存不夠，結(jié)束； 若有：設(shè)為若有：設(shè)為headListj k=jk: 從從headListj取一結(jié)點(diǎn)取一結(jié)點(diǎn)bs (1)將將bs均分為二，高地址部分插入均分為二，高地址部分插入headListj-1; j-; (2) 重復(fù)（重復(fù)（1）直到）直到j(luò)=k；4 將將bs 分配；結(jié)束；分配；結(jié)束；BlockScrpt BS_malloc(int k) for (j=k; jm) return null; / 無(wú)非空鏈表，分配失敗無(wú)非空鏈表，分配失敗 bs=headListj.delet(1); / 從非空鏈表中取第一個(gè)接點(diǎn)；從非空鏈表中取第一個(gè)接點(diǎn)； for (s=j; sk

20、; s-) / 將大塊分割；將大塊分割； bst=new BlockScrpt(s-1, false, bs.add+2s-1); headLists-1.insert(bst); bs.sizePower-; / for bs.used=true; return bs; / 分配分配bs / True s-1 False s-1 bstbs回收算法思想回收算法思想 伙伴系統(tǒng)的一個(gè)重要特點(diǎn)是：任何塊（除最大塊伙伴系統(tǒng)的一個(gè)重要特點(diǎn)是：任何塊（除最大塊外）都有唯一的一個(gè)伙伴，所謂伙伴即：大小一樣外）都有唯一的一個(gè)伙伴，所謂伙伴即：大小一樣且相鄰；且相鄰； 空閑的相鄰塊是可以合并的；空閑的相鄰塊是可以合并的； 一個(gè)塊的伙伴地址是什么？一個(gè)塊的伙伴地址是什么？ 設(shè)塊的首地址是設(shè)塊的首地址是p，其伙伴的首地址是：，其伙伴的首地址是： Buddy(p