伙伴系统算法

背景

最近因为工作的需要开始调研伙伴系统算法，刚开始听到这个名词时竟然是一头雾水，什么都不知道，甚至对它还有一种神秘感、逃离感，不过这终抵不过理智的分析，搜索查一下总可以搞明白的。

由分页引起的问题

我们知道内存分配时是按照“页框”进行分配的，一个页框也就4K，考虑多次分配释放之后的情况：

1. 第一次申请2N个页呢？简单，连续分2N个页；
2. 第二次再申请2N个页？简单，接着上次的2N个页往后分；
3. 第三次请释放掉第一次申请的2N个页？简单，直接收回；
4. 第四次申请N个页？是从第一次释放的位置分配还是从第二次申请空间的后面分配呢？

仔细想想：经过无数次无规律的内存申请释放之后，内存中肯定存在大量的小块内存，无法满足大内存申请的需求，即使小块内存是连着的也需要有种机制来将它们合并。伙伴系统就是解决大块内存管理问题的一种机制；

伙伴的定义

这里给出伙伴的概念，满足以下三个条件的称为伙伴：

1. 两个块大小相同；
2. 两个块地址连续；
3. 两个块必须是同一个大块中分离出来的；

伙伴系统管理策略

可以在维基百科上找到该算法的描述，大体如是：

分配内存：

寻找大小合适的内存块（大于等于所需大小并且最接近2的幂，比如需要27，实际分配32）
1. 如果找到了，分配给应用程序。
2. 如果没找到，分出合适的内存块。
  1. 对半分离出高于所需大小的空闲内存块
  2. 如果分到最低限度，分配这个大小。
  3. 回溯到步骤1（寻找合适大小的块）
  4. 重复该步骤直到一个合适的块

释放内存：

释放该内存块
1. 寻找相邻的块，看其是否释放了。
2. 如果相邻块也释放了，合并这两个块，重复上述步骤直到遇上未释放的相邻块，或者达到最高上限（即所有内存都释放了）。

上面这段文字可能看起来很费劲，我们看个内存分配和释放的示意图：

上图中，首先我们假设我们一个内存块有1024K，当我们需要给A分配70K内存的时候，

我们发现1024K的一半大于70K，然后我们就把1024K的内存分成两半，一半512K。
然后我们发现512K的一半仍然大于70K，于是我们再把512K的内存再分成两半，一半是128K。
此时，我们发现128K的一半小于70K，于是我们就分配为A分配128K的内存。

后面的，B，C，D都这样，而释放内存时，则会把相邻的块一步一步地合并起来（合并也必需按分裂的逆操作进行合并）。

这样的算法，用二叉树这个数据结构比较合适。

分配器的整体思想是，通过一个数组形式的完全二叉树来监控管理内存，二叉树的节点用于标记相应内存块的使用状态，高层节点对应大的块，低层节点对应小的块，在分配和释放中我们就通过这些节点的标记属性来进行块的分离合并。如图所示，假设总大小为16单位的内存，我们就建立一个深度为5的满二叉树，根节点从数组下标[0]开始，监控大小16的块；它的左右孩子节点下标[1~2]，监控大小8的块；第三层节点下标[3~6]监控大小4的块……依此类推。

在分配阶段，首先要搜索大小适配的块，假设第一次分配3，转换成2的幂是4，我们先要对整个内存进行对半切割，从16切割到4需要两步，那么从下标[0]节点开始深度搜索到下标[3]的节点并将其标记为已分配。第二次再分配3那么就标记下标[4]的节点。第三次分配6，即大小为8，那么搜索下标[2]的节点，因为下标[1]所对应的块被下标[3~4]占用了。

在释放阶段，我们依次释放上述第一次和第二次分配的块，即先释放[3]再释放[4]，当释放下标[4]节点后，我们发现之前释放的[3]是相邻的，于是我们立马将这两个节点进行合并，这样一来下次分配大小8的时候，我们就可以搜索到下标[1]适配了。若进一步释放下标[2]，同[1]合并后整个内存就回归到初始状态。

一直到这，这里讲的都很好，但是接下来的内容，在原blog上就有所欠缺了，最起码我是没看懂他对程序的解释，下面我就将我对程序的解释贴在下面。

伙伴系统程序分析

cloudwu和wuwenbin写的两份开源实现和测试用例。实际上后一份是对前一份的精简和优化，而且这份实现真正体现了“极简”二字，追求突破常规的，极致简单的设计，这里是我对该程序的注解。

下面我将几个比较难以理解的点，也是传说中的精华部分在下面解释一下：

伙伴分配器数据结构

truct buddy2{
    unsigned size;            // 管理内存的总单元数目，unsigned后省略的是int
    unsigned longest[1];    // 二叉树的节点标记，表明该节点可分配的最大单元数
};

不论是从存储结构上还是从变量声明（数组成员数为1）上看，这个结构体都比较有意思，我们结合下面一段程序来看：

for (i = 0; i < 2 * size - 1; ++i){
    if (IS_POWER_OF_2(i+1))
        node_size /= 2;
    self->longest[i] = node_size;        // 经验证，这里可以正确向后访问 
}

它是不是发生了语法错误（i的值肯定会有大于0的时候），但是我在运行时竟然没有报错。然后我就做了个测试，程序在这里，为了解读方便，我再将程序片段拷贝一份：

void main()
{
    struct buddy2 self;
      unsigned node_size;
      int i,size=32;

      self->size = size;        // 第一个结构体的size存放总的块数size
      node_size = size * 2;        // 总共的sizeof(unsigned)数

    struct buddy2* init = (struct buddy2*)&self;

    init->size = 32
    init->longest[0] = 222;
      for(i=0; i<2; i++)
          printf("self->size=%d\tself->longest[%d]=%d\r\n",self->size,i,self->longest[i]);
}

可以看到这样不符合C语言语法的程序当然会运行错误：segmentation fault，也就是产生了越界错误；

但是按照buddy2中的程序，我们再做一次实验：

void main()
{
      struct buddy2* self;
      unsigned node_size;
      int i,size=32;

      self = (struct buddy2*)ALLOC( 2 * size * sizeof(unsigned));
      self->size = size;        // 第一个结构体的size存放总的块数size
      node_size = size * 2;        // 总共的sizeof(unsigned)数

    // 以下是验证longest访问正确性的
    unsigned* init = (unsigned*)self;
      for(i=0; i<64; i++,init++)
      {
          *init = i;
      }

      init = (unsigned*)self;
      printf("memories allocated:\r\n");
      for(i=0; i<64; i++,init++)
          printf("%d\t",*init);
      for(i=0; i<32; i++)
          printf("self->size=%d\tself->longest[%d]=%d\r\n",self->size,i,self->longest[i]);
}

这里我是将所分配的内存区域按照0 1 2 3 …的方式存放数据，然后按照self->size,self->longest[1],self->longest[1] …的方式进行读取打印，查看显示的内容的存储方式问题，结果很出乎意料：

1. 首先是能正常运行，没有发生数组越界问题，这个和上面一个程序的区别在于内存分配的方式不同；
2. self->longest[0...]竟然是按照内存的存储方式连续读取的数值，很不可思议，不过这是事实；
3. 只在分配的内存区域起始位置定义个结构体，self->size出现一次，后面都是self->longest的值；

以上结论出乎我的意料，但是事实证明它就是事实，只能接受，不过尚缺少理论支持。

现在我们在回到原程序当中，并且我对他做了一些改变再看一下结果：

void main()
{
      struct buddy2* self;
      unsigned node_size;
      int i,size=32;

      self = (struct buddy2*)ALLOC( 2 * size * sizeof(unsigned));
      self->size = size;        // 第一个结构体的size存放总的块数size
      node_size = size * 2;        // 总共的sizeof(unsigned)数

      for (i = 0; i < 2 * size - 1; ++i) {
        if (IS_POWER_OF_2(i+1))
          node_size /= 2;
        self->longest[i] = node_size;        // 经验证，这里可以正确向后访问 
      }

      printf("memories allocated:\r\n");
    unsigned* init = (unsigned*)self;
      for(i=0; i< 2 * size; i++,init++)
      {
          printf("%d\n",*init);
      }
}

我们打印出的结果是：两个32，2个16，4个8，8个4，16个2，32个1

第一个32是self->size，第二个是根节点0，后面依次为节点1,2,3…

这样的存储确实很牛逼，占用空间少，操作简单，不过难以理解；

调整参数为2的幂次方

static unsigned fixsize(unsigned size){
    size |= size >> 1;
    size |= size >> 2;
    size |= size >> 4;
    size |= size >> 8;
    size |= size >> 16;
    return size+1;
}

找到个注释是这样的：

/*
 * 把size调整到向上取到最近的2次幂
 * size |= size >> n;表示从低位到高位按2n位分组,每组内高n位复制到低n位
 * 最后经过处理size是从最高位的1开始往低位全1的整数
 * return size + 1; 得到向上凑够最近2次幂
 */

说实话，我没看懂。

结束

搞懂上面的两个问题，尤其是第一个问题，后面的阅读都很顺利了。

伙伴系统优缺点

伙伴分配的实质就是一种特殊的“分离适配”，即将内存按2的幂进行划分，相当于分离出若干个块大小一致的空闲链表，搜索该链表并给出同需求最佳匹配的大小。

其优点是快速搜索合并（O(logN)时间复杂度）以及低外部碎片（最佳适配best-fit）；

其缺点是内部碎片，因为按2的幂划分块，如果碰上66单位大小，那么必须划分128单位大小的块。但若需求本身就按2的幂分配，比如可以先分配若干个内存池，在其基础上进一步细分就很有吸引力了。