基于多級緩存的內存管理方案

丁 銳，張亞君，陳 維

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

0 引言

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

1 內存管理模型

本文所設計的內存管理方案模型如圖1所示。

圖1 內存管理模型

本內存管理方案通過3級緩存來實現內存的快速分配與回收:

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

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

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

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

2 內存管理原理

2.1 內存分類

本內存管理方案將內存分為3種:

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

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

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

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

2.2 各級緩存的交互

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

圖2 慢啟動過程示意圖

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

二級緩存與三級緩存以對齊SPAN為交互方式。二級緩存沒有SPAN供切割時，向三級緩存申請一個對齊的SPAN;二級緩存中的空閑SPAN達到一定的門限時，向三級緩存釋放一定數量的對齊SPAN，三級緩存根據得到的對齊SPAN進行適當的合并。

2.3 內存塊的切割與合并

應用進程使用的內存都源于SPAN的切割。內存塊與SPAN的關系如圖3所示。

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

圖3 SPAN與內存塊

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

2.4 內存申請、釋放流程

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

圖4 內存申請、釋放流程

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

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

3 本內存管理方案與PTmalloc的性能比較

本內存管理方案通過引入多級緩存結構和SPAN結構來實現性能的提升:

(1)在多級緩存結構中，通過慢啟動過程動態控制內存池的長度，提高了大批量內存分配速度，并緩解了多級緩存導致的內存浪費問題;

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

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

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

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

表1 small內存測試結果

表2 large、huge內存測試結果

4 結束語

本文的內存管理方案結合了PTmalloc的優點，同時對PTmallo的缺陷進行了優化。實現了內存的快速、穩定分配，很好的解決了大批量內存分配導致的速度慢和內存碎片問題。本文的內存管理方案適用于路由器等反復進行大批量的內存申請的操作系統。

［1］ 王錚，李志軍.一種適用嵌入式系統的自適應動態內存管理方案［J］.計算機技術與發展，2007，17(3):50－54.

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

［3］ 郝慶豐.返璞歸真－UNIX技術內幕［M］.北京:電子工業出版社，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］.北京:北京航空航天大學出版社，2006:105 －109.