三色标记

标记算法

三色标记法把遍历对象图过程中遇到的对象，标记成以下三种颜色：

• 白色：尚未访问过
• 灰色：本对象已访问过，但是本对象引用到的其他对象尚未全部访问
• 黑色：本对象已访问过，而且本对象引用到的其他对象也全部访问完成

当 Stop The World (STW) 时，对象间的引用是不会发生变化的，可以轻松完成标记，遍历访问过程为：

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

并发标记

并发标记时，对象间的引用可能发生变化，多标和漏标的情况就有可能发生

多标情况：当 E 变为灰色或黑色时，其他线程断开的 D 对 E 的引用，导致这部分对象仍会被标记为存活，本轮 GC 不会回收这部分内存，这部分本应该回收但是没有回收到的内存，被称之为浮动垃圾

• 针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，也算浮动垃圾
• 浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除

漏标情况：

• 条件一：灰色对象断开了对一个白色对象的引用（直接或间接），即灰色对象原成员变量的引用发生了变化
• 条件二：其他线程中修改了黑色对象，插入了一条或多条对该白色对象的新引用
• 结果：导致该白色对象当作垃圾被 GC，影响到了程序的正确性

代码角度解释漏标：

Object G = objE.fieldG; // 读
objE.fieldG = null;  	// 写
objD.fieldG = G;     	// 写

为了解决问题，可以操作上面三步，将对象 G 记录起来，然后作为灰色对象再进行遍历，比如放到一个特定的集合，等初始的 GC Roots 遍历完（并发标记），再遍历该集合（重新标记）

所以重新标记需要 STW，应用程序一直在运行，该集合可能会一直增加新的对象，导致永远都运行不完

解决方法：添加读写屏障，读屏障拦截第一步，写屏障拦截第二三步，在读写前后进行一些后置处理：

• 写屏障 + 增量更新：黑色对象新增引用，会将黑色对象变成灰色对象，最后对该节点重新扫描

  增量更新 (Incremental Update) 破坏了条件二，从而保证了不会漏标

  缺点：对黑色变灰的对象重新扫描所有引用，比较耗费时间

• 写屏障 (Store Barrier) + SATB：当原来成员变量的引用发生变化之前，记录下原来的引用对象

  保留 GC 开始时的对象图，即原始快照 SATB，当 GC Roots 确定后，对象图就已经确定，那后续的标记也应该是按照这个时刻的对象图走，如果期间对白色对象有了新的引用会记录下来，并且将白色对象变灰（说明可达了，并且原始快照中本来就应该是灰色对象），最后重新扫描该对象的引用关系

  SATB (Snapshot At The Beginning) 破坏了条件一，从而保证了不会漏标

• 读屏障 (Load Barrier)：破坏条件二，黑色对象引用白色对象的前提是获取到该对象，此时读屏障发挥作用

以 Java HotSpot VM 为例，其并发标记时对漏标的处理方案如下：

• CMS：写屏障 + 增量更新
• G1：写屏障 + SATB
• ZGC：读屏障