CMS 三色标记法

为什么引入三色标记法

为了提供 JVM 垃圾回收的性能,从 CMS 垃圾收集器开始,引入了并发标记的概念(此处的并发标记是指与用户线程一起工作)。引入并发标记的过程就会带来一个问题,在业务执行的过程中,会对现有的引用关系链出现改变。具体如下图:

image-20210626215542908

当 GC 线程开始标记对象的时候,如果这个时候用户线程修改了 F 和 A 的引用,因为此时 A对象已经被遍历完成了,GC线程就不会再对 A 有新的标记操作,这样 GC 线程就会认为 B,C,D 对象没有被任何对象引用,就会被当成垃圾回收。

很明显在并发的情况下,“两色“的标记法是无法满足要求的。

三色标记的过程

为了解决并发的问题,我们可以引入中间的状态(灰色),当一个对象被标记的时候,会有下面几个过程:

  1. 首先被标记成灰色
  2. 检测当前所有的灰色对象,遍历子节点
  3. 如果子节点被遍历完了,把当前节点标记成黑色

image-20210626221314219

在上图中,第一个过程是把 A,E 标记成灰色,后续再遍历 A,E 的子节点,发现了 A 有 C 节点,E 有 F 节点,这样 C,F在后续就会被标记成活着的对象(此处还会存在缺陷,后面讨论)

三色标记的问题

从上面的分析可以得出,三色标记法解决了并发的场景的引用链变动的问题,但是也会存在问题。

在上面的场景中,如果 GC 线程标记 A 成黑色后,用户线程修改了 A 的引用,这个时候 A 是黑色,C 因为没有找到引用的变量,还是会被当成垃圾回收。

CMS 是如何处理的

理解了问题的本质,问题就容易解决了,G1 收集器采用的 SATB 解决方案(略),CMS 采用了 Incremental Update 解决方案:如果发现对象子节点有新的引用,增加一个写入屏障,同时把黑色改成灰色

在采用了 Incremental Update 解决方案后,还是会存在一个巨大的缺陷,在上述的场景中,如果有多个 GC 线程对 A 标记,两个线程判断可能存在不一致,具体如下图:

image-20210626225404368

在上面的场景中,我们假设GC 线程 1 发生在用户线程之前,GC 线程 2 发生在业务线程后:

当 GC 线程 1 发现 A 有没有,会把 A 变成黑色。

当 GC 线程 2 发现 A 有子节点,会把 A 变成灰色。

这样就对垃圾回收的结果产生了误判,所以CMS 在并发标记后还需要一次重新标记,当然这次重新标记会带来更长的 STW。
这个也许是 CMS 不是任何版本 JDK 的默认垃圾回收器了。