详解垃圾回收算法，优缺点是什么？｜金三银四系列

本文详细介绍了在 JVM 中如何判断哪些对象是需要回收的，以及不同的垃圾回收算法以及优缺点。

点击上方“后端开发技术”，选择“设为星标” ，优质资源及时送达

上篇文章详细介绍了 JVM 的结构以及其内存结构，需要阅读请移步。本文主要讲解 JVM 体系中的垃圾收集子系统用到的内存回收算法。

八股文总是忘？一张图牢记JVM内存结构|金三银四系列

2023-02-13

哪些对象需要回收

在进行垃圾回收之前，第一件事就是确定哪些对象还存活着，哪些对象已死需要被回收。

1.引用计数算法

很多判断对象是否存活的算法是这样的：

• 给对象中添加一个引用计数器，每当有个地方引用它时，计数器值就加1；

• 当引用失效时，计数器值就减1，任何时刻计数器为0的对象就是不可能再被使用的，该对象将被回收。

客观的说，引用计数法实现简单，效率高。但是没有主流JVM选择引用计数法管理内存，因为他无法解决循环引用的问题。如下图

当三个对象都不在使用时，因为相互的引用关系，并不会置为0，所以难以被回收。并且，引用计数器要求在每次因引用产生和消除的时候，伴随一个加法操作和减法操作，对系统性能会有一定的影响。

2.可达性分析算法

主流JVM都是称通过可达性分析来判定对象是否存活的。这个算法的基本思路就是通过一系列的称为"GC Roots"的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链( Reference Chain)，当一个对象到GC Roots 没有任何引用链相连，用图论的话来说，就是从GC Roots 到这个对象不可达) 时，则证明此对象是不可用的。

如图所示，深灰色的对象虽然互相有关联，但是它们到 GC Roots 是不可达的，所以它们将会被判定为是可回收的对象。

GC Root 对象

Java中，有一组GC Roots对象，它们是被垃圾回收器直接管理的对象。GC Roots对象是垃圾回收的起始点，垃圾回收器会从这些对象开始遍历所有的对象，并标记出所有存活的对象，未被标记的对象即为可回收对象。

在Java中，可以作为GC Root对象的包括以下几类：

1. 虚拟机栈（栈帧中的本地变量表）中引用的对象。虚拟机栈中保存着每个线程执行方法时的现场信息，包括局部变量、操作数栈、方法出口等。栈帧中的本地变量表中存放着方法中定义的局部变量和参数，如果局部变量或参数中引用了某个对象，则该对象被认为是一个GC Root对象。

2. 方法区中类静态属性引用的对象。类似于栈帧中的本地变量表，类中定义的静态属性也会保存引用对象。因为静态属性是属于类的，所以这些引用对象也被认为是GC Root对象。

3. 方法区中常量引用的对象。常量池中保存着编译器生成的各种字面量和符号引用，例如字符串常量、类和接口的全限定名、字段和方法的名称和描述符等。如果常量池中引用了某个对象，则该对象被认为是GC Root对象。

4. 本地方法栈中JNI（即Java Native Interface）引用的对象。JNI是Java提供的一种机制，用于调用本地的C/C++代码。如果JNI中引用了某个对象，则该对象被认为是GC Root对象。

需要注意的是，不是所有的对象都可以作为GC Root对象。例如，普通的对象实例和数组元素就不可以作为GC Root对象。只有与Java虚拟机内存管理有关的对象才可以作为GC Root对象，因为它们直接或间接地引用了所有其他对象。

垃圾回收算法

1.标记-清除算法

最基础的收集算法是标记-清除算法(Mark-Sweep)，如同它的名字一样，算法分为“标记”和“清除”两个阶段：

1. 首先标记出所有需要回收的对象（可达性分析）。

2. 在标记完成后统一回收所有被标记的对象。

之所以说它是最基础的收集算法，是因为后续的收集算法都是基于这种思路并对其不足进行改进而得到的。

优点

• 实现简单，算法简单、容易实现，与保守式GC 算法兼容，有效处理不连续的内存空间

• 不需要移动对象，因此不会浪费时间和空间。

不足

• 效率问题：标记和清除两个过程的效率都不高，且需要进行两次扫描，第一次标记垃圾对象，第二次清除垃圾对象。

• 空间问题：标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作，从而导致频繁的内存分配和回收。

2.标记-压缩算法（标记-整理）

标记压缩算法（Mark-Compact）是一种垃圾回收算法，主要用于老年代的垃圾回收。它的基本思想是在标记出所有存活对象之后，将所有存活的对象压缩到内存的一端，将所有空闲的内存空间释放出来，从而减少内存的碎片化。

标记压缩算法与标记-清除算法的区别在于，标记-清除算法只是标记出存活和垃圾对象，并将垃圾对象空间释放出来，因此容易造成内存的碎片化。而标记压缩算法则是将存活对象压缩到一端，并将空闲的内存空间释放出来，解决了内存碎片的问题。

标记压缩过程

标记压缩算法的具体实现过程如下：

• 标记阶段：从一组 GC Roots 开始，标记出所有存活的对象，并将这些存活对象的标记信息保存在对象头中。

• 压缩阶段：将所有存活的对象移动到内存的一端，释放出所有空闲的内存空间。在移动对象时，需要更新所有引用对象的指针，确保它们指向对象移动后的位置。

• 更新指针：由于移动对象的过程中，可能会修改引用对象的指针，因此需要扫描整个堆内存，将所有指向移动过的对象的指针进行更新。（这不算一个阶段）

由于需要更新所有引用对象的指针，因此在多线程情况下，需要使用屏障技术来确保线程安全性。

优点

• 可以有效地处理不连续的内存空间。

• 不会产生内存碎片，因为所有存活的对象都被移动到一端。

缺点

• 压缩阶段需要移动存活的对象，占用了系统的消耗，并且如果标记对象过多的话，损耗可能会很大，会浪费时间和空间。在标记对象相对较少的时候，效率较高。

• 需要进行两次扫描，第一次标记存活对象，第二次移动存活对象。

为什么没有清除阶段

标记-整理算法确实只有标记和整理两个阶段，没有显式的清除阶段。在整理阶段，垃圾回收器会将所有存活的对象向一端移动，将空间释放到另一端，这样空间的连续段就被重建了。因此，整理阶段的同时也具有清除的功能，所有未被移动的对象都是垃圾，可以直接被视为已经清除了。不过，在实现时，标记-整理算法的整理阶段可能需要把清除的操作分散在整个过程中进行，因此整理阶段通常会和清除阶段结合在一起，实现起来会更加高效。但是从逻辑上来说，标记-整理算法只需要标记和整理两个阶段，没有显式的清除阶段。

复制算法

为了解决效率问题，一种称为“复制”(Copying)  的收集算法出现了，它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存话着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。这样使得每次都是对整个半区进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效，算是用空间来换时间的思维。

优点

• 可以有效地处理大部分对象都是临时对象的情况，例如新生代中的对象。

• 不会产生内存碎片，因为所有存活的对象都被复制到一个新的内存空间中。

缺点

• 需要一半的内存空间用于复制存活的对象，会造成空间浪费。

• 当有大量存活的对象时，复制效率会降低。

4.分代收集算法

目前主流JVM垃圾收集都采用“分代收集”(Generational Collection) 算法，这种算法并没有什么新的思想，只是根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保（如果有空间，通过分配担保机制进入老年代），就必须使用“标记一清理”或者“标记一整理”算法来进行回收。

对于新生代和老年代来说，通常新生代回收的频率很高，但是每次回收的时间都很短，而老年代回收的频率比较低，但是被消耗很多的时间。为了支持高频率的新生代回收，虚拟机可能使用一种叫做卡表（Card table）的数据结构，卡表为一个比特位集合，每一个比特位可以用来表示老年代的某一区域中的所有对象是否持有新生代对象的引用。

这样以来，新生代GC时，可以不用花大量时间扫描所有老年代对象，来确定每一个对象的引用关系，而可以先扫描卡表，只有当卡表的标记为1时，才需要扫描给定区域的老年代对象，而卡表为0的所在区域的老年代对象，一定不含有新生代对象的引用。

卡表中每一位表示老年代4KB的空间，卡表记录为0的老年代区域没有任何对象指向新生代，只有卡表为1的区域才有对象包含新生代对象的引用，因此在新生代GC时，只需要扫面卡表为1所在的老年代空间，使用这种方式，可以大大加快新生代的回收速度。

优点

• 根据对象的生命周期，将堆分为多个区域，使不同区域采用不同的回收算法，可以提高回收效率。

• 可以避免全局垃圾回收的情况，从而减少了暂停时间。

缺点

需要维护多个堆区域，增加了复杂性。可能会出现对象晋升的情况，导致老年代的内存压力增大。

5.分区算法

分代算法将按照对象的生命周期长短划分成两个部分，分区算法将整个堆空间划分成不同连续的区域。每个小区间都独立使用，采用不同的垃圾回收算法，独立回收。例如，可以将新生代分成多个区域，每个区域采用不同的复制算法，而老年代则采用标记-整理或标记-清除算法。这种算法的好处是可以控制一次回收多少个小区间。

一般来说，在相同的条件下，堆空间越大，一次GC时所需要的时间就越长，从而产生的停顿也越长。为了更好地控制GC产生的停顿时间，将一块大的内存区域分割为多个小块，根据目标的停顿时间，每次合理的回收若干个小区间，而不是整个堆空间，从而减少一次GC所产生的停顿。这算是一种分治思路。

最后，欢迎大家提问和交流。

如果对你有帮助，欢迎点赞、评论或分享，感谢阅读！

无需注册直接体验ChatGPT！附注册ChatGPT详细教程

2023-02-14

一文掌握，单机Redis、哨兵和Redis Cluster的搭建，建议收藏

2023-02-11

Dubbo重点，SPI的自适应扩展原理｜原创

2023-01-11