Linux 内核的内存管理是一个复杂的系统，其中包含了多种机制来分配和回收内存。伙伴系统（Buddy System）是其中最核心的一种内存分配算法，用于管理物理内存的分配和回收。伙伴系统是一种高效的内存管理方式，能够解决内存碎片问题，并且能在较小的时间复杂度下进行内存分配和回收。
伙伴系统概述
伙伴系统的核心思想是将内存按照划分为多个大小为 2 的幂次方的块（页面），并将这些块分组管理。每一组内存块的大小是相同的，可以通过合并或拆分操作来满足不同大小的内存需求。每个内存块都有一个伙伴块，当两个块释放时，它们可以合并成一个更大的块。
关键概念
伙伴系统最小支持的内存大小通常为页面的大小，它取决于系统配置，最常见的是4KB。
- 块大小：内存块的大小是
2的幂次方（比如：4KB, 8KB, 16KB 等）。 - 伙伴块：每个内存块都有一个“伙伴块”，它是与当前内存块相邻的、大小相同的块。如果一个块被释放，它和其伙伴块可以合并成一个更大的块。
- 块分级：所有可用内存块被分为多个级别（通常是
2的幂次方），每个级别都有一个空闲块链表，表示该大小的块的所有空闲块。
伙伴系统的工作原理
伙伴系统的目标是高效地分配和回收内存。通过对内存块进行合并和拆分操作，尽可能减少内存碎片。以下是伙伴系统的基本工作流程：
内存分配
当需要分配内存时，系统会按照以下步骤进行：
- 查找适当大小的空闲块：系统首先会检查当前大小最小的块是否足够。如果不够，就会查找更大的块。
- 拆分块：如果找到的块比需要的块大，系统会将这个块拆分成两个大小相等的“伙伴块”。
- 分配块：直到找到足够大小的空闲块，系统将其分配给请求的进程。
- 更新空闲链表：分配后，空闲链表中相应大小的块数量减少。
内存回收
当内存不再需要时，系统会将其回收。回收操作如下：
- 合并伙伴块：首先检查当前块是否有伙伴块。如果有，且伙伴块也为空闲状态，则可以合并这两个块。合并后的块大小是原来块的两倍。
- 更新空闲链表：合并后，新的块会被插入到相应大小的空闲链表中。如果合并后的块仍然有更大的伙伴，可以继续合并，直到无法合并为止。
- 减少碎片：通过合并操作，系统尽可能减少内存碎片。
内存合并的限制
- 合并操作只能发生在物理上连续的块上，也就是说，伙伴系统依赖于物理连续内存。
- 因此，某些内存区域（例如高端内存）可能不会参与伙伴系统的管理，而由其他机制（如
vmalloc）进行管理。
伙伴系统的实现
Linux 内核的伙伴系统实现分为两大部分：空闲内存块的管理和内存分配与回收。
空闲内存块的管理
内核中的伙伴系统通过维护多个链表来管理不同大小的空闲内存块。这些链表中的每个条目表示该大小的所有空闲块。每个条目都指向该大小块的第一个空闲块，并且该链表使用双向链表结构来存储。
分配算法
伙伴系统使用首次适配（First Fit）算法来查找合适大小的内存块。具体过程如下：
- 查找：从空闲链表中查找最小的适合请求内存大小的块。
- 拆分：如果找到的块比需要的块大，则将其拆分成两个大小相等的伙伴块，直到找到大小合适的块。
- 分配：返回找到的块，并更新空闲链表。
回收算法
内存回收时，伙伴系统通过合并机制来减少碎片：
- 检查伙伴：当一个块被释放时，系统会检查其伙伴块是否也为空闲状态。
- 合并块：如果伙伴块为空闲状态，则将其与当前块合并成一个更大的块，合并后的块会被重新插入到空闲链表中。
- 递归合并：如果合并后的块仍然可以和另一个伙伴块合并，系统将继续进行合并操作。
伙伴系统的优缺点
优点
- 高效的内存分配：由于内存块的大小是 2 的幂次方，伙伴系统能够高效地管理内存，避免了过多的碎片。
- 较低的时间复杂度：伙伴系统的内存分配和回收操作一般是常数时间复杂度
O(1)，即使在高并发的情况下也能保持较高的性能。 - 内存合并减少碎片：通过合并机制，伙伴系统可以减少内存碎片问题，尽量将相邻的空闲块合并为较大的内存块。
缺点
- 内存浪费：由于内存块大小是 2 的幂次方，可能会导致内存分配时出现内存浪费。例如，如果请求的内存是 10KB，但系统只能提供 16KB 的块，则会浪费 6KB 的内存。
- 物理连续性限制：伙伴系统要求内存块必须是物理连续的，因此当内存碎片较多时，可能会无法找到足够大的连续内存块。
伙伴系统的底层实现
伙伴系统的底层实现通过一些关键数据结构来支持内存分配和回收：
- 链表：每个大小的内存块有一个对应的空闲链表，链表用于存储该大小的所有空闲块。
- 块合并和拆分：内存块的合并和拆分是通过管理空闲块的合并关系来实现的，通常使用一种二分查找的方法来查找合适大小的内存块。
- 标记位：内核通过标记每个内存块是否已被分配或空闲来管理内存。标记位有助于加速伙伴系统中空闲块的合并操作。
伙伴系统与 Linux 的 kmalloc
在 Linux 内核中，kmalloc 是基于伙伴系统实现的。kmalloc 通过查找适当的空闲内存块并使用伙伴系统进行分配来管理内存。kmalloc 适合分配小块内存（通常为 4KB 或更小），而当内存需求更大时，kmalloc 会使用更大的块（例如 8KB、16KB 等）。对于更大的内存块，内核会使用 vmalloc 或其他机制。
示例
4G内存分配流程
分配
- 内存从最小的
4KB块开始管理，分成多个4KB的块。 - 如果有一个程序请求分配
12KB的内存，系统将从4KB的块中分配三个块，或者找到一个更大的块（如16KB），然后分割成4KB的块来满足请求。
释放
- 如果一个程序释放了
12KB的内存，释放的块会合并回16KB，再根据需要合并成更大的块，直到最大块（如64KB等）。
总结
伙伴系统在内存管理中扮演着至关重要的角色，尤其是在物理内存分配中。它的优点是高效、简单，并能够有效减少内存碎片。然而，随着内存需求的多样化，伙伴系统的限制也日益显现，如内存浪费问题和物理连续内存的限制。Linux 内核的伙伴系统通过高效的内存分配、回收和合并策略，保障了系统的内存管理性能。