简述内存管理中buddy算法和slab机制的区别

1、Buddy算法

linux对空闲内存空间管理采取buddy算法，

Buddy算法：

把内存中所有页面按照2^n划分，其中n=0~5，每个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。划分后形成了大小不等的存储块，称为页面块，简称页块，包含一个页面的页块称为1页块，包含2个页面的称为2页块，依次类推。

每种页块按前后顺序两两结合成一对Buddy“伙伴”。系统按照Buddy关系把具有相同大小的空闲页面块组成页块组，即1页块组、2页块组……32页块组。 每个页块组用一个双向循环链表进行管理，共有6个链表，分别为1、2、4、8、16、32页块链表。分别挂到free_area[] 数组上。

位图数组

用于标记内存页面使用情况，第0组每一位表示单个页面使用情况，1表示使用，0表示空闲，第二组每一位表示比邻的两个页面使用情况，一次类推。默认为10个数组，当一对Buddy的两个页面中有一个事空闲的，而另一个全部或部分被占用时，该位置1.两个页面块都是空闲，对应位置0.

内存分配和释放过程

内存分配时，系统按照Buddy算法，根据请求的页面数在free_area[]对应的空闲页块组中搜索。 若请求页面数不是2的整数次幂，则按照稍大于请求数的2的整数次幂的值搜索相应的页面块组。

当相应页块组中没有可使用的空闲页面块时就查询更大一些的页块组，在找到可用的页块后分配所需要的页面。当某一空闲页面被分配后，若仍有剩余的空闲页面，则根据剩余页面的大小把他们加入到相应页面组中。

内存页面释放时，系统将其作为空闲页面看待，检查是否存在与这些页面相邻的其他空闲页块，若存在，则合为一个连续的空闲区按Buddy算法重新分组。

2、Slab算法

采用buddy算法，解决了外碎片问题，这种方法适合大块内存请求，不适合小内存区请求。如：几十个或者几百个字节。Linux2.0采用传统内存分区算法，按几何分布提供内存区大小，内存区以2的幂次方为单位。虽然减少了内碎片，但没有显著提高系统效率。

Linux2.4采用了slab分配器算法，该算法比传统的分配器算法有更好性能和内存利用率，最早在solaris2.4上使用。

Slab分配器思想

1）小对象的申请和释放通过slab分配器来管理。

2）slab分配器有一组高速缓存，每个高速缓存保存同一种对象类型，如i节点缓存、PCB缓存等。

3）内核从它们各自的缓存种分配和释放对象。

4）每种对象的缓存区由一连串slab构成，每个slab由一个或者多个连续的物理页面组成。这些页面种包含了已分配的缓存对象，也包含了空闲对象。

Linux 在拿到一大块内存后（譬如是64MB内存），先将其看作是好多个连续排列的 4MB 内存。

那么如果程序请求1MB的内存，那么内存分配 *** 作逻辑如下：

这个算法就是所谓的 binary buddy 分配算法。

在 Linux 中，这个二分法最小分割到 4096 字节，也就是一个页的大小。

因此总共有 11 种大小，分别为 4KB，8KB，……4MB。

其中 4KB 为 order 0，4MB 为 order 10.

我们称其 max order 为 12，有些资料会提到这个概念。

以上这些信息可以在 /proc/buddyinfo 上查看，其格式大概是这样：

buddy 在上面这种情况下，有些被分为小块内存，那么就会存在内存碎片的问题。

/proc/pagetypeinfo

以上 buddy 管理的是不小于4K 的内存分配，slab 则是管理小于4KB 的内存对象。

频繁地请求和释放不同大小的内存，必然导致内存碎片问题的产生，结果就是当再次要求分配连续的内存时，即使整体内存是足够的，也无法满足连续内存的需求。该问题也称之为外碎片(external fragmentation)。

解决方案：

避免外碎片的方法有两种:

1、利用分页单元把一组非连续的空闲页框映射到连续的线性地址

2、开发一种适当的技术来记录现存的空闲的连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲快

第一种方案的意思是，我们使用地址转换技术，把非连续的物理地址转换成连续的线性地址。

第二种方案的意思是，开发一种特有的分配技术来记录下来空闲内存的情况，从而解决内存碎片问题。

Linux采用了第二种方案，因为在某些情况下，系统的确需要连续的物理地址（DMA处理器可以直接访问总线）。

Linux采用著名的伙伴系统(buddy system)算法来解决外碎片问题。把所有的空闲页框分组为11个块链表，每个链表分别包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续的页框，对1024个页框的最大请求对应着4MB大小的连续RAM（每页大小为4KB），每个块的第一个页框的物理地址是该块大小的整数倍，例如，大小为16个页框的块，其起始地址是16*2^12的倍数。

我们通过一个例子来说明伙伴算法的工作原理，假设现在要请求一个256个页框的块（1MB），算法步骤如下：

• 在256个页框的链表中检查是否有一个空闲快，如果没有，查找下一个更大的块，如果有，请求满足。

• 在512个页框的链表中检查是否有一个空闲块，如果有，把512个页框的空闲块分为两份，第一份用于满足请求，第二份链接到256个页框的链表中。如果没有空闲块，继续寻找下一个更大的块。

以上过程的逆过程，就是页框块的释放过程，也是该算法名字的由来，内核试图把大小为B的一对空闲伙伴块合并为一个2B的单独块，满足以下条件的两个块称之为伙伴：

• 两个块具有相同的大小

• 他们的物理地址是连续的

第一块的第一个页框的物理地址是2 * B * 2^12

该算法是递归的，如果它成功合并了B，就会试图去合并2B，以再次试图形成更大的块。

---