简单聊聊G1垃圾回收算法整个流程

本文想和大家简单聊聊G1垃圾回收算法的设计思路和具体细节实现，受限于笔者个人实力，可能存在部分错误，如果发现了错误或者有补充说明的，可以在评论区留言或者私信与我讨论。

本文写作主要参考资料:

本文大部分理论知识摘抄至 G1GC算法源码剖析 -- 中村正洋 ，在某些比较难理解的地方做出了个人补充，本文为理论篇不涉及源码解读，所以大家可以放心阅读。

G1 垃圾回收算法最大的特点就是其非常注重实时性，这里实时性指的是用户指定一个时间期限，GC时长不能超过这个时间。这里关于是否允许打破时间期限又分为 " 硬实时性 " 和 " 软实时性 " ：

与实时性强相关的一个指标就是可预测性，G1算法需要能够预测出本次垃圾回收耗时，并根据具体情况采取一些措施进行处理。

G1 具有软实时性，为了实现该软实时性，它具备以下两个功能:

G1 算法的重点在于如何预测GC的耗时，同时根据预测的结果，采用延迟GC，拆分GC目标对象等手段来使其满足用户设置的期望暂停时间。

Java 语言目前广泛应用于服务端应用程序的开发，而其中一些场景需要具备软实时性，但是java目前所采用的增量GC或者并发GC，这些GC算法虽然能够缩短最大暂停时间，但是缺点就是会导致吞吐量下降，又因为无法预测暂停时间，GC可能会导致用户线程长时间停止的风险。

增量GC和并发GC会导致吞吐量下降，同时总的暂停时间也会因此拉长。

G1的目标是支持用户设置期望暂停时间，而非一味地尝试缩短最大暂停时间，通过用户按照自己的需求设置合适的GC暂停时间，在确保吞吐量比以往GC更好的前提下，实现软实时性。

G1 通过 mmap 系统调用向操作系统一次性申请了最大堆内存空间，然后将堆内存划分为大小相等的区域 :

G1 以 区域为单位进行GC，用户可以随意设置区域大小，内部会将用户设置的值向上调整为2的指数幂，并以该正数为区域大小。

如果正在分配对象的某个区域已经满了，GC线程会寻找下一个空闲的区域继续分配。空闲区域是通过链表进行管理的，因此查找的时间复杂度固定为 O ( 1 ) 。

本文后续所说的区域是指被G1划分为大小相等区域中的一个区域

G1 GC 主要分为两步:

首先，从众多区域中选择一个进行GC操作，如果该区域中有存活对象，则将其复制到其他空闲区域中:

当选择的空闲区域也满了的时候，GC 线程会再次选择其他空闲区域来存放存活对象。对象复制完成之后，只剩下死亡对象 的区域会被重置为空闲区域以便复用。转移其实也起到了压缩 的作用，因此 G1GC 中的区域不会发生碎片化。

所以G1 GC全局来看是标记整理算法，局部来看是标记复制算法。

G1GC 的主要功能是并发标记和转移。其中并发标记由并发标记线程来执行。

需要注意的是，并发标记和转移在处理上是相互独立的。并发标记的结果信息对于转移来说并不是必须的。因此，转移处理可能发生在并发标记开始之前，也可能发生在并发标记的过程中。

根集合枚举，将可从根直接触达的对象都添加标记，带标记的是存活对象，不带标记的是死亡对象。

根集合主要包括以下几个来源:

标记结束后，可从根触达的对象 a、b、c 都带有标记，而对象 d、e 则会因为不带标记而被当作死亡对象处理。

在垃圾回收过程中，修改对象的线程（称为Mutator）必须暂停，这会让应用程序产生停顿，没有任何响应，有点像卡死的感觉，这个停顿称为STW（Stop The Word）。这样可以避免在垃圾回收过程中因额外的线程对对象进行删除或移动等操作，从而造成的漏标、错标等错误。HotSpot VM使用安全点来实现STW 。

安全点会让Mutator线程运行到一些特殊位置后主动暂停，这样就可以让GC线程进行垃圾回收或者导出堆栈等操作。

当用户线程执行过程中发现内存不足时，会向后台线程的任务队列中丢入一个垃圾回收任务，通常会产生一个VM_Operation任务并将其放到VMThread队列中，VMThread会循环处理这个队列中的任务，其中在处理任务时需要有一个进入安全点的操作，任务完成后还要退出安全点。

用户线程与后台线程进行通信都是借助队列完成的，也就是典型的生产者-消费者模式。

下面给出一段HotSpot JDK 7 关于进入安全点的源码:

进入安全点时Java线程可能存在几种不同的状态，这里需要处理所有可能存在的情况:

关于安全点具体的源码实现细节将在后续HotSpot虚拟机源码系列专栏中发布相关文章进行解答。

整个并发标记阶段，包括初始标记阶段，并不是直接在对象上添加标记，而是在标记位图上添加标记。

每个区域都带有两个标记位图: next 和 prev 。next 是本次标记的标记位图 ，而 prev 是上次标记的标记位图，保存了上次标记的结果。

标记位图中每个bit都指向堆中的一个对象，这里假设单个对象的大小都是8个字节，那么堆中每8个字节就会对应标记位图中的1个比特。

棕色表示对象存活，白色表示对象死亡

nextTASM 中的 TAMS 全称为 “Top At Marking Start” (标记开始时的top) 。 nextTASM 保存了本次标记开始时的 top ， 而 prevTASM 保存了上次标记开始时的 top 。

因为并发标记期间，用户线程会不断分配新的对象，此时top指针会不断前移，而nextTAMS是固定不动的，所以nextTAMS 到 top 这个区间范围内的对象都是并发标记期间新创建出来的对象，G1不会扫描该区域内的对象，而是将该区域内的对象都看作是存活对象。

并发标记阶段可以分为如下五个流程:

在初始标记阶段，GC线程会创建标记位图next 。nextTAMS指向标记开始时top所在的位置，对可由根直接引用的对象进行标记的过程叫作根扫描。等所有区域的标记位图都创建完成之后，就可由开始进行根扫描了。

为了防止在根扫描过程中根被修改，在这个过程中用户线程是暂停执行的。

并发标记阶段，GC线程沿着GC ROOTS集合进行广度优先遍历 :

并发标记阶段结束后区域的状态。对象 C 的子对象 A 和E 都被标记了。像 E 这样，一个对象对应了标记位图中多个位的情况，只有起始的标记位（mark bit）会被涂成黑色。

对象E占据16个字节大小，因此对应next位图中的两位。

并发标记阶段的一个重要特点是 GC 线程和用户线程是并发执行的。因为用户线程在执行过程中可能会改变对象之间的引用关系，所以如果只采用一般的标记方法，可能会发生“标记遗漏” 。因此，必须使用写屏障技术来记录对象间引用关系的变化。针对这种情况，G1GC 中所采用了我们耳熟能详的原始快照技术。并发标记阶段也会标记和扫描被写屏障获知变化的对象。

处理完待标记对象之后，就会进入最终标记阶段。

并发标记阶段，GC线程沿着GC ROOTS集合进行广度优先遍历，同时采用三色标记法避免已标记对象的重复遍历，因此下面简单介绍一下三色标记法的概念:

由于并发标记阶段和用户线程是并行执行的，因此这里可能会存在两个问题:

对于第一个问题，是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就可以了。但是第二个问题就很致命了，因为发生了对象消失问题，即我们将原本应该是黑色的对象误标为白色，因此我们必须解决这个问题。

发生对象消失问题，必须同时满足以下两个条件:

这里应该比较好理解，因为用户线程删除了灰色对象到未扫描的白色对象的引用关系，同时又将黑色对象指向该白色对象，由于黑色对象不会再被扫描了，所以此时就会发生对象消失问题。

解决对象消失问题，只需要破坏上面两个条件的任意一个即可，因此又分为了两种解决方案:

G1 使用原始快照法来解决对象消失问题，因此本节我们重点来看看G1是如何实现原始快照的。

SATB（Snapshot At The Beginning）是一种将并发标记阶段开始时对象间的引用关系，以逻辑快照的形式进行保存的手段 。在SATB 中，标记过程中新生成的对象会被看作“已完成扫描和标记”，因此其子对象不会被标记。

上图中 nextTAMS 和 top 之间的对象 J 和 K就是在标记过程中新生成的对象。因为它们的引用关系在标记开始时并不存在，所以它们都会被当成存活对象。因此，也不必专门为标记过程中新生成的对象创建标记位图。这样我们就明白为什么上图中对象 J和 K 没有对应的标记位图了。

另外，如果在并发标记的过程中对象的域上发生了写操作，就必须以某种方式记录下被改写之前的引用关系。G1GC 通过写屏障技术，实现了这个功能，我们也称之为 SATB 专用写屏障。SATB 专用写屏障的伪代码如下所示:

STAB核心就是记录下在引用关系变更时，原始的引用关系；另外，在实现 SATB 专用写屏障的实现考虑到了多线程环境下的执行。其中的奥妙就在于第 5 行的$current_thread.stab_local_queue（SATB 本地队列）。

$current_thread.stab_local_queue 是用户线程各自持有的线程本地队列，而非全局的队列，因此在执行 enqueue() 时不用担心线程之间会发生资源竞争。

SATB 本地队列在装满（默认大小为 1 KB）之后，会被添加到全局的 SATB 队列集合中。这些被添加的 SATB 本地队列，都是并发标记阶段的待标记对象。

mutator指的是用户线程

在并发标记阶段，GC 线程会定期检查 SATB 队列集合的大小。如果发现其中有队列，则会对队列中的全部对象进行标记和扫描。SATB 专用写屏障并不检查目标对象是否被标记，因此队列中可能存在已经被标记的对象。这些已经被标记的对象不会再次被标记和扫描。

另外，比起 “从根开始逐一扫描存活对象并进行标记的处理”，扫描 SATB 队列集合的处理优先级更高。这是因为，写屏障会不断地往 SATB 本地队列中添加对象，但是对象间引用关系的变化并不会改变存活对象的触达链路的总条数。因此，扫描 SATB 队列集合，比扫描存活对象触达链路的优先级更高也是合理的。

G1 对 SATB 专用写屏障进行了以下两点优化 :

SATB 这样优化的目的是为了将写屏障的系统负荷转移到并发标记处理中，从而分担用户线程的负担。

因为用户线程会频繁地执行写屏障，所以减少写屏障的开销也会减轻用户线程的负担。而且，并发标记处理是由 GC线程和用户线程并发执行的，所以多个用户线程就能平摊这些负担，进而减轻单个用户线程的负担。

如果把这些优化放到不支持并发标记的 GC 中，该 GC 的负荷反而会增加。这种针对写屏障的优化，可以说是专为采用了并发标记的 G1GC 设计的。

上面再次贴出了SATB对应的写屏障伪代码，这段代码会在各个用户线程对象发生改写时被调用执行，并且没有加锁，所以如果多线程同时改写 *field ，oldobj就可能会存入意想不到的值。

典型的读-修改-写回原子性问题

在这种情况下，*field 最终会被 t2 写入 obj2。但是 t1 写入的 obj1并不会被添加到 SATB 本地队列中。也就是说，obj1 并没有被 SATB 专用写屏障获知。这看起来像是致命的缺陷，但实际上，即使 obj1 没有被添加到 SATB 本地队列中也没有关系。

SATB 专用写屏障本来是用来防止发生标记遗漏的，那么 obj1 没有被添加到 SATB 本地队列这件事会不会导致标记遗漏呢？

上图表示的是 obj1 未被 SATB 专用写屏障获知时对象之间的关系。我们假定并发标记进行到了 obj3。由于 obj1 不会被添加到 SATB 本地队列中，所以会保持为白色。而 obj0 会被添加到 SATB 本地队列中，所以会变成灰色。但是在后续扫描 obj4 时，obj1 最终还是会被标记，所以不存在标记遗漏。

标记完成的对象用黑色表示；添加到 SATB 本地队列中的对象用灰色表示；其余对象用白色表示。

那么，如果 obj1 不再被 obj4 引用，而变为被 obj2 引用时，情况又是怎样的呢？

在这种情况下，来自 obj4 的引用消失会被 SATB 专用写屏障获知，obj1 会变成灰色，所以也不会有问题。

SATB 专用写屏障会记录下并发标记阶段开始时对象之间的引用关系。这么来看，因为 obj3 对 obj1 的引用在并发标记阶段开始时并不存在，所以根本没有必要记录 obj1。相反，因为 obj3 对 obj0 的引用在并发标记阶段开始时就存在，所以记录 obj0 是有必要的。

最终标记阶段的处理是暂停处理，需要暂停用户线程的运行。

因为未装满的 SATB 本地队列不会被添加到 SATB 队列集合中，所以在并发标记阶段结束后，各个线程的 SATB 本地队列中可能仍然存在待扫描的对象。而最终标记阶段就会扫描这些“残留的 SATB 本地队列”。在下图中，队列中保存了对象 G 和 H 的引用。因此在扫描 SATB 本地队列之后，对象 G 和 H，以及对象 H 的子对象 I 都会被标记。

因为 SATB 本地队列中存在对象 G 和 H 的引用，所以扫描后，对象 G 和 H，以及对象 H 的子对象 I 都会变成黑色。

最终标记结束后，所有的存活对象都已经被标记。因此，此时所有不带标记的对象都可以判定为死亡对象。

因为SATB 本地队列中的数据会被用户线程操作，所以本步骤不能和用户线程并发执行。

这个步骤会扫描各个区域的标记位图 next，统计区域内存活对象的字节数，然后将其存入区域内的next_marked_bytes 中。下图中的存活对象是 A、C、E、G、H 和 I，因此计算出的总字节数 56 会被存入next_marked_bytes 中。对象 E 虽然只有头部的 1 个比特被标记了，但参与统计的是它的真实大小，即 16 字节。

next_marked_bytes 表示对象 A、C、E、G、H 和 I 的总字节数，一共 56 字节。计数过程中新创建了对象 L 和 M。

另外，我们假设在计数过程中新创建了对象 L 和 M。由于这些包含在nextTAMS 和 top 之间的对象都会被当作存活对象来处理，所以不会在这里特意进行计数。

prev_marked_bytes 中存放了上次标记结束时存活对象的字节数。上图中的区域在此之前未曾进行过标记，因此 prev_marked_bytes 中存放的是初始值 0。

计数处理和用户线程是并发执行的。但是，计数过程中操作的对象也可能会被转移的记忆集合（remembered set）线程使用，因此需要先停掉记忆集合线程。

记忆集用于记录跨区域之间的引用关系。

另外，转移处理也可能在计数过程中启动。这时，需要先将正在计数中的区域统计完，再开始转移处理。已完成计数的区域在转移后会变成空区域，所以 next_marked_bytes 也会变成 0。而转移目标区域内都是存活对象，所以也不会对它进行计数。

收尾工作所操作的数据中有些是和用户线程共享的，因此需要暂停用户线程的运行。

在此期间 GC 线程会逐个扫描每个区域，将标记位图 next 中的并发标记结果移动到标记位图 prev 中，再对并发标记中使用过的标记值进行重置，为下次并发标记做好准备。

此外，对没有存活对象的区域进行回收的工作也在这个时候进行。可以把它理解成以区域为单位进行的标记清除处理。

在扫描过程中还会计算每个区域的转移效率，并按照该效率对区域进行降序排序。关于转移效率如何计算，将在软实时性小节进行介绍。

下图展示了收尾工作结束后区域的状态。next·next_marked_bytes 中的值被移到了prev·prev_marked_bytes 中。同时，prevTAMS 被移到了 nextTAMS 先前的位置。prevTAMS 表示的是“上次并发标记开始时 top 的位置”。

next·next_marked_bytes 也会被重置，同时 nextTAMS 会移动到bottom 的位置。nextTAMS 会在下次并发标记开始时，移动到 top 的最新位置。

收尾工作结束后，整个并发标记就结束了。并发标记线程会一直处于等待状态，直到下次并发标记开始。

转移效率可以通过公式“死亡对象的字节数÷转移所需时间”来计算。换句话说，转移效率指的就是转移 1 个字节所需的时间。区域的转移效率可以通过公式“区域内死亡对象的字节数÷转移整个区域所需时间”来计算。

这里的“转移所需时间”严格来说是转移的预测时间。转移的预测时间可以根据过去的实际转移时间来计算。详细内容将在软实时性一节中进行详述。

另外，一般来说死亡对象越多，转移效率就越高。死亡对象多就意味着存活对象少；存活对象越少，转移所需的时间就越少，所以转移效率就会越高。

并发标记结束后，转移处理可以得到以下信息 :

这些信息在并发标记阶段不会被改变，因此，即使在并发标记阶段就开始转移处理也不会有问题。另外，虽然新的对象是在并发标记结束后被创建的，但由于它是分配在 prevTAMS 和 top 之间的，所以会被当成存活对象处理。

通过转移，所选区域内的所有存活对象都会被转移到空闲区域。这样一来，被转移的区域内就只剩下死亡对象。重置之后，该区域就会成为空闲区域，能够再次利用。

下图表示了转移开始前和结束后的状态。转移结束后，可从根触达的存活对象 a、b、c 会被转移到空闲区域 C，而死亡对象 d 和 e 不会被转移，整个区域 B 会被重置以供再次利用。

待转移对象所在的区域是 A 和 B。可从根触达的对象 a、b、c 会被转移到区域 C。

除了可以从根和并发标记的结果发现存活对象之外，转移功能还能通过转移专用记忆集合来发现对象。之前介绍的 SATB 队列集合主要用来记录标记过程中对象之间引用关系的变化，而转移专用记忆集合则用来记录区域之间的引用关系。通过使用转移专用记忆集合，在转移时即使不扫描所有区域内的对象，也可以查到待转移对象所在区域内的对象被其他区域引用的情况，从而简化单个区域的转移处理。

转移专用记忆集合中记录了来自其他区域的引用，因此即使不扫描所有区域内的对象，也可以确定待转移对象所在区域内的存活对象。

G1GC 是通过卡表（card table）来实现转移专用记忆集合的。

卡表是由元素大小为 1 B 的数组实现的。卡表里的元素称为卡片。堆中大小适当的一段存储空间会对应卡表中的 1 个元素（卡片）。在当前的 JDK 中，这个大小被定为 512 B。因此，当堆的大小是1 GB 时，可以计算出卡表的大小就是 2 MB。

卡表的实体是数组。数组的元素是 1 B 的卡片，对应了堆中的 512 B。脏卡片用灰色表示，净卡片用白色表示。

堆中的对象所对应的卡片在卡表中的索引值可以通过以下公式快速计算出来:

因为卡片的大小是 1 B，所以可以用来表示很多状态。卡片的种类很多，这里主要关注以下两种:

转移专用记忆集合的构造如图所示:

每个区域中都有一个转移专用记忆集合，它是通过散列表实现的。散列表的键是引用本区域的其他区域的地址，而散列表的值是一个数组，数组的元素是引用方的对象所对应的卡片索引。

在上图中，区域 B 中的对象 b 引用了区域 A 中的对象 a。因为对象 b不是区域 A 中的对象，所以必须记录下这个引用关系。而在转移专用记忆集合 A 中，以区域 B 的地址为键的值中记录了卡片的索引 2048。因为对象 b 所对应的卡片索引就是 2048，所以对象 b 对对象 a 的引用被准确地记录了下来。

由此我们可以明白，区域间对象的引用关系是由转移专用记忆集合以卡片为单位粗略记录的。因此，在转移时必须扫描被记录的卡片所对应的全部对象的引用。

这里简单说明一下卡表在CMS和G1中工作细节的区别:

CMS中利用卡表每个byte来指示对应老年代某块区域中是否存在跨代引用，这里其实只需要使用到其中1个bit来表示脏位即可。

G1中的情况就复杂了一些，因为存在更多的区域，因此需要为每个区域单独准备一个卡表，但是卡表只能表明当前区域存在跨代引用，但是除非通过扫描所有区域的所有脏卡，否则无法快速计算出区域A中是否存在被其他区域引用的对象；

因此，这里为每个区域单独引入了一个记忆集合，记忆集合中记录了引用当前区域的所有脏卡，同时把脏卡按照所属区域进行分组管理；此时，我们想要获取区域A中所有被其他区域引用的对象，只需要挨个处理每个分组内的脏卡集合即可，依次扫描每个脏卡集合中的脏卡，即可找出本区域中所有被其他区域引用的存活对象。

这里还有一点G1和CMS不同，主要在于卡表脏标记位的应用，后面两节我们会聊到这个问题。

当对象的域被修改时，被修改对象所对应的卡片会被转移专用写屏障记录到转移专用记忆集合中。

转移专用写屏障的伪代码如下：

第 2 行到第 7 行的代码会在 obj 和 newobj 位于同一个区域，或者 newobj 为 Null 时，起到过滤的作用。这是达尔科·斯特凡诺维奇（Darko Stefanović）等人提出的过滤技术。

第 2 行的“^”（XOR 运算符）用来检测两个对象地址的高位部分是否相等。每个区域都是按固定大小进行分配的，如果 obj 和 newobj 是同一个区域中的地址，那么由于两个地址中超过区域大小的高位部分是完全相等的，所以第 2 行变量 check 的值小于区域的大小。第 3 行的LOG_OF_HEAP_REGION_SIZE 是区域大小的对数（底为 2）。之前提到过，区域大小必须是“2 的指数幂”，而指数 就是LOG_OF_HEAP_REGION_SIZE。将 check 右移LOG_OF_HEAP_REGION_SIZE 后，小于区域大小的比特值都会归 0。

这样一来，如果 check 的值小于区域大小，右移之后的结果就会变为 0。第 4 行检查 newobj 是否为 Null，第 6 行检查 check 是否为 0。

第 9 行的函数 is_dirty_card() 用来检查参数 obj 所对应的卡片是否为脏卡片。脏卡片指的是已经被转移专用写屏障添加到转移专用记忆集合日志中的卡片。该行的检查就是为了避免向转移专用记忆集合日志中添加重复的卡片。相反，不在转移专用记忆集合日志中的卡片是净卡片。如果是净卡片，则该卡片将在第 10 行变成脏卡片，然后在第 11 行被添加到队列 $current_thread.rs_log 中。这个处理能够保证转移专用记忆集合日志中的卡片都是脏卡片。

另外，转移专用写屏障和 SATB 专用写屏障做了同样的优化，在多线程环境下性能也不会变差。

下图表示了“转移专用记忆集合日志”和“全局转移专用记忆集合日志队列”的结构。每个用户线程都持有一个名为转移专用记忆集合日志的缓冲区，其中存放的是卡片索引的数组。当对象 b 的域被修改时，写屏障就会获知，并会将对象 b 所对应的卡片索引添加到转移专用记忆集合日志中。转移专用记忆集合日志是由各个用户线程持有的，所以在添加时不用担心线程之间的竞争。

也是得益于这种设计，转移专用写屏障不需要进行排他处理，因而具有更好的性能。上面代码中的$current_thread.rs_log 就是转移专用记忆集合日志 ：

另外，转移专用记忆集合日志会在写满后被添加到全局转移专用记忆集合日志队列中。这个添加过程可能存在多个线程之间的竞争，所以需要做好排他处理。添加完成后，用户线程会被重新分配一个空的转移专用记忆集合日志。

转移专用记忆集合维护线程是和用户线程并发执行的线程，它的作用是基于全局转移专用记忆集合日志队列，来维护转移专用记忆集合。

具体来说，转移专用记忆集合维护线程主要进行下列处理：

如果卡片在③和④的处理过程中被用户线程修改了，那么又会变成脏卡片，然后再次被添加到转移专用记忆集合日志中。

当全局转移专用记忆集合日志队列中元素数量超过阈值（默认为 5 个）时，转移专用记忆集合维护线程就会启动，然后一直处理到数量降至阈值的 1/4 以下。

这里我想提出一个小问题，这个问题也是笔者在刚开始阅读时产生的疑惑:

这个问题建议大家先不要看答案，自行思考一下，下面给出笔者个人的观点，当然不一定正确，有不同意见的小伙伴可以评论区留下自己的观点。

首先来梳理一下整个流程:

这里我们来思考一下： 如果扫描完当前脏卡对应的区域后，不从卡表中移除脏位标记，会怎样？

其实上面也预留了这个问题的埋点，相信到此处大家应该立即了卡表的脏位标记在G1中的作用了吧，注意和CMS的作用进行区分。

频繁发生修改的存储空间所对应的卡片称为热卡片（hot card）。热卡片可能会多次被转移专用记忆集合维护线程处理成脏卡片，从而加重转移专用记忆集合维护线程的负担，因此需要特别处理。

要想发现热卡片，需要用到卡片计数表，它记录了卡片变成脏卡片的次数。卡片计数表记录了自上次转移以来哪个卡片变成了脏卡片，以及变成脏卡片的次数，其内容会在下次转移时被清空。

变成脏卡片的次数超过阈值（默认是 4）的卡片会被当成热卡片，在被处理为脏卡片后添加到热队列尾部。热队列的大小是固定的（默认是 1KB）。如果队列满了，则从队列头部取出老的卡片，给新的卡片腾出位置。取出的卡片由转移专用记忆集合维护线程当作普通卡片处理。

热队列中的卡片不会被转移专用记忆集合维护线程处理，因为即使处理了，它也有可能马上又变成脏卡片。因此，热队列中的卡片会被留到转移的时候再处理。

热卡片的产生可能是由于用户线程频繁修改某个区域中对象的引用关系。

转移过程分为以下三步:

这 3 个步骤都是暂停处理。在转移开始后，即使并发标记正在进行也会先中断，而优先进行转移处理。

另外，第二步和第三步其实都是可以由多个线程并行执行的，这里书中便于理解，是以单线程为例进行讲解的，本文也遵循书中讲解方式。

本步骤的主要工作是选择回收集合。选择标准简单来说有两个:

在选择回收集合时，堆中的区域已经在并发标记收尾阶段中按照转移效率被降序排列了。

接下来，按照排好的顺序依次计算各个区域的预测暂停时间，并选择回收集合。当所有已选区域预测暂停时间的总和快要超过用户的容忍范围时，后续区域的选择就会停止，所有已选区域成为 1 个回收集合。关于转移的预测暂停时间，在后续的软实时性小节会进行介绍。

G1GC 中的 G1 是 Garbage First 的简称，所以 G1 GC 的中文意思是“垃圾优先的垃圾回收”。而回收集合的选择，会以转移效率由高到低的顺序进行。在多数情况下，死亡对象（垃圾）越多，区域的转移效率就越高，因此 G1GC 会优先选择垃圾多的区域进入回收集合。这就是 G1 GC名称的由来。

根转移的转移对象包括以下 3 类：

根转移过程的伪代码如下所示:

转移专用记忆集合中记录了区域之间完整的对象引用关系，但没有记录来自根的引用。因此，代码第 2 行至第 4 行先是把被根引用的位于回收集合内的对象转移到其他的空闲区域。被根引用却不在回收集合内的对象会被直接忽略。第 4 行的 evacuate_obj() 是用于转移对象的函数，它的返回值是转移后对象的地址。

另外，并发标记中使用的 SATB 本地队列和 SATB 队列集合中的引用也包含在 $root 中，会被转移。这是因为它们的引用地址都必须改为转移后的地址。

第 6 行中 force_update_rs() 的作用是将未被转移专用记忆集合维护线程扫描的脏卡片更新到各个区域的转移专用记忆集合中。具体来说，包含如下 3 个部分涉及的脏卡片：

转移专用记忆集合的更新是并发进行的。在转移开始时，转移专用记忆集合维护线程的处理很可能还没结束，因此有必要将①和②中的脏卡片更新到对应区域的转移专用记忆集合中。

通过第 7 行至第 9 行，回收集合内被其他区域引用的对象会像根一样被转移。第 7 行的 $collection_set 是回收集合。第 8 行的 rs_cards 域中保存了区域的转移专用记忆集合中的所有卡片。第 9 行的scan_card() 函数的函数体是第 11 行至第 16 行。

这个函数所做的事情是扫描转移专用记忆集合中的卡片所对应的每个对象。如果某对象存在对回收集合内对象的引用，那么该对象也会被转移。需要注意的是，如果卡片中的对象是未被标记的，那么其子对象将不会继续被扫描。

每个区域会关联一个标记位图，G1使用标记位图来标记存活对象，所以这里标记的意思就是查看标记位图对应位是否为1。

对象转移的整个过程如下图所示:

保存转移后新地址的变量。一旦发现了指向转移前地址的指针，就能将其改为指向转移后的新地址。

这里的转移队列和上面所说的转移专用集合记忆区分开来，不要搞混了。

下面简单看一下对象转移过程的伪代码:

参数 ref 是待转移对象的引用方。第 2 行的 from 是待转移对象。

第 3 行和第 4 行是取消未标记对象的转移，直接返回。而死亡对象无论什么时候都不会被转移。

第 5 行至第 7 行则是在对象已经被转移时返回转移后的地址。第 6 行的函数 add_reference(from, to)，其作用是将 from 对应的卡片添加到 to 所在区域的转移专用记忆集合中（后面会详细介绍）。具体到这段代码中，含义就是将引用方对应的卡片添加到转移目标（forwarding指针）区域的转移专用记忆集合中（和上图中的⑤作用相同）。

第 9 行和第 10 行用来将对象复制到转移目标区域（上图中的①）；第 12 行和第 13 行用于将对象转移后的地址存入 forwarding 指针中（上图中的②）。

第 15 行至第 19 行用来扫描已转移完成的对象的子对象。第 16 行用来检查子对象是否在回收集合内。如果在回收集合内，则执行第 17 行，将子对象添加到转移队列（$ evacuate_queue）中（上图中的③），否则执行第 19 行，调用函数 add_reference()。该函数的参数为子对象的引用方 child 和子对象 *child（上图中的④）。

第 21 行用来将待转移对象所对应的卡片，添加到转移目标区域的转移专用记忆集合中（上图中⑤）。然后，通过第 23 行返回对象转移后的新地址（上图的⑥）。

接下来，我们看一下函数 add_reference() 的伪代码。该函数的作用是向转移专用记忆集合中添加引用方所对应的卡片。

参数 from 是引用方的地址，to 是引用对象的地址。第 2 行和第 3 行分别用来获取各自的区域。如果传递给函数 region() 的地址是堆外的地址，该函数会返回 Null。

第 4 行分别检查 to_region 和 from_region 是否为 Null。第 5 行检查 to_region 和 from_region 是否位于不同的区域。如果二者位于相同的区域，就没有必要将卡片添加到转移专用记忆集合中了。

同时，第 5 行还检查 from 是否在回收集合之外。如果 from 在回收集合之内，那么它要么已经转移完成，要么马上就要被转移，所以都可以忽略掉。

传入的from应该是引用对象的地址，to是被引用对象的地址，这里引用对象地址如果还处在待回收区域中，那么就无需建立此次映射关系了，因为后面等到该对象转移时，还是需要重新建立映射关系，不仅是与引用它的对象，还有它的子对象，也就是这里的被引用对象。

这几步检查都通过之后，就在第 6 行由函数 card() 获取 from 所对应的卡片，然后将其添加到区域 to_region 的转移专用记忆集合中。

当跨区域引用对应的引用方区域和被引用方区域都位于回收集合中时，此时就无需在被引用方的转移专用记忆集合中添加引用方所在卡片了，这里举个例子说明这一点:

完成根转移之后，那些被转移队列引用的对象将会依次转移。直到转移队列被清空，转移就完成了。至此，回收集合内的所有存活对象都被成功转移了。

转移过程伪代码:

最后，清空回收集合的记忆集合，开启用户线程的执行。

转移章节中贴出的很多伪代码都会判断对象是否被标记，进而忽略掉死亡对象。因为有这些处理，所以像下图中b这样的只被死亡对象引用的对象是不会被转移的。这正是并发标记中标记信息的意义所在。

待转移对象所在区域内的对象 b，因为只被死亡对象引用，所以不会被转移。只有对象 d’ 会被转移。

转移专用记忆集合也在不停地记录着来自死亡对象的引用。查看并发标记的标记信息，有助于忽略来自转移专用记忆集合中死亡对象的引用，也有助于更多地发现区域内的死亡对象。

这里说的标记就是G1使用的标记位图，每个区域对应一个标记位图，如果有遗忘的读者可以返回到并发标记小节进行回顾。

在转移过程中，需要选择适当数量的区域组成回收集合，然后将回收集合内的存活对象转移到空闲区域。转移时需要扫描转移专用记忆集合和根。如果转移时有并发标记的标记信息可供参考，更有助于正确地发现存活对象。

另外，如果能知道并发标记之后存活对象的数量，那么选择回收集合时用到的转移预测暂停时间会更加精准。关于详细内容。

由于篇幅原因，本文只能将G1的并发标记和转移流程进行简单分析，理论篇下文中将会和各位大家一起来看看G1是如何计算各个区域回收价值的，以及结合分代使用的G1模式。

本文观点不保证完全正确，如有错误，欢迎各位在评论区指正，或者私信与我讨论。