UC/OS-II中動(dòng)態(tài)內存管理方案的改進(jìn)與實(shí)現

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

TLSF是M.Masmano在IEEE的Euromic的會(huì )議上提出的，用于支持嵌入式實(shí)時(shí)系統的動(dòng)態(tài)內存管理，它結合了2.3分類(lèi)搜索算法與2.4位圖搜索算法的優(yōu)點(diǎn)，速度快、內存浪費少，所用的數據結構如圖1。

圖1 TLSF數據結構

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

4．1 TLSF位圖與TLSF頭指針

TLSF中每一個(gè)第一或第二層次的類(lèi)別對應位圖中的1位，位為1表示該類(lèi)別有空閑內存塊，為0則表示沒(méi)有?？筛鶕谝?、第二類(lèi)別的總數確定總的位圖存儲空間大小。位圖存儲在內存池的開(kāi)始位置。

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

4．2 TLSF塊頭

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

圖2 內存塊塊頭數據結構

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

4．3 TLSF算法分析

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

4．4 TLSF的碎片

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

4．5 TLSF參數的控制

TLSF有3個(gè)可以配置的參數常量。

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

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

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

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

為了克服UC/OS-II原有DSA的不足，本文引進(jìn)了TLSF動(dòng)態(tài)內存管理算法，并做了適當的修改以便適合于UC/OS-II。

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

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