**注意，本文主要内容来自《Understanding the Linux Virtual Memory Manager》，基于2.4内核，和最新内核有所不同。并且本人是内核新手，请轻拍。**
伙伴系统的结构和水位
linux内核使用伙伴系统来分配内存页，分配内存的API是alloc_pages()，但是主函数是__alloc_pages()，这个函数分为三个部分：
- 看是否能在不达到zone->pages_low水位的情况下满足分配要求，如能则直接分配。
- 否则zone需要balance，唤醒kswapd，并看能否在不达到zone->pages_min水位的情况下满足分配要求，如能则分配。
- 否则进入slow path，先看自己是否是即将被OOM killer杀掉的进程，如是则不管水位直接分配，否则自己同步地做kswapd该做的事。
每个zone都有三个水位线：pages_min，pages_low，pages_high，这三个水位线用于描述系统的内存压力大小的，当zone内空闲页的数目达到pages_low时__alloc_pages()会唤醒kswapd进程，当到了pages_min时__alloc_pages()也会自己干kswapd该干的活，也就是同步的kswapd，直到空闲页数目达到pages_high。
不过，物理页分配器最难理解的就是伙伴系统的结构和操作过程了。伙伴系统使用下面的结构体的数组描述空闲页：
typedef struct free_area_struct {
struct list_head free_list;
unsigned long *map;
} free_area_t;
由于伙伴系统的最基本单位是页，而且只能分配2order页数的连续内存块，所以order就作为结构体数组的索引，结构体中的free_list链接的是连续内存块中的第一个struct page，而map则是表示页是否分配的位图。
需要注意的是内核用一种比较特殊的方式操作位图：**只用1位了表示两个伙伴的状态，即每分配或释放一个伙伴就会对相应的位取反。所以0表示两个伙伴都可用或都不可用，1表示有一个可用**。内核使用下面宏来操作位图：
#define MARK_USED(index, order, area) \
__change_bit((index) >> (1 + (order)), (area)->map)
注意其中的1，就是因为内核使用1位表示两个伙伴的状态，才会有中间的1。其中index是struct page在全局mem_map中的索引，area即是struct free_area_struct。
分配内存
考虑一个有16页的系统，如果一开始都是空闲那么free_area数组应该如下图，其中我用page表示结构体中的free_list，page的值就是相应struct page在全局mem_map中的偏移：
free_area初始状态
其中order为4的page有个0表示mem_map的0偏移开始的24页都是空闲，其他page为NULL表示没有对应order大小的空闲页，而由于总共才16（24）页，所以order 4没有伙伴，而内核用位图的1位来描述伙伴，所以order为4的map为NULL，而3有一位，以此类推。
假设现在需要分配order为2的连续内存块，先在free_area[2]中找，由于order为2的page为NULL，即表示没有order 2的连续空间，这样就要往order更高的地方找，3中也没有，只有4中有，这样就要进行分裂，将分裂出来的前一个伙伴放在order为3的page中，而后一个伙伴继续分裂一直到得到想要的order，本例中就是2，所以分配完这次order 2和3都会有一个空闲的块，如下图：
分配内存块后的free_area状态
现在的物理页应该有最后4页被占用，前面12页仍然空闲，上面的结构页表示正确（order为2的page有8表示从第8～11页为空闲，而12～15页已经被分配）。
释放内存
再看看释放的过程，内存块使用者必须记得所使用内存块的order，因为在释放时需要用到，这也是伙伴系统不方便的地方，分配的API是alloc_pages()而释放的API是\_free_pages()，它的主要函数是\_free_pages_ok()，由其做主要的释放工作：检查刚释放的内存块是否能与相应伙伴合并，这只要通过查看相应的位图是否为1即可完成，如果能合并，那么合并后会往更高的order里添加空闲页，并继续查看是否能此合并，直到MAX_ORDER，这个常数常常是10。本例合并后又变成原来的状态了。
碎片
碎片分为两种：
- 外部碎片是无法满足大的分配要求，因为只存在小的内存块。
- 内部碎片是对于小的请求也只能分配大的内存块。
Linux的外部碎片问题并不严重，因为大的请求可以通过vmalloc()分配一个物理地址上不连续但是虚拟地址上连续的内存块。只是伙伴系统的内部碎片问题非常严重，因为伙伴系统的最小单位是页，这个单位对于直接分配结构体太大，所以内核还使用了slab分配器来解决这个问题。