初窥内存管理（三）伙伴算法

假设系统的可利用内存空间容量为2^m个字(地址从0到2^m-1)，则在开始运行时，整个内存区是一个大小为2^m的空闲块，在运行了一段时间之后，被分隔成若干占用块和空闲块。为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表，这就是伙伴系统中的可利用空间表，如图所示：

分配算法：

当用户提出大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应的子表中。
若2^k-1< n ≤ 2^k-1，又第k+1个子表不空，则只要删除此链表中第一个结点并分配给用户即可；若 2^k-2< n ≤ 2^k-1-1，此时由于结点大小为2^k-1的子表为空，则需从结点大小为2^k的子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为2^k-1的子表中，若2^k-i-1< n ≤ 2^k-i-1(i为小于是的整数)，并且所有结点小于2^k的子表均为空，则同样需从结点大小为2^k的子表中取出一块，将其中2^k-i的一小部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为2^k-1、 2^k-2、…、 2^k-i的子表中。

回收算法：

在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中去。这里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴”的两个空闲块的归并。
何谓“伙伴”?如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。例如：假设p为大小为pow(2,k)的空闲块的初始地址，且p MOD pow(2,k+1)=0，则初始地址为p和p+pow(2,k)的两个空闲块互为伙伴。在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一起。
由此，在回收空闲块时，应首先判别其伙伴是否为空闲块，若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。

全文转自