目录

  1. 概述
  2. 标记阶段
    1. 引用计数算法
      1. 循环引用
      2. 验证 Java 是否采用循环引用
    2. 可达性分析算法
      1. 基本思路
      2. GC Roots
    3. 总结
  3. 清除阶段
    1. 标记清除算法
      1. 执行过程
      2. 清除的实现
    2. 复制算法
      1. 核心思想
      2. 应用场景
    3. 标记压缩（整理）算法
      1. 执行过程
      2. 总结
    4. 清除阶段算法总结
  4. 分代收集算法
    1. 年轻代（Young Gen）
    2. 老年代（Tenured Gen）
  5. 增量收集算法
  6. 分区算法
  7. 总结

概述

JVM 在进行垃圾回收时，主要分为两个阶段（标记阶段和清除阶段）进行，其中标记阶段用于搜集 JVM 中哪些对象需要进行回收，清除阶段用于对标记阶段的对象进行真正的回收，本文主要讲解这两个阶段所涉及的相关算法

标记阶段

在堆里存放着几乎所有的 Java 对象实例，在 GC 执行垃圾回收之前，首先需要区分出内存中哪些是存活对象，哪些是已经死亡的对象，只有被标记为己经死亡的对象，GC 才会在执行垃圾回收时，释放掉其所占用的内存空间，这个过程称为垃圾标记阶段

✨判断对象存活一般有两种方式：引用计数算法和可达性分析算法

🤔JVM 究竟如何标记一个死亡对象？

当一个对象已经不再被任何的存活对象继续引用时，此时对象就是死亡对象

引用计数算法

引用计数算法（Reference Counting）就是对每个对象保存一个整型的引用计数器属性，用于记录对象被引用的情况。对于一个对象 A，只要有任何一个对象引用了 A，则 A 的引用计数器就加 1；当引用失效时，引用计数器就减 1。只要对象 A 的引用计数器的值为 0，即表示对象 A 不可能再被使用，可进行回收

👍优点：

  • 实现简单，垃圾对象便于辨识
  • 判定效率高，回收没有延迟性

😣缺点

  • 需要单独的字段存储计数器，增加了存储空间的开销
  • 每次赋值都需要更新计数器，伴随着加法和减法操作，这增加了时间开销
  • 存在循环引用的情况（这是最制命的缺陷，导致在 Java 的垃圾回收器种没有使用这类算法）

循环引用

当p的指针断开的时候，内部引用形成循环，造成引用一直存在，循环引用必然导致内存泄漏

验证 Java 是否采用循环引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class RefCountGC {
    // 这个成员属性的唯一作用就是占用一点内存
    private byte[] bigSize = new byte[5*1024*1024];
    // 引用
    Object reference = null;

    public static void main(String[] args) {
        RefCountGC obj1 = new RefCountGC();
        RefCountGC obj2 = new RefCountGC();

        obj1.reference = obj2;
        obj2.reference = obj1;

        obj1 = null;
        obj2 = null;
        // 显示的执行垃圾收集行为
        // 这里发生GC，obj1和obj2是否被回收？
        System.gc();
    }
}
/** 运行结果
PSYoungGen: 15490K->808K(76288K)] 15490K->816K(251392K)
**/

上述进行了 GC 收集的行为，所以可以证明 JVM 中采用的不是引用计数器的算法

可达性分析算法

✨可达性分析算法又称为：根搜索算法或追踪型垃圾收集,可达性分析算法不仅具备实现简单和执行高效等特点，更重要的是——该算法可以有效地解决在引用计数算法中循环引用的问题，防止内存泄漏的发生

Java、C#使用的就是可达性分析算法来标记对象是否存活，这种类型的垃圾收集通常也叫作追踪性垃圾收集（Tracing Garbage Collection）

基本思路

❓可达性分析算法，是谁与谁可达？

  • 可达性分析算法是以根对象集合（GCRoots）为起始点，按照从上至下的方式搜索被根对象集合（GC Root Set） 所连接的目标对象是否可达
  • 使用可达性分析算法后，内存中的存活对象都会被根对象集合直接或间接连接着，搜索所走过的路径称为引用链（Reference Chain）
  • 如果目标对象没有任何引用链相连，则是不可达的，就意味着该对象己经死亡，可以标记为垃圾对象，在可达性分析算法中，只有能够被根对象集合直接或者间接连接的对象才是存活对象

GC Roots

❓GCRoots 是什么？

所谓GCRoots根集合就是一组必须活跃的引用，下图总结了常见的GC Roots能使哪些

除了这些固定的 GC Roots 集合以外，根据用户所选用的垃圾收集器以及当前回收的内存区域不同，还可以有其他对象临时性地加入，共同构成完整 GC Roots 集合。比如：分代收集和局部回收（PartialGC）

如果只针对 Java 堆中的某一块区域进行垃圾回收（比如：典型的只针对新生代），考虑到内存区域是虚拟机自己的实现细节，更不是孤立封闭的，这个区域的对象完全有可能被其他区域的对象所引用，这时候就需要一并将关联的区域对象也加入GC Roots Set中去考虑，才能保证可达性分析的准确性

由于 Root 采用栈方式存放变量和指针，所以如果一个指针，它保存了堆内存里面的对象，但是自己又不存放在堆内存里面，那它就是一个 Root

使用可达性分析算法来判断内存是否可回收，那么分析工作必须在一个能保障一致性的快照中进行。这点不满足的话分析结果的准确性就无法保证，由于一致性快照的问题，是导致 GC 进行时必须Stop The World的一个重要原因。即使是号称（几乎）不会发生停顿的 CMS 收集器中，枚举根节点时也是必须停顿的

总结

很多语言选择使用引用计数算法进行资源回收，Python 就使用引用计数算法标记对象，Java 并没有选择引用计数算法，因为很难处理循环引用关系，如此并不能说明引用计数算法不好，具体要看应用场景，业界中仍有大规模保留引用计数机制以提高吞吐量的尝试

🤔Python 是如何解决循环引用？

  • 手动解除：在合适的时机，解除引用关系
  • 使用弱引用weakred，weakref是 python 提供的标准库，旨在解决循环引用

清除阶段

当成功区分出内存中存活对象和死亡对象后，GC 接下来的任务就是执行垃圾回收，释放掉无用对象所占用的内存空间，以便有足够的可用内存空间为新对象分配内存

✨目前在 JVM 中比较常见的三种垃圾收集算法是：标记一清除算法（Mark-Sweep）、复制算法（copying）、标记-压缩算法（Mark-Compact）

标记清除算法

标记-清除算法（Mark-Sweep）是一种非常基础和常见的垃圾收集算法，该算法被J.McCarthy等人在 1960 年提出并，并应用于 Lisp 语言

执行过程

当堆中的有效内存空间（available memory）被耗尽的时候，就会停止整个程序（STW），然后进行两项工作，第一项是标记，第二项是清除

标记：Collector 从引用根节点开始遍历，标记所有被引用的对象。一般是在对象的 Header 中记录为可达对象

清除：Collector 对堆内存从头到尾进行线性的遍历，如果发现某个对象在其 Header 中没有标记为可达对象，则将其回收

😣标记清除算法缺点

  • 算法的效率不算高
  • 在进行 GC 的时候，需要停止整个应用程序，用户体验较差
  • 这种方式清理出来的空闲内存是不连续的，产生内碎片，需要维护一个空闲列表

清除的实现

这里所谓的清除并不是真的置空，而是把需要清除的对象地址保存在空闲的地址列表里。下次有新对象需要加载时，判断垃圾的位置空间是否够，如果够，就存放覆盖原有的地址。

复制算法

为了解决标记-清除算法在垃圾收集效率方面的缺陷，提出了复制算法

👍复制算法优点

  • 没有标记和清除过程，实现简单，运行高效
  • 保证复制过去空间的连续性，不会出现碎片问题

😣复制算法缺点

  • 需要两倍的内存空间
  • 对于 G1 这种拆分成为大量 region 的 GC，使用复制而不是移动，意味着 GC 需要维护 region 之间对象引用关系，不管是内存占用还是时间开销都是不小的消耗

复制算法需要复制的存活对象数量非常低才行，如果系统中存在很多的垃圾对象，不适合使用复制算法

核心思想

将活着的内存空间分为两块，每次只使用其中一块。垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后清除正在使用的内存块中的所有对象，交换两个内存的角色，最后完成垃圾回收

应用场景

为了解决空间利用率问题，可以将内存分为三块： Eden、From Survivor、To Survivor，比例是 8:1:1（大量测试后得到的一个结果），每次使用 Eden 和其中一块 Survivor。回收时，将 Eden 和 Survivor 中还存活的对象一次性复制到另外一块 Survivor 空间上，最后清理掉 Eden 和刚才使用的 Survivor 空间。这样只有 10% 的内存被浪费，但是我们无法保证每次回收都只有不多于 10% 的对象存活，当 Survivor 空间不够，需要依赖其他内存（指老年代）进行分配担保

✨分配担保

为对象分配内存空间时，如果 Eden+Survivor 中空闲区域无法装下该对象，会触发 MinorGC 进行垃圾收集。但如果 Minor GC 过后依然有超过 10% 的对象存活，这样存活的对象直接通过分配担保机制进入老年代，然后再将新对象存入 Eden 区

在新生代，对常规应用的垃圾回收，一次通常可以回收 70% - 99% 的内存空间，回收性价比很高，所以现代的商用虚拟机都是用这种收集算法回收新生代

标记压缩（整理）算法

复制算法的高效性是建立在存活对象少、垃圾对象多的前提下的。这种情况在新生代经常发生，但是在老年代，更常见的情况是大部分对象都是存活对象。如果依然使用复制算法，由于存活对象较多，复制的成本也将很高。因此，基于老年代垃圾回收的特性，需要使用其他的算法。

标记一清除算法的确可以应用在老年代中，但是该算法不仅执行效率低下，而且在执行完内存回收后还会产生内存碎片，所以 JVM 的设计者需要在此基础之上进行改进。标记-压缩（Mark-Compact）算法由此诞生

👍标记压缩算法优点

  • 消除了标记-清除算法当中，内存区域分散的缺点
  • 消除了复制算法当中，内存减半的高额代价

😣标记压缩算法缺点

  • 从效率上来说，标记-整理算法要低于复制算法
  • 移动对象的同时，如果对象被其他对象引用，则还需要调整引用的地址
  • 移动过程中，需要全程暂停用户应用程序

执行过程

  1. 和标记清除算法一样，从根节点开始标记所有被引用对象
  2. 将所有的存活对象压缩到内存的一端，按顺序排放
  3. 清理边界外所有的空间

标记的存活对象将会被整理，按照内存地址依次排列，而未被标记的内存会被清理掉。如此一来，当我们需要给新对象分配内存时，JVM 只需要持有一个内存的起始地址即可，这比维护一个空闲列表显然少了许多开销

🆚与标记清除算法相比，标记-清除算法是一种非移动式的回收算法，标记-压缩是移动式的，是否移动回收后的存活对象是一项优缺点并存的风险决策。

总结

标记-压缩算法的最终效果等同于标记-清除算法执行完成后，再进行一次内存碎片整理，因此，也可以把它称为标记-清除-压缩（Mark-Sweep-Compact）算法

清除阶段算法总结

Mark-SweepMark-CompactCopying
速率中等最慢最快
空间开销少（但会堆积碎片）少（不堆积碎片）通常需要活对象的 2 倍空间（不堆积碎片）
移动对象否是是

效率上来说，复制算法最优，但是却浪费了太多内存，而为了尽量兼顾上面提到的三个指标，标记-整理算法相对来说更平滑一些，但是效率上不尽如人意，它比复制算法多了一个标记的阶段，比标记-清除多了一个整理内存的阶段

🎶不存在最优的算法，只有最合适的算法

分代收集算法

前面所有这些算法中，并没有一种算法可以完全替代其他算法，它们都具有自己独特的优势和特点。

分代收集算法，是基于这样一个事实：不同的对象的生命周期是不一样的因此，不同生命周期的对象可以采取不同的收集方式，以便提高回收效率。一般是把 Java 堆分为新生代和老年代，这样就可以根据各个年代的特点使用不同的回收算法，以提高垃圾回收的效率。

在 Java 程序运行的过程中，会产生大量的对象，其中有些对象是与业务信息相关，比如 Http 请求中的 Session 对象、线程、Socket 连接，这类对象跟业务直接挂钩，因此生命周期比较长。但是还有一些对象，主要是程序运行过程中生成的临时变量，这些对象生命周期会比较短，比如：String 对象，由于其不变类的特性，系统会产生大量的这些对象，有些对象甚至只用一次即可回收。

目前几乎所有的 GC 都采用分代收集算法执行垃圾回收的，在 HotSpot 中，基于分代的概念，GC 所使用的内存回收算法结合年轻代和老年代各自的特点

年轻代（Young Gen）

✨年轻代特点：区域相对老年代较小，对象生命周期短、存活率低、回收频繁

这种情况复制算法的回收整理，速度是最快的。复制算法的效率只和当前存活对象大小有关，因此很适用于年轻代的回收。而复制算法内存利用率不高的问题，通过 hotspot 中的两个 survivor 的设计得到缓解

老年代（Tenured Gen）

✨老年代特点：区域较大，对象生命周期长、存活率高，回收不及年轻代频繁

这种情况存在大量存活率高的对象，复制算法明显变得不合适。一般是由标记-清除或者是标记-清除与标记-整理的混合实现。

📓各个阶段开销总结

  • Mark 阶段的开销与存活对象的数量成正比。

  • Sweep 阶段的开销与所管理区域的大小成正相关。

  • Compact 阶段的开销与存活对象的数据成正比。

以 HotSpot 中的 CMS 回收器为例，CMS 是基于 Mark-Sweep 实现的，对于对象的回收效率很高。而对于碎片问题，CMS 采用基于 Mark-Compact 算法的 Serial Old 回收器作为补偿措施：当内存回收不佳（碎片导致的 Concurrent Mode Failure 时），将采用 Serial Old 执行 Full GC 以达到对老年代内存的整理

分待的思想被现有的虚拟机广泛使用，几乎所有的垃圾回收器都区分成新生代和老年代

增量收集算法

上述现有的算法，在垃圾回收过程中，应用软件将处于一种Stop the World的状态。在 Stop the World 状态下，应用程序所有的线程都会挂起，暂停一切正常的工作，等待垃圾回收的完成。如果垃圾回收时间过长，应用程序会被挂起很久，将严重影响用户体验或者系统的稳定性。为了解决这个问题，即对实时垃圾收集算法的研究直接导致了增量收集（Incremental Collecting）算法的诞生

增量算法的基本思想如下：

如果一次性将所有的垃圾进行处理，需要造成系统长时间的停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。

总的来说，增量收集算法的基础仍是传统的标记-清除和复制算法。增量收集算法通过对线程间冲突的妥善处理，允许垃圾收集线程以分阶段的方式完成标记、清理或复制工作

😣使用这种方式，由于在垃圾回收过程中，间断性地还执行了应用程序代码，所以能减少系统的停顿时间。但是，因为线程切换和上下文转换的消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降。

分区算法

一般来说，在相同条件下，堆空间越大，一次 Gc 时所需要的时间就越长，有关 GC 产生的停顿也越长。为了更好地控制 GC 产生的停顿时间，将一块大的内存区域分割成多个小块，根据目标的停顿时间，每次合理地回收若干个小区间，而不是整个堆空间，从而减少一次 GC 所产生的停顿。分代算法将按照对象的生命周期长短划分成两个部分，分区算法将整个堆空间划分成连续的不同小区间，每一个小区间都独立使用，独立回收。这种算法的好处是可以控制一次回收多少个小区间

总结

以上介绍的都只是基本的算法思路，实际 GC 实现过程要复杂的多，目前还在发展中的前沿 GC 都是复合算法，并且并行和并发兼备