内存管理算法--Buddy伙伴算法

不念不忘少年蓝@ 2022-05-28 09:17 219阅读 0赞

**Buddy算法的优缺点：**

1）尽管伙伴内存算法在内存碎片问题上已经做的相当出色，但是该算法中，一个很小的块往往会阻碍一个大块的合并，一个系统中，对内存块的分配，大小是随机的，一片内存中仅一个小的内存块没有释放，旁边两个大的就不能合并。  
![1332778152_5059.jpg][]  
2）算法中有一定的浪费现象，伙伴算法是按2的幂次方大小进行分配内存块，当然这样做是有原因的，即为了避免把大的内存块拆的太碎，更重要的是使分配和释放过程迅速。但是他也带来了不利的一面，如果所需内存大小不是2的幂次方，就会有部分页面浪费。有时还很严重。比如原来是1024个块，申请了16个块，再申请600个块就申请不到了，因为已经被分割了。

3）另外拆分和合并涉及到 较多的链表和位图操作，开销还是比较大的。

**Buddy（伙伴的定义）：**

这里给出伙伴的概念，满足以下三个条件的称为伙伴：  
1）两个块大小相同；  
2）两个块地址连续；  
3）两个块必须是同一个大块中分离出来的；

**Buddy算法的分配原理：**

假如系统需要4(2\*2)个页面大小的内存块，该算法就到free\_area\[2\]中查找，如果链表中有空闲块，就直接从中摘下并分配出去。如果没有，算法将顺着数组向上查找free\_area\[3\],如果free\_area\[3\]中有空闲块，则将其从链表中摘下，分成等大小的两部分，前四个页面作为一个块插入free\_area\[2\]，后4个页面分配出去，free\_area\[3\]中也没有，就再向上查找，如果free\_area\[4\]中有，就将这16(2\*2\*2\*2)个页面等分成两份，前一半挂如free\_area\[3\]的链表头部，后一半的8个页等分成两等分，前一半挂free\_area\[2\]  
的链表中，后一半分配出去。假如free\_area\[4\]也没有，则重复上面的过程，知道到达free\_area数组的最后，如果还没有则放弃分配。

![1332777103_8942.jpg][]

Buddy算法的释放原理：

内存的释放是分配的逆过程，也可以看作是伙伴的合并过程。当释放一个块时，先在其对应的链表中考查是否有伙伴存在，如果没有伙伴块，就直接把要释放的块挂入链表头；如果有，则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块(2\*2\*2\*2\*2\*2\*2\*2\*2个页面)。

![1332777437_9124.jpg][]

整个过程中，位图扮演了重要的角色，如图2所示，位图的某一位对应两个互为伙伴的块，为1表示其中一块已经分配出去了，为0表示两块都空闲。伙伴中无论是分配还是释放都只是相对的位图进行异或操作。分配内存时对位图的  
是为释放过程服务，释放过程根据位图判断伙伴是否存在，如果对相应位的异或操作得1，则没有伙伴可以合并，如果异或操作得0，就进行合并，并且继续按这种方式合并伙伴，直到不能合并为止。

**Buddy内存管理的实现：**

提到buddy 就会想起linux 下的物理内存的管理 ,这里的memory pool 上实现的 buddy 系统

和linux 上按page 实现的buddy系统有所不同的是,他是按照字节的2的n次方来做block的size  
  
实现的机制中主要的结构如下:  
  
整个buddy 系统的结构:

struct mem\_pool\_table

\#define MEM\_POOL\_TABLE\_INIT\_COOKIE (0x62756479)

uint32 initialized\_cookie; /\* Cookie 指示内存已经被初始化后的魔数, 如果已经初始化设置为0x62756479\*/

uint8 \*mem\_pool\_ptr;/\* 指向内存池的地址\*/

uint32 mem\_pool\_size; /\* 整个pool 的size,下面是整个max block size 的大小\*/

uint32 max\_block\_size ; / \* 必须是2的n次方 ,表示池中最大块的大小 \* /  
boolean assert\_on\_empty ; / \* 如果该值被设置成TRUE ,内存分配请求没有完成就返回 并输出出错信息 \* /  
uint32 mem\_remaining ; / \* 当前内存池中剩余内存字节数 \* /  
uint32 max\_free\_list\_index ; / \* 最大freelist 的下标 , \* /  
struct mem\_free\_hdr\_type \*free\_lists \[MAX\_LEVELS \] ; / \* 这个就是伙伴系统的level数组 \* /  
  
\#ifdef FEATURE\_MEM\_CHECK  
uint32 max\_block\_requested ;  
uint32 min\_free\_mem ; / \* 放mem\_remaining \* /  
\#endif / \* FEATURE\_ONCRPC\_MEM\_CHECK \* /   
\} ;

这个结构是包含在free node 或alloc node 中的结构:

其中check 和 fill 都被设置为某个pattern  
用来检查该node 的合法性  
\#define MEM\_HDR\_CHECK\_PATTERN ((uint16)0x3CA4)  
\#define MEM\_HDR\_FILL\_PATTERN ((uint8)0x5C)

typedef struct tagBuddyMemBlockHeadType

mem\_pool\_type pool; /\*回指向内存池\*/

uint16 check;

uint8 state; /\* bits 0\-3 放该node 属于那1级 bit 7 如果置1,表示已经分配(not free)

uint8 fill;

\} BUDDY\_MEM\_BLOCK\_HEAD\_TYPE;

这个结构就是包含node 类型结构的 free header 的结构:

typedef struct tagBuddyMemHeadType

mem\_node\_hdr\_type hdr;

struct mem\_free\_hdr\_type \* pNext; /\* next,prev,用于连接free header的双向 list\*/

struct mem\_free\_hdr\_type \* pPrev;

\} mem\_free\_hdr\_type;

这个结构就是包含node 类型结构的 alloc header 的结构:  
已分配的mem 的node 在内存中就是这样表示的

1.  typedef struct mem\_alloc\_hdr\_type  
    
2.  \{   
    
3.  mem\_node\_hdr\_type hdr;  
    
4.    
    
5.  \#ifdef FEATURE\_MEM\_CHECK\_OVERWRITE  
    
6.  uint32 in\_use\_size;  
    
7.  \#endif  
    
8.    
    
9.  \} mem\_alloc\_hdr\_type;

其中用in\_use\_size 来表示如果请求分配的size 所属的level上实际用了多少  
比如申请size=2000bytes, 按size to level 应该是2048,实际in\_use\_size  
为2000,剩下48byte 全部填充为某一数值,然后在以后free 是可以check   
是否有overwite 到着48byte 中的数值,一般为了速度,只 检查8到16byte  
  
另外为什么不把这剩下的48byte 放到freelist 中其他level 中呢,这个可能  
因为本来buddy 系统的缺点就是容易产生碎片,这样的话就更碎了

关于free or alloc node 的示意图:

假设

最小块为2^4=16,着是由mem\_alloc\_hdr\_type (12byte)决定的, 实际可分配4byte

如果假定最大max\_block\_size =1024,

如果pool 有mem\_free\_hdr\_type\[0\]上挂了两个1024的block node

上图是free node, 下图紫色为alloc node

[![20514606_1311558287t03T.jpg][]][20514606_1311558287t03T.jpg 1]

接下来主要是buddy 系统的操作主要包括pool init , mem alloc ,mem free  
  
pool init :  
 1. 将实际pool 的大小去掉mem\_pool\_table 结构大小后的size 放到  
 mem\_pool\_size, 并且修改实际mem\_pool\_ptr指向前进mem\_pool\_table  
 结构大小的地址  
 2. 接下来主要将mem\_pool\_size 大小的内存,按最大块挂到free\_lists 上  
 level 为0的list 上,然后小于该level block size 部分,继续挂大下一  
 级,循环到全部处理完成 (感觉实际用于pool的size ,应该为减去  
 mem\_pool\_table 的大小,然后和最大块的size 对齐,这样比较好,  
 但没有实际测试过)  
  
  
mem alloc:  
 这部分相当简单,先根据请求mem的size ,实际分配时需要加上mem\_alloc\_hdr\_type  
这12byte ,然后根据调整后的size,计算实际应该在那个 level上分配,如果有相应级  
很简单,直接返回,如果没有,一级一级循环查找,找到后,把省下的部分,在往下一级  
一级插入到对应级的freelist 上  
  
mem free:  
 其中free 的地址,减去12 就可以获得mem\_alloc\_hdr\_type 结构  
 然后确定buddy 在该被free block 前,还是后面, 然后合并buddy,  
 循环寻找上一级的buddy ,有就再合并,只到最大block size 那级  
  
  
  
关于这个算法,在<<The Art of Computer Programming>> vol 1,的

动态存储分配中有描述,对于那些只有OSAL 的小系统,该算法相当有用

转自：https://blog.csdn.net/orange\_os/article/details/7392986

[1332778152_5059.jpg]: https://img-my.csdn.net/uploads/201203/27/1332778152_5059.jpg
[1332777103_8942.jpg]: https://img-my.csdn.net/uploads/201203/26/1332777103_8942.jpg
[1332777437_9124.jpg]: https://img-my.csdn.net/uploads/201203/26/1332777437_9124.jpg
[20514606_1311558287t03T.jpg]: http://blog.chinaunix.net/attachment/201107/25/20514606_1311558287t03T.jpg
[20514606_1311558287t03T.jpg 1]: http://blog.chinaunix.net/link.php?url=http://blog.chinaunix.net%2Fattachment%2F201107%2F25%2F20514606_1311558287t03T.jpg