看数据结构写代码（50）伙伴系统 - fuming0210sc的专栏 - 博客频道 - CSDN.NET
伙伴系统 是一种 只 可以 分配 2的 幂次方 个 空间的 ，回收 内存 时 只 合并 "伙伴空间" 的一种 动态内存管理方式。
例如 一个 空间 大小 为 64 的 内存，伙伴 系统 为 这 64 的内存 建立 一组 双向循环 链表，分别 管理着 2的 0 次方，2的1 次方幂，2的 2 次方幂。。。2的6次方幂的 可用空间。
即使 我们 只想分配 一个 大小 为3的 空间，系统 却 只能 返回 一个 内存 大小 为 4（2的2次方）的 一个空间。
系统 在 初始化的 时候 ，并不是 为 每一个 链表 都 放入 一些 可用空间 。而是 在 2的 6次方幂 插入 一个 空间节点，大小 为64。
当我们 想 要 分配 内存的时候，会 查找 最近 内存大小的 链表，如果 链表 有 可用空间，取 第一个 空间。否则 顺次 查找 可用空间。
假设 我们 要在 这个 64 的 空间 里，分配 一个 大小 为 3 的内存，系统 怎么 分配呢？
系统 会 从 第一个链表 一直 找，直到 找到 2的 6次方的 链表。系统 会 将 前 4个 空间 分配 给用户。可是 其余的 60个空间 ，不能 再 插入到 2的 6次方 的链表中了。只能 插入到
比 它小的链表中去。
具体的 分配 方式 如下：4 4 8 16 32 。
前4个 分给用户 使用，后 面的 4 8 16 32 依次 插入 到 2的 2次方幂，2的 3次方，4次方，5次方幂的链表中去。
这 有一个 规则：
1. 用户 空间 的 邻接空间 总是 被 拆分成 一个 跟 用户 空间 大小 一样的 空间。这个 空间 就是 上面 所有的 "伙伴空间"。
2. 再 下一个空间 依次 是 用户空间的 2倍，4倍，8倍，。。。直到 被拆分空间 一半。 例子的 拆分空间 为 64，它的一半 为 32。
所以 可以 算出：64 是 如何 被 拆分的： 4（用户空间） 4（伙伴空间） 8 16 32
当我们 回收空间时，首先 会 查看 这个空间的 伙伴空间 是否 为 空闲。如果空闲 会 合并，并从 链表中 删除 伙伴空间。。然后 会 再次 查看 合并后的 空间。直至 无法 合并。如果 不空闲，插入到 合适的 链表中去。
伙伴空间 就是 上面 所说的 "4" ，必须 跟 回收空间 空间大小一样 ，而且 是 从 同一个 大块 内存 分配 出去的，
有一个公式可以求出 伙伴空间：
例如 释放 上面 的 空间， 会查找 伙伴空间 ，伙伴空间 空闲，合并空间 成为 一个 大小 为8 的空间，并从 2 的 2 次方 链表中 删除 伙伴空间，然后 继续 查找。 继续删除。。最终 会 合并 成 一个 在 2的 6次幂链表中的 一个 空间。 和 初始的情况一样。
Read full article from 看数据结构写代码（50）伙伴系统 - fuming0210sc的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment