深入剖析 Linux 伙伴系统：内存管理的基石

引言：内存管理与伙伴系统的地位

在现代操作系统中，内存管理是支撑系统运行的核心支柱之一。它不仅决定了资源利用的效率，还直接影响性能、稳定性和应用程序的体验。在 Linux 内核中，内存管理通过分层设计实现了高效与灵活的平衡，其中 伙伴系统（Buddy System） 是物理内存分配的基础机制。无论是用户态程序通过 malloc() 请求内存，还是内核态创建进程描述符、分配文件缓冲区，背后都离不开伙伴系统的支持。

伙伴系统最早由 Kenneth C. Knowlton 在 1965 年提出，旨在解决动态内存分配中的外部碎片问题。Linux 内核借鉴并优化了这一思想，使其成为内存管理的基石。与用户态的动态分配器（如 glibc 的 malloc）不同，伙伴系统专注于物理页面级别的管理，以简单而高效的方式分配和回收内存块。这种设计不仅适用于通用计算场景，也在嵌入式系统和高性能计算中表现出色。

本文将深入剖析 Linux 伙伴系统的设计原理、实现细节、优缺点，以及它在实际场景中的应用。我们将从基础概念入手，逐步探讨其内核实现，与 Slab 系统的协作，优化方法，以及与其他内存管理算法的对比。无论你是内核开发者、系统管理员，还是对操作系统感兴趣的学习者，这篇文章都将为你提供全面而深入的视角。

伙伴系统的基本原理

什么是伙伴系统？

伙伴系统是一种基于页面（page）的内存分配算法，其核心思想是将物理内存划分为大小为 2 的幂次方倍数 的块，并通过“伙伴关系”管理这些块的分配与回收。在 Linux 中，伙伴系统的最小单位是物理页面，通常为 4KB（取决于架构和配置），分配的内存块大小是页面数的 2 的幂次方倍数，例如 1 页（4KB）、2 页（8KB）、4 页（16KB），等等。

“伙伴”这一术语是伙伴系统的灵魂所在，指的是两个大小相同、地址相邻的内存块，它们可以合并成一个更大的块。例如，两个相邻的 4KB 块在释放时可以合并为一个 8KB 块，这种合并机制是伙伴系统减少外部碎片的关键。通过这种方式，伙伴系统在内存分配和回收中保持了高效性和一致性。

为什么选择 2 的幂次方分配？

伙伴系统选择 2 的幂次方作为分配单位并非随意决定，而是基于硬件和算法设计的深思熟虑：

1. 硬件兼容性
   现代计算机的内存管理单元（MMU）通常以 2 的幂次方页面大小操作，例如 4KB（标准页面）、2MB（大页面）、1GB（超大页面）。伙伴系统的设计与这种硬件特性天然契合，避免了额外的对齐开销。

2. 算法简单性
   2 的幂次方允许使用位运算（如左移、右移、按位与）快速计算内存块的大小和地址。例如，给定一个 4KB 块的起始地址，找到其伙伴只需通过位运算 addr ^ (1 << order)，其中 order 表示块的大小级别（order 0 为 1 页，order 1 为 2 页，依次类推）。这种高效性对内核尤为重要，因为内存分配是高频操作。

3. 合并效率
   只有大小相同且地址对齐的块才能成为伙伴，这种规则简化了合并逻辑。如果内存块大小不按 2 的幂次方划分，合并将变得复杂，可能导致更多的外部碎片。2 的幂次方保证了对称性和可预测性，使得伙伴系统在回收时能快速还原大块内存。

例如，假设系统有 16KB 的连续内存（地址 0x0 到 0x3FFF），分配一个 4KB 块（0x0 - 0xFFF）后，剩余 12KB 可以继续按 2 的幂次方分割。如果释放这个 4KB 块，且其伙伴（0x1000 - 0x1FFF）也空闲，系统会合并它们为 8KB（0x0 - 0x1FFF），依此类推。

核心概念：伙伴关系与合并

伙伴系统的核心在于“伙伴关系”和“合并机制”，它们共同定义了系统的行为：

• 伙伴定义
  对于一个大小为 2^k 个页面的内存块，其伙伴是与之相邻的另一个 2^k 大小的块，且它们共同组成一个 2^(k+1) 的块。例如，一个 4KB 块（order 0）的伙伴是相邻的另一个 4KB 块，合并后成为 8KB（order 1）。伙伴的地址通过位运算计算，确保对齐和邻接。

• 合并规则
  当两个伙伴块都空闲时，系统会将它们合并为一个更大的块，这一过程递归进行，直到无法找到空闲的伙伴为止。这种机制有效减少了外部碎片，即内存中分散的小块空闲空间无法满足大请求的问题。

举个具体例子：

• 系统初始化时有 32KB 内存（0x0 - 0x7FFF）。
• 分配一个 8KB 块（0x0 - 0x1FFF），剩余 24KB。
• 再分配一个 4KB 块（0x2000 - 0x2FFF），剩余 20KB。
• 释放 4KB 块后，检查其伙伴（0x3000 - 0x3FFF）。如果伙伴空闲，合并为 8KB（0x2000 - 0x3FFF）。
• 如果 8KB 的伙伴（0x0 - 0x1FFF）也空闲，进一步合并为 16KB（0x0 - 0x3FFF）。

这种递归合并确保了内存的连续性，是伙伴系统区别于其他分配算法的关键特性。

Linux 中的伙伴系统实现

数据结构：空闲链表与页面管理

在 Linux 内核中，伙伴系统通过精心设计的数据结构实现高效的内存管理。以下是主要组件：

1. 空闲链表（Free List）

   • 内核为每种大小的内存块维护一个空闲链表，分别对应不同的 “order”。例如，order 0 表示 1 页（4KB），order 1 表示 2 页（8KB），order 2 表示 4 页（16KB），最高通常到 order 10（1024 页，4MB）。
   • 这些链表存储当前空闲的内存块，使用 free_area 结构体管理：

     struct free_area {
         struct list_head free_list; // 双向链表，存储空闲块
         unsigned long nr_free;      // 该 order 的空闲块数量
     };

   • 空闲链表按内存区域（Zone）组织，例如 ZONE_DMA（低端内存）、ZONE_NORMAL（常规内存）、ZONE_HIGHMEM（高端内存），确保分配满足硬件约束。

2. 页面描述符（struct page）

   • 每个物理页面由一个 struct page 结构体表示，包含其状态信息（如是否分配、所属 order 等）。
   • 对于伙伴系统，struct page 的字段（如 flags 和 private）记录了页面是否空闲及其伙伴信息。
   • 示例部分字段：

     struct page {
         unsigned long flags;    // 页面状态（如 PG_buddy 表示空闲）
         unsigned long private;  // 存储 order 值
         struct list_head lru;  // 用于链表链接
     };

3. 内存区域（Zone）

   • Linux 将物理内存划分为多个 Zone，每个 Zone 包含独立的伙伴系统实例。这种设计隔离了不同类型内存（如 DMA 专用内存），提高了管理的灵活性。

这些数据结构共同构成了伙伴系统的运行基础，确保分配和回收操作的高效性。

分配过程详解

伙伴系统的分配过程是一个自顶向下的查找和分割流程，以下是详细步骤：

1. 确定请求大小

   • 用户或内核通过函数如 alloc_pages(order) 请求一定数量的页面。例如，请求 3 页，系统向上取整到 4 页（order 2）。
   • order 是 2 的幂次方指数，计算公式为 order = ilog2(request_size - 1) + 1。

2. 查找空闲块

   • 从目标 order 的空闲链表开始检查。例如，请求 order 2（4 页），检查 free_area[2].free_list。
   • 如果该链表为空，向上查找更大的块（如 order 3，8 页），直到找到可用块或达到最大 order（通常 10）。

3. 分割内存

   • 如果找到一个 8 页的块（order 3），将其一分为二，得到两个 4 页块（order 2）。
   • 将一个 4 页块分配给请求者，另一个放回 order 2 的空闲链表。
   • 分割过程递归进行，直到块大小匹配请求的 order。

4. 更新状态

   • 修改分配块的 struct page，将 flags 设置为非空闲状态（如清除 PG_buddy），并记录分配信息。
   • 返回页面地址给调用者。

简化代码示例：

struct page *alloc_pages(unsigned int order) {
    struct free_area *area;
    int current_order = order;
    for (; current_order < MAX_ORDER; current_order++) {
        area = &zone->free_area[current_order];
        if (!list_empty(&area->free_list)) {
            struct page *page = list_first_entry(&area->free_list, struct page, lru);
            list_del(&page->lru);
            area->nr_free--;
            split_page(page, current_order, order); // 分割大块
            mark_page_allocated(page, order);
            return page;
        }
    }
    return NULL; // 无可用内存
}

释放与合并过程详解

释放过程是分配的逆操作，重点在于伙伴检查和合并：

1. 标记空闲

   • 调用 free_pages(page, order) 释放页面，将 struct page 的 flags 设置为 PG_buddy，标记为空闲。

2. 查找伙伴

   • 计算伙伴地址。例如，对于 order 0（4KB）块，伙伴地址为 page_addr ^ (PAGE_SIZE << order)。
   • 检查伙伴是否空闲（通过 page_is_buddy() 判断）。

3. 合并检查

   • 如果伙伴空闲，从各自的链表中移除，合并为一个更大的块（order + 1）。
   • 递归检查新块的伙伴，直到无法合并（伙伴不空闲或达到最大 order）。

4. 放回链表

   • 将最终的空闲块加入对应 order 的空闲链表，更新 nr_free。

简化代码示例：

void free_pages(struct page *page, unsigned int order) {
    while (order < MAX_ORDER - 1) {
        struct page *buddy = page + (1 << order); // 计算伙伴地址
        if (!page_is_buddy(buddy, order))
            break;
        list_del(&buddy->lru); // 从链表移除伙伴
        zone->free_area[order].nr_free--;
        page = min(page, buddy); // 合并后取低地址
        order++;
    }
    list_add(&page->lru, &zone->free_area[order].free_list);
    zone->free_area[order].nr_free++;
}

页面大小与架构依赖

伙伴系统的最小单位是页面，其大小取决于架构和内核配置：

• 默认值：x86 上为 4KB，由 PAGE_SIZE 定义。
• 可变性：ARM 等架构支持 1KB、4KB、64KB，通过编译时选项（如 CONFIG_PAGE_SIZE）调整。
• 影响：页面大小决定了分配粒度和碎片特性。小页面（如 1KB）减少内部碎片，但增加 struct page 的内存开销；大页面（如 64KB）适合大块分配，但可能加剧碎片。

在实践中，4KB 是性能与兼容性的折中选择，广泛应用于桌面和服务器系统。

伙伴系统的优点与局限性

优点：简单、高效、减少外部碎片

1. 简单性

   • 伙伴系统的算法逻辑清晰，基于 2 的幂次方和伙伴关系，易于实现和维护。位运算的使用进一步降低了计算开销，使得分配和回收操作快速。

2. 高效性

   • 空闲链表的设计使得查找可用块的时间复杂度接近 O(1)，分割和合并也只需 O(log n)（n 为最大 order）。这对高频内存请求至关重要。

3. 减少外部碎片

   • 通过递归合并，伙伴系统能将分散的小块空闲内存重组为大块，满足大内存请求。例如，释放多个 4KB 块后，可能合并为 16KB，避免了内存“散沙化”。

局限性：内部碎片与大块内存挑战

1. 内部碎片问题

   • 由于分配单位是 2 的幂次方页面，请求大小不匹配时会产生浪费。例如，请求 5KB 被分配 8KB（2 页），多出 3KB 是内部碎片。
   • 对于小内存请求（< 4KB），伙伴系统直接分配一页，导致大量浪费。这也是 Slab 系统存在的原因。

2. 大块内存挑战

   • 系统运行时间长或内存使用频繁时，即使总空闲内存足够，也可能找不到足够大的连续块。例如，请求 1MB（256 页，order 8）可能失败，因为空闲页面被分散为小块，且伙伴未同时空闲。
   • 这种情况称为“外部碎片残留”，虽然伙伴系统通过合并缓解了这个问题，但无法完全消除。

3. 性能与复杂性的权衡

   • 伙伴系统的简单性牺牲了一定灵活性。它不适合动态大小的分配，只能提供固定粒度的块，依赖上层机制（如 Slab）处理小对象。

伙伴系统与 Slab 系统的协作

Slab 系统简介

伙伴系统的局限性催生了 Slab 系统，它是 Linux 内核中管理小块内存的高效机制。Slab 从伙伴系统获取页面，将其切分为固定大小的对象（object），供内核和用户态使用。

• 核心结构：

  • Cache：缓存特定类型对象，例如 kmalloc-64（64 字节）、task_struct（进程描述符）。
  • Slab：由一或多页组成，包含多个对象，分为 Full、Partial、Empty 三种状态。
  • Object：最小分配单位，精确匹配请求大小。

• 工作流程：

  • 分配：从 Partial slab 取对象，无则从 Empty slab 或伙伴系统获取。
  • 释放：标记对象为空闲，更新 slab 状态，必要时归还页面。

如何弥补伙伴系统的不足

1. 减少内部碎片

   • 伙伴系统分配 4KB 页面给 Slab，Slab 将其切分为小对象。例如，请求 64 字节，Slab 返回 64 字节对象，而不是 4KB，浪费仅限于元数据。

2. 提升小块分配效率

   • Slab 预分配和缓存对象，避免了频繁调用伙伴系统。例如，kmalloc(100) 从 kmalloc-128 缓存直接返回，速度远超页面分配。

3. 对象重用

   • 释放的对象保留初始化状态（如进程描述符的字段），重用时无需重新构造，适合内核频繁分配的场景。

实际案例分析

假设内核创建新进程：

• task_struct 大小约为 1.5KB。
• 伙伴系统分配 4KB（1 页），浪费 2.5KB。
• Slab 系统接管，创建 task_struct 缓存，每个对象 1.5KB，一个 4KB 页面可容纳 2 个对象加元数据，浪费仅数百字节。

伙伴系统的优化与扩展

内核参数调优

1. 页面大小调整

   • 通过 CONFIG_PAGE_SIZE 改为 1KB，减少小块请求的 Fragments。但 struct page 数量增加，内存开销上升。
   • 适用于嵌入式系统，通用服务器仍倾向 4KB。

2. Zone 管理

   • 调整 /proc/sys/vm/ 参数（如 min_free_kbytes），确保伙伴系统保留足够空闲内存，避免碎片累积。

多级伙伴系统（Huge Pages）

• 原理：支持大页面（如 2MB、1GB），减少 TLB 开销和碎片。
• 实现：伙伴系统扩展到更高 order（如 order 9，512 页），通过 alloc_pages() 分配。
• 应用：数据库、虚拟化场景，显著提升性能。

实时系统中的改进

• 预留内存：为实时任务保留连续大块，减少分配延迟。
• 延迟合并：释放时不立即合并，降低实时操作的中断。

伙伴系统在实际场景中的应用

通用计算中的角色

在桌面和服务器中，伙伴系统管理物理内存，为文件缓存、进程堆栈等提供支持。其简单性和高效性适合动态负载。

嵌入式系统中的适配

嵌入式设备内存有限，伙伴系统通过小页面（如 1KB）和 SLOB（简化的 Slab）适配低资源环境。

高性能计算中的挑战

HPC 需要大块连续内存，伙伴系统可能因碎片不足以应对，需结合 Huge Pages 或自定义分配器。

与其他内存管理算法的对比

1. 伙伴系统 vs. 动态分配

   • 动态分配（如 malloc 的底层 ptmalloc）支持任意大小，灵活但复杂，碎片管理依赖垃圾回收。
   • 伙伴系统固定粒度，简单高效，适合页面管理。

2. 伙伴系统 vs. 池分配

   • 内存池预分配固定大小块，类似 Slab，但局限于特定应用。伙伴系统更通用，动态性强。

3. 优劣分析

   • 伙伴系统胜在简单和外部碎片控制，输在内部碎片和灵活性。

未来发展趋势与思考

1. 硬件支持演进
   • 更大页面（如 1GB）普及，伙伴系统需扩展更高 order。
2. AI 与内存管理
   • 预测请求模式，优化分配减少碎片。
3. 改进方向
   • 混合算法，结合动态性和伙伴系统的优点。

结论

伙伴系统作为 Linux 内存管理的基石，以其简单、高效和外部碎片控制能力，支撑了系统的稳定运行。尽管存在内部碎片等局限，它通过与 Slab 系统协作，实现了性能与资源利用的平衡。对于开发者而言，理解伙伴系统不仅是掌握内核的关键，也是优化应用内存使用的起点。