- 根节点枚举
- 从根节点开始遍历对象图
前文我们在介绍垃圾收集算法的时候，简单提到过：标记-整理算法(Mark-Compact)中的移动存活对象操作是一种极为负重的操作，必须全程暂停用户应用程序才能进行，像这样的停顿被最初的虚拟机设计者形象地描述为 “Stop The World (STW)”。
显然 STW 并不是一件好事，能够避免那就需要尽可能避免。
在可达性分析中，第一阶段 ”可达性分析“ 是必须 STW 的，而第二阶段 ”从根节点开始遍历对象图“，如果不进行 STW 的话，会导致一些问题，由于第二阶段时间比较长，长时间的 STW 很影响性能，所以大佬们设计了一些解决方案，从而使得这个第二阶段可以不用 STW，大幅减少时间。
先这样笼统的介绍下，大伙儿对可达性分析的整体脉络有个认识就行，下面会详细解释，我会分两篇文章来写，本篇就先来分析第一阶段 ”可达性分析“！
根节点枚举
迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，枚举过程必须在一个能保障 ”一致性“ 的快照中才得以进行。
通俗来说，整个枚举期间整个系统看起来就像被冻结在某个时间点上，不会出现在分析过程中，用户进程还在运行，导致根节点集合的对象引用关系还在不断变化的情况，若这点都不能满足的话，可达性分析结果的准确性显然也就无法保证。
也就是说，根节点枚举与我们之前提到的标记-整理算法(Mark-Compact)中的移动存活对象操作一样会面临相似的 “Stop The World” 的困扰。
另外，众所周知，可作为 GC Roots 的对象引用就那么几个，主要在全局性的引用(例如常量或类静态属性)与执行上下文(例如虚拟机栈中引用的对象)中，尽管目标很明确，但查找过程要做到快速高效其实并不是一件容易的事情。
现在 Java 应用越做越庞大，光是方法区的大小就常有数百上千兆，里面的类、常量等更是一大堆，要是把这些区域全都扫描检查一遍显然太过于费事。
那有没有办法减少耗时呢?
一个很自然的想法，空间换时间!
把引用类型和它对应的位置信息用哈希表记录下来，这样到 GC 的时候就可以直接读取这个哈希表，而不用一个区域一个区域地进行扫描了。Hotspot 就是这么实现的，这个用于存储引用类型的数据结构叫 OopMap。
下图是 HotSpot 虚拟机客户端模式下生成的一段 String::hashCode() 方法的本地代码，可以看到在 0x026eb7a9 处的 call 指令有 OopMap 记录，它指明了 EBX 寄存器和栈中偏移量为 16 的内存区域中各有一个 OopMap 的引用，有效范围为从 call 指令开始直到0x026eb730(指令流的起始位置)+ 142(OopMap 记录的偏移量)= 0x026eb7be，即 hlt 指令为止。
实话实说，这段不理解也就算了，知道 OopMap 是这么一个东西就行了。
安全点 Safe Point
在 OopMap 的协助下，HotSpot 可以快速完成根节点枚举了，但一个很现实的问题随之而来：由于引用关系可能会发生变化，这就会导致 OopMap 内容变化的指令非常多，如果为每一条指令都生成对应的 OopMap，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法忍受的高昂。
所以实际上 HotSpot 也确实没有为每条指令都生成 OopMap，只是在 “特定的位置” 生成 OopMap，换句话说，只有在某些 ”特定的位置“ 上才会把对象引用的相关信息给记录下来，这些位置也被称为安全点(Safepoint)。
有了安全点的设定，也就决定了用户程序执行时并不是随便哪个时候都能够停顿下来开始 GC 的，而是强制要求程序必须执行到达安全点后才能够进行 GC(因为不到达安全点话，没有 OopMap，虚拟机就没法快速知道对象引用的位置呀，没法进行根节点枚举)。
如下图所示：
因此，安全点的设定既不能太少以至于让垃圾收集器等待时间过长，也不能太多以至于频繁进行垃圾收集从而导致运行时的内存负荷大幅增大。所以，安全点的选定基本上是以 “是否具有让程序长时间执行的特征” 为标准进行选定的，最典型的就是指令序列的复用：例如方法调用、循环跳转、异常跳转等，所以只有具有这些功能的指令才会产生安全点。
对于安全点，另外一个需要考虑的问题是，如何在 GC 发生时让所有用户线程都执行到最近的安全点，然后停顿下来呢?。这里有两种方案可供选择：
- 抢先式中断(Preemptive Suspension)：这种思路很简单，就是在 GC 发生时，系统先把所有用户线程全部中断掉。然后如果发现有用户线程中断的位置不在安全点上，就恢复这条线程执行，直到跑到安全点上再重新中断。
抢先式中断的最大问题是时间成本的不可控，进而导致性能不稳定和吞吐量的波动，特别是在高并发场景下这是非常致命的，所以现在几乎没有虚拟机实现采用抢先式中断来暂停线程响应 GC 事件。
- 主动式中断(Voluntary Suspension)：主动式中断不会直接中断线程，而是全局设置一个标志位，用户线程会不断的轮询这个标志位，当发现标志位为真时，线程会在最近的一个安全点主动中断挂起。现在的虚拟机基本都是用这种方式。
安全区域 Safe Region
安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。
对于主动式中断来说，用户线程需要不断地去轮询标志位，那对于那些处于 sleep 或者 blocked 状态的线程(不在活跃状态的线程)来说怎么办?
这些不在活跃状态的线程没有获得 CPU 时间，没法去轮询标志位，自然也就没法找到最近的安全点主动中断挂起了。
换句话说，对于这些不活跃的线程，我们没法掌控它们醒过来的时间。很可能其他线程都已经通过轮询标志位到达安全点被中断了，然后虚拟机开始根节点枚举了(根节点枚举需要暂停所有用户线程)，但是这时候那些本不活跃的用户线程又醒过来了开始执行，破坏了对象之间的引用关系，那显然是不行的。
对于这种情况，就必须引入安全区域(Safe Region)来解决。
安全区域的定义是这样的：确保在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中的任意地方开始 GC 都是安全的。
可以简单地把安全区域看作被拉长了的安全点。
当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域。那样当这段时间里虚拟机要发起 GC 时，就不必去管这些在安全区域内的线程了。当安全区域中的线程被唤醒并离开安全区域时，它需要检查下主动式中断策略的标志位是否为真(虚拟机是否处于 STW 状态)，如果为真则继续挂起等待(防止根节点枚举过程中这些被唤醒线程的执行破坏了对象之间的引用关系)，如果为假则标识还没开始 STW 或者 STW 刚刚结束，那么线程就可以被唤醒然后继续执行。
