HotSpot 的算法实现细节

lllllan ... 2022-3-17

JVM
深入理解Java虚拟机

About 10 min

转载声明

# 一、根节点枚举

迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的。在枚举根节点的期间，根节点集合的对象引用关系应该保持不变，这是枚举根节点应该保证的 一致性 。如果这点都不能满足，分析结果也就无法保证，因此垃圾手机过程必须停顿所有用户线程。

一致性

整个枚举期间执行子系统看起来就像被冻结在某个时间点上，不会出现分析过程中，根节点集合的对象引用关系还在不断变化的情况。如果这个都不能满足的花，分析结果的准确性也就无法保证。

准确式 GC 和 OopMap

保守式GC，不知道每个位置上的数据时什么类型，只能扫描整个新生代。

目前主流Java虚拟机都是使用准确式垃圾收集，即虚拟机知道内存中某个位置存储的数据是什么类型，在GC时，只需遍历引用类型即可，而不需要一个不漏地检查完所有执行上下文和全局的引用位置。

其用来维护哪些地方存有引用的数据结构就叫做 OopMap。在 HotSpot 中一旦类记载完成的时候，HotSpot 会将对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，在特定位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就可以直接获取这些信息了。

# 二、安全点

jvm大局观之内存管理篇: 理解jvm安全点,写出更高效的代码 - 知乎 (zhihu.com) (opens new window)

在OopMap的协助下，HotSpot可以快速准确地完成GC Roots枚举，但一个很现实的问题随之而来：可能导致引用关系变化，或者说导致OopMap内容变化的指令非常多，如果为每一条指令都生成对应的OopMap，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法忍受的高昂。

安全点

实际上HotSpot也的确没有为每条指令都生成OopMap，前面已经提到，只是在“特定的位置”记录了这些信息，这些位置被称为安全点（Safepoint）。

安全点位置选取的原则：

是否具有让程序长时间执行的特征。【长时间执行】的最明显特征就是指令序列的复用，例如方法调用、循环跳转、异常跳转等都属于指令序列服用，只有具有这些功能的指令才会产生安全点
如何在垃圾收集发生时让所有线程（不包括执行JNI调用的线程）都跑到最近的安全点。抢先式中断、主动式中断

两种中断

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

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

# 三、安全区域

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

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

安全区域

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

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

# 四、记忆集和卡表

记忆集

所有涉及部分区域收集（Partial GC）行为的垃圾收集器，都会面临对象跨代引用的问题。记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构

这种记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都相当高昂。而在垃圾收集的场景中，收集器只需要通过记忆集判断出某一块非收集区域是否存在有指向了收集区域的指针就可以了，并不需要了解这些跨代指针的全部细节。

字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的32位或64位，这个精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针。
对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针

卡表

卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等。

HotSpot 虚拟机中卡表就是一个字节数组，其中每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块称为卡页。一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为 1，称为这个元素变脏（Dirty），没有则标识为 0。

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

# 五、写屏障

我们已经解决了如何使用记忆集来缩减 GC Roots 扫描范围的问题，但还没有解决卡表元素如何维护的问题，例如它们何时变脏、谁来把它们变脏等。

何时变脏： 有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻
如何变脏： 通过写屏障技术维护卡表状态

写屏障

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

换句话就是 对一个对象引用进行写操作（即引用赋值）之前或之后附加执行的逻辑，相当于为引用赋值挂上的一小段钩子代码。

参考内存屏障

除了写屏障的开销外，卡表在高并发场景下还面临着【伪共享（False Sharing）】问题。伪共享是处理并发底层细节时一种经常需要考虑的问题

伪共享问题

伪共享（false sharing），并发编程无声的性能杀手 - cyfonly - 博客园 (cnblogs.com) (opens new window)

现代中央处理器的缓存系统中是以缓存行（Cache Line）为单位存储的，当多线程修改互相独立的变量时，如果这些变量恰好共享同一个缓存行，就会彼此影响（写回、无效化或者同步）而导致性能降低，这就是伪共享问题

为了避免伪共享问题：

一种简单的解决方案是 不采用无条件的写屏障，而是先检查卡表标记，只有当该卡表元素未被标记过时才将其标记为变脏。

个人理解，只有必要将 “未变脏” 的卡页变为 “脏”，而没必要记录 “脏” 了多少，从而减少修改卡表的次数。
在JDK 7之后，HotSpot虚拟机增加了一个新的参数 -XX：+UseCondCardMark，用来决定是否开启卡表更新的条件判断；开启会增加一次额外判断的开销，但能够避免伪共享问。

# 六、并发的可达性分析

可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全程冻结用户线程的运行。从 GC Roots 再继续往下遍历对象图，这一步骤的停顿时间就必定会与 Java 堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长。