最近在看周志明的《深入理解Java虚拟机》（第3版）。看第2版的时候还是多年之前，那时候才刚开始工作，每天回家只要有时间都会读一读，也算是JVM知识的启蒙。时光荏苒，白驹过隙，不过这本书依旧经典，值得一读，值得读好几遍。今天读到3.4.6 并发的可达性分析，挺有意思，做一些读书笔记。
之前也学习了，判断一个对象是否可以回收的一些方法，比如引用计数，在JVM中采用的是可达性分析。从GC Roots开始，一直向下遍历，能被引导的对象标记成不可回收，其余的就是可回收的对象了。这里其实有一个隐含的前提，就是在从GC Roots开始向下遍历的过程中，对象的引用关系不能发生变化，因为如果变化了，可能发生一个原本被判断为可回收的对象，又被GC Roots引用到了，但是最后会回收掉，那导致的程序错误是不可接受的。由于不停向下遍历的过程可以理解成一次搜索，不可能瞬间完成，而且这个过程随着堆的增大，几乎会线性增长，这样触发一次垃圾回收，光这个可达性分析的部分的耗时就会让用户难以接受，怎么优化呢？
其实这个问题到了一个关键点，如何在用户线程和标记线程并行的情况下，进行准确的标记？这里引用了一种叫做“三色标记”的工具，来帮助我们分析这个问题。
什么是“三色标记”
白色：表示对象尚未被垃圾收集器访问过
黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过
灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过
标记过程
1、初始状态，0为GC root节点，引用了1，1引用了2，2引用了3和4
2、0号节点找到了它的引用1，因为1还有引用2未遍历，此时1变成灰色
3、1号节点找到它的引用2，2因为还有3和4未遍历，所以2变成灰色；此时1的所有引用都被遍历了，变成黑色
4、2号几点找到它的引用3，因为引用4还未遍历，2号几点继续是灰色，3号节点无引用，变成黑色
5、2号几点继续找到它的引用4，此时4号节点无其他引用，变成黑色，2号几点也不存在未遍历的引用，变成黑色
至此，全部遍历完成。
异常情况
那么，如果这个标记过程如果和用户线程并发，可能会出现哪些情况呢？
1、例如在上述第4步之后，2对3的引用被移除，走到第5步之后，3应该可以被回收，但是因为在第4步被标记成黑色，所以也并不会被回收
这样有问题吗？当然有，3应该被回收，但是没有被及时回收；但是换个角度，这个问题可以被容忍，因为遍历的时间整体来说不会太长，发生这样情况的概率不大，3号节点逃过了本次回收，也还会有下一次等着他，并不会因为少量的应回收未及时回收而造成溢出。
2、如果在上述第4步之后，1增加了对4的引用，2对4的引用被移除，如图所示
这样就会造成4一直是白色，1因为已经是黑色了，不会再去遍历，所以1对4的引用并不会被感知到，这样的话4到最后都是白色的，会被回收掉。这就是“对象消息”的问题，种明明被GC Root引用，但是最后还是被回收掉的话，是绝对不可以接受的，那怎么解决呢？
Wilson于1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问题，即原本应该是黑色的对象被误标为白色：
1、赋值器插入了一条或者多条从黑色对象到白色对象的新引用
2、赋值器删除了全部从灰色对象到该白色对象的直接或间接引用
因此，我们的解法是破划掉上述其中任意一个条件，对应产生2种解决方案：增量更新和原始快照。
增量更新
当黑色标记的对象引用白色标记的对象时，就将这个新的引用记录下来，等并发扫描结束之后，再以这些记录过引用关系中的黑色对象为根，重新向下扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了，这个过程其实就是重新标记。
原始快照
当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。
其实这里对原始快照的理解，一开始会有很多疑问，很多可以用反证来证明，我也想了一些，篇幅所限，下次另开再讲，今天就先记录到这儿。