垃圾收集算法及细节

点击上方“晏霖”，选择“置顶或者星标”

曾经有人关注了我

后来他有了女朋友

1.4垃圾收集算法及细节

1.4.1 分代收集

这是我们一贯认为的垃圾收集方式，在大多的商业虚拟机中几乎都遵循着分代收集的理论。分代收集理论建立在以下三个方面。

l 弱分代假说（Weak Generational Hypothesis）：绝大多数对象都是朝生夕灭的。

l 强分代假说（Strong Generational Hypothesis）：熬过越多次垃圾收集过程的对象就越难以消亡。

l 跨代引用假说（Intergenerational Reference Hypothesis）：跨代引用相对于同代引用来说仅占极少数。

以上分代假说其实默许了垃圾收集器的设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄（熬过垃圾收集过程的次数）分配到不同的区域之中存储。也正是因为有了如此划分之后，我们才有针对某个区域进行回收的回收类型和回收算法的设计，还有我们经常听到的“Minor GC”、“Major GC”、“Full GC”这些名词。

分代收集在HotSpot中把Java堆设计成新生代（Young Generation）和老年代（Old Generation）两个区域，这就是我们常说的新生代和老年代的由来。在新生代中每次收集都会有大量的对象 ，只有少量的幸存者会逐渐晋升到老年代，故将新生代又细划分为一块较大的Eden（伊甸）空间和两块较小的Survivor（幸存）区，两块空间的比例默认是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的时候，如果对象还存活，就会给年龄加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标记-整理算法

标记-整理和标记-清除中的标记是不是一样啊，答案是肯定的，标记-整理相对于标记-清除一个很明显的区别在于“整理”，因为有了整理的过程，该算法解决了内存碎片化的问题。

该算法工作原理是：在标记了需要清除对象后，并不是直接进行清除，而是让所有的存活对象向前移动，然后清除掉其余的内存。如图1-11所示。

图1-11标记-整理算法

1.4.5 枚举根节点

根据前面的内容我们知道HotSpot是用可达性分析算法来判断对象是否存活，存活的关键是看对象是否在GC Roots的引用链上，那么现在重点就在于这个GC Roots，GC Roots的大多数数据都存在于方法区中，因为是线程共享，所以GC Roots也就是全局性质的引用，通常是常量、静态变量、栈帧中的本地变量表等维护程序执行上下文的信息，而我们正常一个Java程序的方法区大小从几百兆向上不等，而且在发生GC的时候要保证目前存在所有对象的引用都不变，就需要用户线程全部暂停，称为“Stop The World”，程序中的线程需要停止来配合可达性分析。如此庞大的空间要在每次垃圾回收时肯定是不能遍历整个引用链的，就好比系统用户量百万以上级别的，用户列表还能每次从硬盘读取吗？我们当然不会这么做。为了解决这一问题最早是用保守式GC和后来的准确式GC。这里准确式GC就会提到一个OopMap，用来保存类型的映射表，而在HotSpot中使用的就是准确式GC。

首先简单介绍一下保守式GC，他会从一些已知的位置进行扫描，只要扫描到一个数字就去判断这个引用是不是指向堆（这里的计算还是比较复杂的，有上下边界检查、对齐检查等），就这样一直检查下去，最后完成可达性分析。这种模糊的判断无法准确判断一个位置上是否是真的指向GC堆中的指针，所以被命名为保守式GC。这种模糊判断天生的性质就是速度快，准确率低，误判断的引用会导致垃圾收集器无法收集，导致空间的浪费。

接下来我们说一下准确式GC，他怎么就这么准确的知道哪个地方有引用指针呢？其实不通的虚拟机实现方式是有区别的，但在Java中就是知道对于某个位置上的数据是什么类型的，在加载类的时候HotSpot就已经把类的偏移量上的类型数据计算出来，然后会在即时编译时会在特定的位置记录栈和寄存器哪些位置引用了，这种从外部记录下类型信息，存成映射表，在HotSpot中把这种映射表称之为OopMap，不同的虚拟机名称是不一样的。

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

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

1. 每次都遍历原始的映射表，循环的一个个偏移量扫描过去；这种用法也叫“解释式”。

2. 为每个映射表生成一块定制的扫描代码（想像扫描映射表的循环被展开的样子），以后每次要用映射表就直接执行生成的扫描代码；这种用法也叫“编译式”。

1.4.6 安全点

OopMap可以帮助我们准确又快速的完成GC Roots枚举。我们可以把oopMap简单理解成是调试信息。在源代码里面每个变量都是有类型的，但是编译之后的代码就只有变量在栈上的位置了。OopMap就是一个附加的信息，告诉你栈上哪个位置本来是个什么东西。这个信息是在JIT编译时跟机器码一起产生的。因为只有编译器知道源代码跟产生的代码的对应关系。每个方法可能会有好几个OopMap，就是根据安全点把一个方法的代码分成几段，每一段代码一个OopMap，作用域自然也仅限于这一段代码。循环中引用多个对象，肯定会有多个变量，编译后占据栈上的多个位置。那这段代码的OopMap就会包含多条记录。所以是安全点的由来，简单来说就是：生成OopMap指令的位置称为安全点（Safepoint），安全点的选择遵循“是否让程序长时间执行的特征”，什么叫长时间？就是持续执行下去的意思，例如方法的调用、循环、异常跳转等这些节点上。

安全点上有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）来维护卡表的。第二章我们会介绍内存屏障volatile，既然是屏障，就都有一个共性，就是区域性对指令进行分隔，防止顺序变化引发的问题，屏障一般出现在并发的场景，在JVM中也是一样的，JVM中的并发指的是用户线程和垃圾收集线程一起工作。在JDK7之前，写屏障是无条件的，无论更新的引用是否存在跨代都会出现一些写屏障，更新引用一般在新生成对象后，对现有对OopMap变更赋值（也可以说对卡表进行更新），这里自然就会影响到卡表的值。赋值前后都属于写屏障，赋值前称为“写前屏障（Pre-Write Barrier）”，赋值后称为“写后屏障（Post-Write Barrier）”。这种方式个人认为还是比较懒的，故HotSpot在JDK7后加入-XX：+UseCondCardMark，来设置开启卡表更新判断。写屏障虽然使得开销变小，但是并发时会出现伪共享。

前面我们介绍垃圾算法时，他们共同点时第一步都是标记，标记过程需要一定时间的STW(stop the world)，STW的过程中，CPU不执行用户代码，也就是用户线程全部暂停，全部用于垃圾回收，这样标记时就会生成一个绝对一致性的快照（我们暂可把GC Roots形成的链路图称为标记后的快照），这个过程的影响很大，因为暂停全部线程的意思是所有程序执行的线程全部暂停，在我们上层使用者看到的现象是程序完全卡住。现如今我们的堆越来越大，GC Roots自然也就大，从GC Roots向下遍历对象的时间就会多，停顿时间就会变长，这个是我们忍受不了的，因此JDK8使用CMS垃圾收集器，而这个收集器其中一步就是并发标记，类似这种高性能的垃圾收集器如G1等都存在并发标记阶段。但是在并发标记的时候我们是否也能生成一个绝对一致性的快照呢？如果不能保证的话就会导致错误标记了死亡对象，也会将活的对象错误标记成死亡的。这就像你的宠物在屋子里活动，你在收拾他掉落的毛，两者同时进行话，是否能保证刚掉落的毛也能收集到呢？

想解决这一问题我们就要引入三色标记（Tri-color Marking）来帮助我们，把在寻找GC Roots过程，按照是否被垃圾收集器访问过这个条件判断，被垃圾收集器访问过说明安全，没有被垃圾收集器访问过，说明他是刚产生的对象，称为不安全的，所以也可以理解为从安全到不安全的过程。三色标记有三种颜色：

l 白色：尚未被垃圾收器访问过，或者分析后仍然是不可达的对象。

l 黑色：对象已被垃圾收集器访问过，而且本对象引用到的其他对象也全部访问过了。代表对象是存活或者已经扫描完毕。

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-18所示，流程已经继续扫描到了对象E，此时用户线程继续上述操作，取消了E对F的引用，增加了D到G的引用。

图1-18 并发三色标记步骤二

其实到这里我们已经发现了问题，没必要继续扫描下去了，由于用户线程的工作使得C和G对象引用发生改变，成为存活的对象，但是扫描过程中并没有加入到GC Roots引用链中，使得系统发生错误。我们继续拿CMS垃圾收集器举例子，CMS执行过程有一步是并发标记，他的并发标记和上述图中1-17、1-18一样，都会存在对象标记错误的现象。我们现在要将的是并不是并发标记是错误的，而是并发标记带来“对象消失”、“意外死亡”该如何解决。HotSpot为我们提供了两种解决方案：

1. 增量更新（CMS）：记录新插入的引用，并发标记完毕后，重新以记录下的引用关系的黑色对象为根扫描。即黑色一旦插入了新的到白色的引用，就变成了灰色。

2. 原始快照（G1和Shenandoah）：灰色对象要删除指向白色对象的引用时，将该引用记录下来，扫描完毕后，再从被记录下的引用的灰色对象开始重新扫描

到这里我们已经讲了好多垃圾收集的算法，以及算法实现的细节，HotSpot从对象生成的那一刻、到开始内存回收、如何快速准确的回收而做了很多工作，在实现上，从GC Roots的快速扫描、记忆集、卡表、又用卡页中元素维护堆中包含跨代引用的对象以及三色标记和解决并发标记带来的问题，等等这些工作我们可以看出虚拟机真的帮助了我们做了很多事情，为了低停顿、提高效检索效率、降低各个区域的内存提高有效使用内存而作出的努力。下一章我们就来讲一下在HotSpot中有哪些垃圾收集器。

胖虎

热 爱 生 活 的 人

终 将 被 生 活 热 爱

我在这里等你哟！