伙伴系统（Buddy System）

一、为什么需要伙伴系统#

操作系统要管理物理内存，最直接的想法是维护一个空闲块链表，分配时遍历找到足够大的块，释放时插回去。问题来了：经过反复分配释放，内存里会散布各种大小的空闲块——128 KB 的、256 KB 的、1 MB 的——但它们彼此不连续，无法合并。当系统需要一块连续的 2 MB 内存时，明明总空闲量足够，却找不到一块能用的。这就是外部碎片（External Fragmentation）。

页级分配器对速度和碎片都极其敏感。Linux 每秒可能处理数万次页面分配和释放，分配延迟直接影响系统吞吐。同时，DMA 控制器要求物理连续的缓冲区，碎片化会让 DMA 分配频繁失败。

伙伴系统用一条规则同时解决这两个问题：所有块的大小都是 2 的幂次方。分配时，把大块一分为二直到大小合适；释放时，检查”伙伴”是否空闲，空闲就合并回去。因为只有相同大小的相邻块才能合并，合并判定变得极其简单——不需要扫描整个空闲列表，O(log N) 就能完成一次分配或释放。

二、现实类比#

想象一块巧克力。你要 4 格，但手里只有 8 格的，那就掰成两半，用一半，另一半放着。下次只要 2 格，就把 4 格的那半再掰一次。吃完了想还回去？看看旁边那半还在不在——还在就合回去变成 8 格，不在就先放着。合并可以递归：两半 4 格合成 8 格，两个 8 格再合成 16 格。

再看地产开发。一块 64 公顷的地，先分成两块 32 公顷的。东边那块卖掉了，西边继续分。后来东边那块退回来了，恰好西边也空着，两块 32 公顷的地重新合并成 64 公顷的大地块。关键约束：只有从同一块地分出来的两半才能合并，不能把不相邻的地拼在一起。

三、核心思想#

伙伴系统的核心是三个操作：分裂（Split）、分配（Allocate）、合并（Coalesce）。所有块的大小必须是 2 的幂次方（1、2、4、8、16……页），每个大小级别维护一条空闲链表。

flowchart TD A["64 KB 空闲"] --> B1["32 KB 空闲"] A --> B2["32 KB 空闲"] B1 --> C1["16 KB 空闲"] B1 --> C2["16 KB 已分配"] B2 --> C3["32 KB 空闲"] style A fill:#e8f5e9 style B1 fill:#e8f5e9 style B2 fill:#e8f5e9 style C1 fill:#e8f5e9 style C2 fill:#ffcdd2 style C3 fill:#e8f5e9

上图中，64 KB 的块先分裂成两个 32 KB 的伙伴，左边的 32 KB 又分裂成两个 16 KB 的伙伴。C2 被分配出去，其余保持空闲。

3.1 伙伴的定义#

两个块称为”伙伴”，当且仅当：

大小相同（都是 2^k）
物理地址相邻
由同一个 2^(k+1) 的块分裂而来

这个定义有一个优雅的数学性质：地址为 p、大小为 2^k 的块，其伙伴地址是 p XOR 2^k。用一条位运算就能找到伙伴，不需要维护任何额外的邻居映射。

3.2 分配流程#

将请求大小向上取整到最近的 2 的幂次方，得到目标阶（order）
检查该阶的空闲链表，有则直接取出
没有则从更高阶取一块，递归分裂直到目标阶
分裂产生的另一半挂入对应阶的空闲链表

3.3 释放流程#

计算释放块的伙伴地址：buddy = block_addr XOR (1 << order)
检查伙伴是否在对应阶的空闲链表中
伙伴空闲则从链表移除，合并成更高阶的块，order++，递归回到步骤 1
伙伴不空闲则将当前块挂入对应阶的空闲链表

3.4 数据结构#

每个阶维护一条空闲链表，外加一个位图记录每个块对的合并状态：

1
order 0 (1 页):   free_list → [A] → [B] → null
2
order 1 (2 页):   free_list → [C] → null
3
order 2 (4 页):   free_list → null
4
...
5
order N (2^N 页): free_list → [Z] → null
6

7
bitmap: 标记每个块对的伙伴是否空闲，用于 O(1) 判定能否合并

Linux 内核用 struct free_area 封装每个阶的空闲链表和位图，所有阶组成 struct zone 中的 free_area[MAX_ORDER] 数组。

3.5 复杂度分析#

操作	时间复杂度	说明
alloc	O(log N)	最坏情况从最高阶分裂到目标阶
free	O(log N)	最坏情况递归合并到最高阶
空间开销	O(N / 2^k)	每个阶一条链表 + 位图

N 是最大阶数。Linux 默认 MAX_ORDER = 11，即最大块 4 MB（2^10 页，每页 4 KB），所以实际操作最多 11 步，非常快。

3.6 内部碎片#

伙伴系统用 2 的幂次方对齐，必然产生内部碎片——分配到的块比请求的大。最坏情况：请求 33 KB，向上取整到 64 KB，浪费近一半。平均内部碎片率约为 25%（请求大小在 2^(k-1)+1 到 2^k 之间均匀分布时，期望浪费 25%）。

这是伙伴系统最明显的代价：用内部碎片换取外部碎片的消除和 O(log N) 的操作速度。

四、变体与对比#

4.1 伙伴系统 vs Slab 分配器#

维度	伙伴系统	Slab 分配器
分配粒度	页级（4 KB 的幂次方）	对象级（任意大小）
碎片类型	内部碎片（对齐浪费）	外部碎片（slab 内部）
适用对象	大块连续物理内存	固定大小的内核对象
合并能力	自动合并伙伴	slab 页面空闲时归还伙伴系统

Linux 两者都用：伙伴系统管理物理页面，Slab 在伙伴系统分配的页面上管理内核对象（inode、dentry、task struct 等）。Slab 向伙伴系统申请整页，对象用完后整页归还。这是分层设计的经典案例。

4.2 伙伴系统 vs 位图分配器#

位图分配器用每一位表示一个页面的占用状态，分配时扫描位图找连续空闲位。优点是精确知道每个页面的状态，缺点是分配大块连续内存时扫描代价高（O(N)）。伙伴系统用阶来组织，跳过不相关的阶，代价是 O(log N)。

4.3 二叉伙伴 vs Fibonacci 伙伴 vs 加权伙伴#

二叉伙伴（Binary Buddy）：每次一分为二，块大小是 2 的幂。最常见，Linux 用的就是这种
Fibonacci 伙伴：块大小遵循 Fibonacci 数列（1, 1, 2, 3, 5, 8, 13……），分裂和合并规则更复杂，但内部碎片更小
加权伙伴（Weighted Buddy）：允许非对称分裂（如 3<1>），进一步减少内部碎片，但数据结构和合并逻辑更复杂

实际生产中，二叉伙伴因为实现简单、位运算高效而占据绝对主流。Fibonacci 和加权伙伴主要停留在学术研究。

4.4 外部碎片 vs 内部碎片的权衡#

分配策略	外部碎片	内部碎片	合并复杂度
首次适应（First Fit）	严重	无	O(n) 扫描邻居
伙伴系统	无	最多 50%	O(log N) 位运算
Slab	slab 内有	对象对齐浪费	归还整页时合并

伙伴系统选择了”宁可浪费一点空间，也要保证分配速度和合并简单”的路线。在页级分配这个场景下，这个取舍是合理的——页面本身是 4 KB 对齐的，2 的幂次方对齐并不额外浪费太多。

五、多语言实现#

5.1 Go 实现#

1
package buddy
2

3
import "errors"
4

5
// BuddySystem 伙伴系统分配器
6
// 管理的内存大小必须是 2 的幂次方
7
type BuddySystem struct {
8
  size  int           // 总大小（字节数）
9
  order int           // 最高阶 = log2(size)
10
  free  [][]int       // free[order] = 该阶空闲块的起始偏移列表
11
  buddy map[int]int   // 起始偏移 → 所属阶，用于释放时查找
12
}
13

14
// NewBuddySystem 创建伙伴系统，size 必须是 2 的幂
15
func NewBuddySystem(size int) (*BuddySystem, error) {
16
  if size <= 0 || size&(size-1) != 0 {
17
    return nil, errors.New("size 必须是 2 的幂次方")
18
  }
19
  order := 0
20
  for s := size; s > 1; s >>= 1 {
21
    order++
22
  }
23
  bs := &BuddySystem{
24
    size:  size,
25
    order: order,
26
    free:  make([][]int, order+1),
27
    buddy: make(map[int]int),
28
  }
29
  // 初始状态：整块内存作为一个最高阶空闲块
30
  bs.free[order] = []int{0}
31
  return bs, nil
32
}
33

34
// Alloc 分配 size 字节，返回起始偏移
35
func (bs *BuddySystem) Alloc(size int) (int, error) {
36
  if size <= 0 {
37
    return 0, errors.New("size 必须大于 0")
38
  }
39
  // 向上取整到 2 的幂
40
  order := bs.sizeToOrder(size)
41
  if order > bs.order {
42
    return 0, errors.New("请求大小超过总容量")
43
  }
44
  // 从目标阶开始找空闲块，没有就分裂更高阶
45
  offset, err := bs.findOrSplit(order)
46
  if err != nil {
47
    return 0, err
48
  }
49
  bs.buddy[offset] = order
50
  return offset, nil
51
}
52

53
// Free 释放从 offset 开始的块
54
func (bs *BuddySystem) Free(offset int) error {
55
  order, ok := bs.buddy[offset]
56
  if !ok {
57
    return errors.New("无效的偏移量，该块未被分配")
58
  }
59
  delete(bs.buddy, offset)
60
  bs.tryMerge(offset, order)
61
  return nil
62
}
63

64
// sizeToOrder 将字节数转换为阶
65
func (bs *BuddySystem) sizeToOrder(size int) int {
66
  order := 0
67
  s := 1
68
  for s < size {
69
    s <<= 1
70
    order++
71
  }
72
  return order
73
}
74

75
// findOrSplit 在目标阶找空闲块，没有则分裂更高阶
76
func (bs *BuddySystem) findOrSplit(order int) (int, error) {
77
  // 当前阶有空闲块，直接取出
78
  if len(bs.free[order]) > 0 {
79
    offset := bs.free[order][0]
80
    bs.free[order] = bs.free[order][1:]
81
    return offset, nil
82
  }
83
  // 已到最高阶，无法再分裂
84
  if order == bs.order {
85
    return 0, errors.New("内存不足")
86
  }
87
  // 从更高阶取一块，分裂成两个伙伴
88
  higher, err := bs.findOrSplit(order + 1)
89
  if err != nil {
90
    return 0, err
91
  }
92
  // 分裂：左半块分配给调用方，右半块挂入当前阶空闲链表
93
  buddyOffset := higher + (1 << uint(order))
94
  bs.free[order] = append(bs.free[order], buddyOffset)
95
  return higher, nil
96
}
97

98
// tryMerge 尝试与伙伴合并，递归向上
99
func (bs *BuddySystem) tryMerge(offset int, order int) {
100
  // 已到最高阶，无法再合并
101
  if order == bs.order {
102
    bs.free[order] = append(bs.free[order], offset)
103
    return
104
  }
105
  // 计算伙伴地址：异或当前阶的大小
106
  buddyOffset := offset ^ (1 << uint(order))
107
  // 在当前阶空闲链表中查找伙伴
108
  found := false
109
  for i, freeOffset := range bs.free[order] {
110
    if freeOffset == buddyOffset {
111
      // 找到伙伴，从空闲链表移除
112
      bs.free[order] = append(
113
        bs.free[order][:i],
114
        bs.free[order][i+1:]...,
115
      )
116
      found = true
117
      break
118
    }
119
  }
120
  if found {
121
    // 合并后递归尝试更高阶合并
122
    mergedOffset := min(offset, buddyOffset)
123
    bs.tryMerge(mergedOffset, order+1)
124
  } else {
125
    // 伙伴不空闲，挂入当前阶
126
    bs.free[order] = append(bs.free[order], offset)
127
  }
128
}
129

130
func min(a, b int) int {
131
  if a < b {
132
    return a
133
  }
134
  return b
135
}

5.2 TypeScript 实现#

1
/**
2
 * 简化版伙伴系统，用于缓冲区管理
3
 * 管理的内存大小必须是 2 的幂次方
4
 */
5
class BuddyAllocator {
6
  private order: number;
7
  private free: Set<number>[];  // free[order] = 该阶空闲块起始偏移集合
8
  private allocated: Map<number, number>; // 偏移 → 阶
9

10
  constructor(private size: number) {
11
    if (size <= 0 || (size & (size - 1)) !== 0) {
12
      throw new Error("size 必须是 2 的幂次方");
13
    }
14
    this.order = Math.log2(size);
15
    this.free = Array.from({ length: this.order + 1 }, () => new Set<number>());
16
    this.allocated = new Map();
17
    // 初始：整块内存作为最高阶空闲块
18
    this.free[this.order].add(0);
19
  }
20

21
  // 分配 size 字节，返回起始偏移
22
  alloc(size: number): number {
23
    if (size <= 0) throw new Error("size 必须大于 0");
24
    const order = this.sizeToOrder(size);
25
    if (order > this.order) throw new Error("请求超过总容量");
26

27
    const offset = this.findOrSplit(order);
28
    this.allocated.set(offset, order);
29
    return offset;
30
  }
31

32
  // 释放偏移量 offset 处的块
33
  free(offset: number): void {
34
    const order = this.allocated.get(offset);
35
    if (order === undefined) throw new Error("无效偏移，该块未分配");
36
    this.allocated.delete(offset);
37
    this.tryMerge(offset, order);
38
  }
39

40
  // 字节数转阶
41
  private sizeToOrder(size: number): number {
42
    let order = 0;
43
    let s = 1;
44
    while (s < size) {
45
      s <<= 1;
46
      order++;
47
    }
48
    return order;
49
  }
50

51
  // 在目标阶找空闲块，没有则分裂更高阶
52
  private findOrSplit(order: number): number {
53
    const freeSet = this.free[order];
54
    if (freeSet.size > 0) {
55
      // 取出任意一个空闲块
56
      const offset = freeSet.values().next().value;
57
      freeSet.delete(offset);
58
      return offset;
59
    }
60
    if (order === this.order) {
61
      throw new Error("内存不足");
62
    }
63
    // 从更高阶分裂
64
    const higher = this.findOrSplit(order + 1);
65
    // 右半块挂入当前阶
66
    const buddyOffset = higher + (1 << order);
67
    this.free[order].add(buddyOffset);
68
    return higher;
69
  }
70

71
  // 尝试与伙伴合并
72
  private tryMerge(offset: number, order: number): void {
73
    if (order === this.order) {
74
      this.free[order].add(offset);
75
      return;
76
    }
77
    // 伙伴地址 = offset XOR 2^order
78
    const buddyOffset = offset ^ (1 << order);
79
    if (this.free[order].has(buddyOffset)) {
80
      // 伙伴空闲，合并
81
      this.free[order].delete(buddyOffset);
82
      const mergedOffset = Math.min(offset, buddyOffset);
83
      this.tryMerge(mergedOffset, order + 1);
84
    } else {
85
      this.free[order].add(offset);
86
    }
87
  }
88

89
  // 调试用：打印各阶空闲状态
90
  debug(): string {
91
    const lines: string[] = [];
92
    for (let o = 0; o <= this.order; o++) {
93
      const blocks = Array.from(this.free[o]).sort((a, b) => a - b);
94
      const blockSize = 1 << o;
95
      lines.push(
96
        `order ${o} (${blockSize}B): [${blocks.join(", ")}]`
97
      );
98
    }
99
    return lines.join("\n");
100
  }
101
}
102

103
// 使用示例：缓冲区池
104
const pool = new BuddyAllocator(1024); // 1 KB 缓冲区
105
const a = pool.alloc(100);  // 分配 128 字节（order 7）
106
const b = pool.alloc(200);  // 分配 256 字节（order 8）
107
console.log(pool.debug());
108
pool.free(a);
109
pool.free(b);
110
console.log(pool.debug()); // 释放后应合并回 1 KB

六、生产验证#

项目	源码位置	用途
Linux 内核	mm/page_alloc.c	`__alloc_pages` / `free_pages`，伙伴系统核心实现，管理所有物理页面
Linux DMA	kernel/dma/contiguous.c	DMA 连续缓冲区分配，底层依赖伙伴系统保证物理连续
FreeBSD	vm/vm_kern.c	内核 malloc 大块分配使用伙伴系统

Linux 内核的伙伴系统实现在 mm/page_alloc.c 中，核心函数是 __alloc_pages() 和 free_pages()。每个内存域（zone）维护 free_area[MAX_ORDER] 数组，free_area[i] 包含一条空闲链表和一个位图。分配时从目标阶向上搜索，找到空闲块后向下分裂；释放时用位运算计算伙伴地址，检查位图判定能否合并。

DMA 控制器无法使用 IOMMU 时（或配置了 CMA 区域），必须分配物理连续的缓冲区。伙伴系统是唯一能保证物理连续性的内核分配器，因此 DMA 分配最终都走伙伴系统。

FreeBSD 的内核 malloc 对大块请求（超过页面大小的 2 的幂次方）也使用伙伴系统，小块则用 slab 风格的内存区分配器。

七、小结#

何时使用：

操作系统内核——物理页面分配，需要快速分配/释放和自动合并
DMA 缓冲区——要求物理连续内存，伙伴系统天然保证
大块内存管理——2 的幂次方对齐的大块分配场景
需要确定性延迟——O(log N) 的分配释放时间可预测

何时不用：

小对象分配——内部碎片浪费严重，用 Slab 更合适
任意大小请求——2 的幂次方对齐导致平均 25% 的空间浪费
需要精确大小匹配——用首次适应或最佳适应算法
单线程小规模场景——伙伴系统的数据结构开销不值得

伙伴系统的精髓在于用规则的分裂和合并替代复杂的碎片整理。2 的幂次方约束让伙伴判定变成一条 XOR 运算，让合并变成递归向上检查，让分配变成从高阶向下分裂。这种简洁性是它在操作系统内核中屹立数十年的根本原因。

八、参考资料#

Linux 内核伙伴系统 - page_alloc.c 核心实现，free_area 数据结构
The Art of Computer Programming, Vol. 1 - Knuth, 1997, Section 2.5 系统论述伙伴系统
Buddy System Allocation - Peterson & Norman, 1977, 伙伴系统经典论文