曹海濤　余永紅

摘要：對(duì)多種不同的動(dòng)態(tài)內(nèi)存分配算法的特點(diǎn)與優(yōu)劣進(jìn)行對(duì)比、分析，在兼顧效率和內(nèi)存碎片率指標(biāo)的要求下，提出了基于multimap映射的動(dòng)態(tài)內(nèi)存分配算法。該算法以內(nèi)存塊的大小作為鍵，內(nèi)存塊的地址信息作為值，以鍵值對(duì)的形式存儲(chǔ)內(nèi)存塊的地址，并在內(nèi)存塊實(shí)體的首部與尾部添加標(biāo)識(shí)信息。為檢驗(yàn)算法效果，設(shè)計(jì)了多組數(shù)據(jù)對(duì)新算法和現(xiàn)有經(jīng)典內(nèi)存管理算法效率進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明新算法在降低時(shí)間開(kāi)銷(xiāo)，保留較大連續(xù)空間，減少內(nèi)存碎片等方面具有較明顯的改善。

關(guān)鍵詞：動(dòng)態(tài)內(nèi)存分配；內(nèi)存碎片；邊界標(biāo)識(shí)法；multimap

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）30-0222-02

Algorithm of Dynamic Memory Allocation Base on Multimap

CAO Hai-tao， YU Yong-hong

（.School of Management and Engineering， Anhui University of Finance & Economic， Bengbu 233030， China）

Abstract： Under the consideration of efficiency and memory fragments indictors， a variety of dynamic memory allocation algorithms were compared and analyzed， and a new dynamic memory allocation based on multimap was proposed. The algorithm put the size of the memory block as the key and the address of the memory block as the value， used the key-value pair to store the address of memory block， and added the boundary tag at both the head and tail of memory block. In order to verify the performance of new algorithm， multiple sets of experiment data were tested on new algorithm and existing classic algorithms of memory allocation.The experiment results show that the new algorithm has obviously improved on time cost， keeping large contiguous space and memory fragments reduction.

Keywords： dynamic memory allocation； memory fragmentation； the boundary tag method； multimap

動(dòng)態(tài)內(nèi)存分配使用靈活，廣泛地應(yīng)用于實(shí)際開(kāi)發(fā)中。在程序的運(yùn)行中，更是頻繁使用動(dòng)態(tài)的內(nèi)存分配方式，因此對(duì)動(dòng)態(tài)內(nèi)存分配的算法效率有著較高要求。目前動(dòng)態(tài)內(nèi)存分配算法主要的兩類(lèi)為，基于順序搜索的動(dòng)態(tài)內(nèi)存分配算法[1，2，3，4]與基于索引搜索動(dòng)態(tài)內(nèi)存分配算法[1-2，5-7]。

首次適應(yīng)算法[1-4]。將可用內(nèi)存塊安置在空閑鏈表中，分配時(shí)總是從空閑鏈表首部開(kāi)始查詢，并將首個(gè)滿足的內(nèi)存塊分配出去，該算法有效的保留了高地址端的大空閑區(qū)。缺點(diǎn)：在空閑鏈表的首部（物理空間的首部）容易產(chǎn)生大量的小碎片，且增加了下一次的查詢次數(shù)。

循環(huán)首次適應(yīng)法[1-2]。與首次適應(yīng)法相似，循環(huán)首次適應(yīng)法可以將產(chǎn)生的小碎片均勻的分布，有效地縮短了下次查詢的時(shí)間，但是仍然沒(méi)有有效地解決存儲(chǔ)空間碎片化的問(wèn)題，而且會(huì)導(dǎo)致缺少大的空閑分區(qū)。

最佳適應(yīng)法[1-2，4]。最佳適應(yīng)法可以有效保留較大的內(nèi)存塊，以滿足用戶對(duì)較大連續(xù)存儲(chǔ)空間的需求，但是在內(nèi)存中會(huì)產(chǎn)生更小的碎片。

最差適應(yīng)法[1-2]。將空閑鏈表中的內(nèi)存塊按照大小順序，逆序排列（由大至?。??？梢杂行У販p少碎片的產(chǎn)生，但是內(nèi)存分區(qū)會(huì)缺乏較大的連續(xù)存儲(chǔ)空間。

快速適應(yīng)法[1-2]。將空閑塊按照大小進(jìn)行分類(lèi)，同時(shí)建立一張管理索引表，此算法在查詢內(nèi)存塊時(shí)效率較高O（1），主要缺點(diǎn)在于合并內(nèi)存塊時(shí)，要遍歷所有的內(nèi)存塊時(shí)間復(fù)雜度為O（n）。

伙伴系統(tǒng)[1-2，5-7]。已分配或未分配的內(nèi)存區(qū)大小均為2的k次冪，其時(shí)間性能比快速適應(yīng)算法差，但是由于采用了索引搜索算法，比順序搜索算法好。而其空間性能，由于對(duì)空閑分區(qū)進(jìn)行合并，提高了內(nèi)存空間的可使用率，故優(yōu)于快速適應(yīng)法，比順序搜索法略差。

哈希算法[1]。哈希算法就是利用哈希快速查找的優(yōu)點(diǎn)，哈希算法具有較高的查找效率，在實(shí)際動(dòng)態(tài)內(nèi)存分配中使用廣泛，但是在合并內(nèi)存時(shí)需要逐個(gè)查找可用內(nèi)存塊并檢查是否為可用的鄰區(qū)內(nèi)存。因此，實(shí)際開(kāi)發(fā)中亟待需求高效的內(nèi)存分配與合并算法?；陧樞蛩阉鞯膭?dòng)態(tài)內(nèi)存分配算法的特點(diǎn)是管理簡(jiǎn)單，但效率不高?；谒饕阉鞯膭?dòng)態(tài)內(nèi)存分配算法的特點(diǎn)是，分配效率較高，但回收效率較低。

兩類(lèi)不同的分配算法在不同的實(shí)際應(yīng)用中有著各自的優(yōu)勢(shì)，但是在大多數(shù)的應(yīng)用開(kāi)發(fā)中普遍存在大內(nèi)存塊不易保留，內(nèi)存碎片化，合并內(nèi)存塊時(shí)間開(kāi)銷(xiāo)大等問(wèn)題[8-9]。multimap映射算法就是指將內(nèi)存塊的大小作為multimap的鍵，對(duì)應(yīng)的值會(huì)記錄內(nèi)存塊的地址信息以供分配[10-11]。該算法可以較好地解決上述問(wèn)題，可以滿足不同應(yīng)用的需求。

1改進(jìn)的內(nèi)存分配算法

基于multimap映射的動(dòng)態(tài)內(nèi)存分配算法采用C++的STL中提供的multimap關(guān)聯(lián)容器，允許多個(gè)相同的鍵存在，鍵與值為一一對(duì)應(yīng)關(guān)系。算法以內(nèi)存塊的大小作為鍵，內(nèi)存塊的地址信息作為值，以鍵值對(duì)的形式存儲(chǔ)內(nèi)存塊的地址，并在內(nèi)存塊實(shí)體的首部與尾部添加標(biāo)識(shí)信息。

1.1內(nèi)存分配算法

算法使用STL中multimap關(guān)聯(lián)容器來(lái)存儲(chǔ)Mcb（自定義的內(nèi)存控制塊）的地址信息。multimap提供了一種可以有重復(fù)鍵值的STL map類(lèi)型。multimap作為為容器的類(lèi)型，以內(nèi)存塊的大小作為鍵，便于查詢內(nèi)存塊。當(dāng)用戶申請(qǐng)內(nèi)存時(shí)，通過(guò)multimap提供的方法去查詢可供用戶使用的內(nèi)存塊。使用lower_bound（k），upper_bound（k）可以得到一組指向鍵為k的元素的迭代器（在有多個(gè)相同鍵值對(duì)的情況下，分別指向元素的首端和尾端），如不存在則兩個(gè)迭代器均指向首個(gè)大于鍵的值元素[11]。

為了避免產(chǎn)生過(guò)小的碎片，定義一個(gè)常量MIN_SIZE。如果切割內(nèi)存塊后會(huì)產(chǎn)生小于MIN_SIZE的碎片，則不再經(jīng)行切割，直接分配供用戶使用。

1.2內(nèi)存釋放、合并算法

內(nèi)存塊在使用后，為了避免產(chǎn)生內(nèi)存大量的碎片。需要在釋放內(nèi)存塊時(shí)，盡可能地將物理空間連續(xù)的內(nèi)存塊合并到一起。在合并內(nèi)存塊時(shí)，需要遍歷空閑內(nèi)存以查找左鄰塊、右鄰塊，時(shí)間復(fù)雜度為O（n）[12-14]。為提高合并效率，本次算法采用邊界標(biāo)識(shí)法[2]。在內(nèi)存塊的首部和尾部添加一些信息（首部添加Mcb類(lèi)型，尾部添加unsigned類(lèi)型記錄此內(nèi)存塊的大?。?。添加邊界標(biāo)識(shí)的內(nèi)存塊信息分布，如下圖1所示：

圖1中的指針p，為返回給用戶的可用內(nèi)存塊首地址。IsAvailable用于標(biāo)識(shí)內(nèi)存塊的可用狀態(tài)，size的大小為包括Mcb與后邊界標(biāo)志在內(nèi)的大小。通過(guò)邊界標(biāo)識(shí)法可使合并內(nèi)存塊的復(fù)雜度為O（1）。

算法步驟：

在合并內(nèi)存塊時(shí)會(huì)查找左鄰塊、右鄰塊，當(dāng)釋放指針p的內(nèi)存區(qū)域時(shí)會(huì)發(fā)生以下步驟：

（1）將指針P回退到內(nèi)存塊的首部，得到Mcb *mcb（使其指向內(nèi)存控制塊的首部）。

（2）檢查當(dāng)前指針是否在堆區(qū)域，指針不可越界。

（3）將mcb->availeble = 1變?yōu)榭捎脿顟B(tài)。

（4）將指針p繼續(xù)回退sizeof（unsigned）個(gè)字節(jié)，讀取左鄰區(qū)的長(zhǎng)度。再將指針p回退size-sizeof（unsigned）字節(jié)，經(jīng)過(guò)強(qiáng)制類(lèi)型轉(zhuǎn)換，讀取Mcb并判斷是否為空閑狀態(tài)，若是則將其從空閑multimap記錄中刪除，與左鄰塊合并后，并將左鄰塊Mcb中的size改為size+mcb->size，將合并后內(nèi)存塊的尾部標(biāo)識(shí)改為size+mcb->size，將指向向左合并后的內(nèi)存塊，重復(fù)執(zhí)行步驟（4）；否則直接跳至步驟（5）。

（5）將指針p向右偏移mcb->size個(gè)字節(jié)，將指針強(qiáng)制類(lèi)型轉(zhuǎn)換為Mcb，讀取available。若右鄰塊為空閑塊，則將其從空閑multimap記錄中刪除，并與p當(dāng)前指向的內(nèi)存塊合并，將mcb->size更新為mcb->size+size，右鄰塊的尾部標(biāo)志的值改為size+mcb->size，重復(fù)執(zhí)行（5）步驟；否則跳至步驟（6）。

（6）將合并后的空閑塊添加到multimap中。添加至multimap中的內(nèi)存塊可能是與左鄰塊合并后的內(nèi)存塊，與右鄰塊合并后的內(nèi)存塊，或者是未合并的內(nèi)存塊。

邊界標(biāo)識(shí)法使得在合并內(nèi)存時(shí)，可以通過(guò)偏移指針直接獲取物理相鄰的內(nèi)存可用信息，所以可使合并內(nèi)存塊的復(fù)雜度為O（1）。

2實(shí)驗(yàn)對(duì)比分析

數(shù)據(jù)準(zhǔn)備：為盡可能的體現(xiàn)每種分配算法的特征（如，體現(xiàn)循環(huán)首次適應(yīng)的特征，應(yīng)當(dāng)至少將內(nèi)存塊的分配循環(huán)一次），本次數(shù)據(jù)元素的選取，將參考實(shí)際應(yīng)用中使用內(nèi)存塊大小的概率，產(chǎn)生若干數(shù)據(jù)元素以組成數(shù)據(jù)集合。本次實(shí)驗(yàn)環(huán)境為：Windows8操作系統(tǒng)，開(kāi)發(fā)工具為vc++6.0。

在實(shí)際使用中，申請(qǐng)的內(nèi)存塊大小近似服從正態(tài)分布。本次模擬中，可供分配的總空間大小為10000個(gè)字節(jié)。參考實(shí)際使用情況，設(shè)定正態(tài)分布中期望與方差，可以得到符合實(shí)際且較為合理的數(shù)據(jù)集合[15-16]。

假設(shè)數(shù)據(jù)元素x ～ N（500， 32400），μ= 500，σ = 180

P{0 < x ≤ 200} = Ф（（200-500）/180） - Ф（-500/180） = 0.0457

P{200 < x ≤ 400} = Ф（（400-500）/180） - Ф（（200-500）/180） = 0.2427

P{400 < x ≤ 600} = Ф（（600-500）/180） - Ф（（400-500）/180） = 0.4176

P{0 < x ≤ 200} = P{800 < x ≤ 1000} = 0.0457

P{200 < x ≤ 400} = P{600 < x ≤ 800} = 0.2427

按照概率隨機(jī)產(chǎn)生23個(gè)樣本，作為申請(qǐng)內(nèi)存的指定大小，并從中隨機(jī)選取6個(gè)元素用于釋放內(nèi)存[16]。通過(guò)計(jì)算可以得到不同大小的內(nèi)存塊使用的概率，以及取樣數(shù)量，如下表1所示。

執(zhí)行順序：

分配內(nèi)存時(shí)，按照Malloc集合中元素的順序進(jìn)行分配。在為528， 604， 345， 523， 621， 494大小的內(nèi)存塊分配內(nèi)存后，按順序分別釋放Free集合中的元素。

對(duì)比不同分配算法下的實(shí)驗(yàn)結(jié)果，比較不同尺寸空閑塊數(shù)量，以及空閑塊最值可以得到圖2、圖3：

編號(hào)1， 2， 3， 4， 5分別代表者首次適應(yīng)法，循環(huán)首次適應(yīng)法，最佳適應(yīng)法，最差適應(yīng)法，基于multimap映射算法。

通過(guò)圖2可以看出，在不同尺寸空閑塊數(shù)量的比較上，首次適應(yīng)法與最佳適應(yīng)法具有相同的結(jié)果。循環(huán)首次適應(yīng)法與最差適應(yīng)法產(chǎn)生大于200個(gè)字節(jié)的內(nèi)存塊數(shù)量較多，首次適應(yīng)法、循環(huán)首次適應(yīng)法、最佳適應(yīng)法均產(chǎn)生了不同數(shù)量的內(nèi)存碎片。multimap映射法沒(méi)有產(chǎn)生內(nèi)存碎片，且大于200個(gè)字節(jié)的內(nèi)存塊數(shù)目不多。

通過(guò)圖3可以看出，首次適應(yīng)法、最佳適應(yīng)法在空閑塊的最值比較上具有相同的結(jié)果，保留了較大的連續(xù)空間，同

時(shí)產(chǎn)生了難以利用的內(nèi)存碎片。循環(huán)首次適應(yīng)法、最差適應(yīng)法未能保留較大連續(xù)空間，且循環(huán)首次適應(yīng)法產(chǎn)生了內(nèi)存碎片，但碎片尺寸大于首次適應(yīng)法與最佳適應(yīng)法所產(chǎn)生的碎片。multimap映射法保留了較大的連續(xù)空間，且未產(chǎn)生內(nèi)存碎片。

由圖2、圖3的分析表明，multimap映射法在保留較大連續(xù)空間、減少內(nèi)存碎片方面具有一定的優(yōu)勢(shì)。

不同的分配算法選取的數(shù)據(jù)結(jié)構(gòu)可能存在一定的差異，通過(guò)分析不同算法所采用的數(shù)據(jù)結(jié)構(gòu)以及具體操作的時(shí)間開(kāi)

銷(xiāo)，并參考圖2、圖3的實(shí)驗(yàn)結(jié)果。可以對(duì)不同內(nèi)存分配算法的效率進(jìn)行比較，從而得到具有更低時(shí)間開(kāi)銷(xiāo)的分配算法。整理結(jié)果可得如下表2：

由表2可以看出，在分配內(nèi)存上最差適應(yīng)法與multimap映射法具有較低的時(shí)間復(fù)雜度，分別為O（1）、O（log n）。在回收內(nèi)存上multimap映射法的時(shí)間復(fù)雜度為O（1），優(yōu)勢(shì)較為明顯。經(jīng)綜合比較可以發(fā)現(xiàn)multimap映射法在降低時(shí)間開(kāi)銷(xiāo)、保留較大連續(xù)空間、減少內(nèi)存碎片方面具有較為明顯的優(yōu)勢(shì)。

3結(jié)束語(yǔ)

對(duì)幾種動(dòng)態(tài)內(nèi)存分配算法進(jìn)行分析與對(duì)比，可以看出選取不同的數(shù)據(jù)結(jié)構(gòu)會(huì)對(duì)效率產(chǎn)生顯著地影響。multimap映射算法通過(guò)紅黑樹(shù)的組織存儲(chǔ)形式，提高了內(nèi)存塊的分配與回收的效率，通過(guò)邊界標(biāo)識(shí)法極大地改善了內(nèi)存塊合并的效率。雖然邊界標(biāo)識(shí)法是以消耗一定空間的方式來(lái)提升速度，但是當(dāng)消耗的空間所占有效空間的比例較小時(shí)，是可以接受的?？傮w上，multimap算法較好地解決了大內(nèi)存塊不易保留，易產(chǎn)生碎片，合并內(nèi)存時(shí)間開(kāi)銷(xiāo)大等問(wèn)題。

參考文獻(xiàn)：

[1]湯小丹，梁紅兵，哲鳳屏，湯子瀛.計(jì)算機(jī)操作系統(tǒng)（第四版）[M].西安：西安電子科技大學(xué)出版社，2014.

[2]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版[M].北京：清華大學(xué)出版社，2007.

[3]Weinstock C.Dynamic Storage Allocation Techniques[D].Carnegie-Mellon University， Pittsburgh，1976.

[4]池元武.嵌入式實(shí)時(shí)操作系統(tǒng)動(dòng)態(tài)內(nèi)存管理優(yōu)化方案的研究[D].上海交通大學(xué)軟件學(xué)院， 2011.

[5]Peterson J L，Norman T A.Buddy Systems[J].Communications of the ACM， 2007， 20（6）：421-431.

[6]姜立波.Linux內(nèi)存管理分析與研究[D].電子科技大學(xué)，2011：46-58.

[7]王振江.提高堆數(shù)據(jù)局部性的動(dòng)態(tài)池分配技術(shù)[J].計(jì)算機(jī)學(xué)報(bào)，2011（4）：665-675.

[8]Stephenson C J. Fast Fits： New Methods for dynamic storage allocation[C]. Proceedings of the 9th Symposium on Operating Systems， ACM， 1983.

[9]McKusick M.K，Karels M J.Efficient Kernel Memory Allocation on Shared-Memory Multiprocessors. Proceedings of the Winter USENIX Technical Conference，1993.