伙伴系统：内存世界的「拼图大师」

项目源码：https://gitee.com/kkkred/thread-caching-malloc

一、为什么需要伙伴系统？内存管理的「痛点」与「破局」

1.1 内存分配的「终极难题」

在计算机程序运行时，内存是最珍贵的资源之一。程序需要动态申请内存（如创建对象、加载文件），并在使用完毕后释放。但内存分配并非简单的「给一块空间」，而是需要解决两个核心问题：

• ​​效率​​：如何快速找到满足大小的连续内存块？
• ​​碎片​​：释放后的内存可能被分割为大量小块，导致「有空间但无法使用」的困境（外部碎片）。

早期的内存管理方式（如「空闲链表」）虽然简单，但面对频繁的分配/释放操作时，效率极低。例如，当程序需要申请一个2KB的内存块时，空闲链表可能需要遍历所有节点才能找到合适的空间，时间复杂度高达O(n)。

1.2 伙伴系统的诞生：从「二分法」到「内存拼图」

1963年，曼彻斯特大学的计算机科学家 ​​K. J. Thurber​​ 在论文中首次提出了「伙伴系统」的原型。其核心思想源于「二分法」：将内存按2的幂次方（2^0, 2^1, 2^2...）分割成大小相等的块，每个块称为一个「伙伴」（Buddy）。这种设计天然解决了碎片问题——因为所有空闲块的大小都是2的幂次，合并时只需将相邻的同大小块合并为更大的块（父节点），形成一棵「伙伴树」。

​​关键洞察​​：通过限制内存块大小为2的幂次，伙伴系统将内存分配的复杂度从O(n)降低到O(log n)，同时极大减少了外部碎片。

二、伙伴系统的核心原理：从「分割」到「合并」的内存魔法

2.1 伙伴树的构建：内存的「二进制地图」

伙伴系统将整个内存区域视为一个大的「根节点」，其大小为2^n（n为整数）。当程序申请内存时，系统会沿着伙伴树的层级向下分割，直到找到大小等于或略大于申请容量的「叶子节点」（即具体的内存块）。

举个例子：假设物理内存总大小为2^10=1024KB（根节点），当程序申请513KB内存时：

1. 检查根节点的子节点（2^9=512KB）是否可用。512KB < 513KB，无法直接分配。
2. 继续分割根节点的父节点（但根节点已是最大块），因此需要将根节点分割为两个512KB的子节点（兄弟伙伴）。
3. 但512KB仍小于513KB，于是继续分割其中一个512KB为两个256KB的子节点，依此类推，直到得到一个≥513KB的块（实际是1024KB的根节点）。

​​数学规律​​：对于任意大小S的内存申请，系统会找到最小的k，使得2^k ≥ S，然后将内存分割为2^k大小的块。

2.2 分配过程：从根到叶子的「精准搜索」

伙伴系统的分配流程可以用「查找-分割-标记」三步概括：

1. ​​查找空闲块​​：从根节点开始，检查当前层是否有足够大的空闲块。若有，直接分配；若没有，将父节点分割为两个子节点（伙伴），继续向下查找。
2. ​​分割伙伴块​​：每次分割将一个大小为2^k的块拆分为两个2^(k-1)的伙伴块，直到找到满足申请大小的块。
3. ​​标记为已用​​：分配的块被标记为「已使用」，并从空闲列表中移除。

2.3 释放过程：从叶子到根的「合并魔法」

释放内存时，伙伴系统需要将相邻的同大小「伙伴块」合并为更大的块，以减少碎片。合并规则如下：

1. ​​检查兄弟块​​：当释放一个大小为2^k的块时，检查其「兄弟块」（同一父节点的另一个子块）是否空闲。
2. ​​合并为父节点​​：如果兄弟块空闲，将两者合并为一个大小为2^(k+1)的父节点，并继续检查该父节点的兄弟节点是否空闲，直到无法合并为止。
3. ​​标记为空闲​​：最终合并后的块被加入对应大小的空闲列表。

​​反例警示​​：如果释放的块与兄弟块不连续（中间有其他已用块），则无法合并，只能作为独立块保留在空闲列表中。

三、代码实现：伙伴系统的「底层逻辑」

3.1 数据结构：空闲列表与伙伴树

伙伴系统的核心是维护不同大小的空闲块列表。通常，系统会为每个可能的块大小（2^0, 2^1...2^n）维护一个空闲链表（Free List）。例如，在Linux内核中，空闲列表用数组表示，数组下标对应块大小的指数（如index=k对应2^k大小的块）。

// 简化的伙伴系统空闲列表结构（C语言示例）
#define MAX_ORDER 10  // 最大块大小为2^10=1024KB
struct free_list {
    struct page *head;  // 空闲块的链表头
};
struct free_list free_area[MAX_ORDER];

3.2 关键函数：分配与释放的实现

分配函数（buddy_alloc）

// 申请大小为size的内存块（假设size是2的幂次）
struct page *buddy_alloc(size_t size) {
    int order = log2(size);  // 计算块大小的指数（如512KB→order=9）
    if (order > MAX_ORDER) return NULL;  // 超过最大支持大小
    
    // 从对应order的空闲列表查找块
    struct free_list *fl = &free_area[order];
    if (fl->head != NULL) {
        struct page *page = fl->head;
        fl->head = page->next;  // 从空闲列表移除
        return page;
    }
    
    // 无可用块，尝试从父节点分割
    for (int i = order; i < MAX_ORDER; i++) {
        struct free_list *parent_fl = &free_area[i];
        if (parent_fl->head != NULL) {
            struct page *parent_page = parent_fl->head;
            parent_fl->head = parent_page->next;  // 分割父节点
            
            // 将父节点拆分为两个子节点（伙伴）
            struct page *buddy1 = parent_page + (1 << (i-1));
            struct page *buddy2 = parent_page;
            
            // 初始化子节点的next指针
            buddy1->next = free_area[i-1].head;
            free_area[i-1].head = buddy1;
            buddy2->next = free_area[i-1].head;
            free_area[i-1].head = buddy2;
            
            // 返回较小的子节点（或任意一个）
            return buddy1;
        }
    }
    return NULL;  // 内存耗尽
}

释放函数（buddy_free）

// 释放大小为size的内存块（需传入块的起始地址和order）
void buddy_free(struct page *page, int order) {
    struct free_list *fl = &free_area[order];
    page->next = fl->head;
    fl->head = page;  // 加入空闲列表
    
    // 尝试合并兄弟块
    while (order < MAX_ORDER - 1) {
        int buddy_order = order + 1;
        struct page *buddy = get_buddy(page, order);  // 获取兄弟块地址
        
        // 检查兄弟块是否空闲且在同一父节点
        if (buddy && is_buddy_free(buddy, buddy_order)) {
            // 从空闲列表中移除兄弟块
            remove_from_freelist(buddy, buddy_order);
            
            // 合并为父节点（order+1）
            page = merge_pages(page, buddy, order);
            order = buddy_order;  // 继续向上合并
        } else {
            break;  // 无法合并，退出循环
        }
    }
}

3.3 辅助函数：兄弟块计算与状态检查

• get_buddy(page, order)：计算当前块的兄弟块地址。由于兄弟块在同一父节点中，地址差为2^(order)（例如，order=2时，块大小为4KB，兄弟块地址相差4KB）。
• is_buddy_free(buddy, order)：检查兄弟块是否空闲（存在于对应order的空闲列表中）。
• merge_pages(page1, page2, order)：将两个同大小的空闲块合并为一个更大的块，并更新父节点的空闲列表。

四、伙伴系统的优缺点：完美与局限的平衡

4.1 优势：高效与稳定的典范

• ​​低时间复杂度​​：分配和释放的时间复杂度均为O(log n)（n为最大块大小），远优于空闲链表的O(n)。
• ​​碎片控制​​：所有空闲块大小均为2的幂次，外部碎片几乎为零（仅可能存在无法合并的小块，但数量极少）。
• ​​可预测性​​：内存分配的结果仅与当前空闲状态有关，避免了随机碎片导致的性能波动。

4.2 局限：理想与现实的差距

• ​​内部碎片​​：如果程序申请的内存大小不是2的幂次（如申请3KB），系统会分配4KB的块，导致1KB的内部碎片。
• ​​复杂度​​：实现中需要维护多个空闲列表，并处理合并逻辑，代码复杂度较高。
• ​​最大块限制​​：内存总大小必须是2的幂次（或通过填充调整），否则无法充分利用空间（现代系统通过虚拟内存技术缓解此问题）。

五、实际应用：伙伴系统在操作系统与编程语言中的身影

5.1 操作系统内核：Linux的内存管理基石

Linux内核的内存管理（如物理页框分配）广泛使用伙伴系统。例如，buddy_alloc函数用于分配连续的物理页，而zone->free_area数组则维护不同大小的空闲块列表。这种设计保证了内核在处理进程内存申请时的高效性。

5.2 编程语言运行时：Java的堆内存优化

Java虚拟机（JVM）的堆内存管理中，虽然主要使用分代收集（Young/Old Generation），但在某些场景（如大对象直接分配）仍会借鉴伙伴系统的思想。例如，G1收集器的「Humongous Region」设计，本质上是对伙伴系统的改进，用于高效管理大对象。

5.3 嵌入式系统：资源受限下的最优解

在嵌入式设备（如单片机）中，内存资源极其有限，伙伴系统因其低开销和高可靠性成为首选。例如，STM32微控制器的内存分配库（如malloc实现）常基于伙伴系统，确保在几百KB内存中高效运行。

六、伙伴系统的进化：从经典到现代的改进

尽管伙伴系统经典，但现代技术对其进行了多维度改进：

6.1 伙伴系统+Slab分配器：解决小对象分配问题

Linux内核中，伙伴系统负责分配大内存块（≥4KB），而小对象（如进程描述符、文件句柄）则由Slab分配器管理。Slab分配器为每种对象预分配一组内存块（称为Slab），进一步减少分配延迟。

6.2 伙伴系统的「非2的幂次」变种

传统伙伴系统强制块大小为2的幂次，但现代变种（如Windows的「低碎片堆」）允许块大小为任意值，通过更复杂的合并策略（如允许不同大小的伙伴合并）降低内部碎片。

6.3 虚拟内存中的伙伴系统：突破物理内存限制

在虚拟内存环境下，伙伴系统可以管理虚拟地址空间（而非物理内存），通过页表映射将虚拟块映射到物理页框。这种设计允许程序使用比物理内存更大的地址空间，而碎片问题由操作系统通过换页机制解决。

结语：伙伴系统——内存世界的「永恒经典」

从1963年K. J. Thurber的论文到今天，伙伴系统已在内存管理领域深耕超过半个世纪。它用「二分法」的数学之美，解决了动态内存分配的核心矛盾；用「合并术」的巧妙设计，平衡了效率与碎片的矛盾。尽管面临Slab分配器、B+树索引等新技术的挑战，伙伴系统依然是操作系统、嵌入式开发中最可靠的「内存管家」。

下一次当你编写程序并调用malloc或new时，不妨想想：在内存的深处，可能正有一个伙伴系统在默默工作，用二进制的智慧，为你的代码分配着最合适的「拼图块」。