Skip to main content

增量式垃圾回收算法怎么实现的

增量式垃圾回收: 为了控制最大暂停时间，通过逐渐推进垃圾回收即垃圾回收与mutator交替执行。 以标记-清除算法为例使用三色标记算法。

利用降低吞吐量来缩短最大停顿时间。

概述#

增量式垃圾回收也并不是一个新的回收算法, 而是结合之前算法的一种新的思路.

之前说的各种垃圾回收, 都需要暂停程序, 执行GC, 这就导致在GC执行期间, 程序得不到执行. 因此出现了增量式垃圾回收, 它并不会等GC执行完, 才将控制权交回程序, 而是一步一步执行, 跑一点, 再跑一点, 逐步完成垃圾回收, 在程序运行中穿插进行. 极大地降低了GC的最大暂停时间.

实现#

增量式垃圾回收只是提出了这样的一个概念, 并没有限定如何去实现. 想必也有不同的实现思路

基础#

  • 将GC中对象分成三种颜色：
    • 白色：还未搜索过
    • 灰色：正在搜索
    • 黑色：搜索完成
  • 增量式的GC标记-清除算法分成以下三个阶段：
    • 根查找阶段
    • 标记阶段
    • 清除阶段

这里的颜色只是一种虚构的概念, 就是在对象上打tag

在GC开始执行时, 所有对象都是白色的, 然后将根集合的对象放到栈中, 并标记为灰色, 依次处理. 将对象从栈中取出, 递归搜索所有子对象, 并标记为灰色, 当子对象搜索完后, 就将对象标记为黑色. 这样, 当一个对象搜索完后, 该对象及其关联的所有子对象就都是黑色的了. 当标记阶段结束后, 所有活动对象都是黑色, 垃圾对象则是白色.

此算法就是通过这样, 逐步对对象进行标记.

三色标记应用于标记清除中

标记清除算法在标记阶段, 应用三色标记逐步标记, 每次搜索一定次数后, 就返回执行, 等待下次继续标记, 将标记分为小段穿插在程序中运行.

在清除阶段, 也可以设置一个次数, 每遍历一定数量的对象, 就返回等待下次继续.

三色标记不光可以应用于标记清除中, 也可以应用于其他标记算法中.

执行过程#

  • 根查找阶段，直接将GC root直接引用的对象从白色涂为灰色，并将其加到标记栈。
  • 标记阶段，每次标记一定数量对象，从标记栈中取出对象将其子对象涂成灰色，当标记阶段要结束时再次将GC root的直接引用的对象加入到标记栈，再次标记。
  • 清除阶段，当标记栈为空时，每次清除一定数量的白色对象，对此执行次步骤直到遍历完整个堆。

写入屏障#

  • 由于标记阶段是多次完成的，因此可能产生“标记遗漏”即从黑色对象指向白色对象的指针。此时该白色的活跃对象会被认为是垃圾。
  • 通过写入屏障解决，在修改指针时如果新引用的对象是白色的就将其标为灰色(加入到标记栈)

分配#

  • 分配时检查可用空间是否小于某个值，小于则开始进行GC(Mark-Sweep是内存不足才进行GC)。
  • 分配时如果GC处于清除阶段，且分配位置还未遍历则需要给该对象标为黑色。

Steele的算法#

  • 标记阶段加入到标记栈时不设置标志，而是在遍历子对象时设置其标记标志。
  • 写入屏障增加条件，标记过程中发生引用的对象是黑色对象且新的引用的目标对象为灰色或白色，则将发出引用的对象涂成灰色。

汤浅的算法#

原则：基于在GC开始时保留活动对象。

  • 标记阶段不需要进行重新遍历GC root，因为其在写入屏障中如果GC处于标记阶段则将对该对象加入标记栈。
  • 分配时如果处于标记阶段则将对象设为黑色。

例子#

RC Immix算法#

合并型引用计数法#

  • 引用计数法由于频繁修改计数器导致吞吐量不高。设计一种把注意力放在某一时期最初和最后状态上，这期间不对计数器做修改，即合并型引用计数法。
  • 引入更改缓冲区，指针的改动记录到该缓冲区。
  • 当指针发送改变时将指针发送改变的对象和其所有子对象注册到更改缓冲区，通过写入屏障实现。
  • 对象增加dirty标志，用于记录该对象是否写入了缓冲区。
  • 当缓冲区满了时进行GC，先对对象当前的引用的子对象进行增量，而后对更改缓冲区记录的子对象进行减量，从而实现了对计数器的恢复。
  • 优点在于增加了吞吐量
  • 缺点则是增加了最大停顿时间

合并型引用计数法和Immix的融合#

  • 回收以线为对象，如果线内没有一个活动对象则回收该线。
  • 线也增加计数器，表示线内存活对象数。
  • 所有没经历过GC的新对象均会记录在更改缓冲区，在GC时只对新对象进行复制算法，实现被动的碎片整理。
  • 积极的碎片整理，采用标记-压缩算法，选择一个块进行。

问题#

如下场景:

//假设 c, d 是两个对象$b->son = $d;$b->son = $c;// 在这个时候, 开始GC, 将d标记为白色, 将c标记为黑色. 返回$b->son = $d;// GC清除阶段, 将c对象保留, 将d对象回收

这样就出现问题了, 也就是说如果我已经对其进行过标记了, 但它在我标记之后进行了修改, 就会导致清除阶段的对象很可能不是当时的真实情况。

那么如何防止这种遗漏的标记呢? 简单粗暴一点, 每次更新指针的时候, 如果对象是白色的, 就将其涂成灰色, 放到待搜索的栈中, 之后重新对其进行标记. 这样就可以保证不会回收到引用的对象, 虽然可能会有一些遗漏对象没有回收, 但是 who care? 下一次再回收。

也有不同的写入屏障处理方法, 在更新对象时进行不同操作。

相关书籍#

垃圾回收的算法与实现