根节点枚举

以可达性分析算法中从GC Roots集合找引用链这个操作作为介绍虚拟机高效实现的第一个例子。

固定可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中。目标明确，但Java应用越做越庞大，方法区的大小就常有数百上千兆，里面的类、常量等更是恒河沙数，检查以这里为起源的引用需耗费大量时间。

主流Java虚拟机使用的都是准确式垃圾收集 ，直接得到哪些地方存放着对象引用的。

HotSpot使用一组称为OopMap的数据结构来达到这个目的。类加载动作完成的时，会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，在特定的位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就可以直接得知这些信息了，不需要一个不漏地从方法区等GC Roots开始查找。

安全点

HotSpot 没有为每条指令都生成OopMap， 只是在“特定的位置”记录了引用信息，这些位置被称为安全点（Safepoint）。

程序执行时并非在代码指令流的任意位置都能够停顿下来开始垃圾收集，而是强制要求必须执行到达安全点后才能够暂停。

安全点的选定

• 不能太少以至于让收集器等待时间过长；
• 不能太过频繁以至于过分增大运行时的内存负荷。

如何在垃圾收集发生时让所有线程都跑到最近的安全点？

1、抢先式中断（Preemptive Suspension）

​ 不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断；发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，一会再重新中断，直到跑到安全点。

2、主动式中断（Voluntary Suspension）

​ 当垃圾收集需要中断线程的时候，不直接对线程操作，设置一个标志位，各个线程执行过程时会不停地主动去轮询这个标志，发现中断标志为真时就在最近的安全点上主动中断挂起。

轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他需要在Java堆上分配内存的地方。从而检查是否即将要发生垃圾收集，避免没有足够内存分配新对象。

解决问题：安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。

缺陷：程序“不执行”的时候，即没有分配处理器时间（如用户线程处于Sleep状态或者Blocked状态），这时线程无法响应虚拟机的中断请求，不能再走到安全的地方去中断挂起自己，虚拟机也不可能持续等待线程重新被激活分配处理器时间。对于这种情况，就必须引入安全区域（Safe Region）来解决。

安全区域

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

当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域。这段时间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。当线程要离开安全区域时，它要检查虚拟机是否已经完成了根节点枚举（或垃圾收集过程中其他需要暂停用户线程的阶段）。

• 完成了， 继续执行；
• 否则，一直等待至收到可以离开安全区域的信号 。

记忆集和卡片

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。

在垃圾收集的场景中，收集器通过记忆集判断出某一块非收集区域，是否存在指向了收集区域的指针，不需要了解跨代指针的全部细节。

记录精度

• 字长精度：每个记录精确到一个机器字长（处理器的寻址位数，如常见的32位或64位，决定了机器访问物理内存地址的指针长度），该字包含跨代指针。

• 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。

• 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。

“卡精度”是用一种称为“卡表”（CardTable）的方式去实现记忆集 ，是最常用的一种记忆集实现形式。

卡表最简单的形式可以只是一个字节数组 ， 字节数组每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称作“卡页”（CardPage）。

关于卡表与记忆集的关系，可按照Java语言中HashMap与Map的关系来类比理解。

元素变脏（Dirty）：一个卡页的内存中通常包含多个对象，卡页内有一个（或更多）对象的字段存在跨代指针，就将对应卡表的数组元素的值标识为 1，若无则标识为0.

在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。

卡表元素如何维护的问题，例如它们何时变脏、谁来把它们变脏？

有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的一刻。

如何变脏，在对象赋值的一刻去更新维护卡表呢？

解释执行的字节码， 虚拟机负责每条字节码指令的执行，有充分的介入空间；

编译执行 ，经过即时编译后的代码已经是纯粹的机器指令流了，这就必须找到一个在机器码层面的手段，把维护卡表的动作放到每一个赋值操作之中，即写屏障。

写屏障

写屏障可以看作在虚拟机层面对“引用类型字段赋值”这个动作的AOP切面 ，在引用对象赋值时会产生一个环形（Around）通知，供程序执行额外的动作，也就是说赋值的前后都在写屏障的覆盖范畴内。

在赋值前的部分的写屏障叫作写前屏障（Pre-Write Barrier），在赋值后的则叫作写后屏障（Post-Write Barrier）。

应用写屏障后，虚拟机会为所有赋值操作生成相应的指令，一旦收集器在写屏障中增加了更新卡表操作，无论更新的是不是老年代对新生代的引用，每次只要对引用进行更新，就会产生额外的开销。

伪共享问题

高并发场景下“伪共享（False Sharing）”问题：多线程修改互相独立的变量时，如果这些变量恰好共享一个缓存行，会彼此影响而导致性能降低。

“伪共享”问题解决：先检查卡表标记，仅当该卡表元素未被标记过时才将其标记为变脏。

并行的可达性分析

可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能进行分析，这意味着必须全程冻结用户线程（Stop The World）。

为什么必须在一个能保证一致性的快照上才能进行对象图的遍历呢？

1、用户线程是冻结的，没问题；

2、用户线程没冻结，也就是用户线程与收集器并发工作呢？收集器在对象图标记，同时用户线程在修改引用关系（修改对象图的结构），这样可能出现两种后果：

• 原本消亡的对象错误标记为存活，这种情况虽不好（产生了浮动垃圾），但还可以容忍。
• 原本存活的对象标记为消亡，这就很严重了，程序肯定会因此报错。

可达性分析的扫描过程如下所示：

对象消失问题.png

上图三色含义：

• 白色：对象尚未被垃圾收集器访问过（若在分析结束后，对象仍为白色，则表示不可达）
• 黑色：对象已被垃圾收集器访问过，且该对象所有引用都已被扫描（安全存活的）
• 灰色：对象已被垃圾收集器访问过，但未扫描完所有引用（即该对象正在被扫描，可理解为中间态）

如何解决上述“对象消失”的问题呢？

“对象消失”的问题产生条件：

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

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

破坏产生条件之一，便可解决问题，由此产生两种解决方案：

• 增量更新（Increment Update）

  破坏的是第一个条件，黑色对象插入新的指向白色对象的引用关系时，将这个新插入的引用记录，等并发扫描结束之后，将这些记录过的引用关系中的黑色对象为根，重新扫描一次。

  简化理解：黑色对象一旦新插入了指向白色对象的引用之后，就变回灰色对象。

• 原始快照（Snapshot At The Begining, SATB）。

  破坏的是第二个条件，灰色对象要删除指向白色对象的引用关系时，将这个要删除的引用记录下来。并发扫描结束之后，将这些记录过的引用关系中的灰色对象为根，重新扫描一次。

  简化理解：无论引用关系删除与否，都按照刚刚开始扫描那一刻的对象图快照来进行搜索。

以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。

在HotSpot虚拟机中，增量更新和原始快照这两种解决方案都有实际应用，譬如，CMS是基于增量更新来做并发标记的，G1、Shenandoah则是用原始快照来实现。

以上主要是为了稍后介绍各款垃圾收集器时做前置知识铺垫，如果感到枯燥或者疑惑，可跳过去，等后续遇到要使用它们的实际场景、实际问题时再结合问题，重新翻阅和理解。

欢迎点赞/评论，你们的赞同和鼓励是我写作的最大动力！