三色标记法

对象什么时候可以被垃圾器回收？

• 如果一个对象没有任何的引用指向它，那么这个对象就是垃圾，如果定位了垃圾，就有可能被垃圾回收器回收。
• 定位垃圾的方式有两种，第一个是引用计数法，第二个是可达性分析算法。
  • 引用计数法：对象被引用一次，对象头上引用次数就会加一，如果对象的引用次数为0，就代表这个对象可回收。
    • 但是引用计数法有可能会出现循环引用的问题，导致内存泄漏
  • 可达性分析算法：
    • 需要扫描堆中的对象，看是否能够沿着以 GC Root 对象为起点的引用链找到该对象，找不到，就说明可以回收

哪些对象可以作为 GC Root ?

• 虚拟机栈（栈帧中的本地变量表）中引用的对象
• 方法区中类静态属性引用的对象
• 方法区中常量引用的对象
• 本地方法栈中 JNI（即一般说的 Native 方法，Native 方法是系统提供的）引用的对象

可达性分析法

可达性分析法最简单的一种实现方案是：从GC Roots节点开始，使用「标记-清除」算法去实现。

这种实现方案分为两个阶段，分别是：标记阶段、清除阶段。

• 在标记阶段，采用可达性分析法，找到所有可达的对象。
• 在清除阶段，扫描整个引用链的不可达对象，然后将垃圾对象清除掉。

但这种方式有一个很大的缺点：整个过程必须「Stop the World」。这就导致整个应用程序必须停止，不能做任何改变，这是非常不友好的。

为了解决上面「标记-清除」算法的问题，于是就出现了「三色标记算法」

三色分析法

三色标记算法指的是将所有对象分为白色、黑色和灰色三种类型：

• 黑色表示该对象已经被扫描，且该对象的所有引用都已经扫描过；
• 灰色表示该对象已经被扫描，但它引用的对象还未被完全扫描；
• 白色表示该对象还未被扫描。

可达性分析法将整个过程拆分成了初始标记、并发标记、重新标记、并发清除四个阶段：

• 初始标记阶段，指的是将 GC Roots 直接引用的节点，标记为灰色，这个阶段需要「Stop the World」
• 并发标记阶段，指的是从灰色节点开始，去扫描整个引用链，然后将它们标记为黑色，这个阶段不需要「Stop the World」
• 重新标记阶段，指的是去校正并发标记阶段的错误，这个阶段需要「Stop the World」
• 并发清除，指的是将已经确定为垃圾的对象清除掉，这个阶段不需要「Stop the World」

对比一下「四阶段拆分」和「一段式」的实现方式，我们可以看出：通过将最耗时的引用链扫描剥离出来作为并发标记阶段，将其与用户线程并发执行，从而极大地降低了 GC 停顿时间。

但 GC 线程与用户线程并发执行，会带来新的问题：对象引用关系可能会发生变化，有可能发生多标和漏标问题。

多标问题

多标问题指的是原本应该回收的对象，被多余地标记为黑色存活对象，从而导致该垃圾对象没有被回收。

多标问题会导致内存产生浮动垃圾（在本轮应该被回收的垃圾没有被回收），这时产生的垃圾怎么办呢？答案是本次不处理，留给下次垃圾回收处理，因此问题还不算很严重。

假设已经遍历到E，此时应用执行 D.E = null ，此刻之后，对象E/F/G是应该被回收，但是E已经变为灰色，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即在本轮应该被回收的垃圾没有被回收。

漏标问题

漏标问题指的是原本应该被标记为存活的对象，被遗漏标记为白色，从而导致该垃圾对象被错误回收。

漏标问题就非常严重了，其会导致存活对象被回收，会严重影响程序功能。漏标问题要发生需要满足如下两个充要条件：

• 黑色对象指向了白色对象
• 灰色对象指向白色对象的引用消失

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

CMS 解决方案：增量更新

增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个黑色对象的引用记录下来，在后续「重新标记」阶段再以这个黑色对象为根，重新扫描一次。

可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。（跟踪黑指向白的增加）

G1 解决方案：原始快照

原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个灰色对象引用的白色对象记录下来，在后续「重新标记」阶段再以这个白色对象为根，对它的引用进行扫描。

可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索。（记录灰指向白的消失）

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

常见问题

三色标记算法是什么？

三色标记算法是可达性分析法的一种实现方案，其目的是为了找出所有可达对象。

为什么要有三色标记算法？

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

三色标记算法有什么缺陷？

三色标记算法会产生多标和漏标问题，其中漏标问题最严重。漏标问题会导致本该存活的对象被回收，从而导致严重的程序问题。

漏标有什么解决方案？

漏标有两种解决方案，分别是：增量更新和原始快照方式。CMS回收器采用了增量更新方式，G1回收器采用了原始快照方式。