最近和一个朋友聊天，他问我关于JVM的三色标记算法。我愣了一下，发现自己根本不知道！于是带着疑惑看了几天网上的资料，终于弄清楚三色标记算法是什么，有什么用，和CMS收集器、G1收集器的关系。今天就让舒哥带大家来一盘吧！RootReachableAlgorithm如果我们要进行垃圾回收，我们需要弄清楚哪些对象需要回收，哪些对象不需要回收。针对这个问题，其实业界有几种通用的解决方案。第一种是计数方式，即每个对象都有一个计数器，被引用时加一，移除引用时减一。但是这种方法比较麻烦，而且还存在循环依赖的问题，所以没有被广泛使用。第二种是root可达性算法，根据GCRoots扫描整个引用链，找到所有可达的对象，剩下的对象是不可达的垃圾对象。第二种算法，root-reachable算法，现在被广泛使用。那么如何实现根可达算法呢？最简单的实现是：从GCRoots节点开始，使用“mark-clear”算法来实现。本实施方案分为两个阶段，即：标记阶段和清算阶段。在标记阶段，它扫描从GCRoots节点开始的整个引用链，以找到所有可达的对象。在清理阶段，扫描整个引用链寻找不可达对象，然后清理垃圾对象。整个算法实现过程如下图所示。但是这种方法有一个很大的缺点：整个过程必须“StoptheWorld”。这导致整个应用程序不得不停止而不进行任何更改，这是非常不友好的。CMS收集器出现之前的所有收集器都是这样实现的，所以GC停顿时间比汽车的要长。三色标记算法为了解决上述“标记-清除”算法的问题，“三色标记算法”出现了！三色标注算法是指将所有物体分为白色、黑色和灰色三种类型。黑色表示从GCRoots开始，它引用的所有对象都被扫描过，灰色表示这个对象本身已经被扫描过，它引用的所有对象还没有被完全扫描过，白色表示还没有被扫描过的对象。但是仅仅将物体分成三种颜色是不够的。真正的关键在于：在实现根可达算法时，整个过程分为初始标记、并发标记、重标记、并发清除四个阶段。初始标记阶段是指对GCRoots直接引用的节点进行标记，并将其标记为灰色。这个阶段需要“停止世界”。并发标记阶段是指从灰色节点开始，扫描整个引用链，然后将其标记为黑色。此阶段不需要“停止世界”。重新标记阶段是指纠正并发标记阶段的错误。这个阶段需要“停止世界”。并发清除是指清除已经确定为垃圾的对象。在这个阶段没有必要“停止世界”。对比“四阶段拆分”和“一阶段拆分”的实现方式，我们可以看出：通过将最耗时的引用链扫描拆分为并发标记阶段，与用户线程并发执行，从而大大减少GC暂停时间。但是GC线程和用户线程并发执行会带来新的问题：对象引用关系可能发生变化，可能出现多标、漏标等问题。多标和漏标问题多标问题是指本应回收的对象被冗余标记为黑色幸存对象，导致垃圾对象没有被回收。出现多标准问题是因为在并发标记阶段，有可能删除了之前标记为alive的对象的引用，从而成为不可达对象。比如下图中，假设我们现在遍历到节点E，应用执行objD.fieldE=null;此时。然后在这一刻之后，对象E、F和G应该被回收。但是因为节点E已经是灰色的，所以节点E、F、G都会被标记为幸存黑状态，不会被回收。多标问题会导致内存产生浮动垃圾，好在下次GC时可以回收，所以问题不是很严重。遗漏标记问题是指一个应该被标记为alive的对象被遗漏了，被标记为black，导致垃圾对象被错误回收。例如下图中，假设我们现在已经遍历到了节点E，此时应用程序执行了如下代码。此时，由于E对象没有引用G对象，所以在扫描E对象时，G对象不会被标记为blackalive状态。但是由于用户线程的D对象引用了G对象，此时G对象应该是存活的，应该被标记为black。但是由于D对象已经扫描过，不会再扫描，所以漏掉了G对象。varG=objE.fieldG;objE.fieldG=null;//灰色E断开对白色G的引用objD.fieldG=G;//黑D引用白G标签缺失的问题很严重，会导致存活对象的回收，会严重影响程序的功能。那么我们的垃圾收集器是如何解决这个问题的呢？答案是：增加一个“备注”阶段。无论是在CMS收集器还是G1收集器，在并发标记阶段之后，都新增了一个“remarking”阶段，以修正“并发标记”阶段出现的问题。只是对于CMS收集器和G1收集器，其解决方案的原理是不同的。漏标解决方法上面提到了三色标记算法会出现漏标和多标的问题。不过，多标问题相对没有那么严重，其中缺标问题最为严重。经过分析，我们可以知道，漏标问题的发生必须满足以下两个充要条件：至少有一个黑色物体指向被标记后的白色物体。在引用扫描完成之前，所有灰色对象都会删除对白色对象的引用。只有满足以上两个条件，三色标注算法才会出现漏标问题。换句话说，如果我们破坏了任何一个条件，白色物体就不会被遗漏。这实际上产生了两种方法，即：增量更新和原始快照。CMS收集器使用的增量更新方案，G1使用原始快照方案。CMS解决方案CMS收集器采用增量更新方案，破坏了第一个条件：“至少有一个黑色对象在被标记后指向这个白色对象”。现在有了标记自己后的黑色物体，它又指向了白色物体。然后我会记录下这个黑色物体的引用，然后在后续的“remarking”阶段用这个黑色物体作为follower重新扫描它的引用。这样，黑色对象引用的白色对象就变成了灰色，从而活了起来。这种方法有一个缺点，就是会重新扫描新加入的黑色物体，会浪费更多的时间。不过这段时间相对于并发标记的整个链接的扫描来说还是微不足道的。毕竟真正改变引用的黑色对象比较少。G1方案G1收集器采用原有的快照方案，破坏了第二个条件：“所有灰色对象在自己的引用扫描完成之前删除对白色对象的引用”。现在灰色对象在扫描完成后删除了它对白色对象的引用，我可以在灰色对象被取消引用之前记录灰色对象引用的白色对象吗？然后在“remarking”阶段，白色对象作为根扫描它的引用，从而避免了标签丢失的问题。这样，原本遗漏的物体就会被重新扫描，变成灰色，从而变得有生命力。这种方法有一个缺点，就是会产生浮动垃圾。因为当用户线程解引用的时候，可能会被解引用，对应的对象真的要被回收了。这个时候，通过这种方式，我们会把本应该被回收的对象复活，从而产生漂浮垃圾。但是相对于本该存活下来的对象的回收，这段代码还是可以接受的。毕竟可以在下次GC的时候回收。关于CMS和G1两种处理方案哪个更好，很多人都说G1的方案更好。原因是感觉G1这样会产生一些浮动垃圾，但是节省了一些时间。但是我对比了一下，发现CMS和G1都需要为某些元素重新扫描引用链。从这一点来看，似乎差别不大。了解的朋友可以在评论区留言讨论讨论。总结阅读整篇文章后，我们尝试回答一些问题。什么是三色标注算法？三色标记算法是根可达算法的一种实现，其目的是找出所有可达的对象。为什么会有三色标记算法呢？由于传统的“标记-清除”算法效率太低，采用三色标记算法将对象分为白色、黑色和灰色，并将整个过程拆分为“初始标记、并发标记、重新标记、concurrentclear”4进程，从而减少GC停顿时间。三色标注算法有哪些缺陷？三色标注算法会产生多标签和漏标问题，其中漏标问题最为严重。标签丢失问题会导致本应存活的对象被回收，从而导致严重的程序问题。标签丢失的解决方法是什么？泄漏标签有两种解决方案：增量更新和原始快照。CMS收集器采用增量更新方式，G1收集器采用原始快照方式。哪种解决方案最适合丢失标签？江湖上有传言说G1采集器独创的快照方式效率高，但是没有确切的理论证明，听听珍惜。
