第五讲 伙伴系统总结
匿名2023/07/31 19:50:16提问
    lecture5studentunanswered
341

题外话:为什么叫“伙伴”?因为每块只能和特定的另一块合并。

参考了wiki上伙伴系统实现的链接,在此做一简单总结

这里采用二叉树管理内存单元,分配和释放的搜索时间复杂度O(logN),在这一点上优于最先匹配、最佳匹配和最差匹配。

 

每个节点标记对应的可用内存块大小

分配:

  1. 传入size,将size调整到2的幂大小,检查是否超过根节点的标记。
  2. 深度优先搜索,找到恰为size大小的空闲内存块(标记等于size且该层每个节点对应内存块大小为size),修改标记为0。根据size和该节点对应二叉树中的序号以及总大小,可以计算出内存块索引offset。
  3. 之后回溯,更新祖先节点的标记,取左右子树较大值,完成分割。

 

释放:

传入offset。从最底层节点向上回溯,遇到标记为0的节点即对应当初分配的内存块,恢复标记为块大小,继续回溯,如果左右子树标记相加等于父节点对应的块大小,则恢复父节点标记为块大小。

回答(0
    推荐问答
      Simple Empty
      暂无数据