JVM之垃圾回收算法

今天药忘吃喽~ 2023-07-17 09:54 39阅读 0赞

# 前言 #

第二篇介绍了`Java`内存运行时区域，其中**程序计数器**、**虚拟机栈**、**本地方法栈** 三个区域随线程而生，随线程而灭；栈中的栈帧随着方法的进入和退出而有条不紊地执行着出栈和入栈操作。每一个栈帧中分配多少内存基本上是在类结构确定下来时就已知的，因此这几个区域的**内存分配和回收**都具备**确定性**。在这几个区域内不需要过多考虑回收的问题，**因为方法结束或线程结束时，内存自然就跟随着回收了**。

而`Java`**堆** 和 **方法区** 则不一样，一个接口中的多个实现类需要的内存可能不一样，一个方法中的多个分支需要的内存也可能不一样。我们只有在程序处于运行期间时才能知道会创建哪些对象，这部分**内存的分配和回收**都是**动态的**，**垃圾收集器** 所关注的是这部分内存。

# 正文 #

## (一). 对象生死判定 ##

如何判断`Java`中一个对象应该 **“存活”** 还是 **“死去”**，这是 垃圾回收器要做的第一件事。

### 1. 引用计数算法 ###

`Java` **堆** 中每个具体对象（**不是引用**）都有一个**引用计数器**。当一个对象被创建并初始化赋值后，该变量计数设置为`1`。每当有一个地方引用它时，计数器值就**加1**。当引用**失效**时，即一个对象的某个引用超过了生命周期（出作用域后）或者被设置为一个新值时，计数器值就**减1**。任何引用计数为`0`的对象可以被当作**垃圾收集**。当一个对象被垃圾收集时，它引用的任何对象计数减1。

*  **优点**：
    
    引用计数收集器执行简单，判定效率高，交织在程序运行中。对程序不被长时间打断的实时环境比较有利。
 *  **缺点**：
    
    难以检测出对象之间的循环引用。同时，引用计数器增加了程序执行的开销。所以Java语言并没有选择这种算法进行垃圾回收。

### 2. 可达性分析算法 ###

**可达性分析算法**也叫**根搜索算法**，通过一系列的称为 `GC Roots` 的对象作为起点，然后向下搜索。搜索所走过的**路径**称为引用链 （`Reference Chain`）， 当一个**对象**到 `GC Roots` 没有任何**引用链**相连时, 即该对象**不可达**，也就说明此对象是 **不可用的**。

如下图所示: `Object5`、`Object6`、`Object7` 虽然互有关联, 但它们到`GC Roots`是不可达的, 因此也会被判定为可回收的对象。

![format_png][]

**GC根对象**

在`Java`中, 可作为`GC Roots`的对象包括以下四种：

*  **虚拟机栈**（栈帧中的**本地变量表**）中引用的对象
 *  **本地方法栈** 中 `JNI` （`Native`方法）引用的变量
 *  **方法区** 中**类静态属性**引用的变量
 *  **方法区** 中**常量**引用的变量
    
    JVM中用到的所有现代GC算法在回收前都会先找出所有仍存活的对象。可达性分析算法是从离散数学中的图论引入的，程序把所有的引用关系看作一张图。下图展示的JVM中的内存布局可以用来很好地阐释这一概念：

![format_png 1][]

## (二). 对象引用分类 ##

**1. 强引用(Strong Reference)**

在代码中普遍存在的，类似`Object obj = new Object()`这类引用，只要强引用还在，垃圾收集器永远不会回收掉被引用的对象。

**2. 软引用(Sofe Reference)**

**有用但并非必需** 的对象，可用`SoftReference`类来实现软引用。在系统将要发生**内存溢出异常**之前，将会把这些对象列进回收范围之中进行**二次回收**。如果这次回收还没有足够的内存，才会抛出内存溢出异常。

**3. 弱引用(Weak Reference)**

**非必需** 的对象，但它的**强度**比软引用更弱，被弱引用关联的对象**只能**生存到下一次垃圾收集发生之前，`JDK`提供了`WeakReference`类来实现弱引用。无论当前内存是否足够，用软引用相关联的对象都会被回收掉。

**4. 虚引用(Phantom Reference)**

虚引用也称为幽灵引用或幻影引用，是最弱的一种引用关系，`JDK`提供了`PhantomReference`类来实现虚引用。为一个对象设置虚引用的唯一目的是：能在这个对象在**垃圾回收器**回收时收到一个**系统通知**。

## (三). finalize()二次标记 ##

一个对象是否应该在垃圾回收器在`GC`时回收，至少要经历**两次标记过程**。

第一次标记过程，通过**可达性分析算法**分析对象是否与`GC Roots`可达。经过第一次标记，并且被筛选为**不可达**的对象会进行第二次标记。

第二次标记过程，判断不可达对象是否有必要执行`finalize`方法。执行条件是当前对象的`finalize`方法被重写，并且还未被系统调用过。如果允许执行那么这个对象将会被放到一个叫`F-Query`的队列中，等待被执行。

> **注意**：由于`finalize`由一个优先级比较低的`Finalizer`线程运行，所以该对象的的`finalize`方法不一定被执行，即使被执行了，也不保证`finalize`方法一定会执行完。如果对象第二次小规模标记，即`finalize`方法中拯救自己，只需要重新和引用链上的任一对象建立关联即可。

## (四). 垃圾回收算法 ##

本节具体介绍一下各种垃圾回收算法的思想：

### 1. 标记-清除算法 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MzEzNjM1_size_16_color_FFFFFF_t_70][]

标记清除算法（Mark-Sweep）是最基础的一种垃圾回收算法，它分为2部分，先把内存区域中的这些对象进行标记，哪些属于可回收标记出来，然后把这些垃圾拎出来清理掉。就像上图一样，清理掉的垃圾就变成未使用的内存区域，等待被再次使用。这逻辑再清晰不过了，并且也很好操作，但它存在一个很大的问题，那就是内存碎片。

上图中等方块的假设是 2M，小一些的是 1M，大一些的是 4M。等我们回收完，内存就会切成了很多段。我们知道开辟内存空间时，需要的是连续的内存区域，这时候我们需要一个 2M的内存区域，其中有2个 1M 是没法用的。这样就导致，其实我们本身还有这么多的内存的，但却用不了。

### 2. 复制算法 ###

![20200322201003818.png][]

复制算法（Copying）是在标记清除算法上演化而来，解决标记清除算法的内存碎片问题。它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。保证了内存的连续可用，内存分配时也就不用考虑内存碎片等复杂情况，逻辑清晰，运行高效。

上面的图很清楚，也很明显的暴露了另一个问题，合着我这140平的大三房，只能当70平米的小两房来使？代价实在太高。

### 3. 标记-压缩算法 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MzEzNjM1_size_16_color_FFFFFF_t_70 1][]

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

标记压缩算法一方面在标记-清除算法上做了升级，解决了内存碎片的问题，也规避了复制算法只能利用一半内存区域的弊端。看起来很美好，但从上图可以看到，它对内存变动更频繁，需要整理所有存活对象的引用地址，在效率上比复制算法要差很多。

### 4. 分代收集算法 ###

分代收集算法分代收集算法（Generational Collection）严格来说并不是一种思想或理论，而是融合上述3种基础的算法思想，而产生的针对不同情况所采用不同算法的一套组合拳。当前商业虚拟机都采用**分代收集**的垃圾收集算法。分代收集算法，顾名思义是根据对象的**存活周期**将内存划分为几块。一般包括**年轻代**、**老年代** 和 **永久代**，如图所示：

![format_png 2][]

新生代（Young generation）

绝大多数最新被创建的对象会被分配到这里，由于**大部分对象**在创建后会很快变得**不可达**，所以很多对象被创建在**新生代**，然后**消失**。对象从这个区域消失的过程我们称之为 `minor GC`。

**新生代** 中存在一个`Eden`区和两个`Survivor`区。新对象会首先分配在`Eden`中（如果新对象过大，会直接分配在老年代中）。在`GC`中，`Eden`中的对象会被移动到`Survivor`中，直至对象满足一定的年纪（定义为熬过`GC`的次数），会被移动到**老年代**。

可以设置**新生代**和**老年代**的相对大小。这种方式的优点是新生代大小会随着整个**堆**大小**动态扩展**。参数 `-XX:NewRatio` 设置**老年代**与**新生代**的比例。例如 `-XX:NewRatio=8` 指定 **老年代/新生代** 为`8/1`. **老年代** 占堆大小的 `7/8` ，**新生代** 占堆大小的 `1/8`（默认即是 `1/8`）。

例如：

-XX:NewSize=64m -XX:MaxNewSize=1024m -XX:NewRatio=8

老年代（Old generation）

对象没有变得不可达，并且从新生代中**存活**下来，会被**拷贝**到这里。其所占用的空间要比新生代多。也正由于其相对**较大的空间**，发生在**老年代**上的`GC`要比**新生代**要**少得多**。对象从**老年代**中消失的过程，可以称之为`major GC`（或者`full GC`）。

永久代（permanent generation）

像一些**类的层级信息**，**方法数据** 和**方法信息**（如**字节码**，**栈** 和 **变量大小**），**运行时常量池**（`JDK7`之后移出**永久代**），已确定的**符号引用**和**虚方法表**等等。它们几乎都是**静态的**并且**很少**被**卸载和回收**，在`JDK8`之前的`HotSpot`虚拟机中，类的这些永久的数据存放在一个叫做**永久代**的区域。

永久代一段**连续的内存空间**，我们在`JVM`启动之前可以通过设置`-XX:MaxPermSize`的值来控制永久代的大小。**但是`JDK8`之后取消了永久代**，这些**元数据**被移到了一个与堆**不相连**的称为**元空间** (`Metaspace`) 的**本地内存区域**。

小结

`JDK8`堆内存一般是划分为**年轻代**和**老年代**，**不同年代** 根据自身特性采用**不同的垃圾收集算法**。

对于**新生代**，每次`GC`时都有**大量**的对象死亡，只有**少量**对象存活。考虑到复制成本低，适合采用**复制算法**。因此有了`From Survivor`和`To Survivor`区域。

对于**老年代**，因为对象**存活率高**，没有额外的内存空间对它进行担保。因而适合采用**标记-清理算法**和**标记-整理算法**进行回收。

### 5. 内存区域与回收策略 ###

对象的内存分配，往大方向讲，就是在堆上分配（但也可能经过`JIT`编译后被拆散为标量类型并间接地栈上分配），对象主要分配在新生代的`Eden`区上，如果启动了本地线程分配缓冲，将按线程优先在`TLAB`上分配。少数情况下也可能会直接分配在老年代中（大对象直接分到老年代），分配的规则并不是百分百固定的，其细节取决于当前使用的是哪一种垃圾收集器组合，还有虚拟机中与内存相关的参数的设置。

5.1 对象优先在Eden分配

大多数情况下，对象会在新生代`Eden`区中分配。当Eden区没有足够空间进行分配时，虚拟机会发起一次 `Minor GC`。Minor GC相比`Major GC`更频繁，回收速度也更快。通过Minor GC之后，Eden区中绝大部分对象会被回收，而那些存活对象，将会送到`Survivor`的From区（**若From区空间不够，则直接进入Old区**） 。

5.2 Survivor区

Survivor区相当于是Eden区和Old区的一个缓冲，类似于我们交通灯中的黄灯。Survivor又分为2个区，一个是From区，一个是To区。每次执行`Minor GC`，会将Eden区中存活的对象放到Survivor的From区，而在From区中，仍存活的对象会根据他们的年龄值来决定去向。（`From Survivor`和`To Survivor`的逻辑关系会发生颠倒： From变To ， To变From，目的是保证有连续的空间存放对方，避免碎片化的发生）

5.2.1 Survivor区存在的意义

如果没有Survivor区，Eden区每进行一次`Minor GC`，存活的对象就会被送到老年代，老年代很快就会被填满。而有很多对象虽然一次`Minor GC`没有消灭，但其实也并不会蹦跶多久，或许第二次，第三次就需要被清除。这时候移入老年区，很明显不是一个明智的决定。所以，**Survivor的存在意义就是减少被送到老年代的对象，进而减少`Major GC`的发生**。Survivor的预筛选保证，**只有经历16次`Minor GC`还能在新生代中存活的对象，才会被送到老年代**。

5.3 大对象直接进入老年代

所谓大对象是指，需要大量连续内存空间的Java对象，最典型的大对象就是那种很长的字符串以及数组。大对象对虚拟机的内存分配来说就是一个坏消息，经常出现大对象容易导致内存还有不少空间时就提前触发垃圾收集以获取足够的连续空间来 “安置” 它们。

虚拟机提供了一个`XX:PretenureSizeThreshold`参数，令大于这个设置值的对象直接在老年代分配，这样做的目的是避免在Eden区及两个Survivor区之间发生大量的内存复制（新生代采用的是复制算法）。

5.4 长期存活的对象将进入老年代

虚拟机给每个对象定义了一个对象年龄（Age）计数器，如果对象在Eden出生并经过第一次`Minor GC`后仍然存活，并且能被Survivor容纳的话，将被移动到Survivor空间中（正常情况下对象会不断的在Survivor的From与To区之间移动），并且对象年龄设为1。对象在Survivor区中每经历一次Minor GC，年龄就增加1岁，当它的年龄增加到一定程度（默认15岁），就将会晋升到老年代中。对象晋升老年代的年龄阈值，可以通过参数 `XX:MaxPretenuringThreshold` 设置。

5.5 动态对象年龄判定

为了能更好地适应不同程度的内存状况，虚拟机并不是永远地要求对象的年龄必须达到 `MaxPretenuringThreshold`才能晋升老年代，如果Survivor空间中相同年龄所有对象大小的总和大于Survivor空间的一半，年龄大于或等于改年龄的对象就可以直接进入老年代，无需等到`MaxPretenuringThreshold`中要求的年龄。

> 这其实有点类似于负载均衡，轮询是负载均衡的一种，保证每台机器都分得同样的请求。看似很均衡，但每台机的硬件不通，健康状况不同，我们还可以基于每台机接受的请求数，或每台机的响应时间等，来调整我们的负载均衡算法。

### **6.HotSpot的算法实现** ###

**一句话来简单说明：**在HotSpot中使用一组称为OopMap的数据结构来存储对象引用，在类加载完成的时候，HotSpot就把对象的相关信息计算出来，在JIT编译的过程中，OopMap会在Safepoint和SafeRegion记录下栈和寄存器中哪些位置是引用。这样，GC在扫描时就可以直接得知这些信息。

**枚举根节点**

从可达性分析中从GC Roots节点找引用链这个操作为例，可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那么必然会消耗很多时间。

另外，可达性分析对执行时间的敏感还体现在GC停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行——这里“一致性”的意思是指在整个分析期间整个执行系统看起来就像被冻结在某个时间点上，不可以出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点是导致GC进行时必须停顿所有Java执行线程（Sun将这件事情称为“Stop The World”）的其中一个重要原因，即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的。

由于目前的主流Java虚拟机使用的都是准确式GC，所以当执行系统停顿下来后，并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得知哪些地方存放着对象引用。在HotSpot的实现中，是使用一组称为OopMap的数据结构来达到这个目的的，在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样，GC在扫描时就可以直接得知这些信息了。

**安全点**

在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举，但一个很现实的问题随之而来：可能导致引用关系变化（或者说可能导致OopMap内容变化）的指令非常多，如果为每一条指令都生成对应的OopMap，那将会需要大量的额外空间，这样GC的空间成本将会变得很高。

实际上，HotSpot也的确没有为每条指令都生成OopMap，前面已经提到，只是在“特定的位置”记录了这些信息，这些位置称为安全点（Safepoint），即程序执行时并非在所有地方都能停顿下来开始GC，只有在到达安全点时才能暂停。Safepoint的选定既不能太少以致于让GC等待时间太长，也不能过于频繁以致于过分增大运行时的负荷。所以，安全点的选定基本上是以程序“是否具有让程序长时间执行的特征”为标准进行选定的——因为每条指令执行的时间都非常短暂，程序不太可能因为指令流长度太长这个原因而过长时间运行，“长时间执行”的最明显特征就是指令序列复用，例如方法调用（方法返回前）、循环跳转（循环的末尾，防止大循环的时候一直不进入Safepoint，导致浪费大量时间）、异常跳转（抛出异常的位置）等，所以具有这些功能的指令才会产生Safepoint。之所以选择这些位置作为Safepoint的插入点，主要的考虑是“避免程序长时间运行而不进入Safepoint”，比如GC的时候必须要等到Java线程都进入到Safepoint的时候VMThread才能开始执行GC，如果程序长时间运行而没有进入Safepoint，那么GC也无法开始，JVM可能进入到Freezen假死状态。

对于Sefepoint，另一个需要考虑的问题是如何在GC发生时让所有线程（这里不包括执行JNI调用的线程）都“跑”到最近的安全点上再停顿下来。这里有两种方案可供选择：抢先式中断（Preemptive Suspension）和主动式中断（Voluntary Suspension），其中抢先式中断不需要线程的执行代码主动去配合，在GC发生时，首先把所有线程全部中断，如果发现有线程中断的地方不在安全点上，就恢复线程，让它“跑”到安全点上。现在几乎没有虚拟机实现采用抢先式中断来暂停线程从而响应GC事件。

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

**安全区域**

使用Safepoint似乎已经完美地解决了如何进入GC的问题，但实际情况却并不一定。Safepoint机制保证了程序执行时，在不太长的时间内就会遇到可进入GC的Safepoint。但是，程序“不执行”的时候呢？所谓的程序不执行就是没有分配CPU时间，典型的例子就是线程处于Sleep状态或者Blocked状态，这时候线程无法响应JVM的中断请求，“走”到安全的地方去中断挂起，JVM也显然不太可能等待线程重新被分配CPU时间。对于这种情况，就需要安全区域（Safe Region）来解决。

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

在线程执行到Safe Region中的代码时，首先标识自己已经进入了Safe Region，那样，当在这段时间里JVM要发起GC时，就不用管标识自己为Safe Region状态的线程了。在线程要离开Safe Region时，它要检查系统是否已经完成了根节点枚举（或者是整个GC过程），如果完成了，那线程就继续执行，否则它就必须等待直到收到可以安全离开Safe Region的信号为止。

[format_png]: /images/20230528/3818b78675044c24bdbae92d5a3a3f3d.png
[format_png 1]: /images/20230528/74ceecd2bdbc4c79811fee22541eda71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MzEzNjM1_size_16_color_FFFFFF_t_70]: /images/20230528/dee7205d99764b70a66df449bc773c65.png
[20200322201003818.png]: /images/20230528/9c69e52c47c94de4b8d6ece02b5fba25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MzEzNjM1_size_16_color_FFFFFF_t_70 1]: /images/20230528/5852132c5d3748f6b7da099fec44b3ef.png
[format_png 2]: /images/20230528/14ee834035b44a23a135aaf4188fc399.png