3.7.1 基本的伙伴分配器

连续的物理页称为页块（page block）。阶（order）是伙伴分配器的一个术语，是页的数量单位，2n个连续页称为n阶页块。满足以下条件的两个n阶页块称为伙伴（buddy）。

（1）两个页块是相邻的，即物理地址是连续的。

（2）页块的第一页的物理页号必须是2n的整数倍。

（3）如果合并成（n+1）阶页块，第一页的物理页号必须是2n+1的整数倍。

这是伙伴分配器（buddy allocator）这个名字的来源。以单页为例说明，0号页和1号页是伙伴，2号页和3号页是伙伴，1号页和2号页不是伙伴，因为1号页和2号页合并组成一阶页块，第一页的物理页号不是2的整数倍。

伙伴分配器分配和释放物理页的数量单位是阶。分配n阶页块的过程如下。

（1）查看是否有空闲的n阶页块，如果有，直接分配；如果没有，继续执行下一步。

（2）查看是否存在空闲的（n+1）阶页块，如果有，把（n+1）阶页块分裂为两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；如果没有，继续执行下一步。

（3）查看是否存在空闲的（n+2）阶页块，如果有，把（n+2）阶页块分裂为两个（n+1）阶页块，一个插入空闲（n+1）阶页块链表，另一个分裂为两个n阶页块，一个插入空闲n阶页块链表，另一个分配出去；如果没有，继续查看更高阶是否存在空闲页块。

释放n阶页块时，查看它的伙伴是否空闲，如果伙伴不空闲，那么把n阶页块插入空闲的n阶页块链表；如果伙伴空闲，那么合并为（n+1）阶页块，接下来释放（n+1）阶页块。

内核在基本的伙伴分配器的基础上做了一些扩展。

（1）支持内存节点和区域，称为分区的伙伴分配器（zoned buddy allocator）。

（2）为了预防内存碎片，把物理页根据可移动性分组。

（3）针对分配单页做了性能优化，为了减少处理器之间的锁竞争，在内存区域增加1个每处理器页集合。