三色标记算法

可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，首先搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历？

引入三色标记法，来说明这个问题。

把遍历对象图过程中遇到的对象，按照是否访问过这个条件标记成以下三种颜色：

白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。
黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。
灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

原书中的图画的太好了，一目了然，这里直接展示原图。

对象只有被黑色对象引用才能存活。

想想之前的问题：为什么必须在一个能保障一致性的快照上才能进行对象图的遍历？

如果不能保证一致性，会有2个问题：

Wilson于1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色：

因此，我们要解决并发扫描时的对象消失问题，只需破坏这两个条件的任意一个即可。由此分别产生了两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

这2种解决方案各破坏一个条件

增量更新

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

这其实有点像之前讲过类似OopMap的思想，本质也是维护了个映射关系，重新扫描的时候扫描这个映射关系就行了，不用全表扫描。

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

以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。写屏障，我们之前讲记忆集与卡表的时候介绍过的，可以理解为Spring中的AOP，目前为止卡表状态的维护，增量更新，原始快照都是基于写屏障。

来源：https://www.cnblogs.com/booksea/p/16991219.html
本站部分图文来源于网络，如有侵权请联系删除。