1 前言

从如何判定对象消亡的角度出发，垃圾收集算法可以分为：

• 引用计数式垃圾收集（Reference Counting GC）
• 追踪式垃圾收集（Tracing GC）

目前主流的 Java 虚拟机用的都是追踪式垃圾收集，所以下面只介绍追踪式垃圾收集的算法。

2 分代收集理论

JDK8 以及更早之前的版本，实践使用的垃圾收集器采用的算法都是遵循了“分代收集”的理论进行设计的（虽然 G1 在 JDK7 Update 4 时已经摘掉了实验标识的，但是在国内各大公司在 JDK8 的时代大多还是用 CMS）。
分代收集理论建立在两个假说之上：
1. 弱分代假说（Weak Generational Hypothesis）—— 绝大多数对象都是朝生夕灭的
2. 强分代假说（Strong Generational Hypothesis）—— 熬过垃圾收集次数越多的对象就越难消亡
根据这两个假说设计的垃圾收集器会将 Java 堆划分为不同的区域，然后将回收对象依据其年龄（即渡过垃圾收集次数）分配到不同的区域之中。根据假设1，我们应该对朝生夕灭的对象放在一起，只标记那少数的存活对象；根据假设2，我们应该将这些难以回收的对象放在一起，这样垃圾收集器就能低频地去回收这个区域。对于释放空间多的内存区域，就多去扫描；对于难以释放空间的内存区域就低频处理；这种设计可以同时兼顾垃圾收集的时间开销和有效利用内存空间。

在 Java 堆划分出不同的区域后，垃圾收集器才可以每次只回收其中某一个或者某些部分的区域，因而才有了“Minor GC”、“Major GC”、“Full GC”这样的回收类型划分，还能够针对不同的区域里面的对象的消亡特征使用相应的垃圾收集算法进行回收。

• Minor GC
  Minor GC 又称为 young gc，指目标只是新生代的垃圾收集。
• Major GC
  Minor GC 又称 old gc，指目标只是老年代的垃圾收集。目前只有 CMS 收集器会有单独收集老年代的行为。
• Full GC
  收集整个 Java 堆和方法区的垃圾收集。

采用分代收集理论的 Java 虚拟机一般会把 Java 堆划分为新生代（Young Generation）和老年代（Old Generation）两个区域。在新生代中，每次垃圾收集时都会大批对象死去，而每次回收后存活的少量对象将会逐步晋升到老年代中。不过真的要完全互相隔离，单独处理自己区域是很难实现的。因为对象之间会存在跨代引用的情况，所以分代收集理论又增加了第三条经验法则——跨代引用假说（Intergenerational Reference Hypothesis）。

跨代引用假说认为跨代引用相对于同代引用来说仅占极少数。

依据“ 跨代引用假说”，只需要在新生代上维护一个全局的数据结构（记忆集，Remembered Set），它把老年代划分成若干小块，标识出老年代的哪一块内存会存在跨代引用。当发生 Minor GC 时，只有包含了跨代引用的小块内存里的对象才会被加入到 GC Roots 进行扫描。虽然增加了额外维护记忆集的成本，但是相对于在 gc 时需要扫描整个老年代的对象来说仍然是笔划算的买卖。

后面 zgc 等新型垃圾收集器已经没有分代的概念

3 经典垃圾收集算法

现在的虚拟机很少单独使用某种垃圾收集算法，一般都是几种混合使用。

3.1 标记-清除算法

标记-清除算法是最早出现的垃圾收集算法，由 Java 之父 John McCarthy 提出

标记-清除算法顾名思义，分为两大步骤：1、标记所有需要回收的对象（也可以标记存活对象）；2、清除需要被回收的对象。

优点：
1. 相较于其他算法，更为简单且容易实现

缺点：
1. 如果需要扫描的对象十分多，那么标记和清除的执行效率则会下降。
2. 清除对象后会产生大量不连续的内存碎片，空间碎片太多可能导致后续申请不到足够大且连续的内存而触发另一次垃圾收集动作。

3.2 标记 - 复制算法

标记 - 复制算法又常被简称为复制算法。

针对“标记-清除算法”在面对大量可回收对象时的效率低问题，提出了 标记-复制算法。标记-复制算法将可用内存按容量划分成大小相等的两块，每次只用其中一块。当一块用完了（一般称这一块为“To”区域），就将其中存活的对象复制到另一块内存上（这块内存一般称为“From”区域）。存活对象复制过来时都会紧凑挨着，所以没有内存碎片问题。接着，一次清除“To”区域内存，并将“From”区域改成“To”区域，“To”区域改成“From”区域。最后，更新引用（需要 stop the world，但是因为存活对象极少，所以停顿不明显）。

优点：
1. 在大量对象是可回收的情况下，拥有更好的回收性能
2. 不会产生内存碎片
缺点：
1. 需要空置一半的内存
2. 如果存活对象是多数时，复制开销过高，内存利用效率也不高

因为新生代的对象绝大多数都是“朝生夕死”的，所以针对这个特性 HotSpot 虚拟机的 Serial、ParNew 等新生代收集器采用了优化版的复制算法。具体做法是将新生代的内存区域分成 Eden 和 两块 Survivor，而分配内存时只用 Eden 和其中一块 Survivor。当发生垃圾收集时，会将 Eden 和 Survivor 的存活对象复制到另一个 Survivor 中，然后清除 Eden 和 “To”区域的Survivor。由于无法保证“From”区域的Survivor 一定可以容纳存活对象，所以一般还会有一个“担保机制”——直接流入老年代。

3.3 标记-整理算法

“标记-复制算法”是针对“标记-清除”在大量回收对象情况下的优化方案；但是如果绝大多数对象是存活对象时，复制算法则有心无力了，而“标记-整理算法”也出现了。

标记-整理算法处理过程：
1. 标记存活对象
2. 将存活对象往内存的一边移动，紧凑挨着
3. 更新引用（需要 stop the world，老年代存活对象多，如果移动对象较多，那么用户能感受到明显的停顿）
4. 清除死亡对象

这里需要注意是移动存活对象，就需要“更新引用”，从而造成 stop the world（即停下所有任务，只执行当前垃圾回收任务）。这种停顿肯定会给用户带来不好的体验，但是不移动的话，碎片化的内存空间就需要使用更为复杂的分配内存技术——空闲列表，甚至无法分配内存。因此，是否移动存活对象需要很好地权衡才行。
流行很长一段时间的CMS就是基于“标记-清除算法”实现的，它更注重于用户体验。直到内存碎片化问题影响到分配对象时，CMS就会采用“标记-整理算法”收集一次。