jvm学习笔记6--HotSpot的算法细节实现

前面学习了怎么判别要回收的对象，以及垃圾回收的一些方式、标记-清除算法、标记-复制算法、标记-整理算法。现在看看我们每天使用的HotSpot虚拟机中算法的细节实现。

根节点枚举

前面已经学习到可作为GC Roots的一些变量或者属性，但是实际上在查找过程中要做到高效也是很困难的，要逐个检查以这里为起源的引用肯定要消耗不少时间。

而且迄今为止，所有收集器在枚举根节点这步骤的时候都是需要暂停所有的用户线程的，这时就会面临和前面整理内存碎片算法中”Stop The World“同样的问题。

目前主流的jvm使用的都是准确式垃圾回收，所以在用户线程停顿的时候，不用一个不漏的检查所有的上下文和全局引用为止，虚拟机应该是有办法知道哪儿存放着对象引用的。在HotSpot中，是使用一组OopMap的数据结构达到这一目标的。一旦类加载完成，会在特定的为止记录下来栈里或者寄存器里哪些位置是引用。这样收集器在扫描的时候就可以直接拿到了，不用真正一个不漏的从方法区等GC Roots查找。

安全点

在OopMap的协助下，HotSpot可以快速的完成GC Roots枚举，但是有一个问题随之而来就是引用的变化，即导致OopMap中内容变化的指令非常多，如果给每一个指令都生成一个OopMap，就会有大量的额外存储空间，空间成本会越来越大。

这时候HotSpot就很机智了，没有上面说的那么愚蠢了。HotSpot只是在一个特定位置记录这些信息，这些位置被称为安全点（SafePoint）

安全点的选取方式：是否能让程序长时间执行的特征为标准，比如：方法调用、循环跳转、异常跳转等都属于长时间执行。

在实际的工作中，如果在垃圾收集发生时，所有的工作线程都跑到最近的一个安全点，然后停顿下来。2种方案：

抢先式中断

在垃圾收集发生时，系统首先把所有的线程全部中断，如果发现用户线程中断的地方不在安全点，就恢复这条线程，让他跑到最近的安全点。
现在几乎没有虚拟机采用这种方式。

主动式中断

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

安全区域

使用安全点的问题可以很好的解决如何停顿用户线程，但是只能保证程序在运行时候，在不太长的时间内遇到一个安全点。如果程序长时间处于”不运行“的时候，即程序处于"sleep"或者”blocked“的状态，这时候线程就无法响应虚拟机的中断请求，不能走到安全的地方中断自己，虚拟机也可能等待线程重新被激活分配处理器时间。对于这种情况，就需要引入安全区域解决。

安全区域是指能确保在某一块代码区域中，引用关系不会发生变化。因此，在这个区域中的任何地方开始垃圾收集都是安全的。可以看做是一个扩展的安全点。

当用户线程执行到安全区域的时候，首先会标识自己进入到了安全区域，这样虚拟机在开始垃圾收集的时候就不用考虑这些已声明自己再安全区域的线程了。当线程要离开安全区域的时候，要先检查下时候已虚拟机是否完成了根节点枚举，如果完成了，就当什么事情都没有发生过；如果没有完成，就待在安全区域，知道收到可以离开安全区域的信号为止。

记忆集和卡表

在前面介绍过的分代收集理论中，为了解决对象跨代引用带来的问题，垃圾收集器在新生代建立了一个记忆集（remrmberrd set）的数据结构，用来避免把整个老年代加紧GC Roots的扫描范围中。

记忆集本身是一种用于记录从非收集区指向收集区的指针的集合的抽象数据结构，不考虑实现成本的话，最简单的实现是用非收集区的所有含跨代引用的对象数组来实现。但是这种方式在空间占用还是维护成本上都有高昂的代价，在实际的垃圾收集过程中，收集器只需要通过记忆集判断出哪一块非收集区域是否存在指向收集区域的指针就可以了，并不需要全部了解所有的跨代指针。列举几种可选择的记忆精度

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

其中第3种就是我们说的卡表的方式实现记忆集，也是目前最常用的方式。卡表和记忆集的关系，可以理解为java中hashmap和map的关系，卡表是记忆集的一种具体实现方式

卡表最简单的实现就是一个字节数组，HotSpot中就是这么实现的。

这个字节数据中每一个元素对应一块内存区域，这块内存被称为卡页，通常一个卡页中包含很多对象，只要卡页中有一个或者多个对象存在跨代引用，就将卡表对应元素的值标记为1，称为该元素变脏，没有标识默认是0。在垃圾收集发生时，只要筛选出来标识为1的元素，就能找到哪些内存区域中包含着跨代指针，将对应的内存区域加入到GC Roots中一并扫描。

写屏障

上面提到了卡表的作用，但是卡表在实际的运行场景中，是怎么更新卡表呢？我们知道，卡表的更新（变脏）发生在引用类型赋值的那一刻。那怎么保证在对象赋值的那一刻去更新维护卡表呢？HotSpot是通过写屏障技术维护卡表状态的。

写屏障其实就是一个类似AOP切面的操作，在引用对象赋值是产生一个环形通知，供程序做额外的动作。也就是说在赋值前后都是在写屏障的覆盖范畴之内。

写屏障分为写前屏障和写后屏障，在G1收集器出来之前，其他的收集器都是采用的写后屏障。

应用写屏障后，每次引用的更新，都会有对应的开销，不过这个开销和GC扫描整个老年代的代价相比小很多。
除了写屏障的开销，卡表在高并发的场景下，也会有”伪共享“的问题。为了避免伪共享的问题，一种解决办法是不采用无条件的写屏障，而是先检查卡表的标记，只有当卡表该元素未被标记的时候才将其标记为变脏。

并发的可达性分析

之前有提到过的可达性分析算法的要求是：全过程基于一个能保证一致性的快照中才能够进行分析

标记阶段是所有追踪式垃圾收集器的共同特征。如果这个阶段会随着堆的增大而等比例的增大停顿时间，其影响会波及到几乎所有的垃圾收集器。同时如果这个阶段能削减停顿时间的话，收益也是系统性的。

想要解决或者降低用户线程的停顿时间，就需要搞清楚为什么必须在一个能保障一致性的快照上进行对象图的遍历？为了解释这个问题，我们引入三色标记法：

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

在可达性分析的过程中，我们可以想象下，如果此时的用户线程是冻结的，只有收集器在工作，那不会有任何的问题。但如果用户线程和收集器是并发工作呢？收集器在对象图上标记颜色，同时工作线程在修改引用关系（修改对象图结构），这样会出现两种后果：一种是把原本消亡的对象标记为存活，这种可以容忍，下次回收这部分残余垃圾即可；另一种就是把存活的对象标记为已消亡，这种就致命了，程序肯定会发生错误。

如下图所示：

理论证明：只有发生以下2种条件同时满足时，才会产生”对象消失“的问题：

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

因此，要解决并发扫描时候对象消失的问题，只要破坏上面两个条件的其中一个即可。由此产生两种方案：增量更新和原始快照

增量更新

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

原始快照

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

以上无论是增量更新还是原始快照，虚拟机的操作记录都是通过写屏障实现的。
在HotSpot中，CMS是基于增量更新来做并发标记的；G1是用原始快照来做实现的。

本文地址：https://blog.csdn.net/csa121/article/details/106653392