伙伴系统

固定分区和动态分区方案都是存在缺陷。

固定分区方案限制了活动进程的数量，并且若可用分区的大小与进程大小很不匹配，则内存空间的利用率就会非常低。
动态分区的维护非常复杂，并且会引入进行压缩的额外开销。

由此，就像是对于查看和修改复杂度这种一般，这种情况下也出现了一种很具有吸引力的这种方案：伙伴系统。

伙伴系统中可用内存块的大小为\(2^K\)个字，L≤K≤U，其中\(2^L\)表示分配的最小块的尺寸，\(2^U\)表示分配的最大块的尺寸，\(2^U\)表示可供分配的整个内存的大小

而分配的流程如下：

最初，整个可供分配的空间被视为一个大小为\(2^U\)的块。若请求的大小s满足\(2^{U-1}\)＜s≤\(2^U\)，那么整个空间将都会被分配。
否则的话，这个块分裂为两个大小相等伙伴，大小均为\(2^{U-1}\)。如果存在\(2^{U-2}\)＜s≤\(2^{U-1}\)，则给请求分配两个伙伴中的一个；
否则，其中的一个伙伴又被分成两半。
持续这一过程，直到产生≥s的最小块，并分配给该请求。
在任何时候，伙伴系统中为所有大小为\(2^i\)的“空洞”维护一个列表。空洞可通过对半分裂从i+1列表中移除，并在i列表中产生两个大小为\(2^i\)的伙伴
当i列表中一对伙伴都变成未分裂的块时，将它们从i列表中移除，合并为i+1的列表中的一个块。

请求大小为k的块，并且k满足\(2^{i-1}\)<k≤\(2^i\)，下面是一个寻找大小为\(2^i\)空间的算法例子

void get_hole(int i)
{
  if(i==(U+1)) <failure>;
  if(<i_list empty>)
  {
    get_hole(i+1);
    <split hole into buddies>;
    <put buddies on i_list>;
  }
  <take first hole on i_list>;
}