原文来自公众号：猿人谷

在Java中内存是由虚拟机自动管理的，虚拟机在内存中划出一片区域，作为满足程序内存分配请求的空间。内存的创建仍然是由程序猿来显示指定的，但是对象的释放却对程序猿是透明的。就是解放了程序猿手动回收内存的工作，交给垃圾回收器来自动回收。

在虚拟机中，释放哪些不再被使用的对象所占空间的过程称为垃圾收集（Garbage Collection，GC）。负责垃圾收集的程序模块，成为垃圾收集器（Garbage Collector）。

既然虚拟机已经帮我们把垃圾自动处理了，为什么还要去了解GC和内存分配呢？

当需要排查各种内存溢出、内存泄漏问题时，当垃圾收集成为系统达到更高并发量的瓶颈时，我们就需要对虚拟机的自动管理技术实施必要的监控和调节了。这也是JVM调优，故障排查，重点需要掌握的知识了。

本篇我们的重点是介绍何谓垃圾及垃圾回收算法，那我们就要弄清到底什么是垃圾？能不能设计一种强大的垃圾回收算法来解决垃圾回收的所有问题？肯定是没有的，后面介绍的每一种垃圾回收算法都有它得天独厚的优点，也有它避之不及的缺点。针对具体的场景，灵活运用方是上策。

希望大家能带着如下问题进行学习，会收获更大。

1. 什么是垃圾？
2. 如何回收垃圾？
3. 有没有一种垃圾回收算法能像银弹一样解决所有垃圾所有？
4. GC的分类是什么样的？（Minor GC、Major GC、Full GC）
5. Stop-the-world是什么？
6. 如何避免全堆扫描？

1 垃圾回收

在堆里面存放着Java世界中几乎所有的对象实例，垃圾收集器在堆进行回收前，第一件事就是要确定这些对象之中哪些还“存活”着，哪些已经“死亡”（即不可能再被任何途径使用的对象）。垃圾回收，其实就是将已经分配出去的，但不再使用的内存回收，以便能够再次分配。在Java虚拟机的规范中，垃圾指的就是死亡的对象所占据的堆空间。

那怎么确定一个对象是存活还是死亡呢？

1.1 引用计数算法

给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1；当引用失效时，计数器值就减1；任何时刻计数器为0的对象就是不可能再被使用的。也就是说，需要截获所有的引用更新操作，并且相应地增减目标对象的计数器。

题外话：记得研一那段时间对iOS开发感兴趣，找个公司去实习，现学现搞iOS开发，当时是做了一个模拟炒股的app。用的就是Objective-C，这门语言起初管理内存的方式就是用的这种引用计数算法，不过后面也有了自动管理内存。接触的对象多了，发现很多东西在本质的原理有非常多的相似之处。

引用计数算法缺点：

• 需要额外的空间来存储计数器，以及繁琐的更新操作。
• 无法处理循环引用对象。

其中无法处理循环引用对象，算是引用计数法的一个重大漏洞。

1.2 可达性分析算法

可达性是指，如果一个对象会被至少一个在程序中的变量通过直接或间接的方式被其他可达的对象引用，则称该对象是可达的（reachable）。更准确的说，一个对象只有满足下述两个条件之一，就会被判断为可达的：

• 本身是根对象。根（Root）是指由堆以外空间访问的对象。JVM中会将一组对象标记为根，包括全局变量、部分系统类，以及栈中引用的对象，如当前栈帧中的局部变量和参数。
• 被一个可达的对象引用。

这个算法的基本思路就是通过一系列的成为“GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链（Reference Chain），当一个对象到GC Roots没有任何引用链相连（即从GC Roots到这个对象不可达），则证明此对象是不可用的。

GC Roots又是什么呢？可以暂时理解为由堆外指向堆内的引用。

在Java语言中，可以作为GC Roots的对象包括下面几种：

• 虚拟机栈（栈帧中的本地变量表）中引用的对象。
• 方法区中类静态属性引用的对象。
• 方法区中常量引用的对象。
• 本地方法栈中JNI（即一般说的Native方法）引用的对象。
• 已启动且未停止的Java线程。

可达性分析算法可以解决引用计数算法不能解决的循环引用问题。举个例子，即便对象a和b相互引用，只要从GC Roots出发无法到达a或者b，那么可达性分析便不会将它们加入存活对象合集之中。

关于Java中的引用的定义及分类（强引用、软引用、弱引用、虚引用）会在单独出一篇进行详细介绍，Java引用的内容虽然有点冷门，但是很多公司面试的常考点。

可达性分析算法本身虽然很简明，但是在实践中还是有不少其他问题需要解决的。比如，在多线程环境下，其他线程可能会更新已经访问过的对象中的引用，从而造成误报（将引用设置为null）或者漏报（将引用设置为未被访问过的对象）。误杀还可以接受，Java虚拟机至多损失了部分垃圾回收的机会。漏报就问题大了，因为垃圾回收器可能回收事实上仍被引用的对象内存。一旦从原引用访问已经被回收了的对象，则很有可能会直接导致Java虚拟机奔溃。

2 垃圾回收算法

上面我们介绍什么是Java中的垃圾，接下来我们就开始介绍如何高效的回收这些垃圾。

2.1 标记-清除算法

标记-清除（Mark-Sweep）算法可以分为两个阶段：

• 标记阶段：标记出所有可以回收的对象。
• 清除阶段：回收所有已被标记的对象，释放这部分空间。

该算法存在如下不足：

1. 内存碎片。由于Java虚拟机的堆中对象必须是连续分布的，因此可能出现总空闲内存足够，但是无法分配的极端情况。无法找到足够的连续内存，而不得不提前触发一次垃圾收集动作。
2. 分配效率较低。如果是一块连续的内存空间，那么我们可以通过指针加法（pointer bumping）来做分配。而对于空闲列表，Java虚拟机则需要逐个访问列表中的项，来查询能够放入新建对象的空闲内存。

标记-清除算法的示意图如下：

2.2 复制算法

复制算法的过程如下：

• 划分区域：将内存区域按比例划分为1个Eden区作为分配对象的“主战场”和2个幸存区（即Survivor空间，划分为2个等比例的from区和to区）。
• 复制：收集时，打扫“战场”，将Eden区中仍存活的对象复制到某一块幸存区中。
• 清除：由于上一阶段已确保仍存活的对象已被妥善安置，现在可以“清理战场”了，释放Eden区和另一块幸存区。
• 晋升：如在“复制”阶段，一块幸存区接纳不了所有的“幸存”对象。则直接晋升到老年代。

该算法解决了内存碎片化问题，但堆空间的使用效率极其低下。在对象存活率较高时，需要进行较多的复制操作，效率会变得很低。

2.3 标记-整理算法

该算法分为两个阶段：

• 标记阶段：标记出所有可以回收的对象。
• 压缩阶段：将标记阶段的对象移动到空间的一端，释放剩余的空间。

该算法的标记过程与标记-清除算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。

解决了内存碎片的问题，也规避了复制算法只能利用一半内存区域的弊端。看起来很美好，但它对内存变动更频繁，需要整理所有存活对象的引用地址，在效率上比复制算法要差很多。

标记-整理算法的示意图如下：

2.4 分代收集算法

分代收集算法倒并没有什么新的思想，只是根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。

在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用标记-清理算法或标记-整理算法来进行回收。

3 HotSpot算法实现

3.1 枚举根节点

以可达性分析中从GC Roots节点找引用链这个操作为例，可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中。上面介绍可达性分析算法时有详细介绍GC Roots，可以参看上面。

3.2 安全点（Safepoint）

安全点，即程序执行时并非在所有地方都能停顿下来开始GC，只有在到达安全点时才能暂停。Safepoint的选定既不能太少以至于让GC等待时间太长，也不能过于频繁以致于过分增大运行时的负荷。

安全点的初始目的并不是让其他线程停下，而是找到一个稳定的执行状态。在这个执行状态下，Java虚拟机的堆栈不会发生变化。这么一来，垃圾回收器便能够“安全”地执行可达性分析。只要不离开这个安全点，Java虚拟机便能够在垃圾回收的同时，继续运行这段本地代码。

程序运行时并非在所有地方都能停顿下来开始GC，只有在到达安全点时才能暂停。安全点的选定基本上是以程序“是否具有让程序长时间执行的特征”为标准进行选定的。“长时间执行”的最明显特征就是指令序列复用，例如方法调用、循环跳转、异常跳转等，所以具有这些功能的指令才会产生Safepoint。

对于安全点，另一个需要考虑的问题就是如何在GC发生时让所有线程（这里不包括执行JNI调用的线程）都“跑”到最近的安全点上再停顿下来。

两种解决方案：

• 抢先式中断（Preemptive Suspension）

  抢先式中断不需要线程的执行代码主动去配合，在GC发生时，首先把所有线程全部中断，如果发现有线程中断的地方不在安全点上，就恢复线程，让它“跑”到安全点上。现在几乎没有虚拟机采用这种方式来暂停线程从而响应GC事件。

• 主动式中断（Voluntary Suspension）

  主动式中断的思想是当GC需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时就自己中断挂起。轮询标志地地方和安全点是重合的，另外再加上创建对象需要分配内存的地方。

3.3 安全区域

指在一段代码片段中，引用关系不会发生变化。在这个区域中任意地方开始GC都是安全的。也可以把Safe Region看作是被扩展了的Safepoint。

4 扩展知识

4.1 GC分类

Minor GC：

• 针对新生代。
• 指发生在新生代的垃圾收集动作，因为java对象大多都具备朝生夕死的特性，所以Minor GC非常频繁，一般回收速度也比较快。
• 触发条件：Eden空间满时。

Major GC：

• 针对老年代。
• 指发生在老年代的GC，出现了Major GC，经常会伴随至少一次的Minor GC（但非绝对的，在Parallel Scavenge 收集器的收集策略里就有直接进行Major GC的策略选择过程）。Major GC的速度一般会比Minor GC慢10倍以上。
• 触发条件：Minor GC 会将对象移到老年代中，如果此时老年代空间不够，那么触发 Major GC。

Full GC：

• 清理整个堆空间。一定意义上Full GC 可以说是 Minor GC 和 Major GC 的结合。
• 触发条件：调用System.gc()；老年代空间不足；空间分配担保失败。

4.2 Stop-the-world

GC进行时必须停顿所有Java执行线程，这就是Stop-the-world。

可达性分析时必须在一个能确保一致性的快照中进行，这里“一致性”的意思是指在整个分析期间整个执行系统看起来就像被冻结在某个时间点上，不可以出现分析过程中对象引用关系还在不断变化的情况，这一点不满足的话分析结果准确性就无法得到保证。

Stop-the-world是通过安全点机制来实现的。当Java虚拟机接收到Stop-the-world请求，它便会等待所有的线程都到达安全点，才允许请求Stop-the-world的线程进行独占的工作。

4.3 卡表

有个场景，老年代的对象可能引用新生代的对象，那标记存活对象的时候，需要扫描老年代中的所有对象。因为该对象拥有对新生代对象的引用，那么这个引用也会被称为GC Roots。那不是得又做全堆扫描？成本太高了吧。

HotSpot给出的解决方案是一项叫做卡表（Card Table）的技术。该技术将整个堆划分为一个个大小为512字节的卡，并且维护一个卡表，用来存储每张卡的一个标识位。这个标识位代表对应的卡是否可能存有指向新生代对象的引用。如果可能存在，那么我们就认为这张卡是脏的。

在进行Minor GC的时候，我们便可以不用扫描整个老年代，而是在卡表中寻找脏卡，并将脏卡中的对象加入到Minor GC的GC Roots里。当完成所有脏卡的扫描之后，Java虚拟机便会将所有脏卡的标识位清零。

想要保证每个可能有指向新生代对象引用的卡都被标记为脏卡，那么Java虚拟机需要截获每个引用型实例变量的写操作，并作出对应的写标识位操作。

卡表能用于减少老年代的全堆空间扫描，这能很大的提升GC效率。