本文转自：http://edsionte.com/techblog/archives/3763
伙伴算法（buddy system）在物理内存管理中占据十分重要的位置，这种算法可以有效的避免内存中的外部碎片。所谓外部碎片（external fragmentation），就是指内存频繁请求和释放大小不同的连续页框后，导致在已分配页框块周围分散了许多小块空闲的页框，尽管这些空闲页框的总数可以满足接下来的请求，但却无法满足一个大块的连续页框。本文接下来详细说明伙伴算法在内核中的结构描述，其基本原理本文不再赘述。
在每个内存管理区中都有一个free_area数组，该数组的长度为MAX_ORDER，默认值为11。free_area数组描述的就是伙伴算法中每个分配阶（从0到11）所对应的页框块链表。比如free_area[2]所对应的页框块链表中，每个节点对应4个连续的页框（2的2次方）。
struct zone {
……
struct free_area free_area[MAX_ORDER];
……
}
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
可以看到，free_area数组的元素类型是struct free_area，该结构的描述如下：
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
在这个结构中的确有一个表示当前分配阶所对应的页框块链表free_list，不过这里稍显复杂一下，因free_list是一个链表数组，这个数组也称为迁移数组。我们可以将这个数组看作是对页框块链表的进一步细分，每个数组元素对应一种迁移类型的页框块链表。迁移列表是在内核2.6.24中引入的，它更加的避免了由于系统长期运行而产生的外部碎片。除了链表结构以外，该结构使用nr_free表示当前链表中空闲页框块的数目，比如free_area[2]中nr_free的值为5，表示有5个大小为4的页框块，那么总的页框数目为20。根据上面对伙伴算法数据结构的描述，可以得到下面的关系图：
上图表示的是某个内存节点中的某个内存管理区中的伙伴算法示意图。需要注意的是，页框描述符page中有一个lru字段，该字段即为链接每个页框块的链表节点。
struct page {
……
struct list_head lru;
……
};
从图中也可以看出，链表中负责连接前后页框块的是该页框块首页框中的链表节点。