jvm深度学习（11）：GC并发标记之三色标记及漏标问题

三色标记

概念叙述

        在三色标记法之前有一个算法叫Mark-And-Sweep（标记清除）。这个算法会设置一个标志位来记录对象是否被使用。最开始所有的标记位都是 0，如果 发现对象是可达的就会置为 1，一步步下去就会呈现一个类似树状的结果。等标记的步骤完成后，会将未被标记的对象统一清理，再次把所有的标记位设置成 0方便下次清理。

        这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，不能异步进行 GC 操作。因为在不同阶段标记清扫法的标志位 0 和 1 有不同的含义， 那么新增的对象无论标记为什么都有可能意外删除这个对象。对实时性要求高的系统来说，这种需要长时间挂起的标记清扫法是不可接受的。所以就需 要一个算法来解决 GC 运行时程序长时间挂起的问题，那就三色标记法。
三色标记最大的好处是可以异步执行，从而可以以中断时间极少的代价或者完全没有中断来进行整个 GC。

        三色标记法很简单。首先将对象用三种颜色表示，分别是白色、灰色和黑色。

        黑色：根对象，或者该对象与它的子对象都被扫描过。
        灰色：对本身被扫描，但是还没扫描完该对象的子对象。
        白色：未被扫描对象，如果扫描完所有对象之后，最终为白色的为不可达对象，既垃圾对象。

 

三色标记的问题

1.   线程1和2开始三色标记，

2.   此时B与C之间引用关系断开，添加A与C的引用关系

3.  完成标记

问题：我们发现C虽然有引用关系但是并没有标记，这就是漏标问题

 

GC 并发情况下的漏标问题解决方案

 

CMS 中的解决方案

使用Incremental Update 算法

当一个白色对象被一个黑色对象引用，将黑色对象重新标记为灰色，让垃圾回收器重新扫描。

注意：圈红的位置，触发1线程重新扫描的是A增加一个引用。

小结：Incremental Update关注的是引用关系的增加，当发现有可达的引用增加，便开始重新标记。

 

G1 中的解决方案

使用SATB算法(snapshot-at-the-beginning  快照)

        刚开始做一个快照，当 B 和 C 引用消失的时候要把这个引用推到 GC 的堆栈，保证 C 还能被 GC 扫描到，最重要的是要把这个引用推到 GC 的堆栈，是灰色对象指向白色的引用，如果一旦某一个引用消失掉了，我会把它放到栈（GC 方法运行时数据也是来自栈中），我其实还是能找到它的，我下回直接扫描他 就行了，那样白色就不会漏标。
对应 G1 的垃圾回收过程中的：

最终标记( Final Marking)：对用户线程做另一个短暂的暂停，用于处理并发阶段结后仍遗留下来的最后那少量的 SATB 记录(漏标对象)。

注意：圈红的位置，触发1线程重新扫描的是B少了一个引用。即使用SATB关注的是引用关系的删除。 

小结：SATB通过快照记录引用关系，一旦发现有引用删除，通过查看快照记录的引用关系，重新标记

 

Incremental Update算法和SATB算法对比

        SATB 算法是关注引用的删除。（B->C 的引用），而Incremental Update 算法关注引用的增加。（A->C 的引用）。
        G1 如果使用 Incremental Update 算法，因为变成灰色的成员还要重新扫，重新再来一遍，效率太低了。 所以 G1 在处理并发标记的过程比 CMS 效率要高，这个主要是解决漏标的算法决定的。