王秀虎，張昕偉

（華北計算機系統(tǒng)工程研究所，北京 100083）

嵌入式實時系統(tǒng)中的關(guān)鍵問題之一是可調(diào)度性分析，以確定系統(tǒng)在運行時是否滿足應(yīng)用程序的時間約束。嵌入式實時應(yīng)用程序通常是在系統(tǒng)的整個生命周期過程中不斷執(zhí)行（幾個月，幾年，…），這種行為是直接影響動態(tài)內(nèi)存管理的關(guān)鍵環(huán)節(jié)之一，即內(nèi)存碎片問題?？紤]這兩個方面，嵌入式實時應(yīng)用程序中，動態(tài)存儲分配 DSA（Dynamic Storage Allocation）算法的要求可以概括為：

（1）時間有界性

執(zhí)行內(nèi)存分配和釋放的最壞執(zhí)行時間是預先已知的，是獨立于應(yīng)用程序的數(shù)據(jù)，這是必須滿足的最主要的要求。

（2）快速響應(yīng)時間

除了具有一個有界的響應(yīng)時間外，使用的DSA算法的響應(yīng)時間應(yīng)該很短。有界的DSA算法，如果響應(yīng)時間是普通算法的10倍，是不適用的。

（3）滿足內(nèi)存需要

系統(tǒng)運行內(nèi)存不足時，非實時應(yīng)用程序能夠接收一個空指針或被操作系統(tǒng)終止。顯然，任何時候都能滿足內(nèi)存需要是不切實際的。但DSA算法必須把內(nèi)存碎片和內(nèi)存浪費降到最少以降低耗盡內(nèi)存池的可能性。

1 RTOS的DSA算法概述

DSA算法的目標是讓應(yīng)用程序訪問空閑內(nèi)存池中內(nèi)存塊。不同的算法在尋找最佳尺寸空閑塊時的策略是不同的。DSA算法可以分為以下類別：

（1）順序擬合算法

在順序擬合算法中，空閑內(nèi)存塊由單向或者雙向鏈表管理。查詢空閑內(nèi)存塊的時間復雜度為O（n）（n為內(nèi)存塊數(shù)目），當內(nèi)存塊數(shù)目較大時，不能保證查詢內(nèi)存塊的實時性，所以不宜在RTOS中使用該算法。

（2）索引查找算法

索引查找算法使用排序二叉樹等非常復雜的數(shù)據(jù)結(jié)構(gòu)來管理空閑內(nèi)存，具有復雜的實現(xiàn)過程，并且因采用的數(shù)據(jù)結(jié)構(gòu)的不同而具有不同的性能。

（3）分類搜索算法

分類搜索算法把空閑內(nèi)存劃分為范圍不同的多個區(qū)間，每個區(qū)間上的內(nèi)存塊由另一個數(shù)組鏈表管理，該數(shù)組鏈表保存著查詢空閑內(nèi)存塊的頭指針。需要說明的是，同一區(qū)間內(nèi)的空閑內(nèi)存塊，不一定物理相鄰。

分類搜索算法雖然復雜，但查找空閑內(nèi)存塊的時間復雜度為O（1），能有效滿足實時性，適合在 RTOS使用。

（4）位圖搜索算法

位圖搜索算法使用位圖管理空閑內(nèi)存塊，搜索空閑內(nèi)存所需信息都被存儲在一小塊內(nèi)存中，可以實時響應(yīng)系統(tǒng)需求，是RTOS中普遍采用的算法。

2 TLSF算法的數(shù)據(jù)結(jié)構(gòu)和算法分析

在 ECRTS 2004（Proceedings 16th Euromicro Conference onRealTimeSystems2004）上，MASMANO M提出了TLSF算法。TLSF算法使用隔離適應(yīng)機制實現(xiàn)了一個最佳適應(yīng)策略，它結(jié)合了分類搜索算法和位圖搜索算法的優(yōu)點，即速度快、碎片少。

隔離適應(yīng)機制使用了空閑鏈表數(shù)組，每個數(shù)組內(nèi)包含了一個區(qū)間范圍的空閑內(nèi)存塊。為了加速訪問空閑塊，并且管理一大組隔離鏈表（以減少碎片），該鏈表數(shù)組被分為兩級數(shù)組來管理。第一級將空閑內(nèi)存塊劃分為2n 個 區(qū) 間 （n=4，5， …… ，31）， 稱 為 FLI （First-level Segregated Fit）， 第二級別 SLI （Second-level Segregated Fit）把第一級線性劃分為 2SLI個區(qū)間（SLI是一個用戶可配置參數(shù)），每個區(qū)間都由一條空閑內(nèi)存塊鏈表管理，每條鏈表對應(yīng)一個相關(guān)的位圖，用來標記鏈表是否為空。1表示鏈表非空，即有空閑內(nèi)存塊可用，0則相反。

為了更快地分配與合并內(nèi)存塊，算法沒有對空閑鏈表進行排序，而是用元素尺寸為32位的二維數(shù)組存儲了所有鏈表頭指針。圖1展示了數(shù)據(jù)結(jié)構(gòu)的兩個層面，第一級是指針數(shù)組，分別指向二級鏈表中的空閑內(nèi)存塊；第二級把第一級線性劃分為8個隔離鏈表。對應(yīng)的位圖如圖2所示。

圖1 TLSF的數(shù)據(jù)結(jié)構(gòu)圖例

圖2 TLSF的數(shù)據(jù)結(jié)構(gòu)對應(yīng)位圖

2.1 位圖與頭指針

從圖2可以看出TLSF中的FL_bitmap與SL_bitmap[]的對應(yīng)關(guān)系，SL_bitmap[]中有一類別存在空閑內(nèi)存，則FL_bitmap對應(yīng)位為1；否則FL_bitmap對應(yīng)位為0。SL_bitmap[]中某位為1，則表示存在屬于該類別的可用空閑內(nèi)存塊。

SL_bitmap[]中每一位對應(yīng)一個頭指針，為 1時該指針指向?qū)?yīng)的空閑塊鏈表；否則指針為空。

2.2 內(nèi)存塊報頭

TLSF把管理內(nèi)存塊需要的信息都嵌入到內(nèi)存塊內(nèi)部（該塊是否為空），這些指針組成兩個鏈表：類似大小的鏈表和根據(jù)物理地址排序的鏈表。這就是內(nèi)存塊報頭的數(shù)據(jù)結(jié)構(gòu)。

TLSF的空閑內(nèi)存塊與使用中的內(nèi)存塊報頭并不相同，由于占用的內(nèi)存塊（使用過的）不在任何隔離鏈表中，它們的頭部比空閑塊的頭部要小，如圖3所示。

圖3 空閑塊和占用塊的報頭

空閑塊的報頭中包含以下所需的數(shù)據(jù)：

（1）塊的大小，釋放該塊和與下一物理內(nèi)存塊鏈接時需要的鏈表。

（2）邊界標簽，前一個物理內(nèi)存塊的頭指針。

（3）把該塊存入相應(yīng)的隔離列表（雙向鏈表）的兩個指針。

一個占用的內(nèi)存塊頭中僅包含大小和邊界標記的指針。

TLSF中使用兩條鏈表管理內(nèi)存塊。邏輯鏈表：該鏈表為雙向鏈表，對應(yīng)TLSF的第二級別的分類，把屬于該類別的所有內(nèi)存塊，非排序的邏輯上鏈接在一起；物理鏈表：把所有空閑與非空閑內(nèi)存塊按物理地址相鄰鏈接起來。

2.3 結(jié)構(gòu)函數(shù)

2.3.1 映射函數(shù)MAPPING_SEARCH（）

大多數(shù) TLSF的操作依賴于MAPPING_SEARCH（）映射函數(shù)。給內(nèi)存大小賦值后，映射函數(shù)計算出指向滿足需求的內(nèi)存塊的相應(yīng)的隔離鏈表的兩個鏈表索引。

此功能可以有效地實現(xiàn)位搜索指令（在最先進的處理器可用），并利用一些數(shù)值屬性。一級索引（[log2（size）]）的位置可以作為滿足需求的最顯著位計算；二級索引可以通過SLI位的大?。ㄏ蛴遥┇@得。例如，假定一個二級指標 SLI=4，大小為 540，一級索引為 f=10和二級索引為s=0。

2.3.2 內(nèi)存分配函數(shù)TLSF_MALLOC（）

TLSF_MALLOC（）函數(shù)復雜分配內(nèi)存，所需內(nèi)存的尺寸為參數(shù)，執(zhí)行成功后返回的是內(nèi)存塊首地址。TLSF_MALLOC （）主要是通過內(nèi)部內(nèi)存分配函數(shù)malloc_ex（）來實現(xiàn)的，malloc_ex（）的操作流程如圖 4所示。

圖 4 malloc_ex（）流程

2.4 TLSF的時間復雜度

TLSF 的 tlsf_malloc（），tlsf_free（）的時間復雜度為 O（1），與內(nèi)存塊數(shù)量無關(guān)。

tlsf_malloc（）的偽代碼如下：

雖然TLSF結(jié)構(gòu)中的tlsf_malloc要做一個搜索——FIND_SUITABLE_BLOCK，但由于使用了位圖搜索算法，最壞情況下的時間復雜度依然為O（1）。

tlsf_free的偽代碼如下：

tlsf_free檢查釋放內(nèi)存塊的上一塊和下一塊物理相連的內(nèi)存塊是否空閑，并將它們合并。

2.5 TLSF參數(shù)化配置

TLSF結(jié)構(gòu)的特征在于一級索引、二級索引、三級索引三個基本參數(shù)。

（1）一級索引（FLI）

它是第一級隔離區(qū)間的數(shù)目，均為2的n次冪。FLI最大可取31。

（2）二級索引（SLI）

該索引將一級索引線性劃分。為了在二進制運算中獲得更高的效率，SLI必須是2的n次冪，并且范圍在[1，32]之間。為方便起見，SLI用第二級別的log2來表示，如SLI=2則表示第二級別把第一級別分為4份。

（3）最小內(nèi)存塊大小（MBS）

該參數(shù)用來限制最小塊的大小?？紤]到實現(xiàn)的原因，MBS常數(shù)被設(shè)置為16 B。

2.6 TLSF的碎片

TLSF在相應(yīng)隔離鏈表中不執(zhí)行窮舉搜索來找一個合適的塊以滿足請求，這樣就產(chǎn)生了碎片。TLSF使用映射函數(shù)和位圖直接找到包含大小相同或大于請求的非空最小隔離鏈表。一旦相應(yīng)的隔離鏈表被發(fā)現(xiàn)，鏈表中的第一塊用來服務(wù)請求。因此，有可能發(fā)生這樣的情況：存在足夠滿足請求的空閑塊，但卻存儲在上一個隔離鏈表中（被映射函數(shù)返回前的隔離鏈表）。

當最大空閑塊具有隔離鏈表（空閑塊的大小小于下一隔離鏈表中的最小容量）的最大容量，并且應(yīng)用程序請求了一個大于該隔離鏈表中開始大小的內(nèi)存塊時，發(fā)生最壞的碎片情況。TLSF將嘗試開始從持有空閑塊的隔離列表中查找一個合適的塊來服務(wù)請求，因此，請求將失敗。

TLSF內(nèi)存碎片的計算公式為：

3 μCOS-II中 DSA 的不足之處

μCOS-II中以分區(qū)的形式管理內(nèi)存，分區(qū)中包含一定數(shù)量的內(nèi)存塊，并且內(nèi)存塊大小相同。在μCOS-II中，DSA由OS_MEM.c實現(xiàn)，包含以下幾個函數(shù)：OS_MemInit、OSMemCreate、OSMemPut、OSMemGet、

OSMemQuery。μCOS-II以代碼精練著稱，DSA函數(shù)更不例外，但精練的背后是功能的不足，主要有以下三點：

（1）編譯時就必須指定內(nèi)存塊的大小，而且不能變動，靈活性極差，內(nèi)存浪費也不可避免。

（2）同一分區(qū)中內(nèi)存塊的大小唯一，然而實際應(yīng)用中需要使用的內(nèi)存塊尺寸卻不盡相同。此時則需要建立兩個以上的內(nèi)存區(qū)，加大了維護開銷，也不可避免地造成了內(nèi)存浪費。

（3）μCOS-II的DSA是分類搜索算法的一種，但沒有提供搜索合適分類的方法，也未提供向某一分類申請內(nèi)存失敗后如何向下一分類申請內(nèi)存的方法。內(nèi)存的使用算法完全由程序員提供，這無疑加重了程序員負擔，而且由于程序員水平參差不同，系統(tǒng)的可靠性與穩(wěn)定性也往往大打折扣。

4 TLSF向 μCOS-II的移植

結(jié)合TLSF的特點和μCOS-II中DSA的不足，本文把TLSF算法移植到 μCOS-II，改善了 μCOS-II中的內(nèi)存管理模塊。

TLSF具有在同一內(nèi)存池中分配不同尺寸的內(nèi)存塊的特點，為方便起見，在移植了TLSF算法的μCOS-II中只使用物理相鄰的一塊內(nèi)存，并把TLSF定制為可裁剪模塊，配置相關(guān)參數(shù)后，編譯TLSF模塊。

移植過程即向μCOS-II添加功能函數(shù)，同時需要為TLSF提供鎖相關(guān)功能。移植后使用μCOS-II提供的Mutex來實現(xiàn)TLSF鎖功能。詳細源碼如下所示：

5 實驗結(jié)果

本次實驗使用BC4.5為開發(fā)環(huán)境，以x86平臺為仿真環(huán)境，測試了μCOS-II中移植的TLSF內(nèi)存管理模塊。

實驗過程中，創(chuàng)建一個任務(wù)，并通過TLSF提供的tlsf_malloc函數(shù)請求隨機大小的內(nèi)存，延時3 s后釋放內(nèi)存，再延時3 s后繼續(xù)請求內(nèi)存。實驗中使用TLSF自帶的調(diào)試函數(shù)print_all_blocks來打印TLSF結(jié)構(gòu)體詳細情況，調(diào)用該函數(shù)，需要開啟TLSF的DEBUG功能：

系統(tǒng)運行如圖5所示。

圖5 系統(tǒng)仿真結(jié)果

TLSF分配和釋放內(nèi)存的時間復雜度為 O（1），在響應(yīng)時間和內(nèi)存碎片方面表現(xiàn)優(yōu)異，并且算法開源，非常適合研究學習。

[1]MASMANO M， RIPOLL I， CRESPO A， et al.TLSF： a new dynamic memory allocator for real-time systems[C].In：16th Euro micro Conference on Real-Time Systems，Catania，Italy， IEEE，2004：79-88.

[2]MASMANO M， RIPOLL I， CRESPO A.Description of the TLSF memory allocator version 2.0[EB/OL].[2005-11-11]（2012-10-23）http：//wks.gii.upv.es/tlsf/.

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

[4]李江，梅靜靜，王申良，等.TLSF動態(tài)內(nèi)存分配算法的研究與應(yīng)用[J].單片機與嵌入式系統(tǒng)應(yīng)用，2011，11：1-4.

[5]童丹，孫漢旭，賈慶軒.一種基于 μCOS-II空間機器人操作系統(tǒng)的研究[D].北京：北京郵電大學，2009.

[6]梁乘銘，韓堅華，夏成文，等.μCOS-II中動態(tài)內(nèi)存管理方案的改進與實現(xiàn)[J].微計算機信息，2008（5）：44-46.