三色标记算法是CMS和G1在并发标记阶段都普遍采用的一种trace算法

首先，为什么要对对象进行标记？

因为tracing的过程中你必须对已经遍历过、正在遍历、还没有遍历到的对象进行区分，如果不进行区分的话，那你tracing有什么意义呢？每次某个垃圾回收线程重新获得了cpu的时间分片，回来之后发现自己根本啥都不记得了，遍历过哪些对象（是否是垃圾）已经全忘了，只能从头重新tracing... 这是一个非常严重的问题！！！

因此为了有效的对是否遍历过的对象的状态进行区分，便有了这个三色标记的算法，其思想很简单，那就是将我刚刚提到的对象的三种状态用不同的颜色进行标记，如果这个对象及对象的引用对象全部都tracing完了，那么这时候我就可以将对象标记为黑色，而如果对象本身已经遍历过了，但是对象所引用的那些孩子对象还没有遍历过，这时候我可以将对象标记为灰色，如果对象完全没有遍历过(对象本身 + 对象的引用孩子)，那么此时我就可以将对象标记为白色，这样一来，即使发生了线程切换，因为在对象头（hotspot）里面存在着对象的颜色标记，仍然看可以从上次遍历过的地方继续遍历，tracing就可以了

这个过程感觉有点类似于层序遍历算法BFS，每次我tracing一层，然后如果孩子不为空的话，将孩子都入队列，然后将本身标记为灰色，之后就不断的从队列中取孩子，如果孩子全部都遍历完了，那么这时候就可以将原来的父节点，置为黑色，以后便可以不再找这个黑色父节点的麻烦了！

 刚刚我解释的过程如果用一张图来表示的话，大概就是这样，三种颜色代表着tracing的三种 不同的状态！

但是我们知道，不论是CMS还是G1的垃圾回收的过程中，并发标记都是和用户线程一起进行的，这会带来什么问题呢？

你一边遍历tracing，但是发现对象间的引用关系还在不断的发生变化，这个过程是不是有点太扯了，让垃圾收集器很难做啊！（真的太难了T T）

具体说的话会带来哪些问题呢？ 一共分为两种case:

1.部分对象会存在遍历不到的问题

 如上图所示，B本来有个引用属性，是引用了对象D B.d = D，但是随着用户线程的继续进行，却B到D的这个引用关系却消失了， B.d = null 这时候势必会没有办法遍历到D这个对象了，我们仔细思考一下，对于D本身而言，没有任何GC Roots对象可以遍历到它，它本身就是一个垃圾对象，如果遍历过程遍历不到的话，它也会变成一个浮动垃圾，所以对于JVM来说的话从结果上看没什么问题，D对象变成了浮动垃圾，计算这次GC干不掉它，下次GC也一定可以把它给干掉。

（顺便插一句，这也就是为什么CMS不会真的等到堆空间快满了的时候再去执行垃圾清理的过程，因为随着用户线程不断变化引用关系，势必会有浮动垃圾产生，这时候如果用户线程不断产生大量的对象到堆，浮动垃圾本次又无法清理，会导致堆空间立马打满，JVM只能产生STW来清理堆空间，对于用户而言，就会看到程序假死）

2.产生last object remove的问题（很严重）

转变为 -> 

 也就是原来B到D的引用消失了，但是D并没有变成垃圾，而是被A重新引用上了这样一个过程

可是对于虚拟机而言，这个过程是存在问题的，因为A已经变成了黑色，从三色标记算法的约定角度出发，是不会再去重新遍历A的，而B会继续遍历，但是因为引用关系的改变，D也不会通过B再trace到了，这样的话，D对于通过三色标记算法的trace而言是一个垃圾对象，会被垃圾回收器进行回收！

可是D因为存在着A到它的引用关系，它并不是一个垃圾，如果此时垃圾回收器清理了D，那么导致的问题就是程序执行到A并取其d属性的时候就会发生空指针异常的问题！

上面就是三色标记算法，及其可能产生的两个问题的总结

接下来补充一个知识点，那就是CMS和G1在进行并发标记的过程中，是如何解决上述我提到的last object remove的问题的呢？

对于CMS而言，它的解决方案非常的直觉，那就是利用write barrier当发生了类似于A->D这种重新引用的情况时，如果发现主动引用的对象此时已经是黑色了，那么这时候我就会重新将其变为灰色，这样子就会重新发起对A对象的再trace的过程，理论上变不会漏掉其新增的属性对象了；

但是这个过程仍然存在bug，看图

 如上图中文字标记的过程所示，m1线程将属性1已经trace完了，然后m2的用户线程此时将新的白色对象D指向了已经标记完的属性1，然后m3线程此时将对象A标记为灰色

这个重新标记成灰色的过程其实没啥用不知道大家发现了没有，因为对于m1线程而言，其看A本身就是还是灰色的，2属性还没标记呢，然后m3线程因为发生了1属性的重新指向，所以再次将A的颜色变为灰色，

根本就没啥区别，当m1重新获得执行权限的时候，它会继续遍历2属性，当2属性也trace完了之后，就把A对象标记为黑色了，问题还是没有得到解决！

所以，最终CMS采用的终极解决方案那就是再重新标记的过程中，对于这种可能存在问题的对象，再执行一遍从头trace的过程，这个过程是需要STW的！

那G1是怎么解决这个问题的呢？

G1不会从变更和改动入手去解决这个问题，而是追根溯源，采用了一种叫做SATB的方式来解决，所谓的SATB，就是snatshop at the begining的缩写，看翻译我们大概也能够知道这种思路，那就是如果B对D的引用发生了变化的话，我们会将这条消失的引用关系链记录到一个队列里，当我们都trace完成之后，会从队列中将这部分消失的关系，重新取出来，在继续进行补充遍历过程，这样子便不会再发生刚刚说过的last object remove的问题啦！

PS:本文所用配图来自mashibing老师的ppt中，如果侵权立马删除，才疏学浅，知识理解能力有限，如有错误，欢迎批评指正!