算法 自动采集列表(我后来他有了女朋友1.4垃圾收集算法及细节)

　　算法 自动采集列表(我后来他有了女朋友1.4垃圾收集算法及细节)

　　点击上方的“颜琳”，选择“Top or Star”

　　有人跟着我

　　后来有了女朋友

　　1.4 垃圾采集算法及细节

　　1.4.1代采集

　　这是我们一直想到的垃圾回收方式，在大多数商用虚拟机中几乎都遵循分代回收理论。代际采集理论基于以下三个方面。

　　l 弱世代假设：绝大多数对象都在死亡。

　　l 强世代假设：在垃圾回收过程中存活次数越多的对象越难死亡。

　　l 代际参考假设（Intergenerational Reference Hypothesis）：代际参考与同代参考相比，只是极少数。

　　上面的分代假设实际上默认了垃圾采集器的设计原则：采集器应该将Java堆划分为不同的区域，然后将回收的对象根据年龄（它们存活的次数）分配到不同的区域进行存储。垃圾采集过程）。也正是因为这样的划分，我们才有了针对某个区域的回收类型和回收算法的设计，以及我们经常听到的名词“Minor GC”、“Major GC”、“Full GC”。

　　分代采集 在 HotSpot 中，Java 堆被设计成两个区域：年轻代和老年代。这就是我们常说的新生代和老年代的由来。新生代中的每个集合都会有大量的对象，只有少数幸存者会逐渐晋升到老年代。因此，新生代被划分为一个较大的伊甸空间和两个较小的幸存者。在（生存）区域，两个空间的比例默认为8:1。每使用一次Eden区和一块Survivor，就将Eden区和Survivor区的幸存对象一次性复制到另一个Survivor区，然后清理刚刚使用过的Eden区和Survivor区。按照这种划分方法，新生代其实是这样的结构：Eden:Survivor1:Survivor2=8:1:1

　　我们刚刚清理了Eden+Survivor1（80%+10%）空间，将幸存的复制到Survivor2空间。下次继续清理，我们将Eden+Survivor2添加到Survivor2的原创幸存对象中。无法确保每次不超过 10% 的对象存活。年轻代重复多次复制。如果其中一个 Survivor 空间不足，则老年代需要分配保证。

　　分配担保类似于银行贷款的担保人，借款人无法偿还担保人。新生代生成的原创对象可以自行恢复。如果任何时候都不能吃自己生产的对象，那么这些对象就必须委托给老年代进行管理。晚年其实是个大坑。凡是能到老年的物件，都不好对付。这里的垃圾回收频率比新生代低十倍左右。在老年代被回收之前，新生代经常复制十次以上。一次。

　　因此，目前对象可以进入老年的三种情况

　　l 上面提到了第一种保证方法。

　　l 第二类是大型物体。JVM 可以设置该值。如果对象太大，或者是数组，会直接放到老年代。

　　l 第三种是按年龄计算。每次在新生代GC中，如果对象还活着，则age加1，如果大于默认15或者同龄大于一半内存，可能达不到设置。年龄将转移到老年。

　　其实上面的描述有一个漏洞，就是没有考虑对象的相互依赖。如果新生代对象和老年代对象之间存在依赖关系，并且一方已经死亡，无论是新生代对象还是老年代对象。老年代触发GC的时候应该清除吗？如果两个对象都死了，那么它们会一起死，否则它们会活着。事实上，这是对世代假说的第三种描述。毕竟这种跨代参照物是少数。当被引用的新生代对象提升到老年代时，这个引用关系就会消失，虚拟机不会为此做这件事。对于某些对象，每次GC都要扫描整个老年代来检查引用很麻烦。相反，它使用了一种称为Remembered Set 的数据结构来实现哪些区域属于旧时代区域的跨代引用。当发生 Minor GC 时，返回将内存集中依赖的对象添加到 GC Roots 并更改对象的引用。这种方法是跨代引用的最具成本效益的解决方案。

　　1.4.2 标签清除算法

　　这是所有垃圾采集算法中最基本的，分为“标记”和“清理”两个阶段。首先标记需要回收的对象，然后统一回收所有标记的对象。他之所以是最基础的，是因为后面的算法都是基于他的改进，弥补了他的不足。他的缺点有两点：第一是效率问题，标记清场效率不高。其实最主要的原因是清除标记后造成不连续的内存碎片，导致大对象无法存储。我们可以通过图 1-9 清楚地看到它。

　　图1-9 标记清除算法

　　1.4.3 标记复制算法

　　把内存按容量分成两半，保证一半是空的，一半是用的。在GC期间，将幸存的对象复制到空的一半，然后清空一半。

　　这样做的好处是每次最多清理一半的内存，大大提高了效率。二是解决内存碎片问题。

　　缺点是空间利用率不高，所以在文章开始之前给大家科普一下。新生代分为三个区域来回复制。聪明的孩子在阅读本文时已经知道，新一代使用复制算法。

　　是因为新生代都是生死存亡，采集频繁，满足复制算法的特点。如图1-10所示。

　　图 1-10 标记复制算法

　　1.4.4 标记排序算法

　　标记组织和标记清除中的标记是否相同？答案是肯定的，mark-organize 和 mark-clear 的明显区别是“组织”。由于排序过程，该算法解决了内存问题。碎片化问题。

　　该算法的工作原理是：标记要清除的对象后，不是直接清除，而是将所有幸存的对象向前移动，然后清除剩余的内存。如图1-11所示。

　　图1-11 标记排序算法

　　1.4.5 枚举根节点

　　根据前面的内容，我们知道HotSpot使用可达性分析算法来判断对象是否存活。生存的关键是看对象是否在GC Roots的引用链上。那么重点就是这个GC Roots，GC Roots的大部分数据。都存在于方法区中。因为是线程共享的，GC Roots也是一个全局引用，通常是栈帧中的常量、静态变量、局部变量表来维护程序执行上下文的信息，而我们普通Java程序的大小方法区范围从数百兆以上，当GC发生时，需要保证当前存在的所有对象的引用不变，所有用户线程都需要挂起，这就是所谓的“Stop The World”。程序中的线程需要Stop来配合可访问性分析。这么大的空间肯定不可能每次垃圾回收都遍历整个引用链。它就像一个拥有超过一百万用户的系统。可以每次都从硬盘读取用户列表吗？当然，我们不会这样做。为了解决这个问题，首先使用了conservative GC和后来的accurate GC。Accurate GC会引用一个OopMap，用于保存类型的映射表，HotSpot中使用了accurate GC。为了解决这个问题，首先使用了conservative GC和后来的accurate GC。Accurate GC会引用一个OopMap，用于保存类型的映射表，HotSpot中使用了accurate GC。为了解决这个问题，首先使用了conservative GC和后来的accurate GC。Accurate GC会引用一个OopMap，用于保存类型的映射表，HotSpot中使用了accurate GC。

　　首先简单介绍一下保守GC。它将从一些已知位置进行扫描。只要扫描一个数，就会判断引用是否指向堆（这里的计算还是比较复杂的，包括上下边界检查，对齐检查等），一直这样检查，最后完成可达性分析。这种模糊的判断无法准确判断一个位置是否是指向GC堆的指针，故称为保守GC。这种模糊判断的内在本质是速度快、准确率低。对引用的误判会导致垃圾采集器无法采集，造成空间浪费。

　　接下来说一下精准GC。他怎么能确切地知道哪里有引用指针呢？其实不同的虚拟机的实现是有区别的，但是在Java中，你知道某个位置的数据是什么类型的。当类加载时，HotSpot 已经计算了类偏移量上的类型数据。, 然后在即时编译的时候会记录在特定位置引用了堆栈和寄存器的哪些位置。此类信息是从外部记录下来的，并保存为映射表。在 HotSpot 中，这个映射表叫做 OopMap。不同 虚拟机名称不同。

　　要实现这个功能，虚拟机中的解释器和JIT编译器需要有相应的支持，它们可以生成足够的元数据提供给GC。

　　使用这样的映射表一般有两种方式：

　　1. 每次都遍历原创映射表，扫描一遍循环的偏移量；这种用法也称为“解释性”。

　　2. 为每个映射表生成自定义的扫描码（想象一下扫描映射表的循环被展开了），以后每次使用映射表时直接执行生成的扫描码；这种用法也称为“已编译”。

　　1.4.6个安全点

　　OopMap可以帮助我们准确快速的完成GC Roots枚举。我们可以简单地将oopMap理解为调试信息。源代码中的每个变量都有一个类型，但编译后的代码只有变量在堆栈上的位置。OopMap 是一条额*敏*感*词*自然就限于这一段代码。如果循环中引用了多个对象，肯定会有多个变量，编译后在栈上占据多个位置。此代码的 OopMap 将收录多个记录。所以它是安全点的起源。简单的说：产生OopMap指令的位置叫做安全点。安全点的选择遵循“是否让程序长时间执行的特性”。什么是长时间？表示持续执行，例如方法调用、循环、异常跳转等。

　　安全点有OopMap，有利于垃圾回收。因此，当GC发生时，需要让所有的用户线程运行到更接近安全点并停止。这里有两种方法：抢占式中断和主动式中断。抢占式中断是指系统主动中断所有用户线程。如果安全点没有线程，它会恢复他并继续执行，直到到达安全点。目前几乎没有虚拟机使用这种方法。主动中断意味着线程主动。虚拟机只设置一个标志。用户线程不断地主动训练这个标志。当它到达这个标志时，它会停止并挂起自己。

　　1.4.7 安全区

　　安全点的概念不能满足所有场景。如果线程没有正常执行，而是处于Sleep或者阻塞状态，那么短时间内就无法响应虚拟机的中断请求，更别说是否能到达安全点，所以没办法执行垃圾采集。，所以我们要把安全点做大一点，让所有线程都可以覆盖这个区域。这就是安全区（Safe Region）的概念。是放大版的安全点。这里的对象引用关系不会改变，所以垃圾回收可以在安全区域的任何地方进行。同样，当一个线程进入安全区时，它会标记自己并告诉虚拟机它已经进入了安全区。当线程想要离开安全区时，需要判断虚拟机是否已经完成枚举和节点，如果完成就继续执行，如果没有完成就继续等待。如图1-12所示。

　　图1-12 安全区*敏*感*词*

　　1.4.7 内存设置和卡表

　　上一篇关于世代假设的文章中提到了Remembered Set。是为了解决跨代引用带来的问题。主要用于减少GC Roots的全堆扫描。因此，据说在所有这样的代或对于采集不同区域行为的垃圾采集器中，都有内存集，例如cms、ZGC、Shenandoah采集器。由于内存集是一种数据结构，会占用虚拟机内存，因此在设计内存集时必须考虑存储和维护成本。下面提供了三种类型的记录精度。

　　l 字长精度：每条记录精确到一个机器字长（处理器的寻址位数，如常见的32位或64位），该字收录一个跨代指针。

　　l 对象精度：每条记录都精确到一个对象，对象中存在收录跨代指针的字段。

　　l 卡片精度：每条记录精确到一个内存区域，该区域中有收录跨代指针的对象。

　　我们用这三种方式来实现内存集，而这种使用精度的方式我们就变成了卡表（Card Table），所以我们可以换一种说法：卡表是实现内存集的一种方式，记录内存设置Record的准确性以及heap和memory heap的映射关系。这种方法目前在虚拟机中也被广泛使用。

　　在 HotSpot 中，卡片表以字节数组的形式存在。此数组中的每个元素对应于此内存区域中的 512 字节内存。这个内存区域称为卡片页（Card Page）。等待多个对象，只要卡表中指向的卡页有跨代引用指针，卡表就被标记为“脏”，然后被收录在GC Roots链中。如图1-13所示。

　　图1-13 卡片表和卡片页的关系

　　1.4.8 并发采集写屏障

　　至此，我们似乎对扫描虚拟机的GC Roots链有了大致的了解，但我们仍然不知道card table是如何维护的。在 HotSpot 中，Write Barrier 用于维护卡表。在第 2 章中，我们将介绍内存屏障 volatile。既然是屏障，就有一个共性，就是指令的区域分离，防止序列变化引起的问题。屏障一般出现在并发场景中，在JVM中也是一样。JVM 中的并发是指用户线程和垃圾采集线程一起工作。在JDK7之前，写屏障是无条件的。无论更新的引用是否跨代存在，都会出现一些写入障碍。更新后的引用一般在新对象生成后改变现有OopMap的值（也可以说是更新了卡片表），这里自然会影响卡片表的值。赋值前后都属于写屏障，赋值之前称为“Pre-Write Barrier”，赋值之后称为“Post-Write Barrier”。我个人认为这个方法比较懒，所以HotSpot在JDK7之后加了-XX:+UseCondCardMark来设置卡表更新判断。虽然写屏障使开销更小，但在并发期间会发生错误共享。分配之前称为“Pre-Write Barrier”，分配之后称为“Post-Write Barrier”。我个人认为这个方法比较懒，所以HotSpot在JDK7之后加了-XX:+UseCondCardMark来设置卡表更新判断。虽然写屏障使开销更小，但在并发期间会发生错误共享。分配之前称为“Pre-Write Barrier”，分配之后称为“Post-Write Barrier”。我个人认为这个方法比较懒，所以HotSpot在JDK7之后加了-XX:+UseCondCardMark来设置卡表更新判断。虽然写屏障使开销更小，但在并发期间会发生错误共享。

　　当我们之前介绍垃圾算法时，它们共同的第一步是标记。标记过程需要一定的时间 STW（停止世界）。在 STW 过程中，CPU 不执行用户代码，即所有的用户线程都被挂起。用于垃圾回收，以便在标记时生成绝对一致的快照（我们可以暂时将GC Roots形成的链接图称为标记快照）。这个过程影响很大，因为它意味着挂起所有线程 就是程序执行的所有线程都被挂起。我们上层用户看到的现象就是程序完全卡死了。现在我们的heap越来越大，GC Roots自然会越来越大。从GC Roots向下遍历对象需要更多时间，暂停时间会变长。这是我们不能忍受的，所以JDK8使用cms垃圾采集器，而这个采集器的步骤之一就是并发标记。类似的高性能垃圾采集器（例如 G1）具有并发标记阶段。但是我们是否也可以在并发标记期间生成一个绝对一致的快照？如果不能保证，就会导致错误地将死对象标记为死对象，将活对象错误地标记为死对象。这就像你的宠物在屋子里走来走去，你正在整理他掉下来的头发。如果两者同时进行，能保证新落下的头发也能采集起来吗？但是我们是否也可以在并发标记期间生成一个绝对一致的快照？如果不能保证，就会导致错误地将死对象标记为死对象，将活对象错误地标记为死对象。这就像你的宠物在屋子里走来走去，你正在整理他掉下来的头发。如果两者同时进行，能保证新落下的头发也能采集起来吗？但是我们是否也可以在并发标记期间生成一个绝对一致的快照？如果不能保证，就会导致错误地将死对象标记为死对象，将活对象错误地标记为死对象。这就像你的宠物在屋子里走来走去，你正在整理他掉下来的头发。如果两者同时进行，能保证新落下的头发也能采集起来吗？

　　为了解决这个问题，我们不得不引入三色标记来帮助我们。寻找GC Roots的过程是根据垃圾采集器是否访问过的情况来判断的。垃圾采集器访问是安全的。没有被垃圾采集器访问过，说明它是一个新创建的对象，称为unsafe，所以也可以理解为从safe到unsafe的过程。三色标有三种颜色：

　　l 白色：垃圾采集器没有访问过的对象，或者分析后仍然无法访问的对象。

　　l Black：该对象已被垃圾采集器访问过，该对象引用的所有其他对象也已被访问过。代表对象是活的或已被扫描。

　　l 灰色：该对象已被垃圾采集器访问过，但该对象引用的所有其他对象都没有被访问过。所有访问后，它将转换为黑色。识别正在扫描的对象。

　　下面我们用一个图例来形象化三色打标的过程：

　　首先，如图1-14所示，垃圾采集器从GC Roots开始扫描引用链，扫描前所有对象都应该是白色的。

　　图1-14 三色打标第一步

　　第二步，在扫描过程中，GC Roots开始像白色一样前进。

　　图1-15 三色打标步骤二

　　第三步是扫描结束。从 GC Roots 链接的所有对象都是安全对象。如果对象没有被扫描为白色，垃圾采集器将在下一步中回收这些白色对象。

　　图1-16 三色打标步骤三

　　以上步骤都是基于STW的三色打标流程，必须依赖STW。比如cms采集器的初始标记和重新标记需要暂停用户线程。如果三色标记不使用STW，在标记过程中，程序逻辑会改变对象的引用，导致标记错误。如果将死对象标记为活着是错误的，则不会产生太大影响。它将在下一次 GC 中清除。如果幸存的对象被错误地标记为死亡，后果将是非常严重的，程序也会出错。让我们来看看这种情况是如何产生的，再次以传说的形式出现。

　　如图1-17所示场景，标记正在进行中。当到达B时，用户线程取消B对C的引用，然后将A对C的引用加入，此时用户线程还在继续。

　　图1-17 并发三色打标步骤1

　　如图1-18所示，进程已经继续扫描对象E，此时用户线程继续上述操作，取消E到F的引用，添加D到G的引用。

　　图1-18 并发三色打标步骤2

　　事实上，此时我们已经发现了问题。无需继续扫描。由于用户线程的工作，C和G对象引用发生了变化，成为幸存的对象。但是扫描过程没有加入到GC Roots引用链中，使得系统发生了错误。我们继续以cms垃圾采集器为例。cms 执行的一个步骤是并发标记。他的并发标记和上图中的1-17、1-18一样，都会存在。物体标记错误的现象。我们现在要做的不是并发标记错误，而是如何解决并发标记导致的“对象消失”和“意外死亡”。HotSpot 为我们提供了两种解决方案：

　　1. 增量更新（cms）：记录新插入的引用，并发标记完成后，重新扫描记录的引用关系的黑色对象为根。也就是说，一旦在黑色中插入了对白色的新引用，它就会变成灰色。

　　2. 原创快照（G1和Shenandoah）：当灰色对象想要删除对白色对象的引用时，记录引用。扫描后，从记录的参考灰色对象开始再次扫描

　　至此我们已经讲了很多垃圾采集算法，以及算法实现的细节。HotSpot从对象生成的那一刻，到内存恢复的开始，以及如何快速准确的恢复，做了很多工作。在实现方面，从GC Roots 快速扫描、内存集、卡片表，以及卡片页中元素的使用来维护堆中收录跨代引用的对象，以及三色标记和解决问题并发标记等引起的，可见虚拟机确实有帮助，所以我们做了很多努力，减少停顿，提高检索效率，减少各个区的内存，提高有效使用的记忆。在下一章，

　　胖虎

　　热爱生活的人

　　会被生活所爱

　　我在这里等你！