第三章 垃圾收集器与内存分配策略

3.3 垃圾收集算法

分代假说

从如何判定对象消亡的角度，垃圾收集算法可以分为两大类：「引用计数式垃圾收集」和「追踪式垃圾收集」，主流 Java 虚拟机都采用第二种。

分代垃圾收集理论基于三个假设：

1. 弱分代假说：大部分对象都是朝生夕死
2. 强分代假说：活过越多次垃圾回收的对象越不容易被回收
3. 跨代引用假说：跨代引用相对于同代引用来说占比极少

因此应当将内存划分为不同区域，根据对象存活过的回收年龄放到不同区域，适用不同的回收算法，对象间即使存在跨代引用，也是极少数，不需要扫描整个老年代，只需要通过记忆集存储即可。泛泛而论，大部分对象位于新生代，适用标记-复制算法回收，熬过多轮回收的对象位于老年代，适用标记-整理算法。

标记-清除算法

最初始、最基本的追踪式垃圾回收算法，先标记出需要回收的对象，然后清除，相应内存位置变为可用状态。容易产生内存碎片。

标记-复制算法

简称为复制算法，为了解决内存碎片问题，留出一半空间不使用，开始回收内存时，先标记，然后将不可回收对象复制到未使用空间，另外一半空间直接清除。时间效率高，但是浪费一半空间。

基于 IBM 一项研究，新生代对象 98% 都可以在第一次垃圾回收时被回收掉，因此可以降低空间浪费，hotspot 虚拟机中，新生代分为 eden、s0、s1 三个区域，大小比例为 8:1:1 空间浪费由 50% 降低为 10%。新生成对象先进入 eden 区，s0, s1 两个区域总有一个保持未使用状态，假设开始垃圾回收时，s1 未使用，将不可回收对象放入 s1，然后清除 eden 和 s0。如果 s1 不够用，就放入老年代。

标记-整理算法

如果存活对象过多，比如老年队，标记-复制算法的效率就会显而易见降低。而且，如果不想浪费 50% 空间，就必须有另外的担保空间，在 s0 或 s1 区域不够放时接住对象。

在标记-清除算法基础上改进，标记完毕后，不是直接清除可回收对象，而是将存活对象移动到内存区域一端，然后将剩下的区域清除，相当于做了个整理操作。

移动存活对象，垃圾回收过程会复杂，执行效率低，并且需要 stop the world，不移动存活对象，由于内存碎片，内存分配过程会复杂。但是总体而言，还是移动存活对象会使得整个内存使用的吞吐量更高。关注低延迟的 CMS 是基于标记-清除算法，关注总吞吐量的 Parallel Scavenge 是基于标记-整理算法。内存碎片过多时，CMS 会触发一次内存整理。

3.4 Hotspot 虚拟机的算法细节实现

枚举根节点

GC Roots 遍历需要 stop the world，因此要尽可能快，由于 Java 虚拟机主流基本都使用准确式内存管理，即记录了内存中数据类型，因此使用 (Ordinary Object Pointer)OOPMap 数据结构记录对象引用就可以快速拿到所有 GC Roots。

安全点与安全区域

指令中记录了 OOPMap 的地方称为安全点，程序只有执行到安全点才可以进行垃圾收集。安全区域是为了避免未执行到安全点就挂起的用户程序不 block 垃圾收集而设置的。对于不进行对象引用修改的指令块，就称为安全区域。

当要进行垃圾收集时，有两种方式让用户程序来到安全点：抢占式中断和主动中断，主流 java 虚拟机都采用主动中断。

• 抢占式中断：不需要用户程序主动配合，系统首先中断所有程序，然后检查有没在安全点的程序，让它继续执行一会儿后重新中断，直到来到安全点
• 主动中断：垃圾收集需要中断线程时，不直接操作用户程序，只设置标志位，用户程序自己轮询标志位，然后主动跑到安全点后主动挂起
  • 标志位的设置与轮询是通过内存陷阱方式实现，需要中断时，系统将位于的内存页 0x160100 设置为不可访问，用户程序访问这个位置时产生错误中断，进入中断处理程序，中断处理程序中预先注册好中断线程进入挂起等待

记忆集与卡表

分区域垃圾回收都要面临的一个问题是，不同区域之间的对象之间存在引用的情况如何解决。一种解决思路是，收集其中一个区域时，记录下被其他区域引用的对象，这个记录就被称为记忆集，记忆集是一种抽象的逻辑概念，卡表则是一种具体的实现方式。

首先，不需要记录对象，只需要记录其他区域的某个内存块范围内，是否有当前区域的对象引用即可。其次，内存块范围的粒度可大可小，卡表取的是 512 字节，这样一个 512 字节的内存块称为卡页。当检查到某个卡页内有指向当前垃圾收集区域的引用时，标记为 dirty，最后把所有 dirty 的卡页指向的内存和 GC Roots 一起，作为垃圾收集起点。

卡表更新是通过写屏障，类似于 CPU/缓存 层面的 AOP，更新引用时会自动插入一条指令更新卡表

可达性分析

拿到 GC Roots 后，还需要遍历对象引用链进行标记，这个时间复杂度和堆内存大小成正比，因此 stop the world 是无法接受的。而程序和收集器并发执行会引入的问题，是程序修改引用后会导致「对象消失」问题，有理论证明，只有同时满足以下两个条件时会出现「对象消失」：

• 修改黑色节点指向白色节点
• 修改灰色节点删除所有指向白色节点的引用

因此只要打破以上两种情况之一，就可以在执行遍历 GC Roots 对象引用链时用户程序也并发执行。

打破条件一的方式被称为增量式更新(Incremental Update)，即当用户程序打算把黑色节点指向白色节点时，将黑色节点记录下来，等并发遍历结束后再扫描一遍记录的黑色节点；相当于黑色对象一旦插入了白色节点的引用，就变回灰色节点了。

打破条件二的方式被称为原始快照(Snapshot At The Beginning SATB)，发现灰色节点要删除指向白色节点的引用关系时，先记录下这个要删除的引用关系，等并发扫描结束后将记录中的灰色节点作为根节点重新扫描一次；相当于，第一次扫描时，无论引用关系删除与否，都按照开始扫描时的对象图快照进行搜索。

引用关系的插入和删除，虚拟机都是通过写屏障实现的。

CMS 是基于增量更新来做并发标记，G1 和 Shenandoah 是用原始快照

3.5 经典垃圾收集器

介绍了 Serial (Old), ParNew, Parallel Scavenge, CMS, G1 这几款垃圾收集器

面向新生代的垃圾收集器：Serial，ParNew，Parallel Scavenge

面向老年代的垃圾收集器：CMS，Serial Old，Parallel

G1 不区分新生代、老年代

hotspot 曾经提出过一个（不够成熟的）垃圾回收的实现框架，由于现存的垃圾收集器有的实现了这个框架，有的没有实现，导致不是所有垃圾收集器可以搭配使用。其中搭配情况如下图所示：

HotSpot虚拟机的垃圾收集器使用搭配

在看一个垃圾收集器时会关注的点：

1. 适用的分代，使用的垃圾收集算法
2. 阶段划分，每个阶段具体做什么事情
3. 每个阶段的垃圾收集是单线程还是多线程并行执行，是否可以和用户程序并发执行
4. 如果不能并发，停顿时间是否和堆大小相关
5. 如果可以并发，对用户程序吞吐量的影响
6. 垃圾收集线程本身需要占用的额外内存（Memory Footprint）大小

3.5.1 Serial 垃圾收集器

1. 适用于新生代，使用的标记-复制算法
2. 标记复制阶段都是单线程执行，并且都需要暂停用户程序，
3. 停顿时间和管理的堆大小正相关
4. 占用的额外内存最小

Serial 收集器运行示意图

Serial 是HotSpot虚拟机运行在客户端模式下的默认新生代收集器，

• 是所有垃圾收集器里占用额外内存最小的
• 单线程执行，避免了线程切换的开销，尤其是运行在单核机器上的时候

3.5.2 ParNew 收集器

可以看作 Serial 收集器的多线程版本，是很多服务器模式的默认新生代收集器，默认并行线程数和机器核数相同，可以通过参数 -XX：ParallelGCThreads 进行限制。

1. 适用于新生代，与 Serial 收集器相同都是用的标记-复制算法
2. 与 Serial 相同，需要暂停用户程序，不过收集线程是多线程并行的
3. 停顿时间和管理的堆大小正相关

JDK9 后，只能与 CMS 搭配使用，面临被淘汰的命运。

ParNew 收集器运行示意图

垃圾收集语境下，并行与并发的区别：

• 并行（Parallel）：并行描述的是多条垃圾收集器线程之间的关系，说明同一时间有多条这样的线程在协同工作，通常默认此时用户线程是处于等待状态。
• 并发（Concurrent）：并发描述的是垃圾收集器线程与用户线程之间的关系，说明同一时间垃圾收集器线程与用户线程都在运行。由于用户线程并未被冻结，所以程序仍然能响应服务请求，但由于垃圾收集器线程占用了一部分系统资源，此时应用程序的处理的吞吐量将受到一定影响。

3.5.3 Parallel Scavenge 收集器

吞吐量优先的收集器，与 ParNew 类似，是多线程、使用复制算法，但是提供参数可以让用户控制吞吐量，并且提供自适应调整策略，细节参数可以由虚拟机根据运行时状态自动调整。

1. 适用于新生代，使用复制算法
2. 与 ParNew 相同，需要暂停用户程序，收集线程是多线程并行
3. 停顿时间和管理的堆大小正相关

吞吐量定义：

吞吐量=用户程序运行时间 / (用户程序运行时间+垃圾收集运行时间)

吞吐量就是处理器用于运行用户代码的时间与处理器总消耗时间的比例。高吞吐量适合离线的计算密集型任务。

Parallel Scavenge 提供的用于控制吞吐量的参数：

• -XX:MaxGCPauseMills : 最大垃圾收集停顿时间，如果设置过小，反而会导致吞吐量降低，因为收集器会通过缩小新生代内存大小来实现，这样就会导致频繁的 GC
• -XX:GCTimeRatio : 吞吐量大小。0-100 的数，默认 99，允许垃圾收集时间占总时间的 1% = 1/(1+99)

开启自适应调整策略的参数：

• -XX:+UseAdaptiveSizePolicy : 虚拟机根据系统运行状态收集监控信息，动态调整细节参数，比如新生代大小、 Eden 和 survivor 比例、进入老年代对象大小等，用户只需要设置好整体的参数，比如最大堆、吞吐量大小，其余的交给虚拟机自动调整即可。

3.5.4 Serial Old 垃圾收集器

Serial 收集器的老年代版本，主要在客户端模式使用。

1. 适用于老年代，使用标记-整理算法
2. 单线程收集，需要暂停用户程序
3. 停顿时间和管理的堆大小正相关

如果是服务器模式，则

• 用于和 Parallel Scavenge 搭配使用（其实是 PS MarkSweep，但是实现和 SerialOld 基本一样）
• CMS 发生 Concurrent Mode Failure失败时的后备预案，提供内存回收支持

3.5.5 Parallel Old 收集器

JDK6 引入，是 Parallel Scavenge 的老年代版本，在注重高吞吐量或资源较为紧缺的情况可以优先考虑使用 Parallel Scavenge+Parallel Old 搭配

1. 适用于老年代，标记-整理算法
2. 多线程收集，需要暂停用户程序
3. 停顿时间和管理的堆大小正相关

Parallel Scavenge + Parallel Old 收集器运行示意图

3.5.6 CMS 收集器

CMS(Concurrent Markup Sweep)是低延迟优先的收集器，首个支持和用户程序并发执行垃圾收集的收集器，适合作为 B/S 模式的 web 后端的垃圾收集器。

1. 适用于老年代，使用标记-清除算法
2. 分阶段执行
   1. 初始标记(CMS initial Mark)，标记 GC Roots，需要暂停用户程序，单线程执行，执行时间与堆大小无关
   2. 并发标记(CMS concurrent Mark)，遍历对象引用图进行可达性分析做标记，和用户程序并发执行，采用增量更新算法保证与用户程序互不干扰，执行时间与堆大小正相关，会对用户程序吞吐量产生影响
   3. 重新标记(CMS remark)，修正并发标记阶段的错误标记，需要暂停用户程序，比初始标记时间略长，但远小于并发标记时间
   4. 并发清理(CMS concurrent sweep)，将标记为可回收的对象清除，由于不需要移动对象，因此可以和用户程序并发执行，会对用户程序吞吐量产生影响

CMS 收集器运行示意图

CMS 收集器的缺点：

1. 基于标记-清理算法，会产生大量内存碎片
2. 由于并发标记时，用户程序同时在运行，会产生新的垃圾，称为「浮动垃圾」，只能在下次 GC 时才可以被回收
3. 由于并发清理是和用户程序同时运行的，因此需要给用户程序预留内存，不能等内存告急才触发 GC
4. 如果触发 GC 时，内存预留不够，就会发生用户程序申请新的大对象时内存不够用的情况，称为 Concurrent Mode Failure，此时需要回退到 Serial Old，性能急剧下降
5. CMS 的并发标记和并发清理和用户程序并发执行，势必会与用户程序争抢资源，造成用户程序吞吐量下降，执行时间变长

3.5.7 G1 收集器

G1 是 Garbage First 的简称，将 Java 堆划分为多个相同大小的 region 区块，每个 region 都可以根据需要扮演新生代、老年代的角色。收集线程维护待回收的 region 块以及回收它们可获得的收益（可释放空间），形成一个优先队列，根据用户设置的停顿时间，优先回收收益最大的 region，因此称为 Garbage First 收集器。

G1 基于 region 的内存布局

用户可以通过设置不同的停顿时间，使得 G1 收集器在吞吐量或延迟时间上表现更优秀，JDK9 以后，G1 替代 Parallel Scavenge + Parallel Old 成为服务器模式下默认的垃圾收集器，CMS 也被标记为 Deprated。

1. 基于 region 的内存布局，新生代和老年代都会管理，整体看是标记-整理，局部看是标记-复制算法
2. 可以粗略地将回收分为以下阶段：
   1. 初始标记
   2. 并发标记
   3. 最终标记
   4. 筛选回收：更新 region 的统计数据，对各个 region 的回收收益与成本进行排序，根据用户设置的停顿时间制定回收计划，选择任意个 region 构成回收集，然后把决定回收的那一部分 region 的存活对象复制到空 region 内，然后将旧 region 统一清空。由于有对象移动，需要暂停用户程序，多个收集线程并行执行。
3. 前三个阶段与 CMS 类似，不过并发标记的可达性分析阶段，是通过快照方式避免和用户程序互相影响，而 CMS 是通过增量更新方式
4. 基于 region 的内存布局，需要通过记忆集保存跨 region 的引用，需要的额外内存很大，占到管理的 Java 堆的 10%~20%

从 G1 开始，不再追求一次把整个 Java 堆全部清理干净，而是维持一个内存申请和回收的动态平衡，只要回收的速度跟得上申请速度就 OK。

G1 与 CMS 相比：

• G1 不会产生内存碎片
• G1 的额外内存占用和运行负载都要比 CMS 高

不过总的来说，G1 还是要替代 CMS 的。G1 的目标是，在延迟可控的前提下，提供尽可能高的吞吐量。

3.6 低延迟垃圾收集器

衡量垃圾收集器的三项最重要的指标：吞吐量(Throughput)、延迟(Latency)和内存占用(Footprint)，三个指标不可能全部达到很好的效果，CPU 性能越来越好，收集器对吞吐量带来的额外负担可以被抵消一些，存储越来越廉价，内存占用的问题也可以忍受，但是随着管理的 Java 堆越大，停顿时间越来越长，低延迟成为设计收集器时最受关注的点。

介绍了 Shenandoah 和 ZGC 这两款以低延迟为首要目标的垃圾收集器。

3.6.1 Shenandoah 收集器

Shenandoah 收集器的目标是，在任何堆内存大小下都可以把垃圾收集的停顿时间限制在十毫秒以内（未达成）。

Shenandoah 设计思想与 G1 一脉相承，基于 region 的堆内存布局，在初始标记、并发标记等许多阶段的处理思路上高度一致，甚至还共享了一部分代码；但是和 G1 不同，Shenandoah 的 region 不区分新生代或老年代，而且引入 Brooks Pointer 使得对象清理可以和用户程序并发执行，摒弃了 G1 中的记忆集，改用「连接矩阵」的全局数据结构来记录跨 region 的对象引用。

1. 基于 region 的内存布局，新生代和老年代都会管理，整体看是标记-整理，局部看是标记-复制算法
2. 执行阶段划分，其中关键阶段是并发标记、并发回收、并发更新引用：
   1. 初始标记(Init Mark): 标记 GC Roots，执行时间与堆大小无关，需要暂停用户程序
   2. 并发标记(Concurrent mark): 遍历对象引用图，标记出全部可达对象，执行时间与堆大小正相关，与用户程序并发执行
   3. 最终标记(Final Mark): 修正并发标记阶段由于用户程序修改导致的错误标记，并统计出回收价值最高的 region 构成回收集(Collection Set)，需要暂停用户程序
   4. 并发清理(Concurrent Cleanup): 清理整个区域内没有任何存活对象的 region
   5. 并发回收(Concurrent evacuation): 把回收集里的存活对象复制到其他未被使用的 region 中，通过读屏障和 Brooks pointer 解决与用户程序并发执行时的并发访问问题
   6. 初始引用更新(Init-UR): 线程集合点，确保回收阶段的收集线程已经完成对象移动任务，需要暂停用户程序
   7. 并发引用更新(Concurrent update refs): 把堆中所有指向旧对象的引用修改为复制后的地址，与用户程序并发执行，与并发标记不同，不需要遍历对象引用图，只需要线性查询堆内存，将其中的引用类型里指向旧对象的引用改为新对象
   8. 最终引用更新(Final-UR): 修正存在于 GC Roots 中的对象引用，需要暂停用户程序，停顿时间与 GC Roots 数量相关
   9. 并发清理(Concurrent Cleanup): 存活对象移动完毕后，整个回收集不再有存活对象，清理回收集中的 region 以供新对象分配使用

图中，蓝色是用户程序可用用来分配对象的 region，绿色是标记的存活对象，黄色表示选入回收集的 region

虽然延迟低，但是由于每次对象访问时需要通过内存屏障走转发指针，导致吞吐量也大幅降低

3.6.3 ZGC 收集器

Z Garbage Collector，JDK11 新加入的，实验性质的低延迟收集器，目标与 Shenandoah 高度类似：在对吞吐量影响不大的情况下，将任意堆大小的垃圾收集停顿时间控制在十毫秒以内。

ZGC 的设计思想与 Azul 的 PGC (Pauseless GC)及 C4(Concurrent Continously Compacting Collector) 雷同，关键点在于通过染色指针将对象的引用信息（比如三色标记）记录在指向对象的指针上，不需要访问对象，就可以拿到对象的引用信息。

ZGC 内存布局也是基于 region，但是与 G1 以及 Shenandoah 不同，ZGC 的 region 是动态分配的，在 x86/64 架构上，有小、中、大三种类型 region，分别用于分配不同大小对象

1. 基于 region 的内存布局，不分代，管理全堆，并发标记-整理算法
2. 执行阶段划分：
   1. 并发标记(Concurrent Mark): 遍历对象图做可达性分析的阶段，与 G1、Shenandoah 类似也要经历初始标记、最终标记的前后停顿，不同的是，ZGC 的标记是在指针而不是对象上，更新染色指针的 Marked 0、Marked 1 标志位
   2. 并发预备重分配(Concurrent Prepare for Reloc.)：统计出本次收集需要清理的 region 组成重分配集，与 G1 只回收记忆集中的 region不同，ZGC 的回收标记是针对全堆的，重分配集只是记录了需要移动存活对象的 region。另外 JDK12 中支持的类卸载以及弱引用的处理也是在这个阶段完成的
   3. 并发重分配(Concurrent Relocate)：核心功能执行阶段。把重分配集中的存活对象移动到其他 region，并为重分配集中的每个 region 维护一个转发表（forward table）用于指针自愈，一旦某个 region 存活对象移动完毕，当前 region 就可以被释放用于新对象的分配，但是转发表需要保留。
   4. 并发重映射(Concurrent Remap)：修正整个堆中指向重分配集中旧对象的所有引用，与 Shenandoah 中的并发引用更新目标相同，但是由于 ZGC 的指针自愈能力，这一步的执行优先级并不高，因此和下一轮 GC 的并发标记合并执行。

ZGC 指针**自愈(Self-Healing)**能力：如果用户线程访问已经移动的对象，就会陷入内存屏障，然后根据 region 中的转发表记录访问到复制后的地址，并更新引用指向最新地址。

ZGC 优点：

• 借助于染色指针自愈技术，不需要每次对象访问都陷入内存屏障或转发指针，提高程序吞吐量
• 同样借助于染色指针，当一个 region 中的存活对象移动完毕后就可以进行回收，不需要等到所有 region 整理完毕

ZGC 缺点：

• 由于不分代，对于新生代中快速消亡的对象和老年代中的对象一视同仁，浮动垃圾不能及时回收，支持的对象分配速率相较于分代回收比较低
• 由于使用染色指针占用了 4 位地址，最大可管理堆内存为 4TB

3.7.1 Epsilon 收集器

在垃圾收集上无作为的收集器，主要用途

1. RedHat 提出将垃圾收集行为统一的接口，即 JEP 304 提案，Epsilon 收集器就是这个接口的有效性验证和参考实现
2. 可以用于需要剥离收集器影响的性能测试和压力测试
3. 对于运行时间很短，整个运行期间不会耗尽堆内存的程序，无需进行垃圾收集，就可以使用 Epsilon 收集器，减轻系统负载

垃圾收集器除了回收内存，还需要兼顾其他工作：

• 堆的管理与布局
• 对象的分配
• 与解释器的协作
• 与监控子系统协作等

其中前两项是最小化垃圾收集器也必须实现的功能

参考：

[1]. Our Collectors

[2]. G1: One Garbage Collector To Rule Them All

[3]. Shenandoah GC - Part I: The Garbage Collector That Could

[4]. The Z Garbage Collector Low Latency GC for OpenJDK