JVM--HostSpot算法细节实现

1.根节点枚举

定义：

        我们以可达性分析算法中从GC Roots 集合找引用链这个操作作为介绍虚拟机高效实现的第一个例 子。固定可作为GC Roots 的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如 栈帧中的本地变量表）中，尽管目标明确，但查找过程要做到高效并非一件容易的事情，现在Java 应 用越做越庞大，光是方法区的大小就常有数百上千兆，里面的类、常量等更是恒河沙数，若要逐个检 查以这里为起源的引用肯定得消耗不少时间。

  

      迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，因此毫无疑问根节点 枚举与之前提及的整理内存碎片一样会面临相似的“Stop The World” 的困扰。现在可达性分析算法耗时 最长的查找引用链的过程已经可以做到与用户线程一起并发，但根节点枚举始终还 是必须在一个能保障一致性的快照中才得以进行—— 这里 “ 一致性 ” 的意思是整个枚举期间执行子系统 看起来就像被冻结在某个时间点上，不会出现分析过程中，根节点集合的对象引用关系还在不断变化 的情况，若这点不能满足的话，分析结果准确性也就无法保证。这是导致垃圾收集过程必须停顿所有 用户线程的其中一个重要原因，即使是号称停顿时间可控，或者（几乎）不会发生停顿的CMS 、 G1 、 ZGC等收集器，枚举根节点时也是必须要停顿的。

重点：

        由于目前主流Java虚拟机使用的都是准确式垃圾收集（这个概念在第1章介绍Exact VM相对于Classic VM的改进时介绍过），所以当用户线程停顿下来之后，其实并不需要一个不漏地检查完所有 执行上下文和全局的引用位置，虚拟机应当是有办法直接得到哪些地方存放着对象引用的。在HotSpot 的解决方案里，是使用一组称为OopMap的数据结构来达到这个目的。一旦类加载动作完成的时候，HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译（过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就可以直接得知这些信息了，并不需要真正一个不漏地从方法区等GC Roots开始查找。

 2 .安全点

定义：

         在OopMap 的协助下， HotSpot 可以快速准确地完成 GC Roots 枚举，但一个很现实的问题随之而 来：可能导致引用关系变化，或者说导致OopMap 内容变化的指令非常多，如果为每一条指令都生成 对应的OopMap ，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法 忍受的高昂。

        实际上HotSpot 也的确没有为每条指令都生成 OopMap ，前面已经提到，只是在 “ 特定的位置 ” 记录 了这些信息，这些位置被称为安全点（Safepoint ）。有了安全点的设定，也就决定了用户程序执行时 并非在代码指令流的任意位置都能够停顿下来开始垃圾收集，而是强制要求必须执行到达安全点后才 能够暂停。因此，安全点的选定既不能太少以至于让收集器等待时间过长，也不能太过频繁以至于过 分增大运行时的内存负荷。安全点位置的选取基本上是以“ 是否具有让程序长时间执行的特征 ” 为标准 进行选定的，因为每条指令执行的时间都非常短暂，程序不太可能因为指令流长度太长这样的原因而 长时间执行，“ 长时间执行 ” 的最明显特征就是指令序列的复用，例如方法调用、循环跳转、异常跳转 等都属于指令序列复用，所以只有具有这些功能的指令才会产生安全点。 对于安全点，另外一个需要考虑的问题是，如何在垃圾收集发生时让所有线程（这里其实不包括 执行JNI 调用的线程）都跑到最近的安全点，然后停顿下来

使线程停留在安全点的两种方式：

    抢先式中断（ Preemptive Suspension ）和主动式中断（ Voluntary Suspension ）

        抢先式中断：

                不需要线程的执行代码 主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地 方不在安全点上，就恢复这条线程执行，让它一会再重新中断，直到跑到安全点上。现在几乎没有虚 拟机实现采用抢先式中断来暂停线程响应GC 事件。

       主动式中断：

                思想是当垃圾收集需要中断线程的时候，不直接对线程操作，仅仅简单地设置一

个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他需要在Java 堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象。

    简单举例二者的区别就是 ：如果让所有车都停在安全的位置检查，抢先式中断就相当于立刻拦截所有车辆，当发现有的车没在安全的位置，让他们继续行驶到安全的位置停下,主动式中断相当于所有车不断地问总台，什么时候需要停到安全的位置，当收到需要的时候，行驶到最近的安全的位置停下

3. 安全区域

便于理解：        

         还用上个举例，如果有的车没人驾驶停在路边，自然不会去安全点，此时又不能长时间暂停所有车辆，去等待没人驾驶的车中的驾驶员回来，这时就引入了一个特殊的区域

        但是如果别的车检查的时候,这辆没人驾驶的车中的驾驶员回来了，此时驾驶员刚刚不在所以没有收到查车的信号，此时怎么办呢？来看下面的定义

定义：

        使用安全点的设计似乎已经完美解决如何停顿用户线程，让虚拟机进入垃圾回收状态的问题了， 但实际情况却并不一定。安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。

        但是，程序“不执行 ” 的时候呢？所谓的程序不执行就是没有分配处理器时间，典型的

场景便是用户线程处于 Sleep 状态或者 Blocked 状态，这时候线程无法响应虚拟机的中断请求，不能再走 到安全的地方去中断挂起自己，虚拟机也显然不可能持续等待线程重新被激活分配处理器时间。

        对于 这种情况，就必须引入安全区域（Safe Region ）来解决。

        安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中 任意地方开始垃圾收集都是安全的 。我们也可以把安全区域看作被扩展拉伸了的安全点。

        当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域，那样当这段时 间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。        

         当线程要离开安全区域时，它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的 阶段），如果完成了，那线程就当作没事发生过，继续执行；否则它就必须一直等待，直到收到可以离开安全区域的信号为为止

4.并发的可达性分析

定义：

        曾经提到了当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象

是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析， 这意味着必须 全程冻结用户线程的运行 。在根节点枚举 这个步骤中，由于 GC Roots 相比起整个Java 堆中全部的对象毕竟还算是极少数，且在各种优化技巧（如 OopMap ）的加持下，它带来的停顿已经是非常短暂且相对固定（不随堆容量而增长）的了。可从GC Roots 再继续往下遍历对象图，这一步骤的停顿时间就必定会与Java 堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长，这听起来是理所当然的事情。

        要知道包含“ 标记 ” 阶段是所有追踪式垃圾收集算法的共同特征，如果这个阶段会随着堆变大而等 比例增加停顿时间，其影响就会波及几乎所有的垃圾收集器，同理可知，如果能够削减这部分停顿时 间的话，那收益也将会是系统性的。

        想解决或者降低用户线程的停顿，就要先搞清楚为什么必须在一个能保障一致性的快照上才能进 行对象图的遍历？为了能解释清楚这个问题，我们引入三色标记（Tri-color Marking ） 作为工具来辅助推导，把遍历对象图过程中遇到的对象，按照“ 是否访问过 ” 这个条件标记成以下三种颜色：

                白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。

                黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代 表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对 象不可能直接（不经过灰色对象）指向某个白色对象。

                灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

    

    关于可达性分析的扫描过程，读者不妨发挥一下想象力，把它看作对象图上一股以灰色为波峰的 波纹从黑向白推进的过程，如果用户线程此时是冻结的，只有收集器线程在工作，那不会有任何问题。

        但如果 用户线程与收集器是并发工作 呢？ 收集器在对象图上标记颜色，同时用户线程在修改引用关系——即修改对象图的结构。 这样可能出现两种后果：

         一种是把原本消亡的对象错误标记为存活 ， 这不是好事，但其实是可以容忍的，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好。

        另一种是把 原本存活的对象错误标记为已消亡， 这就是非常致命的后果了，程序肯定会因此 发生错误。

 下面图 演示了这样的致命错误具体是如何产生的：

Wilson 于 1994 年在理论上证明了，当且仅当以下两个条件同时满足时，会产生 “ 对象消失 ” 的问 题，即原本应该是黑色的对象被误标为白色：

         赋值器插入了一条或多条从黑色对象到白色对象的新引用；

        赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。

如何解决呢？

        我们要解决并发扫描时的对象消失问题，只需破坏这两个条件的任意一个即可。由此分别 产生了两种解决方案： 增量更新 （Incremental Update ）和 原始快照 （ Snapshot At The Beginning ，

SATB ）。

         增量更新要破坏的是第一个条件 ，当黑色对象插入新的指向白色对象的引用关系时，就将这个新 插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这可以简化理解为， 黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了 。

         原始快照要破坏的是第二个条件 ，当灰色对象要删除指向白色对象的引用关系时，就将这个要删 除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描 一次。这也可以简化理解为， 无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来 进行搜索。