根结点枚举与分代收集的关键结构
三色标记法演示并发分析时对象消失问题.png根结点枚举和OopMap
在可达性分析算法中，可以通过一系列被称为“GC Roots”的根对象作为起始节点集，从这些起始节点出发，构建出了一幅描述对象之间引用关系的图，通过判断某一对象到“GC Roots”是否可达，判断此对象当前的使用状态
在Java技术体系中，固定可作为“GC Roots“的对象包括：
- 在虚拟机栈（栈中本地变量表）中引用的对象
- 在方法区中类静态属性引用的对象
- 在方法区中常量引用的对象
- 在本地方法栈中JNI（即Native方法）引用的对象
- Java虚拟机内部的引用，如常驻的异常对象、类加载器等
- 所有被同步锁持有的对象
- 反映Java虚拟机内部情况的JMXBean、JVMTI中注册的回调、本地代码等
尽管“GC Roots”根节点的选取目标明确，但是从“GC Roots”集合出发建立引用链这个操作，就不得不从方法区和堆中对每个对象进行检查（即检查每个对象到GC Roots的可达），这里必定会耗费不少时间
为减少查找并检查每个对象的耗时，不同虚拟机的实现中都会采用不同的方式来记录存储对象的位置，以便直接得到那些地方存放着对象的引用；在HotSpot虚拟机的解决方案里，使用了一组称为OopMap的数据结构来达到这个目的
在HotSpot虚拟机中，一旦类加载动作完成的时候，HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用，这样收集器在扫描时就可以直接得知这些信息，并不需要真正一个不漏地从GC Roots开始查找
安全点
通过使用OopMap的数据结构，HotSpot已经可以快速准确地完成GC Roots枚举，但除此之外还有一个需要保证：即根节点枚举还始终必须保障在一个一致性快照中进行（即在整个枚举期间执行子系统就像被冻结在某个时间上），否则，在分析过程中根节点集合的对象引用关系还在不断变化就无法保证分析结果的准确性
迄今为止，所有收集器在根节点枚举这一步骤时都和之前提及的垃圾收集算法中的整理内存碎片一样存在“Stop The World”的停顿困扰；即使是号称停顿时间可控或者几乎不会发生停顿的CMS、G1、ZGC等收集器，枚举根节点时也是必须要停顿的**
在虚拟机中可能导致引用关系变化，或者说在HotSpot虚拟机中可能导致OopMap内容变化的指令非常多，如果为每一条指令都生成对应的OopMap，那么将会需要大量额外的存储空间；因此，在HotSpot虚拟机中，只是在“特定位置”记录生成OopMap，这些位置称为安全点（Safepoint）
安全点的存在，使得虚拟机在执行垃圾收集需要“Stop The World”时，必须强制要求用户线程必须达到安全点之后才能够暂停
安全点的选取基本上是以“是否具有让程序长时间执行的特征”为标准进行选定的；“长时间执行”最明显的特征就是指令序列的复用，例如方法调用、循环跳转、异常跳转等
关于使得用户线程的到达安全点的方案有两种：抢先式中断、主动式状态，现在的虚拟机大多采用主动式中断
- 抢先式中断
在垃圾收集发生时，系统将把所有用户线程中断，然后将没有在安全点中断的线程，恢复执行，直到跑到安全点之后在再次暂停
- 主动式中断
在垃圾收集发生时，将会设置一个标志位，各个线程执行过程中将不停的轮询这个标志，一旦发现标志位被置为中断状态时，就在离自己最近的安全点主动挂起；轮询的位置和安全点都是重合的，也包括所有创建对象和其他需要在Java堆上分配内存的地方，以避免在即将发生垃圾收集时去分配内存，出现内存分配不足的情况
安全区域
使用安全点和主动式中断，提供了活动线程对垃圾收集机制的准确性保证：可通过让用户线程轮询中断标志位的方式，进入安全点；但是对于当前处于sleep和blocked状态、没有处理器时间、已经挂起的线程确是没有办法
对于这种“静态线程”的情况，就需要引入安全区域（Safe Region）来解决；安全区域确保来在某一段代码片段中，引用关系不会发生变化
当用户线程执行到安全区域里面时，首先会标识自己已经进入了安全区域，当线程需要离开安全区域时，需要检查虚拟机是否已经完成了根节点枚举，如果还在进行则继续在安全区域等待
记忆集和卡表
垃圾收集器在新生代建立记忆集，用以避免把整个老年代加进GC Roots扫描范围
记忆集（Remembered Set）是一种用于记录从非收集区域执行收集区域的指针集合的抽象数据结构，在分代收集理论中，用以解决对象跨代引用所带来的问题
卡表（Card Table），则是记忆集抽象数据结构的具体实现，定义了记忆集的记录精度、与对内存的映射关系
卡页（Card Page），在HotSpot虚拟机里，使用字节数组来表示卡表（卡表最简单的形式，记录精度是字节，与内存的映射关系通过卡页来表示），字节数组中的每个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块就是卡页
一个卡页的内存通常包含不止一个对象，只要卡页内有一个对象字段存在着跨代引用，那么就将对应的卡表的数组元素值标识为1，称为这个元素变脏（通过写屏障维护），在垃圾收集时，只需要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描
写屏障
写屏障（Write Barrier），是HotSpot虚拟机里用于维护卡表状态（变脏）的技术，可以看作是虚拟机层面对“引用类型字段赋值”这个动作的AOP切面，在赋值前的写屏障称为写前屏障，在赋值后写屏障称为写后屏障，在G1收集器之前的收集器使用的都是写后屏障
应用写屏障后，虚拟机就会为所有赋值操作生成相应的指令，在赋值后（写后屏障）更新卡表
卡表在高并发下的会因为“伪共享”（缓存一致性协议）问题产生消耗，在JDK7之后，提供了-XX: UseCondCardMark参数，用以让虚拟机不采用无条件的写屏障，而是先检查卡表标记，只有当该卡表未被标记过时才将其标记为变脏
并发的可达性分析
上文提到可达性分析的根节点枚举还始终必须保障在一个一致性快照中进行，
这是因为在与用户线程并发的过程中对象之间不断变化的引用关系，将会导致分析结果的不准确（类比一下SQL中存在的脏读、幻读等情况），下图中就是使用三色标记法对并发分析时对象消失问题的演示
- 白色：表示对象尚未被垃圾收集器访问过，分析启动之初，所有对象都是白色，分析结束后，若对象还是白色，则表示对象不可达可回收
- 黑色：表示已经被垃圾收集器访问过，且这个对象的所有引用对象都已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无需重新扫描一遍；黑色不可能直接指向白色
- 灰色：标识对象已经被垃圾收集器访问过，但对象上至少存在一个引用还没有被扫描过
三色标记法演示并发分析时对象消失问题.png当且仅当，以下两个条件同时满足时，会产生“对象消失”的问题
- 赋值器插入了一条或多条从黑色对象到白色对象的新引用
- 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用
因此，要解决并发扫描时的对象消失问题，只需破坏两个条件的其中之一就行，由此分别产生了两种解决方案：增量更新、原始快照
- 增量更新
破坏第一个条件：当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次
- 原始快照
破坏第二个条件：当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次
CMS是基于增量更新来做的并发，G1、Shenandoah则是用原始快照来实现
