随着用户程序的执行和结束，系统不断的为其进行分配与回收物理页面，这必然会产生大量的碎片，这些碎片被分成了两类：内部碎片与外部碎片。如下图：
对于伙伴算法中的伙伴是有条件的，即：
那么接下去我们要为程序分配一个3个连续的物理页面显然不可行了，虽然我们实际的物理内存中存在着3个物理页面这么大的空间，这些不连续的物理页面就成为了外部碎片。在linux系统中采用了伙伴算法来解决这个外部碎片的问题。在内核中有一个free_area这个结构体（include/linux/mmzone.h），它表示了内存中的空闲物理页面。结构体代码如下：
点击(此处)折叠或打开
- struct free_area{
- struct list_head free_list[MIGRATE_TYPES];
- unsigned long nr_free;
- };
1）、两个快的大小相同；
2）、两个块的物理地址连续。
下面我们结合上面这张图来说明该算法的工作原理。
假设要求分配的块的大小为128个页面。该算法先在块大小为128个页面的链表中查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小为256个页面的链表中查找一个空闲块。如果存在这个空闲块，内核就把256个页面分为两等份，一份分配出去，另外一份插入到块大小为128的链表中。如果在块大小为256的链表中也没有找到空闲页块，就继续找更大的块，即512个页面的块。如果存在内核就从512分出128个页面满足请求，然后从384个页面中取出256个页面插入到大小256的链表中。然后把剩余的128个页面插入到大小为128个页面的链表中。如果512也没找到，那就继续向上找，一直找不到则算法放弃分配，并发出出错信号。
以上过程的逆过程就是块的释放过程。算法把满足伙伴条件的两个块合并为一个块，该算法是个迭代算法，如果合并后的块还可以跟相邻的块进行合并，那么该算法就继续合并。
slab机制：
伙伴算法也有不足，它不能解决内部碎片的问题，为了解决这个问题，内核又引入了slab机制，它主要是为了减少伙伴算法的调用次数。slab分配器为每个对象都建立了一个高速缓存，内核对这个对象的分配和释放都是在这个缓存中实现的。
比如task_struct这个结构，在每次创建进程都会为这个结构体分配空间，在进程销毁后又回收这部分空间，那么内核就为其建立一个专用的缓冲区，而task_struct就是如上图所示的对象。每个高速缓冲区在内核中都是由kmem_cache这个结构表示的，每个slab都处于三种状态之一：满、部分满、空。
下面是一个slab分配实例，就用刚才提高到了的task_struct这个结构举例：代码在kernel/fork.c中。
首先，内核用一个全局变量存放指向task_struct高速缓冲区的指针：
struct kmem_cache *task_struct_cachep;
task_struct_cachep = kmen_cache("task_struct",sizeof(struct task_struct),
ARCH_MIN_TASKALIGN,
SLAB_PANIC|SLAB_NOTRACK,NULL);
这样就创建了一个名为task_struct的高速缓存，存放的数据类型为struct task_struct的对象。
在创建进程时，将会调用以下内容（dup_task_struct()中完成）：
struct task_struct *tsk;
tsk = kmen_cache_alloc(task_struct_cachep,GFP_KERNEL);
if(!tsk)
return NULL;
这些函数分配的都是专用缓冲区。但是当一个数据结构使用的不频繁，或者其大小不足一个页面时就没有必要给其分配专用缓冲区，而是通过kmalloc()或者数据结构大小接近一个页面时使用__get_free_pages()分配。这些分配的就是在通用缓冲区的分配。
