苏州工业园区苏雅璐308号信投大厦18楼-22楼 17717624695 jiuyouapp@www.j9.com

资讯中心

成倍分块的内存池怎样拆分空间并合并伙伴块:过程核对第15例

2026-11-20

关卡对象申请的空间大小并不总是规则整数块。简化的伙伴分配器把空间切成二的幂次大小,需要时不断对半拆分,释放时尝试和同大小、同一父块的伙伴重新合并。

本例规则与输入

本例总容量六十四单位,最小块为四。申请量向上取到不小于四的二次幂,选择能容纳它的最小现有空闲块,同大小选起点较小者。拆分时保留左半继续拆,右半放回空闲表;无法找到足够大的块则失败。

区间均为起点包含、终点不包含;活动条目按起点、实际块大小、原申请量记录。

逐步计算记录

操作 | 结果 | 活动分配 | 空闲起点、大小 ['alloc', 'A', 3] | 已分配 | {'A': [0, 4, 3]} | [[4, 4], [8, 8], [16, 16], [32, 32]] ['alloc', 'B', 3] | 已分配 | {'A': [0, 4, 3], 'B': [4, 4, 3]} | [[8, 8], [16, 16], [32, 32]] ['free', 'A'] | 已释放 | {'B': [4, 4, 3]} | [[0, 4], [8, 8], [16, 16], [32, 32]] ['free', 'B'] | 已释放 | {} | [[0, 64]] ['alloc', 'C', 16] | 已分配 | {'C': [0, 16, 16]} | [[16, 16], [32, 32]] ['alloc', 'D', 25] | 已分配 | {'C': [0, 16, 16], 'D': [32, 32, 25]} | [[16, 16]] ['alloc', 'E', 15] | 已分配 | {'C': [0, 16, 16], 'D': [32, 32, 25], 'E': [16, 16, 15]} | [] ['free', 'C'] | 已释放 | {'D': [32, 32, 25], 'E': [16, 16, 15]} | [[0, 16]] ['alloc', 'F', 14] | 已分配 | {'D': [32, 32, 25], 'E': [16, 16, 15], 'F': [0, 16, 14]} | [] ['alloc', 'G', 5] | 空间不足 | {'D': [32, 32, 25], 'E': [16, 16, 15], 'F': [0, 16, 14]} | [] ['alloc', 'H', 22] | 空间不足 | {'D': [32, 32, 25], 'E': [16, 16, 15], 'F': [0, 16, 14]} | [] ['free', 'D'] | 已释放 | {'E': [16, 16, 15], 'F': [0, 16, 14]} | [[32, 32]] ['alloc', 'I', 24] | 已分配 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['alloc', 'J', 11] | 空间不足 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['alloc', 'K', 3] | 空间不足 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['free', 'H'] | 无活动分配 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['alloc', 'L', 23] | 空间不足 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['alloc', 'M', 24] | 空间不足 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['alloc', 'N', 6] | 空间不足 | {'E': [16, 16, 15], 'F': [0, 16, 14], 'I': [32, 32, 24]} | [] ['free', 'E'] | 已释放 | {'F': [0, 16, 14], 'I': [32, 32, 24]} | [[16, 16]] ['free', 'F'] | 已释放 | {'I': [32, 32, 24]} | [[0, 32]] ['free', 'G'] | 无活动分配 | {'I': [32, 32, 24]} | [[0, 32]] ['free', 'I'] | 已释放 | {} | [[0, 64]] ['free', 'J'] | 无活动分配 | {} | [[0, 64]] ['free', 'K'] | 无活动分配 | {} | [[0, 64]] ['free', 'L'] | 无活动分配 | {} | [[0, 64]] ['free', 'M'] | 无活动分配 | {} | [[0, 64]] ['free', 'N'] | 无活动分配 | {} | [[0, 64]]

表中编号用于区分本例对象,不代表任何真实产品的默认规则。输入、处理顺序与边界约定都属于题目的一部分;请先按相同规则复算,再比较不同实现。分数保留精确值,若自行改用小数,应把显示舍入与实际计算误差分开。

独立核对方法

释放后用起点与块大小的异或找到伙伴起点。只有伙伴以同大小完整空闲块存在时才合并,然后继续向上检查。每步表格记录活动分配和空闲块,所有区间应无重叠地覆盖整片空间,已分配与空闲总量必须守恒。

验收可以把六十四个单位逐个标记为空闲或占用,再从整块向下递归划分,得到规范的最大空闲块集合。与空闲表比较能发现漏合并和错误合并。只看总空闲数无法发现两块相互重叠或某个单位失去归属的问题。

适用边界

实际占用按向上取整后的块大小计算,申请量与实际占用的差是内部余量。即便空闲总量足够,也可能没有合适的连续伙伴块。本例不移动现有对象、不处理线程并发,也不复用仍处于活动状态的申请标识。

改变输入后,建议先找到第一处不同的中间结果,再追查它所依赖的条件。不要仅因为最后一个数看起来接近,就认定全过程相同。把原始记录、选择理由与边界情况保留下来,更容易区分机制差异和实现失误。