jvm-并发可达性分析的学习记录

本文主要针对周志明大大的《深入理解JVM 第三版》一书的3.4.6小节：并发的可达性分析做一个学习笔记。因为自己在前两遍读的时候没懂（菜鸡落泪.jpg），后面读懂了，遂赶紧记录一下，以备后面回顾或者帮助他人。

书中这一节主要从理论方面介绍JVM在垃圾收集时的并发的可达性分析这个阶段的正确性是如何保障的。

介绍并发的可达性之前，我们先明确一个前提：可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析， 这意味着必须全程冻结用户线程的运行（Stop The World，STW）。注意看修饰词是理论上，so，大佬们想出了办法来解决掉STW这种程序的梦魇从而实现并发的可达性分析（点题）。请仔细阅读上面这段文字，因为书里这一节的意图就是如此。

那我们先来看看理论上的可达性分析算法（会STW）。通俗点说就是：在进行可达性分析的时候，希望这时候不要有对象的引用变动的情况。如果有对象引用不断变动的情况，有可能会出现这样的情况：一个可以被回收的对象突然被一个不可回收的对象引用了，那我们就得重新标记这个对象为不可回收。如果有很多这种情况，那可达性分析算法还要不要正常工作了？

接下来借助三色标记（Tri-color Marking）作为工具辅助推导，搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历？

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

• 白色：表示对象尚未被垃圾收集器访问过。在可达性分析刚开始的时候，所有的对象都是白色的，在可达性分析结束的时候，如果对象还是白色的，表示这个对象不可达，也即可以被回收了。

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

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

倘若用户线程与收集器并发工作，也即用户线程在修改引用 关系——即修改对象图的结构，垃圾收集器在对象图上标记颜色。可能会出现把原本存活的对象错误标记为已消亡，这是很致命的后果，会导致程序发生错误。摘自《深入理解JVM》的下图具体解释了为什么发生这种现象：
在图中标记的①②我会用通俗的话再来说明：

对于①的情况：

从GC Root出发（黑色矩形）向下遍历对象图。在遍历过程中用户线程把灰色对象的一个引用切断了（虚线箭头），同时已经扫描过的黑色对象（黑色圆形）又与被切断的引用指向的对象（白色圆形）建立了引用关系。讲道理，这个白色对象被黑色对象引用，理应不会被回收了，但是由于被标记为黑色的对象不会进行重新扫描，所以无法把白色对象改变成黑色对象，导致本不应该被回收的对象错误地被回收了。

对于②的情况：

从GC Root出发（黑色矩形）向下遍历对象图。在遍历过程中，如果被切断的引用是引用链中的一部分（图中灰色对象虚线箭头所指的白色对象），由于被标记为黑色的对象不会进行重新扫描，所以这个被切断的引用所指的对象本来应该会被标记为黑色，却仍是白色，会被回收。

理解了为什么必须在一个能保障一致性的快照上才能进 行对象图的遍历的原因之后，我们看看怎么解决，也就是实现并发的可达性分析（不STW）

Wilson于1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问 题，即原本应该是黑色的对象被误标为白色：
①赋值器插入了一条或多条从黑色对象到白色对象的新引用；
②赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

所以，只需要破坏上面两个条件的任意一个，就不会出现“对象消失问题”。由此，产生了两种解决方案：增量更新方案和原始快照。

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

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

《！--毁灭吧，赶紧的，累了。--》