TLSF動(dòng)態(tài)內(nèi)存分配算法的研究與應(yīng)用

李江,梅靜靜,王申良,束頎

(安徽理工大學(xué)研究生處,淮南232001)

引 言

由于動(dòng)態(tài)內(nèi)存分配存在著執(zhí)行時(shí)間不確定與內(nèi)存碎片過多等問題,嵌入式實(shí)時(shí)系統(tǒng)中很少使用。TLSF動(dòng)態(tài)內(nèi)存算法中內(nèi)存分配與釋放均為常數(shù),并且具有內(nèi)存自動(dòng)合并、靈活性強(qiáng)、內(nèi)存碎片少等特點(diǎn)[1]。實(shí)時(shí)操作系統(tǒng)μ C/OS-II中內(nèi)存分配使用的是一種靜態(tài)內(nèi)存分區(qū)方式,內(nèi)存分配與釋放的時(shí)間是確定的,缺乏靈活性,而且內(nèi)存的分配與釋放都需要指定正確的內(nèi)存分區(qū)[2],使用比較麻煩,容易出錯(cuò)。

本文把TLSF移植到μ C/OSII中,以提高內(nèi)存分配的靈活性與執(zhí)行的實(shí)時(shí)性,并通過軟件仿真測(cè)試TLSF在μ C/OS-II操作系統(tǒng)中的運(yùn)行效果。

1 對(duì)TLSF的簡介

TLSF是一種二級(jí)隔離適應(yīng)算法,使用位圖與鏈表相結(jié)合的方式對(duì)內(nèi)存池進(jìn)行管理。TLSF實(shí)現(xiàn)過程如下:定義一級(jí)索引最大值MAX_FLI(小于32)與二級(jí)索引最大值MAX_SLI,MAX_SLI等于2的 MAX_LOG2_SLI次方(MAX_LOG2_SLI為程序中計(jì)算方便定義的);申請(qǐng)一塊大的內(nèi)存池,通過定義全局變量作為內(nèi)存池,或者使用操作系統(tǒng)申請(qǐng)一塊比較大的內(nèi)存區(qū)(池)使用;使用tlsf_malloc函數(shù)申請(qǐng)內(nèi)存,使用tlsf_free函數(shù)釋放內(nèi)存,還包括realloc與calloc函數(shù)等函數(shù)[3]。

TLSF的數(shù)據(jù)結(jié)構(gòu)如圖1所示。

使用如同μ C/OS-II中管理任務(wù)就緒表的形式定義變量FL_bitmap與SL_bitmaps[],空閑鏈表中有空閑塊相應(yīng)位置1。使用一級(jí)索引fl與二級(jí)索引sl確定對(duì)應(yīng)空閑鏈表中空閑塊的大小值的范圍。fl確定了此一索引管理的內(nèi)存范圍是[2^fl,2^(fl+1))。二級(jí)索引值sl表示一級(jí)索引被平分為sl塊[4]。

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

2 TLSF中用到的變量與結(jié)構(gòu)體

2.1 tlsf_t結(jié)構(gòu)體

每個(gè)內(nèi)存區(qū)(池)都使用結(jié)構(gòu)體tlsf_t管理,此結(jié)構(gòu)存儲(chǔ)在內(nèi)存區(qū)的首部,其結(jié)構(gòu)如下:

此結(jié)構(gòu)體也記錄內(nèi)存區(qū)的基本信息,在 tlsf.c中定義全局變量“static char*mp=NULL;”管理所有的內(nèi)存區(qū)。在結(jié)構(gòu)體tlsf_t中還用到兩個(gè)結(jié)構(gòu)體:area_info_t與bhdr_t。

2.2 結(jié)構(gòu)體area_info_t

結(jié)構(gòu)體area_info_t用來鏈接各個(gè)不相鄰的內(nèi)存區(qū),其結(jié)構(gòu)如下:

2.3 結(jié)構(gòu)體bhdr_t

結(jié)構(gòu)體bhdr_t存儲(chǔ)各個(gè)空閑鏈表的表頭,如果此鏈表中無空閑內(nèi)存塊,則為null。結(jié)構(gòu)體如下所示:

而結(jié)構(gòu)體struct free_ptr_struct用來鏈接一鏈表中的各個(gè)空閑內(nèi)存塊,結(jié)構(gòu)如下:

3 TLSF中用到的函數(shù)

TLSF算法主要包括:內(nèi)存區(qū)的初始化函數(shù)init_memory_pool、內(nèi)存區(qū)銷毀函數(shù) destroy_memory_pool、增加內(nèi)存區(qū)函數(shù)add_new_area,以及內(nèi)存分配相關(guān)的函數(shù)tlsf_malloc、tlsf_free()、tlsf_realloc()、tlsf_calloc()等。

3.1 內(nèi)存初始化函數(shù)init_memory_pool

此函數(shù)用來初始化一塊大的內(nèi)存區(qū),為結(jié)構(gòu)體tlsf賦值(內(nèi)存區(qū)首地址的N個(gè)字節(jié)),并通過調(diào)用函數(shù)process_area對(duì)剩下的內(nèi)存區(qū)進(jìn)行處理,處理后的內(nèi)存如圖 2所示。之后,把內(nèi)存塊b釋放掉,得到初始內(nèi)存塊b,這也是整個(gè)內(nèi)存區(qū)所管理的動(dòng)態(tài)內(nèi)存大小。

3.2 內(nèi)存分配函數(shù)tlsf_malloc

此函數(shù)實(shí)現(xiàn)內(nèi)存的分配,參數(shù)為內(nèi)存大小,返回為內(nèi)存首地址。其偽函數(shù)如下所示:

圖2 內(nèi)存區(qū)處理后的結(jié)構(gòu)圖

此函數(shù)中,主要是通過內(nèi)部內(nèi)存分配函數(shù)malloc_ex來實(shí)現(xiàn)的,其流程如圖3所示。

圖3 malloc_ex()流程

3.3 釋放內(nèi)存函數(shù)tlsf_realloc

內(nèi)存釋放的主要工作在函數(shù)free_ex中實(shí)現(xiàn),主要是判斷釋放內(nèi)存塊的前后內(nèi)存塊是否也是空閑的,如果是空閑內(nèi)存塊,兩塊內(nèi)存塊合并為一個(gè)大的內(nèi)存塊,并根據(jù)內(nèi)存大小加入相應(yīng)的空閑鏈表中,并調(diào)整bit位。其偽代碼如下:

與內(nèi)存分配相關(guān)的函數(shù)還包括tlsf_realloc、tlsf_calloc等,其實(shí)現(xiàn)過程與tlsf_malloc函數(shù)類似。

4 TLSF移植到 μ C/OS-ⅠⅠ

對(duì)TLSF的移植十分簡單,需要與TLSF鎖相關(guān)函數(shù),包括鎖的創(chuàng)建、申請(qǐng)、釋放、消耗等功能,使用互斥量來實(shí)現(xiàn)TLSF鎖功能[5]。相應(yīng)的函數(shù)如下: