三色标记及漏标问题处理

在上一篇中讲到了CMS、G1都用到了并发标记，那么并发标记的具体是如何实现的呢？主流的垃圾回收器并发标记是核心的实现，我们有必要进行深入的研究。

并发标记与三色标记

并发标记底层用到了三色标记的算法，为什么会用到三色标记呢？什么是三色标记呢?

为什么会有三色标记？

在前几篇的文章中，介绍的垃圾回收算法有个标记清除算法，通过1和0进行标记对象是不是被使用，工作原理是这样的：最开始所有的标记位都是0，如果发现对象是可达的就会置为1，然后一步一步执行下去就会呈现类似树形的结果，等到标记步骤完成后，将未被标记的对象统一清理，然后再把所有的标记位重置为0方便下次清理。为什么并发标记没有用到标记清除的算法呢？主要是因为标记清除算法在GC执行期间，必须要把整个程序暂停，不能异步进行GC操作。在不同阶段标记清除法的标志位0和1有不同的含义，那么新增的对象无论标记什么都有可能被意外的删除，例如在并发标记的过程中用户线程产生了新的对象那么是无法被标记的，而新的对象默认标记为0，所以有可能会意外的当做垃圾清除掉，这显然是不可接受的，所以需要一个算法来解决GC运行时程序长时间挂起的问题，就有了三色标记法。

什么是三色标记

三色标记：通过三种颜色表示，分别是白色、灰色、黑色

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

三色标记可以异步执行，标记和业务线程并发执行。三色标记看似完美的解决了并发标记的问题，但是存在漏标的问题。如下图所示：在并发标记的过程中，线程1已经扫描完成了，此时业务线程执行了A.c=C B.c=null

那么就变成了如下图：此时线程1和线程2完成了所有标记，对象C会被错误的回收掉。这就是漏标的问题，主要发生在并发标记和业务线程同时执行，业务线程改变了对象的指向，而线程已经完成了所有标记，那么此时无法在进行标记。

那么如何解决漏标问题呢？

漏标的解决方案

CMS的解决方案

Incremental Update 算法：当一个白色对象被一个黑色对象引用，将黑色对象重新标记为灰色，让垃圾回收器重新扫描(注意这里是从根节点开始扫描而不是从A)。

将A变成灰色，则垃圾回收器会重新扫描。然后A就会变成黑色，C就变成灰色 -> 黑色。

G1的解决方案

SATB （snapshot-at-the-beginning）刚开始做一个快照，当B和C消失的时候要把这个引用推到GC的堆栈，保证C还能被GC扫描到，最重要的是要把这个引用推到GC的堆栈，是灰色对象指向白色的引用，如果一旦某一引用消失掉，会把它放到栈(GC方法运行时数据也是来自栈中)，其实还是能找到它，下回直接扫描就可以了。对应着G1垃圾回收过程的最终标记，对用户线程做一个短暂的暂停，用于处理并发阶段后，扔遗留下来的少量的SATB记录(漏标对象)。例如：刚开始GC的时候，会做一个快照，可以理解为拍了一张照片，这张照片如下：取名叫做S。

这时候业务线程执行操作A.c=C B.c=null，B和C的连线消失了,就会把上述的快照S，推到GC堆栈中去。那么就意味着之前的关系/引用还是存在的，SATB关注引用的删除。两张快照信息对比发现了不一致，专门针对变化的地方进行处理就可以了，就会从A开始再扫描一次。

CMS和G1的两种解决方案的对比：

SATB 算法关注引用的删除 (b->c的引用)，从A开始扫描。
Incremental Update 算法关注引用的增加 (A->C的引用)，从根重新扫描。
G1在处理并发标记的过程比CMS效率更高，主要就是解决漏标算法决定的。

G1的技术细节：跨代引用及解决方案

在上一篇文章中讲到G1的内存区域是不固定的。G1将堆区化整为零，在Region区跨代引用一般是老年代引用新生代的对象。由于新生代的垃圾收集通常很频繁，如果老年代对象引用了新生代的对象，那么回收新生代的话，需要跟踪从老年代到新生代的所有引用，所以要避免每次YGC扫描整个老年代，减少开销。那么如何解决这个问题呢？ G1通过Rset和CardTable的方式进行避免每次YGC扫描整个老年代。

RSet 记忆集记录了其他Region中的对象到本Region的引用。存储跨代引用但是跨代引用越来越多可能达到占20%堆内存，这也是为什么在堆内存小的情况下不推荐使用G1垃圾回收器。RSet的价值在于是的垃圾收集器不需要扫描整个堆，找到谁引用了当前分区的对象，只需要扫描RSet即可。Rset本身是一个Hash表，如果是在G1的话，则是在一个Region区里面
CardTable 卡表记录跨代引用在哪里(老年代扫一遍没有意义)。由于做新生代GC时，需要扫描整个老年代，效率非常低，所以JVM设计了CardTable，

我们只需要理解其设计思想即可，至于底层是如何实现的就不再探究的范围之内了。

G1处理跨代引用的细节，其实在CMS中也有类似的处理方式，比如CardTable也需要记录一个RSet来记录，在G1中每一个Region都需要一个RSet的内存区域，导致有G1的RSet可能会占据整个堆容量的20%乃至更多，但是CMS只需要一份，所以就内存占用来说，G1占用的内存需求更大，虽然G1的优点很多，但是不推荐在堆空间比较小的情况下使用G1，尤其小于6个G的情况下。

安全点和安全区域

安全点

什么是安全点呢？如下图所示，其实安全点就是在执行GC线程的时候，暂停用户线程，需要确保用户线程暂停的字节码指令不会导致引用关系的变化，所以JVM会在字节码指令中，选一些指令作为“安全点”,比如：方法调用、循环跳转、异常跳转等，一般这些指令才会产生安全点。GC时要暂停用户线程，并不是抢占式的中断而是主动式中断，主动式就是设置一个标志，作为中断标志，各个用户线程在运行过程中会不停的主动轮询这个标志，一旦发现中断标志为true，就会在自己最近“安全点”上主动中断挂起。比如小明正在吃甘蔗，将甘蔗皮吐到了地上(垃圾)，这时候正在吃着甘蔗，小明的妈妈开始打扫卫生(GC)了，这时候小明会把甘蔗放到桌子上(安全点)，小明妈妈开始打扫卫生(GC)，小明妈妈打扫完了，这时候小明从桌子上拿起没有吃完的甘蔗继续吃。不知道我这样解释是否能解释清楚。

安全区域

既然上述已经有了安全点了，那么为什么会有安全区域呢？主要是因为用户线程sleep或Blocked状态，睡眠了不会进行轮询查找中断标志，那么就无法进入安全点，这种情况，引入安全区域。也就是说当用户线程进入sleep或Blocked状态就会进入安全区域，如果这时候开始GC那么GC是不会去管安全区域的线程，如果安全区域的线程睡眠结束了就会准备离开安全区域，需要检查GC是否完成，如果完成则继续执行当前线程。否则一直等待GC完成。安全区域是指能够确保在某一段代码片段中，引用关系不会发生变化，这个区域中任意地方开始垃圾收集都是安全的，可以把安全区域看作被扩展拉伸了的安全点。

当用户线程执行到安全区域里面的代码是，首先会标识自己已经进入了安全区域，这段时间里JVM要是发起GC就不必去管这个线程了，当线程要离开安全区域时，它要等到JVM垃圾回收是否已经完成了，或者其他GC中需要暂停用户线程的阶段。如果完成了，那么线程当做什么都没有发生过，继续执行；如果没有完成，那么必须一直等待，直到收到可以离开安全区域的信号为止。我们再用小明的例子举例：假如小明正在吃甘蔗，地上一堆甘蔗皮，这时小明拿着甘蔗睡着了(sleep)，小明所处的这一段地就处于安全区了, 小明妈妈准备来打扫卫生(GC)了，怕打扰到小明睡觉就会绕过这段区域打扫其他的区域了。这样说不知道会不会解释清楚了。

低延迟的垃圾回收器

垃圾回收器的三个指标：内存占用、吞吐量、延迟现在主流的垃圾回收器主要降低延迟(STW)，降低延迟的时间那么必然导致内存占用和吞吐量的增加。

Epllson

Epllson不能进行垃圾回收，是一个“不干活”的垃圾回收器，它还要负责堆的管理与布局、对象的分配、与解释器的协作、与编译器的协作、与监控子系统的协作等职责，主要用于需要剥离垃圾收集器影响的性能测试和压力测试。

有类似于G1的Region，但是没有分代，标志性的设计是染色指针ColoredPointers,染色指针有4TB的内存限制，但是效率极高，它是一种将少量额外的信息存储在指针上的技术。可以做到几乎整个收集过程全程可并发，短暂的STW也只与GC Roots大小相关与堆空间内存大小无关，STW的时间小于10ms.