基于Buddy動(dòng)態(tài)存儲(chǔ)管理算法的應(yīng)用研究

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

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

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

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

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

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

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

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

9、+k-1的結(jié)點(diǎn)插入到對(duì)應(yīng)大小的鏈表中。算法描繪如下：RD_NDE*AllBuddy(FreeListavail,intn)/*申請(qǐng)容量為n的存儲(chǔ)空間*/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é)點(diǎn);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è)該回收塊的伙伴也為空閑塊，那么需將他們合并成大的空閑塊。然后再判斷合并后的空閑塊的伙伴是否為空閑塊，假設(shè)是那么繼續(xù)合并。否那么只要將釋放的空閑塊簡(jiǎn)單地插入到相應(yīng)空閑塊鏈表中即可。設(shè)大小為2i的空閑塊起始地址為p，其伙伴塊的起始地址可采用下式計(jì)算:假設(shè)pD2i+1=0，那么其伙伴塊的起始地址為p+2i假設(shè)pD2i+1=2i，那么其伙伴塊的起始地址為p-2i例如，假設(shè)p為大小為2i的空閑塊的起始地址，當(dāng)pD2i+1=0時(shí)，起始地址為p和p2i的兩個(gè)空閑塊互為伙伴；當(dāng)pD2i+1=2i時(shí)，起始地址為p和p2

11、i的兩個(gè)空閑塊互為伙伴。利用該性質(zhì)可方便地實(shí)現(xiàn)空閑塊的合并與回收。這里僅給出回收算法的描繪如下：vidFreeBuddy(avail,*addr,n)/*回收長(zhǎng)度為n，起始地址為addr的塊*/置回收塊標(biāo)志tag為0，塊長(zhǎng)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;以新地址和新塊長(zhǎng)為參數(shù)，遞歸調(diào)用FreeBuddy函數(shù)，繼續(xù)調(diào)用并合并伙伴塊;將得到的最后合并塊插入到對(duì)應(yīng)頭指針向量所對(duì)應(yīng)的空閑塊鏈表中;5完畢語操作系統(tǒng)動(dòng)態(tài)內(nèi)存管理方法很多，它們各有其優(yōu)缺點(diǎn)，各有其適用情形。選擇合理的存儲(chǔ)分配和管理方案必須建立在設(shè)計(jì)者對(duì)硬件平臺(tái)和系統(tǒng)中動(dòng)態(tài)內(nèi)存的申請(qǐng)釋放流進(jìn)展科學(xué)評(píng)價(jià)和分析的根底上。本文所提出的存儲(chǔ)管理算法的時(shí)間性能主要取決于查找空閑塊的位置和分割、合并空閑塊所花費(fèi)的時(shí)間。采用哈希快速定位方法查找空閑塊的時(shí)間