VxWorks实时操作系统内存分配算法优化

中国科学院软件研究所 李彦峰 李丽颖山东农村信用社联合社 韩广志金陵科技学院 徐尚喻



VxWorks实时操作系统内存分配算法优化

中国科学院软件研究所 李彦峰 李丽颖
山东农村信用社联合社 韩广志
金陵科技学院 徐尚喻

【摘要】通过研究VxWorks实时系统内存分配算法，发现VxWorks的内存管理算法的局限性。本文提出通过在VxWorks实时操作系统原有的内存管理功能上添加功能，用于实现固定大小内存分配。新增加的功能利用位图管理内存，通过降低内存管理信息占整个内存块的比率提高内存使用效率，通过将固定大小的内存片合并为一组进行整体的内存分配来降低内存碎片；同时由于减少了内存碎片，从而间接提高内存的分配速度。

【关键词】内存分配；位图管理；内存碎片；分配效率

0　引言

VxWorks内存管理是基于Flat模式实现的，管理框架分为分区（Partition）、Pool（池）、Block（块）。系统中的具体实现为分区结构体memSysPartition，内存中的空闲内存通过这个结构体的成员变量freelist链接起来。VxWorks原有的内存分配实现相对而言比较简单——所有任务的内存分配请求调用malloc函数从系统内存分区memSysPartition中获得。内存请求分配时利用最先适应算法从系统分区结构中来满足内存分配请求，而内存回收时则会将相邻地址的空闲内存给聚合成一个更大的空闲内存。

VxWorks的以上内存分配设计没有考虑小内存分配请求的优化，很容易导致下列问题：第一，当系统中存在大量的小内存分配请求时，就可能使得内存中出现较多的内存碎片；导致系统中存在可用的内存却因为大小不能满足而出现内存分配失败的结果，从而影响系统的稳定性。第二，freelist链表中的小内存过多时，整个链表长度会很长，从而使得链表的搜索时间效率降低。第三，整个系统中，一个内存块（BLOCK）就有一个管理信息，小内存分配会出现管理信息站用大量内存空闲的情况。第四，由于所有的内存分配都要竞争系统内存分区memSysPartition的保护锁，导致系统的运行变慢，降低系统的效率。

1　固定大小内存分配

基于上面的考虑，我们的改进通过在现有的VxWorks操作系统的内存分配上面加上一层：将现有的内存管理层次从分区（PARTITION）、池（POOL）、块（BLOCK）扩展到分区（PARTITION）、池（POOL）、块（BLOCK）、内存片(MEMORY_SLICE)。也就是将小内存的内存请求都转化为大小为一个内存片（MEMORY_SLICE）的请求，同时将这些固定大小的内存片组合成一个内存序列。内存序列增加一些额外的内存管理信息头部就组成一个内存块（BLOCK_HDR）原来每个小的内存片都需要一个BLOCK_HDR的管理信息，现在多个内存片共享一个BLOCK_HDR的管理信息；而BLOCK_HDR内部的内存片序列中的内存片MEMORY_SLICE则通过较小的内部管理信息进行管理，从而达到固定大小的内存块管理信息共享的目的；同时由于固定大小的内存以一组内存片为单位进行分配和回收降低了系统的内存碎片，提高了系统内存使用的效率，同时增强了系统的稳定性。

2　优化内存分配算法

算法的主要实现思想是，给小内存块定义一个下界N——所有小于等于N的内存分配请求都会调整到大小为N的内存分配，而多个这样的大小为N的内存片MEMORY_SLICE组成一个内存片序列MEMORY_ARRAY。为了减少额外的内存管理信息，利用位图管理思想来管理固定大小的内存，即每一个内存片MEMORY_SLICE和一个内存管理位图的位对应；当位图的中的某一位为1的时候表明内存被占用，反之则未被占用。同时，为了方便位图的运算，每一个位图包含32个位。这样位图的操作可以转换为C语言中的整形数的位操作，同时32个位对应内存中的4个字节，而VxWorks以4字节为单位进行对齐，这样的设定可以减少内存中不必要的对齐操作。另外，由于BLOCK_HDR不是最底层的内存管理单位，所以还需要额外的链表对这些BLOCK_HDR进行管理，以方便内存分配时找到包含内存片序列的BLOCK_HDR。因此，扩展的内存管理还需要一个额外的链表节点DL_NODE用于将所有的包含内存片序列MEMORY_ARRAY的BLOCK_HDR链接到系统全局链表中。经过调整之后，每一个包含32个内存片的内存片序列MEMORY_ARRAY和一个DL_NODE以及一个32位的位图BITMAP组成VxWorks的一个基本的内存块BLOCK_HDR。这些包含内存片序列的内存块BLOCK_HDR通过DL_NODE链接到链表memlist中。

3　具体实现

根据上面的实现思想，在VxWorks操作系统中实现小内存转化为固定大小的小内存的管理，需要增加一个全局的DL_LIST变量memlist，通过memlist变量将包含内存片序列的BLOCK_HDR链接起来；同时为了实现VxWorks系统下面的多任务访问还需要额外的SEMPHORE信号量来辅助实现memlist的互斥访问，在代码当中的定义：SEMAPHORE memsm； DL_LIST memlist;

当内存分配请求大于sizeof（MEMORY_SLICE）时，直接调用malloc函数实现内存的分配而无需经过我们的内存分配；反之，则首先将内存分配请求大小调整到大小为sizeof（MEMORY_SLICE），然后遍历memlist链表，直到找到可用的BLOCK_HDR或者达到memlist链表表尾。

增加上诉定义来简化理解，其中CusMan用于管理内存片序列MEMORY_ARRAY，bitmap用于内存的位图管理，node用于连接到全局的链表memlist中。遍历的过程中，通过memlist得到链表节点node，将node指针强制转化为CusMan类型的指针cusmanptr。通过CusMan指针cusmanptr可以得到管理内存片序列的内存管理位图bitmap，将32位的bitmap看作一个整形数。利用这个整形数与0xFFFFFFFF进行比较，如果小于0xFFFFFFFF则表明在当前的内存块节点包含可用的空闲内存，则中止遍历。否则，直到到达链表表尾并终止遍历过程。如果遍历到达链表尾终止，则需要重新调用malloc函数分配一个大小为sizeof（MEM_ARRAY）+sizeof（CusMan）的内存块BLOCK_HDR。将这个内存块中的与内存序列对应的内存管理信息CusMan中的bitmap的第一个bit设置为1，同时返回内存序列中的第一个MEM_SLICE，并利用CusMan中的链表节点DL_NODE将新分配的内存块BLOCK_HDR挂载到memlist链表中。

当出现有链表节点node得到的CusMan的成员变量bitmap不全为1而中止遍历时，则表明memlist中该链表节点可以满足内存分配请求。则转入到对包含该节点的内存块BLOCK_HDR的处理过程，首先通过节点node找到CusMan指针，然后通过CusMan指针找到成员变量bitmap。通过位测试操作，找到bitmap中第一个为0的bit位，将该bit位设置为1，并且返回与这个bit对应的MEM_SLICE。

由于分配的时候出现的调整，所以在释放的时候也需要相应的改变。在内存释放时，取下memlist链表当中的内存块节点DL_NODE，通过DL_NODE可以得到内存序列MEMORY_ARRAY。根据比较需要回收的内存地址freeptr和内存序列所包含的地址范围来判断freeptr是否落在包含该节点的内存块BLOCK_HDR当中。如果找到freeptr所在的内存块BLOCK_HDR，则通过BLOCK_HDR可以找到内存片序列MEMORY_ARRAY。由于MEMORY_ARRAY中的内存片是固定大小的，所以可以利用freeptr减去内存片序列MEMORY_ARRAY的首地址再除以每一个内存片的大小N得到freeptr在内存片序列MEMORY_ARRAY中的索引，通过这个索引找到内存管理信息CusMan中的bitmap成员变量，将与索引对应的bit设置为0即可。然后测试该CusMan中的bitmap中的bit位是否全部为0。如果全部为0，则表明节点node所在的整个内存块BLOCK_HDR都是空闲的，因此调用系统的内存回收函数free将整个内存块回收。

如果遍历memlist并没有找到freeptr所在的内存块，则表明freeptr所保存的内存是利用全局的malloc函数直接进行分配的。则直接利用系统的内存回收函数free进行回收即可。

4　总结

通过在系统内存管理上面增加新的内存管理层来管理固定大小的内存分配，可以显著降低系统的内存碎片。同时，系统中的全局内存链表长度变短，使得内存分配过程中搜索时间复杂度降低。改进之后的内存管理系统利用了CPU擅长处理的数字和逻辑计算，所以在新增加的内存分配和回收的过程当中的内存管理位图的测试处理不会消耗太多时间。同时，由于整个系统当中小内存块的数目降低，使得memSysPartition的成员变量freelist的长度降低了一个数量级，从而系统分配的遍历的效率会大大升高。而内存管理信息由原来的32个BLOCK_HDR降低为一个BLOCK_HDR加1个32位的内存管理位图和一个DL_NODE，显著的增加有效内存的比例。同时内存碎片的减少会提高系统的稳定性。

参考文献

[1]陈京,王晓冬,黄标,丁家昕.一种误差可控的地图边界线的等距线计算方法[J].计算机工程与应用.

[2]王鹏,邱天爽,李景春,谭海峰.基于四阶累积量的近场源多参数联合估计[J].大连理工大学学报,2015(06).

[3]方箭,鲁俊,朱颖,李芃芃.全球数字红利频谱释放现状及展望[J].电讯技术,2015(12).

李彦峰（1982-），山东德州人，硕士研究生，中级职称，研究方向：软件工程嵌入式系统。

作者简介：