TLSF动态内存分配算法的研究与应用

李江,梅静静,王申良,束颀

(安徽理工大学研究生处,淮南232001)

引 言

由于动态内存分配存在着执行时间不确定与内存碎片过多等问题,嵌入式实时系统中很少使用。TLSF动态内存算法中内存分配与释放均为常数,并且具有内存自动合并、灵活性强、内存碎片少等特点[1]。实时操作系统μ C/OS-II中内存分配使用的是一种静态内存分区方式,内存分配与释放的时间是确定的,缺乏灵活性,而且内存的分配与释放都需要指定正确的内存分区[2],使用比较麻烦,容易出错。

本文把TLSF移植到μ C/OSII中,以提高内存分配的灵活性与执行的实时性,并通过软件仿真测试TLSF在μ C/OS-II操作系统中的运行效果。

1 对TLSF的简介

TLSF是一种二级隔离适应算法,使用位图与链表相结合的方式对内存池进行管理。TLSF实现过程如下:定义一级索引最大值MAX_FLI(小于32)与二级索引最大值MAX_SLI,MAX_SLI等于2的 MAX_LOG2_SLI次方(MAX_LOG2_SLI为程序中计算方便定义的);申请一块大的内存池,通过定义全局变量作为内存池,或者使用操作系统申请一块比较大的内存区(池)使用;使用tlsf_malloc函数申请内存,使用tlsf_free函数释放内存,还包括realloc与calloc函数等函数[3]。

TLSF的数据结构如图1所示。

使用如同μ C/OS-II中管理任务就绪表的形式定义变量FL_bitmap与SL_bitmaps[],空闲链表中有空闲块相应位置1。使用一级索引fl与二级索引sl确定对应空闲链表中空闲块的大小值的范围。fl确定了此一索引管理的内存范围是[2^fl,2^(fl+1))。二级索引值sl表示一级索引被平分为sl块[4]。

图1 TLSF数据结构图

2 TLSF中用到的变量与结构体

2.1 tlsf_t结构体

每个内存区(池)都使用结构体tlsf_t管理,此结构存储在内存区的首部,其结构如下: