沈非一，張延園，林 奕

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710129)

0 引言

由于嵌入式環(huán)境中擁有的系統(tǒng)資源通常比較小，尤其是內(nèi)存資源非常寶貴，因此內(nèi)存的利用率將會成為嵌入式系統(tǒng)性能的重要瓶頸。內(nèi)存管理是操作系統(tǒng)的核心模塊之一，主要負(fù)責(zé)組織與調(diào)度內(nèi)存的分配和釋放操作，以供內(nèi)核程序和應(yīng)用程序使用［1］。

靜態(tài)內(nèi)存分配要求編譯時(shí)將程序運(yùn)行所需要的內(nèi)存確定好，在整個(gè)程序運(yùn)行過程中不再進(jìn)行分配和釋放。而動態(tài)內(nèi)存分配可以根據(jù)程序執(zhí)行過程中所需的內(nèi)存大小在運(yùn)行時(shí)進(jìn)行分配。因此相比于靜態(tài)分配，動態(tài)分配更加靈活，內(nèi)存的利用率更高。但是動態(tài)分配在分配時(shí)需要消耗更多的時(shí)間，使得系統(tǒng)的實(shí)時(shí)性能受到一定的影響，算法的碎片率和時(shí)間性能將成為主要的指標(biāo)。

典型的動態(tài)內(nèi)存管理算法有［2］:順序適配(Sequential Fit)、分段空閑鏈表(Segregated Free Lists)、伙伴系統(tǒng)(Buddy System)、二級分段匹配算法(Two Level Segregate Fit)等［3］。結(jié)合一些常見的底層結(jié)構(gòu)策略，如:空閑鏈表、邊界標(biāo)記、位圖、延遲合并［4］等。

衡量一個(gè)動態(tài)內(nèi)存管理算法的優(yōu)劣主要從2 個(gè)方面進(jìn)行考察［5-6］:

1)實(shí)時(shí)性。嵌入式系統(tǒng)為了保證實(shí)時(shí)性，要求內(nèi)存分配過程要盡可能地快，確保系統(tǒng)能夠及時(shí)響應(yīng)，同時(shí)在最壞情況下要使得運(yùn)行時(shí)間有界［7］。

2)內(nèi)存碎片率［8］。主要考察系統(tǒng)的內(nèi)部碎片率，與內(nèi)存的利用率等價(jià)［9］。外部碎片在不同大小的內(nèi)存申請中定義有所差別，外部碎片將導(dǎo)致內(nèi)存分配失敗。本方案中并不把外部碎片作為衡量標(biāo)準(zhǔn)，當(dāng)內(nèi)存分配失敗時(shí)，任務(wù)等待一段時(shí)間再次進(jìn)行申請［10］。

μCos 是基于優(yōu)先級的搶占式的實(shí)時(shí)多任務(wù)嵌入式操作系統(tǒng)［11］，包含實(shí)時(shí)內(nèi)核、任務(wù)管理、時(shí)間管理、任務(wù)間通信同步(信號量、郵箱、消息隊(duì)列)和內(nèi)存管理等功能。其內(nèi)核源碼是開源的，代碼本身十分精簡。μCos 系統(tǒng)本身的內(nèi)存管理算法采用固定式的分區(qū)塊模式，雖然效率比較高，但是不夠靈活，內(nèi)存利用率低下。本文選用μCos-III 操作系統(tǒng)作為實(shí)驗(yàn)平臺來實(shí)現(xiàn)仿真動態(tài)內(nèi)存管理算法，在原有算法的基礎(chǔ)上進(jìn)行改進(jìn)。

1 算法方案與設(shè)計(jì)

主要敘述在μCos 操作系統(tǒng)上實(shí)現(xiàn)的動態(tài)內(nèi)存管理改進(jìn)方案。

1.1 總體方案

針對不同大小的內(nèi)存申請，其碎片率與實(shí)時(shí)性能的特點(diǎn)均有所差別，本文對小塊內(nèi)存以及大塊內(nèi)存的申請進(jìn)行分段處理［12］。

很多學(xué)者的研究已經(jīng)證明，現(xiàn)代程序的內(nèi)存分配均以小塊居多。文獻(xiàn)［13］在復(fù)數(shù)的程序中測試了內(nèi)存的使用，結(jié)果表明88%的內(nèi)存分配小于64 字節(jié)。文獻(xiàn)［14］擁有類似的結(jié)果，它指出90%的內(nèi)存分配在512 字節(jié)以下，并且通常擁有較短的生命周期?？梢钥闯鲂K內(nèi)存具有分配與釋放頻繁、生命周期較短的特點(diǎn)，因此對于時(shí)間性能的要求更高，采用伙伴系統(tǒng)對小塊內(nèi)存進(jìn)行管理，提升內(nèi)存分配與釋放的速度，但是伙伴系統(tǒng)通常伴隨著較高的內(nèi)部碎片率。對于小塊內(nèi)存的申請，內(nèi)存塊本身并不大，系統(tǒng)總體的碎片率不會太高，通過犧牲一定的碎片率來換取時(shí)間性能。

小塊內(nèi)存與大塊內(nèi)存的分界，本文實(shí)現(xiàn)中設(shè)定為128 字節(jié)。雖然嵌入式系統(tǒng)總體以小塊內(nèi)存分配居多，但對于具體的不同系統(tǒng)環(huán)境與負(fù)載還是有所差異。所以將大小塊內(nèi)存分界的臨界值(即此處的128字節(jié))作為系統(tǒng)參數(shù)在初始化時(shí)予以設(shè)定，可以動態(tài)調(diào)整，增加算法應(yīng)用的靈活性。

對于大塊的內(nèi)存申請，以二級分段匹配算法(TLSF)［15］的思想為基礎(chǔ)，利用二級位圖索引來管理空閑內(nèi)存塊，將最壞情況下查找內(nèi)存塊的時(shí)間控制在O(1)。同時(shí)采用FIFO 和LIFO 的方式對二級索引下的內(nèi)存塊分配與釋放進(jìn)行管理，并設(shè)定合并閾值，限制合并操作在一定條件下進(jìn)行。圖1 為系統(tǒng)的總體結(jié)構(gòu)。

圖1 系統(tǒng)總體結(jié)構(gòu)

1.2 小塊內(nèi)存區(qū)的處理方式

首先介紹一下伙伴的概念，滿足以下3 個(gè)條件的稱為伙伴:

1)2 個(gè)塊大小相同;

2)2 個(gè)塊地址連續(xù);

3)2 個(gè)塊必須是從同一個(gè)大塊中分離出來的。

系統(tǒng)初始化時(shí)，維護(hù)一系列的空閑鏈表，大小為1，2，4，8，16，...，2m(此處說明時(shí)使用的內(nèi)存大小單位未標(biāo)明，而是從1 開始，通常情況下在32 位的計(jì)算機(jī)中內(nèi)存塊大小不會小于1 個(gè)字長即4 字節(jié)，此處默認(rèn)大小單位為4 字節(jié)，即最小的內(nèi)存塊大小為1 ×4=4 字節(jié))。在本設(shè)計(jì)中，2m的值即為小塊內(nèi)存與大塊內(nèi)存的分界點(diǎn)。

所有的小塊內(nèi)存受到伙伴塊條件的約束，內(nèi)存塊的分割采取一分為二的方式，而只有互為伙伴的2 個(gè)內(nèi)存塊才可以進(jìn)行合并。

在任務(wù)申請內(nèi)存塊時(shí)，假設(shè)此次申請的大小為k，首先定位需要分配的內(nèi)存大小，即找到一個(gè)i，使得申請的大小k 滿足2i-1＜k≤2i。如果2i的空閑鏈表不為空，則從中取出一個(gè)內(nèi)存塊分配給任務(wù)。如果2i的空閑鏈表為空，則搜索空閑塊長度為2i+1的空閑鏈表;如果不為空，則從該空閑鏈表中取出一個(gè)內(nèi)存塊，把該內(nèi)存塊分割為大小相等2 部分(這2 塊就為伙伴內(nèi)存)，一塊用于分配，另一塊鏈入長度為2i的空閑鏈表中;如果2i+1的空閑鏈表也為空，則依次查找長度為2i+2、2i+3...的空閑鏈表，直到找到空閑內(nèi)存塊并作多次分割。這種分配方式比較靈活，可以滿足各種大小的分配要求，有效緩解了外部碎片的問題(內(nèi)部碎片不可避免)。

在空閑鏈表上以2 的冪次構(gòu)建一級位圖索引，在判斷完內(nèi)存塊大小后可以在O(1)時(shí)間內(nèi)找到對應(yīng)的空閑塊。

在任務(wù)不需要使用某占用塊時(shí)，需要將該內(nèi)存塊釋放，把這塊內(nèi)存插入到相應(yīng)的空閑鏈表中。在插入空閑鏈表之前，需要先判斷該內(nèi)存塊的伙伴塊是否是空閑塊，如果空閑則需要將這一對伙伴塊進(jìn)行合并。然后對合并之后的空閑塊再次判斷伙伴塊是否需要合并，依次類推。

小塊內(nèi)存維護(hù)m +1 個(gè)分段空閑鏈表控制塊結(jié)構(gòu)如下:

1.3 大塊內(nèi)存區(qū)的處理方式

大塊內(nèi)存的處理基于TLSF 算法［16］的基本思想，采用位圖和分段空閑鏈表相結(jié)合的方式對系統(tǒng)中的空閑內(nèi)存塊進(jìn)行管理，位圖索引一共分為2 級［17］。

大塊內(nèi)存區(qū)用到如下幾個(gè)參數(shù):

1)一級索引(First Level Index，F(xiàn)LI):一級索引用來控制一級鏈表的長度，表示了最大的內(nèi)存范圍大小。內(nèi)存區(qū)總共被劃分為FLI 個(gè)大小區(qū)間，一級索引值FLI 對應(yīng)的內(nèi)存大小區(qū)間為［2FLI，2FLI+1)。

2)二級索引(Second Level Index，SLI):二級索引對一級索引劃分的內(nèi)存區(qū)間按照線性順序再次進(jìn)行劃分。二級索引的值在系統(tǒng)初始化前進(jìn)行人為設(shè)定，例如SLI=4，則一級索引的內(nèi)存區(qū)被分割為16 段。其中每一段的大小為［2FLI，2FLI+j* 2FLI-SLI］，j 為該段在內(nèi)存區(qū)中線性順序的序號。SLI 的值決定了一級索引內(nèi)存區(qū)被分割的粒度，SLI 的值越大分割的越細(xì)。一般來說SLI 的值不超過5，即分段數(shù)量不超過32，這樣可以用單個(gè)32 位的位圖來對應(yīng)一級索引內(nèi)存區(qū)中的所有內(nèi)存塊。

3)分割閾值(Split Threshold Value，STV):該參數(shù)替代TLSF 中原有的最小塊大小MBS(Minimun Block Size)。只有當(dāng)分配的內(nèi)存塊大小和申請的內(nèi)存塊大小的差值超越這個(gè)閾值的時(shí)候，才進(jìn)行分割操作，否則直接進(jìn)行分配，此處的閾值設(shè)定為64 字節(jié)。

大內(nèi)存區(qū)控制塊結(jié)構(gòu)如下:

一級索引分區(qū)的控制塊結(jié)構(gòu)如下:

在二級索引中為每個(gè)內(nèi)存塊附加塊頭和塊尾結(jié)構(gòu)來進(jìn)行雙向鏈接。

分配內(nèi)存塊時(shí)，利用一級和二級索引來找到與該內(nèi)存塊大小對應(yīng)的二級內(nèi)存分段，如果該鏈表非空，則查找鏈表的頭結(jié)點(diǎn);如果頭結(jié)點(diǎn)的內(nèi)存塊大于或等于申請的內(nèi)存塊大小，則使用該塊內(nèi)存進(jìn)行分配，并比較分割閾值得出是否需要分割;如果該鏈表為空或者頭結(jié)點(diǎn)大小不滿足分配條件，則直接搜索下一個(gè)非空的內(nèi)存分段，從該分段的空閑鏈表尾部取出一個(gè)內(nèi)存塊，因?yàn)樵诒痉侄蝺?nèi)進(jìn)行分割的話余下的內(nèi)存塊通常過小，所以直接去下一級分段取一個(gè)合適的內(nèi)存塊。查找內(nèi)存塊的時(shí)間依然可以在O(1)內(nèi)完成。

釋放內(nèi)存塊時(shí)，判斷能否與前后的內(nèi)存塊進(jìn)行合并(通過邊界標(biāo)記進(jìn)行判斷)，如果進(jìn)行過合并操作，則將該內(nèi)存塊插入對應(yīng)的分段空閑鏈表尾部，否則將該內(nèi)存塊插入到空閑鏈表頭部。因?yàn)槲膊康膬?nèi)存塊有更大的可能性被分割，可以保證其余內(nèi)存塊在物理上的連續(xù)性。

2 函數(shù)接口

函數(shù)接口的設(shè)定沿用原μCos-III 的結(jié)構(gòu)，修改必要的參數(shù)并實(shí)現(xiàn)新的算法。

1)內(nèi)存池初始化。

初始化的主要任務(wù)是為確定大小內(nèi)存區(qū)的臨界值，設(shè)定大內(nèi)存區(qū)控制塊(FLI、SLI 以及STV 的大小)，并且初始化小內(nèi)存區(qū)伙伴系統(tǒng)的空閑鏈表控制塊、大內(nèi)存區(qū)、一級索引控制塊以及位圖。該接口函數(shù)沒有返回值，調(diào)用它的函數(shù)通過查看p_err 的內(nèi)容來判斷內(nèi)存池初始化是否成功。

2)創(chuàng)建內(nèi)存結(jié)構(gòu)。

該接口的任務(wù)是構(gòu)建起整個(gè)內(nèi)存的結(jié)構(gòu)，將空閑內(nèi)存劃分并掛載到相應(yīng)的空閑鏈表下。

3)申請內(nèi)存塊。

與原μCos-III分配函數(shù)不同，接口參數(shù)只需要傳入申請的內(nèi)存塊大小即可，判斷申請的內(nèi)存屬于小內(nèi)存區(qū)還是大內(nèi)存區(qū)進(jìn)行處理。

4)釋放內(nèi)存塊。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

測試系統(tǒng)選用μCos-III 操作系統(tǒng)，將μCos-III 移植到Windows 平臺下運(yùn)行具體的算法。實(shí)驗(yàn)用PC機(jī)的CPU 為Intel i7-3630QM，主頻2.4 GHz。

實(shí)驗(yàn)利用隨機(jī)數(shù)產(chǎn)生一定大小范圍內(nèi)的內(nèi)存申請和釋放請求，把內(nèi)存的大小范圍分為以下5 個(gè)區(qū)間(單位為字節(jié))，分別為區(qū)間1:［32，64)，區(qū)間2:［64，128)，區(qū)間3:［128，256)，區(qū)間4:［256，512)，區(qū)間5:［512，1024］。在μCos-III 系統(tǒng)中設(shè)計(jì)5 個(gè)任務(wù)，分別產(chǎn)生這5 個(gè)區(qū)間范圍內(nèi)大小的隨機(jī)值，并按照這個(gè)大小申請內(nèi)存，隨后間隔一個(gè)隨機(jī)的時(shí)間進(jìn)行內(nèi)存釋放。每個(gè)任務(wù)一共進(jìn)行500 組分配和釋放操作，任務(wù)之間的分配和釋放是同優(yōu)先級的，根據(jù)隨機(jī)的時(shí)間間隔交替進(jìn)行，最后的結(jié)果取平均值。

在整個(gè)系統(tǒng)運(yùn)行過程中，利用trace 文件記錄每一次操作。每一條trace 包含以下幾條信息:操作類型(分配或釋放內(nèi)存塊)、內(nèi)存塊的大小、內(nèi)存塊的物理地址、操作花費(fèi)的時(shí)間、完成操作時(shí)的系統(tǒng)時(shí)間。

3.2 實(shí)驗(yàn)結(jié)果

1)時(shí)間開銷。

通過分析trace 文件得到的分配和釋放時(shí)間如圖2 和圖3 所示，圖中的數(shù)據(jù)為500 次操作的平均值，單位為微秒(μs)。在實(shí)驗(yàn)中采用QueryPerformance-Counter 命令進(jìn)行計(jì)時(shí)，如果硬件中存在定時(shí)器，該命令就會啟動此硬件定時(shí)器，并連續(xù)查詢定時(shí)器的數(shù)值，該定時(shí)器的精度與硬件時(shí)鐘的晶振一樣精確，利用這個(gè)方法使得時(shí)間參數(shù)精確到微秒級。

圖2 內(nèi)存分配的平均時(shí)間(μs)

圖3 內(nèi)存釋放的平均時(shí)間(μs)

由圖2 得出伙伴系統(tǒng)分配內(nèi)存的速度最快，TLSF 算法的速度較慢，并隨著區(qū)間的增大需要的時(shí)間也有所增長。改進(jìn)的算法采用分段的機(jī)制，因此在區(qū)間1 和區(qū)間2 的分配速度和伙伴系統(tǒng)相當(dāng)，在區(qū)間3～區(qū)間5 中的分配速度比TLSF 算法快1μs 左右。

由圖3 得出伙伴系統(tǒng)的內(nèi)存釋放速度比TLSF 和改進(jìn)的算法快，在區(qū)間1 和區(qū)間2 改進(jìn)的算法和伙伴系統(tǒng)相當(dāng)，區(qū)間3～區(qū)間5 和TLSF 算法相當(dāng)，沒有太大的差別。

2)內(nèi)存碎片率。

利用trace 文件中記錄的系統(tǒng)運(yùn)行信息，計(jì)算出當(dāng)前時(shí)刻系統(tǒng)的內(nèi)部碎片率。在每次內(nèi)存的分配和釋放操作之后記錄當(dāng)前的內(nèi)存碎片率，按照區(qū)間不同分組計(jì)算系統(tǒng)運(yùn)行過程中的平均碎片率。

圖4 內(nèi)存碎片率(%)

由圖4 可以看出Buddy 算法的碎片率是相當(dāng)高的，所有區(qū)間基本在25%左右浮動，而在最差情況下可能達(dá)到50%。TLSF 算法的內(nèi)存碎片率要明顯低于伙伴系統(tǒng)，保持在3%以下，由于其內(nèi)存塊大小可以浮動，內(nèi)部碎片率主要體現(xiàn)在塊頭的額外開銷，隨著區(qū)間的增大，碎片率逐步減小。改進(jìn)的TLSF 算法在區(qū)間1 和區(qū)間2 擁有和伙伴系統(tǒng)相似的碎片率，由于合并閾值的關(guān)系，在區(qū)間3～區(qū)間5 要高于TLSF算法，但隨著區(qū)間的增大逐步降低直至與TLSF 算法相當(dāng)。

4 結(jié)束語

本文在伙伴算法及TLSF 算法的基礎(chǔ)上設(shè)計(jì)了一種新的內(nèi)存分配算法，分開處理小內(nèi)存塊和大內(nèi)存塊的請求，通過伙伴系統(tǒng)管理小塊內(nèi)存，在TLSF 上利用不同的申請釋放方式管理二級索引，并在μCos-III 系統(tǒng)上實(shí)現(xiàn)了該算法。實(shí)驗(yàn)結(jié)果表明這種動態(tài)內(nèi)存管理算法在時(shí)間和空間上綜合性能比較好。

［1］Masmano M，Ripoll I，Crespo A，et al.Implementation of a constant-time dynamic storage allocator［J］.Software:Practice and Experience，2007，38(10):1000-1025.

［2］Wilson Paul R，Johnstone Mark S，Neely Michael，et al.Dynamic storage allocation:A survey and critical review［C］// International Workshop on Memory Management，Lecture Notes in Computer Science.1995，986:1-116.

［3］吳文峰.嵌入式實(shí)時(shí)系統(tǒng)動態(tài)內(nèi)存分配管理器的設(shè)計(jì)與實(shí)現(xiàn)［D］.重慶:重慶大學(xué)，2013.

［4］姜艷，曾學(xué)文，孫鵬，等.實(shí)時(shí)嵌入式多媒體系統(tǒng)模糊閾值合并內(nèi)存管理算法［J］.西安電子科技大學(xué)報(bào)(自然科學(xué)版)，2012，39(5):220-227.

［5］Gao Chao，Han Rui，Ni Hong.Memory management solution in enbedded Linux systems［J］.Journal of Chinese Computer Systems，2011，32(4):614-618.

［6］田令平.嵌入式操作系統(tǒng)內(nèi)存管理研究［J］.電腦知識與技術(shù)，2006(4):169-171.

［7］王兆文，蔣澤軍，陳進(jìn)朝.一種提高Linux 內(nèi)存管理實(shí)時(shí)性的設(shè)計(jì)方案［J］.計(jì)算機(jī)工程，2014，40(9):291-294.

［8］Mark S Johnstone，Paul R Wilson.The memory fragmentation problem:Solved?［C］// Proceedings of the 1st International Symposium on Memory Management.1998:26-36.

［9］符麗枚，陳世航.嵌入式軟件運(yùn)行內(nèi)存余量測試方法［J］.自動化應(yīng)用，2014(11):6-8.

［10］董文生，沈春鋒.內(nèi)存大小可控的高速內(nèi)存管理算法［J］.控制工程，2013，20(S1):69-71.

［11］Jean J Labrosse.μC/OS-II 嵌入式實(shí)時(shí)操作系統(tǒng)［M］.2版.邵貝貝，宮輝，蔣俊峰，等譯.北京:北京航空航天大學(xué)出版社，2003:69-95.

［12］陸小雙，帥建梅，吳慶響.一種新的面向?qū)ο蟪绦虻膬?nèi)存管理器［J］.計(jì)算機(jī)工程，2012，38(9):21-23.

［13］Berger E D，Zorn B G，McKinley K S.Reconsidering custom memory allocation［J］.Sigplan Notices-SIGPLAN，2002，37(11):1-12.

［14］Lee W H，Chang J M，Hasan Y.Evaluation of a high-performance object reuse dynamic memory allocation policy for C++programs［C］// Proceedings of the 4th IEEE International Conference on High Performance Computing in the Asia-Pacific Region.2000:386-391.

［15］Masmano M，Ripoll I，Crespo A，et al.TLSF:A new dynamic memory allocator for real-time systems［C］// Proceedings of the 16th Euromicro Conference on Real-Time Systems.2004:79-88.

［16］王秀虎，張昕偉.基于μCOS-Ⅱ的TLSF 動態(tài)內(nèi)存分配算法的應(yīng)用與仿真［J］.微型機(jī)與應(yīng)用，2013，32(5):4-7.

［17］屈慶琳，李良光.TLSF 算法在嵌入式系統(tǒng)中的研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)與信息技術(shù)，2011(10):24-26.