专题进阶 · 操作系统算法推荐总顺序 · 第 148 / 148 课

沿二叉拆分和伙伴合并模拟分配,理解按幂次对齐、异或定位与内部碎片。

先学会这些,再进入本课 二叉树 Big O
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

伙伴分配器Buddy Allocator

按二次幂分块拆分与合并,只能合并对应伙伴,内部碎片与快速管理之间需权衡。

建议 60 分钟 · 含手算、代码与三层练习

本课要建立的能力

沿二叉拆分和伙伴合并模拟分配,理解按幂次对齐、异或定位与内部碎片。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

一块16字节的区域要分配3字节,怎样快速拆分,并在释放后自动合并回大块?

02一步步得到方法

只管理二的幂大小块

Buddy 系统将区域看作一棵二叉拆分树。16可拆为两个8,8可拆为两个4。请求3字节时向上取整到4,这简化了尺寸分类与合并,但产生1字节内部碎片。

本课假定总区域大小是二次幂、起始地址为0、最小块1字节。真实内存分配器常以页或更大单位工作,还要管理元数据和并发;下面只模拟地址区间,不操作系统真实内存。

不是相邻就能合并

大小 s 的块起点必须按 s 对齐,它的伙伴地址为 address XOR s:只翻转当前层对应的那一位。比如 s=4,地址0的伙伴是4,地址4的伙伴是0;地址4与8虽然相邻,却来自不同父块,不能作为这一层伙伴直接合并。

释放时,仅当同阶伙伴也完全空闲,才移除伙伴并合成大小2s的父块,父地址取较小值。不断向上尝试,直到伙伴不空闲或到达总区域。

分配和失败条件

请求先归到最小可容纳的幂次,再寻找该阶或更大阶的空闲块。找到大块后持续二分,保留一半,另一半放回对应空闲集合,直到目标大小。

总空闲字节足够也可能没有足够大的连续伙伴块,这属于外部可用性限制;向上取整造成的块内浪费则是内部碎片。两者应分开理解。

03把一个小例子完全算清楚

总区域16,先分配3字节,再分配4字节。

步骤计算与状态为什么这样做
第一次分配16→8→4,返回地址0、块大小4空闲伙伴为地址4的4块和地址8的8块
第二次分配使用地址4的4块前半个8块完全占用
依次释放0、44与4合为8,再与地址8的8合为16最终恢复整块空闲

窄屏可左右滑动表格,阅读完整计算与理由。

两次释放后空闲集合回到 {16:[0]};只允许同阶真实伙伴合并。

04为什么这个方法成立

  1. 每个空闲或已分配块都来自对齐的二叉拆分,彼此不重叠,合起来覆盖整个区域。
  2. 分配将一个空闲块替换为一个已分配块和若干空闲兄弟,不改变覆盖关系。
  3. 释放仅合并同阶空闲伙伴,合并后恰好覆盖共同父块,因而保持不重叠和对齐不变量。

05把推导翻译成代码

Python · Buddy 地址区间分配模拟

class Buddy:
    def __init__(self,total):
        if total<1 or total & (total-1):
            raise ValueError("power-of-two arena required")
        self.total = total
        self.free_blocks = {1<<k:set() for k in range(total.bit_length())}
        self.free_blocks[total].add(0)
        self.allocated = {}

    def allocate(self,requested):
        if requested<1:
            raise ValueError("positive request required")
        size = 1 << (requested-1).bit_length()
        found = size
        while found<=self.total and not self.free_blocks[found]:
            found *= 2
        if found>self.total:
            return None
        address = self.free_blocks[found].pop()
        while found>size:
            found //= 2
            self.free_blocks[found].add(address+found)
        self.allocated[address] = size
        return address

    def release(self,address):
        if address not in self.allocated:
            raise ValueError("invalid or already freed address")
        size = self.allocated.pop(address)
        while size<self.total:
            partner = address ^ size
            if partner not in self.free_blocks[size]:
                break
            self.free_blocks[size].remove(partner)
            address = min(address,partner)
            size *= 2
        self.free_blocks[size].add(address)

arena = Buddy(16)
a,b = arena.allocate(3),arena.allocate(4)
print(a,b)
arena.release(a)
arena.release(b)
print(arena.free_blocks[16])

逐个理解关键决定

1 << (requested-1).bit_length()
向上取到最小二次幂,恰好是二次幂的请求不会再翻倍。
address ^ size
定位同一父块的另一半,不能简单找任意相邻空闲块。
invalid or already freed address
拒绝重复释放与不是已分配起点的地址,避免破坏结构。

06时间、空间与实现范围

总区域 U、最小块1时有 O(log U) 个阶,分配拆分与释放合并最多经过 O(log U) 层,集合操作按平均 O(1) 计。

空闲块与分配记录的空间按当前块数计,最坏可达 O(U) 个最小块记录;这只是元数据模拟,不实际分配 U 字节数组。

07改变条件,检查哪里会出错

所有相邻空闲块都能立即合并

需要同大小、按层对齐且互为伙伴。

分配返回的块大小等于请求大小

实际块向上取二次幂,多出的空间是内部碎片。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

请求5字节会分到多大块?

需要一点提示

找不小于5的最小二次幂。

查看解析与答案

8字节,内部浪费3字节。

练习 2 · 边界与辨析

大小4、地址12的伙伴地址?

需要一点提示

12 XOR 4。

查看解析与答案

8,它们共同组成地址8开始的8字节块。

练习 3 · 变式与迁移

释放一个块两次应该怎样?

需要一点提示

第二次已无分配记录。

查看解析与答案

应报错;若重复插入空闲结构,后续可能产生重叠分配。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。