小翎哥的博客
小翎哥的博客

JVM 垃圾收集算法核心原理

 约 16600 字 预计阅读 34 分钟 

本文将基于 HotSpot 虚拟机，深入讲解垃圾收集算法的核心原理。本文所有内容均整合自网络，在广泛收集信息的基础上，进行了大量的勘误与扩展，最终著成了此文。

JVM 运行时数据区简介

根据《Java 虚拟机规范》，JVM 管理的内存被划分为以下运行时数据区域：程序计数器、虚拟机栈、本地方法栈、堆、方法区。

JVM 运行时数据区域

  • 程序计数器 (Program Counter Register)：

    程序计数器是内存中很小的一块空间，用于指示当前线程正在执行的字节码行号。在 Java 虚拟机中，字节码解释器使用程序计数器来确定下一条指令，它控制着程序的执行流程，包括分支、循环、跳转、异常处理和线程恢复等基本功能。

    JVM 通过时间片分配和线程轮转来实现多线程。每个线程都需要一个独立的程序计数器，用于恢复正确的执行位置。这些计数器是线程私有的，独立存储，互不影响。

    • 如果线程正在执行 Java 方法，程序计数器记录正在执行的虚拟机字节码指令的地址；
    • 如果正在执行本地方法，则计数器的值为 undefined。

    此内存区域是《Java 虚拟机规范》中唯一没有规定任何 OutOfMemoryError 情况的区域。

  • Java 虚拟机栈 (Java Virtual Machine Stack)：

    与程序计数器一样，Java 虚拟机栈也是线程私有的，它的生命周期与线程相同。虚拟机栈描述的是 Java 方法执行的线程内存模型：每个方法被执行的时候，JVM 都会同步创建一个栈帧 (Stack Frame) 用于存储局部变量表、操作数栈、动态连接、方法出口等信息。每一个方法被调用直至执行完毕的过程，就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。

    局部变量表包括基本数据类型、对象引用和 returnAddress 类型。每种类型使用局部变量槽 (Slot) 表示，long 和 double 类型使用两个槽，其他类型使用一个槽。局部变量表的大小在进入方法时就确定了1，方法运行期间不会再改变。

    对象引用并不等同于对象本身，可能是指向对象起始地址的引用指针，也可能是指向一个代表对象的句柄或其他与此对象相关的位置。

    《Java 虚拟机规范》对虚拟机栈规定了两类异常状况：

    • 如果栈深度过大抛出 StackOverflowError 异常；
    • 如果栈容量可以扩展但无法申请到足够内存，则抛出 OutOfMemoryError 异常。

    HotSpot 虚拟机栈容量不可扩展，因此不会因为栈无法扩展而导致 OutOfMemoryError，但如果线程在申请栈空间时失败，则仍可能出现 OOM 异常。

  • 本地方法栈 (Native Method Stacks)：

    本地方法栈类似于虚拟机栈，不同之处在于本地方法栈是为本地方法服务的。

    《Java 虚拟机规范》没有对其使用的语言、使用方式与数据结构做强制规定，因此虚拟机可以根据需要自由实现它，有的虚拟机会将本地方法栈和虚拟机栈合二为一。

    本地方法栈与虚拟机栈类似，也会在栈深度溢出或者栈扩展失败时分别抛出 StackOverflowError 和 OutOfMemoryError 异常。

  • Java 堆 (Java Heap)：

    Java 堆是 JVM 存放对象实例的内存空间，是虚拟机管理的内存中最大的一块。它被所有线程所共享，且在虚拟机启动时就被创建。几乎 2 所有的对象实例都会在这里分配内存。

    Java 堆可以被实现成固定大小的，也可以是可扩展的。当前主流的 JVM 都是按照可扩展来实现的，通过参数 -Xmx 和 -Xms 设定。当 Java 堆中没有足够的内存完成实例分配，并且无法再扩展时，虚拟机会抛出 OutOfMemoryError 异常。

    尽管 Java 堆可以在物理内存中是不连续的，但从逻辑上来看应该被视为连续的，就像磁盘存储文件一样。

    为了提高对象分配效率，Java 堆内部还设置了多个线程私有的 TLAB（Thread Local Allocation Buffer）分配缓冲区。

  • 方法区 (Method Area)：

    方法区与 Java 堆一样，是多个线程共享的内存区域，存储已加载的类型信息、常量、静态变量和即时编译器编译后的代码缓存。尽管《Java 虚拟机规范》将方法区描述为堆的一个逻辑部分，但它通常被称为 “非堆” (Non-Heap)，以区别于 Java 堆。

    回顾历史，虽然很多国内互联网从业者将方法区称为“永久代 (Permanent Generation)”，但是这种说法是不准确的。永久代是 HotSpot 虚拟机使用的一种实现方式，它使用永久代来实现方法区，将垃圾收集器的分代概念扩展到了方法区。

    使用永久代实现方法区的设计会导致一些问题 3，比如更容易遇到内存溢出的问题和一些不兼容问题，因此在 JDK 8 中，HotSpot 放弃了永久代的设计，采用元空间代替 (Meta-space) 。与此同时，字符串常量池、静态变量等内容也被移到了本地内存中。虚拟机实现方法区的方式并不受《Java 虚拟机规范》的约束。

    《Java 虚拟机规范》对方法区的限制非常宽松，它不需要连续的内存，可以选择固定大小或可扩展，甚至可以选择不实现垃圾收集。方法区的主要回收目标是常量池和类，但这个东西的回收效果往往一般，特别是类型的卸载条件相当苛刻。

    根据规范，如果方法区无法满足新的内存分配需求时，将抛出 OutOfMemoryError 异常。

  • 运行时常量池 (Runtime Constant Pool)：

    运行时常量池是一种在类加载期间创建的数据结构，它属于方法区的一部分，用于存储编译时生成的各种字面量 (literal) 和符号引用 (symbolic references)。在程序运行期间，JVM 可以从常量池中快速地获取需要使用的字面量或符号引用，从而提高程序的运行效率。

    常量池主要包括两种类型的常量：

    • 字面量常量

      字面量常量是一些固定的值，例如字符串、数字和布尔值等。在编译时，Java 编译器会将这些字面量直接嵌入到程序代码中，并存储在常量池中。这样，在程序运行时，JVM 就可以直接从常量池中获取这些值，而不需要再次计算或创建。

    • 符号引用常量

      符号引用常量是一些需要在程序运行时才能确定的值，例如类和方法的名称、描述符和方法句柄等。在编译时，Java 编译器会将这些符号引用转化为一些特殊的常量，并存储在常量池中。在程序运行时，JVM 可以根据这些常量来获取对应的类或方法的信息，从而正确地执行程序代码。

    常量池的主要作用是优化程序的性能。由于常量池可以缓存常用的字面量和符号引用，因此程序运行时可以更快地获取这些值，从而提高程序的运行效率。同时，常量池也可以减少程序的内存占用，因为相同的字面量和符号引用只需要存储一次。

    注意：在程序中过度使用字面量常量会导致程序的可维护性降低。因为这些常量可能散布在代码的各个位置，难以进行统一管理和修改。所以推荐使用常量变量或枚举类型等方式来管理常量。

    此外，运行时常量池属于方法区的一部分，因此受到方法区内存的限制。当常量池无法再申请到内存时，会抛出 OutOfMemoryError 异常。

  • 直接内存 (Direct Memory)：

    JVM 直接内存是一种在 Java 程序中可以直接访问的内存。与 Java 堆不同，直接内存是由操作系统管理的，不受 JVM 垃圾收集机制的控制。

    直接内存不需要通过 Java 堆来中转，因此读写性能更高。然而，分配和释放过程需要即时调用系统的 malloc 和 free 函数，代价比在 Java 堆中要大得多4。因此在使用直接内存时，应尽量重用已分配的内存，避免频繁的分配和释放操作。

JVM 对象简介

对象的创建过程

在 Java 虚拟机中，对象的创建过程可以分为以下三个步骤：

  1. 分配内存：

    常用的分配内存的方式可以以下两种：

    • 指针碰撞：如果 Java 堆内存绝对规整，对象在一侧，空闲内存在另一侧，由一个指针作为分界点。那么分配内存时只需将指针向空闲空间方向移动对象大小的距离即可。
    • 空闲列表：如果 Java 堆内存不规整，则虚拟机需要维护一个列表来记录可用的内存块。在分配内存时，从列表中找到一块足够大的空间划分给对象实例，并更新列表记录。

    内存分配方式的选择取决于 Java 堆是否规整，而 Java 堆是否规整又取决于所采用的垃圾收集器是否具备内存压缩整理能力。因此，使用带压缩整理过程的收集器时，采用的分配算法往往是指针碰撞；使用基于清除算法的收集器时，理论上只能采用较为复杂的空闲列表分配算法。

    在 JVM 中，创建对象是很频繁的操作。而在并发情况下，很可能出现多个线程同时分配内存的情况，解决这个问题通常有以下两种方案：

    • 同步处理：通过 CAS + 失败重试的方式保证更新操作的原子性。
    • 隔离处理：每个线程在 Java 堆中预先分配一小块内存，作为自己的本地分配缓冲 (Thread Local Allocation Buffer，TLAB)。线程先在本地缓冲区中分配内存，本地内存用完后再去堆中通过同步机制分配。

      可以通过 -XX：+/-UseTLAB 参数设定是否启用 TLAB。

  2. 初始化对象：

    内存分配完成后，虚拟机必须将分配到的内存空间（除了对象头）都初始化为零值（如果使用了 TLAB，可以在 TLAB 分配时顺便进行此操作）。

    初始化为零值后，JVM 还需要对实例进行必要的设置，例如确定对象的类实例、如何找到类的元数据、对象的哈希码和 GC 分代年龄等信息。这些信息存储在对象头 (Object Header) 中。对象头的设置方式取决于虚拟机当前运行的状态（例如是否启用偏向锁等）。

    完成上述工作后，从虚拟机的视角来看，新对象已经产生。但对 Java 程序来说，对象创建才刚刚开始。此时构造函数（即 Class 文件中的 <init>() 方法）还未执行，所有字段均为默认的零值，对象需要的其他资源和状态信息也尚未按照预定的意图构造好。通常，Java 编译器会在遇到 new 关键字时同时生成 new 指令和 invokespecial 指令。new 指令后面会紧接着执行 <init>() 方法，按程序员的意愿对对象进行初始化。到这一步，真正可用的对象才算完全构造出来。

    以下是 HotSpot 虚拟机字节码解释器 bytecodeInterpreter.cpp 的代码片段，这个解释器实际上并未被使用，不过对我们了解 HotSpot 的运作过程还是有帮助的：

    在大多数平台上都会使用模板解释器，尤其是代码被即时编译器执行时，它们之间的差异会更加显著。

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

    // 确保常量池中存放的是已解释的类
if (!constants->tag_at(index).is_unresolved_klass()) {
    // 断言确保是 klassOop 和 instanceKlassOop
    oop entry = (klassOop) *constants->obj_at_addr(index);
    assert(entry->is_klass(), "Should be resolved klass");
    klassOop k_entry = (klassOop) entry;
    assert(k_entry->klass_part()->oop_is_instance(), "Should be instanceKlass");
    instanceKlass* ik = (instanceKlass*) k_entry->klass_part();
    // 确保对象所属类型已经经过初始化阶段
    if ( ik->is_initialized() && ik->can_be_fastpath_allocated() ) {
        // 取对象长度
        size_t obj_size = ik->size_helper();
        oop result = NULL;
        // 记录是否需要将对象所有字段置零值
        bool need_zero = !ZeroTLAB;
        // 是否在 TLAB 中分配对象
        if (UseTLAB) {
            result = (oop) THREAD->tlab().allocate(obj_size);
        }
        if (result == NULL) {
            need_zero = true;
            // 直接在 eden 中分配对象
retry:
            HeapWord* compare_to = *Universe::heap()->top_addr();
            HeapWord* new_top = compare_to + obj_size;
            // cmpxchg 是 x86 中的 CAS 指令，这里是一个 C++ 方法，通过 CAS 方式分配空间，并发失败的
            //   话，转到 retry 中重试直至成功分配为止
            if (new_top <= *Universe::heap()->end_addr()) {
                if (Atomic::cmpxchg_ptr(new_top, Universe::heap()->top_addr(), compare_to) != compare_to) {
                    goto retry;
                }
                result = (oop) compare_to;
            }
        }
        if (result != NULL) {
            // 如果需要，为对象初始化零值
            if (need_zero ) {
                HeapWord* to_zero = (HeapWord*) result + sizeof(oopDesc) / oopSize;
                obj_size -= sizeof(oopDesc) / oopSize;
                if (obj_size > 0 ) {
                    memset(to_zero, 0, obj_size * HeapWordSize);
                }
            }
            // 根据是否启用偏向锁，设置对象头信息
            if (UseBiasedLocking) {
                result->set_mark(ik->prototype_header());
            } else {
                result->set_mark(markOopDesc::prototype());
            }
            result->set_klass_gap(0);
            result->set_klass(k_entry);
            // 将对象引用入栈，继续执行下一条指令
            SET_STACK_OBJECT(result, 0);
            UPDATE_PC_AND_TOS_AND_CONTINUE(3, 1);
        }
    }
}

  3. 设置对象的引用：

    在对象初始化完成之后，需要将对象的引用返回给调用者或存储到变量中，以便后续对对象的访问和操作。在 Java 中，对象的引用通常是通过栈中的变量来进行存储和传递的。

需要注意的是，JVM 实际的运行环境往往很复杂。例如，对象可能会面临多线程访问、逃逸分析等情况。在这些情况下，对象的创建过程可能会变得更加复杂。另外，对象的创建过程还可能受到 Java 虚拟机参数的影响，例如堆内存大小、GC 策略等。

对象的内存布局

JVM 中一个对象的内存布局往往分为三个部分：对象头 (Header)、实例数据 (Instance Data) 和对齐填充 (Padding)。

  1. 对象头：

    对象头往往包括标记字段和类型指针两类信息：

    • 标记字段

      标记字段主要用于存储对象的运行时状态信息，包括对象的哈希码、GC 分代年龄、锁状态标志、线程持有的锁、偏向线程 ID、偏向时间戳等。其中的哈希码是为了方便在哈希表中查找对象而添加的，锁状态标志则用于标记对象是否被锁定，线程持有的锁以及偏向线程 ID、偏向时间戳则是为了支持偏向锁而添加的。

    • 类型指针

      类型指针指向对象所属的类型元数据，即类对象。Java 虚拟机通过类型指针来确定该对象是哪个类的实例，从而可以根据对象所属的类进行方法调用、字段访问等操作。类型指针的大小在不同的虚拟机中可能不同，通常是一个指针大小，即 32 位虚拟机中是 4 个字节，64 位虚拟机中是 8 个字节。

      以 HotSpot 为例，由于类型指针在对象头中占用的存储空间比较大，如果对象定义的类型是已知的，可以通过使用 JVM 参数 -XX:+UseCompressedOops 或 -XX:+UseCompressedClassPointers 来压缩类型指针的大小，从而节省内存空间。

      在 HotSpot 虚拟机中，对象头的存储布局会随着虚拟机的版本和使用的指针压缩技术而有所不同。例如，在 32 位的 HotSpot 虚拟机中，对象头部分的标记字段和类型指针共占用 32 个比特的存储空间，而在 64 位的 HotSpot 虚拟机中，对象头部分的标记字段和类型指针共占用 64 个比特的存储空间。不同的对象状态可能会影响对象头部分的存储结构和存储内容，例如，如果对象被锁定，则需要在对象头中存储锁状态标志。

      注意，并非所有的虚拟机实现都需要在对象数据上保留类型指针，一些虚拟机实现会将类型指针存储在另外的位置，例如在一张哈希表中，这些实现可能会比在对象头中存储类型指针更高效。

  2. 对象数据：

    实例数据部分存储对象中有效信息，包括程序代码中定义的各种类型的字段，无论从父类继承还是在子类中定义的字段都需要记录。存储顺序受到虚拟机分配策略和 Java 源码中字段定义顺序的影响。

    以 HotSpot 虚拟机为例，其默认的分配顺序为 longs/doubles、int、shorts/chars、bytes/booleans、OOPs (Ordinary Object Pointers)。此外，从默认的分配策略可以看出，相同宽度的字段总是被分配到一起存放。在满足此前提条件的情况下，父类中定义的变量出现在子类之前。若 HotSpot 虚拟机的 +XX：CompactFields 参数为 true，子类中较窄的变量也可以插入父类变量的空隙中，以节省空间。

  3. 对齐填充：

    对齐填充是用于对齐对象的内存布局的一种技术。由于 JVM 在分配内存时通常按照 8 字节对齐，因此可能会出现对象的实例变量未对齐的情况。为了解决这个问题，HotSpot 会在实例数据的末尾添加一些额外的空间，以确保对象的大小是 8 字节的倍数。

对象的访问定位

创建对象的目的是为了使用它，程序通过栈上的 reference 操作堆上的对象。由于《Java 虚拟机规范》只定义了 reference 为指向对象的引用，没有规定引用如何定位、访问堆中对象的位置，因此对象的访问方式由虚拟机实现。主流访问方式有句柄和直接指针两种：

  • 使用句柄访问时，Java 堆会划分出一块内存来作为句柄池，reference 中存储的就是对象的句柄地址，而句柄中包含了对象实例数据与类型数据各自具体的地址信息。如图所示：

    通过句柄访问对象

  • 使用直接指针访问时，必须考虑如何放置访问类型数据的相关信息，因为直接使用对象地址访问会遗漏这些信息。Reference 存储的是对象地址，如果只需要访问对象本身，就不需要额外的间接访问开销。如图所示：

    通过直接指针访问对象

如何判断 JVM 对象是否存活

Java 堆里面存放着 Java 程序中几乎所有的对象实例，垃圾收集器在对堆进行回收前，第一件事情就是要确定这些对象是否存活。常用的判断方法有以下两种：

引用计数算法

引用计数算法的原理比较简单，它通过维护每个对象的引用计数器来判断对象是否可被回收。每个对象都有一个引用计数器，当有一个指针指向该对象时，引用计数器加 1，当指针失效时，引用计数器减 1。当引用计数器的值为 0 时，说明该对象已经没有指针指向它，可以被回收。

不过它存在一个致命的缺陷：难以处理循环引用的情况。如果存在两个对象 A 和 B，它们互相引用对方，那么它们的引用计数器值始终不为 0，导致它们永远无法被回收，从而造成内存泄漏。

要解决这个问题，通常需要借助其他算法。比如 Python 就是在引用计数算法的基础上，额外引入了可达性分析算法（标记-清除 + 分代收集）来处理循环引用的对象。

可达性分析算法

当前主流的商用编程语言 (Java, C# …) 的内存管理子系统，都是通过可达性分析 (Reachability Analysis) 算法来判定对象是否存活的。

这个算法的基本思路就是通过一系列称为 “GC Roots” 的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程所走过的路径称为 “引用链” (Reference Chain)，如果某个对象到 GC Roots 间没有任何引用链相连，或者用图论的话来说就是从 GC Roots 到这个对象不可达时，则证明此对象是不可能再被使用的。

如下图所示，对象 object5、object6、object7 虽然互有关联，但是它们到 GC Roots 是不可达的，因此会被判定为可回收的对象：

判定为可回收的对象

在 Java 技术体系中，可作为 GC Roots 的对象包括以下几种：

  • 在虚拟机栈（栈帧中的本地变量表）中引用的对象，比如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等。
  • 在方法区中类静态属性引用的对象，比如 Java 类的引用类型静态变量。
  • 在方法区中常量引用的对象，比如字符串常量池 (String Table) 里的引用。
  • 在本地方法栈中 JNI（即通常所说的 native 方法）引用的对象。
  • Java 虚拟机内部的引用，如基本数据类型对应的 Class 对象，一些常驻的异常对象（比如 NullPointExcepiton、OutOutOfMemoryError）等，还有系统类加载器。
  • 所有被同步锁（synchronized 关键字）持有的对象。
  • 反映 Java 虚拟机内部情况的 JMXBean、JVMTI 中注册的回调、本地代码缓存等。

除了这些固定的 GC Roots 集合外，不同的垃圾收集器和回收的内存区域，还可能临时加入其他对象，共同构成完整的 GC Roots 集合。例如，分代收集和局部回收中，如果只对 Java 堆中的某个区域发起垃圾收集（如只对新生代进行垃圾收集），必须考虑到内存区域是虚拟机的实现细节，某个区域中的对象可能被堆中其他区域的对象引用。因此，必须将这些关联区域的对象一并加入 GC Roots 集合中，才能确保可达性分析的正确性。

目前主流的垃圾收集器都具备局部回收的特征，为了避免 GC Roots 包含过多对象而过度膨胀，它们在实现上也做出了各种优化处理。

JVM 垃圾收集算法理论

经过七千多字的基础知识铺垫，本文终于进入了正题。接下来，我们将详细介绍基于可达性分析的 JVM 垃圾收集算法的种类和原理。

分代收集理论

分代假说

分代收集名为理论，实质是一套符合大多数程序运行实际情况的经验法则，它建立在两个分代假说之上：

  1. 弱分代假说 (Weak Generational Hypothesis)：绝大多数对象都是朝生夕灭的。

  2. 强分代假说 (Strong Generational Hypothesis)：熬过越多次垃圾收集过程的对象就越难以消亡。

    这两个分代假说共同奠定了多款常用的垃圾收集器的设计原则：

    • 将 Java 堆划分为不同的区域，将回收对象根据其年龄分配到不同的区域存储。
      • 如果一个区域中大多数对象朝生夕灭，难以熬过垃圾收集过程，将它们集中存储可以以较低的代价回收大量空间；
      • 如果剩下的对象难以消亡，集中存储也能降低垃圾收集的频率，兼顾时间和空间的效率。
    • 划分 Java 堆的不同区域之后，垃圾收集器可以每次只回收其中某一个或几个区域，进而划分出 “Minor GC”、“Major GC” 和 “Full GC” 等回收类型；同时也可以针对不同的区域使用与存储对象生命周期特征相匹配的垃圾收集算法，比如“标记-复制算法”、“标记-清除算法”、“标记-整理算法”等。

    把分代收集理论具体放到现在的商用 Java 虚拟机里，设计者一般至少会把 Java 堆划分为新生代 (Young Generation) 和老年代 (Old Generation) 两个区域。顾名思义，在新生代中，每次垃圾收集时都会有大批对象死去，而每次回收后存活的少量对象，将会逐步晋升到老年代中存放。

    经过仔细思考，我们就能发现分代收集并不是简单地划分内存区域那么简单。有一个很明显的问题，就是对象之间存在跨代引用。当执行只局限于新生代区域内的收集 (Minor GC) 时，新生代中的对象可能被老年代所引用。为了找出该区域中的存活对象，就需要在固定的 GC Roots 之外，额外遍历整个老年代中所有对象来确保可达性分析结果的正确性。反过来 5 也是一样。虽然理论上遍历整个老年代所有对象也不是不行，但这么做性能肯定会爆炸。

    幸运的是，我们还有第三条经验法则：

  3. 跨代引用假说 (Intergenerational Reference Hypothesis)：跨代引用相对于同代引用来说仅占极少数。

    其实这是根据前两条假说逻辑推导出的推论：存在互相引用关系的两个对象应倾向于同时生存或消亡。例如，如果某个新生代对象存在跨代引用，由于老年代对象难以消亡，该引用会使得新生代对象在收集时同样存活，进而在年龄增长后晋升到老年代，此时跨代引用也会随之消除。

    依据这条假说，我们就不应再为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用。而是可以在新生代上建立一个全局的“记忆集”（Remembered Set），并在记忆集中将老年代划分为若干块，以标识出老年代中存在跨代引用的内存块。此后，当发生 Minor GC 时，只有包含了跨代引用的小块内存里的对象才会被加入到 GC Roots 进行扫描。虽然这种方法需要在对象改变引用关系（如将自己或者某个属性赋值）时维护记录的正确性，会增加一些运行时开销，但与扫描整个老年代相比，仍然是值得的。

收集类型划分

当前商用虚拟机的垃圾收集器大多依照“分代收集”的理论进行设计。按照不同的收集年代或区域划分，可以概括为以下几种收集方式：

  • 部分收集 (Partial GC)：指目标不是完整收集整个 Java 堆的垃圾收集，其中又分为：
    • 新生代收集 (Minor GC/Young GC)：指目标只是新生代的垃圾收集。
    • 老年代收集 (Major GC/Old GC)：指目标只是老年代的垃圾收集。

      目前只有 CMS 收集器会有单独收集老年代的行为。另外请注意 “Major GC” 这个说法现在有点混淆，在不同资料上常有不同所指，需按上下文区分到底是指老年代的收集还是整堆收集。

  • 混合收集 (Mixed GC)：指目标是收集整个新生代以及部分老年代的垃圾收集。

    G1 等新型收集器会有这种行为。

  • 整堆收集 (Full GC)：收集整个 Java 堆和方法区的垃圾收集，往往作为兜底方案使用。

了解了分代收集理论，接下来我们详细介绍几种适用于不同类型的垃圾收集算法的实现。

标记-清除算法

标记-清除 (Mark-Sweep) 算法是最早出现也是最基础的垃圾收集算法，在 1960 年由 Lisp 之父 John McCarthy 所提出。它将垃圾收集过程分为两个阶段：标记阶段和清除阶段：

  • 标记阶段：垃圾收集器会遍历所有从根对象（如 GC Roots）开始的引用链，标记所有存活的对象。在这个阶段结束后，所有存活的对象都被标记为“存活”。
  • 清除阶段：垃圾收集器会遍历整个内存，将没有标记的对象视为垃圾，进行回收。在这个阶段结束后，所有未被标记的对象都被清除，只剩下了被标记的存活对象。

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

标记-清除算法示意图

标记-清除算法的优点是实现简单，但是缺点也特别明显：

  • 内存碎片化。标记-清除算法只是将垃圾对象标记为可回收的，并不会进行内存整理，所以回收后的内存空间会产生碎片化，导致后续的内存分配过程变得复杂。
  • 效率低下。标记-清除算法需要两次遍历整个内存空间，其中标记阶段需要遍历所有存活对象，耗时较长；而清除阶段需要遍历所有未被标记的对象，同样比较耗时。

因此，标记-清除算法只在老年代有些用武之地，而现代垃圾收集器中几乎没有单独使用这种算法的。

现代垃圾收集器通常采用复合算法，将多种垃圾收集算法结合起来使用，以达到更好的垃圾收集效果。

标记-复制算法

为了解决标记-清除算法面对大量可回收对象时执行效率低的问题，1969 年 Fenichel 提出了一种称为“半区复制” (Semispace Copying) 的垃圾收集算法。

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

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

标记-复制算法示意图

如果内存中多数对象都是存活的，这种算法将会产生大量的内存间复制的开销，但对于多数对象都是可回收的情况，算法需要复制的就是占少数的存活对象，而且每次都是针对整个半区进行内存回收，分配内存时也就不用考虑有空间碎片的复杂情况，只要移动堆顶指针，按顺序分配即可。这样实现简单，运行高效。

不过其缺陷也显而易见，这种复制回收算法的代价是将可用内存缩小为了原来的一半，空间浪费太多。而且这种算法在对象存活率较高时需要进行较多的复制操作，效率会降低。在老年代，由于对象存活率较高，如果也采用复制算法，那就需要额外的空间进行分配担保以应对极端情况。因此，这种算法一般只用于新生代，然后由老年代为它做担保。

HotSpot 的标记-复制算法

现今大部分商用 Java 虚拟机都倾向于采用标记-复制算法回收新生代，IBM 公司曾开展过一项研究，进一步量化了新生代中“朝生夕灭”对象的特点：据统计，有 98% 的对象无法熬过第一轮收集。因此，划分新生代内存空间的比例无需严格按照 1:1，而可以更加灵活。在 1989 年，Andrew Appel 针对这种具备“朝生夕灭”特点的对象，提出了半区复制分代策略的改进方案，现在被称为“Appel 式回收”。

HotSpot 虚拟机的 Serial、ParNew 等新生代收集器也独立研发了与之类似的策略来设计新生代的内存布局。具体做法是把新生代分为一块较大的 Eden 空间和两块较小的 Survivor 空间，每次分配内存只使用 Eden 和其中一块 Survivor。发生垃圾收集时，将 Eden 和用过的 Survivor 空间中仍然存活的对象一次性复制到另外一块 Survivor 空间上，然后直接清理掉 Eden 和已用过的那块 Survivor 空间。示意图如下：

HotSpot 标记-复制算法示意图

默认情况下，Eden 和 Survivor 的大小比例为 8:1，因此每次新生代中可用内存空间为整个新生代容量的 90%（Eden 的 80% 加上一个 Survivor 的 10%），但实际上每次回收存活的对象比例可能高于 10%。针对这种情况，HotSpot 实现了一种分配担保机制，当 Survivor 空间不足以容纳一次 Minor GC 后存活的对象时，会借用老年代的内存进行分配担保。

标记-整理算法

针对老年代对象的长寿特征，1974 年 Edward Lueders 提出了一种有针对性的标记-整理 (Mark-Compact) 算法。这种算法的标记过程仍然与标记-清除算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向内存空间一端移动，然后直接清理掉边界以外的内存。示意图如下图所示：

标记-整理算法示意图

移动存活对象并更新所有引用是一种开销极大的操作，而且对象移动期间必须全程暂停用户应用程序 (Stop The World6)。但如果像标记-清除算法那样完全不进行移动和整理，那么解决空间碎片化问题就只能依赖更为复杂的内存分配算法（空闲列表等）。由于内存申请是 Java 程序中最频繁的操作之一，引入这种复杂的算法势必会降低应用的吞吐量。

由上可知，移动或者不移动对象都有各自的利弊：

  • 移动则内存回收时会更复杂；不移动则内存分配时会更复杂。
  • 从垃圾收集的停顿时间来看：不移动对象停顿时间会更短，甚至可以不需要停顿，
  • 但是从整个程序的吞吐量 7 来看，移动对象会更划算。即使不移动对象会使得收集器的效率提升一些，但因为内存分配和访问相比垃圾收集频率要高得多，这部分的耗时增加，总吞吐量仍然是下降的。

另外，还有一种混合方案：虚拟机在平时多数时间采用标记-清除算法，暂时容忍内存碎片存在，直到内存空间碎片化程度超过阈值时，再采用标记-整理算法。基于标记-清除算法的 CMS 收集器面临空间碎片过多时采用的就是这种处理办法。

HotSpot 垃圾收集算法实现细节

在了解了垃圾收集算法理论的宏观框架之后，让我们再来详细了解一下 HotSpot 垃圾收集算法的实现细节。

根节点枚举

虽然固定的 GC Roots 节点在全局性的引用（如常量或类静态属性）与执行上下文（如栈帧中的本地变量表）中目标明确，但要实现高效的查找还是很困难的。随着 Java 应用规模的不断扩大，方法区的大小通常就有几百上千兆，里面的类、常量等更是极多，如果要逐个检查以这里为起点的引用，肯定需要消耗大量时间。

迄今为止，所有的垃圾收集器在根节点枚举这一步骤都必须暂停用户线程。尽管可达性分析算法中查找引用链的过程已经可以与用户线程一起并发执行，但根节点枚举仍需要在保证一致性的快照中进行。否则，一旦在枚举过程中发生变化，分析出来的结果就无法保证准确性。即使是号称停顿时间可控或几乎不会发生停顿的 Shenandoah、ZGC 等新型低延迟收集器，在枚举根节点时也会停顿。

由于目前主流的 Java 虚拟机使用的是准确式垃圾收集，所以当用户线程停顿下来时，并不需要完全检查所有执行上下文和全局引用位置，虚拟机可以直接获取存放对象引用的位置。

注释
  • 准确式垃圾收集 (Precise Garbage Collection) 是一种垃圾回收算法，它可以精确地找出程序中哪些对象是垃圾，以便将其回收。在这种算法中，垃圾收集器必须遍历整个堆内存，标记所有存活的对象，并回收未被标记的对象。
    • 准确式垃圾收集通常采用的是"标记-清除"、“标记-复制”、“标记-整理"等算法，其核心是在垃圾回收过程中 进行可达性分析，即标记程序中所有仍在使用的对象，将其保留下来，而未被标记的对象则被认为是垃圾并被回收。
    • 准确式垃圾收集通常需要在垃圾回收期间暂停程序执行，以便进行全局的可达性分析。但现代的垃圾回收器已经可以做到分代、增量、并发、并行等技术手段，以尽量减少垃圾回收期间的停顿时间，提高应用程序的响应性和吞吐量。
  • 非准确式垃圾收集 (Non-precise Garbage Collection) 相对于准确式垃圾收集，它不需要精确地确定哪些对象是可达的，而是通过某种简化的方式来判断哪些对象可能是垃圾，从而进行回收。这种算法的主要优点是速度快，但代价是回收可能不够精确，可能会回收一些仍然被引用的对象，或者一些垃圾对象被误判为存活对象而未被回收。

OopMap 数据结构

HotSpot 使用一组名为 OopMap 的数据结构来达到这个目的：一旦类加载动作完成，HotSpot 就会计算对象内部的偏移量，以及这些偏移量上是什么类型的数据。在即时编译过程中，HotSpot 也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样，在垃圾收集器扫描时，就可以直接得知这些信息，而不需要真正一个不漏地从方法区等 GC Roots 开始查找。

下面代码是 HotSpot 虚拟机客户端模式下生成的一段 String::hashCode() 方法的汇编代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

[Verified Entry Point]
0x026eb730: mov    %eax,-0x8000(%esp)
//......
;; ImplicitNullCheckStub slow case
0x026eb7a9: call   0x026e83e0       ; OopMap{ebx=Oop [16]=Oop off=142}
                                    ; *caload
                                    ; - java.lang.String::hashCode@48 (line 1489)
                                    ;   {runtime_call}
    0x026eb7ae: push   $0x83c5c18   ;   {external_word}
    0x026eb7b3: call   0x026eb7b8
    0x026eb7b8: pusha
    0x026eb7b9: call   0x0822bec0   ;   {runtime_call}
    0x026eb7be: hlt

可以看到，在 0x026eb7a9 处的 call 指令有一个 OopMap 记录，其中记录了 EBX 寄存器和栈中偏移量为 16 的内存区域中各有一个普通对象指针 (Ordinary Object Pointer，OOP) 的引用，有效范围为从调用指令开始直到 0x026eb730（指令流的起始位置）加上 142（OopMap 记录的偏移量）= 0x026eb7be，也就是 hlt 指令为止的范围。

安全点

在 OopMap 的协助下，HotSpot 可以快速准确地完成 GC Roots 枚举，但由于会导致引用关系变化的指令非常多，为每一条指令都生成对应的 OopMap 会消耗大量的额外存储空间。因此 HotSpot 只在特定的位置记录了这些信息，这些位置被称为安全点 (Safepoint)，所有到达安全点的线程都需要停顿下来，然后再进行垃圾收集相关的操作。

安全点机制要求用户程序在执行到安全点之后才能启动垃圾收集。因此，安全点的选择不能太少，以免收集器等待时间过长；也不能太频繁，以免增加收集器运行时的内存负担。安全点的位置主要基于“是否具有使程序长时间执行的特征”来确定。具有使程序长时间执行的特征包括方法调用、循环跳转、异常跳转等。这些指令的执行可能涉及大量的内存访问和数据处理，因此容易被用作安全点。

在垃圾收集时，需要确保所有线程（除了执行JNI调用的线程）都能迅速到达最近的安全点并停顿。实现方案有两种：抢先式中断 (Preemptive Suspension) 和主动式中断 (Voluntary Suspension)：

  • 抢先式中断不需要线程的执行代码主动配合，在垃圾收集发生时，系统首先中断所有用户线程。如果发现有线程被中断时不在安全点上，就恢复这条线程的执行，让它稍后再重新中断，直到到达安全点为止。现在几乎没有虚拟机采用抢先式中断，因为中断机制对指令流水线的破坏太暴力了。
  • 主动式中断指的是当垃圾收集需要中断线程时，简单地设置一个标志位。各个线程执行过程中会轮询这个标志，一旦发现中断标志为 true，则会在最近的安全点上主动挂起。轮询标志的地方和安全点是重合的，同时还需要在所有创建对象和需要在 Java 堆上分配内存的地方检查是否即将发生垃圾收集，以避免没有足够的内存分配新对象。

由于轮询操作会频繁执行，因此必须足够高效。HotSpot 使用内存保护陷阱的方式，把轮询操作精简到了只有一条汇编指令。下面的 test 指令就是 HotSpot 生成的轮询指令：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

0x01b6d627: call   0x01b2b210          ; OopMap{[60]=Oop off=460}
                                       ; *invokeinterface size
                                       ; - Client1::main@113 (line 23)
                                       ;   {virtual_call}
    0x01b6d62c: nop                    ; OopMap{[60]=Oop off=461}
                                       ; *if_icmplt
                                       ; - Client1::main@118 (line 23)
    0x01b6d62d: test   %eax,0x160100   ;   {poll}
    0x01b6d633: mov    0x50(%esp),%esi
    0x01b6d637: cmp    %eax,%esi

当需要暂停用户线程时，虚拟机把 0x160100 的内存页设置为不可读，那线程执行到 test 指令时就会产生一个自陷异常信号，然后在预先注册的异常处理器中挂起线程实现等待，这样仅通过一条汇编指令便完成安全点轮询和触发线程中断了。

安全区域

安全点机制保证了程序执行时，在较短的时间内就会遇到可进入垃圾收集状态的安全点，但对于那些没有被分配时间片而处于休眠或阻塞状态的线程，就无能为力了。这些线程既无法响应中断请求，也不能走到安全点挂起自己，而虚拟机也不能一直等待线程获得时间片。为了解决这种情况，HotSpot 引入了安全区域（Safe Region）的概念。

安全区域可以看作是代码中的一个片段，该片段需要保证区间内的引用关系不会发生变化，因此在这个区域中的任意位置开始垃圾收集都是安全的。

当用户线程执行到安全区域内的代码时，首先会标记自己已经进入了安全区域，这样在这段时间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。当线程要离开安全区域时，它需要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的阶段）。如果完成了，线程就当什么事都没发生过，继续执行；否则它就必须一直等待，直到收到可以离开安全区域的信号。

在实际应用中，安全区域常用于需要访问底层资源的代码块。这些代码块执行耗时较长，且通常需要长时间休眠（典型的例子就是 I/O 操作），进而导致线程无法及时响应中断请求。

记忆集

记忆集是为了解决跨代引用的问题而设计的。在垃圾收集器对新生代进行垃圾回收时，为了避免扫描整个老年代，垃圾收集器会在新生代中建立记忆集数据结构，记录所有跨越新生代和老年代的引用。

Note
事实上并不只有新生代、老年代间才存在跨代引用的问题，所有涉及部分区域收集 (Partial GC) 行为的垃圾收集器，典型的如 G1、ZGC 和 Shenandoah 收集器，都会面临相同的问题。

如果我们不考虑效率和成本的话，最简单的实现可以用非收集区域中所有含跨代引用的对象数组来实现这个数据结构，伪代码如下：

1
2
3

Class RememberedSet {
    Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE];
}

在垃圾收集的场景中，收集器只需要通过记忆集判断某一块非收集区域中的某个对象是否存在指向收集区域的引用，而不需要了解这些跨代引用的全部细节。因此，在实现记忆集时，设计者可以选择更粗糙的记录粒度来减少存储和维护成本。

下面列举了一些可供选择的记录精度：

  • 字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的 32 位或 64 位，这个精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针。
  • 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
  • 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。

以上三种精度中，最常用的记录精度是卡精度，其实现形式一般被称作 “卡表” (Card Table)。

卡表

卡表 (Card Table) 是一种在分代垃圾收集器中使用的一种记忆集实现，用于记录跨代指针和非收集区域之间的引用关系，以提高跨代垃圾收集的效率。

HotSpot 虚拟机中的卡表就是一个字节数组。以下代码是 HotSpot 默认的卡表标记逻辑：

1

CARD_TABLE [this address >> 9] = 0;
  • CARD_TABLE 中的每一个元素都对应着其标识的内存区域中的一块特定大小的内存块，这个内存块被称作 “卡页” (Card Page)。一般来说，卡页大小都是以 2 的 N 次幂的字节数，通过上面代码可以看出 HotSpot 中使用的卡页是 2 的 9 次幂，即 512 字节。
  • 如果卡表标识内存区域的起始地址是 0x0000 的话，数组 CARD_TABLE 的第 0、1、2 号元素，分别对应了地址范围为 0x0000～0x01FF、0x0200～0x03FF、0x0400～0x05FF 的卡页内存块。

在卡表中，一个卡页通常包含不止一个对象，只要卡页内有一个或多个对象的字段存在着跨代指针，那么对应卡表的数组元素的值就会被设为 1，被称为这个页变脏 (Dirty)，否则标识为 0。在垃圾收集发生时，只需筛选出卡表中变脏的元素，就能轻松确定哪些卡页内存块中包含跨代指针，将其加入 GC Roots 扫描即可。

卡表的实现通常需要使用硬件的特性来提高扫描的效率，例如 x86 架构的处理器支持 PCD (Page-Level Cache Disable) 和 PWT (Page-Level Write Through) 特性，可以避免卡表中标记为 dirty 的卡片被缓存在处理器的 L1 缓存中，从而减少扫描的开销。

写屏障

写屏障 (Write Barrier) 是一种与并发垃圾收集密切相关的技术。它是垃圾收集器在进行并发标记阶段，通过记录对象引用关系变化的技术，保证在并发标记期间不会遗漏任何存活对象。

在 Java 虚拟机的垃圾收集器中，有两种写屏障技术：基于插桩的写屏障和基于编译器的写屏障。

  • 基于插桩的写屏障就是在程序运行过程中，为每个对象插入一个钩子 (Hook)，当程序执行修改对象引用的指令时，钩子就会被触发，记录下这次引用的变化。
  • 基于编译器的写屏障则是在编译器对程序进行优化的过程中，为对象引用的修改点插入钩子。这种方式可以减少在程序运行时对修改点的遍历，提高垃圾收集器的执行效率。

写屏障是垃圾收集器实现并发标记的关键技术之一，可以确保垃圾收集器在进行并发标记时不会错过任何存活对象，同时也能减少并发标记过程中的内存占用，提高垃圾收集器的效率。

并发的可达性分析

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的。可达性分析算法理论上要求全过程都基于一个能保障一致性的快照来分析，这意味着必须全程冻结用户线程的运行。在根节点枚举过程中，由于 GC Roots 数量少而且有各种优化技巧加持（如 OopMap），它带来的停顿已经非常短暂且相对固定了（不随堆容量线性增长）。但是，从 GC Roots 继续遍历对象图的过程不可避免地与 Java 堆的容量正相关：堆越大，存储的对象越多，对象图结构越复杂，停顿时间就越长。标记阶段是所有追踪式垃圾收集算法的共有阶段，因此也是各类算法优化的重点。

为什么标记过程依赖一致性快照？

JVM 的并发标记过程依赖一致性快照，是因为在并发标记的过程中，应用程序线程可能会修改对象图的引用关系。如果没有一致性快照，允许用户线程修改引用关系与收集器标记过程同时进行，会导致以下两个问题：

  • 原本消亡的对象被错误标记为存活：这种还能忍受，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好。
  • 把原本存活的对象错误标记为已消亡：这就致命了，程序会直接崩溃。

下面我们通过三色标记 (Tri-color Marking) 工具来演示这样的致命错误具体是如何产生的：

三色标记工具演示
三色标记工具

把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

  • 白色：表示对象尚未被垃圾收集器访问过。

    显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。

  • 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

    在具体的实现中，可以将正在分析的对象置为灰色，待分析完该对象的引用关系后，再将其标记为黑色。

  • 黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。

    黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象。

因此，为了保证垃圾收集的准确性，需要在标记过程中使用一致性快照来冻结对象图，以保证对象图的引用关系不会在标记过程中发生变化。

如何解决并发扫描时对象消失的问题？

Wilson 于 1994 年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问题（即原本应该是黑色的对象被误标为白色）：

  • 赋值器插入了一条或多条从黑色对象到白色对象的新引用；
  • 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

因此，只要破坏这两个条件中的任意一个，就能解决这个问题。由此分别产生了以下两种方案：

  • 增量更新 (Incremental Update)：

    增量更新要破坏的是第一个条件：当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来。等并发扫描结束后，将这些记录过的引用关系中的黑色对象作为根，重新扫描一次。简单来说，黑色对象一旦插入指向白色对象的引用，就会重新变为灰色对象。

  • 原始快照 (Snapshot At The Beginning, SATB)：

    原始快照要破坏的是第二个条件：当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。这也可以简化理解为，无论引用关系删除与否，重新扫描时都会使用开始扫描那一刻的对象图快照。

以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。在 HotSpot 虚拟机中，增量更新和原始快照这两种解决方案都有实际应用。比如 CMS 是基于增量更新来做并发标记的，G1、Shenandoah 则是用原始快照来实现的。

至此，JVM 垃圾收集算法的核心内容就介绍完了。

  1. 这里的“大小”指的是变量槽的数量，不同虚拟机实现具体使用多少比特来实现一个变量槽则不同。 ↩︎

  2. 按照《Java 虚拟机规范》所述，所有的对象实例以及数组都应当在堆上分配，但目前栈上分配、标量替换等优化手段导致这一结论不再绝对。 ↩︎

  3. 永久代有一个 -XX：MaxPermSize 的上限，即使不设置也有默认大小。相比之下，J9 和 JRockit 只要没有触及进程可用内存的上限，就不会出现问题。此外，由于永久代的原因，极少数方法（例如 String::intern()）会导致不同虚拟机之间表现不同。鉴于 HotSpot 未来的发展，JDK 6 时，HotSpot 开发团队计划放弃使用永久代，逐步采用本地内存 (Native Memory) 来实现方法区。 ↩︎

  4. Java 堆内的空间都是预先申请好的，使用时可以直接在应用层进行分配，因此开销较低。 ↩︎

  5. 通常能单独发生收集行为的只是新生代，所以这里“反过来”的情况只是理论上允许，实际上除了 CMS 收集器，其他收集器都不存在只针对老年代的收集。 ↩︎

  6. 通常标记-清除算法也是需要停顿用户线程来标记、清理可回收对象的，只是停顿时间相对而言要来的短而已。 ↩︎

  7. 此语境中，吞吐量的实质是赋值器（Mutator，可以理解为使用垃圾收集的用户程序）与收集器的效率总和。 ↩︎

更新于 2021-11-20 
CC BY-NC-SA 4.0
Java
返回 | 主页
0%