Linux内存管理-内存碎片的终极解决方案

内存碎片问题

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

解决方案

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

• 利用分页单元把一组非连续的空闲页框映射到连续的线性地址
• 开发一种适当的技术来记录现存的空闲的连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲快

第一种方案的意思是，我们使用地址转换技术，把非连续的物理地址转换成连续的线性地址。
第二种方案的意思是，开发一种特有的分配技术来记录下来空闲内存的情况，从而解决内存碎片问题。

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

伙伴系统(buddy system)

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，以再次试图形成更大的块。