HotSpot虚拟机的算法细节实现

下面来阅读总结下HotSpot虚拟机的一些实现细节。

根节点枚举

以可达性分析算法中从GC Roots集合找引用链这个操作来作为介绍虚拟机高效实现的例子。迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的。现在可达性分析算法耗时最长的查找引用链的过程已经可以做到与用户线程一起并发，但根节点枚举始终还是必须在一个能保障一致性的快照中才得以进行——这里“一致性“的意思是整个枚举期间执行子系统看起来就像被冻结在某个时间点上，不会出现分析过程中，根节点的集合的对象引用关系还在不断变化的情况，若这点不能满足的话，分析结果准确性也就不能保证。

由于目前主流Java虚拟机使用的都是准确式垃圾收集，所以当用户线程停顿下来以后，其实并不需要全部检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得到哪些地方存放着对象引用的。在HotSpot的解决方案里，是使用一组称为OopMap的数据结构来达到这个目的。一旦完成类加载，得到类似的哈希码来找到其位置。

普通对象指针（Ordinary Object Pointer， OOP）

安全点

在快速准确完成GC Roots枚举后，其实HotSpot也的确没有为每条指令都生成OopMap，为解决引用关系变化的问题，在"特定的位置"记录了信息，这些位置被称为安全点（Safepoint）。有了安全点的设定，也就决定了用户线程在执行时并非在代码指令流的任意位置都能够够停顿下来开始垃圾收集，而是强制要求必须执行到达安全点后才能够暂停。因此 ，安全点的选择既不能太少以至于让收集器等待时间过长，也不能太过频繁以至于过分增大运行时的内存负荷。安全点位置的选取基本上是以“是否具有让程序长时间执行的特征”为标准进行选定的。“长时间执行”的最明显特征就是指令序列的复用，例如方法调用、循环跳转、异常跳转等都属于指令序列的复用，所以只有具有这些功能的指令才会产生安全点。

对于安全点，另一个需要考虑的问题就是如何在垃圾收集发生时让所有线程都跑到最近的安全点，然后停顿下来。有两种方案可供选择：

• 抢先式中断（Preemptive Suspension）

抢先式中断不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，让其运行一会再重新中断，直到跑到安全点上。但现在几乎没有虚拟机实现采用抢先式中断来暂停线程响应GC事件。

• 主动式中断（Voluntary Suspension）

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

安全区域

安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但是，当程序不执行即没有分配处理器时间时，典型场景即用户线程处于sleep状态或者blocked状态，这时线程不能走到安全点，虚拟机也不可能持续等待线程重新被激活分配处理器时间。对于这种情况，就必须引入安全区域（Safe Region）来解决。

安全区域是指能够保证在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中任意地方开始垃圾收集都是安全的。

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

记忆集与卡表

为解决对象跨代引用所带来的问题，垃圾收集器在新生代中建立了名为记忆集（Remembered Set）的数据结构，用以避免把整个老年代加入GC Roots的扫描范围。

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

在实现记忆集的时候，可以选用更为粗犷的记忆粒度来节省记忆集的存储和维护成本，下面列举了一些可供选择的记忆精度：

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

卡精度指的是用一种称为“卡表”（Card Table）的方式去实现记忆集，这也是目前最常用的一种记忆集的实现形式。它定义了记忆集的记录精度，与堆内存的映射关系等。

卡表最简单的形式可以只是一个字节数组，而HotSpot虚拟机确实也是这样做的。下面这段代码是HotSpot默认的卡表标记逻辑。

CARD_TABLE [this address >> 9] = 0;

字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称作“卡页”（Card Page）。一般来说，卡页大小都是以2的N次幂的字节数，通过上面代码可以看出HotSpot中使用的卡页是2的9次幂。

一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素值标为1，称为这个元素变脏，没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。

写屏障

在HotSpot虚拟机里是通过写屏障（Write Barrier）技术维护卡表状态的。写屏障可以看做在虚拟机层面对“引用类型子段赋值”这个动作的AOP切面，在引用赋值对象时会产生一个环形通知，供程序执行额外的动作，也就是说赋值的前后都在写屏障的覆盖范畴内。在赋值前的部分写屏障叫做写前屏障（Pre-Write Barrier），在赋值后的则叫做写后屏障（Post-Write Barrier）。

AOP为Aspect Oriented Programming的缩写，意为面向切面编程，通过预编译方式和运行期动态代理实现程序功能的统一的一种技术。

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

除了写屏障的开销外，卡表在高并发场景下还面临着“伪共享”（False Sharing）问题。伪共享是处理并发底层细节时一种经常需要考虑的问题，现代中央处理器的缓存系统中是以缓存行（Cache Line）为单位存储的，当多线程修改相互独立的变量时，如果这些变量恰好共享同一个缓存行，就会彼此影响（写回、无效化或者同步）而导致性能降低，这就是伪共享问题。

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

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

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

并发的可达性分析

当前主流语言的垃圾收集器都是以可达性分析算法来判定对象是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。在根节点枚举这个步骤中，由于GC Roots相比整个Java堆中的全部对象毕竟来说还是极少数，且在各种优化技巧的加持下，它带来的停顿已经是非常短暂且相对固定的了。

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

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

若用户线程与收集器是并发工作的，收集器在对象图上标记颜色，同时用户线程在修改引用关系——即修改对象图的结构，这样可能出现两种后果，一种是把原本消亡的对象错误标记为存活，这种情况可容忍且可在下次收集清理掉就好；另一种是把原本存活的对象错误标记为已消亡，程序肯定会因此而发生错误。下图演示了这样的致命错误是如何产生的

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

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

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

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

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

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

以上介绍的HotSpot虚拟机如何发起垃圾回收、如何加速内存回收，以及如何保证回收正确性问题，但是虚拟机如何具体地进行垃圾回收动作仍然未涉及。因为内存回收如何进行是由虚拟机采用哪一款垃圾收集器所决定的，而通常虚拟机中往往有多种垃圾收集器。

---

参考《深入理解Java虚拟机》周志明著