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、4 | 4与4合为8,再与地址8的8合为16 | 最终恢复整块空闲 |
窄屏可左右滑动表格,阅读完整计算与理由。
两次释放后空闲集合回到 {16:[0]};只允许同阶真实伙伴合并。
04为什么这个方法成立
- 每个空闲或已分配块都来自对齐的二叉拆分,彼此不重叠,合起来覆盖整个区域。
- 分配将一个空闲块替换为一个已分配块和若干空闲兄弟,不改变覆盖关系。
- 释放仅合并同阶空闲伙伴,合并后恰好覆盖共同父块,因而保持不重叠和对齐不变量。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
请求5字节会分到多大块?
需要一点提示
找不小于5的最小二次幂。
查看解析与答案
8字节,内部浪费3字节。
大小4、地址12的伙伴地址?
需要一点提示
12 XOR 4。
查看解析与答案
8,它们共同组成地址8开始的8字节块。
释放一个块两次应该怎样?
需要一点提示
第二次已无分配记录。
查看解析与答案
应报错;若重复插入空闲结构,后续可能产生重叠分配。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces