一、根节点枚举

• 固定可作为GC Roots的节点主要在全局性的引用(常量或类静态属性)与执行上下文(栈帧中的本地变量表)中，尽管目标明确，但查找过程要做到高效并非一件容易的事情，现在Java应用越做越大，光是"方法区"的大小就常有数百上千兆，里面的类、常量等更多，若要逐个检查以这里的起源的引用肯定得消耗不少时间
• 迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，因此毫无疑问根节点枚举与之前提及的整理内存碎片一样会面临相似的 "Stop-The-World"的困扰。
• 现在可达性分析算法耗时最长的查找引用链的过程已经可以做到与用户线程一起并发，但根节点枚举始终还是必须在一个能保障一致性的快照中才得以进行，这里"一致性"的意思是整个枚举期间执行子系统看起来就像被冻结在某个时间点上，不会出现在分析过程中，根节点集合的对象引用关系还在不断变化的情况，若这点不能满足的话，分析结果准确性也就无法保证。这是导致垃圾收集过程必须停顿所有用户线程的其中一个重要原因，即使是号称停顿时间可控，或者(几乎)不会发生停顿的CMS、G1、ZGC等收集器，枚举根节点时也是必须要停顿的
• 主流Java虚拟机使用的都是准确式垃圾收集，所以当用户线程停顿下来之后，其实并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得到哪些地方存放这对象引用的。在HotSpot的解决方案里，是使用一组称为OopMap的数据结构来达到这个目的。一旦类加载动作完成的时候，HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就可以直接得知这些信息了，并不需要真正一个不漏地从方法区等GC Roots开始查找

二、安全点

• 在OopMap的协助下，HotSpot可以快速准确地完成GC Roots枚举，但一个很现实的问题随之而来：可能导致引用关系变化，或者说导致OopMap内容变化的指令非常多，如果为每一条指令都生成对应的OopMap，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法忍受的高昂。实际上HotSpot也的确没有为每条指令都生成OopMap，前面已经提到，只是在"特定的位置"记录了这些信息，这些位置被称为安全点(SafePoint)。
• 有了安全点的设定，也就决定了用户程序执行时并非在代码指令流的任意位置都能够停顿下来开始垃圾收集，而是强制要求必须执行到达安全点后才能够暂停。所以，安全点的选定既不能太少以至于让收集器等待时间太长，也不能太过频繁以至于过分增大运行时的内存负荷。
• 安全点位置的选取基本上是以"是否具有让程序长时间执行的特征"为标准进行选定的，因为每条指令执行的时间都非常短暂，程序不太可能因为指令流长度太长这样的原因而长时间执行，"长时间执行"的最明显特征就是指令序列的复用，如：方法调用、循环跳转、异常跳转等都属于指令序列复用，所以只有具有这些功能的指令才会产生安全点。
• 对于安全点，需要考虑一个问题，如何在垃圾收集发生时让所有线程都跑到最近的安全点，然后停顿下来。
  • 抢先式中断(Preemptive Suspension)：抢先式中断不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复 这条线程执行，让他一会再重新中断，直到跑到安全点上。
  • 主动式中断(Voluntary Suspension)：主动式中断的思想是当垃圾回收需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象

三、安全区域

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

• 安全点的设计似乎已经完美解决如何停顿用户线程，让虚拟机进入垃圾回收状态的问题了。但实际情况却并不一定。安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但是，程序"不执行"的时候怎么办？所谓程序不执行就是没有分配处理器时间，典型的场景便是用户线程处于 Sleep 状态或者 Blocked 状态，这时候线程无法响应虚拟机的中断请求，不能走到安全点位置中断挂起自己，虚拟机也显然不可能持续等待线程重新被激活分配处理器时间。对于这种情况，就必须引入安全区域(Safe Region)来解决

• 当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域，那样当这段时间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。当线程要离开安全区域时，它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的阶段），如果完成了，那线程就当作没事发生过，继续执行；否则它就必须一直等待，直到收到可以离开安全区域的信号为止。

四、记忆表与卡表

• 在分代收集理论中提到了为解决"对象跨代引用"所带来的问题，垃圾收集器在新生代中建立了名为记忆集(Remembered Set)的数据结构，用以避免把整个老年代加进GC Roots 扫描范围。事实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集（Partial GC）行为的垃圾收集器，典型的如：G1、ZGC和Shenandoah收集器，都会面临相同的问题，因此有必要进一步理清记忆集的原理和实现方式。
• 记忆集：是一种用于记录从 "非收集"区域指向 "收集区域" 的指针集合的抽象数据结构。如果我们不考虑效率和成本的话，最简单的实现可以用 "非收集" 区域中所有含跨代引用的对象数组来实现这个数据结构。这种记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都相当高昂

Class RememberedSet { 
Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE]; 
}

• 字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的 32 为 或 64位，这个精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针
• 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针
• 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。卡精度所指的是用一种称为 "卡表"（Card Table）的方式去实现记忆表。卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等
• 卡表最简单的形式可以只是一个字节数组，而HotSpot虚拟机确实也是这样做的。以下这行代码是HotSpot默认的卡表标记逻辑

CARD_TABLE [this address >> 9] = 0;

• 字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称为 "卡页" (Card Page)。 image.png
• 一个卡页的内存中通常包含不止一个对象，只要卡页有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏（Dirty），没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把他们加入GC Roots中一并扫描

五、写屏障

• 已经解决了如何使用记忆集来缩减GC Roots 扫描范围的问题，但是还没有解决 "卡表" 元素如何维护的问题，如它们如何变脏、谁来把它们变脏等等
• 卡表元素何时变脏的答案是明确的——有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应用变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻
• 现在有一个问题是如何在对象赋值的那一刻去更新维护卡表呢？
  • 假如是解释执行的字节码，那相对好处理，虚拟机负责每条字节码指令的执行，有充分的介入空间
  • 在编译执行的场景中呢？因为经过即时编译后的代码已经是纯粹的机器指令流了，这就必须找到一个在机器码层面的手段，把维护卡表的动作放到每一个赋值操作中
• 在HotSpot虚拟机里是通过写屏障（Write Barrier）技术维护卡表状态的。
• 写屏障（Write Barrier）可以看作在虚拟机层面对“引用类型字段赋值”这个动作的 AOP 切面，在引用对象赋值时会产生一个环形（Around）通知，供程序执行额外的动作，也就是说赋值的前后都在写屏障的覆盖范畴内

void oop_field_store(oop* field, oop new_value) { 
// 引用字段赋值操作
 *field = new_value;
 // 写后屏障，在这里完成卡表状态更新 
post_write_barrier(field, new_value); 
}

• 应用写屏障后，虚拟机就会为所有赋值操作生成相应的指令，一旦收集器在写屏障中增加了更新卡表操作，无论更新的是不是老年代对新生代对象的引用，每次只要对引用进行更新，就会产生额外的开销，不过这个开销与Minor GC时扫描整个老年代的代价相比还是低的多的

六、并发的可达性分析

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

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

  • 白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达。
  • 黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表已经扫描过，它是安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接（不经过灰色对象）指向某个白色对象
  • 灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过 image.png

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

  • 赋值器插入了一条或多条从黑色对象到白色对象的新引用
  • 赋值器删除了全部从灰色对象到白色对象的直接或间接引用

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

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

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

• 无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。在HotSpot虚拟机中，CMS是基于增量更新来做并发标记的，G1、Shenandoah则是原始快照实现。