伙伴系统 - 2的幂次内存块的优雅分配与合并

📰 5W1H 发明者故事

Who（何人）- 发明者是谁？

发明者：哈里·诺尔顿（Harry Knowlton）
背景：

• 诺尔顿（生卒年不详）：美国数学家和计算机科学家，1965年在Bell实验室或相关机构工作
• 同期独立发现者：肯尼思·诺尔顿（Kenneth Knowlton，Bell实验室图形学先驱）和马克·丹尼尔（Mark Daniel）也对相关思想有贡献
• 高德纳（Knuth）在TAOCP第1卷2.5节中给出了伙伴系统的完整数学分析，使其广为人知

当时的处境：1960年代中期，计算机内存管理是一个重大挑战。程序需要动态分配不同大小的内存块，早期的"首次适配"和"最佳适配"算法会产生严重的内存碎片，导致虽然有足够总内存，却无法满足大内存请求。

When（何时）- 什么时候发明的？

时间：1965年
发表：Knowlton在1965年发表了伙伴系统的技术报告
时代背景：

• IBM System/360发布（1964年），引发操作系统设计的新浪潮
• 分时操作系统兴起，多个程序同时运行需要动态内存管理
• 虚拟内存概念正在发展，但分页系统尚不成熟
• 程序员开始意识到内存碎片是一个严重的系统性问题

Where（何地）- 在哪里发明的？

地点：美国，具体可能是AT&T Bell实验室或相关研究机构
环境：

• Bell实验室是当时美国最顶级的工业研究实验室
• Unix操作系统（1969年）的前身研究在此进行
• 多个关键操作系统内存管理技术在此期间被发明

What（何事）- 发明了什么？

算法：伙伴系统内存分配器（Buddy System Memory Allocator）
核心概念：所有内存块的大小都是2的幂次方。当分配k字节时，实际分配2^⌈log₂k⌉大小的块。当释放一个块时，检查其"伙伴"（相同大小、地址差为块大小的相邻块）是否也空闲，若是则合并成更大的块，递归向上合并。
关键特性：

• 2的幂次大小：所有块的大小都是2^n（n为整数）
• 伙伴关系：大小为2^n的块，其伙伴地址 = 当前地址 XOR 2^n
• 快速合并：判断伙伴的空闲状态只需查找对应链表，O(log n)时间
• 内部碎片有限：最坏情况浪费50%内存（分配刚超过2^(n-1)时）

Why（何因）- 为什么发明？

要解决的问题：

1. 外部碎片：传统分配器产生大量小碎片，虽然总空闲内存够，却无法满足大块请求
2. 合并困难：传统方案合并释放的块需要扫描整个内存，效率低
3. 分配速度：需要O(log n)而非O(n)的分配和释放时间

伙伴系统的优势：

• 合并只需检查一个固定地址的伙伴，无需扫描
• 通过2的幂次约束，使得伙伴的地址可以通过位操作直接计算
• 对小对象（64字节~4096字节）效率极高

核心数学：若块的起始地址为A，大小为2^n，则伙伴地址为 A XOR 2^n（简单的位翻转！）

How（何果）- 如何实现？有什么影响？

数据结构：

free_lists[0] : 大小为 2^MIN_ORDER 的空闲块链表
free_lists[1] : 大小为 2^(MIN_ORDER+1) 的空闲块链表
...
free_lists[k] : 大小为 2^(MIN_ORDER+k) 的空闲块链表

分配大小为s的块：
1. 找到最小的2^n >= s
2. 从free_lists[n-MIN_ORDER]取一块
3. 若该链表为空，从更大的链表分裂（拆成两个伙伴，一个用，一个加入下一级链表）

释放地址为addr、大小为2^n的块：
1. 计算伙伴地址 = addr XOR 2^n
2. 若伙伴也空闲，合并成2^(n+1)的块，递归重复步骤1
3. 否则将当前块加入free_lists对应链表

历史影响：

• Linux内核的物理页框分配器（Zone allocator）使用伙伴系统
• Linux的伙伴系统是操作系统课程的标准教学内容
• FreeBSD、macOS的内核内存分配也借鉴了伙伴系统思想
• Knuth在TAOCP中证明了伙伴系统的平均利用率约为60%-80%

今天的使用：

• Linux内核源码：mm/page_alloc.c中的buddy allocator
• JVM的堆内存分配（部分GC实现）
• GPU内存管理（CUDA的内存分配器）
• 嵌入式实时操作系统（FreeRTOS等）

名言：Knuth在分析伙伴系统时写道，“伙伴系统的美妙之处不在于它完美，而在于它在简单性和效率之间取得了近乎完美的平衡。”

---

📝 自然语言需求定义

需求名称：实现伙伴系统内存分配器，支持2的幂次块分配、释放和相邻伙伴合并

功能需求（用精确的中文描述）

1. 初始化伙伴系统：将一块大内存分割成初始状态的伙伴系统

   • 输入：总内存大小（必须是2的幂次）
   • 操作：将整个内存块作为最大阶的单一空闲块
   • 输出：伙伴系统控制结构

2. 分配内存（buddy_alloc）：分配至少size字节的内存

   • 输入：请求大小（字节）
   • 操作：向上取整到2的幂次，从对应链表取块，若无则从更大的块分裂
   • 输出：内存指针，失败返回NULL

3. 释放内存（buddy_free）：释放之前分配的内存块

   • 输入：内存指针，块大小（或阶数）
   • 操作：计算伙伴地址，检查伙伴是否空闲，若是则合并，递归向上
   • 输出：无

4. 打印状态（buddy_print）：打印各阶空闲链表的状态

   • 输入：伙伴系统控制结构
   • 操作：对每个阶，打印该阶空闲块的数量和地址
   • 输出：打印到标准输出

5. 获取空闲内存量：计算当前总空闲内存字节数

   • 输入：伙伴系统控制结构
   • 输出：空闲内存字节数

6. 统计碎片：计算外部碎片（无法被使用的空闲内存）

   • 输入：伙伴系统，最大单次请求大小
   • 输出：无法满足该请求所导致的碎片比例

约束条件

• 最小块大小：MIN_BLOCK_SIZE = 16字节（或32字节）
• 最大块大小：MAX_BLOCK_SIZE（整个内存池）
• 块大小必须是2的幂次
• 使用静态数组模拟内存池（不依赖系统malloc管理被分配的内存）
• 伙伴地址计算：buddy_addr = block_addr XOR block_size

验收标准（必须可验证）

编号	测试场景（自然语言描述）	预期结果	验证方式
1	初始化1024字节伙伴系统	最高阶有一个空闲块，总空闲=1024	检查free_lists和总空闲量
2	分配64字节	成功返回非NULL指针，空闲量减少64	检查返回值和空闲量
3	连续分配多个不同大小的块	每次分配成功，总空闲量正确减少	累计分配量对比
4	释放后伙伴合并	释放一个块后，若伙伴空闲则合并	分配两个伙伴块，释放其中一个再释放另一个，验证合并
5	分配超出剩余容量	返回NULL，不崩溃	尝试分配超大块
6	分配-释放循环后内存恢复	多次分配释放后，总空闲=初始值	全部释放后检查空闲量
7	buddy_print输出可读	打印各阶空闲块数量	目测验证输出格式
8	请求大小向上取整到2的幂	请求17字节实际分配32字节	检查块大小计算

AI 生成提示

基于以上需求和验收标准，用标准C语言实现伙伴系统内存分配器。

要求：
1. 使用标准C99
2. 使用静态char数组作为内存池（memory_pool[POOL_SIZE]）
3. 用链表数组 free_lists[MAX_ORDER+1] 管理各阶空闲块
4. 块头部存储元数据（是否空闲、阶数）
5. 伙伴地址：buddy = addr XOR (1 << order) * MIN_BLOCK_SIZE
6. 在main函数中实现所有8个验收标准的测试用例
7. 测试通过输出 "✓ 测试X通过"，失败输出 "✗ 测试X失败"

核心函数：
- buddy_init(pool_size) - 初始化
- buddy_alloc(size) - 分配
- buddy_free(ptr, size) - 释放
- buddy_print() - 打印状态
- buddy_free_space() - 获取空闲量

---

💻 C语言实现文件

对应文件: buddy_system.c

编译运行:

gcc -Wall -std=c99 -o buddy_system_test buddy_system.c
./buddy_system_test

# 内存泄漏检测
valgrind --leak-check=full ./buddy_system_test

核心函数:

• buddy_init() - 初始化内存池
• buddy_alloc(size) - 分配内存（自动向上取整）
• buddy_free(ptr, size) - 释放并合并伙伴
• buddy_print() - 打印各阶空闲链表状态
• buddy_free_space() - 查询空闲总量