前言
关于垃圾回收算法，基本就是那么几种：标记-清除、标记-复制、标记-整理。在此基础上可以增加分代（新生代/老年代），每代采取不同的回收算法，以提高整体的分配和回收效率。
无论使用哪种算法，标记总是必要的一步。这是理算当然的，你不先找到垃圾，怎么进行回收？
垃圾回收器的工作流程大体如下：
- 标记出哪些对象是存活的，哪些是垃圾（可回收）；
- 进行回收（清除/复制/整理），如果有移动过对象（复制/整理），还需要更新引用。
本文着重来看下标记的部分。
概述
在 CMS 垃圾收集器中提到了，在 CMS 的并发清理阶段才产生的垃圾对象，会被当做浮动垃圾，留到下一次 GC 再清理。其实在并发标记阶段，由于用户线程在并发运行，也可能会导致引用关系发生改变，导致标记结果不准确，从而引发更加严重的问题，这些发生变更的数据会在重新标记阶段被处理，那么会出现什么问题？又是如何处理的呢？
CMS 算法的基础是通过可达性分析找到存活的对象，然后给存活的对象打个标记，最终在清理的时候，如果一个对象没有任何标记，就表示这个对象不可达，需要被清理，标记算法就是使用的三色标记。并发标记阶段是从 GC Root 直接关联的对象开始枚举的过程。
对于三色标记算法而言，对象会根据是否被访问过（也就是是否在可达性分析过程中被检查过）被分为三个颜色：白色、灰色和黑色：
- 白色：这个对象还没有被访问过，在初始阶段，所有对象都是白色，所有都枚举完仍是白色的对象将会被当做垃圾对象被清理。
- 灰色：这个对象已经被访问过，但是这个对象所直接引用的对象中，至少还有一个没有被访问到，表示这个对象正在枚举中。
- 黑色：对象和它所直接引用的所有对象都被访问过。这里只要访问过就行，若 A 只引用了 B，B 引用了 C、D，那么只要 A 和 B 都被访问过，A 就是黑色，若 B 所引用的 C 或 D 还没有被访问到，此时 B 就是灰色。
根据这些定义，我们可以得出：
- 在可达性分析的初始阶段，所有对象都是白色，一旦访问了这个对象，那么就变成灰色，一旦这个对象所有直接引用的对象都访问过（或者没有引用其它对象），那么就变成黑色
- 初始标记之后，GC Root 节点变为黑色（GC Root 不会是垃圾），GC Root 直接引用的对象变为灰色
- 正常情况下，一个对象如果是黑色，那么其直接引用的对象要么是黑色，要么是灰色，不可能是白色（如果出现了黑色对象直接引用白色对象的情况，就说明漏标了，就会导致对象误删，后面会介绍如何解决），这个特性也可以说是三色标记算法正确性保障的前提条件。
标记过程
- 初始时，所有对象都在【白色集合】中；
- 将 GC Roots 直接引用到的对象挪到【灰色集合】中
- 从灰色集合中获取对象：
- 将本对象引用到的其他对象全部挪到【灰色集合】中
- 将本对象挪到【黑色集合】里面
- 重复步骤 3，直至【灰色集合】为空时结束
- 结束后，仍在【白色集合】的对象即为 GC Roots 不可达，可以进行回收
并发标记问题
垃圾变成了非垃圾（多标）
浮动垃圾：本应该被标记为白色的对象，没有被标记，造成该对象本次 GC 不会被回收。
标记的下一步操作是取出 C 对象进行分析，但是这个时候 GC 线程的时间片用完了，操作系统调度用户线程来运行，而用户线程先执行了这个操作：A.c = null，已完成标记的 A 与 C 断开联系。这时候如果 GC 线程获得时间片继续运行，继续标记 C、D 最后为黑色。**最后发现问题：C、D 其实已经从 GC Root 不可达，但是还是完成了标记，不会被 GC 回收。**这种也可以当作浮动垃圾。可以等下次 GC 处理。
非垃圾变成了垃圾（漏标）
漏标只有同时满足以下两个条件时才会发生：
条件一：灰色对象断开了白色对象的引用；即灰色对象原来成员变量的引用发生了变化。
条件二：黑色对象重新引用了该白色对象；即黑色对象成员变量增加了新的引用。
场景重现
标记的下一步操作是从队列中取出 B 对象进行分析，但是这个时候 GC 线程的时间片用完了，操作系统调度用户线程来运行，而用户线程先执行了这个操作：A.f = F，已完成标记的 A 与 F 建立联系。接着执行：B.f = null，去掉 B 与 F 之间的联系。这时候如果 GC 线程获得时间片继续运行，发现 B 对象没有直接引用，那么将 B 对象变为黑色。然后继续标记 C、D，发现 C、D 没有直接引用，那么 C、D 变成黑色。最后发现问题：F 其实被 A 引用，但是 F 仍然漏标，这直接影响了程序的正确性。
增量更新和原始快照(SATB)
上面一共出现了两个问题，从结果上来看，可以这样描述：
- 一个本应该是垃圾的对象被视为了非垃圾
- 一个本应该不是垃圾的对象被视为了垃圾
对于第一个问题，我们前文也提到了，即使不去处理它也无所谓，大不了等到下次 GC 再清理。最重要的是第二个问题，如果误清理了正在被使用的对象，那就是实打实的 BUG 了。那么如何解决这个问题呢？
出现漏标这个问题的主要原因是，一个对象从被 B 引用，变更为了被 A 引用。那么对于 A 来说就是多了一个直接引用，对于 B 来说就是少了一个直接引用。我们可以从这两个方面入手来解决这个问题，对应了也有两个方案，分别是增量更新（Incremental Update）和原始快照（SATB，Snapshot At The Beginning）。
读写屏障
在这讲述解决方案之前，要描述两个名词：读屏障和写屏障。注意，这里的屏障和并发编程中的屏障是两码事儿。这里的屏障很简单，可以理解成就是在读写操作前后插入一段代码，用于记录一些信息、保存某些数据等，概念类似于 AOP。
增量更新
增量更新是站在新增引用的对象（也就是例子中的 A 对象）的角度来解决问题。所谓增量更新，就是在赋值操作之前添加一个写屏障，在写屏障中记录新增的引用。比如，用户线程要执行：A.f = F；那么在写屏障中将新增的这个引用关系记录下来。标准的描述就是，当黑色对象新增一个白色对象的引用时，就通过写屏障将这个引用关系记录下来。然后在重新标记阶段，再以这些引用关系中的黑色对象为根，再扫描一次，以此保证不会漏标。
在我们这个例子中，在并发标记阶段，A 是一个黑色对象，F 是一个白色对象，A 引用了 F，这个引用关系会被记录下来，然后通过这个记录在重新标记阶段再从 A 对象开始枚举一次，保证如果 A 还是保持着F的引用，那么 F 会被正确标记；如果 A 到 F 的引用在并发标记阶段又断开了，此次枚举也无法访问到它，活该被清除。
要实现也很简单，在重新标记阶段直接把 A 对象（和其它有相同情况发生的对象）变为灰色，放入队列中，再来一次枚举过程。要注意，在重新标记阶段如果用户线程还是继续执行，那么这个 GC 永远可能也做不完了，所以重新标记需要 GC 中断，但是这个时间消耗不会太夸张。如果实在重新标记阶段耗时过长，那么可以尝试在重新标记之前做一次 Minor GC。
原始快照SATB
**原始快照是站在减少引用的对象（也就是例子中的 B 对象）的角度来解决问题。**所谓原始快照，简单的讲，就是在赋值操作（这里是置空）执行之前添加一个写屏障，在写屏障中记录被置空的对象引用。比如，用户线程要执行：B.f=null；那么在写屏障中，首先会把 B.f 记录下来，然后再进行置空操作。记录下来的这个对象就可以称为原始快照。
那么记录下来之后呢？很简单，之后直接把它变为黑色。意思就是默认认为它不是垃圾，不需要将其清理。当然，这样处理有两种情况，一种情况是，F 的确不是垃圾，直到清理的那一刻，都仍然有至少一个引用链能访问到它，这没有什么问题；另一种情况就是 F 又变成了垃圾。在上述的例子中，就是 A 到 F 的引用链也断了，或者直接 A 都成垃圾了，那 F 对象就成了浮动垃圾。对于浮动垃圾，前面不止一次就提到了，直接不用理会，如果到下一次 GC 时它仍然是垃圾，自然会被清理掉。
方案选择
从增量更新和原始快照的实现（理论上）就可以发现，原始快照相比于增量更新来说效率会更高，因为不用在重新标记阶段再去做枚举遍历，但是也就可能会导致有更多的浮动垃圾。G1 使用的就是原始快照，CMS 使用的是增量更新。
既然原始快照可能会有更严重的浮动垃圾问题，那么为什么不使用增量更新呢？原因可能很简单，就是因为简单。想象一下，G1 虽然也是基于年轻代和老年代的分代收集算法，但是年轻代和老年代被弱化为了逻辑上，其所管理的内存被划分为了很多 region，对象跨代引用带来的问题在 G1 中要比传统的分代收集器更加突出，虽然有 Remember Set 方案缓解，但是相对来说在重新标记阶段进行再次遍历枚举的代价会大很多。最重要的是，重新标记（最终标记）阶段是会 GC 中断的，如果这个阶段花费太多的时间去做可达性分析，那么就违背了 G1 低延时的理念。
总结
这里有一个需要注意的点，重新标记阶段会 GC 中断，以此保证标记结果的正确性（主要是漏标）。到现在你可能理解了，垃圾收集器中所描述的：并发清理阶段产生的垃圾会被当做浮动垃圾，只能留待下一次GC被清理。那么实际上是怎么回事呢？其实就很简单了，只要在并发清理阶段产生的对象，直接就认为是黑色对象，全部都不是垃圾。如果一个对象最终成了垃圾，那它就是浮动垃圾，如果没成垃圾，那么标记为黑色也没有什么问题。因为到了清理阶段，标记工作已经完成，没有办法再找到合适的方式去处理这个问题，不然一次 GC 可能永远也结束不了。
话说回来，对于上面漏标的情况，你可能还有一个疑问：在并发标记过程中，除了引用关系发生变更的情况，如果用户线程直接创建了一个新对象，这个对象默认是白色，又直接和黑色对象关联，那又该当如何呢？也就是白色对象可能是从其他对象的引用链上”转移“过来的，也可能就是一个新对象。其实可以想象的到，对于新对象加入到黑色节点，我们无法使用原始快照，但是可以使用增量更新，或者直接简单处理，和并发清理阶段一样：在这期间创建的新对象都认为不是垃圾（比如标记为黑色），如果成了垃圾，那就是浮动垃圾，还是留待下一次 GC 处理。总之，标记的总体原则就是：“另可放过，不可杀错”。
关于黑白灰三个颜色，是一个抽象的概念，虽然使用可达性分析的垃圾收集器基本都采取三色标记的思想，但在实现上可能也各不相同，像如何标识颜色、灰色队列如何实现等等。
