UC/OS-II中動態內存管理方案的改進與實現

4、TSLF的數據結構介紹和算法分析【2】

TLSF是M.Masmano在IEEE的Euromic的會議上提出的，用于支持嵌入式實時系統的動態內存管理，它結合了2.3分類搜索算法與2.4位圖搜索算法的優點，速度快、內存浪費少，所用的數據結構如圖1。

圖1 TLSF數據結構

TLSF用兩個層次的分類對不同尺寸的內存塊進行分類。第一層次的類別目錄為2n，n為4，5，……，31的整數，稱為FLI（First-level Segregated Fit）。每一個FLI類別又根據第二層的SLI細分為2SLI個子類別。第二層的每個類別，都對應一條屬于該類別尺寸范圍內的內存塊鏈表。為了加快分配與合并內存塊的速度，鏈表是不排序的。所有的鏈表頭指針用數組元素尺寸為32位的二維數組存儲起來。各個類別所表示的內存塊尺寸范圍可參見圖1。第一層次、第二層次都使用位圖指示該類別有無空閑內存塊，有則該類別對應的位為1，否則為0。

4．1 TLSF位圖與TLSF頭指針

TLSF中每一個第一或第二層次的類別對應位圖中的1位，位為1表示該類別有空閑內存塊，為0則表示沒有。可根據第一、第二類別的總數確定總的位圖存儲空間大小。位圖存儲在內存池的開始位置。

TLSF第二層次的每一類別皆對應一個頭指針。若該類別的空閑內存塊鏈表非空，則類別頭指針指向該鏈表，否則頭指針為空。

4．2 TLSF塊頭

TLSF的空閑內存塊與使用中的內存塊塊頭并不相同，如圖2所示。

圖2 內存塊塊頭數據結構

TLSF中所用的內存塊由兩條鏈表組織。邏輯鏈表：每個第二層次的類別可有0條或1條，它是一個雙向鏈表，把屬于該類別的所有內存塊不排序地邏輯上鏈接在一起；物理鏈表：把所有空閑與非空閑內存塊按物理地址相鄰鏈接起來。www.51kaifa.com

4．3 TLSF算法分析

參考文獻【2】的推導，TLSF的malloc，free的時間復雜度并不隨空閑內存塊的數量而變化，都是O(1)。

4．4 TLSF的碎片

由于TLSF的分類內的自由空閑內存鏈表是不排序的，分配時也不搜索，所以申請尺寸屬于某一類別的內存塊時，卻要從下一個類別分配內存【2】。TLSF內存碎片的計算公式為：

4．5 TLSF參數的控制

TLSF有3個可以配置的參數常量。

FLI：是第一層次類別的數目，類別都是2的n次方。FLI最大可去到31，

SLI：是第二層次類別的數目。出于性能考慮，SLI必須是2的n次方，并且范圍在[1, 32]之間，以便用單字處理指令。一般，SLI用第二層次類別數目的 來表示，如SLI＝2則表示第二層次類別把對應的第一層次類別分為4份。

MBS(Minimum block size)：最小塊的尺寸，一般為16Bytes。www.51kaifa.com

5、TLSF向UC/OS-II的移植定制

為了克服UC/OS-II原有DSA的不足，本文引進了TLSF動態內存管理算法，并做了適當的修改以便適合于UC/OS-II。

由于TLSF可以在同一內存池分配不同尺寸的內存塊，為了充分發揮TLSF這一優點、減少管理開銷，在其移植后只使用物理地址連續的一塊內存。在 TLSF的移植過程中，仿照了UC/OS-II系統的風格，把其定制成可裁減的模塊，只有配置了相關常數后，才編譯該模塊。提供的編程接口函數與配置常數如表1。

表1 UC/OS-II的TLSF編程接口函數與配置常數