JVM (十一) 三色标记

前言：

所有的垃圾回收算法都要经历标记阶段。如果 GC 线程在标记的时候暂停所有用户线程（STW），那就没三色标记什么事了。但是这样会有一个问题，用户线程需要等到 GC 线程标记完才能运行，给用户的感觉就是很卡，用户体验很差。

现在主流的垃圾收集器都支持并发标记。什么是并发标记呢？就是标记的时候不暂停或少暂停用户线程，一起运行。这样就会出现标记对象的过程中又有新的对象产生，或者标记对象过程中有改变对象引用的操作，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。那这些情况标记过程中怎么处理呢？这就设计到标记算法了。

标记算法就是标记出那些对象是可以回收的，然后再执行回收操作。

三色标记，是把对象分成三种不同的颜色来表示不同的状态。来表示是否可以进行回收。

从 GCRoot 对象开始扫描访问。

• 白色：尚未访问过。
• 黑色：本对象已访问过，而且本对象 引用到 的其他对象 也全部访问过了。标记过程中新产生的对象也是黑色的。
• 灰色：本对象已访问过，但是本对象 引用到 的其他对象 尚未全部访问完。全部访问后，会转换为黑色。

 

假设现在有白、灰、黑三个集合（表示当前对象的颜色），其遍历访问过程为：

1、 初始时，所有对象都在【白色集合】中；
2、 将 GCRoots 直接引用到的对象挪到【灰色集合】中；
3、 从灰色集合中获取对象：；
3、 1.将本对象引用到的其他对象全部挪到【灰色集合】中；
3、 2.将本对象挪到【黑色集合】里面；
4、 重复步骤 3，直至【灰色集合】为空时结束；
5、 结束后，仍在【白色集合】的对象即为 GCRoots 不可达，可以进行回收；

多标-浮动垃圾

假设已经遍历到 E（变为灰色了），此时应用执行了 objD.fieldE = null ：

 

此刻之后，对象 E/F/G 是“应该”被回收的。然而因为E 已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮 GC 不会回收这部分内存。

这部分本应该回收 但是 没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。

另外，针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能会变为垃圾，这也算是浮动垃圾的一部分。

漏标-读写屏障

 

假设 GC 线程已经遍历到 E（变为灰色了），此时应用线程先执行了：

var G = objE.fieldG;
objE.fieldG = null;  // 灰色E 断开引用 白色G
objD.fieldG = G;  // 黑色D 引用 白色G

此时切回 GC 线程继续跑，因为 E 已经没有对 G 的引用了，所以不会将 G 放到灰色集合；尽管因为 D 重新引用了 G，但因为 D 已经是黑色了，不会再重新做遍历处理。
最终导致的结果是：G 会一直停留在白色集合中， 最后被当作垃圾进行清除。这直接 影响到了应用程序的正确性，是不可接受的。

---

---

不难分析，漏标只有 同时满足以下两个条件时才会发生：
条件一：灰色对象 断开了 白色对象的引用（直接或间接的引用）；即灰色对象 原来成员变量的引用 发生了变化。
条件二：黑色对象 重新引用了 该白色对象；即黑色对象 成员变量增加了 新的引用。

从代码的角度看：

var G = objE.fieldG; // 1.读
objE.fieldG = null;  // 2.写
objD.fieldG = G;     // 3.写

1、 读取对象 E 的成员变量 fieldG 的引用值，即对象 G；
2、 对象 E 往其成员变量 fieldG，写入 null 值；
3、 对象 D 往其成员变量 fieldG，写入对象 G；

我们只要在上面这三步中的任意一步中做一些“手脚”， 将对象 G 记录起来，然后作为灰色对象再进行遍历即可。比如放到一个特定的集合，等初始的 GC Roots 遍历完（并发标记），该集合的对象 遍历即可（重新标记）。

重新标记是需要 STW 的，因为应用程序一直在跑的话，该集合可能会一直增加新的对象，导致永远都跑不完。当然，并发标记期间也可以将该集合中的大部分先跑了，从而缩短重新标记 STW 的时间，这个是优化问题了。

写屏障用于拦截第二和第三步；而读屏障则是拦截第一步。
它们的拦截的目的很简单：就是在读写前后，将对象 G 给记录下来

上面漏标的情况，由于 G 会被回收，会导致程序过程中使用会有问题，为了避免这个问题，有两种方法解决这个问题：

增量更新：

在标记程序运行过程中发生了引用链的变动，通过写屏障将这个变动记录下来，比如对象 A 对 D 建立新的引用时，将 D 放入一个 OopMap 中，作为灰色对象，并发标记结束后对这个 OopMap 进行遍历，就可以避免漏标的情况。解决条件二。

**原始快照：**SATB

这种方式解决的是条件一，带来的结果是依然能够标记到D，具体做法如下：
对象B的引用关系变动的时候，即给B对象中的某个属性赋值时，将之前的引用关系记录下来。 标记的时候，扫描旧的对象图，这个旧的对象图即原始快照。