核心数据结构
linux 2.6 的内存管理支持NUMA(Non Uniform Memory Access Achitecture)，即非一致内存访问体系，在该体系中存在多个CPU，并且拥有分离的存储器以及共享存储器。因此在linux的代码中将每一个CPU的可访问内存定义为一个内存节点。总体上linux采取了节点、域、页面三级结构描述物理内存，核心数据结构如下：
typedef struct pglist_data { //内存节点数据结构
struct zone node_zones[MAX_NR_ZONES];
//略}
struct zone {//域数据结构
//略
//#define MAX_ORDER 11
struct free_area free_area[MAX_ORDER]; //页管理 MAX_ORDER为11
//略}
buddy算法概述：
free_area对应一个域中的物理页面，页面的管理采用buddy算法。在buddy算法中物理内存被分为11个组，其中第0,1，N个组分别对应20、2N个连续物理界面。当分配2N 个页面是就会到相应的组去寻找，若没有则向下寻找同时向上归并空闲块。举例如下：
第一次：初始情况，所有的页面状态为可用；
第二次：申请一个页面，因此数组0的页面被获取；
第三次：申请两个页面，因此数组1的页面给获取；
第四次：仍然申请两个页面，此时数据1已经无空闲块，遍历至数组2；获取两个页面，同时将数组2的剩余两个页面向上归并，最终数组2满，而数组1空闲；
buddy算法实现（根据linux 2.6.11版本）
核心函数为mm/page_alloc.c中的__alloc_pages，函数原型为：
struct page * fastcall
__alloc_pages(unsigned int gfp_mask, //申请修饰符，如__GPF_WAIT表示分配器可以休眠
unsigned int order, //申请页面的阶数
struct zonelist *zonelist)
在该函数中调用：page = buffered_rmqueue(z, order, gfp_mask);
buffered_rmqueue调用__rmqueue和expand分别完成buddy算法中的申请页面查找，和分拆后的向上空闲块归并，代码如下：
static struct page *__rmqueue(struct zone *zone, unsigned int order)
{
struct free_area * area;
unsigned int current_order;
struct page *page; for (current_order = order; current_order < MAX_ORDER; ++current_order) {
area = zone->free_area + current_order;//到与current_order阶数对应的free_area数组元素
if (list_empty(&area->free_list))//当前area下无空闲块
continue;
page = list_entry(area->free_list.next, struct page, lru); //在area的free_list中获取属于LRU（当前最久未使用页面）
list_del(&page->lru);//在最久未使用页面列表中删除该页面
rmv_page_order(page);
area->nr_free--;//该area的可用页面-1
zone->free_pages -= 1UL << order; //整个域的页面减去2的阶层次个页面
return expand(zone, page, order, current_order, area);//拆分归并，current_order为实际获取页面的阶层数，如上例中的数组2
}
return NULL;
}
static inline struct page *
expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area)
{
unsigned long size = << high;//获取页面的数组所包含页面数量，如数组2包含4个页面 while (high > low) {//若实际阶层数大于申请阶层数，则需要进行拆分归并
area--;//向上查找
high--;
size >>= ;//size>>1表示上一级的全部页面数（举例，若在第4组即16个页面处，申请4个页面，那么剩下的12个会分为8个（size>>=1）和4个(size>>=2)填充到上面的数组里）
BUG_ON(bad_range(zone, &page[size]));
list_add(&page[size].lru, &area->free_list);//将上一级free_list变为空闲块
area->nr_free++;//该级可用页面数增加
set_page_order(&page[size], high);
}
return page;
}