UC/OS-II中动态内存管理方案的改进与实现

4、TSLF的数据结构介绍和算法分析【2】

TLSF是M.Masmano在IEEE的Euromic的会议上提出的，用于支持嵌入式实时系统的动态内存管理，它结合了2.3分类搜索算法与2.4位图搜索算法的优点，速度快、内存浪费少，所用的数据结构如图1。

图1 TLSF数据结构

TLSF用两个层次的分类对不同尺寸的内存块进行分类。第一层次的类别目录为2n，n为4，5，……，31的整数，称为FLI（First-level Segregated Fit）。每一个FLI类别又根据第二层的SLI细分为2SLI个子类别。第二层的每个类别，都对应一条属于该类别尺寸范围内的内存块链表。为了加快分配与合并内存块的速度，链表是不排序的。所有的链表头指针用数组元素尺寸为32位的二维数组存储起来。各个类别所表示的内存块尺寸范围可参见图1。第一层次、第二层次都使用位图指示该类别有无空闲内存块，有则该类别对应的位为1，否则为0。

4．1 TLSF位图与TLSF头指针

TLSF中每一个第一或第二层次的类别对应位图中的1位，位为1表示该类别有空闲内存块，为0则表示没有。可根据第一、第二类别的总数确定总的位图存储空间大小。位图存储在内存池的开始位置。

TLSF第二层次的每一类别皆对应一个头指针。若该类别的空闲内存块链表非空，则类别头指针指向该链表，否则头指针为空。

4．2 TLSF块头

TLSF的空闲内存块与使用中的内存块块头并不相同，如图2所示。

图2 内存块块头数据结构

TLSF中所用的内存块由两条链表组织。逻辑链表：每个第二层次的类别可有0条或1条，它是一个双向链表，把属于该类别的所有内存块不排序地逻辑上链接在一起；物理链表：把所有空闲与非空闲内存块按物理地址相邻链接起来。www.51kaifa.com

4．3 TLSF算法分析

参考文献【2】的推导，TLSF的malloc，free的时间复杂度并不随空闲内存块的数量而变化，都是O(1)。

4．4 TLSF的碎片

由于TLSF的分类内的自由空闲内存链表是不排序的，分配时也不搜索，所以申请尺寸属于某一类别的内存块时，却要从下一个类别分配内存【2】。TLSF内存碎片的计算公式为：

4．5 TLSF参数的控制

TLSF有3个可以配置的参数常量。

FLI：是第一层次类别的数目，类别都是2的n次方。FLI最大可去到31，

SLI：是第二层次类别的数目。出于性能考虑，SLI必须是2的n次方，并且范围在[1, 32]之间，以便用单字处理指令。一般，SLI用第二层次类别数目的 来表示，如SLI＝2则表示第二层次类别把对应的第一层次类别分为4份。

MBS(Minimum block size)：最小块的尺寸，一般为16Bytes。www.51kaifa.com

5、TLSF向UC/OS-II的移植定制

为了克服UC/OS-II原有DSA的不足，本文引进了TLSF动态内存管理算法，并做了适当的修改以便适合于UC/OS-II。

由于TLSF可以在同一内存池分配不同尺寸的内存块，为了充分发挥TLSF这一优点、减少管理开销，在其移植后只使用物理地址连续的一块内存。在 TLSF的移植过程中，仿照了UC/OS-II系统的风格，把其定制成可裁减的模块，只有配置了相关常数后，才编译该模块。提供的编程接口函数与配置常数如表1。

表1 UC/OS-II的TLSF编程接口函数与配置常数