JVM基础回顾记录（二）：垃圾收集

上一篇介绍了jvm的内存模型，本篇将介绍虚拟机中最为复杂的一部分：垃圾收集，本篇会从垃圾回收前的准备工作到后面的收集阶段的方式以及HotSpot虚拟机对这些工作的实现做个较为系统的记录，方便自己以后查找阅读。

一、栈帧、变量类型、引用分析

讲解垃圾收集器的实现之前，结合之前讲的jvm内存区域划分，先来看下HotSpot虚拟机中对于对象的访问定位是怎样的，对象访问定位如下图所示：

一般来说，一个方法视为一个栈帧，栈帧内会存放当前方法所有的变量，这就是栈的本地变量表，变量分为基本类型变量和引用类型变量，基本类型是直接在栈空间分配存储空间的（也即是当前栈帧内，受-Xss一定的影响），而引用类型则是预先无法知晓其内存占用量为多大，因此需要动态分配内存，这就需要借助堆区的存储，这种一般是堆区创建对象实例，而栈帧内创建一个引用reference，其存放的实际上是指向堆区实例对象的地址，实例对象的内部也有很多成员变量，其次实例对象也会有一个指针指向方法区里的属于该对象的类型数据（这一步就标记了当前实例属于哪个Class）。

先来看一段程序：

代码块1

public class Student {
    private int id;
    private int age;
    private Teacher teacher;
}

public class Teacher {
    private int id;
}

public static void main(String[] args) {

    int a = 1;
    long b = 2L;

    Student student = new Student();
    student.setId(1);
    student.setAge(2);

    Teacher teacher = new Teacher();
    teacher.setId(1);

    student.setTeacher(teacher);
}

上面是很简单的一个程序，main方法里声明了一些变量以及初始化了一些对象，那么上面的程序执行过程中的引用关系表示为下图：

上图就是执行到main方法尾部的最终引用关系，我们知道像栈帧里的数据（本地变量表）随着方法的执行结束，自然就被释放了，因此像main方法里的a、b、student、teacher是不需要GC来关心的，GC需要关心的是图2里堆区的俩实例对象，这俩实例对象是不会随着栈帧的结束而被回收掉的，因此需要借助GC来进行回收，那么什么样的对象可以被回收呢？这又回到上一篇里对可达性分析算法的描述了，其实就是看看当前实例还有没有被GC Root引用，针对上例，GC Root就是student和teacher，这俩引用没了，引用局面就变成了下面这样：

很显然，两个实例已经失去了GC Root的引用，尽管Teacher实例还存在一个强引用，但是基于可达性分析算法的特性，也会被判定为“不可达”对象，最终俩实例会被GC回收掉。

到这里总结一下，栈帧里存放的本地变量表，存在两种类型的变量：基本类型&引用类型，基本类型由于预先知道要为其分配多大内存，因此会直接在栈帧内创建，创建完毕后随着栈帧的结束而销毁，引用变量（非基本类型的其他类型变量）由于预先并不清楚需要分配多大的内存，可能后续需要动态扩容等，需要放入堆空间，栈帧内保留一个指向其内存地址的引用变量，而放入堆空间意味着实例本身无法随着栈帧的消失而被释放，需要借助GC来完成回收。

二、预回收阶段

2.1：回收前的对象判活

通过第一部分，大致了解了两种变量类型，而GC需要关心的则是GC Root，典型的作为GC Root的类型，则是引用类型，而判定变量是否为引用类型变量，往往影响着GC的实现。

这里所处的阶段是预回收阶段，这个阶段的GC不会发生回收，所以先不说回收阶段的算法（下面将要介绍的标记-清除算法、标记-压缩算法、复制算法），GC要进入回收阶段，首先要做的事情就是判断出“哪些对象还是活着的”，那么这个阶段需要做的事情是分析出对象的存活状态，有哪些方式可以判断出对象的活性呢？这里有两种主要方式：引用计数&可达性分析算法，其中可达性分析算法是根据GC Root来进行判断的，所以需要关心栈帧里的引用类型变量，这个判断引用变量的方式，又分为保守式和准确式，这些判定方法的选择往往会影响GC的实现。

2.1.1：引用计数法

这种判定算法非常简单，给对象添加一个引用计数器，每当有一个地方引用它，就加1，每当一个引用失效，就减1，当引用计数器为0的时候，就认为该对象失活，处于可回收状态。但是这种算法是有缺陷的，比如对象的循环引用问题，如下：

A a = new A();
B b = new B();
a.b = b;
b.a = a;
a = null;
b = null;

如上代码，首先A、B的实例首先被a、b引用，这时加1，然后又被a.b、b.a引用一次，再次加1，然后a、b指向null，A、B实例失去了一个引用，但是计数器里的引用数还是1，单看上面的代码，A、B对象的实例应该是需要被回收的的，因为不存在任何方法栈的引用，反而是它们内部的属性互相引用着彼此，因此利用这个算法，很大程度上会造成内存泄漏的问题。jvm在上述代码中，也是会把A和B的实例对象给回收掉的，因此JVM并不是采用这种方法分析对象活性的。

2.1.2：可达性分析算法

这个算法的基本思路就是通过一系列的GC Roots的对象作为起点，然后从这些对象往下搜索，搜索走过的路径被称作“引用链”，当一个对象到GC Roots没有任何引用链相连时，则认为该对象死亡，GC Roots通常包含：

1. 虚拟机栈（栈帧中的本地变量表）中直接引用的对象
2. 方法区中的类静态属性直接引用的对象
3. 常量直接引用的对象
4. 本地方法栈中的native方法直接引用的对象

那么再利用此算法来看看上述AB循环依赖问题例子的引用变化：

通过图4可以看到，最后失去引用后，A、B的实例对象不再「可达」，最终会被判定为死亡对象并被回收。目前JVM的对象是否死亡也是通过该算法来判定的。

通过之前对可达性分析算法的介绍，这种判活方法主要根据判定一个对象是否直接或间接被一个GC Root对象引用，那么如何枚举出所有的GC Roots对象呢？目前有两种方式标记GC Roots对象：

2.1.2.1：可达性分析算法-保守式GC

如果JVM不选择记录下来栈帧中的变量哪些是引用类型，哪些是基本类型，对于GC而言，是无法知道变量类型，于是GC在回收前夕，需要遍历栈帧里的每一个变量，通过一些判定条件来分析出当前变量是否是引用变量，这些条件包括边界检查、对齐检查等，符合标准的，会被视为引用类型变量，否则为基本类型变量，这种判定方式比较简单，但是存在缺点，比如一个对象实际上没有任何引用存在了，但是仍然存在“疑似指向”它的指针，使得其逃过被GC的命运，这里“疑似指向”的意思是说，栈帧里可能恰好存在一个通过了条件检查（边界、对齐等检查都符合引用类型数据的条件）的变量，这时GC会认为它就是一个GC Root，被认为是GC Root后，其值正好对应上这个无用对象的地址，那么这个死对象仍然被认为“可达”，此时就会绕过了一次GC。

2.1.2.2：可达性分析算法-准确式GC

这是目前HotSpot虚拟机会采用的一种枚举GC Roots的方式（下面③会介绍实现方式），准确式GC不同于保守式GC，准确式GC是在枚举GC Roots时，GC已经知道了栈帧里所有对象的类型，这就免去了上面的不确定检查，因为预先知道栈帧里的变量是引用类型还是基本类型，那么枚举GC Roots就变的非常准确，这就是准确式GC。

2.1.2.3：HotSpot对于准确式GC的实现-OopMap

HotSpot虚拟机是采用OopMap来实现引用类型标记的，OopMap可以记录下当前栈帧里所有引用类型变量，GC时，只需要读取这里面的变量即可，很多资料会提到OopMap是提高了枚举GC Roots的效率，其实这不是OopMap真正的目的，OopMap的实现是HotSpot用来实现准确式GC的（重点在于准确性，而非提升效率），而这样处理，恰好对枚举效率的提升也起到一定的帮助（比如枚举时完全可以忽略掉那些基本类型变量了，因为他们不会被记到OopMap里）。

2.1.3：跨代引用&记忆集

2.1.3.1：记忆集的作用

在分代收集（参考下面3.4）理论中，每个分代采用不同的垃圾收集算法，其内部的对象也可能存在跨代引用的问题，比在回收新生代时，新生代里的某些对象有可能被老年代的对象所引用，所以为防止误判，要在固定的GC Roots之外，再遍历整个老年代中所有的对象来保证可达性分析的准确性，这就加重了枚举GC Roots的操作，但跨代引用相对于同代引用来说属于少数派，因此垃圾收集器通常会在新生代中建立一个名为记忆集的数据结构，用来避免扫描整个老年代，如下图：

不仅仅是新生代/老年代之间才有跨代引用的问题，所有涉及部分区域收集的垃圾收集器都面临同样的问题（比如G1、ZGC、Shenandoah）。

2.1.3.2：卡表

如何实现记忆集呢？方法有很多种，比如最简单的可以用非跨代区域中所有包含跨代引用的对象数组来实现，但这样比较占内存，而且维护成本很高，所以就有了另一个实现记忆集的方法：卡表

卡表的最简单形态就是一个字节数组，HotSpot虚拟机就是这么实现的，卡表中的每一个元素都对应一块特定大小的内存块（HotSpot中是512字节），这个内存块就是卡页，当对应卡页中的对象包含跨代指针时，就将该卡页对应的卡表元素标记为1，1代表脏元素，否则则是0，GC时，只要筛选出卡表中的脏元素，就能得到所有包含跨代指针的卡页，将这些包含跨代指针的对象加入到GC Roots扫描即可，整个过程如下：

2.1.3.3：写屏障

卡表变脏的条件时很明确的：有其他分代区域的对象引用了本区域对象时其对应的卡表元素应设置为dirty；那么如何实现这个标记的更新呢？

在HotSpot里是通过写屏障来实现这个过程的，写屏障可以理解成在虚拟机层面对引用对象赋值这个动作的AOP切面，也就是在引用对象赋值的前后可以做一些额外的逻辑处理，在赋值发生前处理叫做写前屏障，之后则叫写后屏障，下面就是写后屏障的示例代码：

代码块1

void oop_field_store(oop* field, oop new_value) {
  // 引用字段赋值
  *field = new_value;
  // 写后屏障，在这里完成卡表的状态更新
  post_write_barrier(field, new_value);
}

HotSpot虚拟机的许多收集器中都用到了写屏障，但在G1出现之前，其他收集器都是采用写后屏障做操作的；应用写屏障后，虚拟机就会为所有的赋值操作生成相应的指令。

2.2：STW

上面说了GC开始前针对对象的判活方法，HotSpot通过OopMap实现了准确式GC，现在来讲下GC前的准备工作，GC前往往需要将所有正在运行的线程挂起，这是为了防止一些引用在GC过程中还在不停的发生变化而做的一致性保护，这种行为叫做STW（Stop The World，我们下一节会介绍很多垃圾收集器，无论是哪一款，STW都是无法避免的），一般来说，STW发生时的线程中断，HotSpot虚拟机需要每个线程将自己的程序执行到指定位置，根据用户线程是否已经挂起而分为两种意义上的位置：

2.2.1：安全点（Safe Point）-用户线程非挂起

针对的是GC发生时还在正常运行的用户线程，这时候需要等待该线程主动运行到指定位置才中断线程，这些指定的位置，被称为安全点，安全点的意义是什么呢？上面说到HotSpot通过OopMap来完成准确式GC，但是引用关系的变化是不可避免的，每变化一次，就更新一次OopMap显然效率不高，因此JVM更新OopMap的实现就用到了安全点，当线程运行到安全点，记录下当前引用，更新至OopMap即可，这也就解释了为什么程序中断前必须要停靠在最近的安全点上。可作为安全点的位置有：循环末尾、方法临近返回前、方法调用后、抛出异常的位置。

2.2.2：安全区域（Safe Region）-用户线程挂起

意义类似安全点，主要针对那些GC发生时，处于“CPU让出状态（挂起）”的用户线程，这种状态下的线程是没能力运行到就近安全点的，针对此情况，便有了安全区域概念，安全区域是指在一段代码区域中，引用关系是不会发生变化的，在此区域的任意位置开始GC都是安全的。用户线程在运行到安全区域内，首先会标记自己已经到达了安全区域，GC时发现该线程已经进入安全区域，则不会再去管其状态（无视挂起状态），直接对其内部进行OopMap更新，完成GC Roots的枚举；当线程离开安全区域时（被唤起），就需要判断是否已经完成了GC或者GC Roots枚举，若完成则继续执行，否则就必须等待直到收到可以离开安全区域的信号为止。

2.2.3：STW中断线程的两种方式

安全点和安全区域均为HotSpot虚拟机为了保证枚举GC Roots的准确性而做出的实现，结合安全点、安全区域，在达到安全点时GC对线程的中断（STW）又分为两种中断方式：

2.2.3.1：抢先式中断

GC发生时，首先中断所有线程，然后检查各个用户线程是否执行到了安全点，如果没有，则恢复对应线程让其运行到安全点再次完成中断。

2.2.3.2：主动式中断

GC发生时，主动式中断不会直接中断线程，而是全局设置一个标志位，用户线程会不断的轮询这个标志位；当发现标志位为真时，线程会在最近的一个安全点主动中断挂起。

三、回收阶段-垃圾回收算法

第二部分讲的是GC前的准备工作，以及HotSpot在GC前针对枚举GC Roots的实现，下面来看下完成GC Roots枚举后的回收阶段的几种回收算法。

3.1：标记-清除算法

这是一种最基础的收集算法，这种算法分为两个阶段：

1. 标记出所有需要回收的对象（这里的标记使用可达性分析算法进行判定）
2. 标记完成后统一回收所有被标记的对象

这个算法两个阶段的效率都不高，而且会产生大量的内存碎片，碎片过多可能会导致无法找到连续内存存储较大的对象，所以会被迫提前触发一次GC，图示如下：

由上图可以看到，在回收后，产生了大量不连续的内存单元碎片。单纯从图5看，只能知道这个算法会产生内存碎片，并不能了解整个算法的细节，因此单纯通过上图，是没办法体现该算法效率问题的，图5是大部分资料里都会展示的一个最终态，算法细节则全部省略，导致很多时候，标记-清除算法相比复制算法的效率究竟弱在哪里没有很清晰的认知，下面，通过一幅图来说明下其具体的执行细节：

上图就是标记-清除算法的执行过程，首先从标记阶段到清除阶段，GC执行流程如下：

1. 把从root开始的可能被引用的对象（可达对象）进行一个个的标记，图中的“标记阶段”就是在干这件事，被标记的对象图里已染成绿色。
2. 重复1步骤就可以把所有从root出发的被引用或间接引用的对象全部打上标记
3. 在上述两个过程完成后，标记阶段就算告一段落，接下来就是清除阶段，清除阶段将上述被标记的对象视为“存活对象”，这时会扫描全部对象，将没有被标记的对象清除，同时将有标记的对象的标记去除，方便下次GC使用。

了解完这个算法的执行过程，大致上就知道了为什么这个算法的效率会很低了，如果系统中会创建大量的对象，但只有很少的对象会存活的比较久，这时候该算法的效率在清除阶段的时候，耗时就会很久，因为要整体遍历，而且还要进行大量回收。

3.2：复制算法

这种算法将可用内存划分为大小相等的两块，每次只使用其中一块，GC触发时，就将该块内存里还存活着的对象整体复制到另外一块内存上去，然后再把已使用的内存一次性清除掉，下面来展示下回收状态：

同样的，这张图仅用来表现清理过程和最终态，下面，通过图8来说明下这种算法的执行流程：

上图就是复制算法的执行过程：

1. 根据root，找出来所有的可达对象（存活对象），整体复制到新空间里（这个过程类似标记-清除算法里的标记阶段）。
2. 将原来的旧空间里的所有对象整体清除掉（完成复制后，可以认为原来的旧空间里的所有对象都可以回收），下次GC的时候，本次GC意义上的“新空间”就变成了下次GC意义上的“旧空间”，以此类推。

相比标记-清除算法，复制算法虽然内存被一分为二，但是节省了整体遍历所有对象这一步操作，对于那种产生大量对象，但是对象生命周期极短的情况，这个算法相比标记-清除算法效率高了不止一个档次，因为每次仅复制一小批存活的对象，没必要整体遍历所有的对象进行标记判断+清理的操作。所以这种算法适合那种对象多，但大部分对象生命周期短的情况，如果对象多，生命周期长，那么意味着复制算法每次对复制这个动作的开销，是非常大的，这也就解释了，为什么jvm新生代的回收算法采用复制算法，而老年代则不用。

3.3：标记-压缩算法

也分为两个阶段：

1. 标记阶段，这个阶段跟标记-清除算法一致，具体流程可以参考图8
2. 压缩阶段，相比标记-清除算法，该算法不再整体遍历所有的对象，而是将带有标记的“存活对象”依次压缩排列，排列完成后，存活对象将紧紧挨在一起，清除时只需要将存活对象边界以外的区域全部清理即可。

过程如图所示：

这里不再画算法的执行流程图，标记步骤参考图8，压缩过程参考图11即可。

这个算法的好处就是不会产生内存碎片，不会大量复制，相比复制算法，内存也不会减半，由于少了一层遍历所有对象的操作，因此一般效率也要比标记-清除算法高。

3.4：分代收集算法

目前商业虚拟机的垃圾回收都采用分代收集算法，这种算法基于上述几个基本的垃圾回收算法，通过「分代」的方式分类不同生命周期特征的对象，将不同「代」使用适合的收集算法来实现回收，比如jvm新生代，新生代中的对象特征为生命周期短，每次回收只有少量对象存活，且要求快速，因此适合用复制-收集算法来实现（比如新生代里的Eden区和两个Survivor区，就是为复制算法而拆分出来的），而老年代里的对象因为生命周期长，每次回收大量的对象还处于存活期，如果再使用复制-收集算法来实现，那么复制成本是很高的，因此老年代则适合使用标记-整理算法，这种不使用单一算法，会根据对象的生命周期特征进行算法隔离分区的方式就叫做「分代收集」。

四：并发可达性分析

4.1：STW带来的问题

前面讲可达性分析算法时说过，在扫描对象时为了保证准确性，需要STW，即停掉所有用户线程，这样就可以保证在做可达性分析时不会因为引用关系变化而出错。但STW持续的时间越长，对用户线程就越不友好，JVM的吞吐量就越低：

但一般情况下，真正的GC Roots对象只是极少数，再加上OopMap的协助，枚举GC Roots这个步骤已经非常短暂了，按理说已经不需要继续优化了，但实际上并非如此，因为这种说法仅仅局限在了枚举GC Roots这一步，而真正到了标记阶段，是需要遍历整个引用对象图的，比如：

所以真正会严重影响STW时间的，是深度遍历所有可达对象这一步，因为这些对象的数量并不可控，那有没有一种可能，只在枚举GC Roots的时候STW，深度遍历时与用户线程并发运行？诶，有的，接下来我们就来聊一聊并发可达性分析。

4.2：三色标记法&并发问题

开始前我觉得有必要说一下GC发生时的前提条件，防止后续被例子绕晕：

根据4.1，我们的GC Roots已经通过初步的STW找到，需要并发处理的是以这些GC Roots为根，遍历所有可达对象的这步操作，所以在枚举GC Roots这步结束后，本次GC要处理哪些对象就已经是固定的了，这期间如果有新对象被创建，那肯定不属于本次GC扫描范围，直接视为「可达对象」即可（G1实现SATB就是这么干的），所以可能造成的并发问题都是围绕这些被圈定好的对象来说的。

先来了解下三色标记，开始遍历前我们会把对象按照以下三个标准标上颜色：

• 白色：本对象尚未被访问过。（刚开始都是白色，垃圾收集结束后若还为白，则视为「不可达」对象）
• 灰色：本对象已访问过，但是本对象引用的其他对象尚未全部访问完，全部访问后，会转为黑色。
• 黑色：本对象已访问过，且本对象引用的其他对象也全部被访问（确认存活）。

基于三色标记，正常情况下完成一次可达性分析的过程如下：

如果遍历是在STW下进行的是没有任何问题的，因为上面所有对象的引用关系都不会在扫描期间发生变化，但我们的目标是让这一步不再STW，这就意味着在GC线程沿着GC Roots遍历对象时用户线程仍可以随意更改对象间的引用关系，你可能已经想到了，这会引发很严重的后果：

多标

如果GC线程扫描过程中用户线程让已扫描对象间的引用断开，此时断开后的引用链仍然会继续标记，直到全部变成黑色为止：

这就是多标，导致一些原本应该被回收的对象存活到了下一次GC，这部分由于多标而多存活了一轮的垃圾对象被称为浮动垃圾，当然这并不会造成很严重的问题，反正这些对象最终都会被顺利回收，真正可怕的是漏标。

漏标

导致漏标的前提条件：

可以根据两个条件来分析下为什么这样会导致漏标：当GC线程扫描到灰色对象时，其引用的白色对象被用户线程断开，然后建立起其和黑色对象的引用，此时白色对象不属于垃圾，但始终会是白色（因为黑色对象已经扫描完成了，不会再次发现这个白色对象），最终这个白色的「可达对象」将会被回收。

这里可能比较容易晕，为什么非得同时满足这俩条件呢？条件2还好说，如果只满足条件2顶多会造成多标，而多标并不会造成什么严重后果，但只满足条件1不是也会导致漏标吗？比如我直接新建一个对象让黑色对象引用：

按理说这的确也会有问题，但这是新建的对象，本小结刚开始就说过，后面新建的对象不属于本次GC范围，会直接被视为「可达对象」，所以这个对象打从被创建出来就不可能在本次GC中被回收了。

当然，还有另一种情况，要是一个在本次回收范围内的「不可达」对象被黑色对象引用了呢？比如：

这也（几乎）是不可能的，因为一个「不可达」的对象是不能再被用户线程访问到的，所以这种情况不会实际发生（想象一个在根上不存在引用的对象，是不能被我们的程序访问到的）。

综上，当且仅当两个条件同时满足时，才会造成漏标问题，否则要么没问题，要么就是不需要处理的多标问题。

4.3：漏标解决方案

对于多标问题可以忽略，因为它并不会影响到正常逻辑，所以我们只需要把漏标问题解决掉即可，由图14所知，导致漏标必须要同时满足两个条件，那就意味着随意破坏其中一个条件，就可以解决漏标问题。

增量更新

这个方案通过破坏掉第一个条件来解决漏标问题，具体做法是当黑色对象插入新的指向白色对象的引用关系时，通过写屏障将这个新插入的引用记录下来，等并发扫描结束后，STW一下（如果不STW，可能会持续产生新的增量引用，这样GC可能永远都没办法正确结束），再从这些被记录的黑色对象出发，再进行一次扫描，这时新插入的白色对象就会完成标记，也就不会被回收了：

通过这个方案，我们让第一个条件不成立，自然也就解决了漏标问题；值得一提的是这里虽然也发生了STW，但比起全量扫描时就STW，还是要轻量不少，因为在GC途中发生这种变化的情况并不多。

原始快照（SATB）

这个方案通过破坏第二个条件来解决漏标问题，当灰色节点要删除指向白色对象的引用关系时，就将这个要删除的引用当场记录下来（也就是引用快照），在并发扫描结束后，同样需要STW一下，再以这些被记录的灰色节点为根，重新扫描标记一遍，将这条链上所有的对象标黑，为了说明这个逻辑，我们的例子中使用了2个白色对象，第一个在失去灰色节点的引用后又被一个黑色节点引用了，另一个则没被重新引用，到最后，这两个对象的命运将截然不同：

如你所见，这种方式会造成一些浮动垃圾，但相比增量更新，它的效率更高一些，而这些被标黑的对象最终结局就两种，1是真的存活，2是变成浮动垃圾，图19已经完整体现了这两种情况。

实际应用

后面要介绍几种常见的垃圾收集器，其中一些垃圾收集器是可以和用户线程并发执行的，比如CMS和G1收集器，其中CMS利用增量更新来实现并发，而G1则是通过原始快照实现并发，尽管它们也会STW，但相比遍历对象图带来的STW来说已经好很多了，这些留到下一篇再说吧~