JVM 垃圾回收算法和 CMS 垃圾回收器

本文核心主要是讲述：JVM 中的几种垃圾回收算法理论，以及多种垃圾收集器，并且详细参数 CMS 垃圾收集器的实现、优缺点等，最后也会解释一下三色标记法与读写屏障。

垃圾收集算法

收集算法.png

分代收集理论 (Generational Collection)

当前商业虚拟机的垃圾收集都是采用 "分代收集" (Generational Collecting)算法，根据对象不同的存活周期将内存划分为多块

一般是把 Java 堆分作新生代和老年代, 这样就可以根据各个年代的特点采用最适当的收集算法，譬如新生代每次GC都有大批量对象死去，只有少量存活，那就选用复制算法只需要付出少量存活对象的复制成本就可以完成收集。

综合前面几种GC算法的优缺点，针对不同生命周期的对象采用不同的GC算法

新生代采用 Copying
老年代采用 Mark-Sweep or Mark-Compact

标记-复制算法 (Copying)

为了解决效率问题，“复制” 收集算法出现了。他可以将内存分为大小相同的两块，每次使用其中一块。当这块的内存使用完成后，就将存活的对象复制到另外一边去，然后再把使用的空间一次清理掉。这样就使每次的内存回收都是对内存区间的一半进行回收。

标记复制算法.png

标记-清除算法(Mark-Sweep)

算法分为 "标记" 和 "清除" 两阶段，首先标记出所有需要回收的对象，然后回收所有需要回收的对象

缺点

效率问题, 标记和清理两个过程效率都不高
空间问题, 标记清理之后会产生大量不连续的内存碎片，空间碎片太多可能会导致后续使用中无法找到足够的连续内存而提前触发一次的垃圾收集动作。

标记清除算法.png

标记-整理算法 (Mark-Compact)

标记过程仍然一样，但后续步骤不是进行直接清理，而是令所有存活的对象一端移动，然后直接清理掉这端边界以外的内存。
没有内存碎片
对 Mark-Sweep(标记清除) 耗费更多的时间进行 compact(整理)

标记整理算法.png

垃圾收集器

垃圾收集器.png

如果说垃圾收集算法是内存回收的方法理论，那么垃圾收集器就是内存回收的具体实现。

虽然我们对各收集器进行比较，但并非为了挑选出一个最好的收集器，因为直到现在为止还没有最好的垃圾收集器出现，更加没有万能的垃圾收集器，我们能做的就是根据具体应用场景选择适合自己的收集器，试想一下：如果有一个完美无暇的垃圾收集器适用于所有场景，那么我们 Java 虚拟机就不会去实现那么多的垃圾收集器了。

查询当前使用的 JVM 信息查询命令 java -XX:+PrintCommandLineFlags -version

    ➜  ~ java -XX:+PrintCommandLineFlags -version
    -XX:InitialHeapSize=134217728 -XX:MaxHeapSize=2147483648 -XX:+PrintCommandLineFlags -XX:+UseCompressedClassPointers -XX:+UseCompressedOops -XX:+UseParallelGC 
    java version "1.8.0_281"
    Java(TM) SE Runtime Environment (build 1.8.0_281-b09)
    Java HotSpot(TM) 64-Bit Server VM (build 25.281-b09, mixed mode)

Serial 收集器

单线程收集器，收集时会暂停所有工作线程(Stop The World, 简称 STW)，使用复制收集算法，虚拟机运行在 Client 模式的默认新生代收集器

最早的收集器，单线程进行GC
New 和 Old Generation 都可以使用
在新生代, 采用复制算法; 在老年代，采用Mark-Compact算法
因为使用单线程GC，没有多线程切换的额外开销，简单实用。
Hotspot Client 模式缺省的收集器
Safepoint 安全点

JVM 参数：-XX:+UseSerialGC -XX:+UseSerialOldGC

Serial收集器.png

PerNew 收集器

ParNew 收集器就是 Serial 的多线程版本，除了使用多个收集线程外，其余行为包括算法、STW、对象分配规则、回收策略等都与Serial 收集器一模一样

对应的这种收集器是虚拟机运行在 Server 模式的默认新生代收集器，在单 CPU 的环境下，ParNew 收集器的效果并不会比Serial收集器有更好的效果

Serial 收集器的在新生代的多线程版本
使用复制算法(因为针对新生代)
只有在多CPU的环境下，效率才会比Serial收集器高
可以通过-XX:ParallelGCThreads来控制GC线程数的多少。需要结合CPU的个数
Server模式下新生代的缺省收集器。

JVM 参数：-XX:UseParNewGC

ParNew收集器.png

Parallel Scavenge 收集器(1.8 默认)

Parallel Scavenge 收集器也是一个多线程收集器，也是使用复制算法，但它的对象分配规则与收集策略都与ParNew收集器有所不同，它是以吞吐量最大化(即GC时间占总运行时间最小)为目标的收集器实现，它允许较长的STW换取总吞吐量最大化。
默认收集器线程数跟 CPU 核数相同，也可以通过参数指定
JDK 1.8 默认垃圾收集器
JVM 参数：`-XX:UseParallelGC(年轻代) -XX:UseParallelOldGC(老年代)

Serial Old 收集器

Serial Old收集器是单线程收集器，使用标记-整理算法，是老年代的收集器

Parallel Old 收集器(1.8 默认)

老年代版本吞吐量优先的收集器，使用多线程和标记-整理算法，JVM 1.6提供，在此之前，新生代使用了PS收集器的话，老年代除Serial Old外别无选择，因为PS无法与CMS收集器配合工作。

Parallel Scavenge 在老年代的实现
在 JVM 1.6 才出现 Parallel Old
采用多线程，Mark-Compact 算法
更注重吞吐量
Parallel Scavenge + Parallel Old = 高吞吐量，但是GC停顿可能不理想

Parallel Old收集器.png

CMS (Concurrent Mark Sweep) 收集器

CMS 是一种以最短停顿时间为目标的收集器，使用CMS并不能达到GC效率最高(总体GC时间最小)，但它能尽可能降低GC时服务的停顿时间， CMS收集器使用的是标记-清除算法

CMS 收集器.png

CMS 垃圾收集器步骤

CMS 收集器是基于标记-清除算法实现的，它的运作过程相对于前面几种收集器来说要更复杂一些，整个过程分为四个步骤，包括：

1)初始标记(CMS initial mark) 暂停所有的其他线程(STW)。记录下 GC ROOT 直接引用对象，速度很快。

2)并发标记(CMS concurrent mark) 并发标记阶段就是从 GC ROOT 行的直接关联对象开始遍历整个对象的过程，这个过程耗时比较长但是不需要停顿用户线程，可以与垃圾收集器一起并发运行。因此用户程序继续运行，可能会导致已经标记过的对象状态发生变化。

3)重新标记(CMS remark) 重新标记阶段就是为了修正并发标记期间，因为用户程序继续运行而导致标记产生变动，的那一部分对象的标记记录。这个阶段的停顿时间一般比初始标记阶段的时间稍长，远远比并发标记阶段时间短。主要是用到三色标记里的增量更新算法

4)**并发清除(CMS concurrent sweep)**开启用户线程，同时 GC 线程开始对未标记的区域做清扫，这个阶段如果有新增对象会被标记为黑色不做任何处理(见下面三色标记算法详解)。

CMS 垃圾收集器优缺点

从它的名字可以看出他是一款优秀的垃圾收集器，主要优点：并发收集、低停顿。但是它有以下几个明显的缺点：

对于 CPU 资源敏感(会和服务抢资源);
无法处理浮动垃圾(在并发标记和并发清理阶段又产生垃圾，这种浮动垃圾只能等到下次 gc 的时候在进行清理了)
它使用的收集算法 “标记-清除” 算法会导致结束时候又大量空间碎片产生，当然通过参数 -XX:UseCMSCompactAtFullCollection 可以让 JVM 在执行标记清除完成后再做整理。
执行过程中的不确定性，会存在一次垃圾回收还没有执行完成，然后垃圾回收又被触发的情况，特别是在并发标记和并发清理阶段出现，一边回收，系统一边运行，也许没回收完成就再次触发 Full GC, 这就是 “concurrent mode failure” 此时会进入 stop the world . 用 serial old 垃圾器来回收。

CMS 垃圾收集器的参数

三色标记和读写屏障

三色标记算法

提到并发标记，我们不得不了解并发标记的三色标记算法。它是描述追踪式回收器的一种有效的方法，利用它可以推演回收器的正确性。

因为在并发标记期间应用线程还在继续跑，对象间的引用可能发生变化，**多标 **和漏标的情况还可能发生。

三色标记法.gif

我们将对象分为三种类型：

黑色：根对象，或者该对象与它的子对象都被扫描过(对象被标记了，且它的所有field也被标记完了)
灰色：对象本身被扫描，还没有扫描完该对象中的子对象(它的field还没有被标记或标记完)
白色：未被扫描对象，扫描完成所有对象之后，最终为白色的为不可达对象，即垃圾对象(对象没有被标记到)

三色标记过程

第一步，三色标记算法，如果将根对象设置为黑色，那么下级节点的为灰色，再下面的的为白色
第二步，灰色扫描完毕后，那么剩下的白色变为灰色
第三步，灰色扫描完毕后，那么全部被标记为黑色，不可达的还是为白色

三色标记算法的对象丢失

但是如果在标记过程中，应用程序也进行，那么对象的指针就有可能改变。这样的话，我们就会遇到一个问题：对象丢失。

例子：

A.c = C
B.c = null
第一步，初始 Root(黑)-> A(黑) Root(黑)-> B(灰)-> C(白)
第二步，在当前场景下执行如下操作

Root(黑)-> A(黑)-> C(白) Root(黑)-> B(黑)

第三步，如果内存回收的时候，就会将 C 回收掉，会导致 C 对象丢失。

SATB 原始快照(Snapshot-At-The-Beginning)

SATB是维持并发GC的一种手段。G1并发的基础就是SATB。SATB可以理解成在GC开始之前对堆内存里的对象做一次快照，此时活的对象就认为是活的，从而形成一个对象图
在GC收集的时候，新生代的对象也认为是活的对象，除此之外其他不可达的对象也认为是垃圾对象。
如何找到在GC过程分配的对象呢?每个region记录着两个top-at-mark-start(TAMS) 指针，分别为prevTAMS 和nextTAMS。在TAMS以上的独享就是新分配的，因而被视为隐式marked
通过这种方式我们就找到了再GC过程中新分配的对象，并把这些对象认为是活的对象。
解决了对象在GC过程中分配的问题，呢么GC过程中引用频繁变化的问题是怎么解决的呢?
G1给出的解决办法是通过Write Barrier. Write Barrier 就是堆引用字段进行赋值做了额外处理。通过Write Barrier就可以了解到哪些引用对象发生了什么样的变化
mark 的过程就是遍历heap标记live object的过程，采用的三色标记算法，这三种颜色为white(表示还未访问到)、gray(访问到但是它用到的引用还诶有完全扫描)、black (访问到而且其用到的引用完全扫描完)
整个三色标记算法就是从GC Roots出发遍历heap，针对可达对象先标记white为gray，然后再标记gray为black; 遍历完成之后所有可达对象都是black的，所有white 都是可以回收的。
SATB仅仅对于在marking开始阶段进行"snapshot"(marked all reachable at mark start), 但是concurrent 的时候并发修改可能造成对象漏标记

为什 G1 采用 STAB?CMS 使用增量更新?

我的理解：STAB 相对增量更新效率会很高(当然 STAB 可能造成更多的浮动垃圾)，因为不需要重新标记再次深度扫描被删除引用对象，而 CMS 对增量引用的根对象会做深度扫描， G1 因为很多对象都是位于不同的 region ，CMS 是一块老年代区域，重新深度扫描对象的话 G1 的代价会比 CMS 高，所以 G1 选择 STAB 不深度扫描对象，只是简单标记，等到下一轮 GC 再深度扫描。

写屏障(Write Barrier)

    void oop_field_store(oop* field, oop new_value) { 
        *field = new_value; // 赋值操作
    }

所谓的写屏障，其实就是指在赋值操作前后，加入一些处理(可以参考AOP的概念)：

    void oop_field_store(oop* field, oop new_value) {  
        pre_write_barrier(field); // 写屏障-写前操作
        *field = new_value; 
        post_write_barrier(field, value);  // 写屏障-写后操作
    }

写屏障和SATB

当对象E的成员变量的引用发生变化时(objE.fieldG = null;)，我们可以利用写屏障，将E原来成员变量的引用对象G记录下来：

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

这种做法的思路是：尝试保留开始时的对象图，即原始快照(Snapshot At The Beginning，SATB)，当某个时刻的GC Roots确定=后，当时的对象图就已经确定了。比如当时 D是引用着G的，那后续的标记也应该是按照这个时刻的对象图走(D引用着G)。如果期间发生变化，则可以记录起来，保证标记依然按照原本的视图来。

值得一提的是，扫描所有GC Roots 这个操作(即初始标记)通常是需要STW的，否则有可能永远都扫不完，因为并发期间可能增加新的GC Roots。

一点小优化：如果不是处于垃圾回收的并发标记阶段，或者已经被标记过了，其实是没必要再记录了，所以可以加个简单的判断:

    void pre_write_barrier(oop* field) {
      // 处于GC并发标记阶段 且 该对象没有被标记（访问）过
      if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) { 
          oop old_value = *field; // 获取旧值
          remark_set.add(old_value); // 记录  原来的引用对象
      }
    }

写屏障和增量更新

当对象D的成员变量的引用发生变化时(objD.fieldG = G;)，我们可以利用写屏障，将D新的成员变量引用对象G记录下来：

    void post_write_barrier(oop* field, oop new_value) {  
      if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
          remark_set.add(new_value); // 记录新引用的对象
      }
    }

这种做法的思路是：不要求保留原始快照，而是针对新增的引用，将其记录下来等待遍历，即增量更新(Incremental Update)

读屏障

    oop oop_field_load(oop* field) {
      pre_load_barrier(field); // 读屏障-读取前操作
      return *field;
    }

读屏障是直接针对第一步：var G = objE.fieldG;，当读取成员变量时，一律记录下来：

    void pre_load_barrier(oop* field, oop old_value) {  
      if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
          oop old_value = *field;
          remark_set.add(old_value); // 记录读取到的对象
      }
    }

现代追踪式(可达性分析)的垃圾回收器几乎都借鉴了三色标记的算法思想，尽管实现的方式不尽相同：比如白色/黑色集合一般都不会出现(但是有其他体现颜色的地方)、灰色集合可以通过栈/队列/缓存日志等方式进行实现、遍历方式可以是广度/深度遍历等等。

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

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

漏标-读写屏障

漏标会导致被引用的对象被当成垃圾误删除，这个是严重的 BUG ，有两种处理方案：增量更新(Incremental Update)和原始快照(Snapshot At The Beginning, STAB)

增量更新就是当黑色对象插入新的指向白色对象的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这个可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了。

原始快照就当灰色对象要删除指向白色的对象，将白色对象直接标记为黑色(目的就是让这种对象在本轮 GC 清理中能够存活下来，等待下一轮 GC 的时候重新扫描，这个对象也可能就是浮动垃圾)

以上无论是引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。

记忆集和卡表 (Remember Set & Cardtable)

在新生代做 GC Roots 可达性扫描过程中可能会碰到跨代引用的对象 ,这种如果又去对老年代再去扫描效率太低了。为此,在新生代可以引入记录集 (Remember Set) 的数据结枃 (记录从非收集区到收集区的指针集合) , 避免把整个老年代加入 GC Roots扫描范围。事实上并不只是新生代、老年代之间才有跨代引用的问题,所有涉及部分区域收集( Partial GC)行为的垃圾收集器,典型的如G1、ZC和 Shenandoah 收集器,都会面临相同的问题。

垃圾收集场景中, 收集器只需通过记忆集判断岀某一块非收集区域是否存在指向收集区域的指针即可, 无需了解跨代引用指针的全部细节hotspot使用一种叫做 "卡表"( Cardtable )的方式实现记忆集,也是目前最常用的一种方式。关于卡表与记忆集的关系,可以类比为Java语言中 Hashmap与Map的关系卡表是使用一个字节数组实现: CARD TABLE[],每个元素对应着其标识的内存区域一块特定大小的内存块,称为“卡页”。hotspot使用的卡页是2^9大小,即512字节