前言

今天方木就带大家聊聊 JVM 垃圾回收机制(GC) 中的垃圾回收算法，开发 Java 的小伙伴，不用像开发 C++ 的小伙伴一样，需要代码执行垃圾回收（Java 程序中不再需要使用的内存空间进行回收）， 但是作为合格 Java 开发，还是需要了解 「JVM垃圾回收机制」，不至于遇到 「堆内存不足、OOM、频繁GC等问题」 不知所措。

对象存活性判断

垃圾收回的前提需要 「判断对象存活性」，常用的对象存活性判断方法有「引用计数法」与「可达性分析」，不过由于引用计数法无法解决对象循环引用的问题，因此「主流的 JVM 倾向于使用可达性分析」。

Reference Counting（引用计数）

「引用计数器」在微软的 COM 组件技术中、Adobe 的 ActionScript3 种都有使用。「引用计数器的原理很简单」，对于一个对象 A，只要有任何一个对象引用了 A，则 A 的引用计数器就加 1，当引用失效时，引用计数器就减 1。只要对象 A 的引用计数器的值为 0，则对象 A 就不可能再被使用。引用计数器的实现也非常简单，只需要为每个对象配置一个整形的计数器即可。但是引用计数器有一个严重的问题，即无法处理循环引用的情况。因此，在 Java 的垃圾回收器中没有使用这种算法。一个简单的循环引用问题描述如下：有对象 A 和对象 B，对象 A 中含有对象 B 的引用，对象 B 中含有对象 A 的引用。此时，对象 A 和对象 B 的引用计数器都不为 0。但是在系统中却不存在任何第 3 个对象引用了 A 或 B。也就是说，A 和 B 是应该被回收的垃圾对象，但由于垃圾对象间相互引用，从而使垃圾回收器无法识别，引起内存泄漏。

引用树遍历

「引用树本质」是有根的图结构，它沿着对象的根句柄向下查找到活着的节点，并标记下来；其余没有被标记的节点就是死掉的节点，这些对象就是可以被回收的，或者说活着的节点就是可以被拷贝走的，具体要看所在 HeapSize 中 的区域以及算法，它的大致示意图如下图所示（注意这里是指针是单向的）：

首先，所有回收器都会通过一个标记过程来对存活对象进行统计。JVM 中用到的所有现代 GC 算法在回收前都会先找出所有仍存活的对象。下图中所展示的JVM中的内存布局可以用来很好地阐释这一概念：

而所谓的 「GC 根对象」包括：「当前执行方法中的所有本地变量及入参、活跃线程、已加载类中的静态变量、JNI 引用」。接下来，垃圾回收器会对内存中的整个对象图进行遍历，它先从 GC 根对象开始，然后是根对象引用的其它对象，比如实例变量。回收器将访问到的所有对象都标记为存活。存活对象在上图中被标记为蓝色。当标记阶段完成了之后，所有的存活对象都已经被标记完了。其它的那些（上图中灰色的那些）也就是 GC 根对象不可达的对象，也就是说你的应用不会再用到它们了。这些就是垃圾对象，回收器将会在接下来的阶段中清除它们。

不过那些发现不能到达 GC Roots 的对象并不会立即回收，在真正回收之前，对象至少要被标记两次。当第一次被发现不可达时，该对象会被标记一次，同时调用此对象的 finalize() 方法（如果有）；在第二次被发现不可达后，对象被回收。利用 finalisze() 方法，对象可以逃离一次被回收的命运，但是只有一次。逃命方法如下，需要在 finalize() 方法中给自己加一个 GCRoots 中的 hook：

public class EscapeFromGC {
  
 public static EscapeFromGC hook;
  
  @Override
  protected void finalize() throws Throwable {
    super.finalize();
        System.out.println("finalize mehtod executed!");
        EscapeFromGC.hook = this;
  }
  
}

Mark-Sweep（标记-清除算法）

「标记-清除算法」将垃圾回收分为两个阶段：「标记阶段和清除阶段」。一种可行的实现是，在标记阶段首先通过根节点，标记所有从根节点开始的较大对象。因此，未被标记的对象就是未被引用的垃圾对象。然后，在清除阶段，清除所有未被标记的对象。该算法最大的问题是存在大量的空间碎片，因为回收后的空间是不连续的。在对象的堆空间分配过程中，尤其是大对象的内存分配，不连续的内存空间的工作效率要低于连续的空间。

从概念上来讲，标记-清除算法使用的方法是最简单的，只需要忽略这些对象便可以了。也就是说当标记阶段完成之后，未被访问到的对象所在的空间都会被认为是空闲的，可以用来创建新的对象。这种方法需要使用一个空闲列表来记录所有的空闲区域以及大小。对空闲列表的管理会增加分配对象时的工作量。这种方法还有一个缺陷就是——虽然空闲区域的大小是足够的，但却可能没有一个单一区域能够满足这次分配所需的大小，因此本次分配还是会失败（在 Java 中就是一次 OutOfMemoryError）。

Copying（复制算法）

将现有的内存空间分为两快，每次只使用其中一块，在垃圾回收时将正在使用的内存中的存活对象复制到未被使用的内存块中，之后，清除正在使用的内存块中的所有对象，交换两个内存的角色，完成垃圾回收。如果系统中的垃圾对象很多，复制算法需要复制的存活对象数量并不会太大。因此在真正需要垃圾回收的时刻，复制算法的效率是很高的。又由于对象在垃圾回收过程中统一被复制到新的内存空间中，因此，可确保回收后的内存空间是没有碎片的。该算法的缺点是将系统内存折半。

Java 的新生代串行垃圾回收器中使用了「复制算法」的思想。新生代分为 eden 空间、from 空间、to 空间 3 个部分。其中 from 空间 和 to 空间 可以视为用于复制的两块大小相同、地位相等，且可进行角色互换的空间块。from 和 to 空间也称为 survivor 空间，即幸存者空间，用于存放未被回收的对象。在垃圾回收时，eden 空间中的存活对象会被复制到未使用的 survivor 空间中 (假设是 to)，正在使用的 survivor 空间 (假设是 from) 中的年轻对象也会被复制到 to 空间中 (大对象，或者老年对象会直接进入老年带，如果 to 空间已满，则对象也会直接进入老年代)。此时，eden 空间和 from 空间中的剩余对象就是垃圾对象，可以直接清空，to 空间则存放此次回收后的存活对象。这种改进的复制算法既保证了空间的连续性，又避免了大量的内存空间浪费。

Mark-Compact（标记-压缩算法）

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

「标记-压缩算法」是一种老年代的回收算法，它在标记-清除算法的基础上做了一些优化。也首先需要从根节点开始对所有可达对象做一次标记，但之后，它并不简单地 清理未标记的对象，而是将所有的存活对象压缩到内存的一端。之后，清理边界外所有的空间。这种方法既避免了碎片的产生，又不需要两块相同的内存空间，因此，其性价比比较高。

通用垃圾回收算法对比

对上面阐述三种比较基础的垃圾收回算法进行对比：

Incremental Collecting（增量回收算法）

在垃圾回收过程中，应用软件将处于一种 CPU 消耗很高的状态。在这种 CPU 消耗很高的状态下，应用程序所有的线程都会挂起，暂停一切正常的工作，等待垃圾回收的完成。如果垃圾回收时间过长，应用程序会被挂起很久，将严重影响用户体验或者系统的稳定性。

「增量算法现代垃圾回收的一个前身，其基本思想」是，如果一次性将所有的垃圾进行处理，需要造成系统长时间的停顿，那么就可以让垃圾收集线程和应用程序线程交替执行。每次，垃圾收集线程只收集一小片区域的内存空间，接着切换到应用程序线程。依次反复，直到垃圾收集完成。使用这种方式，由于在垃圾回收过程中，间断性地还执行了应用程序代码，所以能减少系统的停顿时间。但是，因为线程切换和上下文转换的消耗，会使得垃圾回收的总体成本上升，造成系统吞吐量的下降。

Generational Collecting（分代回收算法）

「分代回收器」是增量收集的另一个化身，根据垃圾回收对象的特性，不同阶段最优的方式是使用合适的算法用于本阶段的垃圾回收，分代算法即是基于这种思想，它将内存区间根据对象的特点分成几块，根据 每块内存区间的特点，使用不同的回收算法，以提高垃圾回收的效率。以 Hot Spot 虚拟机为例，它将所有的新建对象都放入称为年轻代的内存区域，年轻代的特点是对象会很快回收，因此，在年轻代就选择效率较高的复制算法。当一个对象经过几 次回收后依然存活，对象就会被放入称为老生代的内存空间。在老生代中，几乎所有的对象都是经过几次垃圾回收后依然得以幸存的。因此，可以认为这些对象在一 段时期内，甚至在应用程序的整个生命周期中，将是常驻内存的。如果依然使用复制算法回收老生代，将需要复制大量对象。再加上老生代的回收性价比也要低于新 生代，因此这种做法也是不可取的。根据分代的思想，可以对老年代的回收使用与新生代不同的标记-压缩算法，以提高垃圾回收效率。

Concurrent Collecting（并发回收算法）

所谓的「并发回收算法」即是指垃圾回收器与应用程序能够交替工作，并发回收器其实也会暂停，但是时间非常短，它并不会在从开始回收寻找、标记、清楚、压缩或拷贝等方式过程完全暂停服务，它发现有几个时间比较长，一个就是标记，因 为这个回收一般面对的是老年代，这个区域一般很大，而一般来说绝大部分对象应该是活着的，所以标记时间很长，还有一个时间是压缩，但是压缩并不一定非要每 一次做完 GC 都去压缩的，而拷贝呢一般不会用在老年代，所以暂时不考虑；所以他们想出来的办法就是：第一次短暂停机是将所有对象的根指针找到，这个非常容 易找到，而且非常快速，找到后，此时 GC 开始从这些根节点标记活着的节点（这里可以采用并行），然后待标记完成后，此时可能有新的 内存申请以及被抛弃（java 本身没有内存释放这一概念），此时 JVM 会记录下这个过程中的增量信息，而对于老年代来说，必须要经过多次在 survivor 倒腾后才会进入老年代，所以它在这段时间增量一般来说会非常少，而且它被释放的概率前面也说并不大（JVM如果不是完全做 Cache，自 己做 pageCache 而且发生概率不大不小的 pageout 和 pagein 是不适合的）；JVM 根据这些增量信息快速标记出内部的节点，也是非常快速 的，就可以开始回收了，由于需要杀掉的节点并不多，所以这个过程也非常快，压缩在一定时间后会专门做一次操作，有关暂停时间在 Hotspot 版本，也就是 SUN 的 jdk 中都是可以配置的，当在指定时间范围内无法回收时，JVM 将会对相应尺寸进行调整，如果你不想让它调整，在设置各个区域的大小时，就使用定 量，而不要使用比例来控制；当采用并发回收算法的时候，一般对于老年代区域，不会等待内存小于 10%左右的时候才会发起回收，因为并发回收是允许在回收的 时候被分配，那样就有可能来不及了，所以并发回收的时候，JVM可能会在 68%左右的时候就开始启动对老年代 GC 了。

总结

最后，简单总结一下，本次我们探讨了「六种垃圾回收算法」。基础的垃圾回收算法有「标记-清除算法、标记-整理以及复制算法」。另外还探讨了「三种综合性的垃圾回收算法」，即「增量回收算法、分代回收算法以及并发回收算法」。