算法 自动采集列表(多谢分享GC策略解决了哪些问题？|左潇龙的技术)

　　算法 自动采集列表(多谢分享GC策略解决了哪些问题？|左潇龙的技术)

　　来源：博客朴左小龙的技术博客--，谢谢分享

　　GC策略解决了什么问题？

　　既然要进行自动GC，就必须有相应的策略，这些策略解决了什么问题？粗略地说，主要有以下几点。

　　1、哪些对象可以回收。

　　2、这些对象什么时候被回收。

　　3、如何回收。

　　GC策略使用什么算法

　　关于上面提到的三个问题，其实最重要的是第一个，也就是哪些对象可以回收。有一种比较简单直观的方法，效率更高，叫做引用计数。算法，原理是：这个对象有引用，则+1；删除一个引用，然后 -1。仅采集计数为 0 的对象。缺点是：(1）不能处理循环引用的问题。例如：对象A和B分别有字段b和a，让Ab=B和Ba=A，除了这两个对象没有引用，那么实际上这两个对象已经无法访问了，但是引用计数算法却无法回收它们。（2）引用计数方法需要编译器的配合，并且编译器需要为这个对象生成额外的代码。如果赋值函数给这个对象分配一个引用，它需要增加这个对象的引用计数。此外，当引用变量的生命周期结束时，需要更新该对象的引用计数器。引用计数的方法有一个显着的缺点是它并没有被JVM实际使用。想象一下，如果JVM采用这种GC策略，当程序员在编写程序时，应该不会期望再次出现下面的代码。引用计数的方法有一个显着的缺点是它并没有被JVM实际使用。想象一下，如果JVM采用这种GC策略，当程序员在编写程序时，应该不会期望再次出现下面的代码。引用计数的方法有一个显着的缺点是它并没有被JVM实际使用。想象一下，如果JVM采用这种GC策略，当程序员在编写程序时，应该不会期望再次出现下面的代码。

　　 1 public class Object {

2

3 Object field = null;

4

5 public static void main(String[] args) {

6 Thread thread = new Thread(new Runnable() {

7 public void run() {

8 Object objectA = new Object();

9 Object objectB = new Object();//1

10 objectA.field = objectB;

11 objectB.field = objectA;//2

12 //to do something

13 objectA = null;

14 objectB = null;//3

15 }

16 });

17 thread.start();

18 while (true);

19 }

20

21 }

　　这段代码看似有点刻意，但其实在实际编程过程中，经常会出现，比如两个数据库对象一一对应，各自维护着对另一个的引用，最后的无限循环只是以防止 JVM 运行。退出，没有意义。

　　对于我们现在使用的GC来说，当线程线程运行完毕后，所有的objectA和objectB都会被视为需要回收的对象，如果我们的GC采用上面提到的引用计数算法，这两个对象永远不会被回收，甚至如果我们在使用后显式地使对象无效，则没有效果。

　　这是LZ的一般解释。在代码中，LZ标记了三个数字1、2、3。执行第一个语句时，两个对象的引用计数都为1。执行第二个语句时，两个对象的引用计数都变为2。当第三个语句为执行，即两者都归类为null后，两者的引用计数仍为1。根据引用计数算法的回收规则，当引用计数不返回0时，不会被回收。

　　根搜索算法

　　由于引用计数算法的缺点，JVM一般采用一种称为根搜索算法的新算法。它的处理方法是设置几个根对象。当任何根对象无法到达某个对象时，该对象就被认为是可回收的。

　　

　　以上图为例，ObjectD 和 ObjectE 是相互关联的，但是由于这两个对象的 GC 根不可达，所以最终 D 和 E 仍会被视为 GC 对象。如果上图中使用了引用计数的方法，那么 AE 五个对象都不会被回收。说到 GC 根（GC 根），在 JAVA 语言中，可以作为 GC 根的对象有以下几种：

　　1、虚拟机堆栈中的引用对象。

　　2、方法区中类静态属性引用的对象。

　　3、方法区常量引用的对象。

　　4、本地方法栈中JNI引用的对象。

　　第一个和第四个是指方法的局部变量表，第二个表达的意思更清楚，第三个主要是声明为final的常量值。

　　根搜索算法解决了垃圾回收的基本问题，也就是上面提到的第一个问题，也是最关键的问题，就是哪些对象可以被回收，但是垃圾回收显然需要解决最后两个问题，当回收和如何回收，基于寻根算法，在现代虚拟机的实现中，主要有三种垃圾回收算法，分别是mark-sweep算法、copy算法、mark-sort算法，这三种算法已经扩展了root search算法，但它们仍然很好理解。

　　首先，让我们回忆一下上一章提到的寻根算法。它可以解决我们应该回收哪些对象的问题，但它显然不能承担垃圾采集的重任，因为我们在程序中（程序意味着我们运行在JVM中）。如果要在上面的JAVA程序运行过程中进行垃圾回收），必须让GC线程和程序中的线程相互配合，这样才能顺利回收垃圾而不影响程序的运行。

　　为了达到这个目的，mark/sweep算法应运而生。它的做法是在堆中可用内存耗尽时停止整个程序（也称为stop the world）。然后完成了两个工作，第一个是标记，第二个是清除。

　　(1） 标记：标记过程实际上是遍历所有GC Roots，然后将GC Roots 可达的所有对象标记为存活对象。

　　(2）清除：清除过程会遍历堆中的所有对象，清除所有未标记的对象。

　　其实这两个步骤并不是特别复杂，也很容易理解。LZ用简单的话来解释mark/sweep算法，就是程序运行的时候，如果可用内存用完，就会触发GC线程，程序会挂起，然后还活着的对象会被再次标记，最后清除堆中所有未标记的对象，然后程序恢复运行。

　　下面，LZ为大家制作了一组图片来说明上述过程。结合图片，我们直观的看一下流程，首先是第一张图片。

　　

　　这张图代表了程序执行过程中所有对象的状态，它们的标志位全部为0（即未标记，下面默认0为未标记，1为标记），假设此时有效内存空间已耗尽。，JVM会停止应用程序的运行并启动GC线程，然后开始标记工作。根据寻根算法，标记后对象的状态如下图。

　　

　　可以看出，根据根搜索算法，所有从根对象可达的对象都被标记为幸存对象，此时第一阶段标记已经完成。接下来，将进行第二阶段的清算。清空后，剩余对象及对象状态如下图所示。

　　

　　可以看到，没有被标记的对象会被回收并清除，而被标记的对象会被留下，标志位会被清0。不用说，只要唤醒停止的程序线程，让程序继续运行。其实这个过程并不复杂，甚至可以说非常简单。你是对的吗？但是有一点值得一提，那就是为什么一定要停止程序的运行呢？这其实不难理解。LZ举了一个最简单的例子。假设我们的程序和 GC 线程一起运行。想象一下这样的场景。

　　假设我们刚刚标记了图中最右边的对象，暂时称它为A。结果此时程序中新建了一个对象B，A对象可以到达B对象，但是由于此时A对象已经被标记在末尾，B对象的标记位为这个时候还是0，因为错过了标记阶段，所以下一轮清关的时候，新对象B会被强制清零。这样一来，不难想象GC线程会导致程序无法正常运行的结果。上述结果当然是不可接受的。我们刚刚创建了一个新对象，但是在一次 GC 之后，它突然变成了 null。如何才能做到这一点？

　　标记/扫描算法的缺点

　　1、首先它的缺点是它的效率比较低（递归和全堆对象遍历），并且在进行GC时需要停止应用程序，这样会导致用户体验很差，特别是对于交互式应用程序。这简直是​​不可接受的。试想一下，如果你玩一个网站，这个网站在一小时内挂了五分钟，你还玩吗？

　　2、第二个主要缺点是这种方式清理出来的空闲内存是不连续的，不难理解。我们的死物立即出现在记忆的各个角落。现在清除它们之后，内存布局自然会乱七八糟。为了解决这个问题，JVM 必须维护一个空闲的内存列表，这是另一个开销。并且在分配数组对象时，要找到连续的内存空间并不容易。

　　复制算法

　　我们先来看看复制算法的实践。复制算法将内存分成两个区间。在任何时间点，所有动态分配的对象只能在其中一个区间（称为活动区间）分配，而另一个区间（称为空闲区间）是空闲的。当有效内存空间耗尽时，JVM会暂停程序运行并启动复制算法的GC线程。接下来，GC线程会将活动区中的所有幸存对象复制到空闲区，并严格按照内存地址进行排列。同时，GC线程会更新幸存对象的内存引用地址，指向新的内存地址。至此，空闲区间已与活动区间交换，并且垃圾对象现在都停留在原来的活动区间，也就是当前的空闲区间。事实上，当活动间隔转换为空间间隔时，垃圾对象已经被一次性回收了。LZ给大家画了个图来说明问题，如下图。

　　

　　其实这张图还是上一章的例子，只不过此时内存被复制算法分成了两部分。我们来看看复制算法的GC线程处理完后这两个区域会是什么样子，如下图。

　　

　　可以看到，对象1和4都被清空了，而对象2、3、5、6则有规律的排列在刚才的空闲区间，是当前活跃区间之一。里面。至此，左半场就变成了自由区。不难想象，在下一次GC之后，左侧又会成为活跃区。显然，复制算法弥补了标记/扫描算法杂乱的内存布局。但同时，它的缺点也相当明显。

　　1、浪费了一半的内存，太可怕了。

　　2、如果对象的存活率很高，我们可以走极端，假设它是100%存活的，那么我们需要复制所有的对象并重置所有的引用地址。当对象存活率达到一定水平时，复制这项工作所需的时间变得不可忽略。

　　所以从上面的描述不难看出，要想使用复制算法，至少对象的存活率必须很低，最重要的是我们必须克服50%的浪费记忆。

　　标记/整理算法

　　mark/sweep 算法与mark/sweep 算法非常相似，也分为两个阶段：mark 和groom。

　　(1）Marking：它的第一阶段和mark/sweep算法一模一样，遍历GC Roots，对幸存的对象进行标记。

　　(2）Finishing：移动所有幸存的对象并按照内存地址的顺序排列，然后在结束内存地址之后回收所有内存。因此，第二阶段称为finishing阶段。

　　GC前后的图和copy算法的图很相似，但是active区间和free区间没有区别，过程和mark/sweep算法很相似。让我们看一下GC之前内存中对象的状态和布局。如下所示。

　　

　　这张图其实和mark/clear算法一模一样，只是LZ为了方便内存规则的连续排列，增加了一个矩形来表示内存区域。如果此时 GC 线程开始工作，则标记阶段立即开始。该阶段与标记/清除算法的标记阶段相同。我们看看标记阶段之后对象的状态，如下图所示。

　　

　　没有什么好解释的。接下来应该是排序阶段。我们来看看排序阶段处理后的内存布局是怎样的，如下图所示。

　　

　　可以看出，被标记的存活对象会按照内存地址的顺序进行排序排列，而未标记的内存会被清理掉。这样，当我们需要为一个新的对象分配内存时，JVM只需要保存一个内存的起始地址，这显然比维护一个空闲列表的开销要小很多。不难看出，标记/排序算法不仅可以弥补标记/清除算法中内存区域分散的缺点，还可以消除复制算法中内存减半的高成本。标记/排序算法唯一的缺点是效率不高，不仅要标记所有幸存的对象，还要对所有幸存对象的引用地址进行排序。标记/整理算法的效率低于复制算法。这里LZ总结了三种算法的共同点以及各自的优缺点。让你比较一下，会更清楚，它们有以下两点共同点。

　　1、这三种算法都是基于寻根算法来判断一个对象是否应该被回收，而支撑寻根算法正常工作的理论依据是语法中变量作用域的内容。因此，要防止内存泄漏，最根本的方法是掌握变量的作用域，而不是使用上一章内存管理中提到的C/C++风格的内存管理方法。

　　2、当GC线程启动时，或者当GC进程启动时，它们都停止了世界。

　　根据以下几点向您展示它们之间的区别。（>表示前者优于后者，=表示两者效果相同）

　　效率：Copy Algorithm > Mark/Collat​​e Algorithm > Mark/Sweep Algorithm（这里的效率只是时间复杂度的简单比较，实践中不一定如此）。

　　内存均匀性：复制算法 = 标记/扫描算法 > 标记/扫描算法。

　　内存利用率：标记/扫描算法 = 标记/扫描算法 > 复制算法。

　　可以看出mark/clear算法是一种比较落后的算法，但是后两种算法都是建立在这个基础上的。算法的前身。而且，在某些时候，标记/扫描也会派上用场。

　　至此，我们已经清楚的了解了这三种算法。可以看出，在效率方面，复制算法是当之无愧的leader，但是浪费了太多内存。为了尽可能的兼顾到上面提到的三个指标，mark/排序算法相对来说比较流畅，但是效率还是差强人意。它比复制算法多一个标记阶段，比标记/清除多一个内存排序过程。最后介绍GC算法中的神级算法——分代采集算法。那么分代采集算法是如何处理GC的呢？

　　对象分类

　　上一章提到，分代采集算法是根据对象的不同特性，使用合适的算法，并没有实际生成新的算法。分代采集算法与其说是第四种算法，不如说是前三种算法的实际应用。首先，让我们讨论对象的不同特征。接下来，LZ 和你将为这些对象选择 GC 算法。内存中的对象根据其生命周期的长短大致可以分为三种。以下名称均以LZ个人命名。

　　1、Aborted objects：在不久的将来死亡的对象。通俗地说，它们是活后不久就会死去的物体。示例：方法中的局部变量、循环中的临时变量等。

　　2、老仙物：这种物一般都活的比较久，到很老的时候依然不会死，但是说到底，老仙物迟早会死的差不多，但是只有差不多。示例：缓存对象、数据库连接对象、单例对象（单例模式）等。

　　3、坚不可摧的物体：这类物体通常一出生就几乎是不朽的，它们几乎总是不朽的，记住，只是勉强。示例：字符串池中的对象（享元模式）、加载的类信息等。

　　对象对应的内存区域

　　还记得我们之前介绍内存管理时 JVM 对内存的划分吗？我们将以上三个对象对应到内存区，即死对象和老不朽对象在JAVA堆中，不朽对象在方法区。上一章我们已经说过，对于JAVA堆，JVM规范要求必须实现GC，所以对于aborted对象和老不死对象来说，死亡几乎是必然的结果，但也只是几乎，难免会有一些将存活到应用程序结束的对象，但 JVM 规范在方法区域中没有 GC。做需求，所以假设一个JVM实现对方法区没有实现GC，那么永生对象就是真正的永生对象。因为不朽物件的生命周期太长，

　　JAVA堆对象回收（死对象和旧的不死对象）

　　有了上面的分析，我们来看看分代回收算法是如何处理JAVA堆的内存回收的，也就是aborted对象和old undead对象的回收。Aborted objects：这些对象有生有死，生存时间短。还记得使用复制算法的要求吗？即对象存活率不能太高，所以aborted对象最适合使用复制算法。小问题：如果50%的内存被浪费了怎么办？答：因为被中止的对象的存活率普遍较低，50%的内存不能作为空闲使用。一般两个 10% 的内存用作空闲和活动区，另*敏*感*词*和其他 80% 的幸存对象被转移到 10% 的空闲范围，然后之前的 90% 的内存都被释放，以此类推。为了让大家更清楚地看到这个GC过程，LZ给出了下图。

　　

　　图中标出了每个阶段三个区域的内存情况。相信看图，它的GC过程不难理解。但是，有两点需要提及。第一点，通过这种方式，我们只浪费了10%的内存，这是可以接受的，因为我们获得了内存的整齐排列和GC的速度。第二点，这个策略的前提是每个幸存对象占用的内存不能超过这10%的大小。一旦超过，多余的对象将无法复制。

　　为了解决上述突发情况，即当幸存对象占用的内存过大时，专家将JAVA堆分成两部分进行处理。以上三个区域是第一部分，称为新生代或年轻代，其余部分，专门用于存储旧的不死对象，称为老年代。这是一个恰当的名字吗？让我们看看如何处理旧的不死物体。不朽的物件：这类物件的成活率非常高，因为大部分是从新生代传下来的，就像人一样，活久了就会长生不老。

　　通常，当出现以下两种情况时，对象会从年轻代区域转移到老带区域。

　　1、新生代中的每个对象都会有一个年龄。当这些对象的年龄达到一定程度时（年龄是存活的GC次数，每次GC如果对象存活，加上年龄1），就会转移到老年代，这个转移到老年代的age值一般可以在JVM中设置。

　　2、当年轻代存活对象占用的内存超过10%时，多余的对象会被放到老年代。此时老一代就是新一代的“后备仓库”。

　　对于老不朽对象的特性，显然不再适合使用复制算法，因为它的存活率太高了，别忘了，如果老一代使用复制算法，它是没有备份仓库的. 因此，一般来说，对于旧的不死物体，只能使用标记/排序或标记/清除算法。

　　方法区对象恢复（不朽对象）

　　以上两种情况解决了GC的大部分问题，因为JAVA堆是GC的主要关注点，而且上面还收录了分代回收算法的全部内容，不朽对象的回收不在分类。采集算法内容的生成。不朽的对象存在于方法区。在我们常用的热点虚拟机（JDK默认的JVM）中，方法区也被亲切地称为永久代，这是一个非常贴切的名字，不是吗？事实上，很久很久以前，没有永久的一代。当时永久代和老年代存储在一起，里面收录了JAVA类的实例信息和类信息。然而，后来发现班级信息的卸载很少发生，所以将两者分开。幸运的是，这确实提高了很多性能，所以永久代被拆分出来了。这部分区域的GC采用与老年代类似的方法。由于没有“备份仓库”，两者都只能使用mark/sweep和mark/sort算法。

　　回收时机

　　JVM 在进行 GC 时，并不总是一起回收上述三个内存区域。大多数时候，它指的是新一代。因此，GC根据回收的区域分为两种，一种是普通GC（minor GC），另一种是global GC（m​​ajor GC或Full GC）。他们针对的领域如下。Normal GC（m​​inor GC）：只针对新生代区域进行GC。Global GC（m​​ajor GC或Full GC）：老年代GC，偶尔伴随着新生代GC和永久代GC。因为老年代和永久代的GC效果都比较差，而且两者的内存使用增长速度也比较慢，一般情况下，需要几次普通GC才能触发一次全局GC。