【JVM】聊聊垃圾回收之三色标记算法

在垃圾收集器 CMS中存在四个阶段，初始标记、并发标记、重新标记、并发清理。

那么在并发标记中由于没有STW，业务程序和GC程序是并发执行的，那么是如何实现对象的并发标记的。

并发垃圾回收

并发标记其实是一个宏观的过程，仍然需要STW，只不过减少STW的时间。

初始标记：标记GC Roots，并发标记是在应用程序不暂停的情况下，以GC Roots为起点，广度或者深度遍历所有可达对象。因为在这个过程中，应用程序和GC程序是并发执行的，所有很有可能对象的引用关系随时变化。导致并发标记过程出现标记错误。而重新标记的就是为了调整对标记错误的进行修正。并发清理是在应用程序不暂停的情况下，对垃圾对象进行清理

初始、并发、重新标记 三个阶段属于可达性分析，标记环节。

GC垃圾收集器的其实就是在吞吐量和STW之间权衡，为了减少STW对业务的影响，只能利用并发执行。

三色标记算法

三色标记是应用程序还在执行，对象引用关系随时会发生变化，所以引入三色标记算法。

白色对象: 没有被遍历过的对象，在开始遍历时都是白色对象，在经过可达性分析之后，还是白色，那么就是可被回收的对象。
灰色对象： 该对象已经被遍历，但是所引用的对象没有被遍历完。
黑色对象： 对象已经被遍历，所引用的对象已全部被遍历。

核心流程：
1.初始化将GC roots对象设置为灰色，其他对象为白色
2.以GC roots 开始遍历，将可达对象设置为灰色，自己设置为黑色
3.重复执行上述，最后是白色的对象就是不可达对象。

而1就是初始标记阶段，2、3是并发标记阶段。

说白了就是一个游戏，大家成群结对，找到不在队伍中的人员，开始都是一样的颜色，经过标记后，脱离队伍的一定是初始颜色的同学。

漏标和误标

在并发标记的过程，因为应用程序在同步执行，所以可能将存活对象标记为死亡对象称为漏标，将死亡对象标记为存活对象称为误标，后者是不可接受的，前者在下一次GC时会被清理。

误标

如果目前对象标记状态时如下图，那么当objA.fieldB = null ，因为本身A对象已经被标记为黑色，那么B以及B引用的对象都将标记为存活对象。

漏标

如果目前对象标记时上图所以，执行

objA.filedc = objA.fileB.filedC;
objA.fileB.fileC = null;

那么B到C之间的引用会断开，A和C之间建立连接。因为A是黑色对象，不会在遍历A的引用对象，从而出现漏标，将存活对象标记为死亡对象。

增量更新和原始快照

对于误标其实问题不大，大不了下一次在执行GC的时候处理，但是对于漏标就问题很大，会将存活的对象标记为死亡对象。

产生漏标的主要是两点
1.产生了一个新引用，黑色对象到白色对象的引用
2.删除引用：删除灰色对象到白色对象的所有引用

两种解决方案：增量更新和原始快照，增量更新记录新增的引用关系，原始快照记录的是删除的引用关系。CMS使用增量更新，G1使用原始快照。

增量更新

在并发标记中，如果应用程序新增了一个黑色对象对一个白色对象的引用，那么就将这个白色对象记录下来，在并发标记完成之后，重新标记以白色标记的对象，进行可达性分析。这样漏标的对象就会重新标记为黑色对象。

原始快照

增量更新是对新增的，而原始快照针对的是当删除一个白色对象对于灰色对象的引用时，虚拟机会记录这个白色对象，在完成并发标记阶段后，在可达性分析这些白色对象的引用关系。

对于上述不管时什么其实都需要在代码的新增和删除引用的过程进行拦截处理，也叫读写屏障。
虚拟机的记录操作都是通过写屏障实现的。

写屏障

给某个对象的成员变量赋值时，其底层代码大概长这样:

 /**
 * @param field 某对象的成员变量，如 a.b.d
 * @param new_value 新值，如 null
 */
 void oop_field_store(oop* field, oop new_value) {
	 *field = new_value; // 赋值操作
}

所谓的写屏障，其实就是指在赋值操作前后，加入一些处理(可以参考AOP的概念)

 void oop_field_store(oop* field, oop new_value) {
	 pre_write_barrier(field); // 写屏障‐写前操作
 	 *field = new_value;
 	 post_write_barrier(field, value); // 写屏障‐写后操作
}

写屏障实现SATB
当对象B的成员变量的引用发生变化时，比如引用消失(a.b.d = null)，我们可以利用写屏障，将B原来成员变量的引用对象D记录下来:

void pre_write_barrier(oop* field) {
	oop old_value = *field; // 获取旧值
 	remark_set.add(old_value); // 记录原来的引用对象
}

写屏障实现增量更新
当对象A的成员变量的引用发生变化时，比如新增引用(a.d = d)，我们可以利用写屏障，将A新的成员变量引用对象D 记录下来:

 void post_write_barrier(oop* field, oop new_value) { 
  remark_set.add(new_value); // 记录新引用的对象
}

读屏障

读屏障是直接针对第一步:D d = a.b.d，当读取成员变量时，一律记录下来:

 void pre_load_barrier(oop* field) {
	oop old_value = *field;
	remark_set.add(old_value); // 记录读取到的对象
}

CMS:写屏障 + 增量更新
G1，Shenandoah:写屏障 + SATB
ZGC:读屏障

并发清理和新建对象

在最后的阶段，并发清理阶段，其实存活对象可能变成死亡对象，那么只需要在下次GC时进行回收就可以了，那么死亡对象可能变成存活对象嘛，从而导致被清理掉嘛？
因为死亡对象不在有变量可以直接被引用。

** 为什么CMS和G1都使用标记-清除而非标记-整理算法来回收老年代的垃圾对象？**
垃圾回收时间快，减少STW时间。在多次垃圾回收之后进行一次碎片整理有效避免了分配效率问题和空间利用率问题。

小总

本篇主要介绍了垃圾回收算法中CMS中 并发标记阶段中的主要问题，从而引出漏标和误标，而解决漏标的问题主要增量更新和原始引用，而都是通过底层的读写屏障解决的。