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

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

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

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

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)級管理編譯系統(tǒng)級管理 在編譯中，編譯系統(tǒng)為程序設(shè)置了一個虛擬在編譯中，編譯系統(tǒng)為程序設(shè)置了一個虛擬空間，它管理的是虛擬空間?？臻g，它管理的是虛擬空間。用戶程序：int x,y;float r,s;char str10; 虛擬空間：虛擬空間：x: 4bytesy: 4bytesstr: 10bytesr: 4

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

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

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

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

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

10、除，進行分配； 若若p.sizen+s，從，從p的下部切割的下部切割size為為n的一塊進的一塊進行分配，如圖所示：行分配，如圖所示：n=16k064kp116k48k回收回收: 程序釋放空間程序釋放空間(如如free(p)、程序運行結(jié)束后、程序運行結(jié)束后將占用的塊歸還系統(tǒng)，如果收回的塊的相鄰塊將占用的塊歸還系統(tǒng)，如果收回的塊的相鄰塊是空閑的，需要合并它們。是空閑的，需要合并它們。回收過程：設(shè)釋放塊是回收過程：設(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 有時也不必馬上合并，如果釋放塊有時也不必馬上合并，如果釋放塊p的大小恰的大小恰好符合下次申請空間的要求，可以將好符合下次申請空間

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

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

14、0 k0 k0 k內(nèi)存最大空間是內(nèi)存最大空間是2m空閑塊按其大小鏈入各自的鏈表；空閑塊按其大小鏈入各自的鏈表；該數(shù)組是各鏈表的表頭接點該數(shù)組是各鏈表的表頭接點同尺寸的空閑塊構(gòu)成雙向循環(huán)鏈表；有同尺寸的空閑塊構(gòu)成雙向循環(huán)鏈表；有4個域：個域：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個表頭結(jié)點構(gòu)成的線性表個表頭結(jié)點構(gòu)成的線性表 BlockScr

15、pt/ 塊描述塊描述 Memory/ 整個內(nèi)存空間整個內(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分配算法思想：分配算法思想：申請空間量為申請空間量為2k；1 從從k到到m依次搜尋非空鏈表依次搜尋非空鏈表若

19、無：內(nèi)存不夠，結(jié)束；若無：內(nèi)存不夠，結(jié)束； 若有：設(shè)為若有：設(shè)為headListj k=jk: 從從headListj取一結(jié)點取一結(jié)點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; / 無非空鏈表，分配失敗無非空鏈表，分配失敗 bs=headListj.delet(1); / 從非空鏈表中取第一個接點；從非空鏈表中取第一個接點； 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)的一個重要特點是：任何塊（除最大塊伙伴系統(tǒng)的一個重要特點是：任何塊（除最大塊外）都有唯一的一個伙伴，所謂伙伴即：大小一樣外）都有唯一的一個伙伴，所謂伙伴即：大小一樣且相鄰；且相鄰； 空閑的相鄰塊是可以合并的；空閑的相鄰塊是可以合并的； 一個塊的伙伴地址是什么？一個塊的伙伴地址是什么？ 設(shè)塊的首地址是設(shè)塊的首地址是p，其伙伴的首地址是：，其伙伴的首地址是： Buddy(p