4、TSLF的數(shù)據(jù)結(jié)構(gòu)介紹和算法分析【2】

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

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

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

4．1 TLSF位圖與TLSF頭指針

TLSF中每一個(gè)第一或第二層次的類別對(duì)應(yīng)位圖中的1位，位為1表示該類別有空閑內(nèi)存塊，為0則表示沒有?？筛鶕?jù)第一、第二類別的總數(shù)確定總的位圖存儲(chǔ)空間大小。位圖存儲(chǔ)在內(nèi)存池的開始位置。

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

4．2 TLSF塊頭

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

圖2 內(nèi)存塊塊頭數(shù)據(jù)結(jié)構(gòu)

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

4．3 TLSF算法分析

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

4．4 TLSF的碎片

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

4．5 TLSF參數(shù)的控制

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

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

SLI：是第二層次類別的數(shù)目。出于性能考慮，SLI必須是2的n次方，并且范圍在[1, 32]之間，以便用單字處理指令。一般，SLI用第二層次類別數(shù)目的 來(lái)表示，如SLI＝2則表示第二層次類別把對(duì)應(yīng)的第一層次類別分為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)內(nèi)存管理算法，并做了適當(dāng)?shù)男薷囊员氵m合于UC/OS-II。

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

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