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

2、言的編譯系統和程內存管理分別由操作系統、高級語言的編譯系統和程序員分工合作管理。通常編譯系統負責靜態儲存管理，序員分工合作管理。通常編譯系統負責靜態儲存管理，操作系統負責整個內存管理和動態儲存管理。操作系統負責整個內存管理和動態儲存管理。 程序員級的管理：程序員級的管理： 用戶程序中所用的儲存結構有兩種，用戶程序中所用的儲存結構有兩種，靜態結構靜態結構 ：空間量在編譯后，即可確定空間量在編譯后，即可確定 動態結構：動態結構：程序運行中申請空間，編譯時無法確定。程序運行中申請空間，編譯時無法確定。靜態儲存由編譯系統管理。靜態儲存由編譯系統管理。動態儲存由程序員和操作系統管理，但程序員的管理動態儲

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

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

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

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

7、收基礎技術、存儲空間的邏輯結構和物理結構。收基礎技術、存儲空間的邏輯結構和物理結構。 8.2 可利用空間表可利用空間表 初試狀態初試狀態OS bootOS 占用空間占用空間freetagsizelink一個連續的存儲空間稱為一個連續的存儲空間稱為“塊塊” blockTag：標記空間是否分配：標記空間是否分配Size：空間大小：空間大小Link：指向下一個空閑塊：指向下一個空閑塊初試狀態：除了操作系統占用的空間初試狀態：除了操作系統占用的空間外，其它空間形成一個空閑塊。當空外，其它空間形成一個空閑塊。當空閑塊多時，用閑塊多時，用link 鏈成一個鏈表，該鏈成一個鏈表，該鏈表就是可利用空間表。初試

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

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

10、除，進行分配； 若若p.sizen+s，從，從p的下部切割的下部切割size為為n的一塊進的一塊進行分配，如圖所示：行分配，如圖所示：n=16k064kp116k48k回收回收: 程序釋放空間程序釋放空間(如如free(p)、程序運行結束后、程序運行結束后將占用的塊歸還系統，如果收回的塊的相鄰塊將占用的塊歸還系統，如果收回的塊的相鄰塊是空閑的，需要合并它們。是空閑的，需要合并它們。回收過程：設釋放塊是回收過程：設釋放塊是p，大小為，大小為size。（1） 設置設置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例如，一個使用單鏈表的程序，它會不斷地申請例如，一個使用單鏈表的程序，它會不斷地申請和釋放同類型的結點（塊大小相等），和釋放同類型的結點（塊大小相等），1 回收時不進行合并，而是放在另一個鏈表回收時不進行合并，而是放在另一個鏈表avail中；中；2 分配時首先從分配時首先從avail取一個塊分配，當取一個塊分配，當avail中沒中沒有空閑塊時在從有空閑塊時在從free表里分配。表里分配。這樣就省去了不斷地合并切割的麻煩，可以提高這樣就省去了不斷地合并切割的麻煩，可以提高效

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

14、0 k0 k0 k內存最大空間是內存最大空間是2m空閑塊按其大小鏈入各自的鏈表；空閑塊按其大小鏈入各自的鏈表；該數組是各鏈表的表頭接點該數組是各鏈表的表頭接點同尺寸的空閑塊構成雙向循環鏈表；有同尺寸的空閑塊構成雙向循環鏈表；有4個域：個域：tag標記，標記，0空閑，空閑，1占用，占用，k: 塊的大小塊的大小2k , llink:q前驅指針，前驅指針，rlingk:后繼指針后繼指針 伙伴系統抽象數據類型伙伴系統抽象數據類型ADT BoddySystem Data : int m/ 可用內存可用內存2m FreeHeadList / m個表頭結點構成的線性表個表頭結點構成的線性表 BlockScr

15、pt/ 塊描述塊描述 Memory/ 整個內存空間整個內存空間 opration: BS_malloc(size)/ 分配內存分配內存 BS_reclaim(BlockScrpt bp) / 回收內存回收內存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 伙伴系統結構

17、伙伴系統結構Class BuddySystem int m;/ 最大可用內存最大可用內存2m BlockHeadList headList/ 表頭向量表頭向量 BlockScrpt blkScrpt;/ 塊描述塊描述 Byte mem;/ 內存內存 public BuddySystem(int k) / 構造函數構造函數 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 初始狀態初始狀態012.k.mfalse m00122m-1headListmemBlockScrpt分配分配 26 之后之后.67.k.m-1mfalsem-12m-102m-12m-1headListmemfalse k2kfalse 727true 60false 626分配算法思想：分配算法思想：申請空間量為申請空間量為2k；1 從從k到到m依次搜尋非空鏈表依次搜尋非空鏈表若

19、無：內存不夠，結束；若無：內存不夠，結束； 若有：設為若有：設為headListj k=jk: 從從headListj取一結點取一結點bs (1)將將bs均分為二，高地址部分插入均分為二，高地址部分插入headListj-1; j-; (2) 重復（重復（1）直到）直到j=k；4 將將bs 分配；結束；分配；結束；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回收算法思想回收算法思想 伙伴系統的一個重要特點是：任何塊（除最大塊伙伴系統的一個重要特點是：任何塊（除最大塊外）都有唯一的一個伙伴，所謂伙伴即：大小一樣外）都有唯一的一個伙伴，所謂伙伴即：大小一樣且相鄰；且相鄰； 空閑的相鄰塊是可以合并的；空閑的相鄰塊是可以合并的； 一個塊的伙伴地址是什么？一個塊的伙伴地址是什么？ 設塊的首地址是設塊的首地址是p，其伙伴的首地址是：，其伙伴的首地址是： Buddy(p