嵌入式操作系统MQX内存管理机制分析与改进

文　瑾　王宜怀　柏　祥

1(昆明学院信息技术学院　云南 昆明 650214)2(苏州大学计算机科学与技术学院　江苏 苏州 215006)



嵌入式操作系统MQX内存管理机制分析与改进

文瑾1,2王宜怀2*柏祥2

1(昆明学院信息技术学院云南 昆明 650214)2(苏州大学计算机科学与技术学院江苏 苏州 215006)

摘要针对嵌入式实时操作系统MQX(Message Queue eXecutive)中内存管理不够灵活等问题，提出一种基于哈希索引表和最先匹配策略相结合的自适应内存管理算法，针对不同大小的内存采用不同的内存管理策略。对于小块内存采用哈希索引表组织，实现内存分区池的常数级定位，并且通过双向链表将分区池紧密联系提高内存申请的鲁棒性；对于大块内存采用最先适应策略，减少内部碎片的产生，提高内存的利用率。实验结果表明，改进后的算法在保证MQX原有内存管理算法较高实时性的同时，提高了内存申请的命中率以及内存管理的可靠性。

关键词实时操作系统MQX内存管理哈希索引表最先适应策略

0引言

MQX是飞思卡尔半导体公司在2009年推出的一款其内核精简、源代码开放、可裁剪性较强的嵌入式实时操作系统RTOS(Real Time Operating System)[1]，并将MQX移植到其公司推出的CodeFire、Kinetis等系列微控制器中。MQX从1989年诞生至今，已经走过了二十多年的发展历程。由于支持多任务调度、优先级抢占、快速中断响应[2]等特点，被广泛应用于医疗电子、工业控制等领域。

在嵌入式实时操作系统中，内存资源是十分宝贵的，因此必须提供有效的内存管理机制对内存资源进行合理高效的管理，才能提高内存资源的利用率。内存分配的方法主要有两种：静态分配和动态分配，考虑到静态分配相对简单，灵活性相对于动态分配较差，动态分配因其按需分配的灵活性使得众多学者对其进行深入研究[3,4]，在现在程序中也被广泛使用[5]。嵌入式实时操作系统对内存管理的要求主要有以下几点：

(1) 稳定性，任务的内存申请请求应当尽可能被满足[6]；

(2) 实时性，内存的申请或者释放都应该保持在确定的时间范围之内；

(3) 安全性[7]，内存应该由申请它的任务负责，不能对不是由自己申请的内存进行释放或者其他操作。

若内存管理存在不足则会导致大量内存碎片的产生，内存碎片分为内部碎片和外部碎片[8]。内部碎片是指已经被分配出去(明确属于某个任务)却不能被利用的内存空间，直到此块内存被该任务释放系统才可能重新利用此块内存空间；外部碎片指的是还没有被分配出去(不属于任何任务)，但由于太小无法分配给申请内存空间的新任务的内存空闲区域。所以在内存管理中需要对内存碎片进行控制，使得其对内存申请和释放的干扰降到最低。

在对MQX固定大小的内存管理机制进行剖析的基础上，针对其内存分配算法存在的问题，提出一种基于哈希索引表和最先匹配策略相结合的自适应内存管理算法，针对不同大小的内存采用不同的内存管理策略。对于小块内存采用哈希索引表组织，实现内存分区池的常数级定位，并且通过双向链表将分区池紧密联系提高内存申请的鲁棒性；对于大块内存采用最先适应策略，减少内部碎片的产生，提高内存的利用率，并以飞思卡尔公司基于ARM Cortex-M4内核的32位微控制器MK60N512 VMD100(简称K60)为硬件平台，对改进后算法的有效性进行验证。

1MQX内存管理机制分析

图1　系统架构图

MQX从系统架构上分为三层：用户层、内核层以及物理层。以内存申请为例，任务调用用户层接口_partition_alloc申请内存块，_partition_alloc再其内部调用内核层接口_partition_alloc_internal从空闲内存块链表中申请空闲内存，空闲内存块链表顺序不一定按照内存的物理地址顺序。程序架构如图1所示。

MQX固定大小的内存管理算法与μC/OS-II类似[10]，通过_partition_create_at函数来创建分区，该函数传入三个参数：分区的起始地址、分区的大小以及分区中每个内存块的大小。MQX中地址按照16字节进行对齐，将函数传入地址进行16字节对齐之后作为内存分区的起始地址。因为内存块大小固定，所以只需通过计算即可将整块分区划分成块。在划分成块的同时使用内存块控制信息中的NEXT_BLOCK_PTR指针将所有的内存块连接起来构成空闲内存块链表。因系统中可能存在多个分区，还需将分区加入到分区链表中，分区链表在内核数据区中进行维护，内核数据区负责维护MQX在运行过程中相关信息。分区在创建完成之后其可以分配的内存块大小。

固定大小的内存分配管理方式在进行内存块分配时调用_partition_alloc函数。首先检查分区中是否有可用的空闲内存块，没有可用内存块则返回错误，若存在可用内存块，则获取分区控制信息中的空闲内存块链表首指针FREE_LIST_PTR将空闲内存块链表中第一个空闲内存块的地址返回。再将FREE_LIST_PTR更新为内存块控制信息中指向的下一个空闲内存块，内存管理的实时性要求内存申请操作应当在确定的时间范围之内，即申请内存的最差时间复杂度也应该是确定的。固定大小的内存块管理方式由其内存分配特点可知其分配过程时间复杂度为O(1)，具有较好的实时性。

固定大小内存块的释放与申请过程相反，在释放时调用_partition_free函数。首先需验证当前任务是否具有释放指定内存的资格，即通过比较内存块控制信息中的TASK_ID与通过内核数据区获取的当前的任务ID是否一致判断该内存块是否属于当前任务。如果不属于再判断该内存是否是系统内存块，两者都不相等意味着当前任务没有权限释放此内存块，通过此机制保证了内存管理的安全性。接着将需要释放的内存块控制信息更新，再将它插入到空闲链表FREE_LIST_PTR的头部。然后将分区控制信息中空闲内存块链表首指针更新为当前释放的内存块地址达到释放此内存块的目的。由此过程可知固定大小的内存块管理方式中内存块释放时间复杂度也为O(1)。

2改进算法的提出及实现

MQX固定大小的内存块管理方案内存块分配释放速度较快，但是存在以下不足：

(1) 分区大小的确定

任务在创建分区时根据自己需求的大小创建内存池，定义其中内存块的大小以及内存块的数目。当创建完内存分区池之后这些参数也就固定下来。如果任务需要再次申请内存时，假设任务需要求的是与上次创建分区中大小相同的内存块，若前一次创建分区时内存块数目设置没有存在冗余，需要重新调用_partition_create_at函数再次创建分区；若前一次创建分区时将内存块数目设置较大，又会造成内存的浪费。

(2) 分区之间相对孤立

当任务在申请内存块时只会在指定分区申请空闲内存块。虽然各个内存池被内存分区池控制信息中的成员NEXT和PREV连接起来，但是在进行内存的申请释放等操作时各个分区之间是没有联系的。当任务的内存块申请得不到满足时，若该系统对于内存管理的稳定性要求较高，可能会引起灾难性的后果。

(3) 大块内存管理效率低

固定大小的内存管理策略对于小块内存的申请比较合适，但是由于嵌入式系统中可用内存是有限的。对于大块内存创建内存分区池受到限制，会导致内存利用率较低，申请的内存块越大，利用率越低，因此针对大块内存的管理需要采用另外的解决方案。

为了解决上述问题，对不同大小的内存块请求采用不同的策略，内存块大小以1 KB为界限，小块内存代表小于等于1 KB的内存块，大块内存代表大于1 KB的内存块。

2.1小块内存管理策略

对原有固定大小的内存管理算法进行改进，采用哈希索引表对内存分区池进行索引。用户在创建调用_partition_create_at创建分区时首先创建8个区存，每个分区的块大小分别定为8 B、16 B、32 B依次增加至1 KB。每个内存池中内存块的数目从512按2的幂次递减，8个内存分区池共占内存32 KB，初始化之后的分区池结构如图2所示。

图2　分区池结构图

8个内存分区池的首地址存放在指针数组PARTPOOL_STRUCT_PTR MemPool[8]中。当任务需要申请内存时，首先按照需要申请的内存块大小通过散列函数定位到从哪个分区进行申请，散列函数MemPoolLocation主要步骤伪代码如下所示：

MemPoolLocation (size)

1index <- 31

2while(!(size & (1 << index)) && (index >= 0))

3index <- index-1

4index <- index+1-3

5return index

通过计算得出左数第一个1的位置，从而获得所需内存块数量级。接着得到对应数量级内存块所在分区的首地址在指针数组MemPool中的位置。使用该方法可以在O(1)时间内确定从哪个内存分区池中申请内存块。

在分配内存块时也对MQX原有的固定大小的内存块分配算法做了改进。当发现当前分区中可用内存块数目为零时便通过分区控制信息中NEXT成员获取下一个分区的地址，从下一个内存分区池进行申请内存块。由于NEXT指向的内存分区池中内存块的大小是当前内存分区池中内存块大小的2倍，内存块大小必定大于当前分区，避免了在某些情况下可能的内存泄露问题。对于所引起的内部碎片问题由于针对的小块内存的申请，产生内部碎片较小。改进的小块内存管理策略有以下优点：

(1) 分区大小固定。任务不需要多次调用内存池创建函数，以增加初始化分区时间为代价。创建完成后任务可以根据自己需求申请对应内存块，减少了小块内存的平均申请时间。

(2) 增强各个内存分区池之间联系。当前内存分区池不存在可用内存块时从下一个内存分区池申请空间，提高了分配策略的灵活性，以较小的内碎片为代价，换来系统的稳定高效运行。

(3) 通过构造哈希表以及散列函数实现根据申请内存块大小快速定位到对应分区，保持了MQX原有固定大小内存分配的高实时性。

2.2大块内存管理策略

固定大小的内存管理策略对于小块内存是合适的，但是针对大块内存则存在着明显的不足，会造成内存碎片较大，利用率较低。虽然频繁对内存进行划分会对内存分配时间产生影响，但在嵌入式系统中大块内存的申请并不是很频繁。因此权衡利弊后针对大块内存的管理采用可变大小的内存分配策略。

(1) 内存池的创建

在MQX启动函数_mqx中调用_mem_init函数初始化内存池，申请一大块连续内存作为内存池。创建内存池时会为每个内存池创建内存池控制信息结构体MEM_POOL_STRUCT，其结构如下：

typedef volatile struct mem_pool_struct

{

void *POOL_ALLOC_START_PTR;

//内存池的起始地址

void *POOL_ALLOC_END_PTR;

//内存池的结束地址

void *POOL_FREE_LIST_PTR;

//空闲内存块链表

void *POOL_ALLOC_PTR;

//申请内存块时用于遍历的指针

void *POOL_FREE_PTR;

//释放内存块时用于遍历的指针

} MEM_POOL_STRUCT, * MEM_POOL_STRUCT_PTR;

内存池中的空闲链表使用单向链表进行管理，在内存池控制信息结构体中成员POOL_FREE_LIST_PTR指向这个空闲链表的第一个节点。在每个空闲内存块的内存块控制信息结构体中成员NEXTBLOCK指向下一个空闲内存块的地址。

(2) 可变大小内存申请

可变大小的内存块申请策略采用的是最先适应算法(First Fit)。空闲内存块按照内存地址顺序递增排列，申请内存时要知道需要申请空闲内存块的大小，该内存块所属任务及所属内存池。从POOL_FREE_LIST_PTR开始寻找合适大小的内存块，合适大小指的就是找到的第一块内存大小大于等于需求内存的内存块。如果当前找到的内存块大于所需要的内存大小时，就将该块内存分为2部分，一部分供申请的空间的任务使用，被标记为已使用内存块，剩下的还是作为空闲内存块链接到空闲链表中。如果找到的空闲块是在POOL_FREE_LIST_PTR前面，那么需要重新定义POOL_FREE_LIST_PTR。采用这种方案虽然快，但是这会导致系统在后面不能分配出大块的内存供其他任务使用。内存申请流程如图3所示。

图3　内存申请流程图

(3) 可变大小内存释放

可变大小内存释放的过程比申请过程复杂一些，内存块释放流程图如图4所示。在释放时，首先界限内存保护检查，也就是查看该内存是否属于当前任务。接着根据该内存块的地址来决定插入空闲链表的具体位置。在插入之前还需要判断该内存块前后是否有相邻的空闲内存块，按照“先后再前”的原则进行判断是否需要合并，如果需要合并，则对内存块控制信息进行更新；如果不需要合并则只需要将该块插入空闲链表中free_list_ptr之后。

图4　内存释放流程图

(4) 实时性问题

在申请和释放内存块的操作中是禁止中断的，但是在申请和释放内存块的操作中都需要对空闲链表进行遍历。若存在较多空闲内存块，遍历空闲链表的时间开销就显得比较可观了。为了保证MQX的高实时性，避免这种情况的发生，在申请内存块时，在遍历空闲链表的循环中，在每查找完一个空闲块之后就开中断查看是否有高优先级的任务需要切换。使用内存池控制信息结构体中的成员变量POOL_ALLOC_PTR保存当前查找位置，切换回来之后将POOL_ALLOC_PTR里面的值重新加载回去继续执行。从高优先级任务切换回低优先级任务时恢复遍历位置时重新从空闲链表头开始。在释放内存块时操作类似，使用内存池控制信息结构体中的成员变量POOL_FREE_PTR来存储当前遍历位置，通过上述方法保证了MQX的高实时性。

3测试结果与分析

在嵌入式系统当中，大部分内存申请都是小块内存的申请，所以对于小块内存更具有实时性可靠性的要求。大块内存的分配释放时间取决于空闲链表的长度，相比于固定内存管理较长，但是其内存利用率较高，而且在嵌入式系统中大块内存的申请较少，因此可以满足系统的需求。

实验针对小块内存的管理策略，将改进的固定大小内存分管理算法与MQX原有固定大小内存管理算法进行比较，应用于苏州大学飞思卡尔嵌入式中心设计的SD-FSL-K60-C评估板进行小块内存申请对比试验。该评估板以飞思卡尔公司基于ARM Cortex-M4内核的32位微控制器K60[11]作为主控芯片，CPU运行主频高达100 MHz，拥有512 KB的Flash和128 KB的RAM。

根据改进前后内存管理算进行了400次测试，每次测试分别进行完全相同的N次(N<1000)内存申请及对应释放操作。操作顺序随机，每次申请的内存块大小是64 B、128 B、256 B、512 B和1 KB中随机一种。

图5(a)是改进后内存管理算法的时间消耗，图5(b)是MQX原内存管理算法的时间消耗。从图5可以看出改进后内存管理算法的内存块申请和释放所消耗时间保持平稳，保持常数级变化，相比于原有的内存管理算法并没有过多的增加。

图5　算法改进前后申请和释放N次内存的时间消耗对比

表1是测试过程中统计每种类型的内存块申请次数和失败次数，得到各种类型的内存块申请命中率进行对比。

表1　算法改进前后内存申请命中率对比

内存申请的快速性与分配时间呈负相关，可靠性与内存申请命中率是正相关的。由表1中的数据可以看出，在可用内存完全一致的情况下，相比MQX原有的固定大小内存管理算法，改进后的算法在内存块分配及释放的时间上与MQX原有内存管理算法并没有显著的增加。在保证了内存申请和释放实时性的同时，使得内存申请命中率得到了很大的提高，提高了内存分配的可靠性。

4结语

本文对MQX固定大小内存管理机制进行分析。在其基础之上提出一种基于哈希索引表和最先匹配策略相结合的自适应内存管理算法，并以ARM Cortex-M4内核的32位微控制器K60为硬件平台，对改进后的算法进行验证。实验表明，改进算法在保证原有内存分配算法的高效性的同时，提高了内存块申请的命中率。因此，改进后的算法在小块内存申请较为频繁的嵌入式系统中可以得到更好的应用。

参考文献

[1] Freescale MQX real-time operating system user’s guide Rev.3[EB/OL].http://cache.freescale.com/files/32bit/doc/user_guide/MQXUG.pdf.

[2] 石晶,王宜怀,苏勇,等.基于ARM Cortex-M4的MQX中断机制分析与中断程序框架设计[J].计算机科学,2013,40(6):12-19.

[3] Dominguez A,Udayakumaran S Barua.Heap data allocation to scratch-pad memory in embedded systems[J].Journal of Embedded Computing,2005,1(4):521-540.

[4] Risco-Martin,Jose L,David Atienza,et al.A parallel evolutionary algorithm to optimize dynamic memory managers in embedded systems[J].Parallel Computing,2010,36(10):572-590.

[5] 王振江,武成岗,张兆庆.提高堆数据局部性的动态池分配技术[J].计算机学报,2011,34(4):665-675.

[6] 孙晓辉,王劲林,陈晓.实时系统中的动态内存分配算法[J].计算机工程,2008,34(8):80-81.

[7] 王丽杰,熊光泽,罗蕾.嵌入式RTOS安全保护机制的研究与实现[J].电子科技大学学报,2006,34(5):650-653.

[8] 朱沿旭,尹俊文.一种减少碎片的伙伴算法的改进[J].计算机工程与科学,2008,28(A2):175-176.

[9] Cormen T H,Leiserson C E Rivest,et al.Introduction to algorithms[M].Cambridge:MIT press,2001.

[10] 常铁原,孙学儒.TBS算法在μC/OS-Ⅱ内存管理中的应用[J].计算机应用与软件,2012,29(9):261-264.

[11] Freescale.K60 Sub-Family Reference Manual Rev.6[EB/OL].http://cache.freescale.com/files/32 bit/doc/ref_manual/K60P144M 100SF2V2RM.pdf.

收稿日期：2015-01-28。国家自然科学基金项目(60871086)；云南省应用基础研究计划项目(2011FZ176)；昆明市物联网及泛在工程技术中心开放课题(KMIOTKFKT2015001)。文瑾，副教授，主研领域：嵌入式系统，物联网技术。王宜怀，教授。柏祥，硕士生。

中图分类号TP391

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.07.055

ANALYSIS AND IMPROVEMENT OF MEMORY MANAGEMENT MECHANISM IN EMBEDDED OPERATING SYSTEM MQX

Wen Jin1,2Wang Yihuai2*Bai Xiang2

1(SchoolofInformationTechnology,KunmingUniversity,Kunming650214,Yunnan,China)2(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)

AbstractAiming at the inflexibility of memory management in embedded real-time operating system MQX(Message Queue eXecutive), we propose a self-adaptive memory management algorithm which is based on the combination of hash index table and first-fit strategy, in it different memory management strategies will be applied for different memory size. For memories in small block the hash index table will be adopted to organise them so as to realise constant level positioning of the memory partition pools, and through doubly linked list the partition pools are closely connected to improve the robustness of memory application; For memories in big block the first-fit strategy is adopted to decrease the occurrence of internal fragments and to improve the utilisation of memory. Experimental results show that the improved algorithm improves the hit rate for memory application and the reliability of memory management while maintaining the high real-time property of MQX’s original memory management algorithm.

KeywordsReal-time operating systemMQXMemory managementHash index tableFirst-fit strategy