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管理,此结构存储在内存区的首部,其结构如下:

此结构体也记录内存区的基本信息,在 tlsf.c中定义全局变量“static char*mp=NULL;”管理所有的内存区。在结构体tlsf_t中还用到两个结构体:area_info_t与bhdr_t。

2.2 结构体area_info_t

结构体area_info_t用来链接各个不相邻的内存区,其结构如下:

2.3 结构体bhdr_t

结构体bhdr_t存储各个空闲链表的表头,如果此链表中无空闲内存块,则为null。结构体如下所示:

而结构体struct free_ptr_struct用来链接一链表中的各个空闲内存块,结构如下:

3 TLSF中用到的函数

TLSF算法主要包括:内存区的初始化函数init_memory_pool、内存区销毁函数 destroy_memory_pool、增加内存区函数add_new_area,以及内存分配相关的函数tlsf_malloc、tlsf_free()、tlsf_realloc()、tlsf_calloc()等。

3.1 内存初始化函数init_memory_pool

此函数用来初始化一块大的内存区,为结构体tlsf赋值(内存区首地址的N个字节),并通过调用函数process_area对剩下的内存区进行处理,处理后的内存如图 2所示。之后,把内存块b释放掉,得到初始内存块b,这也是整个内存区所管理的动态内存大小。

3.2 内存分配函数tlsf_malloc

此函数实现内存的分配,参数为内存大小,返回为内存首地址。其伪函数如下所示:

图2 内存区处理后的结构图

此函数中,主要是通过内部内存分配函数malloc_ex来实现的,其流程如图3所示。

图3 malloc_ex()流程

3.3 释放内存函数tlsf_realloc

内存释放的主要工作在函数free_ex中实现,主要是判断释放内存块的前后内存块是否也是空闲的,如果是空闲内存块,两块内存块合并为一个大的内存块,并根据内存大小加入相应的空闲链表中,并调整bit位。其伪代码如下:

与内存分配相关的函数还包括tlsf_realloc、tlsf_calloc等,其实现过程与tlsf_malloc函数类似。

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

对TLSF的移植十分简单,需要与TLSF锁相关函数,包括锁的创建、申请、释放、消耗等功能,使用互斥量来实现TLSF锁功能[5]。相应的函数如下: