丁 銳,張亞君,陳 維
(杭州電子科技大學(xué)電子信息學(xué)院,浙江杭州310018)
隨著計算機(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ù)是實(shí)現(xiàn)內(nèi)存分配的高效性、可靠性和實(shí)時性,保證系統(tǒng)的正常運(yùn)行[1],但PTmalloc并不能很好的適應(yīng)大批量的內(nèi)存申請,本文在PTmalloc的基礎(chǔ)上提出了基于多級緩存的內(nèi)存管理方案。
本文所設(shè)計的內(nèi)存管理方案模型如圖1所示。
圖1 內(nèi)存管理模型
本內(nèi)存管理方案通過3級緩存來實(shí)現(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合并而成。
本內(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ù)實(shí)際應(yīng)用系統(tǒng)的情況,本內(nèi)存管理方案再將Small內(nèi)存按不同的步長分為56種,每個一級緩存和二級緩存均有56個鏈表形式的內(nèi)存池[2]與之相對應(yīng)。
一級緩存與二級緩存以批量的內(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>
應(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控制信息以單向鏈表管理。
本內(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]。
本內(nèi)存管理方案通過引入多級緩存結(jié)構(gòu)和SPAN結(jié)構(gòu)來實(shí)現(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é)果
本文的內(nèi)存管理方案結(jié)合了PTmalloc的優(yōu)點(diǎn),同時對PTmallo的缺陷進(jìn)行了優(yōu)化。實(shí)現(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.