Buddy算法的μC/OSII高可靠内存管理方案

3Buddy算法简介

Buddy算法是内存管理的经典算法，目的是为了解决内存的外碎片问题，以及提高内存管理的可靠性。Buddy算法在Linux内核内存管理模块得到成功的应用。

如图2 所示，Buddy算法将所有空闲页框分组为10个块链表，每个块链表的每个块元素分别包含1、2、4、8、16、32、64、128、256、512个连续的页框，每个块的第一个页框的物理地址是该块大小的整数倍。例如，大小为4个页框的块，其起始地址是4×212（一个页框的大小为4K,4个页框的大小为4×4K,1K=1024=210，4K=212）的倍数。

图2 Buddy算法简介

假设要请求一个128个页框的块，算法先检查128个页框的链表是否有空闲块，如果没有则查256个页框的链表，有则将256个页框的块分裂为两份，一份使用，一份插入128个页框的链表。如果还没有，就查512个页框的链表，有的话就分裂为128、128、256，一个128使用，剩余两个插入对应链表。如果在512还没查到，则返回出错信号。用这种方法来分配页框，由Linux内核的稳定性可知其可靠性。

回收过程相反，内核试图把大小为b的空闲伙伴合并为一个大小为2b的单独块，满足以下条件的两个块称为伙伴： 两个块具有相同的大小，记做b；它们的物理地址是连续的；第一个块的第一个页框的物理地址是2b×212的倍数。该算法迭代，如果成功合并所释放的块，会试图合并2b的块来形成更大的块。在本方案中，只要满足前两个条件就足够了。

4 μC/OSII内存管理改进方案

4.1 改进方案思路

① 修改内存控制块的结构OS_MEM，去掉OS_MemAddr、OS_MemNFree成员，添加一个内存块链表尾指针OSMemBlkTail，所以OS_MEM结构还含有4个成员：OSMemFreeLiST、OSMemBlkSize、OSMemNBlks、OSMemBlkTail。改进后的内存控制块结构如图3所示。

图3 改进方案中的内存管理组织结构

② 首先初始化一个内存控制块结构数组struct OS_MEM []，其下标是内存块规模的对数，引入结构数组的目的是在申请内存块时能够快速定位，起到索引的作用。而内存块的实际大小为内存块规模与内存块粒度的乘积。然后将内存块按内存块规模从小到大挂到不同结构数组指向的链表上，并且保证初始化后同一链表上的内存块地址不连续。在申请内存块通过内存控制结构数组的下标快速定位到内存块链表，查看内存块控制结构字段中OSMemFreeList成员指针是否为空。若不为空，则从表头取一个内存块，并返回该内存块的地址；否则向后搜索数组，看是否有空闲内存块。若有则将该内存块一分为二，低地址的那块分配给申请者，高地址的那块则挂到前一个结构数组的表头，以备其他申请者申请。同样，释放内存块时也是通过结构数组快速定位到具体结构数组，然后检查该结构数组内存块链表中是否有和要释放的内存块地址连续的内存块。若有，则合并两内存块并挂到后一个结构数组，并检查地址是否连续，直至没有为止；若无，则将该内存块挂到该内存块链表的表尾。改进后的内存管理组织结构如图3所示。

4.2 具体改进措施

① 改进函数OS_MemInit（void）。此函数原来是初始化空闲内存控制块链表，改进后此函数用于初始化OS_MEM结构数组即可，根据OS_CFG.H文件中宏OS_MAX_MEM_PART来决定数组元素个数。

② 改进函数OSMemCreate（void *addr, INT32U nblks, INT32U granularity , INT8U *err）。根据Buddy的规则横向创建内存块，每创建一个内存块就链到相应的结构体数组上，如图3的Create Direction所示，这样能保证每个结构数组上的相同大小的内存块地址不连续，从而避免了所有内存块合并的现象。创建出来的内存块组织结构如图3所示。

③ 改进函数OSMemGet（INT32U size, INT32U granularity, INT8U *err）。因为结构体数组名是在OS_CFG.H文件中宏定义的，所以本函数的参数只包括需求的内存块大小及内存块粒度即可。用内存块大小除以内存块粒度，首先判断所得值是否为2的幂次，若是直接取对数即得结构数组的下标；若不是则取对数后向上取整。得到指定数组元素后若有内存块，取下一内存块然后指针下移，若无内存块则继续搜索下一个结构数组。若该数组有空闲内存块则取将其平分为两块，一块分配出去，一块挂到前面结构数组链表。这样一直搜索到最后一个结构数组，若一直无内存块，则报错返回。

④ 改进函数OSMemPut（INT32U size, INT32U granularity）。如何取得结构数组下标值同OSMemGet（）函数。在找到所要回收的结构数组后，判断该数组内存块链表上是否有与要回收的内存块连续的地址。若有合并且挂到下一内存块结构数组内存块链表，这样一直到最后一个结构数组，目的是为了保证有更大的内存块可满足应用程序的申请，提高了内存管理的可靠性。

在改进以上函数的基础上，还可以在申请内存块之前有选择地使用OSMemQuery（）查询内存中是否有满足需要的内存块。如果没有则作好相应的规避措施，进一步提高内存管理的可靠性，使系统更稳定。

5 实验结果及性能分析

针对改进前后μC/OSII内存管理策略的特点，设计一组具有代表性的测试用例来分析μC/OSII系统在改进前后内存管理的可靠性和灵活性。实验环境为ARM Develop Suit V1. 2及三星公司S3C2440微控制器，由于S3C2440片内包含MMU模块，所以需要将协处理器CP15的C1寄存器0位置0,以禁用MMU功能。

假设两种方案内存初始化都创建了5个分区，每个分区中所含内存块为10个，且这5个内存分区中的内存块大小依次为16 B、32 B、64 B、128 B、256 B。原方案创建分区时要调用5次OSMemCreate（）函数，而改进方案只需调用一次。表1是申请内存块大小与两种方案可以满足的次数之间的关系。

表1 申请内存块大小与两种方案可以满足的次数比较

由表1的数据及图4的对比曲线可看出，改进方案与原方案在可用内存完全相同的情况下，使内存的利用率大大提高。因为可靠性与可满足次数正相关，而可满足次数与曲线与坐标轴围成的面积成正比，所以该面积与可靠性正相关。新方案曲线所围图形面积为12960， 而原方案曲线所围成的图形面积为2400。所以新方案的可靠性将比原来方案提高大约4倍，而且申请内存块越小，可满足次数越多，提高了内存分配的灵活性。