并发可达性分析

回顾与问题：

在可达性分析算法中，需要有根节点枚举，然后从根节点开始遍历对象图。

根节点枚举中，GC Roots相比于整个堆的对象占比还是较小的，且有OopMap这种优化技巧，

因此根节点枚举带来的停顿时间是短暂且相对固定的（不会随着堆容量而增长）。

但是！从GC Roots遍历对象图，这一步的停顿时间是会和堆容量成正比的。

三色标记（Tri-color Marking）

要解决或降低用户线程的停顿，需要明白一点，就是必须在一个保障一致性的快照上才能进行对象图的遍历。

三色标记可以帮助理解这一点。

按照“是否被访问过”这个条件将对象标记成以下三个颜色

• 白色

  对象尚未被垃圾收集器访问过。在可达性分析开始阶段，所有对象都是白色的。

  分析结束时，仍是白色的对象即代表不可达。

• 黑色

  表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。

  黑色对象是存活的，如果有对象引用指向了黑色对象，无须在扫描一遍。

  （标识最开始的时候，GC Roots都是黑色的，其他对象都是白色的）。

• 灰色

  表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

并发标识时的问题及方案

如果标识的过程中用户线程是冻结的，那就不会有任何问题。

如何是并发的，那就可能出现如下情况：

• 用户线程将一个黑色对象引用了一个白色对象。由于黑色对象不会再扫描，

  最终导致被白色对象被认为不可达。

错误地认为对象不可达必须同时满足两个条件：

• 赋值器插入了一条或多条从黑色对象到白色对象的新引用
• 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

方案：

只要破环两个条件中的任意一个即可。因此有两种方案

• 增量更新（Incremental Update）

  破坏的是第一个条件

  当黑色对象插入新的指向白色对象的引用关系时，记录这个引用，等并发扫描结束后重新扫描一遍。

  相当于黑色对象变成了灰色对象。

• 原始快照（Shapshot At The Begining，SATB）

  破坏的是第二个条件

  当灰色对象要删除白色对象的引用关系时，记录删除的引用，等并发扫描结束后将记录中的灰色节点为

  根重新扫描一次。

对于引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。

CMS是基于增量更新来做并发标记的，G1、Shenandoah则是原始快照。

思考及疑问

• 关于三色标记。如果是新创建一个对象，然后黑色对象引用了这个对象，这种情况下这个新对象也是不会被标记为黑色对象的。 也就是不需要满足第二点，也能出现黑色对象（假设新创建的对象不应该被回收）被误标记为白色的情况了。

  三色标记只是帮助理解并发标记。

  新建一个对象，可以理解为天然满足第二点。