高效動態存儲再分配方案與實現

胡平平，王晶杰

（北京信息科技大學 自動化學院，北京100192）

0 引 言

傳統的動態存儲管理 （DMM）有首先適配法、再次適配法、最佳適配法和最壞適配法4種方法［1］，許多文獻也提出了各種改進算法以提高DMM 的性能，如利用二叉樹來管理內存分區以提高DMM 的效率［2］；利用虛擬內存管理實現DMM，以便有效降低時間耗費［3］；改進DMM 算法降低分配失敗率［4］、或改善內存泄漏［5］、或改進動態內存分配的脆弱性并提高內存分配安全性［6］等。有些研究者則注重不同應用對DMM 需求的差異，希望找到其需求特性以提供最佳策略［7－9］。文獻 ［10］通過模擬應用的內存分配需求，從所提供的多種分配方法中選擇最適合的，以便在存儲區使用量和處理功耗方面取得好的效果。這些改進措施可分為兩類：一類是在系統級對DMM 進行改進，使其對各種動態存儲的需求都具有較優的性能；另一類則針對具體應用的特性，分別提供不同的最佳方法。

筆者發現，在需要連續存儲大量大小和數量均不確定的數據時，若直接使用系統的DMM 實現，其空間利用率和執行效率都比較差。為此，本文提出了動態存儲再分配（DMRA）方案，該方案有效地減少了對系統DMM 的執行次數，不僅明顯提高了存儲空間的利用率，還極大地提高了存儲空間的分配速度。

本文以VC＋＋6.0控制臺應用程序為例，先分析指出了常規動態存儲分配存在的問題，然后介紹了DMRA 方案和實現算法，在對其性能進行了簡單的理論分析之后，用多個實例數據進行了測試，最后給出了改進方案和注意事項。實例數據的測試結果表明該方案能節省36%至75%的存儲空間，而分配速度則提高了20～50倍。

1 常規動態存儲分配存在的問題

C語言實現DMM 的基本函數是malloc（），VC＋＋系統又為其提供了DEBUG （以下簡稱D 版）和RELEASE（以下簡稱R 版）兩種不同版本的代碼。malloc（）每分配一塊存儲空間，都要使用一些額外的空間以實現DMM，兩種版本代碼所使用的額外空間和執行時間不同，因此其效率也不相同。如要分配長度是L 字節的空間，實際使用的存儲空間長度AL 為

兩種版本的BaseL 都是8 （實際上是鏈表兩個指針占用的空間），R 版的ExtraL 為0，D 版的ExtraL 是36 （實際上是一個32字節的信息頭和4字節的安全預留），即：

D 版

R 版

令WL＝AL－L，這就是每次內存分配的浪費空間，D版的WL 在44 （L%16＝12時）至59 （L%16＝13時）之間；而R 版的WL 在8 （L%16＝0 時）至23 （L%16＝1時）之間。顯然，在L 較小時WL 與L 相比還是很可觀的，若用malloc（）為大量小長度數據申請動態存儲空間，則會導致系統存儲空間的巨大浪費。

在比較不同處理方法的執行時間時，處理所執行的CPU 指令數量是較可靠的依據。由于本文僅涉及動態儲存連續分配的情況 （即分配結束前不釋放任何所分配的空間），因此下面僅對malloc（）函數被連續調用的情況進行分析。跟蹤分析發現，malloc（）代碼的執行由下面3部分構成

其中，BaseI是固定執行的指令數量，ScanI 是執行串掃描指令的重復次數，StosI 是執行串存儲指令的重復次數。malloc（）對存儲區的處理是以4KB 為單位進行的，其過程按當前要分配存儲區長度的不同可分兩種情況 （用圖1來說明）。圖中每個粗矩形框表示一個4KB 存儲區域，左邊為低地址，陰影部分為已分配的空間，P0為當前可分配空間的起始位置，B1和B2分別為P0后面兩個4KB 存儲區的邊界位置。

圖1 malloc（）對存儲空間的處理方法

情況1：分配空間的結束位置為P1，也即可與P0在同一個4KB內完成分配。ScanI的處理是掃描P0至B1之間是否為0xFEEEFEEE （以下簡稱DD1），StosI 的處理分3部分：第一部分是將P1至B1之間填充為DD1，第二部分是將P0至P1之間填充為0xBAADF00D，第三部分 （僅D版）是將P0至P1之間實際申請長度的空間填充為0xCDCDCDCD。

情況2：分配空間的結束位置為B1之后的P2，即不能與P0在同一個4KB內完成分配。ScanI的處理有兩部分，StosI的處理則有4部分，依次是：掃描P0至B1之間是否為DD1，將P0至B2之間填充為DD1，掃描P0至B2之間是否為DD1，將P2至B2之間填充為DD1，將P0至P2之間填充為0xBAADF00D，（僅D 版）將P0至P2之間實際申請長度的空間填充為0xCDCDCDCD。

上述串指令的重復次數不僅和P1的位置有關，還和申請長度有關，本文涉及的分配長度有兩類，分別為1至255（平均長15至25）和固定長度2048，因此B1和B2一定是相鄰的兩個4KB區域。下面以第一類情況1的D 版為例，說明其平均指令數量的求解方法。

首先固定執行的指令數量BaseI＝716；掃描區域最短8，最長4KB－8，平均長2KB，按雙字為單位掃描，掃描指令平均重復次數為512；同理，第一次填充指令的平均重復次數也為512；第二次填充區域長度為申請長度與16B對齊后加0x30，最短64，最長304，平均184，平均重復次數為46；第三次填充區域最短4，最長256，平均長130，平均重復次數為32。因此，申請長度為1至255情況1的D版malloc（）所執行指令的平均總數量為2076。同理可以計算出情況2的D 版執行指令的平均總數量為3560。至于情況1和情況2出現的概率應該按平均申請長度15至25來計算，其實際使用空間的長度是72。因為儲存分配的間隔是8的倍數，按均勻分布在4 KB 范圍內計算，則共有1024種情況，其中只有72／8＝9 種會導致情況2。因此，申請長度為1至255的D 版malloc（）執行指令總數量的平均為：2076· （1024－9）／1024＋3560·9／1024＝2089。同樣方法可以計算出其它情況下malloc（）函數執行的指令數量，見表1。

表1 各種情況下malloc（）函數執行指令的數量

DMM 之所以需要額外的存儲空間并執行相對復雜的操作，是為了較好地滿足復雜的儲存申請和釋放需求。但在實際應用程序中，經常需要連續動態存儲大量的短長度數據，且在完成所有數據的儲存之前，不需要釋放任何空間。在這種情況下，若用malloc （）為每一個數據申請空間，不僅會導致系統存儲空間的巨大浪費，而且還執行了大量沒必要的操作。為解決這個問題，本文提出了一種動態儲存再分配方案，可以有效改善該情況下動態儲存的空間利用率和執行效率。

2 DMRA 方案

所謂動態儲存再分配方案是將零散的動態儲存申請轉換為集中申請，并利用簡單的本地分配策略對已申請的存儲空間進行有效的再分配。現以短數據連續動態儲存為例加以說明。

圖2是用malloc（）連續為N 個短數據單獨申請存儲空間的分布情況。其中P1至PN為申請到的N 個數據儲存區域的指針，每個實箭頭線表示一次對malloc （）函數的調用，得到的存儲區域用粗線矩形表示，其陰影部分為DMM 占用的額外空間。

圖2 為N 個短數據單獨申請存儲空間的分布

圖3 DMRA 方法為N 個短數據申請存儲空間的分布

從上圖可以看出，DMRA 方案具有更高的存儲空間利用率和較少的malloc（）調用次數，而本地分配處理非常簡單，因此DMRA 將具有更快的速度。

3 DMRA 的實現

DMRA 的實現要在滿足應用需求的前提下保證其執行速度。由于數據的數量N 不確定，因此存儲塊的數量M 也不確定，指針BPi必須用動態數組儲存。雖然C＋＋提供了vector模板類可以方便地實現動態數組，但其效率非常低，因此本文直接利用realloc （）實現BPi的動態儲存。為了使用方便，DMRA 僅需實現一個和malloc（）完全相同函數，其原型為：

void＊DMRAalloc（size＿t size）；

實現DMRA 算法需要設置的常量和變量以及各變量的初始值如下所示：

＃define INC＿BLK＿NUM 128 ／／Bpi動態數組遞增長度

＃define BLK＿LEN 2048 ／／每個存儲塊的長度

char＊＊pBP＝NULL； ／／Bpi動態數組指針

int BPLen＝0； ／／Bpi動態數組長度

調查顯示，創業的動機包括獲得財富、自我實現、親友支持、社會支持，創業動機與少數民族大學生創業能力正相關，相關系數為0.72，其中，自我價值實現與創業力相關性最顯著。

char＊CntMemBuf； ／／當前存儲塊首地址

int BlkIdx＝－1； ／／當前使用的存儲塊下標

int NextPos＝BLK ＿LEN； ／／當前存儲塊下一個地址

基本DMRAalloc（）函數的實現流程如圖4所示，pBf是該函數僅有的一個局部指針變量。從各變量的初始值可以看出，第一次調用該函數將自動調用malloc （）申請第一個存儲塊，同時也將第一次調用realloc（）為存儲塊指針分配空間。而本地分配處理則簡單到僅有兩次加法賦值和一次判斷。

圖4 基本DMRA 算法的流程

4 DMRA的設計要點

為了保證DMRA 算法的正確性及較高的空間利用率，必須注意下述設計要點：

（1）BLK＿LEN 必須大于等于所申請存儲空間的最大長度。

（2）DMRA 算法的空間利用率和BLK＿LEN 與平均申請長度的比成正比。

（3）每個存儲塊后部的剩余空間沒有使用，最壞情況下，該剩余空間是最大申請長度減一。

（4）在總申請空間小于存儲塊長度情況下，DMRA 的空間利用率反而會比直接用DMM 低。

（5）DMRA 算法沒有考慮存儲空間起始地址的對齊問題。實際上，若要與A＝2k對齊，只需將NextPos＋＝size改為NextPos＝ （NextPos＋size＋A－1）＆～（A－1），將NextPos＝size改為NextPos＝ （size＋A－1）＆～（A－1）即可。

（6）當不再使用由DMRA 申請的存儲空間時，必須將動態數組pBP中的BlkIdx＋1個指針都釋放掉。為了盡量保證系統存儲空間的連續性，建議按倒序的順序釋放，最后還要釋放指針pBP。

5 DMRA 的改進

基本DMRA 算法只能完成一次多存儲區的連續分配，在實際應用中，當處理完這些數據后，常需對同類型的其它數據進行相同的處理。雖然可以將DMRA 所申請的存儲塊釋放后重新初始化變量再次使用，但這樣沒有充分利用DMRA 執行效率的優勢。改進的DMRA 算法不僅能實現多次連續分配，而且使后續分配具有更高的執行效率。其原理是：不釋放DMRA 已申請的存儲區，僅通過變量的重新設置，實現多次連續存儲DMRA 已申請空間的再使用。為此，僅需再設置一個表示Bpi動態數組中已申請存儲塊的數量BlkNum，其初始值為0，并對基本DMRA 算法進行改進，如圖5所示。

再次使用DMRA 算法連續為其它數據分配空間前需要進行下述設置：

如果BlkNum 非零 （表示上一次DMRA 至少為一個數據分配了空間），則將BlkIdx和NextPos 清零，并將Cnt－MemBuf設置為pBP ［0］；如果BlkNum 為零，則不用改變任何變量的值。這樣，新數據的空間將從上次第一個存儲塊開始分配。若新數據使用的空間沒有上次大，則不需要申請任何新的存儲塊；當新數據空間比上次大時，DMRA會繼續申請新的存儲塊，直到滿足需求為止。

跟蹤測試得出改進的DMRA 算法函數在各種情況下執行指令的數量如表2所示，其中的3473和2679使用了表1的最后一列數據，且假設realloc（）和malloc（）函數的數據一樣。

將表2第二列數據與表1第四列數據對比，對于為長度在1至255的數據分配存儲空間時，DMRA 本地分配的執行速度分別是直接調用malloc（）的近44 （2089／47）和127 （1781／14）倍，可見DMRA 有非常快的執行速度。

6 DMRA 性能的實際測試

與常規DMM 性能相比，DMRA 的改進程度與許多因素有關，下面以實際測試的數據為例加以說明。本實例用DMRA 方法為儲存大量隨機長度的文件名稱字符串分配空間，這些文件可能是一個磁盤或一個文件夾中的所有文件。

圖5 DMRA 改進算法的流程

表2 改進的DMRA 算法函數各種情況執行指令的數量

WindowsXP系統下文件名稱的長度從1至255不等，數量從幾百至幾萬不等，非常適合于用本文介紹的DMRA 方法為之分配存儲空間。

測試程序對所處理的文件數量和文件名長度進行了統計，按式 （2）和式 （3）計算出每一個文件名實際使用的空間，求和則是直接用malloc （）分配所用的空間。根據DMRA 處理所使用的存儲塊數量則可直接算出使用DMRA分配所用的空間。

在執行時間方面，直接分配的時間是文件數量乘以單個malloc（）的平均執行指令數量，而DMRA 的時間則分別是：

D 版

R 版

其中，3500和2703是表2第三列與第二列的差，3488 和2691則是第四列與第三列的差，分別表示為申請存儲塊和動態數組而額外執行的指令數量。

表3是對5個不同對象的實際測試數據，表4則是他們的對比結果。圖6和圖7分別是第二和第三個對象文件名長度的分布圖 （由測試程序自動生成）。

表3 5個不同對象的實際測試數據

表4 5個不同對象DMRA與直接分配方法的空間和速度比

圖6 C盤文件名長度的分布圖和基本數據

圖7 D 盤文件名長度的分布圖和基本數據

當DMRA 用于多次連續存儲區分配時，在無需申請新存儲塊的情況下，與直接分配的速度比是常數，D 版為2089／61＝34.25，而R 版則為1781／24＝74.21。

表4和表5中第一個對象是個用于測試的數據，其中僅含不同長度的文件37個，由于僅需一個存儲塊，且該存儲塊尚有1636個空間沒有使用，因此其空間利用率最小，R 版下甚至還不如直接分配 （幾乎比直接分配還多用一倍的空間），可見，DMRA 在數據量少的情況下，并無優勢。后4個對象的數據量很大，實際數據表明，D 版DMRA 使用的空間才幾乎是直接分配方法的1／4 （24.9% 至33.4%），R 版則是直接分配方法的一半多一些 （53.5%至63.3%）。速度方面，DMRA 在各種情況下都有較大的優勢，D 版DMRA 的速度是直接分配方法的23至28倍，R版則是更高的37至50倍。

7 結束語

本文對需要連續為大小和數量均不確定的海量數據動態分配存儲空間的問題進行了研究，在細致分析了直接利用malloc（）存在的問題后，提出了一種高效的動態存儲再分配方案，并給出了實現該方案的高效算法。實際測試結果表明，該方案有效地減少了系統動態存儲管理的執行次數，在明顯節省系統存儲空間36%至75%的同時，分配速度提高了20～50倍，在重復多次使用的情況下速度提高最多達70倍，該方法在作者開發的多個以磁盤文件為處理對象的軟件中得到應用，效果明顯。

［1］LI Jun.A brief analysis on dynamic memory management in C／C＋＋program ［J］.Xinjiang Radio and TV University Journal，2009，13 （2）：53－54 （in Chinese）.［李軍.淺析C／C＋＋程序運行過程中的動態存儲管理 ［J］.新疆廣播電視大學學報，2009，13 （2）：53－54.］

［2］HU Bin，SUN Jianli，ZHANG Yongping，et al.Research and implementation of technique for memory management ［J］.Computer Engineering and Design，2007，28 （5）：1226－1228（in Chinese）.［胡濱，孫健力，張永平，等.一種內存管理技術的研究與實現 ［J］.計算機工程與設計，2007，28 （5）：1226－1228.］

［3］WEI Haitao，JIANG Yuming，LI Jianwu，et al.Research of high efficient implementation of memory management mechanism ［J］.Computer Engineering and Design，2009，30 （16）：3798－3712 （in Chinese）.［魏海濤，姜昱明，李建武，等.內存管理機制的高效實現研究 ［J］.計算機工程與設計，2009，30 （16）：3798－3712］.

［4］Zhao Feimeng，Shu Dong Zhang.Buddy algorithm optimization in linux memory management［J］.Applied Mechanics and Materials，2013，2746 （423）：746－2750.

［5］Varlese，Marco.Improving performance for dynamic memory allocation［J］.Embedded Systems Design，2009，22 （5）：21－29.

［6］Yves Younan，Wouter Joosen，Frank Piessens.Improving memory management security for C and C＋＋ ［J］.International Journal of Secure Software Engineering，2010，1 （2）：57－82.

［7］Florence Charreteur， Bernard Botella， Arnaud Gotlieb.Modelling dynamic memory management in constraint－based testing ［J］.Journal of Systems and Software，2009，82 （11）：1755－1766.

［8］Marja del Mar Gallardo，Pedro Merino，David Sanon.Model checking dynamic memory allocation in operating systems［J］.Journal of Automated Reasoning，2009，42 （2）：229－264.

［9］Jose L Risco－Martin，Manuel Colmenar J，Ignacio Hidalgo J.A methodology to automatically optimize dynamic memory managers applying grammatical evolution ［J］.The Journal of Systems ＆Software，2014，91 （1）：109－123.

［10］Jose L Risco－Martin，Manuel Colmenar J，David Atienza.Simulation of high－performance memory allocators ［J］.Microprocessors and Microsystems，2011，35 （8）：755－765.