可分配直方图-togaf 9.2 full version

图5.22　可分配直方图 F R E E 线 的 总 数 要找备用 From 块，首先要从碎片化最严重的块开始找，也就是从直方图中 hole_cnt 最 大的地方开始往小的地方搜索，这个过程是在 require 上加上申请直方图的纵轴（非 FREE 线 的总数）的值，从 available 里减去可分配直方图的纵轴（FREE 线的总数）的值。设 require 的初始值为 0，available 的初始值是堆中 FREE 线的总数。此时，require < available。 当 require > available 时，对直方图的搜索就结束了。最后，哪些块的孔数比搜索 到的数量大，哪些块就是备用 From 块。 我们在这里做的就是选出满足“From 块中 ALLOCATED 线和 CONSERVATIVE 线的总数”“除 From 以外的块中 FREE 线的总数”这样的 From 块。 下面结合具体的例子来看一下，依然使用图 5.21 和图 5.22 的直方图。不过因为在实现 上是用数组表示直方图的，所以这里也用数组来进行说明。 require、available 的值分别如图 5.23 所示。 图5.23　选定备用From块（初始状态） FREE 线的总数 孔数（hole_cnt） 非 FREE 线的总数 1 2 3 4 5 6 502 227 207 215 220 216 10 29 49 41 36 40 require：0 available：717 此外，我们设堆中存在 2 个 FREE 块。这样一来，就不是从 available 减去可分配直方 图中 FREE 线的总数了，而是加上了 2 个 FREE 块，也就是加了 512。 首先从 hole_cnt = 6 开始搜索这个数组。请看图 5.24。