最近和一个敌人聊天，他问了我 JVM 的三色标记算法。我脑袋一愣发现居然齐全不晓得！于是我带着疑难去网上看了几天的材料，终于搞清楚啥事三色标记算法，它是用来干嘛的，以及它和 CMS 回收器和 G1 回收器的关系了。明天，就让树哥带着大家一起盘一盘它！
根可达算法
咱们要进行垃圾回收，就须要弄明确哪些对象是须要回收的，哪些对象是不须要回收的。针对这个问题，其实业界曾经有几种常见的解决办法了。
第一种是计数法，就是每个对象都有一个计数器，被援用了加一，移除援用减一。但这种办法比拟麻烦，而且也会有循环依赖的问题，因而并不被宽泛应用。第二种是根可达算法，即以 GCRoots 为根底去扫描整个援用链，从而找到所有的可达对象，那剩下的其余对象就是不可达的垃圾对象了。
当初被宽泛应用的是第二种算法，即根可达算法。
那怎么去实现根可达算法呢？
最简略的一种实现计划是：从 GCRoots 节点开始，应用「标记 - 革除」算法去实现。
这种实现计划分为两个阶段，别离是：标记阶段、革除阶段。在标记阶段，它从 GCRoots 节点开始扫描整个援用链，找到所有可达的对象。在革除阶段，扫描整个援用链的不可达对象，而后将垃圾对象革除掉。整个算法实现过程如下图所示。
但这种形式有一个很大的毛病：整个过程必须「Stop the World」。这就导致整个应用程序必须进行，不能做任何扭转，这是十分不敌对的。CMS 回收器呈现之前的所有回收器，都是用这种形式实现的，因而 GC 进展工夫都比轿长。
三色标记算法
为了解决下面「标记 - 革除」算法的问题，于是就呈现了「三色标记算法」！
三色标记算法指的是将所有对象分为红色、彩色和灰色三种类型。彩色示意从 GCRoots 开始，已扫描过它全副援用的对象，灰色指的是扫描过对象自身，还没齐全扫描过它全副援用的对象，红色指的是还没扫描过的对象。
但仅仅将对象划分成三个色彩还不够，真正要害的是：实现根可达算法的时候，将整个过程拆分成了初始标记、并发标记、从新标记、并发革除四个阶段。
- 初始标记阶段，指的是标记 GCRoots 间接援用的节点，将它们标记为灰色，这个阶段须要「Stop the World」。
- 并发标记阶段，指的是从灰色节点开始，去扫描整个援用链，而后将它们标记为彩色，这个阶段不须要「Stop the World」。
- 从新标记阶段，指的是去校对并发标记阶段的谬误，这个阶段须要「Stop the World」。
- 并发革除，指的是将曾经确定为垃圾的对象革除掉，这个阶段不须要「Stop the World」。
比照一下「四阶段拆分」和「一段式」的实现形式，咱们能够看出：通过将最耗时的援用链扫描剥离进去作为并发标记阶段，将其与用户线程并发执行，从而极大地升高了 GC 进展工夫。但 GC 线程与用户线程并发执行，会带来新的问题：对象援用关系可能会发生变化，有可能产生多标和漏标问题。
多标与漏标问题
多标问题指的是本来应该回收的对象，被多余地标记为彩色存活对象，从而导致该垃圾对象没有被回收。多标问题会呈现，是因为在并发标记阶段，有可能之前曾经被标记为存活的对象，其援用被删除，从而变成了不可达对象。例如下图中，假如咱们当初遍历到了节点 E，此时利用执行了 objD.fieldE = null;。那么此刻之后，对象 E、F、G 应该是被回收的。但因为节点 E 曾经是灰色的，那么 E、F、G 节点都会被标记为存活的彩色状态，并不会被回收。
多标问题会导致内存产生浮动垃圾，但好在其能够再下次 GC 的时候被回收，因而问题还不算很重大。
漏标问题指的是本来应该被标记为存活的对象，被脱漏标记为彩色，从而导致该垃圾对象被谬误回收。例如下图中，假如咱们当初遍历到了节点 E，此时利用执行如下代码。这时候因为 E 对象没有援用了 G 对象，因而扫描 E 对象的时候并不会将 G 对象标记为彩色存活状态。但因为用户线程的 D 对象援用了 G 对象，这时候 G 对象应该是存活的，应该标记为彩色。但因为 D 对象曾经被扫描过了，不会再次扫描，因而 G 对象就被漏标了。
var G = objE.fieldG;
objE.fieldG = null; // 灰色 E 断开援用 红色 G
objD.fieldG = G; // 彩色 D 援用 红色 G 漏标问题就十分重大了，其会导致存活对象被回收，会重大影响程序性能。
那么咱们的垃圾回收器是怎么解决这个问题的呢？
答案是：减少一个「从新标记」阶段。无论是在 CMS 回收器还是 G1 回收器，它们都在并发标记阶段之后，新增了一个「从新标记」阶段来校对「并发标记」阶段呈现的问题。只是对于 CMS 回收器和 G1 回收器来说，它们解决的原理不同罢了。
漏标解决方案
正如后面所说，三色标记算法会造成漏标和多标问题。但多标问题绝对不是那么重大，而漏标问题才是最重大的。咱们通过剖析能够晓得，漏标问题要产生须要满足如下两个充要条件：
- 有至多一个彩色对象在本人被标记之后指向了这个红色对象
- 所有的灰色对象在本人援用扫描实现之前删除了对红色对象的援用
只有当下面两个条件都满足，三色标记算法才会产生漏标的问题。换言之，如果咱们毁坏任何一个条件，这个红色对象就不会被漏标。这其实就产生了两种形式，别离是：增量更新、原始快照。CMS 回收器应用的增量更新计划，G1 采纳的是原始快照计划。
CMS 解决方案
CMS 回收器采纳的是增量更新计划，即毁坏第一个条件：「有至多一个彩色对象在本人被标记之后指向了这个红色对象」。
既然有彩色对象在本人标记后，又从新指向了红色对象。那么我就把这个彩色对象的援用记录下来，在后续「从新标记」阶段再以这个彩色对象为跟，对其援用进行从新扫描。通过这种形式，被彩色对象援用的红色对象就会变成灰色，从而变为存活状态。
这种形式有个毛病，就是会从新扫描新增的这部分彩色对象，会节约多一些工夫。然而这段时间绝对于并发标记整个链路的扫描，还是小巫见大巫，毕竟真正产生援用变动的彩色对象是比拟少的。
G1 解决方案
G1 回收器采纳的是原始快照的计划，即毁坏第二个条件：「所有的灰色对象在本人援用扫描实现之前删除了对红色对象的援用」。
既然灰色对象在扫描实现后删除了对红色对象的援用，那么我是否能在灰色对象勾销援用之前，先将灰色对象援用的红色对象记录下来。随后在「从新标记」阶段再以红色对象为根，对它的援用进行扫描，从而防止了漏标的问题。通过这种形式，本来漏标的对象就会被从新扫描变成灰色，从而变为存活状态。
这种形式有个毛病，就是会产生浮动垃圾。因为当用户线程勾销援用的时候，有可能是真的勾销援用，对应的对象是真的要回收掉的。这时候咱们通过这种形式，就会把本该回收的对象又复活了，从而导致呈现浮动垃圾。但绝对于本该存活的对象被回收，这个代码还是能够承受的，毕竟在下次 GC 的时候就能够回收了。
对于 CMS 和 G1 这两种解决计划哪种更好，很多材料说的是 G1 这种解决方案更好。起因是其感觉 G1 这种形式产生了一些浮动垃圾，但节俭了一些工夫。但我比照了一下发现：CMS 和 G1 都须要从新对某些元素进行援用链扫描。从这点看来，如同差异不大。有弄懂的敌人能够评论区留言探讨探讨。
总结
看完了整篇文章，咱们试图来答复一些问题。
三色标记算法是什么？三色标记算法是根可达算法的一种实现计划，其目标是为了找出所有可达对象。
为什么要有三色标记算法？因为传统的「标记 - 革除」算法效率太低，于是采纳三色标记算法通过将对象分成红色、彩色、灰色，以及将整个过程拆分成「初始标记、并发标记、从新标记、并发革除」4 个过程，从而升高 GC 进展工夫。
三色标记算法有什么缺点？三色标记算法会产生多标和漏标问题，其中漏标问题最重大。漏标问题会导致本该存活的对象被回收，从而导致重大的程序问题。
漏标有什么解决方案？漏标有两种解决方案，别离是：增量更新和原始快照形式。CMS 回收器采纳了增量更新形式，G1 回收器采纳了原始快照形式。
漏标哪种解决方案最好？江湖风闻 G1 回收器的原始快照形式效率高，但没有确切的实践证实，且听且珍惜。