JVM-GC算法

---

一、GC基本概念

GC(Garbage Collection)垃圾收集，1960年最早在List中使用。在Java中GC回收的对象是堆空间和永久区，可以有效避免程序员人为造成内存泄漏问题。将堆空间和永久区没有作用的对象进行释放和回收。

二、 如何判断对象是垃圾

有两种经典的判断方法，借用网友的图（文中最后有给出链接）：

引用计数法，思路很简单，但是如果出现循环引用，即：A 引用 B，B 又引用 A，这种情况下就不好办了，所以 JVM 中使用了另一种称为“可达性分析”的判断方法：

还是刚才的循环引用问题（也是某些公司面试官可能会问到的问题)，如果 A 引用 B，B 又引用 A，这 2 个对象是否能被 GC 回收？

答案：关键不是在于 A、B 之间是否有引用，而是 A、B 是否可以一直向上追溯到 GC Roots。如果与 GC Roots 没有关联，则会被回收，否则将继续存活。

上图是一个用“可达性分析”标记垃圾对象的示例图，灰色的对象表示不可达对象，将等待回收。

三、 哪些内存区域需要 GC

在第一部分 JVM 内存布局中，我们知道了 thread 独享的区域：PC Regiester、JVM Stack、Native Method Stack，其生命周期都与线程相同（即：与线程共生死），所以无需 GC。线程共享的 Heap 区、Method Area 则是 GC 关注的重点对象。

四 常用的 GC 算法

1）mark-sweep 标记清除法

如上图，黑色区域表示待清理的垃圾对象，标记出来后直接清空。该方法简单快速，但是缺点也很明显，会产生很多内存碎片。

2）mark-copy 标记复制法

思路也很简单，将内存对半分，总是保留一块空着（上图中的右侧），将左侧存活的对象（浅灰色区域）复制到右侧，然后左侧全部清空。避免了内存碎片问题，但是内存浪费很严重，相当于只能使用 50% 的内存。

3）mark-compact 标记 - 整理（也称标记 - 压缩）法

避免了上述两种算法的缺点，将垃圾对象清理掉后，同时将剩下的存活对象进行整理挪动（类似于 windows 的磁盘碎片整理），保证它们占用的空间连续，这样就避免了内存碎片问题，但是整理过程也会降低 GC 的效率。

4）根搜索算法（补充）

根搜索算法是从离散数学中的图论引入的，程序把所有引用关系看作一张图，从一个节点GC ROOT 开始，寻找对应的引用节点，找到这个节点后，继续寻找这个节点的引用节点。当所有的引用节点寻找完毕后，剩余的节点则被认为是没有被引用到的节点，即无用的节点。应该可以想想出来，就是根据爹妈往下找孩子，剩下没有关系的孤儿都是孤儿院（GC）收集对象。基本所有GC算法都引用根搜索算法这种概念

目前Java中可以作为GC ROOT的对象有：

1、虚拟机栈中引用的对象（本地变量表）

2、方法区中静态属性引用的对象

3、方法区中常亮引用的对象

4、本地方法栈中引用的对象（Native对象）

5）generation-collect 分代收集算法

将内存分成了三大块：年青代（Young Genaration），老年代（Old Generation）, 永久代（Permanent Generation），其中 Young Genaration 更是又细为分 eden，S0，S1 三个区。

结合我们经常使用的一些 jvm 调优参数后，一些参数能影响的各区域内存大小值，示意图如下：

注：jdk8 开始，用 MetaSpace 区取代了 Perm 区（永久代），所以相应的

jvm 参数变成

 -XX:MetaspaceSize 及 -XX:MaxMetaspaceSize

以 Hotspot 为例，我们来分析下 GC 的主要过程：

刚开始时，对象分配在 eden 区，s0（即：from）及 s1（即：to）区，几乎是空着。

随着应用的运行，越来越多的对象被分配到 eden 区。

当 eden 区放不下时，就会发生 minor GC（也被称为 young GC），第 1 步当然是要先标识出不可达垃圾对象（即：下图中的黄色块），然后将可达对象，移动到 s0 区（即：4 个淡蓝色的方块挪到 s0 区），然后将黄色的垃圾块清理掉，这一轮过后，eden 区就成空的了。

注：这里其实已经综合运用了“【标记 - 清理 eden】 + 【标记 - 复制 eden->s0】”算法。

随着时间推移，eden 如果又满了，再次触发 minor GC，同样还是先做标记，这时 eden 和 s0 区可能都有垃圾对象了（下图中的黄色块），注意：这时 s1（即：to）区是空的，s0 区和 eden 区的存活对象，将直接搬到 s1 区。然后将 eden 和 s0 区的垃圾清理掉，这一轮 minor GC 后，eden 和 s0 区就变成了空的了。

继续，随着对象的不断分配，eden 空可能又满了，这时会重复刚才的 minor GC 过程，不过要注意的是，这时候 s0 是空的，所以 s0 与 s1 的角色其实会互换，即：存活的对象，会从 eden 和 s1 区，向 s0 区移动。然后再把 eden 和 s1 区中的垃圾清除，这一轮完成后，eden 与 s1 区变成空的，如下图。

对于那些比较“长寿”的对象一直在 s0 与 s1 中挪来挪去，一来很占地方，而且也会造成一定开销，降低 gc 效率，于是有了“代龄 (age)”及“晋升”。

对象在年青代的 3 个区 (edge,s0,s1) 之间，每次从 1 个区移到另 1 区，年龄 +1，在 young 区达到一定的年龄阈值后，将晋升到老年代。下图中是 8，即：挪动 8 次后，如果还活着，下次 minor GC 时，将移动到 Tenured 区即老年代。

如果老年代，最终也放满了，就会发生 major GC（即 Full GC），由于老年代的的对象通常会比较多，因为标记 - 清理 - 整理（压缩）的耗时通常会比较长，会让应用出现卡顿的现象，这也是为什么很多应用要优化，尽量避免或减少 Full GC 的原因。

注：如果分配的新对象比较大，eden 区放不下，但是 old 区可以放下时，会直接分配到 old 区（即没有晋升这一过程，直接到老年代了）。

五  收集器

1 Serial （串）收集器

单线程用标记 - 复制算法，快刀斩乱麻，单线程的好处避免上下文切换，早期的机器，大多是单核，也比较实用。但执行期间，会发生 STW（Stop The World）。

2 ParNew （标准）收集器

Serial 的多线程版本，同样会 STW，在多核机器上会更适用。

3 Parallel Scavenge（并行） 收集器

ParNew 的升级版本，主要区别在于提供了两个参数：-XX:MaxGCPauseMillis 最大垃圾回收停顿时间；-XX:GCTimeRatio 垃圾回收时间与总时间占比，通过这 2 个参数，可以适当控制回收的节奏，更关注于吞吐率，即总时间与垃圾回收时间的比例。

4 Serial Old 收集器

因为老年代的对象通常比较多，占用的空间通常也会更大，如果采用复制算法，得留 50% 的空间用于复制，相当不划算，而且因为对象多，从 1 个区，复制到另 1 个区，耗时也会比较长，所以老年代的收集，通常会采用“标记 - 整理”法。从名字就可以看出来，这是单线程（串行）的， 依然会有 STW。

5 Parallel Old 收集器

一句话：Serial Old 的多线程版本。

6 CMS 收集器

全称：Concurrent Mark Sweep，从名字上看，就能猜出它是并发多线程的。这是 JDK 7 中广泛使用的收集器，有必要多说一下，借一张网友的图说话：

Serial ,ParNew, Parellel Scavenge 都是回收年青代的。CMS，Serial Old, Parallel Old 都是回收老年代的。

1）Inital Mark 初始标记：主要是标记 GC Root 开始的下级（注：仅下一级）对象，这个过程会 STW，但是跟 GC Root 直接关联的下级对象不会很多，因此这个过程其实很快。

2）Concurrent Mark 并发标记：根据上一步的结果，继续向下标识所有关联的对象，直到这条链上的最尽头。这个过程是多线程的，虽然耗时理论上会比较长，但是其它工作线程并不会阻塞，没有 STW。

3）Remark 再标志：为啥还要再标记一次？因为第 2 步并没有阻塞其它工作线程，其它线程在标识过程中，很有可能会产生新的垃圾。

试想下，高铁上的垃圾清理员，从车厢一头开始吆喝“有需要扔垃圾的乘客，请把垃圾扔一下”，一边工作一边向前走，等走到车厢另一头时，刚才走过的位置上，可能又有乘客产生了新的空瓶垃圾。所以，要完全把这个车厢清理干净的话，她应该喊一下：所有乘客不要再扔垃圾了（STW），然后把新产生的垃圾收走。当然，因为刚才已经把收过一遍垃圾，所以这次收集新产生的垃圾，用不了多长时间（即：STW 时间不会很长）。

4）Concurrent Sweep：并行清理，这里使用多线程以“Mark Sweep- 标记清理”算法，把垃圾清掉，其它工作线程仍然能继续支行，不会造成卡顿。

7 G1 收集器

G1 的全称是 Garbage-First，为什么叫这个名字，呆会儿会详细说明。鉴于 CMS 的一些不足之外，比如: 老年代内存碎片化，STW 时间虽然已经改善了很多，但是仍然有提升空间。G1 就横空出世了，它对于 heap 区的内存划思路很新颖，有点算法中分治法“分而治之”的味道。

如下图，G1 将 heap 内存区，划分为一个个大小相等（1-32M，2 的 n 次方）、内存连续的 Region 区域，每个 region 都对应 Eden、Survivor 、Old、Humongous 四种角色之一，但是 region 与 region 之间不要求连续。

注：Humongous，简称 H 区是专用于存放超大对象的区域，通常 >= 1/2 Region Size，且只有 Full GC 阶段，才会回收 H 区，避免了频繁扫描、复制 / 移动大对象。

所有的垃圾回收，都是基于 1 个个 region 的。JVM 内部知道，哪些 region 的对象最少（即：该区域最空），总是会优先收集这些 region（因为对象少，内存相对较空，肯定快），这也是 Garbage-First 得名的由来，G 即是 Garbage 的缩写， 1 即 First。

G1 Young GC

young GC 前：

young GC 后：

理论上讲，只要有一个 Empty Region（空区域），就可以进行垃圾回收。

由于 region 与 region 之间并不要求连续，而使用 G1 的场景通常是大内存，比如 64G 甚至更大，为了提高扫描根对象和标记的效率，G1 使用了二个新的辅助存储结构：

Remembered Sets：简称 RSets，用于根据每个 region 里的对象，是从哪指向过来的（即：谁引用了我），每个 Region 都有独立的 RSets。（Other Region -> Self Region）。

Collection Sets ：简称 CSets，记录了等待回收的 Region 集合，GC 时这些 Region 中的对象会被回收（copied or moved）。

RSets 的引入，在 YGC 时，将年青代 Region 的 RSets 做为根对象，可以避免扫描老年代的 region，能大大减轻 GC 的负担。注：在老年代收集 Mixed GC 时，RSets 记录了 Old->Old 的引用，也可以避免扫描所有 Old 区。

 

8 ZGC （截止目前史上最好的 GC 收集器）

在 G1 的基础上，做了很多改进（JDK 11 开始引入）

3.8.1 动态调整大小的 Region

G1 中每个 Region 的大小是固定的，创建和销毁 Region，可以动态调整大小，内存使用更高效。

3.8.2 不分代，干掉了 RSets

G1 中每个 Region 需要借助额外的 RSets 来记录“谁引用了我”，占用了额外的内存空间，每次对象移动时，RSets 也需要更新，会产生开销。

注：ZGC 没有为止，没有实现分代机制，每次都是并发的对所有 region 进行回收，不象 G1 是增量回收，所以用不着 RSets。不分代的带来的可能性能下降，会用下面马上提到的 Colored Pointer && Load Barrier 来优化。

3.8.3 带颜色的指针 Colored Pointer

这里的指针类似 java 中的引用，意为对某块虚拟内存的引用。ZGC 采用了 64 位指针（注：目前只支持 linux 64 位系统），将 42-45 这 4 个 bit 位置赋予了不同的含义，即所谓的颜色标志位，也换为指针的 metadata。

finalizable 位：仅 finalizer（类比 c++ 中的析构函数）可访问；

remap 位：指向对象当前（最新）的内存地址，参考下面提到的 relocation；

marked0 && marked1 位：用于标志可达对象；

这 4 个标志位，同一时刻只会有 1 个位置是 1。每当指针对应的内存数据发生变化，比如内存被移动，颜色会发生变化。

3.8.4 读屏障 Load Barrier

传统 GC 做标记时，为了防止其它线程在标记期间修改对象，通常会简单的 STW。而 ZGC 有了 Colored Pointer 后，引入了所谓的读屏障，当指针引用的内存正被移动时，指针上的颜色就会变化，ZGC 会先把指针更新成最新状态，然后再返回。（大家可以回想下 java 中的 volatile 关键字，有异曲同工之妙），这样仅读取该指针时可能会略有开销，而不用将整个 heap STW。

3.8.5 重定位 relocation

如上图，在标记过程中，先从 Roots 对象找到了直接关联的下级对象 1，2，4。

然后继续向下层标记，找到了 5，8 对象， 此时已经可以判定 3，6，7 为垃圾对象。

如果按常规思路，一般会将 8 从最右侧的 Region 移动或复制到中间的 Region，然后再将中间 Region 的 3 干掉，最后再对中间 Region 做压缩 compact 整理。但 ZGC 做得更高明，它直接将 4，5 复制到了一个空的新 Region 就完事了，然后中间的 2 个 Region 直接废弃，或理解为“释放”，做为下次回收的“新”Region。这样的好处是避免了中间 Region 的 compact 整理过程。

最后，指针重新调整为正确的指向（即：remap），而且上一阶段的 remap 与下一阶段的 mark 是混在一起处理的，相对更高效。

Remap 的流程图如下：

3.8.6 多重映射 Multi-Mapping

这个优化，说实话没完全看懂，只能谈下自己的理解（如果有误，欢迎指正)。虚拟内存与实际物理内存，OS 会维护一个映射关系，才能正常使用。如下图：

zgc 的 64 位颜色指针，在解除映射关系时，代价较高（需要屏蔽额外的 42-45 的颜色标志位）。考虑到这 4 个标志位，同 1 时刻，只会有 1 位置成 1（如下图），另外 finalizable 标志位，永远不希望被解除映射绑定（可不用考虑映射问题）。

所以剩下 3 种颜色的虚拟内存，可以都映射到同 1 段物理内存。即映射复用，或者更通俗点讲，本来 3 种不同颜色的指针，哪怕 0-41 位完全相同，也需要映射到 3 段不同的物理内存，现在只需要映射到同 1 段物理内存即可。

3.8.7 支持 NUMA 架构

NUMA 是一种多核服务器的架构，简单来讲，一个多核服务器（比如 2core），每个 cpu 都有属于自己的存储器，会比访问另一个核的存储器会慢很多（类似于就近访问更快）。

相对之前的 GC 算法，ZGC 首次支持了 NUMA 架构，申请堆内存时，判断当前线程属是哪个 CPU 在执行，然后就近申请该 CPU 能使用的内存。

小结：革命性的 ZGC 经过上述一堆优化后，每次 GC 总体卡顿时间按官方说法 <10ms。注：启用 zgc，需要设置 -XX:+UnlockExperimentalVMOptions -XX:+UseZGC。