高亮的杂货铺

JVM从0到1-HotSpot垃圾收集算法细节,根节点枚举和可达性分析

2020-03-15 · 7 min read
JVM Java

根节点枚举

可达性分析需要从GC Roots集合找引用链。固定可以作为GC Roots的节点主要是全局性的引用、例如常量和非静态属性,以及执行上下文,即栈帧的本地变量表中。

迄今为止,所有的收集器在根节点枚举这一个步骤都是必须要暂停用户线程的,因此毫无疑问根节点枚举也会有“Stop The World”的困扰。 现在可达性分析算法在查找引用链这个过程已经可以做到和用户线程并发了,但是枚举跟节点这个步骤不行。 因为枚举根节点必须在一个能保障一致性的快照中进行的。 这里一致性指的是整个枚举期间执行子系统看起来就像是被冻结到了某个时间点了,不会出现在分析过程中,根节点上的对象引用关系还在不断变化的情况。 否则将会无法保证分析结果的准确性。

显然,直接进行遍历是消耗极高的行为,必须进行优化。

目前主流的Java虚拟机都是使用的准确式垃圾收集,所以当线程停顿后,并不需要检查上下文和全局中的所有引用位置,虚拟机应该有办法能够直接知道哪里存放着对象的引用。 在HotSpot里,是用一组称为OopMap的数据结构来达到这个目的的,一单类加载动作完成的时候,HotSpot就会把对象内什么偏移量上是什么数据类型计算出来。 这样垃圾收集器在扫描时就可以直接得知这些信息了,并不需要真正的一个不漏的从方法区GC Roots开始查找。

安全点

何时生成OopMap? 显然不能每条指令都生成,这回导致大量的额外存储空间。 实际上HotSpot只会在特定的位置生成OopMap,这种位置被称为安全点。一般安全点位置的选取基本上是遵循“是否能够让程序长时间执行的特征”为标准的,因此,一般会在方法调用、循环跳转、异常跳转等指令时,才会产生安全点。

安全点的定义有了,还有一个问题就是如何在垃圾回收时,让所有的线程都在最近的的安全点停下来。
目前主要采用两种方案,抢先式中断和主动式终端,抢先式终端不需要线程的执行代码进行配合,在垃圾回收时,系统首先让所有的用户线程终端,然后如果发现有线程终端点不在安全点上,就恢复这个线程,让他一会再重新终端,直到跑到安全点上,目前基本没有虚拟机采用抢先式中段来暂停线程响应GC事件。

主动式终端是在垃圾回收需要中断线程的时候,不对线程操作,而是仅仅设置一个标志位,各个线程执行的时候要不断的轮询这个标志位,一但发现中断标志为真,那就自己在最近的安全点上主动挂起。

因为轮询需要频繁出现,因此必须足够高效,HotSpot通过内存保护陷阱的方式,将操作精简到了一条汇编指令。

安全区域

如果一个线程在垃圾回收发生时,正处于sleep或者阻塞状态,就必须要引入安全区域来解决这种情况。
安全区域是指的能确保在某一段代码片段中,引用关系不会发生变化。 因此在这个区域内任意地方开始垃圾收集都是安全的。

当用户线程执行到安全区域里的代码时,首先会标识自己已经进入了安全区域,这时候垃圾收集就不需要关心这个线程了,当线程要离开这个区域的时候,必须要检查虚拟机是否已经完成了根节点枚举。如果完成了,就继续执行,否则,就要阻塞知道收到离开安全区域的信号。

记忆集与卡表

为了解决跨代引用的问题,垃圾收集器在新生代中建立了记忆集的结构,以避免整个老年代都被加进 GC Roots的扫描范围。 事实上,并不仅是新生代和老年代之间才存在跨代引用,所有涉及到分区域收集的收集器,都会有相同问题。

记忆集通常不会直接记录所有存在跨代引用的对象,而是通过卡表的方式,更粗粒度的记录哪一个范围的非收集区域存在指向收集区域的指针就可以了。

卡表就是一种常见的记忆集实现形式, 卡表的每一项元素都对应着内存区域中一块特定大小的内存块,这个内存块被称为卡页,一把来说,卡页大小都是2的N此幂。 卡表一般都设计成一个字节数组。

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

写屏障

通过上面的方式,已经解决了GC Roots扫描范围的问题。 但是卡表谁来维护呢?
HotSpot虚拟机是通过写屏障(Write Barrier)技术来维护卡表状态的。 写屏障可以看作是虚拟机层面堆引用类型字段赋值这个操作的AOP切面,在引用对象赋值时会产生一个环形通知,供程序执行二外的动作。

并发的可达性分析

并发的可达性分析可能会导致两个问题,一种是把原本消亡的对象错误标记为存活,这不是好事,但其实是可以容忍的,只不过产生了一点逃过本次收集的浮动垃圾而已,下次收集清理掉就好。另一种是把原本存活的对象错误标记为已消亡,这就是非常致命的后果了,程序肯定会因此发生错误。

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

  • 赋值器插入了一条或多条从黑色对象到白色对象的新引用;
  • ·赋值器删除了全部从灰色对象到该白色对象的直接或间接引用。
    为了解决这种问题, 只要破坏这两个条件中的任意一个即可,因而出现了两种解决方案,增量更新和原始快照。

增量更新主要是破坏第一个条件,新增引用时,将引用记录下来,当并发扫描结束后,再将这些记录过的引用为根,重新扫描一次。

原始快照主要是破坏第二个条件,当灰色对象要删除指向白色对象的引用的时候,就将这个要删除的引用记录下来,在并发扫描结束后,再重新将这些记录过的引用关系为跟,重新扫描一遍。 即手动恢复到开始扫描那一刻的快照图进行搜索。

CMS是基于增量跟新的,G1和Shenandoah是基于原始快照的。