🍋 这次给大家介绍一下JVM垃圾回收可达性分析算法的实现原理。
🎈🎈🎈上篇文章《JVM垃圾回收-记忆集和卡表》 已经和大家介绍了JVM是如何快速的扫描和标记GC Roots的。标记 完GC Roots之后，JVM就需要从GC Roots开始遍历整个对象图了（即并发标记的过程）。
那么JVM又是如何遍历对象图的呢？
☕现代大多数跟踪垃圾收集器(如CMS、G1、Shenandoah)都实现[三色标记]{.blue}抽象的一些变体来对“垃圾”进行标记的。之所以都选择三色标记是因为它能够解决或者降低用户线程的停顿时间。 🚀🚀🚀
下面就进入本文正题：
三色标记
☘三色标记算法把遍历对象图过程中遇到的对象，按照“是否被访问过”分为以下三种颜色：
- 白色✨： 表示对象尚未被垃圾收集器访问过。 [（显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达）]{.grey}
- 灰色✨： 表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。
- 黑色✨： 表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。 [（黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接(不经过灰色对象)指向某个白色对象）]{.grey}
🌴🌴下面来看一下三色标记遍历对象图的大致过程：
⭐初始状态只有GC Roots是黑色的。被GC Roots直接引用的对象会变成灰色
⭐扫描过程中，按照以下两点扫描整个引用链
- 当前灰色节点没有子节点的话，将当前节点变为黑色。
- 当前灰色节点有子节点的话，当前节点变为黑色，且子节点变为灰色。
⭐扫描完成时，黑色对象就是存活的对象，白色对象就是已消亡可回收的对象
扫描完成之后，垃圾收集器只需要回收仍然是白色的对象所占用的内存即可。乍一看上面的过程好像没有什么问题，但是不要忘了我们的[收集线程是和用户线程并发执行的]{.green}。🚀🚀🚀
🌻🌻那么就会遇到一些问题了，我们的收集器在对象图上标记颜色的同时，用户线程在修改引用关系——即修改对象图的结构，这样可能会出现下面两种后果：
📍一种是把原本消亡的对象错误标记为存活，这不是好事，但其实是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好。
📍另一种是把原本存活的对象错误标记为已消亡，这就是非常致命的后果了，程序肯定会因此发生错误。
下面来演示一下上面的错误具体是如何产生的。
第一种：浮动垃圾
🍺假设 GC 线程已经遍历到 E（变为灰色了），此时D > E 的引用断开：
D > E 的引用断开之后，E、H、G 三个对象不可达，应该要被回收的。然而因为 E 已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮 GC 不会回收这部分内存。
👩这部分本应该回收但是没有回收到的内存，被称之为浮动垃圾。浮动垃圾并不会影响应用程序的正确性，下次收集时清理掉就好。
第二种：“对象消失”
🍬假设 GC 线程已经遍历到 E（变为灰色了），此时E > G 的引用断开，新增D > G 的引用：
👀此时因为 E 已经没有对 G 的引用了，所以不会将 G 置为灰色；尽管因为 D 重新引用了 G，但因为 D 已经是黑色了，不会再重新做遍历处理。
🍑最终导致的结果是：G 会一直是白色，最后被当作垃圾进行清除。这就是非常致命的后果了，程序肯定会因此发生错误，是不可以接受的。
🥇我们很容易看到发生这种错误是需要同时满足以下两个条件才可以成立的：
第一个条件： 赋值器插入了一条或多条从黑色对象到白色对象的新引用。(即新增D > G 的引用)
第二个条件： 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。(即断开E > G 的引用)
🍹我们要解决这个问题，只需破坏这两个条件中的任意一个条件 即可避免发生并发扫描时的对象消失问题。
🍍🍍先来破坏第一个条件，当黑色对象插入新的指向白色对象的引用关系时，我们就可以将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。 这种解决方案称为增量更新。
🍉🍉也可以破坏第二个条件，当灰色对象要删除指向白色对象的引用关系时，我们就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。 这种解决方案称为原始快照。
😎无论采用哪一种方案，都可以解决上面的问题。在HotSpot虚拟机中，增量更新和原始快照这两种解决方案都有实际应用，譬如，CMS就是基于增量更新来做并发标记的，G1、Shenandoah则是用原始快照方式来实现。
🙇读完上面的内容，相信大家已经对JVM并发标记的过程有了一定的了解。JVM虚拟机标记完不可达对象之后还需要对这些对象所占用的内存进行回收，具体的回收动作是由虚拟机采用哪款垃圾回收器所决定的。
🚀🚀🚀
