Javaer面试必记系列！超高频八股三色打标方式

可访问性分析可以分为两个阶段

根节点枚举从根节点开始遍历对象图

如前所述，在可达性分析中，“根节点枚举”的第一阶段必须是STW。否则，如果分析过程中用户进程仍在运行，根节点集的对象引用关系可能会不断变化。，因此可达性分析结果的准确性显然无法保证；而第二阶段“从根节点遍历对象图”，如果不进行STW，会造成一些问题，因为第二阶段比较长，长期STW会影响性能，所以大佬们设计了一些解决方案，这样STW就可以在这个第二阶段消除，大大减少了时间。

上一篇已经介绍了第一阶段“根节点枚举”，本文将分析第二阶段“从根节点遍历对象图”~

老规矩，背诵版在文末

前言

事实上，相对于整个 Java 堆中的所有对象，GC Roots 仍然是一个非常小的数字，并且在各种优化技术（如）的加持下，它带来的停顿时间非常短且相对固定。也就是说，“根枚举”阶段的暂停时间不会随着堆大小的增加而增加。

当我们枚举完所有的 GC Root 后，我​​们就要进入第二阶段，继续遍历对象图。这一步也需要STW，暂停时间与Java堆容量成正比：堆越大，存储的对象越多，对象图结构越复杂，暂停时间越长自然标记更多对象，这是理所当然的

即“从根节点遍历对象图”阶段的暂停时间随着堆容量的增加而增加。

请注意，包含“标记”阶段（也称为可达性分析）是所有可跟踪垃圾收集算法的共同特征，如果此阶段与堆大小成比例地增加暂停时间，其影响将波及几乎所有垃圾收集器。如果能减少这部分的停顿时间，收益将是巨大的

为了减少STW时间甚至避免STW，我们首先要弄清楚为什么对象图遍历必须在可以保证一致性的快照上进行？

为了把这个问题解释清楚，大佬们介绍了工具Tri-color

需要注意的是，三色标记法只是辅助我们分析的工具，并不是垃圾收集器使用的具体算法！！！！！这不是减少 STW 时间或消除 STW 的方法。下面将介绍具体的解决方案。

在这里，三色符号可以帮助我们弄清楚如果用户线程和垃圾收集线程在可达性分析的第二阶段（即遍历对象图）同时运行会发生什么。

辅助分析的工具：三色符号

所谓三色标记法，就是将遍历对象图的过程中遇到的对象，按照“是否被访问过”的条件，标记成以下三种颜色：

因此，对象图遍历的过程实际上就是从灰色到黑色的过程，而灰色是黑白的分界线。

接下来，我们将使用三色标记的方法来分析在对象图遍历阶段如果用户线程和收集器同时工作会出现什么问题

问题一：漂浮垃圾

所谓浮动垃圾，就是因为垃圾回收和用户线程是并行的，所以对象实际上已经死掉了，没有其他人引用过它，却被垃圾回收器错误地标记为活对象

例如，a 引用 b，b 被扫描为可达，但用户线程随后执行 ab = null。这时候b已经是一个死垃圾对象了，但是因为黑色的对象不会被重新扫描，所以b在垃圾回收中还是被标记为黑色为一个活的对象，所以变成了浮动垃圾。如下所示：

当然，浮动垃圾并不是什么好事，但其实还可以忍受，因为它只会产生一点点浮动垃圾，逃过这个收集。不管怎样，还会有另一个垃圾回收，它会被标记为垃圾。清理干净

问题 2：对象消失

对象消失与漂浮垃圾完全相反。对象消失将原始幸存对象标记为误死。这是一个非常致命的后果，程序肯定会出错。下表显示了如何生成此类致命错误。

如上图所示，b -> c 的引用被切断，但同时用户线程从 a -> c 建立新的引用。由于已经遍历到b，所以不可能再回去遍历a（黑色物体不会被重新遍历）。scan)，然后遍历c，所以这个c其实是一个活的对象，但是因为没有被垃圾回收器扫描，所以被错误的标记为白色。

总结一下物体消失问题的两个条件：

插入了一个或多个从黑色对象到白色对象的新引用 删除了从灰色对象到白色对象的所有直接或间接引用

1994年理论上证明，当且仅当上述两个条件同时满足时，才会出现“物体消失”的问题，即本应为黑色的物体被错误地标记为白色。

一种不需要 STW 来遍历对象图的解决方案

如前所述，如果遍历对象图的过程不是STW，第一个浮动垃圾问题很容易处理，但是第二个对象消失问题就很难处理了。

但是遍历对象图的过程太长，设计JVM的大佬们不得不想出一些办法解决对象消失的问题，让STW（即用户线程和对象线程可以使用）在遍历对象图的过程中不需要同时工作）提高可达性分析的效率

以上总结了物体消失问题的两个条件，所以如果我们想解决并发扫描时物体消失的问题，只需要打破这两个条件中的任何一个即可。这导致了两种解决方案：

增量更新（ ）：增量更新破坏第一个条件。当黑色对象插入到指向白色对象的新引用关系（即上图中的a->c引用关系）时，新插入的引用被记录下来，并发扫描结束后，以记录的引用关系中的黑色物体（a）为根，再次扫描。这可以简化为，一旦黑色对象新插入了对白色对象的引用，它就会返回到灰色对象。原始快照（At The, SATB）：原始快照要销毁的第二个条件是，当灰色对象要删除对白色对象的引用关系（上图中的b -> c 引用关系）时，这将被删除。记录 的引用，并发扫描结束后，以记录的引用关系中的灰色对象（b）为根，再次扫描。这也可以简化为，无论是否删除引用关系，都将根据刚开始扫描时的对象图快照进行搜索。

在虚拟机中，增量更新和原始快照都有实际应用。CMS 基于增量更新进行并发标记，G1、 使用原始快照实现。

最后，把这个问题的记忆版本：

分类：

技术要点：

相关文章：