Skip to content

垃圾回收的算法与实现.md

Latest commit

 

History

History
136 lines (84 loc) · 8.95 KB

垃圾回收的算法与实现.md

File metadata and controls

136 lines (84 loc) · 8.95 KB

1.9 评价标准

评价 GC 算法的性能时，我们采用以下 4 个标准。

  • 吞吐量
  • 最大暂停时间
  • 堆使用效率
  • 访问的局部性

较大的吞吐量和较短的最大暂停时间不可兼得 可用的堆越大，GC 运行越快; 相反，越想有效地利用有限的堆，GC 花费的时间就越长。

2 GC标记-清除算法

GC 标记 - 清除算法由标记阶段和清除阶段构成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段。通过这两个阶段，就可以令不能利用的内存空间重新得到利用。

标记所花费的时间是与 “活动对象的总数” 成正比的, 标记阶段就是 “遍历对象并标记” 的处理过程。 在 GC 标记 - 清除算法的使用过程中会逐渐产生被细化的分块，不久后就会导致无数的小分块散布在堆的各处。我们称这种状况为碎片化 (fragmentation)。

2.6 位图标记

在单纯的 GC 标记 - 清除算法中，用于标记的位是被分配到各个对象的头中的。也就是说，算法是把对象和头一并处理的。然而之前在 2.3.3 节中也提过，这跟写时复制技术不兼容。 在堆为多个的情况下，一般会为每个堆都准备一个位图表格。

2.6 延迟清除法

3 引用计数法

对象保存自己的引用次数, 不需要回收算法遍历依赖关系树来标记 这种算法将垃圾回收放在了引用计数操作中,一旦对象引用计数为0即刻回收, 优点是可即刻回收垃圾，最大暂停时间短, 对程序实时性影响较小, 缺点是引用计数保存在对象中, 垃圾回收算法与对象耦合, 对象引用计数字段也会占用内存空间， 另外就是不支持对象的循环引用

3.4 延迟引用计数法

计数器值增减处理繁重的原因之一是从根的引用变化频繁

  • 优点 在延迟引用计数法中，程序延迟了根引用的计数，将垃圾一并回收。通过延迟，减轻了因根引用频繁发生变化而导致的计数器增减所带来的额外负担。

  • 缺点 为了延迟计数器值的增减，垃圾不能马上得到回收，这样一来垃圾就会压迫堆，我们也就失去了引用计数法的一大优点 — 可即刻回收垃圾。 另外，scan_zct() 函数导致最大暂停时间延长了。执行 scan_zct() 函数所费的时间与 $zct 的大小成正比。$zct 越大，要搜索的对象就越多，妨碍 mutator 运作的时间也就越长。要想缩减因 scan_zct() 函数而导致的暂停时间，就要缩小 $zct。但是这样一来调用 scan_zct() 函数的频率就增加了，也压低了吞吐量。很明显这样就本末倒置了

3.5 Sticky引用计数法

有很多研究表明，很多对象一生成马上就死了。也就是说，在很多情况下，计数器的值会在 0 到 1 的范围内变化，很少出现 5 位计数器溢出这样的情况，为了节约内存空间，提出了下面的解决方法

解决方法: 混合GC标记-清除算法与引用计数算法

  • 一开始就把所有对象的计数器值设为 0
  • 不标记对象，而是对计数器进行增量操作
  • 为了对计数器进行增量操作，算法对活动对象进行了不止一次的搜索

像这样，只要把引用计数法和 GC 标记 - 清除算法结合起来，在计数器溢出后即使对象成了垃圾，程序还是能回收它。另外还有一个优点，那就是还能回收循环引用的垃圾。 但是在进行标记处理之前，必须重置所有的对象和计数器(避免可能的溢出造成的影响)。此外，因为标记方式从设置标志位变成了使用计数器进行计数，所以需要多次 (次数和被引用数一致) 查找活动对象。 考虑到这一点的话，显然在这里进行的标记处理比以往的 GC 标记 - 清除算法中的标记处理要花更多的时间。也就是说，吞吐量会相应缩小。

3.6 1位引用计数法

据 Douglas W. Clark 和 C. Cordell Green 观察, "几乎没有对象是被共有的, 所有对象都能被马上回收". 考虑到这一点, 即使计数器只有 1 位, 通过用 0 表示被引用数为 1,用 1 表示被引用数大于等于 2, 这样也能有效率地进行内存管理.注意这里的引用计数保存在引用对象中而不是保存在被引用对象中.

1 位引用计数法 (1bit Reference Counting) 是 Sticky 引用计数法的一个极端例子, 计数器只有 1 位大小, 用 0 表示被引用数为 1, 用 1 表示被引用数大于等于 2.

  • 优点 当某个高速缓存中的对象 A 要引用在内存中的对象 B 时, 以往的引用计数法会 在增减计数器值的时候读取 B, 从而导致高速缓存缺失, 白白浪费大把时间. 1 位引用计数法就不会这样, 它不需要在更新计数器 (或者说是标签) 的时候读取要引用的对象, 同时也节省了内存消耗量.

  • 缺点 有可能生成大量计数器溢出的对象 (也就是内存管理范围之外的对象), 这会给堆带来巨大负担. 这样一来我们就很难保证分块了.

3.7 部分标记-清除算法

引用计数法存在的一大问题就是不能回收循环的垃圾, 用 GC 标记 - 清除算法就不会有这种问题. 如果综合两种算法, 在一般情况下使用引用计数法, 在某个时刻启动 GC 标记 - 清除算法, 虽然解决了问题, 但是这个方法效率很低. 利用 GC 标记 - 清除算法毕竟是单纯为了回收 "有循环引用的垃圾", 而一般来说这种垃圾应该很少, 单纯的 GC 标记 - 清除算法又需要遍历全部堆中的对象, 会产生许多无用的搜索.

对此我们的解决方法是只对 "可能有循环引用的对象群" 使用 GC 标记 - 清除 算法, 对其他对象进行内存管理时使用引用计数法. 像这样只对一部分对象群使用 GC 标记 - 清除算法的方法, 叫作 "部分标记 - 清除算法" (Partial Mark & Sweep). 不过它有个特点, 执行一般的 GC 标记 - 清除算法的目的是查找活动对象, 而执行部分标记 - 清除算法的目的则是查找非活动对象.

在部分标记 - 清除算法中，对象会被涂成 4 种不同的颜色来进行管理:

  1. 黑 (BLACK): 绝对不是垃圾的对象 （对象产生时的初始颜色）
  2. 白 (WHITE): 绝对是垃圾的对象
  3. 灰 (GRAY): 搜索完毕的对象
  4. 阴影 (HATCH): 可能是循环垃圾的对象

如果对象的计数器值减量后不为 0, 说明这个对象可能是循环引用的一份子. 这时会先让这个对象连接到队列 $hatch_queue, 以方便之后搜索它.

当满足下面两种情况时，就会产生循环垃圾:

  1. 产生循环引用
  2. 删除从外部到循环引用的引用

部分标记-清除算法的局限性

部分标记 - 清除算法并不是完美的, 因为从队列搜索对象所付出的成本太大了. 被队列记录的对象毕竟是候选垃圾, 所以要搜索的对象绝对不在少数. 这个算法总计需要查找 3 次对象, 也就是说需要对从队列取出的阴影对象分别执行 1 次 mark_gray() 函数, scan_gray() 函数以及 collect_white() 函数. 这大大增加了内存管理所花费的时间. 此外，搜索对象还害得引用计数法的一大优点 — 最大暂停时间短荡然无存.

4 GC复制算法

把某个空间里的活动对象复制到其他空间, 把原空间里的所有对象都回收掉.

GC 复制算法是利用 From 空间进行分配的. 当 From 空间被完全占满时, GC 会将活动对象全部复制到 To 空间. 当复制完成后, 该算法会把 From 空间和 To 空间互换, GC 也就结束了. From 空间和 To 空间大小必须一致. 这是为了保证能把 From 空间中的所有活动对象都收纳到 To 空间里.

GC 复制算法在类中添加了两个域，一个是 tag 域, 用来标识复制状态, 防止对象复制多次, 一个是 forward 域, 用来存放复制对象对其他对象的引用关系, 防止复制遗漏

  • 优点
  1. 优秀的吞吐量, 消耗的时间与活动对象的数量成比例
  2. 可实现高速分配, 算法没有使用空闲链表对待分配空间进行分级管理, 通过复制来避免内存碎片化
  3. 不会发生碎片化
  4. 与缓存兼容, GC 后有引用关系的对象会位于堆中较近的位置
  • 缺点
  1. 内存使用效率低下
  2. 不兼容保守式GC算法
  3. 递归调用函数, 对象依赖链比较长时有栈溢出的可能

4.4 Cheney的GC复制算法

算法不是递归的, 而是迭代的进行复制.

  • 改进点 类中没有使用 tag 域, 而是用 forward 域来保存复制状态(通过检查指针指向 from 空间还是 to 空间) 引入了 scan 指针, 初始化后指向 to 空间的开始, 用于搜索复制完成的对象

  • 优点

  • 缺点

4.5 近似深度优先搜索方法

4.6 多空间复制算法

5 GC标记-压缩算法

GC 标记 - 压缩算法 (Mark Compact GC) 是将 GC 标记 - 清除算法与 GC 复制算法相结合的产物