算法 自动采集列表(我后来他有了女朋友1.41.4.1分代收集这是收集 )

　　算法 自动采集列表(我后来他有了女朋友1.41.4.1分代收集这是收集

)

　　点击上方的“颜琳”并选择“顶级或明星”

　　曾经有人关注过我

　　后来他有了女朋友

　　

　　1.4 垃圾采集算法及细节

　　1.4.1代采集

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

　　l Weak Generational Hypothesis（Weak Generational Hypothesis）：绝大多数物体都会生与死。

　　lStrong Generational Hypothesis：对象越难在垃圾回收过程中存活。

　　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 第三种是按年龄计算。每次在新生代中，如果对象还活着，则将年龄加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-organization 和mark-clearance 中的mark 是一样的吗？答案是肯定的。 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”，在需要停止程序线程以配合可达性分析。这么大的空间肯定不可能每次垃圾回收都遍历整个引用链。它就像一个拥有超过一百万用户的系统。可以每次都从硬盘读取用户列表吗？我们当然不会这样做。为了解决这个问题，首先使用了conservative GC和后来的accurate GC。 Accurate GC会提到一个OopMap，用于保存类型的映射表，HotSpot使用的是Accurate GC。

　　首先简单介绍一下conservative GC。它会从一些已知的位置开始扫描，只要扫描一个数，就会判断引用是否指向堆（这里的计算还是比较复杂的，有上下边界检查，Alignment检查等），一直这样检查，最后完成可达性分析。这种模糊判断不能准确判断一个位置是否是指向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），所以我们可以换一种说法：卡表是实现内存集的一种方式，记录内存集的记录精度以及堆和内存堆的映射关系。这种方法目前在虚拟机中也被广泛使用。

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

　　

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

　　1.4.8 并发采集写屏障

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

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

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

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

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

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

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

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

　　

　　图1-14 三色标记第一步

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

　　

　　图1-15 三色标记步骤二

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

　　

　　图1-16 三色标记步骤三

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

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

　　

　　图1-17 并发三色标记第一步

　　如图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、内存集、卡片表，以及维护堆中收录与卡片页面元素的跨代引用的对象，三色标记以及解决并发标记引起的问题等。我们可以看到虚拟机确实帮我们做了很多事情，为了减少停顿，提高检索效率，减少每个区域的内存，提高内存的有效使用。在下一章中，我们将讨论 HotSpot 中可用的垃圾采集器。

　　

　　胖虎

　　热爱生活的人

　　我终将被生活所爱

　　我在这里等你！