伙伴页分配与连续块合并

为什么伙伴只差一个二进制位 ​

order $k$ 块的伙伴，是与它从同一个order $k+1$ 父块分出来的另一半。用相对页框编号计算，伙伴起点为

起点 $b$ 的低 $k$ 位全为0；再往上一位决定它在父块的左半还是右半。翻转这一位恰好切换左右，而保留更高位表示的共同父块。比如order 2的块8，二进制是1000，异或0100得到1100，即伙伴12。

释放块时先找这个特定伙伴。只有伙伴也完整地空闲在同一层，才能从 $F_k$ 删除它，并把二者组成的父块拿到上一层继续检查。相邻的两个块不一定是伙伴：$[4,8)$ 与 $[8,12)$ 虽然紧挨着，却分别属于父块 $[0,8)$ 与 $[8,16)$，不能直接拼成一个本模型允许的order 3块。

这个限制使合并不必遍历所有相邻洞。起点、层数和空闲状态足以确定候选者；若空闲集合支持常数期望时间的查询与删除，最多经过 ${\log }_{2}16=4$ 层。这个层数界不包含锁竞争、元数据存取或迁移已用页的成本；伙伴合并本身不搬动已分配内容。

从一个16页块拿出3页 ​

初始只有 $F_4=\{0\}$。请求3页要order 2，分配步骤如下。

实际请求3页，实际占用4页，块内有1页暂未用于这次请求。它是内部碎片，不是可被另一个页框请求随意取走的空闲页。若只统计用户有效需求，利用率是 $3/4$；若统计分配器已交付页数，分子则是4。两种统计不能混用。

总空闲8页，8页请求仍失败 ​

现在重置实验：先把16页分成四个已经交付的4页块，起点依次0、4、8、12。释放起点0和8后，空闲集合为 $F_2=\{0,8\}$，总空闲8页，却没有order 3或更大块。0的伙伴4仍在使用，8的伙伴12也仍在使用，不能合并。

随后释放起点4的块。它的伙伴 $4\mathrm{xor}4=0$ 正在 $F_2$，二者合成 $[0,8)$，插入 $F_3$。此时可以交付8页；起点8的4页空闲块仍独立保留，因为12尚未释放。请复算每一步的总量：释放三块后空闲12，交付8后空闲4，仍在使用的总量12。

若最初改为释放4和8，虽然得到连续区间 $[4,12)$，标准二进制伙伴分配器仍不能用一个order 3块交付它，因为起点4不满足8页对齐。需要“任意连续8页”而不要求这种对齐的分配接口，可以有不同的成功条件；不能把不同分配器的合同混在一起。

异或公式不能越过池的边界 ​

公式使用相对同一根块的编号。本例16页是一段对齐根块；现实内存可能有孔洞、不同节点或不同分区，不能看到绝对页号异或后的数字存在，就跨区域合并。必须先确认两块属于同一可合并池。池起点若不是相应幂二对齐，直接把绝对地址代入也需要重新证明。

重复释放、释放块中间地址、或用错误order释放，都会破坏覆盖不变量。多核情况下，检查伙伴和删除伙伴还需要作为一个同步操作，避免两个释放者同时把同一空闲块拿去合并。正确的数学伙伴关系不自动解决并发所有权。

两种碎片要分别修复 ​

取 $k=\lceil {\log }_{2}r\rceil$ 时，$r\le 2^k<2r$ 对非幂二正整数成立；所以一次向上取整占用小于请求的两倍。这是单块内部碎片的界，不是“只要还有一半内存就能分配”的全局保证。交错占用仍可把大块全部截断。

伙伴合并只能聚合已经空闲的正确兄弟。若想让分散自由页变成更大连续区域，可能需要迁移可移动的在用页，更新映射，再释放旧帧；不能移动的页又可能挡住整个过程。大页映射理路大页与TLB覆盖范围Huge pages · Superpages · TLB reach在数据全部驻留的模型中复算大页减少TLB未命中的条件，分开翻译覆盖、物理连续性、内部碎片与权限变更粒度。需要对齐连续物理区域时，就会遇到这项额外约束。

它与对象堆分配也分工不同：本页按整页幂二块交付，几十字节对象通常由上层分配器在已取得的页内组织。复算终点应同时交出空闲集合、每个已分配块的起点与order、以及总量守恒；只报一个“剩余8页”不足以说明下一项请求能否成功。