1、基于Buddy動態(tài)存儲管理算法的應(yīng)用研究摘要本文分析了動態(tài)存儲管理的特性,提出了一種利用哈希表的快速查找特性來優(yōu)化基于伙伴系統(tǒng)動態(tài)存儲管理器算法的思想，高效地實現(xiàn)了存儲管理器的分配和回收算法，具有簡單、速度快、克制了大量存儲空間的浪費等優(yōu)點。關(guān)鍵詞動態(tài)存儲管理伙伴系統(tǒng)哈希表算法1引言動態(tài)存儲管理在實現(xiàn)中表達為一個動態(tài)存儲分配器(dynaiallatr)。動態(tài)存儲分配器的設(shè)計目的是盡量減少空間的浪費，減少申請釋放存儲空間時的時間消耗1。理想的動態(tài)存儲分配器是在不浪費空間，極少的時耗下，能滿足任何次序的存儲空間申請和釋放。由于減少時間消耗與增加空間利用率往往互相矛盾,現(xiàn)實中理想的分配器是很難甚至是

2、不可能實現(xiàn)的，只能根據(jù)特定的環(huán)境做出適當(dāng)?shù)臎Q策2。本文在對當(dāng)前應(yīng)用中主要采用的動態(tài)存儲管理技術(shù)進展分析的根底上，提出了一種基于buddy動態(tài)存儲分配和回收思想，利用哈希查找快速定位最正確可利用空閑塊在內(nèi)存中位置的動態(tài)存儲管理算法。采用這一算法思想設(shè)計的動態(tài)存儲分配器具有簡單、速度快的優(yōu)點，克制了大量存儲空間浪費的問題。2動態(tài)存儲分配技術(shù)對動態(tài)存儲管理經(jīng)過多年的研究，已有大量的動態(tài)存儲管理解決方案和算法提出并應(yīng)用到不同的系統(tǒng)中3。如：順序搜索、buddy算法、分類搜索、索引搜索、位圖搜索等。其中順序搜索和分類搜索算法在操作系統(tǒng)動態(tài)內(nèi)存分配中被普遍采用4。采用順序搜索的動態(tài)存儲分配器，一般采用“可

3、利用空間隊列avail鏈接運行中形成的長度不相等的空閑存儲塊，采用首次適配(firstfit)、下次適配(nextfit)、最正確適配(bestfit)和最差適配(rstfit)算法順序搜索適配塊。搜索適配塊的時間開銷依賴于avail隊列長度。優(yōu)點是簡單，存儲空間利用率高。缺點是隨著系統(tǒng)規(guī)模的增大，會形成許多小碎塊，使avail隊列變長，搜索時間將可能增加到不可承受的程度。采用分類搜索的動態(tài)存儲分配器，一般按固定大小將存儲空間劃分為多個互相獨立的存儲區(qū)，每一個存儲區(qū)包含一條avail隊列，存儲對象在唯一的avail中分配空間。優(yōu)點是申請分配空間時，不需要進展搜索來查找符合要求的空閑塊。釋放時也

4、沒有相鄰空閑塊合并的要求，進步了系統(tǒng)執(zhí)行速度，具有良好的可伸縮性。缺點是在每一個存儲區(qū)都將有一定的存儲空間空閑，且互相之間不能共享，造成較為可觀的存儲空間浪費。這是典型的以空間換時間的作法。并且存儲區(qū)劃分越細(xì),浪費越嚴(yán)重5。另一種動態(tài)存儲分配方法是將空閑塊組織為伙伴系統(tǒng)(buddysyste)。伙伴系統(tǒng)規(guī)定，無論占用塊或空閑塊其大小均為2的k次冪k為整數(shù)。假設(shè)系統(tǒng)的可利用空間容量為2個字，那么系統(tǒng)開場運行時，整個內(nèi)存區(qū)是一個大小為2的空閑塊，系統(tǒng)運行中可能會形成假設(shè)干個空閑塊，將一樣大小的空閑塊都鏈在的空閑塊都鏈在同一個雙重鏈表中，不同大小空閑塊形成k0=k=個空閑塊鏈表。當(dāng)要分配一長度為n的

5、存儲塊時，求i使2i1n2i。假設(shè)長度為2i的空閑塊已耗盡，那么把長為2i1的空閑塊分為等長的兩半(一對伙伴)，一個用于分配，一個鏈入長為2i的鏈表中。假設(shè)長為2i1的空閑塊也不存在，那么需要對長為2i2的空閑塊進展兩次分割，依此類推。由此可見，在最壞情況下,可能要進展k次分割才能得到適配塊。與一次分配可能要進展屢次分割一樣，一次回收也可能要進展屢次合并。其分配和回收的時間性能取決于查找空閑塊的位置和分割、合并空閑塊所花費的時間。空間性能遠(yuǎn)優(yōu)于分類搜索算法，比順序搜索算法略差。3基于哈希查找的根本思想與構(gòu)造定義3.1基于哈希查找的根本思想基于哈希查找的根本思想是：利用哈希快速查找優(yōu)點和空閑塊在

6、可利用空間表中的分布規(guī)律，構(gòu)造哈希函數(shù)。當(dāng)懇求分配存儲空間時，通過查找以空閑塊大小為關(guān)鍵字的哈希表選擇適宜的空閑塊鏈，實現(xiàn)最正確分配策略。對系統(tǒng)運行可能形成的k個空閑塊鏈表，將頭指針組織成一個向量構(gòu)造，根據(jù)鏈表中空閑塊大小確定鏈表頭指針在向量中的位置。由于申請的空閑塊長度n要求滿足關(guān)系2i1n2i。因此可定義哈希函數(shù)如下：哈希函數(shù)計算結(jié)果確定了所申請大小的空閑塊對應(yīng)鏈表應(yīng)在向量表中的位置。3.2存儲構(gòu)造定義空閑塊結(jié)點構(gòu)造定義，如圖1所示。圖1空閑塊結(jié)點構(gòu)造結(jié)點數(shù)據(jù)類型定義描繪如下：#definensize/*定義size為可利用空間容量，大小為2的次冪*/typedefstrutRD_NDEi

7、nttag;/*塊標(biāo)志，0：空閑，1：占用*/intkval;/*塊大小，值為2的K次冪*/RD_NDE*llink,rlink;/*指向前驅(qū)、后繼結(jié)點的指針域*/therTypether;/*其它部分*/RD_NDE,head;/*內(nèi)存字類型，結(jié)點的第一個字為head*/頭指針向量表數(shù)據(jù)類型定義描繪如下：typedefstrutHeadNdeintndesize;/*該鏈表空閑塊大小*/RD_NDE*first;/*該鏈表的頭指針*/FreeList+1；/*可利用空間表頭向量類型*/系統(tǒng)初始狀態(tài)的可利用空間表狀如圖2所示。圖2可利用空間表初始狀態(tài)4分配與回收算法41分配算法當(dāng)用戶申請分配長

8、度為n的存儲塊時,求i=HASH(n),假設(shè)FreeListi.first不空，只要刪除此鏈表中的第一個結(jié)點，分配給申請者即可；否那么判斷FreeListi1所對應(yīng)的空閑塊鏈表，假設(shè)不空，那么把長為2i1的第一個空閑塊分為等長的兩半(一對伙伴),一個用于分配給申請者，另一個鏈入FreeListi.first對應(yīng)的鏈表中。假設(shè)FreeListi1.first仍然為空，那么依次判FreeListi2.first，以此類推。假假設(shè)直到ik時，F(xiàn)reeListik.first非空，那么需要從該鏈表中取出一個結(jié)點，將大小為2k的一局部分配給申請者，剩余局部分割成假設(shè)干個大小分別為2i+1、2i+2、2i

9、+k-1的結(jié)點插入到對應(yīng)大小的鏈表中。算法描繪如下：RD_NDE*AllBuddy(FreeListavail,intn)/*申請容量為n的存儲空間*/j=HASH(n);hile(!availj.firstj=)j+;if(j)returnNULL;i=j;pa=availi.first;pre=pa-llink;su=pa-rlink;if(pa=su)availi.first=NULL;else從子表刪去*pa結(jié)點;fr(k=j;ki;k+)pi=pa+2i-k;pi-rlink=pi;pi-llink=pi;pi-tag=0;pi-kval=i-k;availi-k.first=piP

10、a-tag=1;pa-kval=i-(-k);Returnpa;42回收算法回收空閑塊時，假設(shè)該回收塊的伙伴也為空閑塊，那么需將他們合并成大的空閑塊。然后再判斷合并后的空閑塊的伙伴是否為空閑塊，假設(shè)是那么繼續(xù)合并。否那么只要將釋放的空閑塊簡單地插入到相應(yīng)空閑塊鏈表中即可。設(shè)大小為2i的空閑塊起始地址為p，其伙伴塊的起始地址可采用下式計算:假設(shè)pD2i+1=0，那么其伙伴塊的起始地址為p+2i假設(shè)pD2i+1=2i，那么其伙伴塊的起始地址為p-2i例如，假設(shè)p為大小為2i的空閑塊的起始地址，當(dāng)pD2i+1=0時，起始地址為p和p2i的兩個空閑塊互為伙伴；當(dāng)pD2i+1=2i時，起始地址為p和p2

11、i的兩個空閑塊互為伙伴。利用該性質(zhì)可方便地實現(xiàn)空閑塊的合并與回收。這里僅給出回收算法的描繪如下：vidFreeBuddy(avail,*addr,n)/*回收長度為n，起始地址為addr的塊*/置回收塊標(biāo)志tag為0，塊長kval為n;求回收塊的伙伴地址buddy=addr%(2*n)?(addr-n):addr+n);求回收塊應(yīng)在頭指針向量中的位置i=HASHn;假如availi.first為空，說明該塊沒有伙伴，直接插入到插入到該鏈表中;否那么在當(dāng)前鏈表中尋找伙伴地址為buddy的塊;假如存在伙伴，并且該伙伴是當(dāng)前鏈表中唯一大小為2i的空閑塊,那么置availi.first為空;否那么，從當(dāng)前鏈表中刪去伙伴;修改合并后的新空閑塊起始地址addr或buddy以及合并塊kval的值為2*n;以新地址和新塊長為參數(shù)，遞歸調(diào)用FreeBuddy函數(shù)，繼續(xù)調(diào)用并合并伙伴塊;將得到的最后合并塊插入到對應(yīng)頭指針向量所對應(yīng)的空閑塊鏈表中;5完畢語操作系統(tǒng)動態(tài)內(nèi)存管理方法很多，它們各有其優(yōu)缺點，各有其適用情形。選擇合理的存儲分配和管理方案必須建立在設(shè)計者對硬件平臺和系統(tǒng)中動態(tài)內(nèi)存的申請釋放流進展科學(xué)評價和分析的根底上。本文所提出的存儲管理算法的時間性能主要取決于查找空閑塊的位置和分割、合并空閑塊所花費的時間。采用哈希快速定位方法查找空閑塊的時間