基于預(yù)測(cè)原理的嵌入式內(nèi)存分配算法設(shè)計(jì)

程小輝，何軍權(quán)，梁?jiǎn)⒘?，黃佳歡，顧俊杰

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

0 引 言

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

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

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

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

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

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

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

2 預(yù)測(cè)－合并內(nèi)存分配機(jī)制

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

2.1 內(nèi)存塊預(yù)測(cè)

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

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

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

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

信息統(tǒng)計(jì)表是一個(gè)局部二維數(shù)組用P 表示，用于統(tǒng)計(jì)每個(gè)任務(wù)內(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ù)。在文獻(xiàn) ［1］中采用了傳統(tǒng)的頻數(shù)作為馬爾科夫預(yù)測(cè)值

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

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

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

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

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

圖2 預(yù)測(cè)鏈表狀態(tài)變化

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

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

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

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

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

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

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

2.3 預(yù)測(cè)合并算法機(jī)制

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

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

圖4 pred＿merge（）算法原理

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

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

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

3.1 預(yù)測(cè)算法對(duì)比實(shí)驗(yàn)

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

表1 改進(jìn)前后預(yù)測(cè)算法命中率

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

3.2 預(yù)測(cè)－合并算法實(shí)驗(yàn)

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

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

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

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

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

3.2.2 實(shí)驗(yàn)結(jié)果分析

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

圖5 內(nèi)存申請(qǐng)

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

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

4 結(jié)束語(yǔ)

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

［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)存預(yù)測(cè)分配算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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 動(dòng)態(tài)內(nèi)存分配算法的研究與應(yīng)用 ［J］.單片機(jī)與嵌入式系統(tǒng)應(yī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）. ［國(guó)慶波，郭兵，沈艷.Buddy 算法的μC／OS－Ⅱ高可靠性內(nèi)存管理方案 ［J］.單片機(jī)與嵌入式系統(tǒng)應(yī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）. ［何進(jìn)仙.基于多核系統(tǒng)的內(nèi)存管理研究 ［D］.成都：電子科技大學(xué)，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）.［楊露.實(shí)時(shí)操作系統(tǒng)μC／OS－Ⅱ任務(wù)調(diào)度機(jī)制的分析與改進(jìn) ［D］.南京：南京郵電大學(xué)，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ìn) ［J］.計(jì)算機(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平臺(tái)內(nèi)存管理方案 ［J］.小型微型計(jì)算機(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］.成都：電子科技大學(xué)，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)應(yīng)用，2009，9 （11）：5－7.］