JVM 八股之首:三大垃圾收集算法-技术圈

前文介绍过，基于分代收集理论的指导，我们才可以针对堆中不同的区域，设计出不同的垃圾收集算法，主要有以下三种：

标记-清除算法
标记-复制算法
标记-整理算法

全文思维导图如下：

老规矩，背诵版在文末

标记-清除算法，Mark-Sweep

“标记-清除”（Mark-Sweep）算法是最基础的垃圾收集算法，在 1960 年由 Lisp 之父 John McCarthy 所提出，后面所介绍的两种算法都是基于此改进而来。

不难理解，从名称上就已经能看出，整个算法分为两个大步骤：

标记 and 清除。

拓展来说：

标记，Mark：指的是标记出所有需要回收的对象（也就是判断对象是否是垃圾，这个前文已经说过了，有两种方法：引用计数法和可达性分析，由于引用计数法无法解决循环引用问题，所以目前主流的虚拟机采用的都是可达性分析法）
清除，Sweep：指的是在标记完成后，统一回收掉所有被标记的对象

当然了，反过来也是可以的，标记存活的对象，统一回收所有未被标记的对象。

我们说这个标记-清除算法是最基础的垃圾收集算法奥，后面两种算法都是基于此改进而来，那么改进改进，既然是改进，这个基础的算法一定是存在一些问题，才能够有改进的空间，对吧。

标记-清除算法的主要缺点有两个：

First：执行效率不稳定。如果堆中包含大量对象，而且其中大部分是需要被回收的，这时就必须进行大量的标记和清除的动作，导致标记和清除两个过程的执行效率都辉随着对象数量的增长而降低，也就是执行效率和对象数量成反比。
Second：内存空间的碎片化问题。标记、清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致当程序运行过程中需要分配较大对象时，因无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

标记-清除算法的执行过程如图：

标记-复制算法，Mark-Copy

“标记-复制”（Mark-Copy）算法常被简称为复制算法。

为了解决标记-清除算法面对大量可回收对象时执行效率低的问题，1969 年 Fenichel 提出了一种称为 “半区复制”（Semispace Copying）的垃圾收集算法，具体思想大概是这样：

将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次性全部清理掉。

很显然，这个方法并不适用于多数对象都是存活的情况，因为这将会产生大量的内存间复制的开销。

但对于多数对象都是可回收的情况，该算法只需要复制少量的存活对象，而且每次都是针对整个半区进行内存回收，分配内存时也就不用考虑有空间碎片的复杂情况，只要移动堆顶指针，按顺序分配即可。

这样实现简单，运行高效，现在大部分的商用 Java 虚拟机都优先采用了这种垃圾收集算法去回收新生代

该算法的执行过程如图所示：

这样实现简单，运行高效，不过其缺陷也显而易见，这种复制回收算法的代价是将可用内存缩小为了原来的一半，空间浪费未免太多了一点。

IBM 公司曾有一项专门研究对新生代 “朝生夕灭” 的特点做了更量化的诠释：新生代中的对象有 98% 熬不过第一轮收集。因此并不需要按照 1∶1的比例来划分新生代的内存空间。

更简单的来说，标记-复制算法设计这么一大块的保留区域，目的就是为了把存活对象移动到这块区域上来，方便对之前的区域进行快速清理。

对于新生代对象来说，其具备的鲜明特点就是 “朝生夕灭”，能够在一轮垃圾收集后活下来的对象少之又少。所以，我们其实并不需要这么大一块的保留区域。

1989 年 Andrew Appel 基于此提出了一种更优化的半区复制分代策略，现在称为 “Appel 式回收”。HotSpot 虚拟机的 Serial、ParNew 等新生代收集器均采用了这种策略来设计新生代的内存布局。

⭐ Appel 式回收的具体做法是把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次分配内存只使用 Eden 和其中一块 Survivor。发生垃圾收集时，直接清空 Eden 和已用过的那块 Survivor 空间，当然，在清空之前需要将存活对象复制到另一块 Survivor 中。

这两块 Survivor 空间也分别被称为 From Survivior 和 To Survivor，很显然，每经过一次新生代 GC，From Survivor 和 To Survivor 的身份就会互换。

简单理解，Eden 和 From Survivor 其实就是新生代能够使用的真正内存，而 To Survivor 的存在是为了在清空新生代空间时提供一个地方用来存放仍然存活的对象 (也即保留区域)

HotSpot 虚拟机默认 Eden 和 Survivor 的大小比例是 8∶1，也即每次新生代中可用内存空间为整个新生代容量的 90%（Eden 的 80% 加上一个 Survivor 的 10%），只有一个 Survivor 空间，即 10% 的新生代空间是会被 “浪费” 的。

当然，任何人都没有办法百分百保证每次回收都只有不多于 10% 的对象存活，万一 To Survivor 的内存空间不足以容纳存活的对象怎么办？

别急，我们都能想到，祖宗能想不到？

Appel 式回收还有一个充当罕见情况的 “逃生门” 的安全设计：当 To Survivor 空间不足以容纳一次新生代 GC 之后存活的对象时，这些对象便将通过分配担保机制（Handle Promotion）直接进入老年代。

所谓分配担保，后续文章介绍垃圾收集器的时候会再详细解释

标记-整理算法，Mark-Compact

Mark-Copy 算法在对象存活率较高时就要进行较多的复制操作，效率将会降低。更关键的是，如果不想浪费 50% 的空间，使用 Apple 式回收的话，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都 100% 存活的极端情况，所以在老年代一般不能直接选用 Mark-Copy 算法

针对老年代对象的存亡特征，1974 年 Edward Lueders 提出了另外一种有针对性的 “标记-整理”（Mark-Compact）算法

其中的标记过程还是一样的，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存，如图所示:

Mark-Sweep 算法与 Mark-Compact 算法的本质差异在于前者是一种非移动式的回收算法，而后者是移动式的。是否移动回收后的存活对象是一项优缺点并存的风险决策

如果移动存活对象，尤其是在老年代这种每次回收都有大量对象存活区域，移动存活对象并更新所有引用这些对象的地方是一种极为负重的操作，而且这种对象移动操作必须全程暂停用户应用程序才能进行，像这样的停顿被最初的虚拟机设计者形象地描述为 “Stop The World (STW)”。（记住这个名词 STW，后续我们会经常见到他！！！移动存活对象时需要 STW，可达性分析中的根节点枚举也需要 STW）
总结来说：移动则内存回收时会更复杂
如果完全不考虑移动和整理存活对象的话，弥散于堆中的存活对象导致的空间碎片化问题就只能依赖更为复杂的内存分配器和内存访问器来解决，而内存的访问是用户程序最频繁的操作，甚至都没有之一，假如在这个环节上增加了额外的负担，势必会直接影响应用程序的吞吐量。
总结来说：不移动则内存分配时会更复杂

⭐ 从垃圾收集的停顿时间来看，不移动对象的停顿时间会更短，甚至可以不需要停顿，但是从整个程序的吞吐量来看，移动对象会更划算。

这里的吞吐量，简单理解，就是用户程序和垃圾收集器的效率总和

所以我们其实可以推断出:

关注延迟/速度的收集器（比如 HotSpot 虚拟机中的 CMS 收集器）应该使用 Mark-Sweep 算法
关注吞吐量的收集器（比如 HotSpot 虚拟机中的 Parallel Old 收集器）应该使用 Mark-Compact 算法

另外，其实还有一种折中的办法，Mark-Sweep 算法速度快，可以让虚拟机平时大多数时间都采用 Mark-Sweep 算法，暂时容忍内存碎片的存在，直到内存空间的碎片化程度已经大到影响对象分配的时候，再采用 Mark-Compact 算法收集一次，以获得规整的内存空间（基于 Mark-Sweep 算法的 CMS 收集器面临空间碎片过多时采用的就是这种处理办法）

最后放上这道题的背诵版：

🥸 面试官：讲一讲有哪些垃圾收集算法？
😎 小牛肉：主要有三种：
1）标记-清除算法：这是最基础的算法，主要思想就是先标记出所有需要回收的对象，然后统一回收掉所有被标记的对象。
这个算法主要有两个缺点：
执行效率不稳定。如果堆中包含大量对象，而且其中大部分是需要被回收的，这时就必须进行大量的标记和清除的动作，也就是说执行效率和对象数量成反比
内存空间的碎片化问题。标记、清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致当程序运行过程中需要分配较大对象时，因无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作
后续两个算法标记-复制算法和标记-整理算法都是在标记-清除算法的基础上做的改进。
2）标记-复制算法：主要思想就是将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次性全部清理掉。
这个半区复制算法也有两个比较明显的问题：
不适用于对象存活率较高的情况（即一般不适用于老生代）
可用内存空间缩小了一半（针对这个问题，“Appel 式回收” 进行了改进，就是根据新生代 “朝生夕灭” 的特点，能够在一轮垃圾收集后活下来的对象少之又少，所以，我们其实并不需要这么大一块的保留区域。具体做法是把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次分配内存只使用 Eden 和其中一块 Survivor。发生垃圾收集时，在清空之前需要将存活对象复制到另一块 Survivor 中，然后直接清空 Eden 和已用过的那块 Survivor 空间。另外，使用 Apple 式回收的话，还需要有额外的空间进行分配担保，因为我们没有办法百分百保证分配给 To Survivor 的内存空间能够容纳全部的存活对象，常见的做法就是当 To Survivor 空间不足以容纳一次新生代 GC 之后存活的对象时，这些对象便将通过分配担保机制直接进入老年代）
3）标记-整理算法：主要思想就是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存。这种移动式的算法相对于非移动式的标记-清除算法来说，吞吐量更高，不过速度相对较慢，因为移动对象需要 Stop the world。所以，关注延迟/速度的收集器（比如 HotSpot 虚拟机中的 CMS 收集器）应该使用 Mark-Sweep 算法，而关注吞吐量的收集器（比如 HotSpot 虚拟机中的 Parallel Old 收集器）应该使用 Mark-Compact 算法。
另外，其实还有一种折中的办法，Mark-Sweep 算法速度快，可以让虚拟机平时大多数时间都采用 Mark-Sweep 算法，暂时容忍内存碎片的存在，直到内存空间的碎片化程度已经大到影响对象分配的时候，再采用 Mark-Compact 算法收集一次，以获得规整的内存空间（基于 Mark-Sweep 算法的 CMS 收集器面临空间碎片过多时采用的就是这种处理办法）

心之所向，素履以往，我是小牛肉，小伙伴们下篇文章再见 👋