根搜索算法

基本思路:通过一系列GCROOT作为起始点，这些节点开始向下搜索，搜索过的路径称为引用链,当一个对象和GCROOT之间没有任何引用链时，则证明对象是不可用的。

如下图所示，ObjectA,ObjectB,ObjectC为可用，ObjectD与ObjectE不可用

根搜索算法

GC ROOT对象

虚拟机栈(栈帧的本地变量表)中的引用的对象。
方法区中的类静态属性引用的对象。
方法区中的常量引用的对象。
本地方法栈中JNI(Native方法)的引用的对象。

如何获得GCROOT对象

如果每次都完全遍历方法区和栈，逐个检查其引用关系，那么每次都会消耗很多时间。
另外可达性分析对执行时间的敏感还体现在gc停顿上，因为这项工作必须在保持同一个版本号(引用关系不变)的快照中进行。
由于目前主流的java虚拟机都是精准式gc(知道一块内存是对象还是引用)，所以当执行系统停顿，并不需要一个不漏地检查完所有上下文和全局的引用位置。

hotsot是通过一组oopmap的数据结构来达到这个目的的，在类加载完成的时候，hotspot就把对象内什么偏移量上是什么类型的数据计算出来，在jit编译中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样,jvm在扫描时可以直接得知这些信息。

这一部分参考文章:找出栈上的指针/引用

如何加速维护oopmap

在oopmap的协助下，hotspot可以较快的完成gc root枚举，但是一个很现实的问题随之而来:可能导致引用关系变化，或者说oopmap内部内容变化的指令非常多，我不可能每次都生成对应的oopmap，那会需要大量空间，同时gc耗时也会增加。

为了解决这一问题。 hotspot做了如下措施:
没有为每条指令生成oopmap，只有在特定的地方记录这些信息,这些信息就是安全点(safepoint)，即程序运行时并非所有地方都能停下,必须到safepoint才可以进行枚举根节点。
但是做了这一措施后又会面临如下问题

如果safepoint的间隔过长，那么每次维护oopmap的时间就会很长;
如果safepoint的间隔过短，吞吐量可能会比较低。

如何到达safepoint

这里还有另外一个问题，我们该采用主动式中断还是抢先式中断:

抢占式中断:不需要线程的执行代码配合，在维护oopmap发生时，直接把所有线程中断，如果发现有线程中断的地方不在安全点，就恢复线程，让他"跑"到安全点。
主动式中断:主动式中断是通过维护oopmap需要实现中断线程的时候，不直接操作线程操作，仅仅是设置一个标志，各个线程执行主动轮询这个标志，发现中断标志为真时自己中断挂机。轮询标志的地方和安全点是重合的，另外加上创建对象需要分配内存的地方。

并不是所有线程都可以到达safepoint

并不是所有线程都可以到达safepoint，比如有线程没有执行,如何解决这一问题？

安全区域(safe region)

安全区域是指一段代码片段中，引用关系不会发生变化。在这个区域的任何地方都可以维护oopmap。
在线程执行到safe region的代码时，首先标识自己进入了safe region。这样维护oopmap的时候就不会管这些已经在safe region的线程。
通过这一方法解决了部分线程无法到达safepint 的问题。