摘  要： 以嵌入式實時系統為背景，深入研究了TLSF動態內存分配算法原理及實現過程，并將TLSF移植到μCOS-II中，進行了基于x86平臺的仿真測試，取得了很好的效果，為以后學習和應用TLSF算法提供了一種新的方式。
關鍵詞： TLSF；動態存儲分配；μCOS-II

    嵌入式實時系統中的關鍵問題之一是可調度性分析，以確定系統在運行時是否滿足應用程序的時間約束。嵌入式實時應用程序通常是在系統的整個生命周期過程中不斷執行（幾個月，幾年，…），這種行為是直接影響動態內存管理的關鍵環節之一，即內存碎片問題。考慮這兩個方面，嵌入式實時應用程序中，動態存儲分配DSA（Dynamic Storage Allocation）算法的要求可以概括為：
    （1）時間有界性
    執行內存分配和釋放的最壞執行時間是預先已知的，是獨立于應用程序的數據，這是必須滿足的最主要的要求。
    （2）快速響應時間
    除了具有一個有界的響應時間外，使用的DSA算法的響應時間應該很短。有界的DSA算法，如果響應時間是普通算法的10倍，是不適用的。
    （3）滿足內存需要
    系統運行內存不足時，非實時應用程序能夠接收一個空指針或被操作系統終止。顯然，任何時候都能滿足內存需要是不切實際的。但DSA算法必須把內存碎片和內存浪費降到最少以降低耗盡內存池的可能性。
1 RTOS的DSA算法概述
    DSA算法的目標是讓應用程序訪問空閑內存池中內存塊。不同的算法在尋找最佳尺寸空閑塊時的策略是不同的。DSA算法可以分為以下類別：
    （1）順序擬合算法
    在順序擬合算法中，空閑內存塊由單向或者雙向鏈表管理。查詢空閑內存塊的時間復雜度為O（n）（n為內存塊數目），當內存塊數目較大時，不能保證查詢內存塊的實時性，所以不宜在RTOS中使用該算法。
    （2）索引查找算法
    索引查找算法使用排序二叉樹等非常復雜的數據結構來管理空閑內存，具有復雜的實現過程，并且因采用的數據結構的不同而具有不同的性能。
    （3）分類搜索算法
    分類搜索算法把空閑內存劃分為范圍不同的多個區間，每個區間上的內存塊由另一個數組鏈表管理，該數組鏈表保存著查詢空閑內存塊的頭指針。需要說明的是，同一區間內的空閑內存塊，不一定物理相鄰。
分類搜索算法雖然復雜，但查找空閑內存塊的時間復雜度為O（1），能有效滿足實時性，適合在RTOS使用。
    （4）位圖搜索算法
    位圖搜索算法使用位圖管理空閑內存塊，搜索空閑內存所需信息都被存儲在一小塊內存中，可以實時響應系統需求，是RTOS中普遍采用的算法。
2 TLSF算法的數據結構和算法分析
    在ECRTS 2004（Proceedings 16th Euromicro Conference on RealTime Systems 2004）上，MASMANO M提出了TLSF算法。TLSF算法使用隔離適應機制實現了一個最佳適應策略，它結合了分類搜索算法和位圖搜索算法的優點，即速度快、碎片少。
    隔離適應機制使用了空閑鏈表數組，每個數組內包含了一個區間范圍的空閑內存塊。為了加速訪問空閑塊，并且管理一大組隔離鏈表（以減少碎片），該鏈表數組被分為兩級數組來管理。第一級將空閑內存塊劃分為2n個區間（n=4，5，……，31），稱為FLI（First-level Segregated Fit），第二級別SLI（Second-level Segregated Fit）把第一級線性劃分為2SLI個區間（SLI是一個用戶可配置參數），每個區間都由一條空閑內存塊鏈表管理，每條鏈表對應一個相關的位圖，用來標記鏈表是否為空。1表示鏈表非空，即有空閑內存塊可用，0則相反。
    為了更快地分配與合并內存塊，算法沒有對空閑鏈表進行排序，而是用元素尺寸為32位的二維數組存儲了所有鏈表頭指針。圖1展示了數據結構的兩個層面，第一級是指針數組，分別指向二級鏈表中的空閑內存塊；第二級把第一級線性劃分為8個隔離鏈表。對應的位圖如圖2所示。

2.1 位圖與頭指針
    從圖2可以看出TLSF中的FL_bitmap與SL_bitmap[]的對應關系，SL_bitmap[]中有一類別存在空閑內存，則FL_bitmap對應位為1；否則FL_bitmap對應位為0。SL_bitmap[]中某位為1，則表示存在屬于該類別的可用空閑內存塊。
    SL_bitmap[]中每一位對應一個頭指針，為1時該指針指向對應的空閑塊鏈表；否則指針為空。
2.2 內存塊報頭
    TLSF把管理內存塊需要的信息都嵌入到內存塊內部（該塊是否為空），這些指針組成兩個鏈表：類似大小的鏈表和根據物理地址排序的鏈表。這就是內存塊報頭的數據結構。
TLSF的空閑內存塊與使用中的內存塊報頭并不相同，由于占用的內存塊（使用過的）不在任何隔離鏈表中，它們的頭部比空閑塊的頭部要小，如圖3所示。

    空閑塊的報頭中包含以下所需的數據：
   （1）塊的大小，釋放該塊和與下一物理內存塊鏈接時需要的鏈表。
   （2）邊界標簽，前一個物理內存塊的頭指針。
   （3）把該塊存入相應的隔離列表（雙向鏈表）的兩個指針。
    一個占用的內存塊頭中僅包含大小和邊界標記的指針。
     TLSF中使用兩條鏈表管理內存塊。邏輯鏈表：該鏈表為雙向鏈表，對應TLSF的第二級別的分類，把屬于該類別的所有內存塊，非排序的邏輯上鏈接在一起；物理鏈表：把所有空閑與非空閑內存塊按物理地址相鄰鏈接起來。

2.4 TLSF的時間復雜度
    TLSF的tlsf_malloc（），tlsf_free（）的時間復雜度為O（1），與內存塊數量無關。
    tlsf_malloc（）的偽代碼如下：
    void*tlsf_malloc（）（size）{
     int f1，s1，fl2，sl2；
        void*found_block，*remaining_block；
        mapping_search（size，&fl，&sl）；        //o（1）
        found_block=FIND_SUITABLE_BLOCK（size，fl，sl）；            //o（1）
        clear_bit（sl，sl_bitmap[fl]）；    //o（1）
        clear_bit（fl，fl_bitmap）；        //o（1）
        if（sizeof（found_block）>size）{
            remaining_block=bhdr_t->size-found_block；
            MAPPING_INSERT（sizeof（remaining_block），
&fl2，&sl2）；    //o（1）
            INSERT_BLOCK（remaining_block，fl2，sl2）；                //o（1）
        }
        remove（found_block）；
        return found_block；
}
    雖然TLSF結構中的tlsf_malloc要做一個搜索——FIND_SUITABLE_BLOCK，但由于使用了位圖搜索算法，最壞情況下的時間復雜度依然為O（1）。
tlsf_free的偽代碼如下：
void tlsf_free（block）{
        int fl，sl；
        void*tmp_block，*tlsf；
        tmp_block=merge（block）；//o（1）
        MAPPING_INSERT（block->size & BLOCK_SIZE，
&fl，&sl）；        //o（1）
        INSERT_BLOCK（block，tlsf，fl，sl）；        //o（1）
}
tlsf_free檢查釋放內存塊的上一塊和下一塊物理相連的內存塊是否空閑，并將它們合并。
2.5 TLSF參數化配置
    TLSF結構的特征在于一級索引、二級索引、三級索引三個基本參數。
    （1）一級索引（FLI）
    它是第一級隔離區間的數目，均為2的n次冪。FLI最大可取31。
    FLI=min（log2（memory_pool_size），31）（2）
    （2）二級索引（SLI）
    該索引將一級索引線性劃分。為了在二進制運算中獲得更高的效率，SLI必須是2的n次冪，并且范圍在[1，32]之間。為方便起見，SLI用第二級別的log2來表示，如SLI=2則表示第二級別把第一級別分為4份。
    （3）最小內存塊大小（MBS）
該參數用來限制最小塊的大小。考慮到實現的原因，MBS常數被設置為16 B。
2.6 TLSF的碎片
    TLSF在相應隔離鏈表中不執行窮舉搜索來找一個合適的塊以滿足請求，這樣就產生了碎片。TLSF使用映射函數和位圖直接找到包含大小相同或大于請求的非空最小隔離鏈表。一旦相應的隔離鏈表被發現，鏈表中的第一塊用來服務請求。因此，有可能發生這樣的情況：存在足夠滿足請求的空閑塊，但卻存儲在上一個隔離鏈表中（被映射函數返回前的隔離鏈表）。
    當最大空閑塊具有隔離鏈表（空閑塊的大小小于下一隔離鏈表中的最小容量）的最大容量，并且應用程序請求了一個大于該隔離鏈表中開始大小的內存塊時，發生最壞的碎片情況。TLSF將嘗試開始從持有空閑塊的隔離列表中查找一個合適的塊來服務請求，因此，請求將失敗。
TLSF內存碎片的計算公式為：
    Fragmentation=2FLI/2SLI-2（3）
3 μCOS-II中DSA的不足之處

     μCOS-II中以分區的形式管理內存，分區中包含一定數量的內存塊，并且內存塊大小相同。在μCOS-II中，DSA由OS_MEM.c實現，包含以下幾個函數：OS_MemInit、OSMemCreate、OSMemPut、OSMemGet、OSMemQuery。μCOS-II以代碼精練著稱，DSA函數更不例外，但精練的背后是功能的不足，主要有以下三點：
  （1）編譯時就必須指定內存塊的大小，而且不能變動，靈活性極差，內存浪費也不可避免。
  （2）同一分區中內存塊的大小唯一，然而實際應用中需要使用的內存塊尺寸卻不盡相同。此時則需要建立兩個以上的內存區，加大了維護開銷，也不可避免地造成了內存浪費。
  （3）μCOS-II的DSA是分類搜索算法的一種，但沒有提供搜索合適分類的方法，也未提供向某一分類申請內存失敗后如何向下一分類申請內存的方法。內存的使用算法完全由程序員提供，這無疑加重了程序員負擔，而且由于程序員水平參差不同，系統的可靠性與穩定性也往往大打折扣。
4 TLSF向μCOS-II的移植
    結合TLSF的特點和μCOS-II中DSA的不足，本文把TLSF算法移植到μCOS-II，改善了μCOS-II中的內存管理模塊。
    TLSF具有在同一內存池中分配不同尺寸的內存塊的特點，為方便起見，在移植了TLSF算法的μCOS-II中只使用物理相鄰的一塊內存，并把TLSF定制為可裁剪模塊，配置相關參數后，編譯TLSF模塊。
移植過程即向μCOS-II添加功能函數，同時需要為TLSF提供鎖相關功能。移植后使用μCOS-II提供的Mutex來實現TLSF鎖功能。詳細源碼如下所示：
INT8U perr；
#define TLSF_MLOCK_T OS_EVENT*
#define TLSF_CREATE_LOCK（ResoureceMutex）    
（*（ResoureceMutex））=OSMutexCreate（4，&perr）
#define TLSF_DESTROY_LOCK（ResoureceMutex）    
OSMutexDel（*（ResoureceMutex），OS_DEL_ALWAYS，&perr）
#define TLSF_ACQUIRE_LOCK（ResoureceMutex）    
OSMutexPend（*（ResoureceMutex），0，&perr）
#define TLSF_RELEASE_LOCK（ResoureceMutex）    
OSMutexPost（*（ResoureceMutex））
5 實驗結果
    本次實驗使用BC4.5為開發環境，以x86平臺為仿真環境，測試了μCOS-II中移植的TLSF內存管理模塊。
實驗過程中，創建一個任務，并通過TLSF提供的tlsf_malloc函數請求隨機大小的內存，延時3 s后釋放內存，再延時3 s后繼續請求內存。實驗中使用TLSF自帶的調試函數print_all_blocks來打印TLSF結構體詳細情況，調用該函數，需要開啟TLSF的DEBUG功能：

    TLSF分配和釋放內存的時間復雜度為O（1），在響應時間和內存碎片方面表現優異，并且算法開源，非常適合研究學習。
參考文獻
[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算法在嵌入式系統中的研究與實現[J].計算機與信息技術，2011，10：24-26.
[4] 李江，梅靜靜，王申良，等.TLSF動態內存分配算法的研究與應用[J].單片機與嵌入式系統應用，2011，11：1-4.
[5] 童丹，孫漢旭，賈慶軒.一種基于μCOS-II空間機器人操作系統的研究[D].北京：北京郵電大學，2009.
[6] 梁乘銘，韓堅華，夏成文，等.μCOS-II中動態內存管理方案的改進與實現[J].微計算機信息，2008（5）：44-46.