Java JVM

[Java] JVM垃圾回收-G1收集器

Garbage First Collector 详细解析

Posted by Penistrong on January 31, 2023

G1收集器

G1收集器(Garbage First Collector)是面向服务器的垃圾收集器，在多CPU和大内存场景下具备优秀性能，HotSpot VM开发团队赋予G1收集器的使命是替换掉CMS收集器，自JDK1.7提出，而在JDK17中G1已成为默认的垃圾收集器

java -XX:+PrintCommandLineFlags -version

# Output
... -XX:+UseG1GC ...

Region划分

其他收集器的收集范围只能是整个新生代或者老年代，而G1可以直接对新生代与老年代一起回收，这是因为G1将堆划分为多个大小相等的独立区域(Region)，从G1的角度上新生代和老年代不再物理隔离，进行的是混合回收(Mixed GC)

引入Region的概念后将整块内存空间划分为许多小空间，每个Region都可以单独进行GC，这使得进行GC时可以对停顿时间进行预测。通过记录每个Region的垃圾回收时间以及回收所获得的空间，G1在后台维护了一个优先队列，每次将允许收集时间作为上限，优先去回收价值最大的Region，这也是其名字Garbage First的由来

G1收集器-堆分配

除了Eden、Survivor和Tenured之外，还有一类特殊的Humongous Region，专门用来存储大对象。

每个Region的容量可以通过参数-XX: G1HeapRegionSize(取值范围为 $2^N \in [1, 32]$ MB)设定。G1收集器将大小超过了Region容量的一半的对象判定为大对象，存放在Humongous Region区域里，而对于大小超过了整个Region容量的超级大对象，将会用连续的Humongous Region存储该对象。G1执行垃圾回收的时候，大多数情况下都把Humongous Region视作老年代的一部分来处理。

每个Region都有一个Remembered Set，用来记录引用该Region中对象的引用对象所在的Region，这样就能够向上溯源形成引用链，在可达性分析阶段能够避免全堆扫描，见RSet原理一节

垃圾回收周期

G1-回收周期概览

从G1的整体垃圾回收周期的角度上看，G1收集器在Young-only与Space Reclamation这两个阶段不断切换，图中蓝点是新生代GC，红点是混合GC

  1. Young-only阶段: 该阶段会执行新生代GC并逐渐将超过晋升年龄阈值的对象晋升到老年代中，当老年代的空间占用超过初始设置的堆占用阈值时，G1就会执行被称为”Concurrent Start”(并发启动)的新生代GC

    • 并发启动: 在执行普通的新生代GC的同时并发启动标记过程，并发标记会标记能够在接下来的空间回收阶段里存活下来的所有位于老年代Region里的可达对象。并发标记还没完成时，普通新生代GC(采用复制算法)可能会并发运行，所以还需要2个需要停顿(STW)的再标记和清理阶段以完成对象标记工作

    并发启动其实包含初始标记和并发标记两个流程，见下一节垃圾回收流程

  2. Space-reclamation阶段: 空间回收阶段会对新生代和老年代的Region进行多次Mixed GC，当G1发现若继续清除老年代对象却不会释放更多空间时就会结束该阶段

空间回收阶段结束后，G1会从Young-only阶段重新开始新的周期。如果在分析对象存活性时出现OOM错误，G1会直接执行一次Full GC(与其他垃圾收集器的缺省操作一致)

垃圾回收流程

G1收集器-工作流程

上图描述了G1收集器的工作流程，G1收集器进行GC时有两种大致策略，一种是只进行Young GC，一种是进行Mixed GC。其中混合回收阶段需要全局并发标记(Global Concurrent Marking)这个较为复杂的流程以标记所有需要清理的对象，最后再使用宏观上的复制算法清理垃圾

全局并发标记 Global Concurrent Marking

  1. 初始标记(STW): 从GC Roots出发仅标记全部直接子节点，该阶段与新生代GC同步进行，且是STW的，该阶段可以和Young GC同步进行(利用了Young GC对GC Roots直接子节点的标记)

    标记可达对象时，会修改TAMS指针(Top At Mark Start)，使得下一步并发标记阶段中并发执行的用户线程能够正确地在可用的Region中分配新对象。

    G1为每一个Region区域设计了2个TAMS指针：PrevTAMS和NextTAMS，同时还有个BitMap位数组用于标记内存中对象的状态，见下面详细解析。

  2. 并发标记: 从GC Roots开始对堆中所有对象执行可达性分析，找出存活对象，并发标记耗时很长，但该阶段不是STW的，用户线程也在同时工作

  3. 再标记(STW): 修复并发标记阶段因用户线程工作而导致标记发生变动的对象的标记记录，JVM会将这段时间的对象变化记录在线程的Remembered Set Logs里，该阶段会将日志里的数据合并到Remembered Set中，需要停顿，但可并行运作多个GC线程

  4. 清理(STW): 清点出有存活对象的Region和无存活对象的Region，需要停顿，但该阶段仅执行统计而不会清理垃圾也不会复制存活对象，还会决定是否真的要开启空间回收阶段，如果确实要进入空间回收阶段，还会再执行一次新生代GC(作为后续混合GC的准备工作)

TAMS指针和Bitmap位数组在标记过程中起到了非常大的作用，G1收集器原论文中提出的并发标记流程图如下所示

Implict marking via TAMS variables

变量 释义
PrevTAMS 上一次并发标记阶段的结束地址
NextTAMS 当前并发标记阶段的结束地址
PrevBitmap 记录上一次并发标记阶段位于两个TAMS限制的内存区域中对象的状态(即上一阶段的NextBitmap)
NextBitmap 标记当前并发标记阶段位于两个TAMS限制的内存区域中对象的状态

  • 初始标记阶段，将上一阶段NextBitmap复制到PrevBitmap中，同时将NextTAMS指针挪到Top位置，重置NextBitmap的长度为 NextTAMS - Bottom，其中Bottom就是当前Region下限的内存地址

  • 并发标记阶段(上图没有画出，在Remark再标记阶段之前)，由于用户线程也在运行，会不断地为新的对象分配内存，此时Top指针会向前移动以保证指向所有包含对象的内存区域上限。

    同时，G1也在使用可达性分析标记 [Bottom, NextTAMS] 区域中的存活对象，并在NextBitmap中将相应数位置为1。该阶段结束后，[NextTAMS, Top] 区域中存在的是用户线程分配的新对象

  • 再标记阶段，利用三色标记法和SATB方法将并发标记阶段中发生变动的对象重新标记，清理SATB Buffer（见SATB解决漏标多标一节

  • 清理阶段，根据NextBitmap里的标记结果清理内存(并没有实际清除，只是打上标记)，之后将PrevTAMS指向当前的NextTAMS，同时NextTAMS重置到Bottom位置，完成该轮全局并发标记

回收 Evacuation

G1收集器会对各个Region按照回收价值和回收时间成本进行排序，根据用户期望的GC停顿时间来制定回收计划。该阶段是STW的

本可以与用户线程一起并发执行，这是因为只有部分Region需要回收且回收时间上限由用户控制，选择停顿用户线程专门进行回收能够大幅提升收集效率

G1基于本次的回收类型(Young GC / Mixed GC)选定回收集合 Collection Set(CSet)：

  • Young GC：CSet包含所有属于新生代的Region
  • Mixed GC：CSet包括所有新生代的Region和全局并发标记阶段得到的老年代中收益最高的Region

使用复制算法完成回收，将Region里存活的对象复制到其他空闲的Region中，然后直接清空对象原来所在的Region

三色标记原理

从GC Roots开始执行可达性分析时，按照对象是否被访问过这个条件将引用链上的对象标记成黑、灰、白三种颜色:

  • 黑色：可达性分析初始时，将GC Roots根对象标记为黑色，在后面的扫描里，如果某个对象及其直接儿子被扫描过，则将该对象标记为黑色

  • 灰色：某对象本身被扫描过，但是它至少还存一个对其他对象的引用没有被扫描，将该对象标记为灰色

  • 白色：未被扫描的对象都被标记为白色，当执行完整个可达性分析过程后，剩余的白色对象即为不可达对象，需要清除

每一趟分析都是从灰色节点出发，将其直接子儿子标记为黑色，并将当前灰色节点标记为黑色，直到不存在任何灰色节点，只剩黑色与白色节点，其中黑色都是引用链上可达的节点，白色都是不可达节点

G1存在的问题

任何垃圾收集器都有它的局限性，只能分场景选择最适合的收集器，G1同样存在如下问题

并发标记问题

CMS和G1的并发标记过程中，GC线程和用户线程并发运行，且GC在使用可达性分析算法标记所有可达对象。但是用户线程会修改某些对象的引用链，这将导致两个问题:

漏标

经过可达性分析后的存活的对象成为了不可达对象，仿佛“对象消失”一般

三色标记的漏标问题

上图是漏标的一个例子，GC线程从根开始执行可达性分析，当它把B节点标记为灰色之后，在下一趟扫描前用户线程使用A.d = D, B.c = null断开了灰色对象B与白色对象C的引用，并给黑色对象A添加了白色对象D的引用

但是由于三色标记流程，下一趟只能从灰色节点开始扫描其可达子节点，而B到C的引用链已断开。完成可达性分析后，只有A、B、E节点被标记为黑色可达，本应该可达的D节点仍保持白色状态，导致本轮GC会对其进行回收，漏标直接影响了程序的正确性

Wilson等人于1994年理论证明，当且仅当以下2个条件成立时就会产生漏标问题：

  1. 赋值操作插入了一条或多条从黑色对象到白色对象的引用
  2. 赋值操作删除了全部的从灰色对象到该白色对象的直接或间接的引用

多标

将原本不可达的对象错误标记为存活，成为浮动垃圾，本轮GC过程中不会再对其进行回收

三色标记的多标问题

上图是多标的一个例子，分析到B节点并将其标记为灰色后，在下一趟扫描前用户线程使用A.b = null断开了对B的引用，照理说B节点应该是不可达对象了，但由于它已经被标记为灰色，下一趟扫描仍然会从B开始，导致多标的出现，B、C、D、E都成为了本轮GC无法清除的浮动垃圾

如果是在并发标记阶段开始后创建的新对象，直接将它们标为黑色，本轮不会再对它们执行清除。这些新对象有可能又会变为无引用指向的垃圾，也算作浮动垃圾的一部分!

跨代引用问题

新生代执行Minor GC的频率很高，如果老年代里的对象持有了新生代对象的引用，那么回收新生代时，就需要更新所有老年代对象对这些被挪动了的新生代对象的引用，导致要扫描整个老年代的对象，开销较大

G1解决问题的策略

基于弱三色不变式的SATB解决漏标问题

弱三色不变式的定义如下：

所有被黑色直接引用的白色对象都应该被灰色对象直接或间接的引用

对于漏标问题，如果要确保被黑色对象引用的白色对象不会被删除，就必须将其保护起来，添加的这层保护称为灰色保护(Grey Protected)，

弱三色不变式适用于非复制型垃圾回收器，因为回收器不需要修改存活对象的指针。注意，G1虽然在回收时确实是使用复制算法，但是在标记时是利用Bitmap标记，并不直接移动内存，所以适用

G1通过SATB(Snapshot At The Beginning，原始快照)解决并发标记过程中引用关系出现的变化，具体而言是利用写前屏障实现

在JVM针对漏标问题提出的读写屏障策略中，包含一个读屏障和两个写屏障：

通常称读屏障为pre_load_barrier，写操作的前后两个写屏障为pre_write_barrier和post_write_barrier

G1采用的就是”写引用”之前的写屏障pre_write_barrier

void pre_write_barrier(oop* field) {
   oop old_value = *field;    // 记录旧值
   remark_set.add(old_value); // 加入再标记集合中(相当于标记为灰色，不过要等到Remark阶段处理)
}

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

// 很像JDK动态代理，在反射得到Method执行invoke方法的前后插入pre和post操作完成切面

当灰色对象要删除指向白色对象的引用时，利用写前屏障记录引用旧值(记录旧值指向的白色对象)

比如，用户线程通过B.c = null想断开灰色对象B对白色对象C的引用，首先通过写前屏障记录该白色对象C，并将其加入remark_set中(注意该集合是哈希集合，自动去重)，相当于为该白色对象C裹上了一层”灰色保护”

本轮并发标记过程虽然不会直接扫描被”灰色保护”的对象，但是在并发标记的下一个阶段，即Remark再标记阶段，就会对remark_set中的所有对象执行可达性分析。同时，再标记阶段是STW的，用户线程停止运作，不会在可达性分析过程中又出现漏标的幺蛾子

当初研究到这里，我有一个疑问，如果有一个白色对象，在并发标记刚开始时就没有任何对象引用它，那么如果某个黑色对象突然增加了一条到该对象的引用，而G1只处理灰色到白色的删除，那不还是漏标了？

对于这个问题，仔细想想后就释然了: 如果一个白色对象，一开始就没有任何引用指向它，那么用户线程就不可能从任何地方获得对该白色对象的引用，那么也无法让黑色对象引用该白色对象

这也是原始快照的含义: 一旦初始快照中可达的引用关系改变，就记录下这些发生了改变的对象，对于初始快照中本来就不可达的，它们的引用关系不会再发生变化了，根本不用理会。即开始时是可达的，那么就认为其一定存活。原始快照破坏了Wilson提出的漏标条件2，保证不会漏标

显然，SATB会导致浮动垃圾增多，比如某个白色对象被断开后，并发标记阶段结束后它又没有被其他黑色对象引用，应该是需要被回收的垃圾，但是本轮无法对其回收，延迟到下一轮

Oracle官方文档对G1的SATB描述如下:

G1 GC uses the Snapshot-At-The-Beginning (SATB) algorithm, which takes a snapshot of the set of live objects in the heap at the start of a marking cycle. The set of live objects is composed of the live objects in the snapshot, and the objects allocated since the start of the marking cycle.

原始快照除了初始时存活的对象，还包括并发标记过程中由用户线程创建的新对象，新创建的对象默认就是存活的，具体可以看之前Region标记过程一节，[NextTAMS, Top]区间里分配的对象就是并发标记阶段里由用户线程新建的对象

题外话: CMS基于强三色不变式的增量更新解决漏标问题

与弱三色不变式对仗的强三色不变式是指

严格禁止黑色对象直接引用白色对象，保证永远不会存在黑色对象到白色对象的引用

CMS的并发标记过程中采用基于强三色不等式的增量更新(Incremental Update)算法：

与G1的SATB不同，增量更新是在引用发生变化后利用写后屏障，将新值记录下来

void post_write_barrier(oop* field, oop new_value) {
   if ($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
      remark_set.add(new_value); // 加入再标记集合，等到Remark阶段处理
   }
}

当黑色对象A新增了一条到白色对象D的引用时A.d = D，将白色对象D加入到remark_set标记栈中，等到Remark再标记阶段再扫描一次

这也是增量更新的含义: 记录的是可达性分析开始时初始引用关系的更新值，破坏了Wilson提出的漏标条件1，保证不会漏标

多标问题没有解决

多标问题尚没有好的解决方法，但至少浮动垃圾不会影响程序的正确性，所以将它们延迟到下一次GC时进行清理仍然是可以接受的

RSet解决跨代引用问题

RSet即Remembered Set，G1用RSet解决跨代引用问题，首先分析一下G1划分的各个Region之间可能存在的引用关系:

  1. Young Region(包括Eden和Survivor Region) 到 Young Region 的引用：每次GC时(包括Young GC 和 Mixed GC)都会回收整个新生代，新生代区域间的引用关系不用考虑，无需记录该引用

  2. Young Region 到 Old Region(包括Tenured和Humongous) 的引用：被新生代对象引用的老年代对象，并发标记时新生代的对象等会成为GC Roots，从根出发可以遍历到所有老年代，无需记录该引用

  3. Old Region 到 Young Region 的引用：被老年代对象引用的新生代对象，这个必须要记录

  4. Old Region 到 Old Region的引用：由于G1需要进行Mixed GC，且绝大多数时候它只会回收老年代的部分Region，在回收这些老年代对象时，必须要感知其他不在回收范围里的Region中是否存在其他老年代对象引用这些被回收的对象

出于以上考量，G1需要一张表记录老年代到新生代、老年代到老年代的引用，于是采用基于Point in方式的Remembered Set，通俗来说就是”谁引用了我”

而Rememered Set的具体实现中，其数据结构被称作PRT (Per Region Table)，这是一种动态数据结构，会根据记录引用的数量变化它的存储粒度，主要目的是处理超多对象引用导致RSet过大占据Region过多空间的问题

总结

G1收集器的特点总结如下:

  • 空间整合: G1整体上看是基于标记-整理算法实现的收集器，而从回收的局部性上看(Region之间)，G1会将需要回收的Region里的对象统统复制到空闲Region中，再对原来的Region执行回收，类似于复制算法，这样就避免了标记-清除算法带来的空间碎片问题

  • 可预测停顿: 用户能够明确指定在一个长度为$M$ms的时间片内，消耗在GC上的时间不得超过$N$ms，相比CMS可以控制用户线程的停顿时间上限

观察G1流程中存在STW的阶段:

  • 初始标记只需标记GC Roots的直接子节点，耗时较短
  • 再标记要处理的标记变动对象较少，耗时也较短
  • 清理阶段因为只负责清点Region有无存活对象，且Region数量也较少，耗时也较短
  • 复制时，由于要将所有存活对象复制到目标空闲Region，在这个阶段耗时是最长的

如果能够改进复制算法中转移对象的阶段，那么就可以减少耗时最长的停顿，这也是ZGC的诞生原因之一

Oracle官方建议G1收集器采用默认设置即可，G1会在期望停顿时间内尽力地完成垃圾回收工作，如果想要以高吞吐量为目标进行优化，可以修改JVM启动参数:

# 降低GC的期望停顿时间 默认是200ms
-XX: MaxGCPauseMillis

# 设置更大的堆空间
-Xmx

使用G1时不建议使用-Xmn、-XX:NewRatio等选项限制新生代大小，否则G1无法通过调整新生代大小以达到给定的停顿时间目标，限定新生代大小相当于禁用了G1的调整策略

CATALOG
    FEATURED TAGS
    毕业设计 Java JVM Spring RecSys Deep Learning LeetCode CV Spring Cloud
    FRIENDS