王秀虎，張昕偉

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

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

（1）時(shí)間有界性

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

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

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

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

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

1 RTOS的DSA算法概述

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

（1）順序擬合算法

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

（2）索引查找算法

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

（3）分類(lèi)搜索算法

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

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

（4）位圖搜索算法

位圖搜索算法使用位圖管理空閑內(nèi)存塊，搜索空閑內(nèi)存所需信息都被存儲(chǔ)在一小塊內(nèi)存中，可以實(shí)時(shí)響應(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)機(jī)制實(shí)現(xiàn)了一個(gè)最佳適應(yīng)策略，它結(jié)合了分類(lèi)搜索算法和位圖搜索算法的優(yōu)點(diǎn)，即速度快、碎片少。

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

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

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

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

2.1 位圖與頭指針

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

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

2.2 內(nèi)存塊報(bào)頭

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

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

圖3 空閑塊和占用塊的報(bào)頭

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

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

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

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

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

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

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

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

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

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

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

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

圖 4 malloc_ex（）流程

2.4 TLSF的時(shí)間復(fù)雜度

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

tlsf_malloc（）的偽代碼如下：

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

tlsf_free的偽代碼如下：

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

2.5 TLSF參數(shù)化配置

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

（1）一級(jí)索引（FLI）

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

（2）二級(jí)索引（SLI）

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

（3）最小內(nèi)存塊大?。∕BS）

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

2.6 TLSF的碎片

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

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

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

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

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

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

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

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

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

4 TLSF向 μCOS-II的移植

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

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

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

5 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

[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)中的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)與信息技術(shù)，2011，10：24-26.

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

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

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