一. 简介

三色标记算法(tri-color-marking),是一种常见的垃圾收集的标记算法，属于可达性分析算法的一部分，常用于垃圾收集器CMS和G1。

三色标记算法将每个节点归纳分类为三类：白色节点、灰色节点和黑色节点。三色标记算法采用深度优先搜索的策略。
白色：可达性分析初始阶段，每个节点初始颜色都是白色(默认的)，表示该节点还没被GC扫描过。如果可达性分析结束之后，节点仍然是白色，这表示该节点没有被引用，正常情况下是可以被GC回收。
灰色：表示该节点至少还有一个引用节点未被扫描过，这样的节点会被标记成灰色节点。
黑色：GC扫描过的节点节点会被标记成黑色节点，黑色节点表示存活对象，GC是不能回收的。

二.  执行过程

三色标记算法的过程：
(1) 初始阶段，所有节点全部标记成白色；
(2) GC Roots直接引用的节点会被标记成灰色，然后将这些节点放到一个集合中。
(3) 从灰色节点集合中获取节点，将该节点直接引用的节点全部标记成灰色，将该节点标记成黑色。
(4) 重复(3)，直到灰色对象的集合为空
(5) 扫描结束后，如果有存在标记为白色的节点，就可认为该节点不可达，可以对该节点进行回收

三.  具体演示
(1) 初始标记阶段，所有节点均为白色，所以全部放入到白色节点集合中

(2)然后从GC开始进行扫描，依次A、E节点扫描到变成灰色，这样就会从白色节点移除  节点到灰色节点集合

(3)GC将继续沿着灰色节点继续扫描，接下来将扫描到B、F节点而变成灰色，而A 、E 节点则被标记成黑色，将A、E 节点从灰色节点集合移到黑色节点集合，将B、F从白色节点集合移到灰色节点集合。

(4) 继续执行(3) 直到灰色节点集合为null就不再往下继续执行了，这时候只会剩下两种颜色的节点，黑色和白色；

(5)最终在回收阶段，那些黑色节点依旧存活，而白色节点将会被清理。

四. 多标和漏标问题

问题一：多标问题
产生原因：并发标记阶段，用户与GC同时运行，假设现在GC标记到B节点，D、C也会标记成灰色，但是此时用户进程执行B.D = null,这样按道理来说，D是垃圾应该要被回收，
这种多标的问题会在重新标记阶段修复。并发清楚阶段，用户和GC同时运行，会产生新的对象但是会存在没有及时被GC清理，但是下次一GC就可以清理。

问题二：漏标问题
产生原因：用户执行B.D = null ,这样在扫描到B的时候，会扫描不到D，所以D依旧是白色，而此时用户执行A指向了D，此时GC扫描到B，将不会重新从A进行扫描，
所以最后D会被当成垃圾被回收。这就是漏标问题，漏标带来的影响是巨大的，严重的话可能直接导致用户程序出问题不可用。

五. 如何解决多标和漏标

接下来介绍下三色标记算法在CMS和G1中应用，是如何规避和解决这两类问题的
漏标这个问题的产生需要满足两个条件：
条件一：有且至少有一个黑色节点在自己被标记后，并发节点指向了一个白色节点，且该白色节点并未被其他引用。
条件二：所有灰色节点在扫描完之前删除了对该白色节点的引用

CMS垃圾收集器
解决方式：增量更新
当灰色节点与白色节点断开引用关系，并且在并发标记阶段黑色节点引用关联到该白色节点，这时候记录下黑色节点，在重新标记阶段（STW），会将B标记成灰色，这样就会该链路重新进行扫描。
缺点：多了一次扫描，会增加STW的时间

G1垃圾收集器
解决方式：原始快照
当灰色节点与白色节点断开引用，且有一个黑色节点与此白色节点增加了引用，这时会记录原始快照，在重新标记阶段的时候，会将白色节点标记成灰色节点，然后再从该节点继续扫描，本次GC不会清理。
优点：无需从头再扫描一次，减少了STW的时间
缺点：会产生浮动垃圾