嵌入式实时系统中动态内存管理算法的设计与实现

沈非一，张延园，林 奕

(西北工业大学计算机学院，陕西 西安 710129)

0 引言

由于嵌入式环境中拥有的系统资源通常比较小，尤其是内存资源非常宝贵，因此内存的利用率将会成为嵌入式系统性能的重要瓶颈。内存管理是操作系统的核心模块之一，主要负责组织与调度内存的分配和释放操作，以供内核程序和应用程序使用［1］。

静态内存分配要求编译时将程序运行所需要的内存确定好，在整个程序运行过程中不再进行分配和释放。而动态内存分配可以根据程序执行过程中所需的内存大小在运行时进行分配。因此相比于静态分配，动态分配更加灵活，内存的利用率更高。但是动态分配在分配时需要消耗更多的时间，使得系统的实时性能受到一定的影响，算法的碎片率和时间性能将成为主要的指标。

典型的动态内存管理算法有［2］:顺序适配(Sequential Fit)、分段空闲链表(Segregated Free Lists)、伙伴系统(Buddy System)、二级分段匹配算法(Two Level Segregate Fit)等［3］。结合一些常见的底层结构策略，如:空闲链表、边界标记、位图、延迟合并［4］等。

衡量一个动态内存管理算法的优劣主要从2 个方面进行考察［5-6］:

1)实时性。嵌入式系统为了保证实时性，要求内存分配过程要尽可能地快，确保系统能够及时响应，同时在最坏情况下要使得运行时间有界［7］。

2)内存碎片率［8］。主要考察系统的内部碎片率，与内存的利用率等价［9］。外部碎片在不同大小的内存申请中定义有所差别，外部碎片将导致内存分配失败。本方案中并不把外部碎片作为衡量标准，当内存分配失败时，任务等待一段时间再次进行申请［10］。

μCos 是基于优先级的抢占式的实时多任务嵌入式操作系统［11］，包含实时内核、任务管理、时间管理、任务间通信同步(信号量、邮箱、消息队列)和内存管理等功能。其内核源码是开源的，代码本身十分精简。μCos 系统本身的内存管理算法采用固定式的分区块模式，虽然效率比较高，但是不够灵活，内存利用率低下。本文选用μCos-III 操作系统作为实验平台来实现仿真动态内存管理算法，在原有算法的基础上进行改进。

1 算法方案与设计

主要叙述在μCos 操作系统上实现的动态内存管理改进方案。

1.1 总体方案

针对不同大小的内存申请，其碎片率与实时性能的特点均有所差别，本文对小块内存以及大块内存的申请进行分段处理［12］。

很多学者的研究已经证明，现代程序的内存分配均以小块居多。文献［13］在复数的程序中测试了内存的使用，结果表明88%的内存分配小于64 字节。文献［14］拥有类似的结果，它指出90%的内存分配在512 字节以下，并且通常拥有较短的生命周期。可以看出小块内存具有分配与释放频繁、生命周期较短的特点，因此对于时间性能的要求更高，采用伙伴系统对小块内存进行管理，提升内存分配与释放的速度，但是伙伴系统通常伴随着较高的内部碎片率。对于小块内存的申请，内存块本身并不大，系统总体的碎片率不会太高，通过牺牲一定的碎片率来换取时间性能。

小块内存与大块内存的分界，本文实现中设定为128 字节。虽然嵌入式系统总体以小块内存分配居多，但对于具体的不同系统环境与负载还是有所差异。所以将大小块内存分界的临界值(即此处的128字节)作为系统参数在初始化时予以设定，可以动态调整，增加算法应用的灵活性。

对于大块的内存申请，以二级分段匹配算法(TLSF)［15］的思想为基础，利用二级位图索引来管理空闲内存块，将最坏情况下查找内存块的时间控制在O(1)。同时采用FIFO 和LIFO 的方式对二级索引下的内存块分配与释放进行管理，并设定合并阈值，限制合并操作在一定条件下进行。图1 为系统的总体结构。

图1 系统总体结构

1.2 小块内存区的处理方式

首先介绍一下伙伴的概念，满足以下3 个条件的称为伙伴:

1)2 个块大小相同;

2)2 个块地址连续;

3)2 个块必须是从同一个大块中分离出来的。

系统初始化时，维护一系列的空闲链表，大小为1，2，4，8，16，...，2m(此处说明时使用的内存大小单位未标明，而是从1 开始，通常情况下在32 位的计算机中内存块大小不会小于1 个字长即4 字节，此处默认大小单位为4 字节，即最小的内存块大小为1 ×4=4 字节)。在本设计中，2m的值即为小块内存与大块内存的分界点。

所有的小块内存受到伙伴块条件的约束，内存块的分割采取一分为二的方式，而只有互为伙伴的2 个内存块才可以进行合并。

在任务申请内存块时，假设此次申请的大小为k，首先定位需要分配的内存大小，即找到一个i，使得申请的大小k 满足2i-1＜k≤2i。如果2i的空闲链表不为空，则从中取出一个内存块分配给任务。如果2i的空闲链表为空，则搜索空闲块长度为2i+1的空闲链表;如果不为空，则从该空闲链表中取出一个内存块，把该内存块分割为大小相等2 部分(这2 块就为伙伴内存)，一块用于分配，另一块链入长度为2i的空闲链表中;如果2i+1的空闲链表也为空，则依次查找长度为2i+2、2i+3...的空闲链表，直到找到空闲内存块并作多次分割。这种分配方式比较灵活，可以满足各种大小的分配要求，有效缓解了外部碎片的问题(内部碎片不可避免)。

在空闲链表上以2 的幂次构建一级位图索引，在判断完内存块大小后可以在O(1)时间内找到对应的空闲块。

在任务不需要使用某占用块时，需要将该内存块释放，把这块内存插入到相应的空闲链表中。在插入空闲链表之前，需要先判断该内存块的伙伴块是否是空闲块，如果空闲则需要将这一对伙伴块进行合并。然后对合并之后的空闲块再次判断伙伴块是否需要合并，依次类推。

小块内存维护m +1 个分段空闲链表控制块结构如下:

1.3 大块内存区的处理方式

大块内存的处理基于TLSF 算法［16］的基本思想，采用位图和分段空闲链表相结合的方式对系统中的空闲内存块进行管理，位图索引一共分为2 级［17］。

大块内存区用到如下几个参数:

1)一级索引(First Level Index，FLI):一级索引用来控制一级链表的长度，表示了最大的内存范围大小。内存区总共被划分为FLI 个大小区间，一级索引值FLI 对应的内存大小区间为［2FLI，2FLI+1)。

2)二级索引(Second Level Index，SLI):二级索引对一级索引划分的内存区间按照线性顺序再次进行划分。二级索引的值在系统初始化前进行人为设定，例如SLI=4，则一级索引的内存区被分割为16 段。其中每一段的大小为［2FLI，2FLI+j* 2FLI-SLI］，j 为该段在内存区中线性顺序的序号。SLI 的值决定了一级索引内存区被分割的粒度，SLI 的值越大分割的越细。一般来说SLI 的值不超过5，即分段数量不超过32，这样可以用单个32 位的位图来对应一级索引内存区中的所有内存块。

3)分割阈值(Split Threshold Value，STV):该参数替代TLSF 中原有的最小块大小MBS(Minimun Block Size)。只有当分配的内存块大小和申请的内存块大小的差值超越这个阈值的时候，才进行分割操作，否则直接进行分配，此处的阈值设定为64 字节。

大内存区控制块结构如下:

一级索引分区的控制块结构如下:

在二级索引中为每个内存块附加块头和块尾结构来进行双向链接。

分配内存块时，利用一级和二级索引来找到与该内存块大小对应的二级内存分段，如果该链表非空，则查找链表的头结点;如果头结点的内存块大于或等于申请的内存块大小，则使用该块内存进行分配，并比较分割阈值得出是否需要分割;如果该链表为空或者头结点大小不满足分配条件，则直接搜索下一个非空的内存分段，从该分段的空闲链表尾部取出一个内存块，因为在本分段内进行分割的话余下的内存块通常过小，所以直接去下一级分段取一个合适的内存块。查找内存块的时间依然可以在O(1)内完成。

释放内存块时，判断能否与前后的内存块进行合并(通过边界标记进行判断)，如果进行过合并操作，则将该内存块插入对应的分段空闲链表尾部，否则将该内存块插入到空闲链表头部。因为尾部的内存块有更大的可能性被分割，可以保证其余内存块在物理上的连续性。

2 函数接口

函数接口的设定沿用原μCos-III 的结构，修改必要的参数并实现新的算法。

1)内存池初始化。

初始化的主要任务是为确定大小内存区的临界值，设定大内存区控制块(FLI、SLI 以及STV 的大小)，并且初始化小内存区伙伴系统的空闲链表控制块、大内存区、一级索引控制块以及位图。该接口函数没有返回值，调用它的函数通过查看p_err 的内容来判断内存池初始化是否成功。

2)创建内存结构。

该接口的任务是构建起整个内存的结构，将空闲内存划分并挂载到相应的空闲链表下。

3)申请内存块。

与原μCos-III分配函数不同，接口参数只需要传入申请的内存块大小即可，判断申请的内存属于小内存区还是大内存区进行处理。

4)释放内存块。

3 实 验

3.1 实验设计

测试系统选用μCos-III 操作系统，将μCos-III 移植到Windows 平台下运行具体的算法。实验用PC机的CPU 为Intel i7-3630QM，主频2.4 GHz。

实验利用随机数产生一定大小范围内的内存申请和释放请求，把内存的大小范围分为以下5 个区间(单位为字节)，分别为区间1:［32，64)，区间2:［64，128)，区间3:［128，256)，区间4:［256，512)，区间5:［512，1024］。在μCos-III 系统中设计5 个任务，分别产生这5 个区间范围内大小的随机值，并按照这个大小申请内存，随后间隔一个随机的时间进行内存释放。每个任务一共进行500 组分配和释放操作，任务之间的分配和释放是同优先级的，根据随机的时间间隔交替进行，最后的结果取平均值。

在整个系统运行过程中，利用trace 文件记录每一次操作。每一条trace 包含以下几条信息:操作类型(分配或释放内存块)、内存块的大小、内存块的物理地址、操作花费的时间、完成操作时的系统时间。

3.2 实验结果

1)时间开销。

通过分析trace 文件得到的分配和释放时间如图2 和图3 所示，图中的数据为500 次操作的平均值，单位为微秒(μs)。在实验中采用QueryPerformance-Counter 命令进行计时，如果硬件中存在定时器，该命令就会启动此硬件定时器，并连续查询定时器的数值，该定时器的精度与硬件时钟的晶振一样精确，利用这个方法使得时间参数精确到微秒级。

图2 内存分配的平均时间(μs)

图3 内存释放的平均时间(μs)

由图2 得出伙伴系统分配内存的速度最快，TLSF 算法的速度较慢，并随着区间的增大需要的时间也有所增长。改进的算法采用分段的机制，因此在区间1 和区间2 的分配速度和伙伴系统相当，在区间3～区间5 中的分配速度比TLSF 算法快1μs 左右。

由图3 得出伙伴系统的内存释放速度比TLSF 和改进的算法快，在区间1 和区间2 改进的算法和伙伴系统相当，区间3～区间5 和TLSF 算法相当，没有太大的差别。

2)内存碎片率。

利用trace 文件中记录的系统运行信息，计算出当前时刻系统的内部碎片率。在每次内存的分配和释放操作之后记录当前的内存碎片率，按照区间不同分组计算系统运行过程中的平均碎片率。

图4 内存碎片率(%)

由图4 可以看出Buddy 算法的碎片率是相当高的，所有区间基本在25%左右浮动，而在最差情况下可能达到50%。TLSF 算法的内存碎片率要明显低于伙伴系统，保持在3%以下，由于其内存块大小可以浮动，内部碎片率主要体现在块头的额外开销，随着区间的增大，碎片率逐步减小。改进的TLSF 算法在区间1 和区间2 拥有和伙伴系统相似的碎片率，由于合并阈值的关系，在区间3～区间5 要高于TLSF算法，但随着区间的增大逐步降低直至与TLSF 算法相当。

4 结束语

本文在伙伴算法及TLSF 算法的基础上设计了一种新的内存分配算法，分开处理小内存块和大内存块的请求，通过伙伴系统管理小块内存，在TLSF 上利用不同的申请释放方式管理二级索引，并在μCos-III 系统上实现了该算法。实验结果表明这种动态内存管理算法在时间和空间上综合性能比较好。

［1］Masmano M，Ripoll I，Crespo A，et al.Implementation of a constant-time dynamic storage allocator［J］.Software:Practice and Experience，2007，38(10):1000-1025.

［2］Wilson Paul R，Johnstone Mark S，Neely Michael，et al.Dynamic storage allocation:A survey and critical review［C］// International Workshop on Memory Management，Lecture Notes in Computer Science.1995，986:1-116.

［3］吴文峰.嵌入式实时系统动态内存分配管理器的设计与实现［D］.重庆:重庆大学，2013.

［4］姜艳，曾学文，孙鹏，等.实时嵌入式多媒体系统模糊阈值合并内存管理算法［J］.西安电子科技大学报(自然科学版)，2012，39(5):220-227.

［5］Gao Chao，Han Rui，Ni Hong.Memory management solution in enbedded Linux systems［J］.Journal of Chinese Computer Systems，2011，32(4):614-618.

［6］田令平.嵌入式操作系统内存管理研究［J］.电脑知识与技术，2006(4):169-171.

［7］王兆文，蒋泽军，陈进朝.一种提高Linux 内存管理实时性的设计方案［J］.计算机工程，2014，40(9):291-294.

［8］Mark S Johnstone，Paul R Wilson.The memory fragmentation problem:Solved?［C］// Proceedings of the 1st International Symposium on Memory Management.1998:26-36.

［9］符丽枚，陈世航.嵌入式软件运行内存余量测试方法［J］.自动化应用，2014(11):6-8.

［10］董文生，沈春锋.内存大小可控的高速内存管理算法［J］.控制工程，2013，20(S1):69-71.

［11］Jean J Labrosse.μC/OS-II 嵌入式实时操作系统［M］.2版.邵贝贝，宫辉，蒋俊峰，等译.北京:北京航空航天大学出版社，2003:69-95.

［12］陆小双，帅建梅，吴庆响.一种新的面向对象程序的内存管理器［J］.计算机工程，2012，38(9):21-23.

［13］Berger E D，Zorn B G，McKinley K S.Reconsidering custom memory allocation［J］.Sigplan Notices-SIGPLAN，2002，37(11):1-12.

［14］Lee W H，Chang J M，Hasan Y.Evaluation of a high-performance object reuse dynamic memory allocation policy for C++programs［C］// Proceedings of the 4th IEEE International Conference on High Performance Computing in the Asia-Pacific Region.2000:386-391.

［15］Masmano M，Ripoll I，Crespo A，et al.TLSF:A new dynamic memory allocator for real-time systems［C］// Proceedings of the 16th Euromicro Conference on Real-Time Systems.2004:79-88.

［16］王秀虎，张昕伟.基于μCOS-Ⅱ的TLSF 动态内存分配算法的应用与仿真［J］.微型机与应用，2013，32(5):4-7.

［17］屈庆琳，李良光.TLSF 算法在嵌入式系统中的研究与实现［J］.计算机与信息技术，2011(10):24-26.