基于多級緩存的內(nèi)存管理方案

丁 銳，張亞君，陳 維

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

0 引言

隨著計算機(jī)技術(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)的正常運(yùn)行［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)二級緩存，進(jìn)程級別的緩存，每進(jìn)程一緩存，管理大量的內(nèi)存塊;

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

由圖1可知，一級緩存與二級緩存通過批量的內(nèi)存塊進(jìn)行交互，二級緩存與三級緩存通過對齊SPAN進(jìn)行交互，三級緩存與操作系統(tǒng)通過非對齊SPAN進(jìn)行交互。SPAN是具有一定頁面數(shù)的內(nèi)存，用于切割成小內(nèi)存塊供用戶進(jìn)程使用。本內(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達(dá)到4N時停止增長;當(dāng)一級緩存內(nèi)存池的內(nèi)存塊個數(shù)大于Num時，若Num大于N，則以N為步長減少Num，否則逐漸減少到1。

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

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

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

SPAN根據(jù)用戶進(jìn)程的需要按照需要多少切割多少的原則被切割為多個大小相同的內(nèi)存塊。在本內(nèi)存分配方案中，SPAN的切割一般都是批量的切割，為了保證內(nèi)存分配的效率，Small內(nèi)存的切割與Large內(nèi)存的切割有所區(qū)別:Large內(nèi)存的切割引用PTmalloc的內(nèi)存頭邊界標(biāo)記切割，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)存時，直接在二級緩存中進(jìn)行內(nèi)存的邊界標(biāo)記切割與合并。

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)存浪費(fèi)問題;

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

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

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

通過PTmalloc自帶的測試用例測試(20個線程隨機(jī)申請、隨機(jī)釋放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的缺陷進(jìn)行了優(yōu)化。實現(xiàn)了內(nèi)存的快速、穩(wěn)定分配，很好的解決了大批量內(nèi)存分配導(dǎo)致的速度慢和內(nèi)存碎片問題。本文的內(nèi)存管理方案適用于路由器等反復(fù)進(jìn)行大批量的內(nèi)存申請的操作系統(tǒng)。

［1］ 王錚，李志軍.一種適用嵌入式系統(tǒng)的自適應(yīng)動態(tài)內(nèi)存管理方案［J］.計算機(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.