并发的可达性分析

CMS和G1都有一个并发标记的过程，并发标记要解决什么问题？带来了什么问题？怎么解决这些问题呢？

可达性分析算法需要一个理论前提：该算法的全过程都需要基于一个能保障一致性的快照才能够分析，这意味着必须全程冻结用户线程的运行。而为了不冻结用户线程的运行，那我们就需要让垃圾回收线程和用户线程同时运行。

并发标记，为了削减“标记”过程的停顿时间。

产生问题？
标记过程，用户线程仍在工作，会导致标记不准确。

三色标记

把遍历对象图过程中遇到的对象，按照“是否访问过”来标记成三种颜色：

可以看到，灰色对象是黑色对象与白色对象之间的中间态。当标记过程结束后，只会有黑色和白色的对象，而白色的对象就是需要被回收的对象。

垃圾回收器在对象图上面标记颜色，而同时用户线程在修改引用关系，引用关系修改了，那么对象图就变化了，这样就有可能出现两种后果：

浮动垃圾：一种是把原本消亡的对象错误的标记为存活，这不是好事，但是其实是可以容忍的，只不过产生了一点逃过本次回收的浮动垃圾而已，下次清理就可以。
对象消失：一种是把原本存活的对象错误的标记为已消亡，这就是非常严重的后果了，一个程序还需要使用的对象被回收了，那程序肯定会因此发生错误。

JVM_GC-Concurrent-Mark-Object-Disappear

Wilson，他在1994年在理论上证明了，只有同时满足以下两个条件时，会产生“对象消失”的问题，原来应该是黑色的对象被标记成了白色。

两个条件之间是当且仅当的关系，所以我们要解决并发标记时对象消失的问题，只需要破坏两个条件中的任意一个就行。

于是产生了两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

在HotSpot虚拟机中，CMS是基于增量更新来做并发标记的，G1则采用的是原始快照的方式。

增量更新要破坏的是第一个条件（赋值器插入了一条或者多条从黑色对象到白色对象的新引用），当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再以这些记录过的引用关系中的黑色对象为根，重新扫描一次。

可以简化的理解为：黑色对象一旦插入了指向白色对象的引用之后，它就变回了灰色对象。

原始快照要破坏的是第二个条件（赋值器删除了全部从灰色对象到该白色对象的直接或间接引用），当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再以这些记录过的引用关系中的灰色对象为根，重新扫描一次。

可以简化理解为：无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照开进行搜索。

需要注意的是，上面的介绍中无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。

增量更新用的是写后屏障(Post-Write Barrier)，记录了所有新增的引用关系。

原始快照用的是写前屏障(Pre-Write Barrier)，将所有即将被删除的引用关系的旧引用记录下来。