丁 銳，張亞君，陳 維

(杭州電子科技大學(xué)電子信息學(xué)院，浙江杭州310018)

0 引言

隨著計算機技術(shù)和數(shù)字技術(shù)的不斷發(fā)展，嵌入式系統(tǒng)在國防和社會生活中得到了廣泛的應(yīng)用。一套內(nèi)存管理方案對嵌入式系統(tǒng)顯得越發(fā)重要。在嵌入式平臺上，首次出現(xiàn)的是GNU的面向單線程的dlmalloc，隨著嵌入式系統(tǒng)對內(nèi)存需求的增加，GNU在dlmalloc的基礎(chǔ)上提出了面向多線程的PTmalloc。內(nèi)存管理主要任務(wù)是實現(xiàn)內(nèi)存分配的高效性、可靠性和實時性，保證系統(tǒng)的正常運行［1］，但PTmalloc并不能很好的適應(yīng)大批量的內(nèi)存申請，本文在PTmalloc的基礎(chǔ)上提出了基于多級緩存的內(nèi)存管理方案。

1 內(nèi)存管理模型

本文所設(shè)計的內(nèi)存管理方案模型如圖1所示。

圖1 內(nèi)存管理模型

本內(nèi)存管理方案通過3級緩存來實現(xiàn)內(nèi)存的快速分配與回收:

(1)一級緩存，線程級別的緩存，每線程一緩存，管理少量的內(nèi)存塊;

(2)二級緩存，進程級別的緩存，每進程一緩存，管理大量的內(nèi)存塊;

(3)三級緩存，進程級別的緩存，每進程一緩存，管理從操作系統(tǒng)申請的大批量內(nèi)存。

由圖1可知，一級緩存與二級緩存通過批量的內(nèi)存塊進行交互，二級緩存與三級緩存通過對齊SPAN進行交互，三級緩存與操作系統(tǒng)通過非對齊SPAN進行交互。SPAN是具有一定頁面數(shù)的內(nèi)存，用于切割成小內(nèi)存塊供用戶進程使用。本內(nèi)存管理方案中的SPAN分為對齊SPAN(固定頁面數(shù))和非對齊SPAN，二級緩存管理對齊SPAN，三級緩存以地址排序鏈的形式分別管理對齊SPAN和非對齊SPAN，非對齊SPAN主要由對齊SPAN合并而成。

2 內(nèi)存管理原理

2.1 內(nèi)存分類

本內(nèi)存管理方案將內(nèi)存分為3種:

(1)Small內(nèi)存，大小在［8，4K］，該種內(nèi)存有一級緩存;

(2)Large內(nèi)存，大小在(4K，32K］，該種內(nèi)存沒有一級緩存;

(3)Huge內(nèi)存，大小在(32K，∞)，該種內(nèi)存只有三級緩存。

根據(jù)實際應(yīng)用系統(tǒng)的情況，本內(nèi)存管理方案再將Small內(nèi)存按不同的步長分為56種，每個一級緩存和二級緩存均有56個鏈表形式的內(nèi)存池［2］與之相對應(yīng)。

2.2 各級緩存的交互

一級緩存與二級緩存以批量的內(nèi)存塊為交互方式，在交互過程中，交互內(nèi)存塊個數(shù)隨著該類內(nèi)存使用頻率而動態(tài)變化，稱為慢啟動。如圖2所示。

圖2 慢啟動過程示意圖

當(dāng)一級緩存的內(nèi)存池沒有內(nèi)存塊供分配時，向二級緩存申請Num塊內(nèi)存。慢啟動過程就是控制Num動態(tài)變化的過程:系統(tǒng)初始化時，Num為1，隨著該類內(nèi)存使用頻率的不斷增加，Num逐漸增大到N后以N為步長繼續(xù)增長，當(dāng)Num達到4N時停止增長;當(dāng)一級緩存內(nèi)存池的內(nèi)存塊個數(shù)大于Num時，若Num大于N，則以N為步長減少Num，否則逐漸減少到1。

二級緩存與三級緩存以對齊SPAN為交互方式。二級緩存沒有SPAN供切割時，向三級緩存申請一個對齊的SPAN;二級緩存中的空閑SPAN達到一定的門限時，向三級緩存釋放一定數(shù)量的對齊SPAN，三級緩存根據(jù)得到的對齊SPAN進行適當(dāng)?shù)暮喜ⅰ?/p>

2.3 內(nèi)存塊的切割與合并

應(yīng)用進程使用的內(nèi)存都源于SPAN的切割。內(nèi)存塊與SPAN的關(guān)系如圖3所示。

SPAN根據(jù)用戶進程的需要按照需要多少切割多少的原則被切割為多個大小相同的內(nèi)存塊。在本內(nèi)存分配方案中，SPAN的切割一般都是批量的切割，為了保證內(nèi)存分配的效率，Small內(nèi)存的切割與Large內(nèi)存的切割有所區(qū)別:Large內(nèi)存的切割引用PTmalloc的內(nèi)存頭邊界標記切割，Small內(nèi)存的切割為完全無縫切割:無內(nèi)存頭切割。

圖3 SPAN與內(nèi)存塊

SPAN除了支持內(nèi)存塊的切割外，還支持內(nèi)存塊的合并。此處的合并僅僅只是被釋放的內(nèi)存塊與point指向的地方合并，不能合并的內(nèi)存塊則通過SPAN控制信息以單向鏈表管理。

2.4 內(nèi)存申請、釋放流程

本內(nèi)存分配方案的申請、釋放流程如圖4所示。

圖4 內(nèi)存申請、釋放流程

本內(nèi)存管理方案中，Small內(nèi)存和Large內(nèi)存的申請、釋放大致步驟如圖4。由于Large內(nèi)存沒有一級緩存，在申請、釋放Large內(nèi)存時，直接在二級緩存中進行內(nèi)存的邊界標記切割與合并。

Huge內(nèi)存引用PTmalloc的分配方法:通過mmap與munmap向操作系統(tǒng)申請、釋放［3－5］。

3 本內(nèi)存管理方案與PTmalloc的性能比較

本內(nèi)存管理方案通過引入多級緩存結(jié)構(gòu)和SPAN結(jié)構(gòu)來實現(xiàn)性能的提升:

(1)在多級緩存結(jié)構(gòu)中，通過慢啟動過程動態(tài)控制內(nèi)存池的長度，提高了大批量內(nèi)存分配速度，并緩解了多級緩存導(dǎo)致的內(nèi)存浪費問題;

(2)一個一級緩存嚴格對應(yīng)一個線程，并且一級緩存與二級緩存通過批量內(nèi)存進行交互，大大降低了鎖沖突。PTmalloc存在多個線程對應(yīng)一個分配區(qū)域的問題，導(dǎo)致大量的鎖沖突;

(3)通過地址排序鏈管理SPAN，盡量使用使用過的、地址低的SPAN進行切割。PTmalloc只是對內(nèi)存塊按大小進行排序，切割時會導(dǎo)致過多的內(nèi)存碎片;

(4)一個SPAN對應(yīng)一種大小的內(nèi)存，避免了PTmalloc雜亂無章的內(nèi)存切割與合并，大大提高了內(nèi)存分配速率，降低了內(nèi)存碎片。

通過PTmalloc自帶的測試用例測試(20個線程隨機申請、隨機釋放100 000次)，本內(nèi)存管理方案Small內(nèi)存的處理比PTmalloc快一倍左右，Large與Huge內(nèi)存的處理與PTmalloc不相上下，測試結(jié)果如表1、2所示。

表1 small內(nèi)存測試結(jié)果

表2 large、huge內(nèi)存測試結(jié)果

4 結(jié)束語

本文的內(nèi)存管理方案結(jié)合了PTmalloc的優(yōu)點，同時對PTmallo的缺陷進行了優(yōu)化。實現(xiàn)了內(nèi)存的快速、穩(wěn)定分配，很好的解決了大批量內(nèi)存分配導(dǎo)致的速度慢和內(nèi)存碎片問題。本文的內(nèi)存管理方案適用于路由器等反復(fù)進行大批量的內(nèi)存申請的操作系統(tǒng)。

［1］ 王錚，李志軍.一種適用嵌入式系統(tǒng)的自適應(yīng)動態(tài)內(nèi)存管理方案［J］.計算機技術(shù)與發(fā)展，2007，17(3):50－54.

［2］ Jonathan Bartlett.內(nèi)存管理內(nèi)幕［EB/OL］.http://www.ibm.com/developerworks/cn/linux/，2004 －1 －20.

［3］ 郝慶豐.返璞歸真－UNIX技術(shù)內(nèi)幕［M］.北京:電子工業(yè)出版社，2010:53－55.

［4］ Marshall Kirk McKusick，George V.Neville-Neil.The Design and Implementation of the FreeBSD Operating System［M］.北京:中國電力出版社，2008:141－143.

［5］ Mel Gorman.Understanding the Linux Virtual Memory Manger［M］.北京:北京航空航天大學(xué)出版社，2006:105 －109.