Buddy算法在μC/OSII动态内存管理改进方案中的应用

时间：02-14 来源：3721RD 点击：

1 内存管理概述

内存管理是操作系统的中心任务之一，其主要任务是组织内存以容纳内核和待执行程序，跟踪当前内存的使用情况，在需要时为进程分配内存，使用完毕后释放并回收内存。目前嵌入式系统中常用的内存管理策略主要有两种--静态内存分配和动态内存分配。

静态内存分配：编译或链接时将所需内存分配好，程序运行起来后所分配的内存不释放。对于实时性和可靠性要求极高的系统，不允许延迟或者分配失效，必须采用静态内存分配的方式。

动态内存分配：根据程序执行过程中所需内存的大小而动态分配内存的策略。此方案按需分配内存，避免了静态分配中的内存浪费，灵活性比较强，给程序的实现带来了很大方便。缺点是容易造成内存碎片，且容易造成程序响应不及时等问题。

综上所述，静态内存分配和动态内存分配各有优点，出于嵌入式系统可靠性、实时性及成本、功耗的考虑，如何在两种方案中作出平衡的选择是令嵌入式操作系统设计者头疼的事。一般的嵌入式操作系统都是两种方案的高效结合，μC/OSII也不例外。除此之外，嵌入式操作系统对内存的分配还有以下几点要求：

① 可靠性。内存分配的请求必须得到满足，如果分配失败可能会带来灾难性的后果。比如，航天飞机的嵌入式操作系统若发生内存分配失效，损失是不可估量的。

② 快速性。嵌入式系统对实时性的保证，要求简单、快速地分配内存。

③ 高效性。嵌入式系统中内存是一种有限、昂贵的资源，内存分配要尽可能地减少浪费。

μC/OSII作为一种典型的嵌入式操作系统，其内存管理同样要满足以上3点要求，下面简单介绍μC/OSII的内存管理策略，并分析其不足之处。

2 μC/OSII动态内存管理方案及不足

2.1 μC/OSII内存管理方案简介

μC/OSII内存管理模块主要由一个数据结构体和5个函数组成：

◆ 内存控制块数据结构OS_MEM；
◆ 内存分区创建函数OSMemCreate（void *addr, INT32U nblks, INT32U blksize, INT8U *err）；
◆ 内存块分配函数OSMemGet（OS_MEM *pmem , INT8U *err）；
◆ 内存块释放函数OSMemPut（OS_MEM *pmem , void *pblk）；
◆ 内存分区状态查询函数OSMemQuery（OS_MEM *pmem, OS_MEM_DATA *p_mem_data）；
◆ 内存控制块链表初始化函数OSMemInit（void）。

μC/OSII用一个内存控制块（OS_MEM）来管理内存分区，主要通过以下4步来管理：

① 内存控制块链表初始化函数OSMemInit（）负责创建空内存控制块结构的链表，链表长度由内核OS_CFG.H文件中定义的OS_MAX_MEM_PART宏确定。

② 内存块创建函数OSMemCreate（）先从空内存控制块结构链表上获取一个空的内存控制根块结构，根据用户需要内存块的大小来创建分区。一个分区中含有相同大小的内存块，各内存块也是通过链表链接起来，而不同分区中的内存块大小一般不同，如图1所示的PartitiON # 1和Partition # 2中内存块的大小是不同的。

图1 μC/OSII通过内存控制块管理内存

③ 内存块分配函数OSMemGet（）通过从内存控制块链表中找到能够满足自己内存块需要的内存控制块，然后从这个内存控制块指向的分区链表首部得到自己需要的内存块。

④ 内存块释放函数OSMemPut（）负责回收内存块。当应用程序不再使用某一个内存块时，必须及时把它释放，并放回到相应的内存分区中。

2.2 μC/OSII内存管理方案的不足之处

如前所述，μC/OSII的内存管理方案简短精炼，仅百余行代码，5个函数就能胜任。然而考虑到第1节提到的嵌入式系统对内存管理策略的3个要求，μC/OSII的内存管理策略存在以下不足之处：

① 原μC/OSII内存管理方案可靠性不高。因为原方案中各内存分区之间是孤立的，没有联系。一个内存分区上的内存块用完时，不能利用其他分区上的内存块，而只是简单地报错，从而使系统可靠性大大降低。在内存块大小及需求量不确定的场合，如果经常发生内存申请得不到满足的情况，是嵌入式系统所不能容忍的。

② 原μC/OSII内存管理方案中内存分配不够灵活。举个例子来说，一个应用程序需要大小为1 KB、512 B、256 B三种内存块，原方案有两种解决方案，一是创建一个内存块大小为1 KB的内存分区，内存块数目至少为3个；二是创建3个内存分区，内存块大小分别为1 KB、512 B、256 B。方案一创建了较少分区，性能有保证，但造成内存资源的浪费；方案二虽然没有浪费内存，但却调用3次OS_MemCreate（）函数，效率较低。

3 Buddy算法简介

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的块来形成更大的块。在本方案中，只要满足前两个条件就足够了。

上一篇：DSP在数字语音压缩系统中的应用
下一篇：DSP在光缆通信的远程高速数据采集及处理系统的设计与应用

内存管理 Buddy算法静态分配相关文章：

栏目分类