伙伴分配Buddy allocation
按 2 的幂管理内存块，按需拆分并合并伙伴。
- 核心约束
- 只有同阶且满足条件的伙伴块可合并。
- 适用问题
- 连续物理页分配与空闲块管理。
- 边界与取舍
- 块大小约束导致内部碎片；可用内存不等于可用连续大块。
常见操作#
G 为可用阶数范围；order 为请求的 2 的幂次页数。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 分配一块 | 按阶寻找空闲块，必要时逐级拆分；这里仅计伙伴链表路径。 | |
| 释放并合并 | 每阶只检查相应 buddy，满足同阶且空闲等条件时向上合并。 | |
| 触发页回收 / 内存规整 | 由扫描、迁移和等待决定 | 这属于完整页分配路径，不能被伙伴算法的阶数界覆盖。 |
时间与空间#
- 时间复杂度
- 拆分 / 合并 ，系统慢路径另计
- 辅助空间
- 各阶空闲链表 + 页状态元数据
按 2 的幂分配可能造成内部碎片；空闲页总量足够也不代表存在所需连续块。
工程中的应用#
1 个案例 · 附源码伙伴分配器把空闲物理页组织为不同 order 的连续块，并用空闲链表管理同阶块。
附源码片段 · 内存管理
基础原理参考资料
Linux 6.12 · Page allocatorexpand、__rmqueue_smallest 和 __free_one_page 的逐阶拆分 / 合并。