内存管理深入：Buddy系统页框分配与内存碎片整理

可视化演示

展示Buddy系统页框分裂与合并、内存碎片整理compaction过程与OOM killer/kswapd三级回收策略，帮助理解操作系统内存管理。

基础概念

我们继续用仓库管理员的故事开场。管理员把仓库地面划分成无数标准尺寸的储物格，每组相邻格子都有唯一编号。为了满足不同大小的储物需求，他从不一个个格子地操作，而是把相邻格子拼成更大的“块”。最小的块就是 1 个储物格，稍大一点是 2 格，再往上 4 格、8 格、16 格……块的大小永远按照 2 的倍数增长。

在操作系统术语中，这个最小储物格叫“页框”（page frame），是内核管理物理内存的最小单位。多个连续页框组成的区域叫“块”。为了快速描述块的大小，内核引入了“阶数”（order）：0 阶块包含 1 个页框，1 阶块包含 2 个页框，k 阶块包含 2^k 个页框。阶数就像储物格的“层架编号”，管理员看到编号就能立刻知道柜子能装多少东西，不用去数格子。

在 Linux 内核里，struct page 是页框的描述符，内核用 mem_map 数组把物理内存中所有页框描述符串联起来。Buddy 系统则维护一组按阶数分层的空闲块链表，叫作 free_area。每个阶数都有专属链表，挂着该尺寸的空闲块。初始化时，内核会把整个物理内存拆成多个大块挂入最高阶链表，之后所有分配与回收都从这个源头开始。

有了阶数这个“编号”，仓库管理员管理起来轻松多了——他不需要逐格记忆，只需要知道“几阶块”对应多大空间。后面所有的拆分、合并，都建立在这个阶数框架之上。

分配策略

顾客来了，管理员怎么快速找到合适的柜子？他站在“分格索引台”前，台面贴着标签：0 阶、1 阶、2 阶……每个标签下面有一个抽屉，抽屉里放着当前所有空闲柜子的编号。管理员先把顾客的需求换算成最小合适的阶数，然后从对应抽屉开始翻找。

如果目标阶数的抽屉是空的怎么办？管理员会顺手打开更大的抽屉，取出一块大柜子，当场拆成两半：一半交给顾客，另一半放回低一阶的抽屉。这个过程就是 Buddy 系统分配内存的核心思路：“从上往下借，借了立刻拆”。

具体到内核，alloc_pages(order) 首先从 free_area[order] 链表取块；如果该链表为空，便向 free_area[order+1] 借块，并把借来的大块拆成两个 order-1 的伙伴块，一个挂回低阶链表，一个继续使用；若高一级也空，就继续向上查找，直到找到非空链表。这个“向上索引”的过程在实现上通常配合位图或快速查找表来加速。

这个策略保证了柜子尺寸“刚好够用，又不会大太多”，同时查找过程像翻抽屉一样快捷，分配均摊复杂度接近 O(1)。

伙伴分裂

把大柜子拆成两半时，管理员会在本子上把两个半柜用括号连在一起，注明它们是“双胞胎”。只有双胞胎才能彼此认亲——以后释放时，管理员只在双胞胎之间考虑合并，绝不随便把两个不相干的空闲块拼起来。这个“双胞胎”就是伙伴。

在 Buddy 系统中，分裂是分配过程的必经之路：当需要的块小于当前可用的最大块时，内核会把这个大块递归二分。每拆一次，就得到两个同阶且物理地址相邻的伙伴块。Linux 内核中的分配位图（bitmap）会记录各块状态，帮助系统快速判断某块的伙伴是否空闲。

伙伴地址的计算是整个算法最精妙的一环。给定块大小为 2^k 个页框，其伙伴地址只需一次异或运算即可得到：伙伴地址 = 块地址 XOR 块大小。因为块地址对齐到自身大小，低 k 位是 0，而块大小的二进制在第 k 位上是 1，两者异或恰恰只翻转第 k 位——正好找到同一大块的另一半。

从仓库管理员的视角看，这就像在格子地图上涂掉一个坐标，立刻就能读出隔壁格子的编号。伙伴发现能力，正是 Buddy 系统合并速度的底气所在。

伙伴合并

当顾客取走货物、归还柜子时，管理员的第一件事不是把柜子硬塞回抽屉，而是查看旁边那格：它的“双胞胎兄弟”是不是也在闲着？如果兄弟也空置，就把两个半格拼成一个完整的双格柜；如果拼好的双格柜还能和另一个双格柜继续拼，就再拼一次，直到找不到空闲的兄弟为止。

这正对应 Buddy 系统释放内存时的伙伴合并流程。释放一个 order=k 的块后，内核先用伙伴地址公式找到它的伙伴；若伙伴同样空闲，则将两者从各自链表摘下，合并成一个 order=k+1 的块，并继续尝试向上合并。合并过程可以一直递归到 MAX_ORDER，也可能因为伙伴忙碌而提前停止。

合并是分裂的逆操作，也是消除外部碎片最直接的手段。需要注意，合并必须保证两个块是“合法伙伴”：来自同一个父块、物理地址相邻、阶数相同。如果只是大小相同但地址不相邻，绝不能合并。内核常通过 struct page 的 private 字段与 PG_buddy 标志位来维护伙伴关系。

管理员把两个本就相邻的空柜子拼在一起，既腾出了大块空间，又让柜子编号依然规律。伙伴合并，正是 Buddy 系统对抗碎片最重要的武器。

碎片问题

仓库的麻烦也随之而来。管理员勤勉地拆拼柜子，但顾客来来往往，空间总会被“弄花”：某个区域里，大小不一的柜子像跳棋一样交错排列，中间散落着许多零星空格。明明空闲格子总数不少，却找不到一个大到能放下整台冰箱的连续格子——这就是外部碎片。

与外部碎片相对的是内部碎片：当请求 5KB 时，Buddy 分配器给了 8KB 的块，多出的 3KB 虽然在块内，却无法被任何其他请求利用。内部碎片是 Buddy 按 2 的幂次分配导致的固有代价，而外部碎片则是伙伴系统合并机制未能完全回收的结果，多由小块的分配、释放序列造成。

我们可以用碎片率来量化碎片化程度：统计空闲页框中最大的连续块有多大，再除以总空闲内存。碎片率越接近 1，表示虽然空闲块总数多，但无法满足大块请求；越接近 0，表示空闲内存在很大程度上是连续的。

就像仓库里能用的格子总数不少，却总差那么一块“整地方”，碎片率就是管理员判断何时需要大扫除的仪表盘。

碎片整理

当碎片率严重影响到大客户，管理员会启动“深夜大扫除”：把仓库里的货柜挪来挪去，将所有已占用的柜子逐步搬到同一侧，把散落的空格聚拢成一整片区域。搬移过程虽然消耗人力，但能让仓库重新拥有“超大储物区”。

Linux 内核的对应招数是内存规整（memory compaction）。它扫描可迁移页框，把正在使用的页块搬到一起，尽量让空闲页框形成连续区间。页块迁移的关键是页表更新和数据拷贝；而反碎片技术则从源头下手：按页框的可移动性（不可移动、可回收、可移动）分组存放不同类型的页，避免碎片从分配阶段就聚集起来。

任何整理都要付出代价。移动一个页框需要拷贝数据、修改页表并刷新 TLB；迁移的页数越多，开销越大。因此内核只有在碎片率较高或大块分配失败时，才会触发迁移与规整。这正是“碎片收益与开销的取舍”——频繁迁移反而会拖垮整体性能。

管理员不会天天大扫除，只在碎片影响大局时才动手。Buddy 系统负责“日常分配与合并”，内存规整负责“紧急疏导”，两者合力，才能让内存长期维持较高的连续可用空间。

AI 应用场景

Python 演示

class BuddyAllocator:    # 简化版Buddy系统 以页框为基本单位    def __init__(self, max_order=5):        self.max_order = max_order        self.total_pages = 1 << max_order        self.free_lists = {o: [] for o in range(max_order + 1)}        self.free_lists[max_order].append(0)        self.busy = {}        self.flags = [0] * self.total_pages     def buddy_addr(self, addr, order):        return addr ^ (1 << order)     def alloc(self, order):        if order > self.max_order:            return None        cur = order        while cur <= self.max_order and not self.free_lists[cur]:            cur += 1        if cur > self.max_order:            return None        addr = self.free_lists[cur].pop()        while cur > order:            cur -= 1            buddy = self.buddy_addr(addr, cur)            self.free_lists[cur].append(buddy)        self.busy[addr] = order        for i in range(addr, addr + (1 << order)):            self.flags[i] = 1        return addr     def free(self, addr):        if addr not in self.busy:            raise ValueError('unknown address')        order = self.busy.pop(addr)        for i in range(addr, addr + (1 << order)):            self.flags[i] = 0        while order < self.max_order:            buddy = self.buddy_addr(addr, order)            if buddy in self.free_lists[order]:                self.free_lists[order].remove(buddy)                addr = min(addr, buddy)                order += 1            else:                break        self.free_lists[order].append(addr)        return order     def frag_rate(self):        max_cont = 0        cnt = 0        for i in range(self.total_pages + 1):            if i < self.total_pages and self.flags[i] == 0:                cnt += 1            else:                max_cont = max(max_cont, cnt)                cnt = 0        total_free = self.flags.count(0)        return 0.0 if total_free == 0 else 1.0 - max_cont / total_free  def main():    b = BuddyAllocator(max_order=5)   # 32个页框    print('free list before:', {o: len(b.free_lists[o]) for o in range(6)})    a1 = b.alloc(3)    print('alloc(3) -> addr =', a1)    a2 = b.alloc(2)    print('alloc(2) -> addr =', a2)    print('free list middle:', {o: len(b.free_lists[o]) for o in range(6)})    print('frag rate: %.3f' % b.frag_rate())    b.free(a1)    print('after free(a1) :', {o: len(b.free_lists[o]) for o in range(6)})    b.free(a2)    print('after free(a2) :', {o: len(b.free_lists[o]) for o in range(6)})    print('frag rate end : %.3f' % b.frag_rate())  if __name__ == '__main__':    main()

1. self.free_lists = {o: [] for o in range(max_order + 1)}为每个阶数准备一条空闲链表，对应内核的 free_area 数组
2. return addr ^ (1 << order)用异或运算一步定位伙伴地址，是 Buddy 算法最核心的位运算
3. while cur <= self.max_order and not self.free_lists[cur]: cur += 1顺着阶数向上查找非空链表，找不到则分配失败
4. buddy = self.buddy_addr(addr, cur); self.free_lists[cur].append(buddy)拆分大块时，把多余的一半挂回低阶链表备用
5. if buddy in self.free_lists[order]释放时先确认伙伴确实空闲，不满足条件绝不合并
6. addr = min(addr, buddy)合并后块地址取两个伙伴中较小的起始地址，保证新的块往低地址对齐
7. return 1.0 - max_cont / total_free最大连续空闲块占比越低，碎片率越高，直接量化内存质量

常见误区

面试题