分配内核内存（buddy系统和slab系统）

先决条件—— 伙伴制

管理分配给内核进程的空闲内存的两种策略：

1.伙伴制-

伙伴分配系统（Buddy allocation system，简称Buddy allocation system，简称Buddy allocation system，简称Buddy allocation system，简称Buddy allocation system）是一种将较大的内存块划分为较小的部分以满足请求的算法。该算法用于给出最佳拟合。区块的两个较小部分大小相同，被称为伙伴。以同样的方式，两个伙伴中的一个将进一步分成更小的部分，直到请求得到满足。这种技术的好处是，两个伙伴可以根据内存请求组合成更大的块。

例如—— 如果请求25Kb，则分配大小为32Kb的块。

四种类型的好友系统——

1. 二进制伙伴系统
2. 斐波那契伙伴系统
3. 加权伙伴系统
4. 第三伙伴制

为什么是伙伴制？ 如果分区大小和进程大小不同，则会出现不匹配，并且可能会低效地使用空间。 它易于实现，效率高，然后是动态分配。

二进制伙伴系统– buddy系统维护一个每个大小的空闲块列表（称为空闲列表），以便在可用的情况下很容易找到所需大小的块。如果没有请求大小的块可用，则为至少请求大小的块分配第一个非空列表搜索。无论哪种情况，都会从空闲列表中删除一个块。

例如—— 假设内存段的大小最初为256kb，内核请求25kb的内存。该部分最初分为两个伙伴。我们把A1和A2的大小分别称为128kb。其中一个伙伴被进一步划分为两个64kb的伙伴，比如B1和B2。但25kb的次高幂是32kb，因此B1或B2进一步划分为两个32kb伙伴（C1和C2），最后使用其中一个伙伴来满足25kb的请求。拆分的块只能与其唯一的buddy块合并，然后buddy块将对拆分后的较大块进行重组。

斐波那契伙伴系统- 这是一个系统，其中块被划分为大小为斐波那契数。它满足以下关系：

  Zi = Z(i-1)+Z(i-2)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 144, 233, 377, 610. 二进制和加权好友系统的地址计算是直接的，但Fibonacci好友系统的原始过程要么局限于较小的、固定数量的块大小，要么是耗时的计算。

优势——

• 与动态分配等其他更简单的技术相比，伙伴存储系统几乎没有外部碎片。
• 伙伴内存分配系统使用二叉树来表示已使用或未使用的分割内存块。
• buddy系统分配或释放内存的速度非常快。
• 在伙伴系统中，分配和释放内存块的成本比最佳匹配算法或第一匹配算法低。
• 另一个优势是融合。
• 地址计算很容易。

什么是凝聚？ 它的定义是相邻的伙伴能以多快的速度结合成更大的片段，这就是所谓的结合。 例如，当内核释放分配给它的C1单元时，系统可以将C1和C2合并成64kb的段。这段B1可以依次与其伙伴B2合并，形成一个128kb的段。最终我们可以得到原来的256kb片段。

退税—— buddy系统的主要缺点是内部碎片，因为需要获取更大的内存块。例如，如果发出了一个36 kb的请求，那么它只能由64 kb的段来满足，剩余的内存将被浪费。

2.楼板分配-

第二种分配内核内存的策略称为slab分配。它消除了分配和解除分配造成的碎片。此方法用于保留包含特定类型数据对象的已分配内存，以便在后续分配相同类型的对象时重用。在slab分配中，预先分配适合于特定类型或大小的数据对象的内存块。Cache不会在使用后立即释放空间，尽管它会跟踪经常需要的数据，以便在发出请求时，数据会很快到达。所需的两个条款是：

• 板- 平板由一个或多个物理上连续的页面组成。slab是与特定类型的包含缓存的对象关联的数据的实际容器。
• 缓存– 缓存代表少量非常快的内存。缓存由一个或多个板组成。每个独特的内核数据结构都有一个单独的缓存。

例如——

• 用于表示进程描述符的数据结构的单独缓存
• 文件对象的单独缓存
• 信号量等的单独缓存。

每个缓存都填充有对象，这些对象是缓存所代表的内核数据结构的实例化。例如，代表信号量的缓存存储信号量对象的实例，代表流程描述符的缓存存储流程描述符对象的实例。

实施—— slab分配算法使用缓存来存储内核对象。创建缓存时，会将一些最初标记为空闲的对象分配给缓存。缓存中对象的数量取决于关联板的大小。 例如—— 一个12KB的平板（由三个连续的4KB页面组成）可以存储六个2KB的对象。最初，缓存中的所有对象都标记为空闲。当内核数据结构需要一个新对象时，分配器可以从缓存中分配任何空闲对象来满足请求。从缓存分配的对象被标记为已使用。

在linux中，slab可能处于以下三种状态之一：

1. 完整- 板中的所有对象都标记为已使用
2. 空的—— 板中的所有对象都标记为自由
3. 部分- 板由两部分组成

板分配器首先尝试使用部分板中的自由对象来满足请求。如果不存在自由对象，则从空板指定自由对象。如果没有可用的空板，将从连续的物理页分配一个新板，并将其分配给缓存。

平板分配器的好处——

• 不会因为碎片而浪费内存，因为每个唯一的内核数据结构都有一个关联的缓存。
• 内存请求可以很快得到满足。
• 在频繁分配或解除分配对象时，楼板分配方案尤其有效。分配和释放内存可能是一个耗时的过程。但是，对象是预先创建的，因此可以从缓存中快速分配。当内核处理完一个对象并将其释放后，它会被标记为空闲并返回其缓存，从而使其立即可用于内核的后续请求。