1.2.4 G1

从执行方式来看，垃圾回收器的发展经历了最初期的串行执行，到并行执行用于提高执行效率，再到目前主流的并发执行用于减少垃圾回收器停顿时间。第一款成熟的并发执行垃圾回收器是CMS。CMS是一款非常成功的垃圾回收器，是使用最多和最广的垃圾回收器，但是其复杂性（有上百个参数）给程序员的使用带来了不便，所以需要设计一款简单的垃圾回收器来替代CMS, G1应运而生。

G1是从JDK7 Update 4及后续版本开始正式提供的。G1致力于在多CPU和大内存服务器上对垃圾回收提供软实时目标（soft real-time goal）和高吞吐量（high throughput）。目前G1已经相当成熟，从众多的测评结果上看，也达到了G1最初的设计目标。从JDK 9开始G1作为默认的垃圾回收器，目前已经有不少公司开始在生产环境中逐步使用G1。

G1垃圾回收器的设计和前面提到的3种回收器都不同，在并行、串行以及CMS中针对堆空间的管理方式都是连续的，如图1-4所示。

连续的内存将导致垃圾回收时收集时间过长，停顿时间不可控。所以G1将堆拆成一系列的分区（heap region），这样在一个时间段内，大部分垃圾回收操作就只是针对一部分分区执行，而不是整个堆或整个（老年）代，从而满足在指定的停顿时间内完成垃圾回收的动作。G1内存分区如图1-5所示。

在G1里，新生代就是一系列的内存分区，这意味着不用再要求新生代是一个连续的内存块。类似地，老生代也是由一系列的分区组成。在JVM运行时，从内存管理角度不需要预先设置分区是老生代分区还是新生代分区，而是在内存分配时决定：当新生代需要空间时，则分区被加入新生代中；当老生代需要内存空间时，则分区被加入老生代中。事实上，G1通常的运行状态是：映射G1分区的虚拟内存随着时间的推移在不同的代之间切换。例如，一个G1分区最初被指定为新生代，经过一次新生代的回收之后，整个新生代分区都被划入待使用的分区中，那它既可以作为新生代分区使用，也可以作为老生代分区使用。很可能在完成一个新生代回收之后，一个新生代的分区在未来的某个时刻被用于老生代分区。同样，在一个老生代分区完成回收之后，它就成为待使用分区，在未来某个时候作为一个新生代分区使用。

G1新生代的回收方式是并行回收，采用复制算法。与其他JVM垃圾回收器一样，一旦发生一次新生代回收，整个新生代都会被回收。这就是我们常说的新生代回收（Young GC, YGC）。但是G1和其他垃圾回收器的不同之处在于：①G1会根据预测时间动态地改变新生代的大小；②G1老生代的垃圾回收方式与其他JVM垃圾回收器对老生代处理有着极大的不同。G1老生代的回收不会为了释放老生代的空间而对整个老生代进行回收。相反，在任意时刻只有一部分老生代分区会被回收，并且这部分老生代分区将在下一次增量回收时与所有的新生代分区一起被回收，这就是我们所说的混合回收（Mixed GC）。在选择老生代分区时，优先考虑垃圾多的分区。

老生代分区的选择涉及G1的并发标记算法，这个过程称为“并发标记阶段”。并发标记是指并发标记线程和应用程序线程同时运行，它有4个典型的子阶段：初始标记子阶段、并发标记子阶段、再标记子阶段和清理子阶段。

1．初始标记子阶段

负责标记所有从根集合直接可达的对象，根集合是对象图的起点，初始标记需要将应用程序线程暂停，也就是需要一个STW的时间段。在混合回收中的初始标记子阶段和新生代的初始标记几乎一样。实际上混合回收的初始标记子阶段是借用了新生代回收的结果，即新生代垃圾回收后的新生代Survivor分区作为根，所以混合回收一定发生在新生代回收之后，且不需要再进行一次初始标记。这就是所谓的“借道”。

2．并发标记子阶段

当YGC执行结束之后，如果发现满足并发标记的条件，并发线程就开始进行并发标记。根据新生代的Survivor分区开始并发标记。并发标记的时机是在YGC后，只有内存消耗达到一定的阈值后才会触发。在G1中，这个阈值通过参数InitiatingHeapOccupancyPercent控制（默认值是45，表示的是当已经分配的内存加上本次将分配的内存超过内存总容量的45%时就可以开始并发标记）。多个并发标记线程启动，每个线程每次只扫描一个分区，从而标记出存活对象。在标记的时候还会计算存活对象的数量，同时会计算存活对象所占用的内存大小，并计入分区空间。

并发标记子阶段会对所有分区的对象进行标记。这个阶段并不需要STW，故标记线程和应用程序线程并发运行。使用Snapshot-At-The-Beginning（SATB）算法进行并发标记。

3．再标记子阶段

再标记是最后一个标记阶段。在该阶段中，G1需要一个STW的时间段，找出所有未被访问的存活对象，同时完成存活内存数据计算。引入该阶段是为了能够达到结束标记的目标。要结束标记过程，需要满足3个条件：

❑从根（survivor）出发并发标记子阶段已经标记出所有的存活对象。

❑标记栈是空的。

❑所有的引用变更对象都被处理了。这里的引用变更对象包括新增空间分配的对象和引用变更对象，新增空间所有对象被认为都是活跃的（即使对象已经“死亡”也没有关系，在这种情况下只是增加了一些浮动垃圾），引用变更处理的对象通过一个队列记录，在该子阶段会处理这个队列中所有的对象。

前两个条件是很容易满足的，但是满足最后一个条件是很困难的。如果不引入一个STW的再标记过程，那么应用会不断地更新引用，也就是说，会不断地产生新的引用变更，因而永远无法达成完成标记的条件。

这个子阶段是并行执行的。

4．清理子阶段

再标记子阶段之后是清理子阶段，该子阶段也需要一个STW的时间段。清理子阶段主要执行以下操作：

❑统计存活对象，统计的结果将会用来排序分区，以用于下一次的垃圾回收时分区的选择。

❑交换标记位图，为下次并发标记做准备。

❑把空闲分区放到空闲分区列表中。这里的空闲分区指的是全都是垃圾对象的分区，如果分区中还有活跃对象，则不会释放，真正释放的动作发生在混合回收中。

该阶段比较容易引起误解的地方在于，清理子阶段并不会清理垃圾对象，也不会执行存活对象的复制。也就是说，在极端情况下，该阶段结束之后，空闲分区列表将毫无变化，JVM的内存使用情况也毫无变化。

该子阶段也是并行执行的。

并发标记阶段完成之后，在下一次进行垃圾回收的时候就会回收垃圾比较多的老生代分区。这时进行的垃圾回收称为混合回收，混合回收和YGC最大的区别就是混合回收不仅仅回收所有的新生代分区，也回收部分垃圾多的老生代分区，所以JVM在实现混合回收时重用了YGC所有的代码，两者的不同之处就在于是否回收老生代分区。整个G1垃圾回收的过程如图1-6所示。

最后，同样在垃圾回收过程或者并发执行过程中，当内存不足需要进行FGC时，也需要STW对整个内存进行串行回收。在JDK 10中对FGC做了改进，把串行回收改进成并行回收，注意是并行的FGC，而不是并发回收。

在G1工作时，还有两个值得注意的地方：

❑G1的引用集RSet处理，它是并发执行的，目的是记录对象的引用关系，能减少垃圾回收过程中的停顿时间。

❑在G1中，并发标记算法使用了SATB算法，该算法是G1并发标记的核心。

引用集RSet的处理是代际管理垃圾回收器中非常重要的一个内容，虽然ZGC目前是单代管理，暂时不会涉及引用集概念，但是ZGC未来很有可能会支持多代管理。另外，ZGC中并发算法和G1的并发标记算法有相似之处，都是基于SATB实现的，但实现方式不同，所以有必要对G1的RSet处理和SATB算法做一个介绍。

1. RSet处理

RSet是一个抽象概念，记录对象在不同代际之间的引用关系，目的是加速垃圾回收的速度。JVM使用的是根对象引用的收集算法，即从根集合出发，标记所有存活的对象，然后遍历对象的每一个成员变量并继续标记，直到所有的对象标记完毕。在分代垃圾回收中，我们知道新生代和老生代处于不同的回收阶段，如果还是采用这样的标记方法，不合理也没必要。假设我们只回收新生代，如果标记时把老生代中的活跃对象全部标记，但回收时并没有回收老生代，则浪费了时间。同理，在回收老生代时有同样的问题。当且仅当我们要进行FGC时，才需要对内存做全部标记。所以算法设计者做了这样的设计——用一个RSet记录从非收集部分指向收集部分的指针的集合，而这个集合描述就是对象的引用关系。通常有两种方法记录引用关系，第一种为Point Out，第二种为Point In。假设有这样的引用关系，对象A的成员变量指向对象B（伪代码为：ObjA. Field = ObjB），对于Point Out的记录方式来说，会在对象A（ObjA）的RSet中记录对象B（ObjB）的地址；对于Point In的记录方式来说，会在对象B（ObjB）的RSet中记录对象A（ObjA）的地址，这相当于一种反向引用。这二者的区别在于处理时有所不同：Point Out记录简单，但是需要对RSet做全部扫描；Point In记录操作复杂，但是在标记扫描时可以直接找到有用和无用的对象，不需要进行额外的扫描，因为RSet里面的对象可以看作根对象。G1中使用的是Point In的方式，为了提高RSet的存储效率，使用了3种数据结构：

1）稀疏表，通过哈希表方式（哈希表底层使用数组）来存储。

2）细粒度表，通过数组来存储，每个数组元素指向引用者分区中512字节内存块对本分区的引用情况。

3）粗粒度位图，通过位图来指示，每1位表示对应的分区有引用到本分区。

RSet的3种数据结构如图1-7所示。

G1新引入了Refine线程，它实际上是一个线程池，有两大功能：

❑用于处理新生代分区的抽样，并且在满足响应时间这个指标的情况下，更新新生代分区的数目，通常由一个单独的线程来处理。

❑更新RSet（也是最重要的功能）。对于RSet的更新并不是同步完成的，G1会把所有引用关系都先放入一个队列中，称为Dirty Card Queue（DCQ），然后使用Refine线程来消费这个队列完成引用关系的记录。正常来说有G1ConcRefinementThreads个线程处理；实际上除了Refine线程更新RSet之外，GC工作线程或者应用程序线程也可能会更新RSet; DCQ通过Dirty Card Queue Set（DCQS）来管理；为了能够快速、并发地处理，每个Refine线程只负责DCQS中的某几个DCQ。

虽然RSet是为了记录对象在代际之间的引用，但是并不是所有代际之间的引用都需要记录。我们简单地分析一下哪些情况需要使用RSet进行记录。分区之间的引用关系可以归纳为：

❑分区内部有引用关系。

❑新生代分区到新生代分区之间有引用关系。

❑新生代分区到老生代分区之间有引用关系。

❑老生代分区到新生代分区之间有引用关系。

❑老生代分区到老生代分区之间有引用关系。

这里的引用关系指的是分区里面有一个对象存在一个指针指向另一个分区的对象。针对这5种情况，最简单的方式就是在RSet中记录所有的引用关系，但这并不是最优的设计方案，因为使用RSet进行回收实际上有两个重大的缺点：

❑需要额外的内存空间；这一部分通常是G1最大的额外开销，一般会达到1%～20%。

❑可能导致浮动垃圾；由于根据RSet回收，而RSet里面的对象可能已经死亡，这个时候被引用对象会被认为是活跃对象，实质上它是浮动垃圾。

所以有必要对RSet进行优化，根据垃圾回收的原理，我们来逐一分析哪些引用关系需要记录在RSet中：

❑分区内部有引用关系，无论是新生代分区还是老生代分区内部的引用，都无须记录引用关系，因为回收的时候是针对一个分区而言，即这个分区要么被回收，要么不回收。如果分区回收，则会遍历整个分区，所以无须记录这种额外的引用关系。

❑新生代分区到新生代分区之间有引用关系，这无须记录，原因在于G1的YGC/Mixed GC/FGC回收算法都会全量处理新生代分区，所以它们都会被遍历，所以无须记录新生代到新生代之间的引用。

❑新生代分区到老生代分区之间有引用关系，这无须记录，对于G1中YGC针对的新生代分区，无须知道这个引用关系，混合回收发生时，G1会使用新生代分区作为根，那么遍历新生代分区时自然能找到新生代分区到老生代分区的引用，所以也无须记录这个引用关系，对于FGC来说更是如此，所有的分区都会被处理。

❑老生代分区到新生代分区之间有引用关系，这需要记录，在YGC的时候有两种根：一个就是栈空间/全局空间变量的引用，另外一个就是老生代分区到新生代分区的引用。

❑老生代分区到老生代分区之间有引用关系，这需要记录，在混合回收的时候可能只有部分分区被回收，所以必须记录引用关系，快速找到哪些对象是活的。

表1-2中总结了上面的关系。

2. SATB算法介绍

并发标记指的是标记线程和应用程序线程并发运行。那么标记线程如何并发地进行标记？并发标记时，一边标记垃圾对象，一边还在生成垃圾对象，如何能正确标记对象？为了解决这个问题，以前的垃圾回收算法采用串行执行方式，这里的串行指的是标记工作和对象生成工作不同时进行。而G1中引入了新的算法SATB，在介绍算法之前，我们先回顾一下对象分配。

在堆分区中分配对象时，对象都是连续分配的，所以可以设计几个指针，分别是Bottom、Prev、Next和Top。用Bottom指向堆分区的起始地址，用Prev指针指向上一次并发处理后的地址，用Next指向并发标记开始之前内存已经分配成功的地址，当并发标记开始之后，如果有新的对象分配，可以移动Top指针，使用Top指针指向当前内存分配成功的地址。Next指针和Top指针之间的地址就是应用程序线程新增对象使用的内存空间。如果假设Prev指针之前的对象已经标记成功，在并发标记的时候从根出发，不仅仅标记Prev和Next之间的对象，还标记了Prev指针之前活跃的对象。当并发标记结束之后，只需要把Prev指针设置为Next指针即可开始新一轮的标记处理。

Prev和Next指针解决了并发标记工作内存区域的问题，还需要引入两个额外的数据结构来记录内存标记的状态，典型的是使用位图（BitMap）来指示哪块内存已经使用，哪块内存还未使用，所以并发标记引入两个位图PrevBitmap和NextBitmap，用PrevBitmap记录Prev指针之前内存的标记状况，用NextBitmap表示整个内存从Bottom到Next指针之前的标记状态。

也许你会奇怪，NextBitmap包含了整个使用内存的标记状态，那为什么要引入PrevBitmap这个数据结构？这个数据结构在什么时候使用？我们可以想象，如果并发标记每次都成功，我们确实不需要用到PrevBitmap，只需要根据NextBitmap这个位图对对象进行清除即可。但是如果标记失败将会发生什么？我们将丢失上一次对Prev指针之前所有内存的标记状况，也就是说当不能完成并发标记时，将需要重新标记整个内存，这显然是不对的。我们通过示意图来演示一下并发标记的过程。

假定初始情况如图1-8所示。

这里用Bottom表示分区的底部，Top表示分区空间使用的顶部，TAMS指的是Top-At-Mark-Start, Prev就是前一次标记的地址，即Prev TAMS, Next指向的是当前开始标记时最新的地址，即Next TAMS。并发标记开始是从根对象出发开始并发的标记。在第一次标记时PrevBitmap为空，NextBitmap待标记。开始进行并发标记，结束后如图1-9所示。

并发标记结束后，NextBitmap记录了分区对象存活的情况，假定上述位图中黑色区域表示堆分区中对应的对象还活着。在并发标记的同时应用程序继续运行，所以Top指针发生了变化，继续增长。

这个时候，可以认为NextBitmap中活跃对象以及Next和Top之间的对象都是活跃的。在进行垃圾回收的时候，如果分区需要被回收，则会把这些对象都进行复制；如果分区可用空间比较多，那么分区不需要回收。当应用程序继续执行，新一轮的并发标记启动时，初始状态如图1-10所示。

在新一轮的并发标记开始时，交换Bitmap，重置指针。根据根对象对Bottom和Next TAMS之间的内存对象进行标记，标记结束后，状态如图1-11所示。

当标记完成时，如果分区垃圾对象满足一定条件（如分区的垃圾对象占用的内存空间达到一定的数值），分区就可以被回收。

这里演示的仅仅是并发标记的SATB算法，但是还有一个主要的问题没有解决，那就是应用程序和并发标记工作线程对同一个对象进行修改，如何保证标记的正确性？这一内容将在4.2.1节中进一步讨论。

3. G1中的屏障

在G1中使用了两种屏障：读屏障和写屏障。其中写屏障是为了处理RSet引入的，而读屏障是为了处理SATB并发标记引入的，所以一句简单的Java赋值语句，例如Object.Field=other_object，实际上被JVM处理成3条伪代码，如下所示：

    JVM----> Insert Pre-write barrier，处理SATB，保证标记的正确性
        Object.Field = other_object；真正的代码
    JVM----> Insert Post-write Barrier，处理RSet，即产生对象到DCQ中

关于读屏障和写屏障这里不再进一步介绍。另外，G1中还引入了字符串去重的功能，在JDK 10中还对G1的FGC进行了优化，从串行回收变成了并行回收等，更多相关内容可以参考其他书籍。