CMS和G1改用三色标记法，可达性分析到底做错了什么？

CMS和G1改用三色标记法，可达性分析到底做错了什么？-HollisChuang's Blog

我们都知道， 当JVM判断对象不再存活的时候，便会在下一次GC时候将该对象回收掉，为堆腾出空间，而JVM判断对象存活的算法大家比较熟知的有两种，分别是引用计数法和可达性分析算法

• 引用计数法：给对象中添加一个引用计数器，每当有一个地方引用它，计数器就加 1；当引用失效，计数器就减 1；任何时候计数器为 0 的对象就是不可能再被使用的。这个方法实现简单，效率高，但是目前主流的虚拟机中并没有选择这个算法来管理内存，其最主要的原因是它很难解决对象之间相互循环引用的问题。

• 可达性分析算法： 这个算法的基本思想就是通过一系列的称为 “GC Roots” 的对象作为起点，从这些节点开始向下搜索，节点所走过的路径称为引用链，当一个对象到 GC Roots 没有任何引用链相连的话，则证明此对象是不可用的。

但是这两种算法其实并不完美，主要存在以下问题：

1、循环引用问题，如果两个对象互相引用，就形成了一个环形结构，如果采用引用计数法的话，那么这两个对象将用于无法被回收。

2、误标记的问题，在多线程环境下，如果一个线程正在遍历对象图，而另一个线程在同时修改对象图，就会导致遍历结果不准确。

3、STW时间长，可达性分析的整个过程都需要STW，以避免对象的状态发生改变，这就导致GC停顿时长很长，大大影响应用的整体性能。

为了解决上面这些问题，就引入了三色标记算法

什么是三色标记算法

三色标记法将对象分为三种状态：白色、灰色和黑色。

白色：该对象没有被标记过。

灰色：该对象已经被标记过了，但该对象的引用对象还没标记完。

黑色：该对象已经被标记过了，并且他的全部引用对象也都标记完了。

三色标记法的标记过程可以分为三个阶段：初始标记（Initial Marking）、并发标记（Concurrent Marking）和重新标记（Remark）。

这三个阶段看上去是不是很熟悉，这不就是CMS的四个阶段中的前三个么？没错，就是他们。

● 初始标记：遍历所有的根对象，将根对象和直接引用的对象标记为灰色。在这个阶段中，垃圾回收器只会扫描被直接或者间接引用的对象，而不会扫描整个堆。因此，初始标记阶段的时间比较短。（Stop The World）

● 并发标记：在这个过程中，垃圾回收器会从灰色对象开始遍历整个对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。（不需要STW）

● 重新标记：重新标记的主要作用是标记在并发标记阶段中被修改的对象以及未被遍历到的对象。这个过程中，垃圾回收器会从灰色对象重新开始遍历对象图，将被引用的对象标记为灰色，并将已经遍历过的对象标记为黑色。（Stop The World）

在重新标记阶段结束之后，垃圾回收器会执行清除操作，将未被标记为可达对象的对象进行回收，从而释放内存空间。这个过程中，垃圾回收器会将所有未被标记的对象标记为白色（White）。

以上三个标记阶段中，初始标记和重新标记是需要STW的，而并发标记是不需要STW的。其中最耗时的其实就是并发标记的这个阶段，因为这个阶段需要遍历整个对象树，而三色标记把这个阶段做到了和应用线程并发执行，大大降低了GC的停顿时长。

并发标记过程中，应用程序线程可能会修改对象图，因此垃圾回收器需要使用写屏障（Write Barrier）技术来保证并发标记的正确性。

写屏障是一种在对象引用被修改时，将其新的引用信息记录在特殊数据结构中的机制。在三色标记法中，写屏障技术被用于记录对象的标记状态，并且只对未被标记过的对象进行标记。

当应用程序线程修改了一个对象的引用时，写屏障会记录该对象的新标记状态。如果该对象未被标记过，那么它会被标记为灰色，以便在垃圾回收器的下一次遍历中进行标记。如果该对象已经被标记为可达对象，那么写屏障不会对该对象进行任何操作。

通过使用写屏障技术，三色标记法能够确保垃圾回收器能够准确地标记所有可达对象，并且避免了多次标记同一对象的情况。同时，写屏障技术也会带来一定的性能开销，因为每次引用被修改时都需要记录新的标记状态。为了减少性能开销，垃圾回收器通常会使用基于插入式写屏障的优化技术，来降低写屏障的开销。

多标的问题

所谓多标，其实就是这个对象原本应该被回收掉的白色对象，但是被错误的标记成了黑色的存活对象。从而导致这个对象没有被GC回收掉。

这个一般发生在并发标记过程中，该对象还是有引用的，但是在过程中，应用程序执行过程中把他的引用关系删除了，导致他变成了一个垃圾对象。

多标的话，会产生浮动垃圾，这个问题一般都不太需要解决，因为这种垃圾一般都不会太多，另外在下一次GC的时候也都能被回收掉。

漏标的问题

所谓漏标，和多标刚好相反，就是说一个对象本来应该是黑色存活对象，但是没有被正确的标记上，导致被错误的垃圾回收掉了。

这种情况一旦发生是很危险的，一个正常使用的对象被垃圾回收掉了，这对系统来说是灾难性的问题，那么如何解决呢？

具体的解决方式，在CSM和G1中也不太一样。CMS采用的是增量更新方案，G1则采用的是原始快照的方案。

漏标的问题想要发生，需要同时满足两个充要条件：

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

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

那么，增量更新方案就是破坏了第一个条件，而原始快照方案就是破坏了第二个条件。

“至少有一个黑色对象在自己被标记之后指向了这个白色对象”，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：

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

这种方式有个缺点，就是会重新扫描新增的这部分黑色对象，会浪费多一些时间。但是其实这个浪费还好，因为本来这种漏标的情况就并不是特别常见，所以这部分需要重新扫描的黑色对象也并不多。

“所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用”，这个条件如果被破坏了，那么就不会出现漏标的问题。所以：

如果灰色对象在扫描完成前删除了对白色对象的引用，那么我们就在灰色对象取消引用之前，先将灰色对象引用的白色对象记录下来。

在后续「重新标记」阶段再以这些白色对象为根，对它的引用进行扫描，从而避免了漏标的问题。通过这种方式，原本漏标的对象就会被重新扫描变成灰色，从而变为存活状态。

但是这种放回寺可能会把本来真的要取消引用的对象给错误的复活了，从而产生浮动垃圾。但是就像前面说的，多标的问题是可以忽略的。

为了解决传统的引用计数法和可达性分析算法存在的循环引用问题、误标记问题以及STW时间长的问题，才CMS和G1中引入了三色标记算法，其实就是在标记过程中将对象的状态划分为白色、灰色、和黑色三种状态。

同时把一次标记拆分成初始标记、并发标记以及重新标记三个阶段。并且只有初始标记和重新标记是STW的，而耗时最长的重新标记不需要STW，可以和应用线程并行。

但是因为并发标记过程中是不需要STW的，这就需要采用写屏障的方式避免并发。但是还是会存在漏标的多标的问题。

多标的问题我们一般可以忽略，因为下次GC还是可以回收掉的。但是漏标的问题还是要解决的，避免对象使用过程中被回收了，为了解决这个问题，CMS和G1分别采用了增量更新和原始快照两种方案来实现的，都能帮助我们解决漏标的问题。

(全文完) 扫描二维码，关注作者微信公众号