摘  要： 以嵌入式实时系统为背景，深入研究了TLSF动态内存分配算法原理及实现过程，并将TLSF移植到μCOS-II中，进行了基于x86平台的仿真测试，取得了很好的效果，为以后学习和应用TLSF算法提供了一种新的方式。
关键词： TLSF；动态存储分配；μCOS-II

    嵌入式实时系统中的关键问题之一是可调度性分析，以确定系统在运行时是否满足应用程序的时间约束。嵌入式实时应用程序通常是在系统的整个生命周期过程中不断执行（几个月，几年，…），这种行为是直接影响动态内存管理的关键环节之一，即内存碎片问题。考虑这两个方面，嵌入式实时应用程序中，动态存储分配DSA（Dynamic Storage Allocation）算法的要求可以概括为：
    （1）时间有界性
    执行内存分配和释放的最坏执行时间是预先已知的，是独立于应用程序的数据，这是必须满足的最主要的要求。
    （2）快速响应时间
    除了具有一个有界的响应时间外，使用的DSA算法的响应时间应该很短。有界的DSA算法，如果响应时间是普通算法的10倍，是不适用的。
    （3）满足内存需要
    系统运行内存不足时，非实时应用程序能够接收一个空指针或被操作系统终止。显然，任何时候都能满足内存需要是不切实际的。但DSA算法必须把内存碎片和内存浪费降到最少以降低耗尽内存池的可能性。
1 RTOS的DSA算法概述
    DSA算法的目标是让应用程序访问空闲内存池中内存块。不同的算法在寻找最佳尺寸空闲块时的策略是不同的。DSA算法可以分为以下类别：
    （1）顺序拟合算法
    在顺序拟合算法中，空闲内存块由单向或者双向链表管理。查询空闲内存块的时间复杂度为O（n）（n为内存块数目），当内存块数目较大时，不能保证查询内存块的实时性，所以不宜在RTOS中使用该算法。
    （2）索引查找算法
    索引查找算法使用排序二叉树等非常复杂的数据结构来管理空闲内存，具有复杂的实现过程，并且因采用的数据结构的不同而具有不同的性能。
    （3）分类搜索算法
    分类搜索算法把空闲内存划分为范围不同的多个区间，每个区间上的内存块由另一个数组链表管理，该数组链表保存着查询空闲内存块的头指针。需要说明的是，同一区间内的空闲内存块，不一定物理相邻。
分类搜索算法虽然复杂，但查找空闲内存块的时间复杂度为O（1），能有效满足实时性，适合在RTOS使用。
    （4）位图搜索算法
    位图搜索算法使用位图管理空闲内存块，搜索空闲内存所需信息都被存储在一小块内存中，可以实时响应系统需求，是RTOS中普遍采用的算法。
2 TLSF算法的数据结构和算法分析
    在ECRTS 2004（Proceedings 16th Euromicro Conference on RealTime Systems 2004）上，MASMANO M提出了TLSF算法。TLSF算法使用隔离适应机制实现了一个最佳适应策略，它结合了分类搜索算法和位图搜索算法的优点，即速度快、碎片少。
    隔离适应机制使用了空闲链表数组，每个数组内包含了一个区间范围的空闲内存块。为了加速访问空闲块，并且管理一大组隔离链表（以减少碎片），该链表数组被分为两级数组来管理。第一级将空闲内存块划分为2n个区间（n=4，5，……，31），称为FLI（First-level Segregated Fit），第二级别SLI（Second-level Segregated Fit）把第一级线性划分为2SLI个区间（SLI是一个用户可配置参数），每个区间都由一条空闲内存块链表管理，每条链表对应一个相关的位图，用来标记链表是否为空。1表示链表非空，即有空闲内存块可用，0则相反。
    为了更快地分配与合并内存块，算法没有对空闲链表进行排序，而是用元素尺寸为32位的二维数组存储了所有链表头指针。图1展示了数据结构的两个层面，第一级是指针数组，分别指向二级链表中的空闲内存块；第二级把第一级线性划分为8个隔离链表。对应的位图如图2所示。

2.1 位图与头指针
    从图2可以看出TLSF中的FL_bitmap与SL_bitmap[]的对应关系，SL_bitmap[]中有一类别存在空闲内存，则FL_bitmap对应位为1；否则FL_bitmap对应位为0。SL_bitmap[]中某位为1，则表示存在属于该类别的可用空闲内存块。
    SL_bitmap[]中每一位对应一个头指针，为1时该指针指向对应的空闲块链表；否则指针为空。
2.2 内存块报头
    TLSF把管理内存块需要的信息都嵌入到内存块内部（该块是否为空），这些指针组成两个链表：类似大小的链表和根据物理地址排序的链表。这就是内存块报头的数据结构。
TLSF的空闲内存块与使用中的内存块报头并不相同，由于占用的内存块（使用过的）不在任何隔离链表中，它们的头部比空闲块的头部要小，如图3所示。

    空闲块的报头中包含以下所需的数据：
   （1）块的大小，释放该块和与下一物理内存块链接时需要的链表。
   （2）边界标签，前一个物理内存块的头指针。
   （3）把该块存入相应的隔离列表（双向链表）的两个指针。
    一个占用的内存块头中仅包含大小和边界标记的指针。
     TLSF中使用两条链表管理内存块。逻辑链表：该链表为双向链表，对应TLSF的第二级别的分类，把属于该类别的所有内存块，非排序的逻辑上链接在一起；物理链表：把所有空闲与非空闲内存块按物理地址相邻链接起来。

2.4 TLSF的时间复杂度
    TLSF的tlsf_malloc（），tlsf_free（）的时间复杂度为O（1），与内存块数量无关。
    tlsf_malloc（）的伪代码如下：
    void*tlsf_malloc（）（size）{
     int f1，s1，fl2，sl2；
        void*found_block，*remaining_block；
        mapping_search（size，&fl，&sl）；        //o（1）
        found_block=FIND_SUITABLE_BLOCK（size，fl，sl）；            //o（1）
        clear_bit（sl，sl_bitmap[fl]）；    //o（1）
        clear_bit（fl，fl_bitmap）；        //o（1）
        if（sizeof（found_block）>size）{
            remaining_block=bhdr_t->size-found_block；
            MAPPING_INSERT（sizeof（remaining_block），
&fl2，&sl2）；    //o（1）
            INSERT_BLOCK（remaining_block，fl2，sl2）；                //o（1）
        }
        remove（found_block）；
        return found_block；
}
    虽然TLSF结构中的tlsf_malloc要做一个搜索——FIND_SUITABLE_BLOCK，但由于使用了位图搜索算法，最坏情况下的时间复杂度依然为O（1）。
tlsf_free的伪代码如下：
void tlsf_free（block）{
        int fl，sl；
        void*tmp_block，*tlsf；
        tmp_block=merge（block）；//o（1）
        MAPPING_INSERT（block->size & BLOCK_SIZE，
&fl，&sl）；        //o（1）
        INSERT_BLOCK（block，tlsf，fl，sl）；        //o（1）
}
tlsf_free检查释放内存块的上一块和下一块物理相连的内存块是否空闲，并将它们合并。
2.5 TLSF参数化配置
    TLSF结构的特征在于一级索引、二级索引、三级索引三个基本参数。
    （1）一级索引（FLI）
    它是第一级隔离区间的数目，均为2的n次幂。FLI最大可取31。
    FLI=min（log2（memory_pool_size），31）（2）
    （2）二级索引（SLI）
    该索引将一级索引线性划分。为了在二进制运算中获得更高的效率，SLI必须是2的n次幂，并且范围在[1，32]之间。为方便起见，SLI用第二级别的log2来表示，如SLI=2则表示第二级别把第一级别分为4份。
    （3）最小内存块大小（MBS）
该参数用来限制最小块的大小。考虑到实现的原因，MBS常数被设置为16 B。
2.6 TLSF的碎片
    TLSF在相应隔离链表中不执行穷举搜索来找一个合适的块以满足请求，这样就产生了碎片。TLSF使用映射函数和位图直接找到包含大小相同或大于请求的非空最小隔离链表。一旦相应的隔离链表被发现，链表中的第一块用来服务请求。因此，有可能发生这样的情况：存在足够满足请求的空闲块，但却存储在上一个隔离链表中（被映射函数返回前的隔离链表）。
    当最大空闲块具有隔离链表（空闲块的大小小于下一隔离链表中的最小容量）的最大容量，并且应用程序请求了一个大于该隔离链表中开始大小的内存块时，发生最坏的碎片情况。TLSF将尝试开始从持有空闲块的隔离列表中查找一个合适的块来服务请求，因此，请求将失败。
TLSF内存碎片的计算公式为：
    Fragmentation=2FLI/2SLI-2（3）
3 μCOS-II中DSA的不足之处

     μCOS-II中以分区的形式管理内存，分区中包含一定数量的内存块，并且内存块大小相同。在μCOS-II中，DSA由OS_MEM.c实现，包含以下几个函数：OS_MemInit、OSMemCreate、OSMemPut、OSMemGet、OSMemQuery。μCOS-II以代码精练著称，DSA函数更不例外，但精练的背后是功能的不足，主要有以下三点：
  （1）编译时就必须指定内存块的大小，而且不能变动，灵活性极差，内存浪费也不可避免。
  （2）同一分区中内存块的大小唯一，然而实际应用中需要使用的内存块尺寸却不尽相同。此时则需要建立两个以上的内存区，加大了维护开销，也不可避免地造成了内存浪费。
  （3）μCOS-II的DSA是分类搜索算法的一种，但没有提供搜索合适分类的方法，也未提供向某一分类申请内存失败后如何向下一分类申请内存的方法。内存的使用算法完全由程序员提供，这无疑加重了程序员负担，而且由于程序员水平参差不同，系统的可靠性与稳定性也往往大打折扣。
4 TLSF向μCOS-II的移植
    结合TLSF的特点和μCOS-II中DSA的不足，本文把TLSF算法移植到μCOS-II，改善了μCOS-II中的内存管理模块。
    TLSF具有在同一内存池中分配不同尺寸的内存块的特点，为方便起见，在移植了TLSF算法的μCOS-II中只使用物理相邻的一块内存，并把TLSF定制为可裁剪模块，配置相关参数后，编译TLSF模块。
移植过程即向μCOS-II添加功能函数，同时需要为TLSF提供锁相关功能。移植后使用μCOS-II提供的Mutex来实现TLSF锁功能。详细源码如下所示：
INT8U perr；
#define TLSF_MLOCK_T OS_EVENT*
#define TLSF_CREATE_LOCK（ResoureceMutex）    
（*（ResoureceMutex））=OSMutexCreate（4，&perr）
#define TLSF_DESTROY_LOCK（ResoureceMutex）    
OSMutexDel（*（ResoureceMutex），OS_DEL_ALWAYS，&perr）
#define TLSF_ACQUIRE_LOCK（ResoureceMutex）    
OSMutexPend（*（ResoureceMutex），0，&perr）
#define TLSF_RELEASE_LOCK（ResoureceMutex）    
OSMutexPost（*（ResoureceMutex））
5 实验结果
    本次实验使用BC4.5为开发环境，以x86平台为仿真环境，测试了μCOS-II中移植的TLSF内存管理模块。
实验过程中，创建一个任务，并通过TLSF提供的tlsf_malloc函数请求随机大小的内存，延时3 s后释放内存，再延时3 s后继续请求内存。实验中使用TLSF自带的调试函数print_all_blocks来打印TLSF结构体详细情况，调用该函数，需要开启TLSF的DEBUG功能：

    TLSF分配和释放内存的时间复杂度为O（1），在响应时间和内存碎片方面表现优异，并且算法开源，非常适合研究学习。
参考文献
[1] MASMANO M， RIPOLL I， CRESPO A， et al. TLSF： a new dynamic memory allocator for real-time systems[C]. In：16th Euro micro Conference on Real-Time Systems，Catania，Italy， IEEE，2004：79-88.
[2] MASMANO M， RIPOLL I， CRESPO A. Description of the TLSF memory allocator version 2.0[EB/OL]. [2005-11-11]（2012-10-23）http：//wks.gii.upv.es/tlsf/.
[3] 屈庆琳，李良光.TLSF算法在嵌入式系统中的研究与实现[J].计算机与信息技术，2011，10：24-26.
[4] 李江，梅静静，王申良，等.TLSF动态内存分配算法的研究与应用[J].单片机与嵌入式系统应用，2011，11：1-4.
[5] 童丹，孙汉旭，贾庆轩.一种基于μCOS-II空间机器人操作系统的研究[D].北京：北京邮电大学，2009.
[6] 梁乘铭，韩坚华，夏成文，等.μCOS-II中动态内存管理方案的改进与实现[J].微计算机信息，2008（5）：44-46.