三色标记法是一种垃圾回收法，它可以让JVM不发生或仅短时间发生STW(Stop The World)，从而达到清除JVM内存垃圾的目的。JVM中的CMS、G1垃圾回收器所使用垃圾回收算法即为三色标记法。

三色标记算法思想

三色标记法将对象的颜色分为了黑、灰、白，三种颜色。

白色：该对象没有被标记过。（对象垃圾）

灰色：该对象已经被标记过了，但该对象下的属性没有全被标记完。（GC需要从此对象中去寻找垃圾）

黑色：该对象已经被标记过了，且该对象下的属性也全部都被标记过了。（程序所需要的对象）

算法流程

从我们main方法的根对象（JVM中称为GC Root）开始沿着他们的对象向下查找，用黑灰白的规则，标记出所有跟GC Root相连接的对象,扫描一遍结束后，一般需要进行一次短暂的STW(Stop The World)，再次进行扫描，此时因为黑色对象的属性都也已经被标记过了，所以只需找出灰色对象并顺着继续往下标记（且因为大部分的标记工作已经在第一次并发的时候发生了，所以灰色对象数量会很少，标记时间也会短很多）, 此时程序继续执行，GC线程扫描所有的内存，找出扫描之后依旧被标记为白色的对象（垃圾）,清除。

具体流程:

首先创建三个集合：白、灰、黑。

将所有对象放入白色集合中。

然后从根节点开始遍历所有对象（注意这里并不递归遍历），把遍历到的对象从白色集合放入灰色集合。

之后遍历灰色集合，将灰色对象引用的对象从白色集合放入灰色集合，之后将此灰色对象放入黑色集合

重复 4 直到灰色中无任何对象

通过write-barrier检测对象有变化，重复以上操作

收集所有白色对象（垃圾）

三色标记算法缺陷

不知道你是否还记得我们前言说的，所有垃圾收集器在根节点枚举这一步骤时都是必须暂停用户线程的，产生 STW，这对实时性要求高的系统来说，这种需要长时间挂起用户线程是不可接受的。想要解决或者降低用户线程的停顿的问题，我们才引入了三色标记算法。

三色标记算法也存在缺陷，在并发标记阶段的时候，因为用户线程与 GC 线程同时运行，有可能会产生多标或者漏标。

多标

假设已经遍历到 E（变为灰色了），此时应用执行了 objD.fieldE = null (D > E 的引用断开) 。

D > E 的引用断开之后，E、F、G 三个对象不可达，应该要被回收的。然而因为 E 已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮 GC 不会回收这部分内存。

这部分本应该回收但是没有回收到的内存，被称之为浮动垃圾。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。

另外，针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能会变为垃圾，这也算是浮动垃圾的一部分。

漏标

假设 GC 线程已经遍历到 E（变为灰色了），此时应用线程先执行了：

var G = objE.fieldG;

objE.fieldG = null; // 灰色E 断开引用 白色G

objD.fieldG = G; //

此时切回到 GC 线程，因为 E 已经没有对 G 的引用了，所以不会将 G 置为灰色；尽管因为 D 重新引用了 G，但因为 D 已经是黑色了，不会再重新做遍历处理。

最终导致的结果是：G 会一直是白色，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性，是不可接受的。

不难分析，漏标只有同时满足以下两个条件时才会发生：

一个或者多个黑色对象重新引用了白色对象；即黑色对象成员变量增加了新的引用。

灰色对象断开了白色对象的引用（直接或间接的引用）；即灰色对象原来成员变量的引用发生了变化。

如下代码：

var G = objE.fieldG; // 1.读

objE.fieldG = null; // 2.写

objD.fieldG = G;

我们只需在上面三个步骤中任意一个中，将对象 G 记录起来，然后作为灰色对象再进行遍历即可。比如放到一个特定的集合，等初始的 GC Roots 遍历完（并发标记），该集合的对象遍历即可（重新标记）。

重新标记是需要 STW 的，因为应用程序一直在跑的话，该集合可能会一直增加新的对象，导致永远都跑不完。当然，并发标记期间也可以将该集合中的大部分先跑了，从而缩短重新标记 STW 的时间，这个是优化问题了。看到了没？三色标记算法也并不能完全解决 STW 的问题，只能尽可能缩短 STW 的时间，尽可能达到停顿时间最少。

漏标解决方案

正如前面所说，三色标记算法会造成漏标和多标问题。但多标问题相对不是那么严重，而漏标问题才是最严重的。我们经过分析可以知道，漏标问题要发生需要满足如下两个充要条件：

有至少一个黑色对象在自己被标记之后指向了这个白色对象

所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用

只有当上面两个条件都满足，三色标记算法才会发生漏标的问题。换言之，如果我们破坏任何一个条件，这个白色对象就不会被漏标。这其实就产生了两种方式，分别是：增量更新、原始快照。CMS 回收器使用的增量更新方案，G1 采用的是原始快照方案。

CMS 解决方案

CMS 回收器采用的是增量更新方案，即破坏第一个条件：「有至少一个黑色对象在自己被标记之后指向了这个白色对象」。

既然有黑色对象在自己标记后，又重新指向了白色对象。那么我就把这个黑色对象的引用记录下来，在后续「重新标记」阶段再以这个黑色对象为跟，对其引用进行重新扫描。通过这种方式，被黑色对象引用的白色对象就会变成灰色，从而变为存活状态。

这种方式有个缺点，就是会重新扫描新增的这部分黑色对象，会浪费多一些时间。但是这段时间相对于并发标记整个链路的扫描，还是小巫见大巫，毕竟真正发生引用变化的黑色对象是比较少的。

但是把黑色对象修改为灰色的这个操作如何实现的呢，这肯定不是由GC垃圾收集线程完成的，因为它是不会在并发标记阶段重新扫描已经扫描过的对象的。

写屏障

实际上这个操作是通过写屏障实现，写屏障就是在指针赋值操作前后插入一段额外的逻辑。

增量更新是在黑色对象建立到白对象引用的之后，把该黑色对象标记为黑色的，因此自然是把写屏障插入到指针赋值操作的后面。

然后在重新标记阶段，GC就可以从该灰色对象开始，重新进行扫描。

G1 解决方案

G1 回收器采用的是原始快照的方案，即破坏第二个条件：「所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用」。

把删除引用的对象保存起来变成灰色，标记为存活，造成了浮动垃圾，下一次回收的时候再回收。

个人理解是把原本应该删的白色对象变成灰色，造成浮动垃圾，重标记节点会对其子节点扫描删除他的垃圾，而它本身等到下一轮垃圾回收通过可达性分析不可达删除。

既然灰色对象在扫描完成后删除了对白色对象的引用，那么我是否能在灰色对象取消引用之前，先将灰色对象引用的白色对象记录下来。随后在「重新标记」阶段再以白色对象为根，对它的引用进行扫描，从而避免了漏标的问题。通过这种方式，原本漏标的对象就会被重新扫描变成灰色，从而变为存活状态。

这种方式有个缺点，就是会产生浮动垃圾。 因为当用户线程取消引用的时候，有可能是真的取消引用，对应的对象是真的要回收掉的。这时候我们通过这种方式，就会把本该回收的对象又复活了，从而导致出现浮动垃圾。但相对于本该存活的对象被回收，这个代码还是可以接受的，毕竟在下次 GC 的时候就可以回收了。

对于 CMS 和 G1 这两种处理方案哪种更好，很多资料说的是 G1 这种解决方案更好。 原因是其觉得 G1 这种方式产生了一些浮动垃圾，但节省了一些时间。

G1垃圾收集器解决漏标的办法则是原始快照，原始快照是在灰色对象断开对白色对象的引用时，把被删除的灰色对象到白色对象的引用记录下来，把白色对象修改为灰色。

这样GC就可在最终标记阶段通过该快照引用继续扫描到该白色对象。

由于是在灰色对象断开对白色对象的引用前，把该引用作为快照保存下来，因此是在指针赋值操作前插入的写屏障。

为什么G1使用原始快照而不用增量更新。

我个人觉得，G1之所有使用的是原始快照而不是增量更新，是因为原始快照比起增量更新来说，在最终标记阶段需要扫描的对象更少。

我们根据上面的例子，看看增量更新需要重新扫描的对象：

然后再看看使用原始快照，需要扫描多少个对象：

可以看到，使用增量更新，需要扫描三个对象。而使用原始快照，只需要重新扫描1个对象。

这个例子只有少量几个对象，如果在真实场景下，对象的数量会非常非常多，这样性能差距就很明显了。并且G1它是面向大内存的垃圾收集器，使用原始快照就会比起使用增量更新来说少扫描很多的对象。

  1. 由于程序运行时引用增加的操作比引用断开更为频繁，因此在并发标记期间增量更新的消耗比原始快照大。同时增量更新重新标记阶段会连同新加入对象一起遍历

  2. 对于对象的消失的问题，原始快照和增量更新都能解决。

  3. 原始快照的浮动垃圾比增量更新多。

  4. 为什么要有三色标记算法？ 因为传统的「标记 - 清除」算法效率太低，于是采用三色标记算法通过将对象分成白色、黑色、灰色，以及将整个过程拆分成「初始标记、并发标记、重新标记、并发清除」4 个过程，从而降低 GC 停顿时间。