前言
JVM中哪些内存需要回收中简单说明了如何判断对象是否已经称为垃圾对象，并简单介绍了可达性分析算法，了解了可作为 GC Roots 的对象有哪几种。而在垃圾收集算法中，我们也知道对象可能会存活在不同的区域，跨区域引用是客观存在的。这一章节将会更详细地介绍可达性分析算法的实现细节。
根节点枚举
OopMap
JVM中哪些内存需要回收中介绍了 GC Roots 都有哪些，这些对象占比虽然很小，但是数量却十分多。如果挨个遍历做引用判断的话，那么将会消耗大量的时间。而且至今为止所有垃圾收集器在做根节点枚举时都是需要暂停用户线程的（因为可达性分析算法做引用判断时需要根节点的对象引用关系是不变的，这样才能保证不会出现回收非死亡对象这种严重的bug）。这样Java的应用就无法提供给人使用了，因为明显的卡顿对用户体验来说是毁灭性的打击。
实际上，虚拟机不需要遍历所有根节点，根据自己想要回收的内存区域去扫描这个区域相关的 GC Roots 即可。在 HotSpot 中，它是通过维护 OopMap 来记录哪些地方存放着对象引用的，这样收集器在扫描时就不需要检查所有的 GC Roots。
安全点
在 OopMap 的协助下，HotSpot 可以快速准确地完成 GC Roots 枚举，但是也带来了新的问题：
可能导致引用关系变化或者说导致 OopMap 内容变化的指令非常多。如果为每一条指令都生成对应的 OopMap，那将会需要大量的额外存储空间。这样垃圾收集伴随而来的空间成本就会变得无法忍受的高昂。
需要保证 OopMap 内容不发生变化的位置才能选用为安全点（Safepoint）。用户程序执行时并非在代码指令流的任意位置都能够停顿下来开始垃圾收集的，而是强制要求必须到达安全点才能够暂停。
因此，安全点的选定既不能太少以至于让垃圾收集器等待时间过长，也不能太多以至于过分增大运行时的内存负荷。安全点位置的选取基本上是以 “是否具有让程序长时间执行的特征” 为标准进行选定的。“长时间执行”的最明显特征就是指令序列的复用（例如：方法调用、循环跳转、异常跳转等等），所以只有具有这些功能的指令才会产生安全点。
知道安全点的选取之后，就要思考：如何在垃圾收集发生时让所有线程（不包括执行 JNI 调用的线程）都跑到最近的安全点，然后停顿下来。有两种方案可供选择：抢先式中断（Preemptive Suspension）和主动式中断（Voluntary Suspension，目前大多数虚拟机都采用这个方案响应 GC 事件）。
抢先式中断：抢先式中断不需要线程的执行代码主动配合，在垃圾收集发生时，系统首先把所有用户线程全部中断；如果发现有线程不在安全点上，就恢复该线程执行，让它跑到安全点再重新中断。
主动式中断：当垃圾收集需要中断线程时，不直接对线程操作，仅仅设置一个标志位，各个线程执行过程中会不停地轮询该标志，一旦发现该标志为true时，就会在最近的安全点上主动挂起。
安全区域
安全点看似已经完美解决如何停顿用户线程，让虚拟机进入垃圾回收状态的问题。安全点机制保证了程序执行时在不太长的时间内就会遇到可进入垃圾收集过程的安全点，但是程序“不执行”的时候呢？比如用户线程处于 Sleep 状态或者 Blocked 状态，这时候线程无法响应虚拟机的中断请求，不能再走到安全点中断挂起自己，虚拟机也不可能一直傻傻地等线程重新激活走到安全点。对于这种情况，就必须引入安全区域（Safe Region）来解决。
安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化。因此，在这个区域任意地方开始垃圾收集都是安全的。我们也可以把安全区域看作为被拉伸了的安全点。
当用户线程执行到安全区域时，首先会标识自己已进入安全区域，虚拟机发起垃圾收集时就不需要管那些声明在安全区域的线程。当线程要离开安全区域时，它要检查虚拟机是否已经完成垃圾收集过程中需要暂停用户线程的阶段(如：根节点枚举)。如果完成了，那线程可以离开安全区域继续执行；否则它需要收到垃圾收集器发出可以离开安全区域的信号才可以离开安全区域。
记忆集与卡表
垃圾收集算法提到使用分代收集理论实现的垃圾收集器存在对象跨代引用的问题（哪怕是现在ZGC，虽然没有分代的概念了，但是仍然有区域的概念，跨代引用的问题本质上就是分区域进行垃圾收集，可是对象关系图并非独立所带来的问题。这里以跨代以用为例子）。因此，我们有必要了解虚拟机是如何解决这个问题的。
记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。
最简单的实现方式如下
Class RememberedSet {
Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE];
}
这种记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都相当高。而在垃圾收集的场景中，收集器只需要通过记忆集判断出某一块非收集区域是否存在指向收集区域的指针即可。因此，设计记忆集时，可以选择记录精度更粗的实现方式来节省记忆集的存储成本和维护成本，具体如下：
- 字长精度
每个记录精确到机器字长（处理器的寻址位数），该字包含跨代指针。 - 对象精度
每个记录精确到一个对象，该对象里有字段含有跨代指针。 - 卡精度
每个记录精确到一块内存区域，该区域内有对象含有跨代指针。
“卡精度” 所指的是用一种称为“卡表”（Card Table）的方式去实现记忆集，这也是目前最常用的一种记忆集实现形式。这里需要知道“记忆集”是一种思路，只有一个大概设计方向的数据结构；而“卡表”则是“记忆集”的一种具体实现方案了，它定义了记忆集的记录精度、堆内存的映射关系等。如果觉得还是难理解它们的关系，那可以简单理解成 HashMap 与 Map 之间的关系。
HotSpot 是用一个字节数组实现卡表的，变量声明如下
CARD_TABLE[this address >> 9] = 1;
CARD_TABLE 的每个元素都对应着一块特定大小的内存块，这个内存块被称作 “卡页”。看上面代码可知 HotSpot 中使用的卡页是 2 的 9 次幂，即 512 字节，如下图
一个卡页内往往有许多对象，只要卡页内有对象的字段存在着跨代指针，那就将该卡页对应的卡表元素标识为1，称为这个元素变脏，没有则标识为0。垃圾收集时，只要筛选卡表中变脏的元素对应卡页中的对象加入 GC Root 中一起扫描即可。
写屏障
我们已经用记忆集来缩减 GC Roots 扫描范围的问题，但还没有解决卡表元素如何维护的问题，例如：何时变脏、谁来让它们变脏等等。
卡表元素何时变脏？有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻。那么要如何才能在对象赋值的那一刻去更新维护卡表呢？垃圾收集在编译执行的场景中发生，这里需要面对的是机器指令流。这就需要从机器码层面去把维护卡表的动作放到每一个赋值的操作之中。
HotSpot 是通过写屏障（Write Barrier）技术维护卡表的。
这个写屏障可不是我们学习并发时说的“内存屏障”，千万不要混淆。
写屏障解决问题的思想类似 spring 的 AOP，在引用对象赋值这个动作做了一个切面，在对象赋值动作的前后做技术处理。在赋值前执行的部分叫“写前屏障”（Pre-Write Barrier），在赋值后的部分逻辑则称为“写后屏障”（Post-Write Barrier）。冷门小知识：在 G1 出现之前，其他收集器都只用了写后屏障。
应用写屏障后，虚拟机就会为所有赋值操作生成相应的指令，一旦收集器在写屏障中增加了更新卡表操作，无论更新的是不是老年代对新生代的引用，每次只要对引用进行更新，就会产生额外的开销，不过这个开销与 Minor GC 时扫描整个老年代的代价相比还是低得多。
实际上卡表除了写屏障这个额外开销以外,在高并发的场景下还有“伪共享”问题。现代 CPU 的缓存行大小一般为 64 字节。而我们卡表一个元素是一个字节，假设有 64 个卡表元素共享了一个缓存行，那么这 64 个卡表元素映射的32KB（64 * 512 字节）内存里的对象被不同线程更新时，就会导致更新卡表时因为是用了同一个缓存行而导致性能降低。为了提升性能，在更新卡表元素状态前，要先判断下状态是否已经“脏”了，只有还是“干净”的元素需要更改状态，这个叫有条件更新卡表，我们可以通过 -XX:+UseCondCardMark 来选择是“有条件更新卡表”，还是“无条件更新卡表”。
PS：具体是开启“有条件更新卡表”更好，还是使用“无条件更新卡表”更好，需要根据自己应用进行实测来判断。
并发的可达性分析，三色标记算法
总所周知，当前主流的垃圾收集器基本上都是依靠可达性分析算法来判断对象是否存活，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才进行分析，这意味着“Stop the World”。根节点枚举这个步骤在 OopMap 的优化技巧下，它所需要的停顿时间已经非常短暂且相对固定（不随堆容量而增长）的了。可是从 GC Roots 往下遍历对象图，这一步骤的停顿时间势必与堆容量成正比关系——堆的对象越多，对象图越复杂，标记对象所产生的停顿时间越长。
“标记”阶段是所有追踪式垃圾收集算法的共同特征，如果这个阶段会随堆变大而等比例增加停顿时间，那么采用这类型算法的垃圾收集器都会被诟病。因此，如果能够削减这部分的停顿时间的话，那么带来的收益也将会是巨大的。
为了降低用户线程的停顿问题，出现了三色标记算法。三色标记算法通过将垃圾回收过程拆分为多个小步骤，使得垃圾回收器和应用程序可以交替执行（也就是支持并发执行），从而减少垃圾回收对应用程序运行的影响，增强了实时性和响应性。
三色标记算法顾名思义，它定义了三种颜色，如下：
- 白色
表示对象尚未被垃圾收集器访问过。 - 黑色
表示对象已经被垃圾收集器访问过，而且其子对象也扫描完成（因此黑色对象不可能没有关联灰色对象直接指向白色对象），属于存活对象。 - 灰色
表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。
三色标记算法的执行过程如下：
- 初始化阶段
- 所有对象最初都标记为白色。
- 根对象标记为灰色，并将其放入一个待处理集合（通常是队列或栈）。
- 标记阶段
- 从灰色对象集合中取出一个对象，将其标记为黑色，并将该对象引用的所有白色子对象标记为灰色，并加入灰色对象集合。
- 重复上述过程，直到灰色对象集合为空。
- 清除阶段
- 当标记阶段完成后，所有仍为白色的对象即为垃圾对象，可以被回收。
要支持并发执行，要注意不能误删存活对象，否则就是一个严重 Bug。Wilson 于 1940 年在理论上证明了，当且仅当以下两个条件同时满足时，会产生误删问题：
- 赋值器插入了一条或者多条从黑色对象到白色对象的新引用。
- 赋值器删除了全部从灰色对象到某白色对象的直接或间接引用。
因此，要解决误删问题，只需要破坏上述任一条件即可。由此分别产生了两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。
增量更新破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。
原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次。
以上两种方案都是通过写屏障实现的。在 HotSpot 中，这两种方案都有实际的应用，比如 CMS 就是基于增量更新来做并发标记的，G1 和 Shenandoah 则是使用原始快照来实现的。
总结
- 安全区域
解决何时可以开始垃圾收集（必须 Stop the world 的行为）。 - 记忆集
解决 GC Roots 扫描范围问题。 - 写屏障
解决 卡表 维护问题。
