JAVA垃圾收集算法总结以及CMS、G1算法详解

从方法论上讲，程序语言的回收算法主要分为

一、引用计数算法（Reference Counting）：给对象添加一个引用计数器，每当一个地方引用它时，数据器加1；当引用失效时，计数器减1；计数器为0的即可被回收。

二、根搜索算法（GC Root Tracing）：通过一系列的名为“GC Root”的对象作为起始点，从这些节点开始向下搜索，搜索所有走过的路径称为引用链（Reference Chain）,当一个对象到GC Root没有任何引用链相连时（用图论来说就是GC Root到这个对象不可达时），证明该对象是可以被回收的。

Java采用了根搜索算法，基本原理根据上面解释应该都能理解，基于根搜索方法，又有具体实现算法

一、标记-清除算法（Mark-Sweep）

最基础的垃圾收集器算法，分为“标记”和“清除”两个阶段，先标记处所需要回收的对象，标记完成后，统一回收掉所有被标记的对象。

缺点：
1）效率问题，标记和清除的效率不高。
2）清除后会产生大量的不连续的内存碎片，可能会导致在程序需要为较大对象分配内存时无法找到足够连续的内存，不得不提前触发垃圾收集动作。

二、复制算法（Copying）

将内存容量分成大小相等的两块，每次只使用其中一块，当一块用完时，将还存活的对象复制到另一块去，然后把之前使用满的那块空间一次性清理掉，如此反复。

优点：内存分配的时候不用考虑内存碎片问题，只移动堆顶指针，按顺序分配即可，简单高效。

缺点：内存空间浪费大，每次只能使用当前能够使用内存空间的一半；当对象存活率较高时，需要有大量的复制操作，效率低。

三、标记-整理算法（Mark-Compact）

标记整理是在标记-清算上改进得来，前面说到标记-清算内存碎片的问题，在标记-整理中有解决。同样有标记阶段，标记出所有需要回收的对象，但是不会直接清理，而是将存活的对象向一端移动，在移动过程中清理掉可回收对象。

优点：解决了之前内存碎片的问题，特别是在存活率高的时候，效率远高于复制算法。

四、分代收集算法（Generational Collection）

根据内存对象的存活周期不同，将内存划分成几块，java虚拟机中一般将内存划分成新生代和老年代，当新建对象时一般在新生代中分配内存，在新生代垃圾收集器回收几次后仍然存活的对象，将被移动到老年代，或者当大的对象在新生代中无法分配到足够连续的内存空间时也会直接分配到老年代。

上面四种算法JVM在回收内存时都有采用，大多都是复合运用多种算法一起实现垃圾回收，具体细节每个算法都可以写很多内容，为了不偏题，我们这里只写CMS、G1，其他的有兴趣可以自己查询资料。CMS算法主要是应用在分代收集算法的老年代里，是从JDK8开始采用，当然默认没有启用，如果在开发或生产环境想采用CMS，可以修改JVM配置-XX:+UseConcMarkSweepGC : 手动指定老年代使用CMS收集器。

下面进入正题

CMS定义：英文全称Concurrent Mark Sweep，可以翻译为并发标记清除，是一种以获取最短回收停顿时间为目标的收集器。这是因为CMS收集器工作时，GC工作线程与用户线程可以并发执行，以此来达到降低收集停顿时间的目的。

CMS收集器仅作用于老年代的收集，是基于标记-清除算法的，它的运作过程分为4个步骤：

image

初始标记（CMS initial mark）
并发标记（CMS concurrent mark）
重新标记（CMS remark）
并发清除（CMS concurrent sweep）

其中，初始标记、重新标记这两个步骤仍然需要Stop-the-world。初始标记仅仅只是标记一下GC Roots能直接关联到的对象，速度很快，并发标记阶段就是进行GC Roots Tracing的过程，而重新标记阶段则是为了修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分对象的标记记录，这个阶段的停顿时间一般会比初始阶段稍长一些，但远比并发标记的时间短。

CMS以流水线方式拆分了收集周期，将耗时长的操作单元保持与应用线程并发执行。只将那些必需STW才能执行的操作单元单独拎出来，控制这些单元在恰当的时机运行，并能保证仅需短暂的时间就可以完成。这样，在整个收集周期内，只有两次短暂的暂停（初始标记和重新标记），达到了近似并发的目的。

CMS收集器优点：并发收集、低停顿。

CMS收集器缺点：

CMS收集器对CPU资源非常敏感。
CMS收集器无法处理浮动垃圾（Floating Garbage），所以如果采用CMS算法，JVM还是在浮动垃圾很多时，自动运行fullgc一次来清除浮动垃圾。
CMS收集器是基于标记-清除算法，该算法的缺点都有。

什么情况下CMS比较适合：

（1）响应时间优先，能接受牺牲一定的吞吐量，如果需要高响应时间和高吞吐量，推荐使用G1。后续文章再继续介绍G1。G1也是JDK9默认的垃圾收集器；

（2）硬件配置较高，即CPU和内存资源充足。CMS由于需要与用户线程并发执行，所以可能会竞争CPU资源。同时CMS并发标记阶段，用户线程同时执行时会新建对象，故内存占用会比较高；

（3）堆大小在3G到8G之间，同时存活时间较长的对象比较多

下面再简单讲讲G1算法，

G1重新定义了堆空间，打破了原有的分代模型，将堆划分为一个个区域。这么做的目的是在进行收集时不必在全堆范围内进行，这是它最显著的特点。区域划分的好处就是带来了停顿时间可预测的收集模型：用户可以指定收集操作在多长时间内完成。即G1提供了接近实时的收集特性。

G1收集器将整个Java堆划分为多个大小相等的独立区域（Region），虽然还保留有新生代和老年代的概念，但新生代和老年代不再是物理隔离的了，它们都是一部分Region（不需要连续）的集合。Region的大小是一致的，数值是在1M到32M字节之间的一个2的幂值数，JVM会尽量划分2048个左右、同等大小的Region。其实这个数字既可以手动调整，G1也会根据堆大小自动进行调整。

G1收集的运作过程大致如下：

初始标记（Initial Marking）：仅仅只是标记一下GC Roots能直接关联到的对象，并且修改TAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确可用的Region中创建新对象，这阶段需要停顿线程，但耗时很短。
并发标记（Concurrent Marking）：是从GC Roots开始堆中对象进行可达性分析，找出存活的对象，这阶段耗时较长，但可与用户程序并发执行。
最终标记（Final Marking）：是为了修正并发标记期间因用户程序继续运作而导致标记产生变动的那一部分标记记录，虚拟机将这段时间对象变化记录在线程Remembered Set Logs里面，最终标记阶段需要把Remembered Set Logs的数据合并到Remembered Set中，这阶段需要停顿线程，但是可并行执行。
筛选回收（Live Data Counting and Evacuation）：首先对各个Region的回收价值和成本进行排序，根据用户所期望的GC停顿时间来制定回收计划。这个阶段也可以做到与用户程序一起并发执行，但是因为只回收一部分Region，时间是用户可控制的，而且停顿用户线程将大幅提高收集效率。
下图就是G1堆空间分布
image

** G1特点：**

并行与并发：G1能充分利用多CPU、多核环境下的硬件优势，使用多个CPU来缩短Stop-the-world停顿的时间，部分其他收集器原来需要停顿Java线程执行的GC操作，G1收集器仍然可以通过并发的方式让Java程序继续运行。
分代收集
空间整合：与CMS的标记-清除算法不同，G1从整体来看是基于标记-整理算法实现的收集器，从局部（两个Region之间）上来看是基于“复制”算法实现的。但无论如何，这两种算法都意味着G1运作期间不会产生内存空间碎片，收集后能提供规整的可用内存。这种特性有利于程序长时间运行，分配大对象时不会因为无法找到连续内存空间而提前触发下一次GC。
可预测的停顿：这是G1相对于CMS的一个优势，降低停顿时间是G1和CMS共同的关注点。

总结

随着JVM的发展，ORACLE官方推出的JDK11又有了新算法ZGC，它对内存碎片的整理更加优化，回收暂停时间也更加缩短，具体细节本人还没有深入研究，后面有机会可以写文章专门介绍它。

最后，我把目前主流JDK使用到的JVM垃圾收集器采用的算法做下简单总结，方便大家对比参考，

新生代垃圾收集器

Serial-复制算法：Serial收集器是新生代单线程收集器，优点是简单高效，算是最基本、发展历史最悠久的收集器。它在进行垃圾收集时，必须暂停其他所有的工作线程，直到它收集完成。
ParNew收集器-复制算法：ParNew收集器是新生代并行收集器，其实就是Serial收集器的多线程版本。
Parallel Scavenge（并行回收）-复制算法：

Parallel Scavenge收集器是新生代并行收集器，追求高吞吐量，高效利用 CPU。该收集器的目标是达到一个可控制的吞吐量（Throughput）。所谓吞吐量就是CPU用于运行用户代码的时间与CPU总消耗时间的比值，即吞吐量=运行用户代码时间/（运行用户代码时间+垃圾收集时间）。停顿时间越短就越适合需要与用户交互的程序，良好的响应速度能提升用户体验，而高吞吐量则可用高效率地利用CPU时间，尽快完成程序的运算任务，主要适合在后台运算而不需要太多交互的任务。

2. 老年代垃圾收集器

Serial Old-标记整理算法：Serial Old是Serial收集器的老年代版本，它同样是一个单线程(串行)收集器，使用标记整理算法。这个收集器的主要意义也是在于给Client模式下的虚拟机使用
Parallel Old-标记整理算法：Parallel Old 是Parallel Scavenge收集器的老年代版本，使用多线程和“标记-整理”算法。
CMS：标记清除算法
G1：标记整理算法