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

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

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

引 言

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

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

1 對TLSF的簡介

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

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

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

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

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

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

每個內(nèi)存區(qū)(池)都使用結(jié)構(gòu)體tlsf_t管理,此結(jié)構(gòu)存儲在內(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中還用到兩個結(jié)構(gòu)體:area_info_t與bhdr_t。

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

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

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

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

而結(jié)構(gòu)體struct free_ptr_struct用來鏈接一鏈表中的各個空閑內(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)存分配相關的函數(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個字節(jié)),并通過調(diào)用函數(shù)process_area對剩下的內(nèi)存區(qū)進行處理,處理后的內(nèi)存如圖 2所示。之后,把內(nèi)存塊b釋放掉,得到初始內(nèi)存塊b,這也是整個內(nèi)存區(qū)所管理的動態(tài)內(nèi)存大小。

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

此函數(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來實現(xiàn)的,其流程如圖3所示。

圖3 malloc_ex()流程

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

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

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

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

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