伙伴算法(Buddy System)的原理
哪些公司问过
答案要点
- 按 2 的幂次页数分阶管理空闲块,每阶一个空闲链表
- 分配时找最小满足的阶,不够就从高阶块逐级对半拆分
- 释放时若伙伴块空闲且同阶就合并,并递归向上合并
- 伙伴地址可由页帧号与块大小做异或快速计算
- 优点是分配连续页快、外部碎片少,缺点是存在内部碎片
易错点
- 把伙伴算法说成分配任意字节的通用分配器,它的粒度是页
- 以为任意两个相邻空闲块都能合并,只有同阶且互为伙伴的块才能合并
- 忽略内部碎片:请求大小会向上取整到 2 的幂次
面试官常见追问
- 伙伴算法和 slab 分配器是什么关系?
- 长时间运行后高阶内存还是分配不出来怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。