JVM-垃圾回收算法

前言

垃圾收集算法可以划分为“引用计数式垃圾收集”（Reference Counting GC）和“追踪式垃圾收集”（Tracing GC）两大类，这两类也常被称作“直接垃圾收集”和“间接垃圾收集”^[1]。JVM 中并不涉及引用计数式垃圾回收，所以下面只会介绍关于追踪式垃圾回收相关的算法。

垃圾标记

在具体介绍垃圾回收算法前，先讲讲 JVM 是如何标记将一个对象为垃圾的。

引用计数算法

给每个对象添加一个引用计数器，每多一次引用，计数器加 1；每有一个引用失效，计数器减 1。当计数器值为 0 时，该对象就可以被回收。

该算法简单、高效，不需要 GC 做额外的工作。但它无法解决循环引用问题（或者需要额外的复杂处理），而且需要实时技术，增大系统开销。

根搜索算法

主流的 JVM 都采用根搜索算法。通过以 GC Roots 作为起点，根据引用向下搜索，搜索过程的路径称为引用链。如果一个对象到 GC Roots 没有任何引用链，则表示该对象可能被回收。

GC Roots，是不需要回收的对象。一般有以下几种：

虚拟机栈、本地方法栈中栈帧的本地变量表中所引用的对象
方法区中的类静态属性所引用的对象
方法区中的常量所引用的对象
虚拟机内部的引用，如基本数据类型对应的 Class 对象，常驻的异常对象，系统类加载器
同步锁持有的对象
反映 Java 虚拟机内部情况的 JMXBean、JVMTI 中注册的回调、本地代码缓存等
跨代引用，老年代中的部分对象（CardTable 记录）

上面说到可能被回收，对象需要两次标记才会被判断为可回收。第一次就是通过根搜索算法，搜索不到的对象会判断是否需要（没有覆盖 finalize() 或方法已经执行过就视为不需要）执行 finalize() 方法，而选择进入 F-Queue 队列。在 F-Queue 中的对象，有机会通过 finalize() 方法重新被引用上，避免回收（finalize() 方法只能执行一次）。其它情况下，对象将被打上第二次标记，等待回收。

引用类型

JDK 1.2 之后，对引用概念进行了扩充。

强引用（Strongly Reference）：普遍存在的引用类型。强引用所引用的对象，是不会被垃圾回收器回收掉的。
软引用（Soft Reference）：通过 SoftReference 实现。只有在内存溢出前，这类对象会进入回收范围，释放内存。仍没有足够内存则抛出溢出异常。
弱引用（Weak Reference）：通过 WeakReference 实现。每次进行垃圾回收，这类对象的内存都会被回收释放。
虚引用（Phantom Reference）：通过 PhantomReference 实现。对象是否有虚引用存在，对它的生存时间都没有影响，也无法通过虚引用获取该对象。虚引用的作用是在对象被垃圾回收器回收时，收到系统通知。

标记-复制算法

一种半区复制算法的垃圾回收算法。将堆内存分为两块大小相同的区域，进行内存分配时，只使用其中一块。当使用中的那块区域内存不足时，进行垃圾回收。将存活的对象复制到另一块区域，并将原来的区域一次性清理掉。

这种回收算法实现简单，不会造成内存空间碎片，当回收的对象占多数时，需要复制的对象就少，执行高效。但当存活的对象占多数时，需要进行耗时的大量对象复制。而且算法内存开销大，内存只有算来的一半可用。由于新生代（New Generation）的特点，JVM 基本都优先考虑使用复制算法来回收新生代的垃圾。

有研究表明，新生代中有 98% 活不过第一轮回收。根据新生代的特点，出现了一种优化的复制算法（Appel 式回收）。HotSpot 虚拟机的 Serial、ParNew 等新生代垃圾回收器均才用了这种策略。Appel 式回收 具体做法是，把新生代分为一块较大的 Eden 区和两块较小的 Survivor 区，内存分配时只使用 Eden 区和其中一块 Survivor 区。当 Eden 区内存不足时，进行垃圾回收，会将 Eden 区以及当前使用的 Survivor 中存活的对象，复制到另一块 Survivor区，然后直接清理 Eden 和那块用过的 Survivor。HotSpot 虚拟机默认 Eden 和 Survivor 的比例为 8:1。所以采用这种复制算法，也仅有 10% 的新生代内存会被浪费。虽说一般情况下，会有大量对象会回收，如果真发生了超 10% 内存对象存活的情况，虚拟机会依赖老年代进行分配担保。

标记-清除算法

标记-清除算法（Mark-Sweep），内部维护一张空闲内存表，记录可分配的内存地址和大小。回收过程分为标记和清除两个阶段。先标记出需要回收的对象，标记完成后统一清除。然后更新空闲内存表。

这种回收算法执行效率不稳定。堆中如果存在大量对象，而且又有大量待回收的对象，就需要进行大量的标记和清除操作，执行效率随对象数量增长而降低。垃圾回收后，还会造成大量内存碎片，后续分配较大内存时，找不到满足大小的连续空间，又会触发一次垃圾回收。维护的空闲内存表有额外开销，内存分配需要遍历空闲表，找出合适大小内存。