如果大家关注 JDK，会发现在频繁发布的 JDK 版本中，和垃圾回收相关的 JEP (JDK Enhancement Proposals，Java 增强提案）越来越多了，垃圾回收（Garbage Collection，GC）正处于方兴未艾的阶段。譬如，在 JEP-248 中 G1 替代了并行垃圾回收器成为 JVM 中默认的垃圾回收器，JEP-333 加入了实验性质的 ZGC；最新的 JEP-189 引入了名为 Shenandoah GC 的垃圾回收器。

对于这么一个有趣的话题，我决定写篇文章来介绍，与很多介绍垃圾回收器的文章不同，本文不会涉及「某某垃圾回收器特性」和「如何使用某某垃圾回收器」等「what&how」的内容，而是从底层的垃圾回收算法开始，着重去阐释不同垃圾回收器在算法设计和实现时的一些技术细节，去探索「why」这一部分，通过对比不同的垃圾回收算法和其实现，进一步感知目前垃圾回收的发展脉络。

本文主要分为上下两个部分：

• 第一部分为「算法篇」，主要介绍一些重要的 GC 算法，去领略 GC 独特的思维方式和各算法的特性，这些是和具体的编程语言无关的；
• 第二部分为「实现篇」，主要介绍 JVM 上的一些垃圾回收器实现，包括 G1、ZGC、Shenandoah GC 等，通过了解这些商业垃圾回收器的设计理念，加深对垃圾回收算法的理解。

下面是第一部分，「算法篇」的内容。

算法篇

一 垃圾回收概述

垃圾回收（Garbage Collection，GC）引起大家的关注，是从1995 年 Java 发布后开始的。事实上，GC 作为计算机科学领域非常热的研究话题之一，最早可以追溯到 1959 年的夏天，起初是用用来简化 Lisp 内存管理的。在接下来60余年的时间里， 通过 Cheney、Baker 等大师的不断努力，GC 的世界里出现了标记清除、复制、分代、增量回收等一系列 GC 算法，基于这些算法，又出现了种类繁复的垃圾回收器。

GC 的定义

首先我们来看一下什么是 GC。
GC 把程序不用的内存空间视为「垃圾」，（几乎所有的）GC 要做的就只有两件事：

• 找到内存空间里的垃圾，使其和活对象分开来。
  
• 回收垃圾对象的内存，使得程序可以重复使用这些内存。
  

GC 给我们带来的好处不言而喻，选择 GC 而不是手动释放资源的原因很简单：程序比人更可靠。即便是 C/C++ 这种没有 GC 的语言，也有类似 Boehm GC 这样的第三方库来实现内存的自动管理了。可以毫不夸张地说，GC 已经是现代编程语言的标配。

GC 的流派

GC 从其底层实现方式（即 GC 算法）来看，大体可以分为两大类：基于可达性分析的 GC和基于引用计数法的 GC。当然，这样的分类也不是绝对的，很多现代 GC 的设计就融合了引用计数和可达性分析两种。

可达性分析法

基本思路就是通过根集合（gc root）作为起始点，从这些节点出发，根据引用关系开始搜索，所经过的路径称为引用链，当一个对象没有被任何引用链访问到时，则证明此对象是不活跃的，可以被回收。使用此类算法的有JVM、.NET、Golang等。

引用计数法

引用计数法没有用到根集概念。其基本原理是：在堆内存中分配对象时，会为对象分配一段额外的空间，这个空间用于维护一个计数器，如果有一个新的引用指向这个对象，则计数器的值加1；如果指向该对象的引用被置空或指向其它对象，则计数器的值减1。每次有一个新的引用指向这个对象时，计数器加1；反之，如果指向该对象的引用被置空或指向其它对象，则计数器减1；当计数器的值为0时，则自动删除这个对象。使用此类算法的有 Python、Objective-C、Per l等。
**
基于可达性分析法的 GC 垃圾回收的效率较高，实现起来比较简单（引用计算法是是算法简单，实现较难），但是其缺点在于 GC 期间，整个应用需要被挂起（STW，Stop-the-world，下同），后面很多此类算法的提出，都是在解决这个问题（缩小 STW 时间）。
基于引用计数法的 GC，天然带有增量特性（incremental），GC 可与应用交替运行，不需要暂停应用；同时，在引用计数法中，每个对象始终都知道自己的被引用数，当计数器为0时，对象可以马上回收，而在可达性分析类 GC 中，即使对象变成了垃圾，程序也无法立刻感知，直到 GC 执行前，始终都会有一部分内存空间被垃圾占用。
上述两类 GC 各有千秋，真正的工业级实现一般是这两类算法的组合，但是总体来说，基于可达性分析的 GC 还是占据了主流，究其原因，首先，引用计数算法无法解决「循环引用无法回收」的问题，即两个对象互相引用，所以各对象的计数器的值都是 1，即使这些对象都成了垃圾（无外部引用），GC 也无法将它们回收。当然上面这一点还不是引用计数法最大的弊端，引用计数算法最大的问题在于：计数器值的增减处理非常繁重，譬如对根对象的引用，此外，多个线程之间共享对象时需要对计数器进行原子递增/递减，这本身又带来了一系列新的复杂性和问题，计数器对应用程序的整体运行速度的影响，这里的细节可以参考文章：Boost’s shared_ptr up to 10× slower than OCaml’s garbage collection[1]。

本文后面介绍的垃圾回收算法，主要就是可达性分析类算法及其变种。

二 垃圾回收核心概念

在深入研究垃圾回收算法的实现细节之前，有必要知道 GC 算法中的一些基本概念，这对了解 GC 算法的基本原理和演进过程是有帮助的。除了算法基础名词外，我们需要深入理解GC 世界里极其重要的两个核心概念：读/写屏障和三色标记法。

基础名词

根节点（GC Roots）

在 GC 的世界里，根是执行可达性分析的「起点」部分，在 Java 语言中，可以作为 GC Roots 的对象包括：

• 虚拟机栈中（栈帧中的本地变量表）引用的对象
  
• 方法区中的类静态属性引用的对象
  
• 方法区中常量引用的对象
  
• 本地方法栈中 JNI（Native 方法） 引用的对象
  

是否作为根的判定依据：程序是否可以直接引用该对象（譬如调用栈中的变量指针）。同时还需要注意的是：不同的垃圾回收器，选择 GC Roots 的范围是不一样的。

并行回收&&串行回收

根据垃圾回收的运行方式不同，GC 可以分为三类：

• 串行执行：垃圾回收器执行的时候应用程序挂起，串行执行指的是垃圾回收器有且仅有一个后台线程执行垃圾对象的识别和回收；
  
• 并行执行：垃圾回收器执行的时候应用程序挂起，但是在暂停期间会有多个线程进行识别和回收，可以减少垃圾回收时间；
  
• 并发执行：垃圾回收器执行期间，应用程序不用挂起正常运行（当然在某些必要的情况下垃圾回收器还是需要挂起的）。
  

上面并发和并行容易混淆，因为在 Java 中，我们提到的并发天然会联想到是「同一类多个线程」执行「同一类任务」，在 GC 中，并发描述的是「GC 线程」和「应用线程」一起工作。
当我们说到某种垃圾回收器支持并发时，并不意味着在垃圾回收的过程中都是并发的，譬如，G1 和 CMS 垃圾回收器支持并发标记，但是在对象转移、引用处理、符号表和字符串表处理、类卸载时，是不支持并发的。总之，并发的表述具有「阶段性」。

三色标记法

可达性分析类 GC 都属于「搜索型算法」（标记阶段经常用到深度优先搜索），这一类算法的过程可以用 Edsger W. Dijkstra 等人提出的三色标记算法（Tri-color marking）来进行抽象（算法详情可以参考论文：On-the-fly Garbage Collection：An Exercise in Cooperation）[2]。顾名思义，三色标记算法背后的首要原则就是把堆中的对象根据它们的颜色分到不同集合里面，这三种颜色和所包含的意思分别如下所示：

• 白色：还未被垃圾回收器标记的对象
  
• 灰色：自身已经被标记，但其拥有的成员变量还未被标记
  
• 黑色：自身已经被标记，且对象本身所有的成员变量也已经被标记
  

在 GC 开始阶段，刚开始所有的对象都是白色的，在通过可达性分析时，首先会从根节点开始遍历，将 GC Roots 直接引用到的对象 A、B、C 直接加入灰色集合，然后从灰色集合中取出 A，将 A 的所有引用加入灰色集合，同时把 A 本身加入黑色集合。最后灰色集合为空，意味着可达性分析结束，仍在白色集合的对象即为 GC Roots 不可达，可以进行回收了。下面是第一轮标记结束后，各个对象的颜色分布。

基于可达性分析的 GC 算法，标记过程几乎都借鉴了三色标记的算法思想，尽管实现的方式不尽相同，比如标记的方式有栈、队列、多色指针等。

读屏障&&写屏障

在标记对象是否存活的过程中，对象间的引用关系是不能改变的，这对于串行 GC 来说是可行的，因为此时应用程序处于 STW 状态。对于并发 GC 来说，在分析对象引用关系期间，对象间引用关系的建立和销毁是肯定存在的，如果没有其他补偿手段，并发标记期间就可能出现对象多标和漏标的情况。还是以上面三色标记法中的例子说明：
（1）多标
假设 C 被标为灰色后，在进行下面的标记之前，A 和 C 之间的引用关系解除了（应用程序），按照三色标记法，C 和 E 都应该是垃圾，而事实上，C 不会在本轮 GC 活动中被回收，这部分本应该回收但是没有回收到的内存，被称之为「浮动垃圾」。
（2）漏标
如下图所示，对象 C 在被标记为灰色后，对象 C 断开了和对象 E 之间的引用，同时对象 A 新建了和对象 E 之间的引用。在进行后面的标记时，因为 C 没有对 E 的引用，所以不会将 E 放到灰色集合，虽然 A 重新引用了 E，但因为 A 已经是黑色了，不会再返回重新进行深度遍历了。最终导致的结果是：对象 E 会一直停留在白色集合中，最后被当作垃圾回收，事实上 E 却是活动对象，这种情况也是不可接受的。

多标不会影响程序的正确性，只会推迟垃圾回收的时机，漏标会影响程序的正确性，需要引入读写屏障来解决漏标的问题。GC 里的读屏障（Read barrier）和写屏障（Write barrier）指的是程序在从堆中读取引用或更新堆中引用时，GC 需要执行一些额外操作，其本质是一些同步的指令操作，在进行读/写引用时，会额外执行这些指令。读/写屏障实现的是「对读/写引用这个操作的环切」，即该操作前后都在屏障的范畴内，可以将读/写屏障类比于 Spirng 框架里的拦截器。下面所示的代码，当从 foo 的成员变量第一次从堆上被加载时，就会触发读屏障（后续使用该引用不会触发 ），而当 bar 的成员变量(引用类型的)被分配/写入时，会触发写屏障。

void example(Foo foo) {        
    Bar bar = foo.bar;                  // 这里触发读屏障        
    bar.otherObj = makeOtherValue();   // 这里触发写屏障
}

读写屏障是如何解决并发标记时的漏标的？总结一下发生漏标的充分必要条件是：

1. 应用线程插入了一个从黑色对象（A）到白色对象（E）的新引用。
   
2. 应用线程删除了从灰色对象（C）到白色对象（E）的直接或者间接引用。
   

要避免对象的漏标，只需要打破上述两个条件中的任何一个即可，两种不同的方法核心都是采用了读写屏障：
（a）方法一：

1. 开启写屏障，当新增引用关系后，触发写屏障，发出引用的黑色或者白色对象会被标记成灰色（例子中 A 将被标记为灰色并进入灰色集合），或者将被引用对象标记为灰色。
   
2. 开启读屏障，当检测到应用即将要访问白色对象时，触发读屏障，GC 会立刻访问该对象并将之标为灰色。这种方法被称为「增量更新（Increment Update）」。
   

（b）方法二：

1. 开启写屏障。当删除引用关系前，将所有即将被删除的引用关系的旧引用记录下来（C -> E），最后以这些旧引用为根重新扫描一遍，这种方法实际上是「SATB（Snapshot At The Begining） 算法」的一种具体实现。
   

注：SATB 算法是由 Taiichi Yuasa 为增量式标记清除垃圾收集器开发的一个算法，其核心思想是：GC 开始之前，会复制一份引用关系快照，如果某个指针的地址被改变了，那么之前的地址会被加入待标记栈中，便于后面再次检查，这样就可以保证在 GC 时，所有的对象都会被遍历到，即使指向它们的指针发生了改变。鉴于篇幅原因，这里不再讲述，感兴趣的读者可自行查看 Yuasa 的论文（Real-time garbage collection on general-purpose machines[3]）。

通过读写屏障可以解决并发标记时的漏标问题，具体在工程实践中，不同的垃圾回收器又有不同实现，譬如针对 HotSpot 虚拟机，CMS 使用了「写屏障 + 增量更新」的方法，G1 和 Shenandoah是通过「写屏障 + SATB」来完成的，而 ZGC 则采取了「读屏障」的方式。
下面是 HotSpot 虚拟机中写屏障的一段代码，这段代码记录下了所有的引用关系的变化情况。

void post_write_barrier(oop* field, oop val) {    
    jbyte* card_ptr = card_for(field);    
    *card_ptr = dirty_card;  
}

需要注意的是，读/写屏障只是一种理念，触发读写屏障后具体执行什么，取决于垃圾回收器的实现。由于从堆读取引用是非常频繁的操作，因此这两种屏障需要非常高效，在常见情况下就是一些汇编代码，读屏障的开销通常比写屏障大一个数量级（这也是为何大多数 GC 没有使用或者很少使用读屏障的原因，因为引用的读操作要远多于写操作），读屏障更多的时候是用在解决并发转移时的引用更新问题上。
一些公司可能会在硬件层面对读写屏障做专门的设计，便于达到最高效的垃圾回收效率。譬如，Azul 公司为 Pauseless GC 算法专门定制了一整套系统（包括CPU、芯片组、主板和操作系统），用来运行具备垃圾收集功能的虚拟机，定制的 CPU 内置了「读屏障指令」，来实现并行的、具有碎片压缩功能的高并发(无 STW 暂停)垃圾收集算法。
注意：JVM 里还有另外一组内存屏障的概念：读屏障（Load Barrier）和写屏障（Store Barrier），这两组指令和上面我们谈及的屏障不同，Load Barrier 和 Store Barrier主要用来保证主缓存数据的一致性以及屏障两侧的指令不被重排序。
三 垃圾回收算法
这一部分将从最简单的垃圾回收算法开始，介绍垃圾回收算法的演进情况，主要介绍的算法有：

1. 标记-清除算法
   
2. 标记-压缩算法
   
3. 标记-复制算法
   
4. 分代算法
   
5. 增量算法
   
6. 并发算法
   

前三种是最基础的算法，后面三种是对前面三种算法在某些方面的改进。了解到上述这些算法后，我们可以看到，现在的很多垃圾回收器，无非是是把文中提到的几种算法进行组合或取舍。如 CMS 垃圾回收器，就是「标记-清除 + 并发算法」的组合，其全称 Concurrent Mark-Sweep 也表明了这一点，而 G1 是「标记-复制算法 + 增量算法 + 并发算法」的组合。

基础垃圾回收算法

基础的垃圾回收算法有标记-清除算法、标记-压缩算法和标记-复制算法这三种，后面两种可以视为是对标记-清除算法中「清除」阶段的优化。

标记-清除算法（Mark-Sweep）

在之前介绍三色标记法时，其实已经能看到标记-清除算法的影子了，正是因为如此，它是最简单也是最重要的一种算法。
标记-清除算法由标记阶段和清除阶段构成。标记阶段是把所有活动对象都做上标记的阶段，有对象头标记和位图标记（bitmap marking）这两种方式，后者可以与写时复制技术（copy-on-write）相兼容。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段，回收时会把对象作为分块，连接到被称为「空闲链表（free-lis）」的链表中去。
清除操作并不总是在标记阶段结束后就全部完成的，一种「延迟清除（Lazy Sweep）」的算法可以缩减因清除操作导致的应用 STW 时间。延迟清除算法不是一下遍历整个堆（清除所花费的时间与堆大小成正比），它只在分配对象时执行必要的堆遍历，同时其算法复杂度只与活动对象集的大小成正比。
下图是标记-清除算法执行前后，堆空间的变化情况：

从上图可以看到，标记-清除算法执行完成后，会让堆出现碎片化，这会带来两个问题：

• 大量的内存碎片会导致大对象分配时可能失败，从而提前触发了另一次垃圾回收动作；
• 具有引用关系的对象可能会被分配在堆中较远的位置，这会增加程序访问所需的时间，即「访问的局部性（Locality）」较差。
  

上述两个问题，将分别由下面介绍的标记-压缩算法和标记-复制算法来解决。

标记-压缩算法（Mark-Compact）

标记-压缩算法是在标记-清除算法的基础上，用「压缩」取代了「清除」这个回收过程，如下图所示，GC 将已标记并处于活动状态的对象移动到了内存区域的起始端，然后清理掉了端边界之外的内存空间。

压缩阶段需要重新安排可达对象的空间位置（reloacate）以及对移动后的对象引用重定向（remap），这两个过程都需要搜索数次堆来实现，因此会增加了 GC 暂停的时间。标记-压缩算法的好处是显而易见的：在进行这种压缩操作之后，新对象的分配会变得非常方便——通过指针碰撞即可实现。与此同时，因为 GC 总是知道可用空间的位置，因此也不会带来碎片的问题。
标记-压缩算法算法还有很多变种，如 Robert A. Saunders 研究出来的名为 Two-Finger 的压缩算法（论文：The LISP system for the Q-32 computer. In The Programming Language LISP: Its Operation and Applications[4]），可以把堆搜索的次数缩短到2次， Stephen M. Blackburn 等研究出来的 ImmixGC 算法（论文：Cyclic reference counting with lazy mark-scan[5]）结合了标记-清除和标记-压缩两种算法，可以有效地解决碎片化问题。

标记-复制算法（Mark-Copy）

标记-复制算法与标记-压缩算法非常相似，因为它们会对活动对象重新分配（reloacate）空间位置。两个算法区别是：在标记-复制算法中，reloacate 目标是一个不同的内存区域。
标记清除算法的优点很多，譬如：

1. 不会发生碎片化
   
2. 优秀的吞吐率
   
3. 可实现高速分配
   
4. 良好的 locality
   

对比算法执行前后堆空间的变化，可以看到，不难发现标记-复制算法最大缺点在于所需空间翻倍了，即堆空间的利用率很低。

标记-复制在复制阶段，需要递归复制对象和它的子对象，递归调用带来的开销是不容忽视的。C. J. Cheney 于 1970 年研究出了迭代版本的复制算法，可以抑制调用函数的额外负担和栈的消耗，感兴趣的同学可以参考论文：A Nonrecursive List Compacting Algorithm[6]。

垃圾回收算法的改进

下面介绍的三种垃圾回收算法，会针对基础算法中诸如堆碎片化、暂停时间过长、空间利用率不高等不足进行改进。

分代算法（Generational GC）

分代算法对基础算法的改进主要体现在该算法减小了 GC 的作用范围。如前所述，标记过程和对象的 reloacate 过程都需要完全停止应用程序进行堆搜索，堆空间越大，进行垃圾回收所需的时间就越长，如果 GC 的堆空间变小，应用暂停时间也会相应地降低。
**
分代算法基于这样一个假说（Generational Hypothesis）：绝大多数对象都是朝生夕灭的，该假说已经在各种不同类型的编程范式或者编程语言中得到证实了。分代算法把对象分类成几代，针对不同的代使用不同的 GC 算法：刚生成的对象称为新生代对象，对新对象执行的 GC 称为新生代 GC（minor GC），到达一定年龄的对象则称为老年代对象，面向老年代对象的 GC 称为老年代 GC（major GC），新生代对象转为为老年代对象的情况称为晋升（promotion）。注：代数并不是划分的越多越好，虽然按照分代假说，如果分代数越多，最后抵达老年代的对象就越少，在老年代对象上消耗的垃圾回收的时间就越少，但分代数增多会带来其他的开销，综合来看，代数划分为 2 代或者 3 代是最好的。

在经过新生代 GC 而晋升的对象把老年代空间填满之前，老年代 GC 都不会被执行。因此，老年代 GC 的执行频率要比新生代 GC 低。通过使用分代垃圾回收，可以改善 GC 所花费的时间（吞吐量）。
分代算法由于其普适性，已经被大多数的垃圾回收器采用（ZGC 目前不支持，但也在规划中了），其细节就不赘述了，这里我们主要关注引入分代算法后，GC 过程会出现哪些问题。

（1）问题1：不同分代在堆空间之中如何划分？
Ungar 提出的分代算法（论文：Generation Scavenging[7]）是目前使用最多的分代划分方案，该算法即为目前 CMS 垃圾回收器的原型：堆空间由 eden、survivor0/survivor1、old 共四个区域组成。Ungar 的论文里新生代 GC 采用的是标记-复制算法，主要是利用该算法高吞吐的特性；老年代 GC 使用的是标记-清除算法，因为老年代空间比整体堆要小，如果使用标记-复制算法，能利用的堆空间会变得更小。
分代算法的堆空间组织方式，不只 Ungar 这一种方案。譬如，在一些基于 Ungar 的 Generation GC 的实现中，会把老年代的最后一个代通过标记-复制算法处理（Lisp Machine），还有的算法会把最后一个代通过标记-压缩算法回收，降低复制算法出现的频繁换页的问题。

（2）问题2：如何标记代际之间的引用关系？**
分代算法引入，需要考虑跨代/区之间对象引用的变化情况。新生代对象不只会被根对象和新生代里的对象引用，也可能被老年代对象引用，GC 算法需要做到「在不回收老年代对象的同时，安全地回收新生代里面的对象」，新生代回收时，不适合也不可能去扫描整个老年代（变相搜索堆中的所有对象），否则就失去了对堆空间进行分代的意义了。

解决上述引用问题的关键是引入写屏障：如果一个老年代的引用指向了一个新生代的对象，就会触发写屏障。写屏障执行过程的伪代码如下所示，其中参数 obj 的成员变量为 field，该变量将要被更新为 new_obj 所指向的对象，记录集 remembered_sets 被用于记录从老年代对象到新生代对象的引用，新生代 GC 时将会把记录集视为 GC Roots 的一部分。

write_barrier(obj, field, new_obj){    
    if(obj.old == TRUE && new_obj.young == TRUE && obj.remembered == FALSE){        
        remembered_sets[rs_index] = obj        
            rs_index++        
            obj.remembered = TRUE    }   
    *field = new_obj
    }

在写入屏障里，首先会判断：

1. 发出引用的对象是不是老年代对象；
   
2. 目标引用标对象是不是新生代对象；
   
3. 发出引用的对象是否还没有加入记录集。
   

如果满足以上三点，则本次新建的引用关系中，老年代的对象会被加入到记录集。上述过程可能会带来「浮动垃圾」，原因是所有由老年代->新生代的引用都会被加入记录集，但老年代内对象的存活性，只有在下一次老年代GC 时才知道。
分代算法的优点在于减小了 GC 的作用范围后带来的高吞吐，但与此同时我们需要注意的是，其假说「绝大多数对象都是朝生夕灭的」并不适用于所有程序，在某些应用中，对象会活得很久，如果在这样的场景下使用分代算法，老年代的 GC 就会很频繁，反而降低了 GC 的吞吐。此外，由于在记录代际引用关系时引入了写屏障，这也会带来一定的性能开销。

增量算法（Incremental GC）

增量算法对基础算法的改进主要体现在该算法通过并发的方式，降低了 STW 的时间。下图是增量算法和基础的标记-清除算法在执行时间线上的对比，可以看到，增量算法的核心思想是：通过 GC 和应用程序交替执行的方式，来控制应用程序的最大暂停时间。

增量算法的「增量」部分，主要有「增量更新（Incremental Update）」和「增量拷贝（Incremental Copying）」两种，前者主要是做「标记」增量，后者是在做「复制」增量。
增量更新（Incremental Update）我们已经比较熟悉了，在介绍读/写屏障的时候，我们提到过由于存在并发，会出现对象漏标的情况。同样的，在增量算法中，由于 GC 线程和应用线程是交替执行的，也会出现黑色节点指向白色节点的情况，增量算法中的漏标，同样是通过写屏障来解决的，主要有以下两种（基于快照的 SATB 也可以解决增量更新时出现的漏标，在此不再赘述）。
（1）写入屏障1（Dijkstra 写入屏障）

write_barrier(obj, field, new_obj){    
    if(new_obj == FALSE){        
        new_obj.mark == TRUE        
            push(new_obj, mark_stack)    
        }   *field = new_obj
    }

在上面的代码中，如果新引用的对象 new_obj 没有被标记过，会将它标记后放到 mark_stack 这个标记栈中，对比三色标记法，就是将这个新对象从白色对象涂成了灰色（下图中的 E）。

（2）写入屏障2（Steele 写入屏障）

write_barrier(obj, field, new_obj){    
    if(obj.mark == TRUE && new_obj == FALSE){        
        obj.mark = FALSE        
            push(obj, mark_stack)    
        }   
    *field = new_obj
    }

在上面的代码中，如果新引用的对象 new_obj 没有被标记过，且将要引用它的对象 obj 已经被标记过了，那么会把发出引用的对象去除标记，将其放入标记栈中，对比三色标记法，就是将发出引用的对象从黑色涂成了灰色（下图中的 A）。

Steele 的写入屏障相较于 Dijkstra 的写入屏障来说，多了一个判断条件，缺点是带来的额外的负担，优点是严格的条件减少了被标记的对象的个数，防止了因疏忽而造成垃圾残留的后果，譬如 A 和 E 引用关系被标记后，如果 E 在本轮标记过程中又称为了垃圾，Dijkstra 的写入屏障还需要对 E 及其子节点进行标记，而 Steele 的写入屏障就避免了这一点。
增量拷贝（Incremental Copying）大部分逻辑与标记-复制算法相似，还是会通过遍历引用关系图，把所有引用的对象拷贝到另一半堆内存，不过这个过程是并发执行的。当应用程序访问到老的堆空间对象时，会触发读屏障，对象会从老的空间被拷贝至新的堆空间。
增量算法中大量使用了读写屏障（主要是写屏障），给应用程序带来了负担，结果就是 GC 的吞吐相较于其他的算法来说不高。

并发算法（Concurrent GC）

广义上的并发算法指的是在 GC 过程中存在并发阶段的算法，如 G1 中存在并发标记阶段，可将其整个算法视为并发算法。
狭义上的并发垃圾回收算法是以基础的标记-复制算法为基础，在各个阶段增加了并发操作实现的。与复制算法的3个阶段相对应，分为并发标记（mark）、并发转移（relocate）和并发重定位（remap）:
（1）并发标记
从 GC Roots 出发，使用遍历算法对对象的成员变量进行标记。同样的，并发标记也需要解决标记过程中引用关系变化导致的漏标记问题，这一点通过写屏障实现；
（2）并发转移
根据并发标记后的结果生成转移集合，把活跃对象转移（复制）到新的内存上，原来的内存空间可以回收，转移过程中会涉及到应用线程访问待转移对象的情况，一般的解决思路是加上读屏障，在完成转移任务后，再访问对象；
（3）并发重定位
对象转移后其内存地址发生了变化，所有指向对象老地址的指针都要修正到新的地址上，这一步一般通过读屏障来实现。

并发算法是 ZGC、Shenandoah、C4 等垃圾回收器的算法基础，在具体的实现中，不同的垃圾回收器又有自己的选择和取舍。
至此，GC 算法的理论知识就告一段落了，有一些知识点是没有提到的，如部分标记-清除算法（Partial Mark & Sweep）的原理、保守式 GC（Conservative GC）对数据和指针的识别、基于引用计数法的若干 GC 算法等，感兴趣的同学可以参考文中列出的论文。 相关链接> [1]http://flyingfrogblog.blogspot.com/2011/01/boosts-sharedptr-up-to-10-slower-than.html

[2]https://lamport.azurewebsites.net/pubs/garbage.pdf [3]https://www.sciencedirect.com/science/article/pii/016412129090084Y [4]https://www.semanticscholar.org/paper/The-lisp-system-for-the-q-32-computer-Saunders/ad2b04c404dc40e142332a030a146b487b6e3cf2 [5]https://www.sciencedirect.com/science/article/pii/002001909290088D [6]https://dl.acm.org/doi/10.1145/362790.362798 [7]https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p157-ungar.pdf

下面是第二篇，垃圾回收器实现篇，和常见的垃圾回收器。

实现篇

一 垃圾回收器简介

工业界的垃圾回收器，一般都是上篇中几种垃圾回收算法的组合实现。下图中列举了最常见及最新的几种垃圾回收器，大多数的垃圾回收器均采用了分代设计（或者适用于分代场景），且一般有固定的搭配使用模式，每种垃圾回收器的用法和特性在这里就不赘述了，有需要的话可以参考其他资料。图中的垃圾回收器，还需要补充的一些内容有：

• CMS 是适用于老年代的垃圾回收器，虽然在回收过程中可能也会触发新生代垃圾回收。CMS 在 JDK 9中被声明为废弃的，在JDK 14中将被移除；
• Parallel Scavenge 和大部分垃圾回收器都不兼容，原因是其实现未基于 HotSpot VM 框架；
• Parallel Scavenge + Parallel Old 的组合有自适应调节策略，适用于对吞吐量敏感的场景；
• C4 和 ZGC 可以视为是同一种垃圾回收算法的不同实现，ZGC 目前还没有分代设计（规划中）；
• C4、ZGC、Shenandoah GC 的垃圾回收算法在多处是趋同的，同时各自也有比较独特的设计理念。
  

各种垃圾回收器和垃圾回收算法间的关系如下：

• Serial：标记-复制
  
• Serial Old：标记-压缩
  
• ParNew：标记-复制
  
• Parallel Scavenge：标记-复制
  
• Parallel Old：标记-压缩
  
• CMS（Concurrent-Mark-Sweep）：（并发）标记-清除
  
• G1（Garbage-First）：并发标记 + 并行复制
  
• ZGC/C4：并发标记 + 并发复制
  
• Shenandoah GC：并发标记 + 并发复制
  

可以看到，如果堆空间进行了分代，那么新生代通常采用复制算法，老生代通常采用压缩-复制算法。G1、C4、ZGC、Shenandoah GC 是几种比较新的垃圾回收器，下面会结合算法实现，分别介绍这四种垃圾回收器的核心原理。

二 G1 垃圾回收器

G1是从JDK 7 Update 4及后续版本开始正式提供的，从JDK 9开始G1作为默认的垃圾回收器。
G1 的垃圾回收是分代的，整个堆分成一系列大小相等的分区（Region）。新生代的垃圾回收（Young GC）使用的是并行复制的方式，一旦发生一次新生代回收，整个新生代都会被回收（根据对暂停时间的预测值，新生代的大小可能会动态改变）。老年代回收不会回收全部老年代空间，只会选择一部分收益最高的 Region，回收时一般会搭便车——把待回收的老年代 Region 和所有的新生代 Region 放在一起进行回收，这个过程一般被称为 Mixed GC，Young GC 和 Mixed GC 最大的不同就在于是否回收了老年代的 Region。注意：Young GC 和 Mixed GC 都是在进行对象标记，具体的回收过程与这两个过程是独立的，回收时 GC 线程会根据标记的结果选择部分收益高的 Region 进行复制。从某种角度来说，G1 可视为是一种「标记-复制算法」的实现（注意这里不是压缩算法，因为 G1 的复制过程完全依赖于之前标记阶段对对象生死的判定，而不是自行从 GC Roots 出发遍历对象引用关系图）。
G1 老年代的标记过程大致可以分为下面四个阶段：

1. 初始标记阶段（STW）
   
2. 并发标记阶段
   
3. 再标记阶段（STW）
   
4. 清理阶段（STW）
   

上面的四个阶段中，有三个阶段都是 STW 的，每个阶段的内容就不具体叙述了。为了降低标记阶段中 STW 的时间，G1 使用了记录集（Remembered Set, RSet）来记录不同代际之间的引用关系。在并发标记阶段，GC 线程和应用线程并发运行，在这个过程中涉及到引用关系的改变，G1 使用了 SATB（Snapshot-At-The-Beginning） 记录并发标记时引用关系的改变，保证并发结束后引用关系的正确性。实现 RSet 和 SATB 的关键就是之前提到的写屏障。
G1 中的写屏障分为 pre_write_barrier 和 post_write_barrier，如下面的代码所示，应用 field 将要被赋予新值 value，由于 field 指向的旧的引用对象会丢失引用关系，因此在赋值之前会触发 pre_write_barrier，更新 SATB 日志记录，记录下引用关系变化时旧的引用值；在正式赋值之后，会执行 post_write_barrier，更新新引用对象所在的 RSet。

// 赋值操作，将 value 赋值给 field 所在的引用
void assign_new_value(oop* field, oop value) {    
    pre_write_barrier(field);         // 步骤1  
    *field = value;                   // 步骤2  
    post_write_barrier(field, value); // 步骤3
}

SATB 和 RSet 的更新都是通过写屏障来实现的，但是更新操作并不都是在屏障里做的，否则会对应用线程造成很大的干扰。G1 中的写屏障实现为线程队列+全局队列的两级结构，当写屏障触发后，记录会首先加入到线程队列（线程队列是独立、定长的）中，线程队列区满了后，就会加入到全局队列区里，换一个新的、干净的队列继续执行下去，全局队列里的记录超过一定的阈值，相关线程就会去做相应处理（更新 RSet 或是将记录压入标记栈中）。

RSet

首先来看一下 RSet，这个数据结构是为了记录对象代际之间的引用关系而提出的，目的是加速垃圾回收的速度。引用关系的记录方式通常有两种方式：「我引用了谁」和「谁引用了我」，前一种记录简单，但是在回收时需要对记录集做全部扫描，后一种记录复制，占用空间大，但是在回收时只需要关注对象本身，即可通过 RSet 直接定位到引用关系。G1 的 RSet 使用的是后一种「谁引用了我」的记录方式，其数据结构可理解为一个哈希表。每次向引用类型字段赋值时，会触发：「写屏障 -> 线程队列 -> 全局队列 -> 并发 RSet 更新」这样一个过程。
G1 RSet 记录的是对象之间的引用关系，那到底需要记录哪些引用关系呢？

• Region 内部的引用：无需记录，因为垃圾回收时 Region 内对象肯定要扫描的；
  
• 新生代 Region 间的引用：无需记录，因为新生代在 Young GC 和 Mixed GC 中都会被整体回收：
  
• 老年代 Region 间的引用：需要记录，因为老年代回收时是按 Region 进行回收的，因此需要记录；
  
• 新生代 Region 到老年代 Region 的引用：无需记录，Mixed GC 中会把整个新生代作为 GC Roots；
  
• 老年代 Region 到新生代 Region 的引用：需要记录，Young GC 时直接将这种引用加入 GC Roots。
  

具体在回收时，RSet 的作用是这样的：进行 Young GC 时，选择新生代所在的 Region 作为 GC Roots，这些 Region 中的 RSet 记录了老年代->新生代的的跨代引用（「谁引用了我」），从而可以避免了扫描整个老年代。进行 Mixed GC 时，「老年代->老年代」之间的引用，可以通过待回收 Region 中的 RSet 记录获得，「新生代->老年代」之间的引用通过扫描全部的新生代获得（前面提到过 Mixed GC 会搭 Young GC 的便车），也不需要扫描全部老年代。总之，引入 RSet 后，GC 的堆扫描范围大大减少了。

SATB

SATB 在算法篇介绍过，其实就是在一次 GC 活动前所有对象引用关系的一个快照。之所以需要快照，是因为并发标记时，GC 线程一边在标记垃圾对象，应用线程一边还在生成垃圾对象，如果我们记录下快照，以及并发标记期间引用发生过变更的对象（包括新增对象和引用发生变更的对象），则我们就可以实现一次完整的标记。
SATB 的过程可以简单理解为：当并发标记阶段引用的关系发生变化时，旧引用所指向的对象就会被标记，同时其子引用对象也会被递归标记，这样快照的完整性就得到保证了。SATB 的记录更新是由 pre_write_barrier 写屏障触发的，下面是 G1 论文中介绍的 SATB 原始表述，具体实现时，还是由两级的队列结构缓存，再由并发标记线程批量处理进入标记队列 satb_mark_queue。

void pre_write_barrier(oop* field) {    
    oop old_value = *field;    
    if (old_value != null) {      
        if ($gc_phase == GC_CONCURRENT_MARK) {      
            $current_thread->satb_mark_queue->enqueue(old_value);      
        }    
    }  
}

因此，G1 在结束并发标记后还有一个需要 STW 的再标记（remark）阶段就可以理解了，因为如果不引入一个 STW 的过程，那么新的引用变更会不断产生，永远就无法达成完成标记的条件。再标记阶段，因为有了SATB 的设计，则只需要扫描 satb_mark_queue 队列里的引用变更记录就可以对此次 GC 活动形成完整标记了（可以对比 CMS 的 remark 阶段）。

三 ZGC/C4 垃圾回收器

G1 目前的发展已经相当成熟了，从众多的测评结果上看，也达到了其最初的设计目标。但是 G1 也有下面这些不足之处：

• 堆利用率不高：原因就是引入的 RSet 占用内存空间较大，一般会达到1%~20%；
  
• 暂停时间较长：通常 G1 的 STW 时间要达到几十到几百毫秒，还不够低。
  

G1 由于使用了并发标记，因此标记阶段对暂停时间的影响较小，暂停时间主要来自于标记阶段结束后的 Region 复制（一般占用整个 GC STW 的 80%），这个阶段使用的是复制算法：GC 把一部分 Region 里的活的对象复制到空 Region 里去，然后回收原本的 Region的空间。上述过程是无法并发进行的（并发复制一般需要通过「读屏障」来实现，G1 并未使用），因为需要一边移动对象，同时一边修正指向这些对象的引用（并发期间应用线程可能会访问到这些对象），G1 虽然在复制对象时也做到了并行化，但大量对象的复制会涉及到很多内存分配、变量复制的操作，非常耗时。
ZGC 就是针对上述 G1 的不足提出的，2017 年 Oracle 将 ZGC 贡献给 OpenJDK 社区，2018年 JEP-333 正式引入：ZGC: A Scalable Low-Latency Garbage Collector (Experimental)。ZGC 的设计思路借鉴了一款商业垃圾回收器——Azul Systems公司的的 C4（Continuously Concurrent Compacting Collector） 垃圾回收器，后者是一款分代式的、并发的、协作式垃圾回收算法，目前只在 Azul System 公司的 Zing JVM 得到实现，详细介绍请参考论文：http://go.azul.com/continuously-concurrent-compacting-collector。ZGC 和 C4 背后的算法均是 Azul Systems 很多年前提出的 Pauseless GC，区别在于 C4 是一种分代的实现，而 ZGC 现在还是不分代的。
ZGC 可以视为是一种「标记-复制」算法的并发实现，其中标记阶段是并发的，复制阶段又分为转移（Relocate）和重定位（Remap）两个子阶段，也都是并发的，通过全程并发，可以让暂停时间保持在10ms以内。标记和复制看上去是两个串行的阶段，其实也是有重叠的，譬如重定位（remap）阶段实际上被合并到标记阶段中，即在标记的时候如果发现对象引用到老的地址，这时会先完成重定位更新对象的引用关系，然后再标记对象。
下面具体来看一下 ZGC 是如何高效地设计并发操作的。

算法设计

SATB

ZGC 在进行并发标记和并发复制时也会面临引用关系改变造成的「漏标」和「漏转移」，解决的方法是引入 SATB，和 G1 中通过写屏障实现的 SATB 不同，ZGC 是通过「读屏障」+「多视图映射」来实现 SATB 的。读屏障在算法篇已经介绍过了，它发生在从堆上加载一个对象引用时，后续使用该引用不会触发读屏障。
读屏障是实现 SATB 的关键，除此之外，ZGC 引入读屏障后，也实现了对象的并发复制，弥补了 G1 垃圾回收算法中最大的不足。读屏障和写屏障解决的问题是不一样的，标记-清除算法是不需要读读屏障的，因为没有内存移动的过程（压缩或者复制），但是对于复制算法，如果不用读屏障去跟踪读的情况，并发执行的应用线程可能就会读取到错误的引用。引入读屏障后，GC 线程可以并发执行，应用读取的引用如果发生了转移或者修改，可以在读屏障内完成内存的转移或者重定位，也就不会出现长时间的 STW 了。
可以通过从堆空间中加载对象的执行代码这里对读屏障有更直观的感受，这里调用的load_barrier_on_oop_field_preloaded 就是读屏障。

template <DecoratorSet decorators, typename BarrierSetT>
template <typename T>
inline oop ZBarrierSet::AccessBarrier<decorators, BarrierSetT>::oop_load_in_heap(T* addr) {
  verify_decorators_absent<ON_UNKNOWN_OOP_REF>();
  const oop o = Raw::oop_load_in_heap(addr);
  return load_barrier_on_oop_field_preloaded(addr, o);
}

读屏障触发后，SATB 的具体执行细节就不展开了，SATB 虽然实现的方式不一样，如 G1 中是通过写屏障实现的，但是其核心思想是一致的：标记开始后，把引用关系快照里所有的活对象都看作是活的，如果出现了引用关系变更，则把旧的引用所指向的对象进行标记或记录下来。
读屏障的开销是很大的，因为堆的读操作频率是远高于写操作的，ZGC 是如何对对象进行标记，实现高效的 SATB 算法的呢？答案是上面提到过的「多视图映射」，下面简单介绍下。

多视图映射

和 G1 一样，ZGC 将内存划分成小的分区，在ZGC中称为页面（page），但是 ZGC 中的页面大小并不是固定的，分为小页面、中页面和大页面，其中小页面大小为 2MB，中页面大小为 32MB，而大页面则和操作系统中的大页面的大小一致。
多视图映射指的是在 ZGC 的内存管理中，同一物理地址的对象可以映射到多个虚拟地址上，虚拟地址有 Marked0、Marked1 和 Remapped 三种，在 ZGC 中这三个虚拟空间在同一时间点有且仅有一个空间有效。下表中显示了这三个地址空间的范围，[0~4TB)对应的是Java的堆空间，该虚拟地址对应用程序可见，经 ZGC 映射后，真正使用的就是 Marked0、Marked1 和 Remapped 这三个视图对应的地址空间，这三个视图的切换是由垃圾回收的不同阶段触发的。

+--------------------------------+ 0x0000140000000000 (20TB)
|         Remapped View          |
+--------------------------------+ 0x0000100000000000 (16TB)
|     (Reserved, but unused)     |
+--------------------------------+ 0x00000c0000000000 (12TB)
|         Marked1 View           |
+--------------------------------+ 0x0000080000000000 (8TB)
|         Marked0 View           |
+--------------------------------+ 0x0000040000000000 (4TB)

既然多个视图映射的是同一个物理对象，那么就需要对引用（指针）进行若干改造，ZGC 在堆引用（指针）上增加了若干元数据信息：前42位保留为对象的实际地址（在源代码中作为偏移量引用），42位地址理论上提供了4TB的堆限制，其余的位用于标记：Finalizable、Remapped、Marked1 和 Marked0 (保留一位以备将来使用)，这种引用也被称为着色指针（Color Pointers）。

6                  4 4 4   4 4                                             0
3                  7 6 5   2 1                                             0
+-------------------+-+----+-----------------------------------------------+
|00000000 00000000 0|0|1111|11 11111111 11111111 11111111 11111111 11111111|
+-------------------+-+----+-----------------------------------------------+
|                  | |    |
|                  | |    * 41-0 Object Offset (42-bits, 4TB address space)
|                   | |
|                  | * 45-42 Metadata Bits (4-bits)  0001 = Marked0
|                  |                                 0010 = Marked1
|                  |                                 0100 = Remapped
|                  |                                 1000 = Finalizable
|                  |
|                  * 46-46 Unused (1-bit, always zero)
|
* 63-47 Fixed (17-bits, always zero)

为什么要使用多视图映射呢？最直接的好处就是可以加快标记和转移的速度。比如在标记阶段，标记某个对象时只需要转换地址视图即可，而地址视图的转化非常简单，只需要设置地址中第42~45位中相应的标记位即可。而在以前的垃圾回收器实现中，需要修改相应对象头的标记位，而这会有内存存取访问的开销。在 ZGC 标记对象中无须任何对象访问，这就是ZGC在标记和转移阶段速度更快的原因。
把读屏障、 SATB 和多视图映射放在一起，可以总结 ZGC 中的并发算法的核心要点为：

• SATB 保证了在并发标记和并发复制阶段引用变更的正确性；
  
• 在并发标记阶段，通过标记引用（指针）实现对对象的遍历；
  
• 在并发转移阶段，读屏障会保证并发转移时应用线程读出的指针为对象的新地址；
  
• 在并发重定位阶段，读屏障会保证应用线程可以获取到转移后的对象的新地址。
  

引用 R 大（RednaxelaFX）的话就是：与标记对象的传统算法相比，ZGC 在指针上做标记，在访问指针时加入 Load Barrier（读屏障），比如当对象正被 GC 移动，指针上的颜色就会不对，这个屏障就会先把指针更新为有效地址再返回，也就是，永远只有单个对象读取时有概率被减速，而不存在为了保持应用与 GC 一致而粗暴整体的 Stop The World。

算法实现

下面通过一个简单的例子看了解 ZGC 的并发执行过程。

第一次执行并发标记前，整个内存空间的地址视图被设置为 Remapped，并发标记结束后，对象的地址视图要么是 Marked0，要么是 Remapped。

• 如果地址视图是 Marked0，说明对象是在标记阶段被标记或者是新创建的；如上图所示 A、B 对象均可以通过 GC Roots 访问到，属于活跃的对象，对象 D 在并发期间被创建，也属于活跃对象，均被映射到 Marked0 地址视图；
  
• 如果地址视图是 Remapped，说明对象在标记阶段既不能通过根集合访问到（直接或间接访问），也没有应用线程访问它，所以是不活跃的，即对象所使用的内存可以被回收。上图中的对象 C 不能从 GC Roots 访问，属于不活跃对象，地址视图还是 Remapped，表示为垃圾对象。
  

在并发标记期间，如果应用线程访问对象且对象的地址视图是 Remapped，说明对象是前一阶段分配的，只要把该对象的视图从 Remapped 调整为 Marked0 就能防止对象漏标。
标记阶段结束后，所有活跃对象的地址会被存储在一个「对象活跃信息表」的集合中，然后进入并发转移（Relocated）阶段。转移阶段转移线程会从「对象活跃信息表」中把活跃对象转移到新的内存中，并回收对象转移前的内存空间（注意：如果页面不需要转移，那么页面里面的对象也就不需要转移）。并发转移结束后，对象的地址视图要么是 Remapped，要么是 Marked0。

• 如果地址视图是 Marked0，说明该对象在垃圾回收的标记阶段已经被标记，但是在转移阶段未被转移（如下图中的 B 和 D）；
  
• 如果地址视图是 Remapped，说明对象在并发转移阶段被转移或者被访问过（如下图中的 G 和 F，C 因为不活跃可能就直接被回收了）。
  

在并发转移阶段，如果应用线程访问的对象在对象活跃信息表中，且对象的地址视图为 Marked0，说明对象是标记阶段标记的活跃对象，所以需要转移对象，对象转移以后，对象的地址视图从 Marked0 调整为 Remapped。

并发转移结束后，会再次进入下一次的标记阶段。新的标记阶段为了区分「本次标记的活跃对象」和「上次标记的活跃对象」，使用了 Marked1 来标识本次并发标记的结果，即：用 Marked1 表示本次垃圾回收中识别的活跃对象（上图中的 H 和 F），用 Marked0 表示前一次垃圾回收的标记阶段被标记过的活跃对象，且该对象在转移阶段未被转移，但是在本次垃圾回收中被识别为不活跃对象（上图中的 B 和 D）。注意：在并发转移完活跃对象之后，引用还指向对象转移之前的地址，ZGC 通过「对象转移地址信息表」存储页面对象转移前和转移后的地址，在新一轮垃圾回收启动后，在标记时会执行重定位的操作。
ZGC 虽然是全程并发设计的，但也还是有若干个 STW 的阶段的，包括并发标记中的初始化标记和结束标记阶段，并发转移中的初始转移阶段等。事实上，完全没有 STW 的垃圾回收器是不存在的，即便是 Azul 的 PGC（原汁原味基于 Pauseless GC 算法实现），也是有非常短暂的 STW 阶段，譬如 GC Roots 的扫描。

四 Shenandoah 垃圾回收器

Shenandoah GC 最早是由 Red Hat 公司发起的，后来被贡献给了 OpenJDK，2014 年通过 JEP-189：A Low-Pause-Time Garbage Collector (Experimental)正式成为 OpenJDK 的开源项目，Shenandoah GC 出现的时间比 ZGC 要早很多，因此发展的成熟度和稳定性相较于 ZGC 来说更好一些，实现了包括括C1屏障、C2屏障、解释器、对 JNI 临界区域的支持等特性。
和 ZGC 一样，Shenandoah GC 也聚焦在解决 G1 中产生最长暂停时间的「并行复制」问题，通过与 ZGC 不一样的方式，实现了「并发复制」，在 Shenandoah GC 中也未区别年轻代与老年代。ZGC实现并发复制的关键是：读屏障 + 基于着色指针（Color Pointers）的多视图映射，而 Shenandoah GC 实现并发复制的关键是：读写屏障 + 转发指针（Brook Pointers），转发指针（Brook Pointers）的原理将在下面详细介绍，其过程可以参考论文：Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware。
Shenandoah GC 的 回收周期和 ZGC 非常类似，大致也可以分为并发标记和并发复制两个阶段，在并发标记阶段，也是通过 读屏障+ SATB 来实现的，并发复制阶段也分为并发转移和并发重定位两个子阶段。

算法设计

并发标记阶段的 SATB 在这里就不详细介绍了，这里主要看一下 Shenandoah GC 是如何实现并发复制的。
Shenandoah GC 将堆分成大量同样大小的分区（Region） ，分区大小从 256KB 到 32MB不等。在进行垃圾回收时，也只是会回收部分堆区域。上面提到，Shenandoah GC 实现高效读屏障的关键是增加了 转发指针（Brook Pointers）这个结构，这是对象头上增加的一个额外的数据，在读写屏障触发时时可以通过 Brook Pointer 直接访问对象。转发指针要么指向对象本身，要么指向对象副本所在的空间，如下图所示：

Shenandoah GC 使用写屏障+转发指针完成了并发复制，其过程可以用下面的伪代码表示：

stub evacuate(obj) {
    if(in-colleciton-set(obj) && fwd-ptrs-to-self(obj)) {
        copy = copy(obj);
        CAS(fwd-ptr-addr(obj), obj, copy);
    }
}

上面并发转移的详细过程如下：首先判断待转移对象是否在待回收集合中（这个集合根据标记阶段的结果生成），同时转移指针是否指向了自己，如果没有在待收回集合，则不用转移，如果对象的转移指针已经指向了其他地址，说明已经转移过了，也不用转移；然后进行对象复制；对象复制结束后，会通过 CAS 的方式更新转移指针的值，使其指向新的复制对象所在的堆空间地址，如果 CAS 失败，会多次重试。
Shenandoah GC 使用读屏障+转发指针保证转移过程中或转移结束后，应用线程可以读取到真实的引用地址，保证了数据的一致性，因为如果不这样做，可能会导致一些线程使用旧对象，而另一些线程使用新对象。
需要注意的是，在 ZGC 中并发重定位和并发标记阶段是重合的，而在 Shenandoah GC 在某些情况下，可能会把并发标记、并发转移和并发重定位合并到同一个并发阶段内完成，这种回收方式在 Shenandoah GC 中被称为遍历回收，细节请参考相关资料。如下图所示，第1个回收周期会进行并发标记，第2回收周期会进行并发标记和并发转移，第3个以后的回收周期会同时执行并发标记、并发转移和并发重定位。

算法实现

我们来看一下并发复制的具体过程。
步骤1：将对象从 From 复制到 to 空间，同时将新对象的转移指针指向新对象自己。

步骤2：将旧对象的转移指针通过 CAS 的方式指向新对象。

步骤3：将堆中其他指向旧对象的引用，更新为新对象的地址，如果在这个过程中有应用线程访问到了旧对象，则会通过读屏障的方式将新对象的地址返回给新的应用。

步骤4：所有的引用被更新，旧对象所在的分区可以被回收。

再次回顾一下 Shenandoah GC 里使用的各种屏障：读对象时，会首先通过读屏障来解析对象的真实地址，当需要更新对象（或对象的字段），则会触发写屏障，将对象从 From 空间复制到 to 空间。读写屏障在底层的应用，可以用下面的一个例子去理解。

void updateObject(Foo foo) {
  // 读操作
  Bar b1 = foo.bar;
  // 读操作
  Baz baz = b1.baz;
  // 写操作         
  b1.x = makeSomeValue(baz);  
}

Shenandoah GC 中读写屏障出现的位置：

void updateObject(Foo foo) {
  // 读屏障
  Bar b1 = readBarrier(foo).bar;             
  // 读屏障
  Baz baz = readBarrier(b1).baz;             
  X value = makeSomeValue(baz);
  // 写屏障
  writeBarrier(b1).x = readBarrier(value);  
}

一言以蔽之，Shenandoah GC 的并发复制是基于读屏障+写屏障共同实现的（ ZGC 只使用了读屏障）。Shenandoah GC 中所有的数据写操作均会触发写屏障，包括对象写、获取锁、hash code 的计算等，因此在具体实现时 Shenandoah GC 对写屏障也有若干的优化（譬如从循环逻辑中移除写屏障）。Shenandoah GC 还使用了一种称之为「比较屏障」的机制来解决对象引用间的比较操作，特别是同一个对象分别处于 From 和 to 空间时的比较。此外，Shenandoah GC 里屏障也不需要特殊的硬件支持和操作系统支持。

Shenandoah GC 更适合用在大堆上，如果CPU资源有限，内存也不大，比如小于20GB，那么就没有必要使用Shenandoah GC。Shenandoah GC 在降低了暂停时间的同时，也牺牲了一部分的吞吐，如果对吞吐有较高的要求，则还是建议使用传统的基于 STW 的 GC 实现，譬如 Parallel 系列垃圾回收器。

五 总结与回顾

在这一篇文章中，我们看到了几种比较前沿的垃圾回收器：G1/C4/ZGC/Shenandoah GC，在它们的诸多实现细节中，我们也可以看到 Java 垃圾回收器的一大技术趋势：在大内存的前提下，通过并发的方式降低 GC 算法在标记和转移对象时对应用程序的影响。CMS 做到了并发标记，G1降低了并发标记的成本，同时还通过并行复制的方式对部分堆内存进行了整理，ZGC、C4、Shenandoah GC 进一步降低了并发标记时的 STW 的时间，同时通过并发复制的方式将对象转移时的暂停时间最小化。并发算法降低了应用暂停的时间，但与此同时我们也需要看到：并发算法可以正常执行的前提是「垃圾回收的速度大于对象的分配速度」，这也就意味着并发算法需要更大的堆空间，同时需要预留部分空间用来「喘息」。
在并发算法中，读写屏障和SATB是非常关键的，它们共同保证了并发操作时引用关系的正确性，相信通过对上述垃圾回收器的介绍，可以对这几个概念理解得更加透彻。 参考资料>

[1]http://dinfuehr.github.io/blog/a-first-look-into-zgc/> [2]https://rkennke.wordpress.com/2013/06/10/shenandoah-a-pauseless-gc-for-openjdk/> [3]https://shipilev.net/talks/devoxx-Nov2017-shenandoah.pdf> [4]http://go.azul.com/continuously-concurrent-compacting-collector> [5]https://dl.acm.org/doi/10.1145/800055.802042> [6]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.6386&rep=rep1&type=pdf> [7]https://www.infoq.com/articles/tuning-tips-G1-GC/> [8]https://developers.redhat.com/blog/2019/06/27/shenandoah-gc-in-jdk-13-part-1-load-reference-barriers/