Java 虚拟机在实现垃圾收集算法时，必须对算法的执行效率有严格的考量，才能保证虚拟机高效运行。下面介绍虚拟机为了提高算法效率在具体实现上做了哪些工作。

根节点枚举

固定可作为 GC Roots 的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧的本地变量表）中，尽管目标明确，但查找过程要做到高效并非易事，现在 Java 应用越做越庞大，光是方法区的大小就常有数百上千兆，里面的类、常量等更是恒河沙数，若要逐个检查以这里为起源的引用肯定消耗不少时间。

迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，因此根节点枚举与之前提及的整理内存碎片一样会面临相似的 Stop The World 的困扰。现在可达性分析算法耗时最长的查找引用链的过程已经可以做到与用户线程一起并发，但根节点枚举始终还是必须在一个能保障一致性的快照中才得以进行。这是导致垃圾收集过程必须停顿所有用户线程的一个重要原因。即使是号称停顿时间可控，或者几乎不会发生停顿的 CMS、G1、ZGC 等收集器，枚举根节点时也是必须要停顿的。

由于目前主流 Java 虚拟机使用的都是准确式垃圾收集（指虚拟机可以知道内存中某个位置的数据具体是什么类型，这样它就能知道是不是 GC Roots 的引用节点了），所以当用户线程停顿下来后，其实并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机是能直接得到哪些地方存放着对象引用的。

在 HotSpot 的解决方案里，是使用一组称为 OopMap（Ordinary Object Pointer，OOP）的数据结构来达到这个目的。一旦类加载动作完成时，HotSpot 就会把对象内什么偏移量上是什么类型的数据计算出来，然后保存在 OopMap 中。这样收集器在扫描时就可以根据 OopMap 直接得知这些对象引用的信息了，而不用真正一个不漏地从 GC Roots 开始查找。

安全点

在 OopMap 的协助下，HotSpot 可以快速准确地完成 GC Roots 枚举，但对象间的引用关系是很容易发生改变的，如果为每一条指令都生成对应的 OopMap 判断逻辑，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法忍受的高昂。

实际上 HotSpot 也的确没有为每条指令都生成 OopMap 判断逻辑，上面提到，只是在“特定的位置”记录了这些信息，这些位置被称为安全点（SafePoint）。有了安全点的设定，也就决定了用户程序执行时并非在代码指令流的任意位置都能够停顿下来开始垃圾收集，而是强制要求必须所有的线程执行到达安全点后才允许请求 Stop-the-world 的线程进行独占的工作。安全点的设计目的是为了找到一个稳定的执行状态，在这个状态下，Java 虚拟机的堆栈不会发生变化。这样，垃圾回收器便能够“安全”地执行可达性分析。

1. 安全点检测

安全点的选定既不能太少以至于让收集器等待时间过长，也不能太频繁以至于过分增大运行时的内存负荷。安全点位置的选取基本上是以“是否具有让程序长时间执行的特征”为标准进行选定的，典型的例子就是指令序列的复用，如方法调用、循环跳转等，所以只有具有这些功能的指令才会产生安全点。

对于解释执行来说，字节码与字节码之间皆可作为安全点。Java 虚拟机采取的做法是，当有安全点请求时，执行一条字节码便进行一次安全点检测。

执行即时编译器生成的机器码则比较复杂。由于这些代码直接运行在底层硬件之上，不受 Java 虚拟机掌控，因此在生成机器码时，即时编译器需要插入安全点检测避免机器码长时间没有安全点检测的情况。HotSpot 虚拟机的做法是在生成代码的方法出口以及非计数循环的循环回边处插入安全点检测。

2. 线程中断

对于安全点，另外一个需要考虑的问题是，如何在垃圾收集发生时让所有线程（这里其实不包括执行 JNI 调用的线程）都跑到最近的安全点，然后停顿下来。这里有两种方案可供选择：抢先式中断和主动式中断。

抢先式中断的思想是当垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上就恢复这条线程执行，让它一会再重新中断，直到跑到安全点上。现在几乎没有虚拟机的实现采用抢先式中断来暂停线程以响应 GC 事件。

主动式中断的思想是当垃圾收集需要中断线程时，不直接对线程操作，仅仅简单地设置一个标志位，各个线程执行时会不停地主动去轮询这个标志，一旦发现中断标志为 true 就自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他需要在 Java 堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象。

安全区域

使用安全点的设计似乎已经完美解决如何停顿用户线程，让虚拟机进入垃圾回收状态的问题了，但实际情况却并不一定。安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但是，当程序不执行的时候呢？

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

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

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

记忆集与卡表

前面讲到为解决对象跨代引用所带来的问题，垃圾收集器在新生代中建立了名为记忆集的数据结构，以避免把整个老年代加进 GC Roots 的扫描范围。但事实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集行为的垃圾收集器，如 G1、ZGC 收集器，都会面临相同的问题。因此这里详细讲解下记忆集的原理和实现方式。

记忆集（Remember Set）是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。在垃圾收集的场景中，收集器只需要通过记忆集判断出某一块非收集区域是否存在有指向收集区域的指针就可以了，并不需要了解这些跨代指针的全部细节。

目前最常用的是通过卡表（Card Table）的方式去实现记忆集。记忆集只是一种抽象的数据结构，而卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等。卡表将整个堆划分为一个个大小为 512 字节的卡，并维护了一个表用来存储每张卡的一个标识位。这个标识位代表对应的卡内是否可能存有指向新生代对象的引用。如果可能存在，那么我们就认为这张卡是脏的。

HotSpot 虚拟机通过一个字节数组实现了卡表，下面代码为对应卡表标记逻辑：

CARD_TABLE[this address >> 9] = 0;

字节数组 CARD_TABLE 的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称作卡页（Card Page）。HotSpot 中的卡页大小为 29，即 512 字节。

在下面示例中，如果卡表标识内存区域的起始地址是 0x0000 的话，那 CARD_TABLE 的第 0、1、2 号元素就分别对应了地址范围为 0x0000~0x01FF、0x0200~0x03FF、0x0400~0x05FF 的卡页内存块。

十六进制数 0x0200、0x0400 分别为十进制的 512、1024，这 3 个内存块为从 0 开始、512 字节容量的相邻区域。

一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为 1，称为这个元素变脏，没有则标识为 0。

在进行 Minor GC 的时候，我们便可以不用扫描整个老年代，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，然后把它们加入 GC Roots 中一并扫描。当完成所有脏卡的扫描之后，Java 虚拟机便会将所有脏卡的标识位清零。

写屏障

我们已经解决了如何使用记忆集来缩减 GC Roots 扫描范围的问题，但还没解决卡表元素如何维护的问题。当有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻。那如何在对象赋值的那一刻去更新维护卡表呢？

在 HotSpot 虚拟机里是通过写屏障（Write Barrier）来维护卡表状态的，注意不要和 volatile 中的内存屏障混淆。写屏障可以看作在虚拟机层面对“引用类型字段赋值”这个动作的 AOP 切面，在引用对象赋值时会产生一个环形通知供程序执行额外动作，即赋值的前后都在写屏障的覆盖范畴内。其中，赋值前的部分的写屏障叫作写前屏障，赋值后的部分的写屏障叫作写后屏障。

下面示例代码是更新卡表状态的简化逻辑：

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

写屏障需要尽可能地保持简洁。因为我们不希望在每条引用型实例变量的写指令后跟着一大串注入的指令。因此写屏障不会判断更新后的引用是否是指向新生代中的对象，而是每次只要对引用进行更新，虚拟机就会为所有赋值操作生成相应指令。不过这个开销与 Minor GC 时扫描整个老年代的代价相比还是低得多的。

伪共享问题：

除了写屏障的开销外，卡表在高并发场景下还面临着伪共享（False Sharing）问题。通常处理器的缓存行大小为 64 字节，而一个卡表元素占 1 字节，64 个卡表元素将共享同一个缓存行。这 64 个卡表元素对应的卡页总的内存为 32KB（64×512字节），也就是说如果不同线程更新的对象正好处于这 32KB 的内存区域内，就会导致更新卡表时正好写入同一个缓存行而影响性能。

为了避免伪共享问题，一种简单的解决方案是不采用无条件的写屏障，而是先检查卡表标记，只有当该卡表元素未被标记过时才将其标记为变脏，即将卡表更新的逻辑变为以下代码所示：

if (CARD_TABLE[this address >> 9] != 0) {
    CARD_TABLE[this address >> 9] == 0
}

在 JDK 7 之后，HotSpot 虚拟机增加了一个新的参数 -XX:+UseCondCardMark，用来决定是否开启卡表更新的条件判断。开启会增加一次额外判断的开销，但能够避免伪共享问题，两者各有性能损耗，是否打开要根据应用实际运行情况来进行测试权衡。

并发的可达性分析

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。

根节点枚举中，由于 GC Roots 比起整个 Java 堆中全部的对象毕竟还算是极少数，且在各种优化技巧（如 OopMap）的加持下，它带来的停顿已经是非常短暂且相对固定（不随堆容量而增长）的了。可从 GC Roots 再继续往下遍历对象图，这一步骤的停顿时间就必定会与 Java 堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长。

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

为了能解释清楚这个问题，我们引入三色标记作为工具来辅助推导，把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

白色：表示对象尚未被垃圾收集器访问过。在可达性分析刚开始时，所有对象都是白色的，若在分析结束后仍然是白色的对象，即代表不可达。

黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表安全存活的，如果有其他对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接指向白色对象。

灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过。

我们可以把可达性分析的扫描过程看作对象图上一股以灰色为波峰的波纹从黑向白推进的过程，如果用户线程此时是冻结的，只有收集器线程在工作，那不会有任何问题。但如果用户线程与收集器并发工作，即收集器在对象图上标记颜色，同时用户线程在修改引用关系，这样可能出现两种后果。一种是把原本消亡的对象错误标记为存活。另一种是把原本存活的对象错误标记为已消亡，而后者则是非常致命的问题。

对象消失问题的解决办法：

理论上，当且仅当以下两个条件同时满足时，才会产生对象消失的问题，即本应是黑色的对象被误标为白色：

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

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

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

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

以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。在 HotSpot 虚拟机中，增量更新和原始快照这两种解决方案都有实际应用。譬如，CMS 是基于增量更新来做并发标记的，而 G1 则采用原始快照的方式。

HotSpot 垃圾收集算法实现细节