并发的可达性分析（三色标记法）

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象 是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析， 这意味着必须全程冻结用户线程的运行。

为了减少冻结用户线程的影响，提高效率，采用并发标记的方法

并发标记的作用

根据 可达性分析算法 的核心概念，利用系列根对象（GC Roots ）作为起始点，根据对象之间的引用关系搜索出一条引用链，通过遍历引用链来判断对象的是否存活。

在这个过程中，根对象枚举的时间非常短暂且相对固定，然而，遍历所有引用链（对象图）所需要的时间与对象的数量成正比。因此，对象越多，对象之间的引用关系就越复杂，需要更多的时间去遍历所有的引用链来标记所有的对象。

并发标记的作用就是让垃圾回收线程和用户线程能够同时进行，并发执行。

下面用三色标记法进行说明

三色标记法

• 白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是 白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达

• 黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代 表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对 象不可能直接（不经过灰色对象）指向某个白色对象。

• 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过，也就是还可以继续扫描

当且仅当以下两个条件同时满足时，会产生“对象消失”的问 题，即原本应该是黑色的对象被误标为白色：

• 插入了一条或多条从黑色对象到白色对象的新引用

• 删除了全部从灰色对象到该白色对象的直接或间接引用

解决方案

增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新 插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫 描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象 了。

原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删 除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描 一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来 进行搜索。