本文是对 「A Generational Mostly-concurrent Garbage Collector」论文的学习笔记。

Mostly-concurrent Collection

该算法一般会分为四个步骤:

  • Initial marking pause(初始标记)
    • 从名字可以看出来,这个阶段会暂停用户线程(Stop The World),这个阶段标记 GC ROOT 可直接到达的对象。
  • Concurrent marking phase(并发标记)
    • 这个阶段与用户线程一起执行,对每个可到达的对象进行传递标记。传递标记的过程不能保证在并发标记阶段结束后,标记全部可到达对象。因为与用户线程一同执行的时候,可能阻止了一些可到达对象的标记。为了处理这个复杂的情况,GC 算法还提供了对堆中对象的引用更新跟踪。这个用户线程与 GC 线程之前的唯一交互。
  • Final marking pause(重新标记/最后标记)
    • 名字也可以看出,这个阶段会暂停用户线程(Stop The World),并且完成整个通过 GC ROOT 标记的阶段,在并发标记阶段由于引用修改被标记的对象,会作为附加的 GC ROOT。这样来确保在「重新标记」阶段结束开始时,包含了所有可到达的对象。当然也有可能包含了一些不可到达的对象,他们也被标记了。
  • Concurrent sweeping phase(并发清除)
    • 这个阶段对堆上面的内存进行扫描,释放没被标记的对象的内存。需要注意的是不要将新分配的对象释放掉。

看如下一个例子:

这个例子当中堆内包含了 7 个对象,并且分成了 4 个 pages。初始标记后,所有的 4 个 pages 都是干净的并且对象 a 是活着的,因为他可以在一个线程当中被访问。

「上图 a」 这行,展示的堆正在并发标记的途中,对象 b ,c,e 已经被标记。这个时候用户线有了 2 处更新,对象 g 去掉了对象 d 的引用和对象 b 对 c 的引用转成了对 d 的引用。更新后的结果是「上图 b」。并且 page 1 和 3 由于更新变脏了。

「上图 c」 展示了堆的并发标记结束状态。可以清晰的看到,当前的标记是不完整的。对象 b 指向了一个未被标记的对象 d。在「重新标记」阶段会对所有变脏的 pages 当中重新扫描被标记的对象。因此这个例子当中,对象 b 和 g 在「重新标记」阶段会被重新扫描。

「上图 d」展示了堆在重新标记之后的状态。现在整个标记完成。接着会进行「并发清除」阶段,对象 f 会被回收掉。对象 f 是不可到达对象,因此一个 GC 周期肯定会被回收掉。对象 c 虽然也是不可到达,但是被标记了,所以会等下次 GC 周期才会被回收掉。