最近在复习操作系统，所以顺带总结一下常见的内存分配算法。

first-fit算法：

该算法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按 照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链 中。

优点：从这个分配算法的实现我们可以看出，这个算法倾向于使用内存中低地址部分的空闲块，因此较高地址的空闲块很少用到这样就会导致高地址部分有很大部分的空闲区，这样做显然位移后有大作业分配空间创造了极佳的条件！

缺点：从优点中我们也可以看出，低地址被不断地划分，由此会留下很多的难以利用的、很小的空闲区，从而很多的内部碎片，然而每次查找都会从低地址部分开始查找，从而会增加查找的开销！

best-fit算法：

该算法总是把既能满足要求，又是最小的空闲分区分配给作业。算法执行过程中，将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。和其他分配算法对比，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。

优点: 每次分配给作业都是最适合该作业大小的空闲块

缺点：和首次适配类似，在内存中留下了很多难以利用的小的空闲块

worst-fit算法：

该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲区中分配（不能满足需要则不分配）。很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。该算法克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。

优点：给文件分配后剩下的空闲区不会太小，对中小型作业分配分区有利

缺点：从算法实现我们可以看出，它使存储器缺乏大的空闲区，对大型文件的分配不利！

buddy算法：

Buddy System算法把系统中的可用存储空间划分为存储块(Block)来进行管理, 每个存储块的大小必须是2的n次幂(Pow(2, n)), 即1, 2, 4, 8, 16, 32, 64, 128…

初步理解

我们在练习一中用到的物理内存管理，它的空闲块大小是没有规则的，你想怎么分就怎么分（当然这取决于你的物理内存），而且是通过双向链表键他们链接起来，当要查找合适的空闲块时只能按物理地址顺序线性查找，时间复杂度达到了O（N），现在我们有更加好的物理内存管理方法，能使时间复杂度达到O（log N），这涉及到在上学期数据结构学的二叉树的概念，而且为了更好的进行物理内存管理，规定每个存储块的大小必须是2的n次幂。

优点：快速搜索合并，低外部碎片，，相对于前三种算法来说算是一种比较理想的分配算法

缺点：内部碎片（对于2^n+1等类似大小的会产生很大的内部碎片）

下面是一个内存大小为16的例子：

slab算法：

前面几种算法，要么是比较基础，要么是前面介绍过了，就不仔细展开了，现在我主要来介绍一下slab算法：

背景：

内核管理页面使用了2个算法：伙伴算法和slub算法，伙伴算法以页为单位管理内存，但在大多数情况下，程序需要的并不是一整页，而是几个、几十个字节的小内存。于是需要另外一套系统来完成对小内存的管理，这就是slub系统。slub系统运行在伙伴系统之上，为内核提供小内存管理的功能

实现：

slub把内存分组管理，每个组分别包含2^3、2^4、…2^11个字节，在4K页大小的默认情况下，另外还有两个特殊的组，分别是96B和192B，共11组。之所以这样分配是因为如果申请2^12B大小的内存，就可以使用伙伴系统提供的接口直接申请一个完整的页面即可。slub就相当于零售商，它向伙伴系统“批发”内存，然后在零售出去。

下面是slab一个示意图：

我们可以看出，slab管理系统对于占用内存较小的请求是很友好的，可以做到任意大小的内存分配！

优点：

可以提供小块内存的分配支持

不必每次申请释放都和伙伴系统打交道，提供了分配释放效率

如果在slab缓存的话，其在CPU高速缓存的概率也会较高。

伙伴系统的操作队系统的数据和指令高速缓存有影响，slab分配器降低了这种副作用

伙伴系统分配的页地址都页的倍数，这对CPU的高速缓存的利用有负面影响，页首地址对齐在页面大小上使得如果每次都将数据存放到从伙伴系统分配的页开始的位置会使得高速缓存的有的行被过度使用，而有的行几乎从不被使用。slab分配器通过着色使得slab对象能够均匀的使用高速缓存，提高高速缓存的利用率

缺点：

对于微型嵌入式系统，它显得比较复杂，这是可以使用经过优化的slob分配器，它使用内存块链表，并使用最先适配算法

对于具有大量内存的大型系统，仅仅建立slab分配器的数据结构就需要大量内存，这时候可以使用经过优化的slub分配器