这次彻底讲透JVM垃圾回收算法底层原理

如果大家关注 JDK，会发现在频繁发布的 JDK 版本中，和垃圾回收相关的 JEP （DK Enhancement Proposals,Java 增强提案）越来越多了，垃圾回收（Garbage Collection, GC）正处于方兴未艾的阶 段。譬如，在 JEP-248 中 G1 替代了并行垃圾回收器成为 JVM 中默认的垃圾回收器，JEP-333 加入了实验 性质的 ZGC；最新的 JEP-189 引入了名为 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、Perl 等。 基于可达性分析法的 GC 垃圾回收的效率较高，实现起来比较简单（引用计算法是算法简单，实现较 难），但是其缺点在于 GC 期间，整个应用需要被挂起（STW,Stop-the-world，下同），后面很多此类 算法的提出，都是在解决这个问题（缩小 STW 时间）。

基于引用计数法的 GC，天然带有增量特性（incremental），GC 可与应用交替运行，不需要暂停应用； 同时，在引用计数法中，每个对象始终都知道自己的被引用数，当计数器为 0 时，对象可以马上回收， 而在可达性分析类 GC 中，即使对象变成了垃圾，程序也无法立刻感知，直到 GC 执行前，始终都会有一 部分内存空间被垃圾占用。 上述两类 GC 各有干秋，真正的工业级实现一般是这两类算法的组合，但是总体来说，基于可达性分析的 GC 还是占据了主流，究其原因，首先，引用计数算法无法解决「循环引用无法回收」的问题，即两个对 象互相引用，所以各对象的计数器的值都是 1，即使这些对象都成了垃圾（无外部引用），GC 也无法将 它们回收。当然上面这一点还不是引用计数法最大的弊端，引用计数算法最大的问题在于：计数器值的 增减处理非常繁重，譬如对根对象的引用，此外，多个线程之间共享对象时需要对计数器进行原子递增/ 递减，这本身又带来了一系列新的复杂性和问题，计数器对应用程序的整体运行速度的影响。 后面介绍的垃圾回收算法，主要就是可达性分析类算法及其变种。

在深入研究垃圾回收算法的实现细节之前，有必要知道 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 本身加入黑色集合。最后灰色集合为空，意味看可达性分析结束，仍在白色集 合的对象即为 GCRoots 不可达，可以进行回收了。下面是第一轮标记结束后，各个对象的颜色分布。

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

在标记对象是否存活的过程中，对象间的引用关系是不能改变的，这对于串行 GC 来说是可行的，因为此 时应用程序处于 STW 状态。对于并发 GC 来说，在分析对象引用关系期间，对象间引用关系的建立和销 毁是肯定存在的，如果没有其他补偿手段，并发标记期间就可能出现对象多标和漏标的情况。还是以上 面三色标记法中的例子说明：

假设 C 被标为灰色后，在进行下面的标记之前，A 和 C 之间的引用关系解除了（应用程序），按照三色 标记法，C 和 E 都应该是垃圾，而事实上，C 不会在本轮 GC 活动中被回收，这部分本应该回收但是没有 回收到的内存，被称之为「浮动垃圾」。