CMS垃圾收集器与三色标记算法详解

目录
CMS垃圾收集器详解
垃圾收集器前世今生
CMS垃圾收集器原理
三色标记算法
垃圾收集器的前世今生

现代垃圾收集器都是基于分代收集理论，将java对象按年龄分为新生代和老年代。其中新生代主要采用标记-复制算法以提高效率。老生代通常使用标记-整理和标记-清除算法。jvm的垃圾收集器已经经历了多代的发展：

Serial：Serial（串行）收集器是最基本、历史最悠久的垃圾收集器，这个收集器是一个单线程收集器，它在进行垃圾收集工作的时候必须暂停其他所有的工作线程（ "Stop The World" ），直到它收集结束。新生代采用复制算法，老年代采用标记-整理算法。可用(-XX:+UseSerialGC -XX:+UseSerialOldGC)参数启用。
Parallel Scavenge：Parallel收集器其实就是Serial收集器的多线程版本，除了使用多线程进行垃圾收集外，其余行为（控制参数、收集算法、回收策略等等）和Serial收集器类似。默认的收集线程数跟cpu核数相同，当然也可以用参数(-XX:ParallelGCThreads)指定收集线程数。新生代采用复制算法，老年代采用标记-整理算法。在注重吞吐量以及CPU资源的场合，都可以优先考虑 Parallel Scavenge收集器和Parallel Old收集器(JDK8默认的新生代和老年代收集器)。可用(-XX:+UseParallelGC(新生代),-XX:+UseParallelOldGC(老年代)启用。
ParNew：ParNew收集器其实跟Parallel收集器很类似，区别主要在于它可以和CMS收集器（真正意义上的并发收集器，后面详解）配合使用。新生代采用复制算法，老年代采用标记-整理算法。除了Serial收集器外，只有它能与CMS收集器配合工作。
CMS：CMS（Concurrent Mark Sweep）收集器是一种以获取最短回收停顿时间为目标的收集器。它非常符合在注重用户体验的应用上使用，它是HotSpot虚拟机第一款真正意义上的并发收集器，它第一次实现了让垃圾收集线程与用户线程同时工作。CMS收集器是一种 “标记-清除”算法实现的，它的运作过程相比于前面几种垃圾收集器复杂很多。
G1、ZGC、Shenandoah：更为先进、STW（ "Stop The World" ）时间可控的垃圾收集器，从JDK9开始，jvm开始默认使用这几种垃圾收集器，将会在后面的博文中介绍。

CMS垃圾收集器原理

CMS收集器可用(-XX:+UseConcMarkSweepGC(old))开启，这是一种专门为老年代设计的垃圾收集器。整个过程分为四个步骤：

初始标记：暂停所有的其他线程(STW)，并记录下gc roots直接能引用的对象，速度很快。
并发标记：并发标记阶段就是从GC Roots的直接关联对象开始遍历整个对象树的过程，耗时较长但是不需要停顿用户线程，可以与垃圾收集线程一起并发运行。因为用户程序继续运行，可能会有导致已经标记过的对象状态发生改变。
重新标记：重新标记阶段就是为了修正并发标记期间因为用户程序继续运行而导致引用产生变动的那一部分对象的标记记录，这个阶段的停顿时间一般会比初始标记阶段的时间稍长，远远比并发标记阶段时间短。主要用到三色标记里的增量更新算法(见下面详解)做重新标记。
并发清理：开启用户线程，同时GC线程开始对未标记的区域做清扫。这个阶段如果有新增对象会被标记为存货对象不做任何处理。
并发重置：重置本次GC过程中的标记数据。

值得注意的是，对于CMS收集器本身来说，默认只有在重新标记阶段是多线程并发运行，其它阶段都只有一个CMS线程运行（可由参数调整）。CMS由并发收集、低停顿的优点，但同时存在缺陷：

无法处理浮动垃圾(在并发标记和并发清理阶段又产生垃圾，这种浮动垃圾只能等到下一次gc再清理了)；
执行过程中的不确定性，会存在上一次垃圾回收还没执行完，然后垃圾回收又被触发的情况，特别是在并发标记和并发清理阶段会出现，一边回收，系统一边运行，也许没回收完就再次触发full gc，也就是"concurrent mode failure"，此时会进入stop the world，用serial old垃圾收集器来回收，当然我们要坚决避免这种情况。

CMS的相关核心参数
1. -XX:+UseConcMarkSweepGC：启用cms
2. -XX:ConcGCThreads：并发的GC线程数
3. -XX:+UseCMSCompactAtFullCollection：FullGC之后做压缩整理（减少碎片）
4. -XX:CMSFullGCsBeforeCompaction：多少次FullGC之后压缩一次，默认是0，代表每次FullGC后都会压缩一次
5. -XX:CMSInitiatingOccupancyFraction: 当老年代使用达到该比例时会触发FullGC（默认是92，这是百分比）
6. -XX:+UseCMSInitiatingOccupancyOnly：只使用设定的回收阈值(-XX:CMSInitiatingOccupancyFraction设定的值)，如果不指定，JVM仅在第一次使用设定值，后续则会自动调整
7. -XX:+CMSScavengeBeforeRemark：在CMS GC前启动一次minor gc，目的在于减少老年代对年轻代的引用，降低CMS GC的标记阶段时的开销，一般CMS的GC耗时 80%都在标记阶段
8. -XX:+CMSParallellnitialMarkEnabled：表示在初始标记的时候多线程执行，缩短STW
9. -XX:+CMSParallelRemarkEnabled：在重新标记的时候多线程执行，缩短STW;

三色标记算法

CMS收集器底层使用了三色标记算法。在并发标记的过程中，因为标记期间应用线程还在继续跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。引入“三色标记”，把Gcroots可达性分析遍历对象过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，对于黑色对象， gc线程不会重新扫描。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。
灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。灰色对象在重新标记中会再次扫描。
白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。

在并发标记过程中，如果由于方法运行结束导致部分局部变量(gcroot)被销毁，这个gcroot引用的对象之前又被扫描过(被标记为非垃圾对象)，那么本轮GC不会回收这部分内存。这部分本应该回收但是没有回收到的内存，被称之为“浮动垃圾”。浮动垃圾并不会影响垃圾回收的正确性，只是需要等到下一轮垃圾回收中才被清除。另外，针对并发标记(还有并发清理)开始后产生的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能也会变为垃圾，这也算是浮动垃圾的一部分。

对标无伤大雅，但是漏标就会造成重大错误了，会导致应该存货的对象被当成垃圾回收掉，这是绝对不允许的，下面举例说明漏标的情况：

public class MyTest1 {
    public static void main(String[] args) {
        //初始标记
        A a=new A();
        //并发标记
        C x=a.b.c;//创建了一个新的引用x指向a.b.c的C对象
        //a.b被标记为灰色
        a.b.c=null;//在对象a.b被扫描到了，但还没来得及扫描a.b中的引用c的时候,a.b.c的引用被置为null
    }

    class A{
        B b=new B();
    }

    class B{
        C c=new C();
    }

    class C{ }
}

以上代码就是一个漏标的例子，a在初始标记被标记为gcroot，并在并发标记中被完全扫描为黑色对象，创建一个新的引用x指向a.b.c的C对象，在扫描a.b时，a.b先被标记成灰色对象，紧接着a.b.c的引用被置为null，此时a.b.c指向的C对象还没被扫描到，还是白色对象，这就造成了这个C对象永远也不会被gc扫描到（白色对象），它在并发清理时会被gc回收，但这显然时不对的，因为仍有引用x指向C对象，它并不是垃圾。

针对这种情况，通常有两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

增量更新就是当有引用指向白色对象时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的对象为根，重新扫描一次，即把之前的白色对象涂为灰色。同时，如果黑色对象新插入了指向白色对象的引用之后，它就变回灰色对象了。

原始快照就是当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发标记结束之后，将这些记录过的灰色对象指向的白色对象标记为灰色，重新扫描一次，这样就避免了可能出现的误回收了，当然这个对象也有可能是浮动垃圾，这时允许出现的。以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。

所谓的写屏障，其实就是指在赋值操作前后，加入一些处理（可以参考AOP的概念），当a.b的成员变量的引用发生变化时，比如a.b.c = null，我们可以利用写屏障，将a.b原来成员变量的引用对象c记录下来，这就是原始快照：

void pre_write_barrier(oop* field) {
oop old_value = *field; // 获取旧值
remark_set.add(old_value); // 记录原来的引用对象
}

当C对象的引用发生变化时，比如新增引用（C x=a.b.c），我们可以利用写屏障，将新的引用记录下来：

void post_write_barrier(oop* field, oop new_value) {
remark_set.add(new_value); // 记录新引用的对象
}

对于读写屏障，以Java HotSpot VM为例，其并发标记时对漏标的处理方案如下：

CMS：写屏障 + 增量更新
G1，Shenandoah：写屏障 + SATB
ZGC：读屏障

为什么G1用SATB？CMS用增量更新？

原始快照相对增量更新效率会高(可能造成更多的浮动垃圾)，因为不需要在重新标记阶段再次深度扫描被删除引用对象（黑色对象新插入白色对象或灰色对象的引用），而CMS对增量引用的根对象会做深度扫描，G1因为很多对象都位于不同的region，CMS就一块老年代区域，重新深度扫描对象的话G1的代价会比CMS高，所以G1选择SATB不深度扫描对象，只是简单标记，等到下一轮GC再深度扫描。

原文链接：https://blog.csdn.net/w7sss/article/details/117248618

CMS垃圾收集器与三色标记算法详解

垃圾收集器的前世今生

CMS垃圾收集器原理

三色标记算法