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

1、引言

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

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

2、RTOS的DSA概览【2】【3】【4】【5】

按照记录以及合并空闲内存块的方法，可将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中的分类搜索算法，但其并未提供如何搜索到合适分类的方法，也未提供向某一分类申请内存失败后如何向下一分类申请内存的方法，而需要程序员自己提供，加重了程序员负担的同时更是降低了程序的可靠性与稳定性。[page]

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。

函数

功能

时间复杂度

在OS_CFG.h配置常数为1，表示允许

tlsf_malloc

类似c语言的内存函数malloc

O(1)

OS_MEM_EN，OS_MEM_DESTROY

tlsf_free

类似c语言的内存函数free

O(1)

tlsf_init

初始化内存池

O(1)

tlsf_destroy

销毁内存池

O(1)

OS_MEM_DESTROY

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

根据UC/OS-II的一般应用，还在OS_CFG.h中配置了FLI=20（动态管理1MB内存），SLI=2,MSB=16。根据需要动态管理的内存池大小可以调整FLI，要降低内存块粒度减少内存浪费可以增大SLI。

由于TLSF的内存块是动态分割与合并的，因此其尺寸在运行时可变，所以其内存利用率高，内存分配可靠。

6、UC/OS-II中的TLSF动态内存管理模块实验分析

本文做了一个对比实验，比较UC/OS-II使用原有的DSA与使用TLSF的性能差异。为了便于和TLSF对比，实验条件为：1）原有DSA只使用一个内存分区，其只能提供唯一尺寸的内存块。2）实验所用程序为一个DSA基准测试专用程序cfrac【6】，该程序分解给定数字的因数，在此过程中向系统申请/释放内存，本实验要分解的数是23533。3）用于动态管理内存区heap的尺寸为256KB。4）两个DSA都做10次实验，最后对结果求平均值。www.51kaifa.com

对比表2的分配的内存块最大尺寸与分配的内存块平均尺寸可以看出，虽然UC/OS-II原有DSA与TLSF均使用了一块256KB的内存作为动态内存，但只有TLSF可以提供不同尺寸的内存块。这就让TLSF获得更高的内存利用率。从TLSF的内存最大使用量标志与内存平均使用量标志均是 UC/OS-II原有DSA的10倍，也可以得出以上结论。TLSF的SLI是2，粒度是比较细的，所以平均分配尺寸较小。

虽然TLSF的执行每个malloc平均指令数与执行每个free平均指令数均是UC/OS-II原有DSA的5倍以上，即TLSF要比UC /OS-II原有DSA耗时，但这是以牺牲内存空间为代价的。这是由于此实验的UC/OS-II原有DSA并未使用搜索合适内存区的相关算法，内存资源浪费很大，在程序规模不断增长而要求更节约内存时，UC/OS-II原有DSA这两个指标也会有明显增大。

DSA

TLSF

原有DSA

DSA

TLSF

原有DSA

内存最大使用量maxUsed（Byte）

1191

10680

内存最大使用量标志（heap/maxUsed）

220.1

24.5

内存平均使用量avgUsed（Byte）

558

5819

内存平均使用量标志（heap/avgUsed）

469.4

45.0

分配的内存块最大尺寸（Byte）

268

280

执行每个malloc平均指令数

526.0

60

分配的内存块平均尺寸（Byte）

30.5

280

执行每个free平均指令数

325.9

58

表2  TLSF实验结果数据

此外，对比文献【2】【7】【8】中TLSF相关的数据，也可知在UC/OS-II中实现的TLSF动态内存管理算法获得较好的性能。

7、结论

本文创新地在UC/OS-II中实现了一种使用方便、高效、快速、可靠与节约的动态内存管理方案TLSF，它是可以裁减的模块，具有优秀的空间利用率与较好的时间响应速度，提供方便的内存管理函数，改善了UC/OS-II原有内存管理方案程序接口不够友好、不够规范的缺点，减少了内存浪费，对于一般的实时系统特别是软实时的、应用程序规模大的场合具有较大的应用价值。

参考文献：

【1】黄贤英，王越，陈媛.嵌入式实时系统内存管理策略[J].计算机工程与设计. 2004 年10 月,第25 卷第10 期.www.51kaifa.com

【2】M. Masmano, I. Ripoll, A. Crespo, and J. Real.TLSF: a New Dynamic Memory Allocator for Real-Time Systems[R]. Proceedings of the 12th 16th Euromicro Conference on Real-Time Systems (ECRTS’04).1068-3070/04

【3】M. Masmano. TLSF Implementation and Evaluationin OCERA[R]. Technical Report OCERA D4.4, RealTime Research Group. Universidad Politecnica de Valencia,2004. Available at: http://www.ocera.org andhttp://rtportal.upv.es.www.51kaifa.com

【4】吴晓勇,曾家智.操作系统内核中动态内存分配机制的研究[J]. 成　都　信　息　工　程　学　院　学　报. 2005 年2 月,第20 卷第1 期.

【5】杨雷, 吴珏, 陈汶滨.实时系统中动静结合的内存管理实现[J]. 微计算机信息.( 嵌入式与SOC )2005 年第21 卷第10-2 期。

【6】[EB/OL]ftp://ftp.cs.colorado.edu, directory/pub/cs/misc/malloc-benchmarks

【7】I. Puaut. Real-Time Performance of Dynamic MemoryAllocation Algorithms[R]. Technical Report 1429,Institut de Recherche en Informatique et SystemesAleatories, 2002.

【8】K. Nilsen and H. Gao. The real-time behavior of dynamicmemory management in C++[R]. In Proceedings of the 1995 Real-Time technology and Applications Symposium, pages142–153, Chicago, Illinois, June 1995.