伙伴系统（Buddy System）详解​​

​​伙伴系统​​ 是一种 ​​高效管理物理内存的算法​​，核心思想是将内存划分为大小相等的块，并按 2 的幂次方分层组织，从而快速分配和释放内存，同时减少碎片。它广泛应用于操作系统内核（如 Linux）、内存分配器（如 jemalloc 的 medium bins）和嵌入式系统中。

---

​​1. 核心原理​​

​​（1）内存块的分层组织​​

• 内存被划分为 ​​大小不同的块​​，每个块的大小是 2 的幂次方（如 1KB、2KB、4KB、…）。
• 每一层（order）维护一个 ​​空闲链表​​，存储当前大小的可用块。
  • 例如：order=0（1KB）、order=1（2KB）、order=2（4KB）……

​​（2）分配内存的流程​​

1. ​​计算请求大小的最小 2 的幂次方​​：
   • 例如：申请 3KB → 向上取整为 4KB（order=2）。
2. ​​查找对应 order 的空闲链表​​：
   • 如果当前 order 有空闲块，直接分配。
   • 如果无空闲块，向更大的 order 分裂：
     • 从 order=3（8KB）分裂为两个 4KB 块（“伙伴”），一个用于分配，另一个加入 order=2 的空闲链表。

​​（3）释放内存的流程​​

1. ​​释放块回到对应 order 的空闲链表​​。
2. ​​检查“伙伴块”是否空闲​​：
   • 如果伙伴块也空闲，合并为更大的块（如两个 4KB 合并为 8KB），递归向上合并。
   • 否则，仅将当前块加入链表。

---

​​2. 关键概念​​

​​（1）什么是“伙伴”？​​

• ​​定义​​：两个大小相同、地址连续且同属一个更大块的内存块互为伙伴。
• ​​示例​​：
  • 块 A（4KB，地址 0x0000）和块 B（4KB，地址 0x1000）是伙伴，因为它们由同一个 8KB 块分裂而来。
  • 合并时需满足：​​伙伴块必须同时空闲​​。

​​（2）分裂与合并的示例​​

• ​​初始状态​​：仅有一个 8KB 空闲块（order=3）。
• ​​分配 3KB（实际分配 4KB）​​：
  • 8KB 分裂为两个 4KB（A 和 B），A 被分配，B 加入 order=2 空闲链表。
• ​​释放 A（4KB）​​：
  • 检查 A 的伙伴 B 是否空闲。若 B 空闲，合并 A+B 为 8KB，回到 order=3。

---

​​3. 优缺点分析​​

​​✅ 优点​​

1. ​​快速分配/释放​​：通过幂次方分层，搜索复杂度为 O(1)。
2. ​​减少外部碎片​​：通过合并伙伴块，尽量保留大块连续内存。
3. ​​算法简单高效​​：适合实现操作系统底层内存管理。

​​❌ 缺点​​

1. ​​内部碎片​​：分配大小必须向上取整（如 3KB → 4KB，浪费 1KB）。
2. ​​合并条件苛刻​​：仅当伙伴块空闲时才能合并，可能导致碎片残留。
3. ​​不适合小对象​​：对微小内存（如几十字节）的管理效率低。

---

​​4. 实际应用​​

​​（1）Linux 内核的内存管理​​

• ​​页分配器​​：Linux 使用伙伴系统管理物理内存页（通常 4KB 一页）。
• ​​alloc_pages()​​：内核函数，按 order 分配连续物理页。

​​（2）jemalloc 的 medium bins​​

• jemalloc 对中等对象（如 4KB~16KB）采用类似伙伴系统的策略，按 2 的幂次方分块。

​​（3）嵌入式系统​​

• 资源受限设备（如 RTOS）常用伙伴系统管理内存，因其开销低。

---

​​5. 代码示例（简化版）​​

#define MAX_ORDER 10  // 最大块大小：2^10 = 1024KB

struct free_area {
    struct list_head free_list;  // 空闲链表
    int nr_free;                // 空闲块数量
};

struct free_area free_areas[MAX_ORDER];  // 各阶的空闲区域

// 分配内存（简化版）
void* buddy_alloc(size_t size) {
    int order = ceil_log2(size);  // 计算最小满足的 order
    for (int i = order; i < MAX_ORDER; i++) {
        if (!list_empty(&free_areas[i].free_list)) {
            // 分裂更大的块
            while (i > order) {
                i--;
                split_block(i);  // 将块分裂为两个 i-1 阶的伙伴
            }
            return allocate_block(i);  // 分配当前阶的块
        }
    }
    return NULL;  // 内存不足
}

// 释放内存（简化版）
void buddy_free(void* addr, int order) {
    while (order < MAX_ORDER - 1) {
        buddy = find_buddy(addr, order);  // 找到伙伴块
        if (buddy_is_free(buddy, order)) {
            merge_blocks(addr, buddy);    // 合并伙伴块
            order++;
        } else {
            break;
        }
    }
    add_to_free_list(addr, order);       // 加入空闲链表
}

---

​​6. 总结​​

• ​​伙伴系统​​ 通过 ​​2 的幂次方分层​​ 和 ​​伙伴块合并​​，实现高效的内存管理。
• ​​适用场景​​：
  • 需要快速分配连续内存的场景（如操作系统、嵌入式系统）。
  • 中大型内存块管理（如 jemalloc 的 medium bins）。
• ​​不适用场景​​：
  • 微小内存分配（需结合 slab 分配器）。
  • 高内部碎片敏感的应用。

​​核心价值​​：在内存分配速度与碎片控制之间取得平衡，是许多系统级内存管理的基础。