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

1、引言

嵌入式系统的内存资源相当有限，所以需对其进行合理的规划和管理，即需要满足其管理特点：快速性、可靠性和高效性。

随着嵌入式应用软件规模的增长，人们希望DSA在满足以上特性的同时，更能够被方便而充分地使用。而UC/OS-II的DSA功能较弱，所以对其进行改进是很有必要的。

2、RTOS的DSA概览

按照记录以及合并空闲内存块的方法，可将RTOS的DSA分成顺序搜索、索引搜索、分类搜索、位图搜索以及伙伴算法等。这些DSA算法都具有分配真实内存，立即合并空闲内存等特点。

2．1 顺序搜索算法

顺序搜索算法采用单向或双向链表维护空闲内存。该算法的时间花费与空闲内存链表长度成正比，时间花费是有界的，但会随着空闲内存块增多而增加，在嵌入式实时系统中并不宜使用。

2．2 索引搜索算法

索引搜索算法用一种比链表复杂的数据结构来记录空闲内存。常见的如排序二叉树，树中每一个节点代表某一个尺寸的空闲内存，存储该尺寸的空闲内存链表指针。索引搜索算法的数据结构和分配、合并内存较为复杂。

2．3 分类搜索算法

分类算法把所有空闲内存按其尺寸范围划归不同的类，同一类内的内存块链接成一个空闲自由内存链表。所有的空闲内存头指针统一由另一个数组链表维护，每个空闲内存头指针对应该数组一个元素。值得注意的是，属同一类的自由内存，并不要求其物理上是相邻的。

分类搜索算法中的链表可以是按空闲内存尺寸排序的，也可以是不排序的。分类算法较为复杂，但不必搜索即可查找合适空闲内存，时间花费不随空闲内存的数量而变化，适合于嵌入式系统采用。

2．4 位图搜索算法

位图搜索算法用一个位图来查找空闲内存，该算法查找空闲内存所需的信息全部存储在一小块内存中，查找响应速度很快。

3、UC/OS-II的DSA不足之处

UC/OS-II中的内存管理模块把动态管理的内存分成多个内存区，每一个内存区又分成一定数量相同尺寸的内存块。具体的UC/OS-II 中，DSA由OS_MEM.c实现，总共只包含5个函数OSMenInit,，OSMemCreate，OSMemGet，OSMemPut 与OSMemQuery，约100行代码，十分精炼。正是由于其精炼，UC/OS-II的DSA提供的功能十分有限，存在以下不足：

1）动态管理的内存块尺寸须在编译时指定，运行时不能更改，限制了系统以后扩展应用程序的灵活性，也造成内存浪费。

2）由于同一分区只能提供唯一尺寸的内存块，而应用中一般需使用到不同尺寸的内存块。为了减少资源浪费，此时则需建立两个以上的内存区，加大了维护开销。

3）不可能提供确定不同内存区的内存块之间尺寸差距的方案，使内存的浪费不可避免。这是由于系统中可能的应用千变万化，而他们申请的内存块尺寸也不尽相同。

4）UC/OS-II的DSA可以归类为2.3中的分类搜索算法，但其并未提供如何搜索到合适分类的方法，也未提供向某一分类申请内存失败后如何向下一分类申请内存的方法，而需要程序员自己提供，加重了程序员负担的同时更是降低了程序的可靠性与稳定性。

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

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条，它是一个双向链表，把属于该类别的所有内存块不排序地逻辑上链接在一起；物理链表：把所有空闲与非空闲内存块