昨晚做梦面试官问我三色标记算法

本文已收录至 GitHub，推荐阅读 👉 Java随想录

微信公众号：Java 随想录

原创不易，注重版权。转载请注明原作者和原文链接

某天，爪哇星球上，一个普通的房间，正在举行一场秘密的面试：

面试官：我们先从 JVM 基础开始问，了解三色标记算法吗？

我：额......不了解。

面试官：出去的时候记得把门带上。

现在 Java 面试真的已经是越来越卷了，直接上来问原理给你直接干懵。

上篇我们讲了记忆集，这篇来聊聊「三色标记算法」，也是 Java 面试的常客。聊好了会让面试官觉得你这小伙子有点东西。

三色标记算法

既然叫三色标记算法，首先我们要搞明白是哪三色，三色是：黑色，白色，灰色。

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

• 白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。

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

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

《深入理解 Java 虚拟机》书中关于这块图画的很好，一目了然，直接上原图：

从上面这段话中，我们提炼一下关键要点：

• 初始阶段，GC Root 是黑色的，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。

• 如果有其他对象引用指向了黑色对象，无须重新扫描一遍。

• 黑色对象不可能直接指向某个白色对象。

让我来给大伙稍微解释一下第二点和第三点。

我上面画了一个示意图，第一幅和第二幅画的是对的，第三幅画的是错的。

先分析第二点，如果有其他对象引用指向了黑色对象，那么这个对象只能为灰色或者黑色，自然无须再重新扫描一遍。

然后再说第三点，黑色对象不可能直接指向某个白色对象。

我们从上面可知黑色对象的定义是：「对象的所有引用都已经扫描过」，而白色对象是：「对象尚未被垃圾收集器访问过」。

那么问题来了，如果黑色对象直接指向某个白色对象，那么他就跟黑色对象的定义矛盾了。

因为白色对象还没被访问过，怎么能算所有引用都扫描过了呢，所以他就不可能是黑色。

上面这个很重要，把这个理解透彻之后，我们看看三色标记算法存在的一些问题：

由于一些垃圾回收器存在垃圾回收线程和用户线程并发的情况（例如 CMS 的并发阶段），那么三色标记会有两个问题：

• 一种是把原本消亡的对象错误标记为存活，这不是好事，但其实是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好，问题不大。

• 另一种是把原本存活的对象错误标记为已消亡，这就是非常致命的后果了，程序肯定会因此发生错误。

第一点无伤大雅，所以我们解决问题的重心放到第二点上。

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

• 赋值器插入了一条或多条从黑色对象到白色对象的新引用。

• 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

其实一句话说白了就是：「跟灰色对象断开连接，跟黑色对象建立连接」。

因此，我们要解决并发扫描时的对象消失问题，只需破坏这两个条件中的任意一个即可。

由此分别产生了两种解决方案：「增量更新（Incremental Update）」和「原始快照（Snapshot At The Beginning，SATB）」。

这两个解决方案各破坏一个条件。

增量更新

增量更新要破坏的是第一个条件。

当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。

这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。

这其实有点像之前讲过类似 OopMap 的思想，本质也是维护了个映射关系，扫描结束的时候把这个映射关系再重新扫描一遍，不用全局扫描。

如图，将这个新插入的引用关系记录下来，扫描结束之后，将记录过的引用关系中的黑色对象 1 为根，重新扫描一次，就 OK 了。

原始快照

原始快照要破坏的是第二个条件。

当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。

这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的「对象图快照」来进行搜索，故名「原始快照」。

如图，将这个删除的引用关系记录下来，扫描结束之后，将记录过的引用关系中的灰色对象 2 为根，重新扫描一次，就 OK 了。

那么有个问题，增量更新和原始快照都需要记录引用关系，那这个记录的时间点发生在什么时刻呢？

不知道大家还是否记得之前说过的「写屏障」，是的没错。

无论是增量更新还是原始快照，虚拟机的记录操作都是通过写屏障实现的。

写屏障，我们之前讲记忆集与卡表的时候介绍过的，可以理解为 Spring 中的 AOP，目前为止卡表状态的维护，增量更新，原始快照都是基于写屏障。

另外，课外拓展一下，CMS 使用的是增量更新，G1 使用的是原始快照。

本篇文章就到这了，本篇篇幅可能有点短，不过能把事情说清楚就行。之后开始讲垃圾回收器，大家一起期待下吧。

用心写文章，大伙要是有收获，希望点个赞激励一下，thank you。

感谢阅读，如果本篇文章有任何错误和建议，欢迎给我留言指正。

老铁们，关注我的微信公众号「Java 随想录」，专注分享 Java 技术干货，文章持续更新，可以关注公众号第一时间阅读。

一起交流学习，期待与你共同进步！