深入浅出JVM（十六）之三色标记法与并发可达性分析

深入浅出JVM（十六）之三色标记法与并发可达性分析

上篇文章深入浅出JVM（十五）之垃圾回收器（上篇）介绍性能指标吞吐量和延迟、串行收集器、并行收集器以及吞吐量优先收集器

为了更好的描述并发垃圾收集器，本篇文章将先深入浅出的介绍三色标记法以及并发可达性分析遇到的问题以及解决方案

三色标记法

JVM中使用可达性分析算法来判断对象是否继续使用

当对象不可达时，执行过finalize方法或者finalize方法搭不上引用链时才能回收这些对象

不理解如何判断对象不再使用的同学可以看这篇文章深入浅出JVM（十一）之如何判断对象“已死”

为了更好的说明并发可达性分析，我们使用三色标记法模拟，先说明三色标记法

三色标记法的颜色、流程说明

三色标记法的三种颜色说明

黑色：当前对象被扫描过，并且它引用的对象也被扫描

灰色：当前对象被扫描过，至少有一个引用未被扫描

白色：当前对象未被扫描过

GC 根节点总是黑色的，因为它们隐式可达

扫描时，从GC Roots节点（灰色）开始，将它引用的对象全染成灰色，再将自己染成黑色，再从灰色对象集合中遍历上述操作，类似树的层序遍历

当扫描完毕时，如果对象依旧是白色说明这个对象是不可达对象

比如图中的a变成黑色，说明a引用的对象b已经被扫描了；而b是灰色，说明b至少有一个引用的对象没被扫描（b引用的c就还未被扫描）

b将引用的c染成灰色后，将自己染成黑色，再从灰色对象集合中取出对象c进行后续操作

并发可达性分析

当GC、用户线程并发执行时，就会出现对象引用可能改变的情况，可能造成浮动垃圾和对象丢失的情况

浮动垃圾

一种情况会把原本死亡的对象改成活的对象，成为浮动垃圾，下次再回收掉

比如c将引用的d、e染成灰色后将自己染成黑色

因为还未扫描结束，用户线程将c引用e删除了c.e = null，本来e没有被引用应该变成垃圾

但由于并发执行，后续GC线程从灰色对象集合中获取d、e进行处理，最终会被染黑，e就变成浮动垃圾，本轮GC不会回收e

浮动垃圾的出现可以被接受，本轮不GC，下次GC也会进行回收

对象丢失

另一种情况会把原本存活的对象变成死亡的对象从而进行回收，十分危险

在从灰色对象拿出对象c 处理前，用户线程将c引用e删除c.e = null，后续c就不会将e染成灰色，只将d染成灰色

处理完对象c后，用户线程修改引用，让对象b引用对象eb.e = e，对象e变成需要使用的对象，但最终处理完d后，对象c依旧是白色

这种情况下就会发生对象丢失，对象c可能被GC回收，这种情况是危险的，不允许出现

经过研究表明对象消失需要满足的条件：

1. 插入一条或多条从黑色对象到白色对象的新引用
2. 删除全部从灰色对象到该白色对象的直接或间接引用

只需要破坏其中一条就可以避免对象消失

增量更新和原始快照分别破坏条件1、2

增量更新和原始快照会借助写屏障来处理，写屏障可以理解成AOP（在执行核心方法的前、后可以执行其他操作）

 //写前屏障处理
 //执行核心方法
 //写后屏障处理

增量更新

增量更新使用写后屏障，某个对象新增的引用时，将该对象记录下来，扫描完后将这个对象变为灰色对象重新扫描，在后续这个重新扫描的阶段需要用户线程STW

使用重新扫描，短暂STW的方式破坏条件一

用上面那张对象丢失的图举例的话，就是b对象在新增e引用时，后续会将b对象变为灰色重新扫描

重新扫描后，e对象最终也染黑

原始快照

原始快照使用写前屏障，在删除引用前保存要删除的引用，在扫描完毕后将这些删除的引用变为灰色对象重新扫描

原始快照破坏条件二，将白色对象变为灰色

并且GC开始后发生新增引用时，使用TAMS（Top at Mark Start）指针对新增引用进行记录（隐式可达）

对象c删除引用的对象e时记录对象e，扫描完毕时如下

STW重新扫描时，会将记录的对象e变灰色重新扫描，对象e变成了浮动垃圾；而新增的对象g用TAMS指针隐式可达直接变黑

由于被删除引用变灰，它可能变成浮动垃圾

增量更新：写后屏障，新增重扫（STW）

原始快照：写前屏障，删除变灰，新增隐式可达（开销大、可能有浮动垃圾）

总结

本篇文章围绕并发的可达性分析深入浅出的解析三色标记法、并发可达性分析可能出现的浮动垃圾，对象丢失问题以及解决对象丢失问题的增量更新、原始快照两种方式

在三色标记法中，黑色代表已经扫描完成、灰色代表至少有一个引用未扫描、白色代表还未扫描，GC根节点默认黑色隐式可达

三色标记法从GC根节点开始将引用对象变成灰色并放入灰色集合，并将自己变成黑色，接着再从灰色集合中取出下一个对象进行处理，直到灰色集合为空，还是白色的对象就是不可达对象

用户、GC线程并发执行时，可能改变对象的引用关系，可能造成浮动垃圾、对象消失的问题；浮动垃圾可以接受，下次GC会进行回收，但是对象消失是不能接受的

对象消失发生的两个条件是黑色对象新增到白色对象的引用和删除所有灰色对象到白色对象的间接/直接引用

增量更新使用写后屏障破坏条件一，记录新增白色对象引用的黑色对象，扫描完毕后STW将这个黑色对象变为灰色对象重新扫描

原始快照使用写前屏障破坏条件二，记录被删除的白色对象，使用TAMS指针让新增引用隐式可达，扫描完笔后STW将记录的白色对象变成灰色对象重新扫描，并且将隐式可达的对象变黑

最后（一键三连求求拉~）

本篇文章将被收入JVM专栏，觉得不错感兴趣的同学可以收藏专栏哟~

本篇文章笔记以及案例被收入 gitee-StudyJava、 github-StudyJava 感兴趣的同学可以stat下持续关注喔~

有什么问题可以在评论区交流，如果觉得菜菜写的不错，可以点赞、关注、收藏支持一下~

关注菜菜，分享更多干货，公众号：菜菜的后端私房菜