一种微型嵌入式系统动态内存分区管理机制的研究

肖蕾　刘克江

摘 要：本文基于现有嵌入式操作系统动态内存管理机制的原理，研究和分析了μC/OS、freeRTOS等多个微型嵌入式操作系统内存管理的优缺点，以多平台通用、高效率、简单易用为目标，实现了一种新的动态内存管理机制，主要适用于不使用操作系统或使用小型操作系统的嵌入式产品中，有效解决了动态内存的管理问题。

关键词：嵌入式系统；动态内存；内存溢出；管理机制

中图分类号：TP316.2 文献标识码：A

Abstract：Based on the principle of existing embedded operating system dynamic memory management mechanism， research and analysis of the advantages and disadvantages of μC/OS，freeRTOS and other micro embedded operating system memory management.In this paper，multi-platform，highly efficient，easy to use as the goal to achieve a new dynamic memory management mechanism， mainly applicable to not use the operating system or the use of small embedded operating system products，the mechanism effectively solves the problem of dynamic memory management.

Keywords：embedded system；dynamic memory；memory overflow；management mechanism

1 引言（Introduction）

嵌入式操作系统内核往往提供了动态内存分区管理机制，基于操作系统移植便可以在应用开发时使用动态内存分配，使用动态内存分配可避免使用大量内存空间，从而使软件设计更加合理。但是有时由于成本、硬件设计或功能需求等因素不需要移植嵌入式操作系统，或者只需使用μC/OS、freeRTOS等微型操作系统内核，就会发现动态内存分区管理机制存在着许多不足[1]。μC/OS为了尽可能精简代码和追求更好的实时性，其内存管理模块根据用户程序要求把动态内存分成多个分区，每一个分区又分成数量和大小固定的内存块，内存块数量和大小在编程时便已确定不可更改，限制了系统的扩展性和灵活性，而且由于μC/OS内存管理模块创建一个动态内存分区只能提供唯一尺寸的内存卡，当系统需要不同尺寸时须创建多个动态内存分区，这样便不可避免地加大了系统开销和内存浪费，且μC/OS不对回收的内存块进行合法性检查[2，3]。freeRTOS提供的动态内存管理方案在动态内存回收时只是将其从小到大排列并不把相邻的两块空闲区合并成一个大空闲区，该方案将可能导致整个动态内存分区被分割成很多个细小的内存碎片，同样，freeRTOS不对回收的内存块进行合法性检查[4，5]。

针对上述存在的不足，本文提出一种多平台通用、高效率、简单易用同时具有动态内存溢出检测机制的微型嵌入式动态内存管理机制HeapManager。

2 HeapManager的实现（Realization of HeapManager）

本文基于现有嵌入式操作系统动态内存管理机制的原理，研究和分析了多个微型嵌入式操作系统内存管理的优缺点，以多平台通用、高效率、简单易用为目标，实现了一种新的动态内存管理机制方法HeapManager。

2.1 数据结构

HeapManager将动态内存区连续内存空间视为一块空闲分块，并为每一块空闲块建立一个链表节点以记录该空闲块信息，将所有空闲块链表节点组成一个空闲分区链表，其链表节点的数据结构类型如下：

heapMalloc（）会检查自身是否第一次被调用。在用户首次调用heapMalloc（）时，heapMalloc（）会执行一次初始化堆分区建立一个空闲分区链表。初始化的过程包括：建立整个空闲分区链表的起始节点和终止节点；将初始节点的下一个分区节点指向系统动态内存堆首地址，初始节点空闲分区大小定为0；将终止节点的下一个分区节点指向NULL，终止节点空闲分区大小定为整个系统动态内存堆长度；建立第一个空闲分区节点并存放于系统动态内存堆顶部，将该节点的下一个分区节点指向终止节点，定义该节点空闲分区大小为整个系统动态内存堆总长度减去节点所占空间。

heapMalloc（）被调用后会对参数wantedSize进行检测判断，如果wantedSize不大于系统所剩余空闲空间，则从heapStart指向的空闲空间链表开始对比每个空闲分区的大小是否大于所申请长度，直到找到第一个合适的空闲分区或者heapEnd结束，再根据除去用户所申请空间的空闲分区大小决定是否重新创建一个新空闲分区节点，最后更新空闲分区链表并返回所申请内存（保留顶部节点信息）的首地址。

unsigned char heapFree（void*freeBlock）在用户程序使用完所申请内存空间后释放该动态内存时被调用，用户调用时须传递参数freeBlock指向所释放内存的首地址，函数结束后将返回执行结果信息（没有错误返回0）。

heapFree（）被调用后会根据freeBlock指向的地址得到回收空闲分区的空闲分区节点并进行检测，比较freeBlock所指向的位置是否包含于动态内存区，如果不是则返回错误，再判断该空闲分区节点结构是否损坏，然后从空闲分区链表heapStart所指向的第一个空闲分区开始地址对比，找到该内存块合适的回收位置，进行回收操作，在HeapManager中会根据回收空间所在位置的不同情况作不同的回收处理。

HeapSizeType heapGetFreeSize（void）函数被调用时返回HeapManager中所剩空闲分区的总大小，该大小为绝对空闲区，即除去空闲分区节点所占用后剩下的空间。如果在第一次调用heapMalloc（）函数前调用heapGetFreeSize（）则返回用户所设置的总动分区大小configTotalHeapSize。

2.3 设置与使用

HeapManager的定位是一个简单易用的微型管理机制，所以在使用HeapManager时需要设置的参数仅有两个，分别是_HEAP_MANAGER_ON_和configTotalHeapSize。

_HEAP_MANAGER_ON_用于定义是否启用HeapManager。我们将HeapManager的两个文件（C文件和H文件）添加到项目工程中，如果将_HEAP_MANAGER_ON_设置为0则编译器在编译时不会产生HeapManager代码，也即关闭HeapManager。configTotalHeapSize设置系统用于动态内存分区的总大小。开发人员在使用HeapManager之前须根据硬件资源为HeapManager划分一块configTotalHeapSize大小的内存区作为动态内存分区，该值必须大于一个空闲分区节点的长度（空闲分区节点长度=平台数据指针所占空间+HeapSizeType实际表示空间）。HeapManager会在用户程序申请或释放动态内存空间时进行各种检测，如果出现错误则将该错误的信息反馈给用户程序，开发人员可根据HeapManager返回的错误信息在程序中做出相应措施。

HeapManager主要以低成本嵌入式产品为应用对象，具有以下特点：简单易用，使用HeapManager只需划分一块大小合适的内存空间即可，只有三个应用接口函数，全部源代码不到200行（含注释）；动态内存申请采用可变分区管理的首次适应算法，空闲分区按照地址从低到高排列，每次分配从空闲分区链表的链首开始查找满足要求的分区；内存回收时对回收的内存块进行严格的合法性检查，避免了整个动态内存分区的混乱或崩溃，保证了系统稳定性和可靠性；具备将邻近空闲块合并成一个大空闲块的功能，有利于动态内存的高效利用，有效避免了内存碎片的产生；HeapManager是一个完全独立的内存管理机制，它可以不依赖于任何操作系统，独立添加到工程中直接调用接口函数，也可以通过修改源代码代替小型操作系统的内存管理机制；实现跨平台的移植，HeapManager在不同硬件平台中使用其空闲链表节点所占的存储空间会根据硬件平台自行做出调整。

3 HeapManager的测试（Test of HeapManager）

本文以某一应用场景为例对HeapManager进行测试，假设产品中共运行10个死循环线程，每个线程在循环运行过程中将向动态内存区申请一块随机长度（1—10个内存单位）的存储空间，使用完后释放，另外每个线程每次运行一个循环所用时间也是随机的。微处理器或微控制器在同一时刻只能运行一条指令，即同一时刻只有一个线程在运行，且HeapManager可以在脱离操作系统的基础上使用。

分析应用情景后设计的测试程序如下：定义一个长度为10的指针数组用于存放10个线程所申请的内存块首地址；从随机函数中取得一个0—9的随机数，表示现在正在运行的其中一个线程；检测对应随机数的指针数组元素是否已存在申请的内存块首地址，不存在（值为NULL）则表示该线程还没申请动态内存空间，执行步骤4，否则执行步骤5；再次从随机函数中取得一个1—10的随机数作为长度参数，并通过HeapManager提供的接口函数向动态内存区申请动态内存块，将得到的内存块首地址存放于对应线程的指针数组中，回步骤2；释放指针数组下标为所得随机数的元素所对应的内存块，并将该元素值赋为NULL，回步骤2。

测试结果表明，HeapManager能实现动态内存管理机制的所有基本操作，可根据用户程序参数动态分配合适的空间，具备将相邻空闲块合并功能，并且，当空闲分区节点结构损坏时，HeapManager可以做出相对应的处理保持系统稳定运行。

参考文献（References）

[1] Masmano M，Ripoll I，Real J.Implementation of a Constant-time Dynamic Storage Allocator[J].Software：Practice and Experience，2007，38（10）：995-1026.

[2] 常铁原.μC/OSII内存管理技术的研究[J].计算机工程，2007，33（9）：82-83.

[3] Labrosse J J.邵贝贝，译.嵌入式实时操作系统?C/OS-II（第2版）[M].北京：北京航空航天大学出版社，2005.

[4] 刘滨.嵌入式操作系统FreeRTOS的原理与实现[J].单片机与嵌入式应用，2005（7）：8-11.

[5] Richard Barry.USING THE FREERTOS REAL TIME KERNEL[M].2009.