伙伴系统算法（解决外碎片问题)

它把所有的空闲页放到11个链表中，每个链表分别管理大小为1，2，4，8，16，32，64，128，256，512，1024个页的内存块。当系统需要分配内存时，就可以从buddy系统中获取。

例如，要申请一块包含4个页的连续内存，就直接从buddy系统中管理4个页连续内存的链表中获取。同样的，如果系统需要申请3个页的连续内存，则只能在4个页的链表中获取，剩下的一个页被放到buddy系统中管理1个页的链表中。

原理

Linux伙伴算法把所有空闲页面为分1^0个块组，每组中块的大小是2的幂次方个页面。比如，第0组中块大小都为2^0(1个页面)，第1组块的大小都为2^1(2个页面)，第9组中块的大小都为2^9(512个页面)。每一组中块大小是相同，大小的块形成一个链表。

假设要求分配的块的大小为128个页面(由多个页面组成的块叫页面块)，该算法先在块大小为128个页面的链表中查找，看是否有这样的一个空闲块。如果有，就直接分配; 如果没有，该算法会查找下一个更大的块，具体地说，就是在块大小256个页面的链表中查找一个空闲块。如果在存在这样的空闲块，内核就把这个256个页面分成2等份，一份分配出去，另一份插入到块大小为128个页面的链表中。如果在块大小为256个页面的链表中也没有找到空闲页面，就继续找更大的块，即512个页面的块。如果存在这样的块，内核就从512个页面的块中分出128个页面满足要求，然后从384个页面取出256个页面插入到块大小为256个页面的链表中，然后把剩下128个页面插入到块大小为128个页面的链表中。如果512个页面的链表中还没有空闲块，该算法就放弃分配，并发出出错信号。

上述过程的反向过程就是块的释放过程。

满足两个条件的块称为伙伴: 两个块的大小相同，两个块的物理地址连续。迭代合并过程

slab 分配机制（解决内部碎片问题）

slab核心思想：

对象管理内存（简单说：你经常用什么我先给你创造一堆出来，你要用直接拿，不用放回来），使用对象的概念来管理内存。

slab分配器基本思想：

先利用页面分配器分配出单个或者一组连续的物理页面，然后在此基础上将整块页面分割成多个相等的小内存单元，以满足小内存空间分配的需要。当然，为了有效的管理这些小的内存单元并保证极高的内存使用速度和效率。

slab的对象/内存池思想

在内核中，经常会使用一些链表，链表中会申请许多相同结构的结构体，比如文件对象，进程对象等等，如果申请比较频繁，那么为它们建立一个内存池，内存池中都是相同结构的结构体，当想申请这种结构体时，直接从这种内存池中取一个结构体出来，是有用且速度极快的。一个物理页就可以作用这种内存池的载体，进而进行充分利用，减少了内部碎片的产生。

所以，Slab 相当于内存池思想，且是为了解决内碎片而产生的，slab的核心思想是以对象的观点管理内存。

slab中对象是什么？

所谓的对象就是存放一组数据结构的内存区，为便于理解可把对象看作内核中的数据结构（例如：task_struct, file_struct 等）。

相同类型的对象归为一类，每当要申请这样一个对象时，slab分配器就从一个slab列表中分配一个这样大小的单元出去，而当要释放时，将其重新保存在该列表中，而不是直接返回给伙伴系统，从而避免内部碎片。

cache是内存中的区域，而不是指硬件高速缓存

这种场景是非常多的，为了应对这种场景，slab为这样的对象创建一个cache，即缓存。每个cache所占的内存区又被划分多个slab，每个 slab是由一个或多个连续的页框组成。每个页框中包含若干个对象，既有已经分配的对象，也包含空闲的对象。

lab分配器的一个基本原则

slab分配器对不同长度内存是分档的，这是slab分配器的一个基本原则，按申请的内存的大小分配相应长度的内存。

这可以先参考kmalloc的实现，kmalloc申请的物理内存长度为参数size，它需要先根据这个长度找到相应的长度的缓存

slab分配器并非一开始就能智能的根据内存分档值分配相应长度的内存。每种cache对应一种长度的slab分配

slab与buddy系统的关系

互补的

slab系统与buddy系统所要解决的问题是互补的，一个解决外部碎片一个解决内部碎片，但事实上，slab在新建cache时同样需要用到buddy来为之分配页面，而在释放cache时也需要buddy来回收这此页面。也就是说，slab事实上是依赖buddy系统的。

实际还是伙伴系统分配物理页

从slab的分配可以知道，其实所有的内存最终还是要伙伴系统来分配，这里就可以知道，这些内存都是连续的物理页。

slab作为内核缓存对象

在某些情况下内核模块可能需要频繁的分配和释放相同的内存对象，这时候slab可以作为内核对象的缓存，当slab对象被释放时，slab分配器并不会把对象占用的物理空间还给伙伴系统。这样的好处是当内核模块需要再次分配内存对象时，不需要那么麻烦的向伙伴系统申请，而是可以直接在slab链表中分配一个合适的对象

原文链接：