3. 伙伴系统（Buddy System）：页分配器原理、order与free_area结构、内存碎片化问题

伙伴系统是 Linux 内核物理内存页分配的核心算法，负责管理连续物理页框的分配与回收。它通过将内存按 2 的幂次方分割成块（称为 order），有效平衡了分配速度与外部碎片问题。本节将深入剖析其数据结构、分配/释放流程以及固有的碎片化挑战。

3.1 核心数据结构：order 与 free_area

伙伴系统的管理数据位于每个内存节点（pg_data_t）的 free_area 数组中。该数组的索引即为 order（阶），每个元素对应一个特定大小的空闲块链表。

free_area 结构体包含两个核心成员：

• struct list_head free_list[MIGRATE_TYPES]：按迁移类型（MIGRATE_UNMOVABLE、MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE 等）分组的空闲块链表。同一 order 的空闲页块通过 page->lru 链接。
• unsigned long nr_free：当前 order 中空闲块的总数。

3.2 伙伴系统分配与释放流程

分配和释放均遵循“分裂-合并”的递归逻辑，确保相邻块能重新组合成更大的连续块。

3.2.1 分配流程（以请求 order=2 为例）

1. 查找空闲块： 从 free_area[2] 的链表中摘取一个空闲块。如果链表非空，直接返回。
2. 向上分裂： 如果 free_area[2] 为空，则查找 free_area[3]。找到后，将 order=3 的块分裂成两个 order=2 的伙伴块：一个返回给请求者，另一个插入 free_area[2] 链表。
3. 递归分裂： 若 free_area[3] 也为空，继续向 free_area[4] 查找，直到找到非空链表或达到 MAX_ORDER-1。
4. 分配失败： 若所有 order 均无空闲块，则触发内存回收或 OOM。

3.2.2 释放流程（以释放 order=2 块为例）

1. 查找伙伴： 计算当前释放块的伙伴地址。伙伴与当前块大小相同、物理地址相邻，且由同一个父块分裂而来。
2. 伙伴空闲检查： 检查伙伴块是否在 free_area[2] 链表中且未被分配。
3. 合并： 如果伙伴空闲，则从链表中摘除伙伴，将当前块与伙伴合并成一个 order=3 的块。
4. 递归合并： 将合并后的 order=3 块作为新块，继续向上查找其伙伴（order=3 级别），尝试进一步合并。
5. 插入空闲链表： 当无法继续合并时，将最终块插入对应 order 的 free_list。

3.3 伙伴系统分配与合并流程 SVG 图

3.4 内存碎片化问题

尽管伙伴系统通过合并机制缓解了外部碎片，但在长期运行的系统（尤其是嵌入式设备）中，碎片化仍然不可避免。主要分为两类：

3.4.1 外部碎片

指虽然总空闲内存足够，但无法分配出连续的物理大块。例如：系统有 10 个空闲页，但分散在 5 个不同的 order=0 块中，无法满足一个 order=2（4 页）的请求。

3.4.2 内部碎片

指分配出的块大于实际需求，造成块内空间浪费。例如：请求 3 页，伙伴系统只能分配 order=2（4 页）的块，浪费 1 页。

3.5 碎片化问题可视化 SVG 图

3.6 嵌入式环境下的碎片化应对策略

在内存资源受限的嵌入式系统中，碎片化可能导致关键驱动（如 DMA、显示控制器）分配大块连续内存失败。以下是常用优化手段：

• 迁移类型分组 (MIGRATE_TYPES)：将不可移动页、可回收页、可移动页分别放入不同链表，避免不可移动页阻塞大块连续内存的形成。
• 内存规整 (Memory Compaction)：通过扫描并迁移可移动页，将分散的空闲页合并成大块连续区域。内核通过 /proc/sys/vm/compact_memory 手动触发。
• 预分配大块内存池：在系统初始化阶段，通过 alloc_pages_exact() 或 CMA (Contiguous Memory Allocator) 预留连续内存区域，专供驱动使用。
• 调整 MAX_ORDER：对于内存极小的嵌入式设备（如 64 MB），可将 MAX_ORDER 从 11 降低到 8 或 9，减少管理链表开销，但会限制最大连续分配大小。
• 使用 slab 分配器：对于小于一页的小对象，绕过伙伴系统直接使用 slab，避免内部碎片。