程小輝，何軍權(quán)，梁啟亮，黃佳歡，顧俊杰

（桂林理工大學 信息科學與工程學院，廣西 桂林541006）

0 引 言

內(nèi)存作為嵌入式系統(tǒng)中十分有限的資源之一，其管理效率的高低制約著系統(tǒng)的整體性能。本文從內(nèi)存分配速率和內(nèi)存碎片率方面出發(fā)，設計一種可預測的、合并算法的動態(tài)內(nèi)存管理機制。此機制一方面利用預測線程預測即將需要的內(nèi)存塊大小進行預分配，減少任務等待內(nèi)存分配的時間開銷［1］；另一方面，采用了合并原理，在內(nèi)存分配時將當前需要的內(nèi)存空間與預測的內(nèi)存空間整體分配，以減少內(nèi)存碎片。

1 嵌入式內(nèi)存分配算法

嵌入式系統(tǒng)中，內(nèi)存分配算法有多種多樣，也有各自的特點，其中比較經(jīng)典的有：首先適應算法、TLSF分配算法和伙伴系統(tǒng)。

首先適應算法，該算法主要是從系統(tǒng)的空閑內(nèi)存鏈表頭部開始查詢，一旦尋找到不小于所需求的內(nèi)存空間長度的內(nèi)存塊，則停止搜索，再按照作業(yè)的實際需求，從該內(nèi)存塊中分配出所需要的內(nèi)存空間給請求者，剩下的空閑空間留在空閑分區(qū)鏈表中。首次適應算法主要使用空閑分區(qū)中的低地址內(nèi)存空間，在系統(tǒng)一開始該算法效率較高，但隨著系統(tǒng)運行時間的增長，空閑鏈表中前部的分區(qū)已被分割成多小塊，難以滿足后來的大塊需求，算法查找開銷也會隨之越來越大。

TLSF （two level segregated fit）算法是一種二級隔離適應算法，使用位圖與鏈表相結(jié)合的方法對內(nèi)存池進行管理［2］。TLSF算法使用隔離適應機制實現(xiàn)一個最佳適應策略，使用位圖實現(xiàn)了快速、定時的映射和搜索功能［3］。隔離適應機制采用了空閑鏈表數(shù)組，每一個空閑數(shù)組都擁有一個特定大小的空閑內(nèi)存塊。為了盡可能的提高獲得空閑塊的速度和方便管理大量的隔離鏈表，這些空鏈表分成兩級。第1級將數(shù)據(jù)空間劃分為2n個部分 （n＝4，5，…），第2級將第1級鏈表進行線型劃分，每一個組都有一個與之相關(guān)的位圖，用于標志鏈表是否為空和哪些數(shù)組有空閑塊，為了保證內(nèi)存空間不越界與連貫性，第2級在劃分第1級鏈表時，往往只能劃分成8個隔離鏈表，分別是0到7。TLSF算法在實時嵌入式系統(tǒng)中有很高的應用，它的優(yōu)勢在于用2個位圖優(yōu)化合適的內(nèi)存查找，實現(xiàn)了查詢時間復雜度為常數(shù)。

伙伴系統(tǒng)主要解決的是內(nèi)存外碎片問題以及提高系統(tǒng)的可靠性［4］，它是把系統(tǒng)中所有的內(nèi)存空間按照2n進行劃分，在linux系統(tǒng)中，伙伴算法將系統(tǒng)的所有空閑頁面分為10個塊鏈表，每個塊鏈表的每個塊元素分別包含1，2，4，…，1024個連續(xù)的頁框，每個塊的第1個頁框的物理地址是該塊大小的整數(shù)倍，如果任務需要內(nèi)存則從塊鏈表中選擇對應的塊元素進行分配。例如，大小為8個頁框的塊，它的起始地址為8＊4K 的倍數(shù)。算法在分配內(nèi)存塊時是尋找合適的i，使得需要分配k大小的內(nèi)存空間滿足，2i－1＜k＜＝2i。伙伴系統(tǒng)中，要想成為伙伴必須滿足3個條件：①塊大小相等；②塊來自同一個大塊分割而成；③2 個塊地址連續(xù)［5］?；锇樗惴ㄔ诮鉀Q外部碎片問題上相當出色，但是由于它的3個條件使得該算法存在一些不足，往往一個很小的塊就會阻礙2個很大的塊的合并，算法也會導致大量的內(nèi)部碎片，使得本身可以申請空閑塊，由于分割過小而無法繼續(xù)分配。

以上幾種算法都是嵌入式系統(tǒng)中常用到的內(nèi)存分配算法，雖然這些算法有很多的有點，但也存在著一定的不足，無法同時在系統(tǒng)空閑時提前預知接下來要的內(nèi)存塊。本文設計了一種帶有提前預測內(nèi)存塊大小的分配算法，該算法一方面使用了文獻 ［1］中的馬爾科夫預測算法的改進版，另一方面采用了類伙伴算法，從時間和碎片率方面提高系統(tǒng)的效率。

2 預測－合并內(nèi)存分配機制

在嵌入式系統(tǒng)中，內(nèi)存資源十分有限，如何高效利用有限的內(nèi)存資源，是保證系統(tǒng)實時性、可靠性、高效性的關(guān)鍵之一。提高內(nèi)存管理效率要從時間和空間2個方面考慮，既要考慮系統(tǒng)的實時性，又要考慮資源利用率。

2.1 內(nèi)存塊預測

嵌入式系統(tǒng)中，對內(nèi)存資源的使用有一定規(guī)律性，申請內(nèi)存塊的大小一般比較集中在某一區(qū)域，這為內(nèi)存預測創(chuàng)造了良好的條件。本文設計了一種馬爾科夫預測內(nèi)存預測分配算法，該算法相對于先前學者的研究，在預測內(nèi)存塊方面做了一定的改進，以達到提高預測的命中率的效果。預測分配原理如圖1示。

圖1 內(nèi)存預測原理

為了實現(xiàn)預測功能，需要在系統(tǒng)中額外增加2 個塊：信息統(tǒng)計表struct stat＿table和預測表struct pred＿list，其中pred＿list結(jié)構(gòu)如下所示：

其中，total是指該fl中對應sl鏈表中內(nèi)存塊數(shù)量，task＿size則是申請fl中對應內(nèi)存塊大小的任務數(shù)量，head＿sl＿list指向二級鏈表的第1個元素。

信息統(tǒng)計表是一個局部二維數(shù)組用P 表示，用于統(tǒng)計每個任務內(nèi)存塊轉(zhuǎn)移信息，假如系統(tǒng)中可分配的內(nèi)存塊大小為8B，16B，32B，64B，128B，256B，512B，1024 B的8 種狀態(tài)，分別用｛s0，s1，s2，s3，s4，s5，s6，s7｝表示，則Pij＝Count（Si→Sj）（i，j＝0，1，…，7），Pij表示為內(nèi)存塊由狀態(tài)Si轉(zhuǎn)移到狀態(tài)Sj的頻數(shù)。在文獻 ［1］中采用了傳統(tǒng)的頻數(shù)作為馬爾科夫預測值

敲減Fascin后的CaSki細胞裸鼠移植瘤在7、12、17、22、27 d腫瘤體積和腫瘤質(zhì)量均明顯降低，而陰性對照慢病毒對CaSki細胞裸鼠移植瘤腫瘤體積和腫瘤質(zhì)量均沒有影響（表3）。敲減Fascin可以明顯抑制CaSki細胞裸鼠移植瘤生長（P＜0.05）。

改進后的預測值是根據(jù)所有狀態(tài)的期望值得到的，預測值為

預測鏈表數(shù)組：是pred＿list類型的數(shù)組，是面向整個系統(tǒng)的、兩級隔離的，第1級 （fl）用于區(qū)分內(nèi)存塊大小，系統(tǒng)中每一個基本分配單元 （大小為size）可以通過索引log2（size）對應一個struct Pred＿list fl＿list［］數(shù)組中的元素。第2級 （sl）是用于存放內(nèi)存塊的單向鏈表，并且同在一個fl中的sl級內(nèi)存塊大小是相同的，為2 的冪次方。假設系統(tǒng)中最大的分配單位為Max，最小為Min，則fl＿list的 索引號為i ＝log2（size／Min），最大索引號：n ＝log2（Max／Min），為了減少查找時間，定義系統(tǒng)級位圖unsigned int PL＿bitmap用于說明系統(tǒng)中fl＿list［i］所對應的鏈表中是否存在 “多余”的內(nèi)存塊，初始值為0，PL＿bitmap計算方式為：PL＿bitmap＝fl＿list［i］.total＞fl＿list［i］.task＿size？PL＿bitmap｜ （1＜＜i）：0。

內(nèi)存預測分配需要大量的原始數(shù)據(jù)，數(shù)據(jù)越多預測結(jié)果越準確。模型首先通過預測算法預測將要分配的內(nèi)存塊大小，如圖1所示。

當內(nèi)存大小預測后，接著開始向系統(tǒng)申請內(nèi)存空間，申請內(nèi)存塊前，首先需要查看PL＿bitmap的狀態(tài)，查看預測鏈表中是否已存在所申請的內(nèi)存塊，如果命中則直接使用，并將對應位置0，如果沒有命中，則向系統(tǒng)內(nèi)存空閑鏈表中申請；其次，完成申請后，對信息統(tǒng)計表的對應位信息進行更新。因此，任務在申請內(nèi)存塊時，總是先查詢PL＿bitmap，根據(jù)PL＿bitmap查看預測鏈表中是否有需要的內(nèi)存塊，如果沒有再從系統(tǒng)內(nèi)存空閑表中申請，并加入到預測鏈表中例如，系統(tǒng)假設只有8個基本塊，在A、B、C、D時刻，預測線程predict（stat＿table）預測到的待分配內(nèi)存塊大小分別為17B，56B，237B，148B，320B。分配內(nèi)存時，首先需要根據(jù)PL＿bitmap｜ （Sj＞＞4）來確認鏈表中是否已存在所分配的內(nèi)存塊，如果存在則不分配，不存在則分配，已使用則對應位置0，預測鏈表狀態(tài)變化如圖2所示。

圖2 預測鏈表狀態(tài)變化

2.2 內(nèi)存塊 “合并”分配

預測算法可以很好地節(jié)約系統(tǒng)分配內(nèi)存消耗的時間，但是卻無法改變內(nèi)存外碎片問題，內(nèi)存空間利用率沒有得到很好地改善。內(nèi)存空間利用率是評價系統(tǒng)效率的一個重要因素，系統(tǒng)在內(nèi)存分配過程中，由于分配算法以及系統(tǒng)固有設計等原因不可能分配恰好與需要的內(nèi)存塊大小一致的空間，而導致分配出去的內(nèi)存塊中有部分未被使用的空閑空間而使得對內(nèi)存空間不能達到100%的利用。本文設計的“預測合并算法”是從內(nèi)存分配塊著手，力圖在內(nèi)存申請時，將當前需要的內(nèi)存塊與預測出的即將需要的內(nèi)存塊作為整體進行申請，這樣可以有效的減少分配塊的內(nèi)部碎片，提高內(nèi)存的有效利用率，同時帶有預測功能可以降低時間消耗。為了便于處理，需要定義一個數(shù)據(jù)結(jié)構(gòu)BLK＿INFO，用于記錄每個合并后的新塊的劃分，結(jié)構(gòu)如下：

2個 “小塊”地址分別為BlkAddr和 （BlkAddr＋First－Size）。內(nèi)存利用率定義為

式中：S——任務實際需求的內(nèi)存空間大小，P——系統(tǒng)malloc（）函數(shù)分配給任務的內(nèi)存塊大小。

當申請內(nèi)存塊大小滿足以上2個條件，算法會將2個待分配請求進行合并，統(tǒng)一向系統(tǒng)申請內(nèi)存塊，并在對應BLK＿INFO 變量中寫入相關(guān)信息。

例如，任務在某一時刻向系統(tǒng)申請大小為U1，U2（U1＜U2）的內(nèi)存塊，并且滿足合并算法的2個條件，則內(nèi)存整個申請過程如圖3所示。其中圖3 （a）表示為傳統(tǒng)的內(nèi)存分配方式，圖3 （b）表示本文采用的合并后再分配的方式。

圖3 合并內(nèi)存分配模型

2.3 預測合并算法機制

合并算法可以在一定程度上提高系統(tǒng)內(nèi)存的利用率，但是沒有考慮時間上的消耗；預測算法考慮了時間消耗指標，但是對內(nèi)存利用率卻沒有考慮。因此，本文綜合預測算法與合并算法各自的優(yōu)點，設計了一種預測合并分配算法。為了降低再次申請同樣大小內(nèi)存的時間消耗，任務結(jié)束后，內(nèi)存塊不會立即釋放，而是存入一個Pred＿List結(jié)構(gòu)體系統(tǒng)變量wait＿release對應位置中，并設定一個閾值，只有超過閾值或系統(tǒng)內(nèi)存不足時方進行內(nèi)存回收。

本算法從時間和空間兩方面考慮。時間上，采用預測算法，根據(jù)每個任務中的信息統(tǒng)計表預測任務即將需要的內(nèi)存塊大小，將預測結(jié)果傳遞給合并函數(shù)，該預測過程將后期內(nèi)存塊的分配工作提前化以減少后期內(nèi)存分配的時間消耗；空間上，當任務申請內(nèi)存塊時，分配算法首先調(diào)用系統(tǒng)中的合并算法，將當前需要的內(nèi)存塊與預測出的即將需要的內(nèi)存塊進行合并并將2個塊的相關(guān)信息寫入BLK＿INFO 變量中，以合并后的內(nèi)存塊為整體向系統(tǒng)申請空閑內(nèi)存塊，這樣可以有效的減少分配塊的內(nèi)部碎片，提高內(nèi)存的有效利用率。任務申請內(nèi)存塊時先從wait＿release表中查找，如果存在則直接分配，不存在則從系統(tǒng)的空閑鏈表中獲取，這種類似 “快表”的方法節(jié)省了任務申請內(nèi)存塊的等待時間，同時，合并模式又降低內(nèi)存的內(nèi)部碎片。原理如圖4所示。

圖4 pred＿merge（）算法原理

對應不滿足預測合并分配算法第2 個條件 （即UM＜Um）的內(nèi)存塊，則無法使用該算法，對于這部分則單獨使用預測算法模型予以解決。

當任務完成內(nèi)存申請時，要判斷預測是否成功，如果成功需要對信息統(tǒng)計表進行更新，調(diào)取更新后的信息統(tǒng)計表，進行第2次內(nèi)存塊預測，將當前需要的內(nèi)存塊與預測內(nèi)存塊合并，重復預測合并分配操作。

3 實 驗

3.1 預測算法對比實驗

評價內(nèi)存預測算法的好壞，主要是通過內(nèi)存塊大小預測的命中率來評價，本文也是從預測的命中率高低來對文獻 ［1］和本文的預測算法進行對比。為此，本文設計了一種通過以隨機數(shù)生成函數(shù)生成的隨機數(shù)，以每64個數(shù)為一組，分別用2種不同的預測算法得到的預測值，進行命中率比較，matlab仿真實驗結(jié)果見表1。

表1 改進前后預測算法命中率

從表1可以看出，隨著循環(huán)次數(shù)的增加，改進前的算法變化不大，基本持平，改進后的算法命中率有很大的提高，但是當循環(huán)次數(shù)增加到一定時，改進后的算法增加幅度不大。

3.2 預測－合并算法實驗

3.2.1 μCOS－Ⅱ內(nèi)存管理機制

μC／OS－Ⅱ是一款開源的、可讀性強，具備實時操作系統(tǒng)全部功能的嵌入式多任務實時操作系統(tǒng)［6］。μC／OS－Ⅱ系統(tǒng)在內(nèi)存管理上改進原有的DSA 的內(nèi)存管理機制，采用內(nèi)存兩級管理策略，把一個大片的連續(xù)系統(tǒng)空間分割成多個分區(qū)，每個分區(qū)又被分割成多個內(nèi)存塊，并且同一分區(qū)中的內(nèi)存塊大小一致。在系統(tǒng)中，內(nèi)存管理通常用到內(nèi)存控制塊OS＿MEM、OS＿MemInit（）、OSMemCreate （）、OSMemGet（）、OSMemPut（）、OSMemQuery （），它們分別完成內(nèi)存塊分區(qū)信息記錄和跟蹤、內(nèi)存初始化、動態(tài)內(nèi)存分區(qū)創(chuàng)建、請求獲得內(nèi)存塊、釋放內(nèi)存塊，以及查詢動態(tài)內(nèi)存分區(qū)狀態(tài)。

為了分析預測合并算法的性能，本文選用μC／OS－Ⅱ系統(tǒng)和預測合并機制μC／OS－Ⅱ系統(tǒng)作為實驗系統(tǒng)，并將它們移植到VC＋＋環(huán)境。考慮到μC／OS－Ⅱ中內(nèi)存管理是使用分區(qū)管理形式，每個內(nèi)存分區(qū)中內(nèi)存塊大小一致且不能再分割，為了便于分割和合并，需增加一個內(nèi)存信息表BLK＿INFO，主要用于記錄每個固定內(nèi)存塊的分割情況，且每個固定大小的內(nèi)存塊最多只有一個BLK＿INFO 表。

相應的OS＿MEM 也需要增加一個信息段void ＊BlkInfo，指向內(nèi)存塊分割信息表，此后，固定大小的內(nèi)存塊可以根據(jù)信息表被再次劃分，減少了內(nèi)存內(nèi)部碎片的大小。修改后的os＿mem 結(jié)構(gòu)如下：

為了減少額外開銷、便于系統(tǒng)的管理，本方案只對μC／OS－Ⅱ系統(tǒng)內(nèi)存分區(qū)中的固定大小內(nèi)存塊做一次分割，分割后的2個內(nèi)存塊不可以被再次分割，如圖5所示。

3.2.2 實驗結(jié)果分析

評價嵌入式系統(tǒng)內(nèi)存分配算法的優(yōu)良除時間外，另一個重要的的指標是碎片率，內(nèi)存碎片率θ定義為

圖5 內(nèi)存申請

式中：C——所有申請的內(nèi)存空間減去釋放了的內(nèi)存空間，即malloc（）的總量減去free（）的總量；S——內(nèi)存實際使用的總量。由此可見，內(nèi)存碎片率不僅和分配的內(nèi)存塊大小有關(guān)，還與釋放大小有聯(lián)系［7］。由式 （4）可知，內(nèi)存的碎片率會隨著釋放總量的增加而遞減。考慮到嵌入式系統(tǒng)運行的種種復雜性，本文采用了專用測試程序CFRAC［7］作為內(nèi)存碎片的測試程序。圖6顯示了改進后的預測合并算法在申請不同大小內(nèi)存塊的內(nèi)存碎片率，從圖可以看出，預測合并算法的內(nèi)存碎片率比原來的要低，但是內(nèi)存碎片率會隨著申請內(nèi)存塊的增加而增加。

圖6 內(nèi)存碎片率

4 結(jié)束語

本文在研究前人研究成果的基礎上，對嵌入式系統(tǒng)內(nèi)存管理進行深入研究，設計了一種預測合并分配機制，該內(nèi)存分配機制包括2部分：一方面通過信息統(tǒng)計表對即將申請的內(nèi)存空間進行預測；另一方面，采用合并成大塊原理，將2次分配內(nèi)存塊合并后統(tǒng)一分配。通過實驗結(jié)果表明，該算法不僅可以對下一次內(nèi)存塊大小進行預測，還能有效地降低碎片率。

［1］CHENG Xiaohui，GONG Youmin，XU Anming.Research of predictable embedded memory distribution mechanism based on Markov ［J］.Computer Engineering and Design，2013，34（8）：2727－2731 （in Chinese）.［程小輝，龔幼民，許安明.基于馬爾可夫鏈的嵌入式內(nèi)存預測分配算法 ［J］.計算機工程與設計，2013，34 （8）：2727－2731.］

［2］LI Jiang，MEI Jingjing，WANG Shenliang.Research and application of TLSF dynamic memory allocation algorithm ［J］.Microcontroller ＆ Embedded Systems，2011，11 （11）：1－4（in Chinese）.［李江，梅靜靜，王申良，等.TLSF 動態(tài)內(nèi)存分配算法的研究與應用 ［J］.單片機與嵌入式系統(tǒng)應用，2011，11 （11）：1－4.］

［3］Masmano M，Ripoll I，Balbastre P，et al.A constant－time dynamic storage allocator for real－time systems［J］.Real－Time Systems，2008，40 （2）：149－179.

［4］GUO Qingbo，GUO Bing，SHEN Yan.Strategy of higher reliability memory management inμC／OS－Ⅱwith buddy algorithm［J］.Microcontroller ＆ Embedded Systems，2011，11 （7）：30－33 （in Chinese）. ［國慶波，郭兵，沈艷.Buddy 算法的μC／OS－Ⅱ高可靠性內(nèi)存管理方案 ［J］.單片機與嵌入式系統(tǒng)應用，2011，11 （7）：30－33.］

［5］HE Jinxian.Research of memory management base on multicore systems ［D］.Chengdu：University of electronic science and technology of China，2009 （in Chinese）. ［何進仙.基于多核系統(tǒng)的內(nèi)存管理研究 ［D］.成都：電子科技大學，2009.］

［6］YANG Lu.Research and improvement of real－time operating systemμC／OS－Ⅱtask scheduling mechanism ［D］.Nanjing：Nanjing University of Posts and Telecomunications，2011 （in Chinese）.［楊露.實時操作系統(tǒng)μC／OS－Ⅱ任務調(diào)度機制的分析與改進 ［D］.南京：南京郵電大學，2011.］

［7］YU Qinfeng，SUN Yong.Analysis and Improvement of memory management method inμC／OS－Ⅱ ［J］.Computer Engineering，2009，35 （11）：280－282 （in Chinese）. ［俞勤豐，孫涌.μC／OS－Ⅱ中內(nèi)存管理方法的分析及改進 ［J］.計算機工程，2009，35 （11）：280－282.］

［8］GAO Chao，HAN Rui，NI Hong.Memory management solution in embedded Linux systems［J］.Journal of Chinese Computer Systems，2011，32 （4）：614－618 （in Chinese）.［高超，韓銳，倪宏.嵌入式Linux平臺內(nèi)存管理方案 ［J］.小型微型計算機系統(tǒng)，2011，32 （4）：614－618.］

［9］JIANG Libo.Analysis and research of memory management in Linux ［D］.Chengdu：University of Electronic Science and Technology of China，2011 （in Chinese）.［姜力波.Linux內(nèi)存管理分析與研究 ［D］.成都：電子科技大學，2011.］

［10］TIAN Linlin，ZHANG Quan，TANG Chaojing.Analysis and comparison of memory management techinques for embedded operating ［J］.Microcontrollers ＆ Embedded Systems，2009，9 （11）：5－7 （in Chinese）.［田林林，張權(quán)，唐朝京.嵌入式操作系統(tǒng)內(nèi)存管理技術(shù)的分析與比較 ［J］.單片基于嵌入式系統(tǒng)應用，2009，9 （11）：5－7.］