嵌入式實時系統(tǒng)中動態(tài)內存管理算法的設計與實現(xiàn)

沈非一，張延園，林 奕

(西北工業(yè)大學計算機學院，陜西 西安 710129)

0 引言

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

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

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

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

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

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

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

1 算法方案與設計

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

1.1 總體方案

針對不同大小的內存申請，其碎片率與實時性能的特點均有所差別，本文對小塊內存以及大塊內存的申請進行分段處理［12］。

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

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

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

圖1 系統(tǒng)總體結構

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

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

1)2 個塊大小相同;

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

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

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

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

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

在空閑鏈表上以2 的冪次構建一級位圖索引，在判斷完內存塊大小后可以在O(1)時間內找到對應的空閑塊。

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

小塊內存維護m +1 個分段空閑鏈表控制塊結構如下:

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

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

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

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

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

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

大內存區(qū)控制塊結構如下:

一級索引分區(qū)的控制塊結構如下:

在二級索引中為每個內存塊附加塊頭和塊尾結構來進行雙向鏈接。

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

釋放內存塊時，判斷能否與前后的內存塊進行合并(通過邊界標記進行判斷)，如果進行過合并操作，則將該內存塊插入對應的分段空閑鏈表尾部，否則將該內存塊插入到空閑鏈表頭部。因為尾部的內存塊有更大的可能性被分割，可以保證其余內存塊在物理上的連續(xù)性。

2 函數(shù)接口

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

1)內存池初始化。

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

2)創(chuàng)建內存結構。

該接口的任務是構建起整個內存的結構，將空閑內存劃分并掛載到相應的空閑鏈表下。

3)申請內存塊。

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

4)釋放內存塊。

3 實 驗

3.1 實驗設計

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

實驗利用隨機數(shù)產生一定大小范圍內的內存申請和釋放請求，把內存的大小范圍分為以下5 個區(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)中設計5 個任務，分別產生這5 個區(qū)間范圍內大小的隨機值，并按照這個大小申請內存，隨后間隔一個隨機的時間進行內存釋放。每個任務一共進行500 組分配和釋放操作，任務之間的分配和釋放是同優(yōu)先級的，根據(jù)隨機的時間間隔交替進行，最后的結果取平均值。

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

3.2 實驗結果

1)時間開銷。

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

圖2 內存分配的平均時間(μs)

圖3 內存釋放的平均時間(μs)

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

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

2)內存碎片率。

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

圖4 內存碎片率(%)

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

4 結束語

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

［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］吳文峰.嵌入式實時系統(tǒng)動態(tài)內存分配管理器的設計與實現(xiàn)［D］.重慶:重慶大學，2013.

［4］姜艷，曾學文，孫鵬，等.實時嵌入式多媒體系統(tǒng)模糊閾值合并內存管理算法［J］.西安電子科技大學報(自然科學版)，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)內存管理研究［J］.電腦知識與技術，2006(4):169-171.

［7］王兆文，蔣澤軍，陳進朝.一種提高Linux 內存管理實時性的設計方案［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］符麗枚，陳世航.嵌入式軟件運行內存余量測試方法［J］.自動化應用，2014(11):6-8.

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

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

［12］陸小雙，帥建梅，吳慶響.一種新的面向對象程序的內存管理器［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)內存分配算法的應用與仿真［J］.微型機與應用，2013，32(5):4-7.

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