本文已收录至 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 技术干货，文章继续更新，能够关注公众号第一工夫浏览。
一起交流学习，期待与你共同进步！