国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2011-09-04 06:08張亞君
關(guān)鍵詞:線程步長進(jìn)程

丁 銳,張亞君,陳 維

(杭州電子科技大學(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ù)是實(shí)現(xiàn)內(nèi)存分配的高效性、可靠性和實(shí)時性,保證系統(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級緩存來實(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合并而成。

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ù)實(shí)際應(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)來實(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é)果

4 結(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.

猜你喜歡
線程步長進(jìn)程
基于Armijo搜索步長的BFGS與DFP擬牛頓法的比較研究
基于C#線程實(shí)驗(yàn)探究
基于國產(chǎn)化環(huán)境的線程池模型研究與實(shí)現(xiàn)
債券市場對外開放的進(jìn)程與展望
改革開放進(jìn)程中的國際收支統(tǒng)計
淺談linux多線程協(xié)作
基于逐維改進(jìn)的自適應(yīng)步長布谷鳥搜索算法
一種新型光伏系統(tǒng)MPPT變步長滯環(huán)比較P&O法
社會進(jìn)程中的新聞學(xué)探尋
一種新穎的光伏自適應(yīng)變步長最大功率點(diǎn)跟蹤算法