掘金后端 ( ) • 2024-04-30 17:16

垃圾回收算法是JVM、Go等语言中非常重要的一环，尽管在我们平时的业务开发中，可能用不到这些，但是不管是在面试或者是性能调优时，都可能涉及到这部分知识。当然，网络上垃圾回收相关的文章与八股文都很很多了，但是，往往这些文章都太“干”了，对于为什么要有垃圾回收算法，算法的设计究竟是为什么，讨论的就很少。而这，其实是不助于我们真正去理解他的，在本文，我会结合自己的理解，来谈谈为什么要有垃圾回收算法，以及对于其设计的思考。

1.垃圾回收算法

垃圾回收算法的根本目的是让程序员从对内存的手动控制中抽身出来，专注于对代码逻辑的编写，因此，自动就是其第一要义。在C语言中，使用malloc()函数进行动态内存分配，使用free()函数进行内存释放：

// 使用指针p指向的内存空间

int *p = (int *) malloc(sizeof(int));

... 使用内存...

// 内存释放
free(p);

这样虽然很灵活，但是，只要有人介入的事情，不确定性就会多起来，内存泄漏必然常常发生，并且，程序员承担内存管理的重任，也会导致本就不富裕的头发更加稀薄，因此，如果能让程序自己管理内存，那便是极好的。最简单的一个思路是，每隔一段时间，我们的程序定期扫描在内存空间中创建的所有对象，将已经没有引用的对象直接全部清除，这样就达到了自动管理内存的效果。

2.如何判断对象“活着”

对象的引用是一组树状结构（不是网状，有环就内存泄漏了），如果我们找到必定存活的对象，之后沿着其叶子节点全盘梳理，那么没有被引用到的对象，就已经可以被回收掉了，这种方法被称为可达性分析：

而那些必定存活的对象，就是我们常说的GC Roots，以java为例，GC Roots包括：

Java栈帧中的本地引用变量：每个Java方法在执行时都会创建一个栈帧，其中包含该方法的局部变量表。局部变量表中的引用变量就是根对象之一。
方法区中的静态字段：Java类的静态字段也是根对象之一。
JNI（Java Native Interface）本地方法栈中的引用：JNI本地方法栈中的引用也是根对象之一。当然，上述并不是唯一的方法，我们也可以维护每个对像的引用计数属性，当有对象引用它时，它的引用计数加一；当引用失效时，引用计数减一。如果对象的引用计数为零，则认为该对象不可达，可以被垃圾回收（引用计数法）。

3. STW的诞生

STW（stop the world）是指为了垃圾回收，需要暂停我们的业务代码。那么，为什么需要STW的过程呢？这就涉及了计算机老生常谈的并发问题：如果在垃圾回收线程工作的同时，业务代码的线程还在更新对象的状态，那么就有可能发生以下的几个问题：

垃圾回收判断对象存活后，对象被更新为死亡状态；
垃圾回收判断后，对象状态被更新。

第一种情况可能导致垃圾的漏回收，这个其实还好，下次就回收掉了，后一种情况就要命了，垃圾回收的线程把业务线程需要的对象回收了，那业务代码就要报错了。

那么，如何解决并发问题呢？---“加锁”，没错，STW本质上就是加锁，垃圾回收的时候，业务代码直接停摆，那就不存在并发问题了。

但是，我们现在更多的程序都是跑在服务器上，为我们的客户提供服务的，如果垃圾回收线程直接把内存“锁住”，服务就不可用了，如果这个时间还很长，那就更是重大问题了。

如果尽可能降低STW的时间----“并发”。因此，各种垃圾回收算法开始从垃圾回收流程上进行优化拆解，引入各种可以的“并发”过程，控制STW的时间。

因此，我们后续介绍的各种各样算法的各种并发设计，本质都是并发与STW的博弈，明白了这一点，对于垃圾回收算法的理解，就能轻松和自然很多。

4. CMS垃圾回收算法

CMS（Concurrent Mark Sweep）垃圾回收算法是一种并发的垃圾回收算法，也是JDK8默认的垃圾回收算法，它可以在垃圾回收过程中与应用程序线程同时运行，从而减少垃圾回收对应用程序性能的影响。

初始标记：从根对象开始，标记出所有直接可达的对象，这个过程是STW的，会暂停业务线程。

为什么初始标记阶段需要STW呢？

这是因为GC Root中很多对象的变化是非常频繁的（栈帧，本地方法表，具体的JVM知识这里就不展开了），如果并发进行，会有大量的错标与漏标问题，得不偿失。在几乎所有使用可达性分析的GC算法中，初始标记阶段都是STW的，不过，GC Roots的数量相较于整体是很有限的，这个STW并不长。

并发标记：从初始标记阶段标记出的对象开始，遍历整个对象图，标记出所有可达的对象。这个过程是并发进行的。

这个过程是并发进行的，大部分对象也是在这一阶段进行标记的。但是，大家应该还记得前面说的，并发就会有问题：

垃圾回收判断对象存活后，对象被更新为死亡状态；
垃圾回收判断后，对象状态被更新。

针对这些特殊问题，就需要进行下一步。

重新标记：修正并发标记阶段由于应用程序线程修改对象图而产生的错误标记。这个过程是STW的这个过程需要STW很好理解，因为如果校准的过程仍然并发，就仍然可能有上述问题，那就会无限套娃了，而具体重新标记是怎么实现的呢？我会在下一节详细的说一说
并发清除：清除所有不可达的对象。

4. 并发问题fix：三色标记与读写屏障

三色标记算法是一种常用的垃圾回收算法，它主要用于标记可达对象和不可达对象。在三色标记算法中，垃圾回收器将对象分为三种颜色：黑色、灰色和白色。

在三色标记算法中，垃圾回收器首先从根对象开始，将所有可达的对象标记为黑色或灰色。然后，垃圾回收器会遍历所有灰色对象，将它们引用的对象标记为黑色或灰色。最后，垃圾回收器会将所有白色对象标记为不可达，准备进行垃圾回收。

结合前面的几个问题：

垃圾回收判断对象存活后，对象被更新为死亡状态->黑色节点可以被回收->漏回收问题，可以忽略；
垃圾回收判断后，对象状态被更新（白色节点被挂在黑色节点上）。

这种情况下，需要把灰色节点重置为灰色，之后在STW的重新标记阶段，会对所有的灰色节点及其子节点进行状态更新。

那么？如果在对象状态更新的同时，变更三色标记的状态呢，这就要用到读写屏障的能力了。我们其实不需要去深究读写屏障最底层的原理，我们就可以理解这是JVM层面的，在对内存对象访问时的AOP操作，在访问内存对象时，JVM会在其前后植入一些逻辑，而JAVA的垃圾回收算法利用了这个能力，更新了三色标记的状态。

5. G1垃圾回收算法

G1（Garbage-First）垃圾回收算法是一种基于分区的垃圾回收算法，也是JDK11默认的垃圾回收器。它将Java堆划分为多个区域（Region），并将这些区域组织成一个虚拟的连续空间。G1垃圾回收器的目标是在尽可能短的时间内，完成垃圾回收任务，同时保持应用程序的响应速度。

这里涉及了分代回收的概念，这个并不是在G1提出的，在之前的垃圾回收算法中就已经广泛采用了。80%的对象都是朝生夕死的，生命周期很短，而一般能熬过这段时间的对象，往往会长期存在。所以，我们可以用分代算法把这些对象区分开来，新创建的对象放在新生代，频繁GC，长期存在的对象晋升到老年代，减少重复扫描。

在G1以前的分代算法，各区域都是连续的，幸存者区一般有两个，在mix GC 的时候，会对新生代和幸存者一区进行清理，存活时间长的会通过“复制”到幸存者二区，在幸存者区存活足够长的对象会“复制”到老年代。

这里提到了垃圾回收时的“复制”，就涉及到了三种不同的垃圾回收方法：

标记删除：将标记不存活的对象原地删除对象。
标记整理：将标记存活对象移动到空间开头，维护一个指针，指针之后的空间都是闲置空间。
标记复制：将标记存活的对象复制到另一个空间，原空间全部标记为闲置。

回到G1本身，G1采用的是分代的标记复制算法，只是各个分区在物理上并不连续，在一般情况下，只需要针对新生代做young GC就好了，当内存使用率过高时，再触发mix GC对所有分区进行整体回收。

在young GC时，由于不回收老年代，可达性分析的Root除了前面提到的东西，又多了老年代的对象。难道每次初始标记时，都要全量扫描老年代吗，那不是STW时间很长？G1是通过Card Table和Rset记忆集处理这个问题的。

G1的每个Region都有自己的Card Table和Rset记忆集，Card Table是Region基本存储单元，而Rset记录了每个Card被哪些Card引用。因此在进行可达性分析时，对于跨代调用的情况，只需要在并发标记时沿着Rset调用量看是否有老年代对象的引用即可，而不需要在STW时全量扫描老年代，这样就大大降低了初始标记的STW时间。

当然，事情都是有两面性的，过多结构的引入就导致复杂度的提升，G1位了维护Card Table与Rset，还引入了脏卡表以及更新线程，不过这部分在这里就不过多展开了。另外，young GC时，只要被老年代引用的对象都不会被回收，这就导致很多本可以回收的对象被遗漏了，只能等到mix GC时和老年代一起处理。