java虚拟机--垃圾回收（二）HotSpot的算法细节实现

一、根节点枚举
上一篇文章已经介绍过GC Roots了，那么如何在GC Roots找到引用链的呢

    我们以可达性分析算法中从GC Roots集合找引用链这个操作作为介绍虚拟机高效实现的第一个例子。固定可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中，尽管目标明确，但查找过程要做到高效并非一件容易的事情，现在Java应 用越做越庞大，光是方法区的大小就常有数百上千兆，里面的类、常量等更是恒河沙数，若要逐个检查以这里为起源的引用肯定得消耗不少时间。
    迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，因此毫无疑问根节点枚举与之前提及的整理内存碎片一样会面临相似的“Stop The World”的困扰

由于目前主流Java虚拟机使用的都是准确式垃圾收集，所以当用户线程停顿下来之后，其实并不需要一个不漏地检查完所有 执行上下文和全局的引用位置，虚拟机应当是有办法直接得到哪些地方存放着对象引用的。在HotSpot 的解决方案里，是使用一组称为OopMap的数据结构来达到这个目的。一旦类加载动作完成的时候， HotSpot就会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样收集器在扫描时就可以直接得知这些信 息了，并不需要真正一个不漏地从方法区等GC Roots开始查找
二、安全点
1.概述
在OopMap的协助下，HotSpot可以快速准确地完成GC Roots枚举，但一个很现实的问题随之而来：可能导致引用关系变化，或者说导致OopMap内容变化的指令非常多，如果为每一条指令都生成 对应的OopMap，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法 忍受的高昂。
实际上HotSpot也的确没有为每条指令都生成OopMap，前面已经提到，只是在“特定的位置”记录了这些信息，这些位置被称为安全点（Safepoint）。有了安全点的设定，也就决定了用户程序执行时 并非在代码指令流的任意位置都能够停顿下来开始垃圾收集，而是强制要求必须执行到达安全点后才 能够暂停。
2.安全点设置的原则
GC的目的是帮助我们回收不再使用的内存，在多线程环境下这种回收将会变得非常复杂，要安全地回收需要满足一下两个条件：

1.堆内存的变化是受控制的，最好所有的线程全部停止。

2.堆中的对象是已知的，不存在不再使用的对象很难找到或者找不到即堆中的对象状态都是可知的。

3.抢占式、主动式
对于安全点，另外一个需要考虑的问题是，如何在垃圾收集发生时让所有线程（这里其实不包括
执行JNI调用的线程）都跑到最近的安全点，然后停顿下来。这里有两种方案可供选择：抢先式中断 （Preemptive Suspension）和主动式中断（Voluntary Suspension），
（1）抢先式中断
不需要线程的执行代码 主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，让它一会再重新中断，直到跑到安全点上。现在几乎没有虚 拟机实现采用抢先式中断来暂停线程响应GC事件。

（2）主动式中断
思想是当垃圾收集需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他 需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象
4.安全点设置位置
HostSop虚拟机采用的是主动式使线程中断。那么应该在什么地方设置全局变量呢？显然不能随意设置全局变量，进入安全点有个默认策略那就是：“避免程序长时间运行而不进入Safe Point”，程序要GC了必须要等线程进入安全点，如果线程长时间不进入安全点这样就比较糟糕了，因此安全点主要咋以下位置设置：

（1）循环的末尾

（2）方法返回前

（3）调用方法的call之后

（4）抛出异常的位置

三.安全区域
安全点完美的解决了如何进入GC问题，实际情况可能比这个更复杂，但是如果程序长时间不执行，比如线程调用的sleep方法，这时候程序无法响应JVM中断请求这时候线程无法到达安全点，显然JVM也不可能等待程序唤醒，这时候就需要安全区域了。

安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中任
意地方开始垃圾收集都是安全的。我们也可以把安全区域看作被扩展拉伸了的安全点。
当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域，那样当这段时
间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。当线程要离开安全 区域时，它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的 阶段），如果完成了，那线程就当作没事发生过，继续执行；否则它就必须一直等待，直到收到可以 离开安全区域的信号为止。
四、记忆集与卡表
上篇文章提到过部分垃圾回收器是分代回收的，既然将java堆分成不同的代那么必然会存在跨代引用的问题所以垃圾收集器在新生代中建 立了名为记忆集（Remembered Set）的数据结构，用以避免把整个老年代加进GC Roots扫描范围。事 实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集（Partial GC）行为的

垃圾收集器，典型的如G1、ZGC和Shenandoah收集器，都会面临相同的问题，因此我们有必要进一步理清记忆集的原理和实现方式
1.记忆集
记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。如果我们不考虑
效率和成本的话，最简单的实现可以用非收集区域中所有含跨代引用的对象数组来实现这个数据结
构
Class RememberedSet {
Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE];
}
这种记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都相当高昂。而在垃圾
收集的场景中，收集器只需要通过记忆集判断出某一块非收集区域是否存在有指向了收集区域的指针 就可以了，并不需要了解这些跨代指针的全部细节。那设计者在实现记忆集的时候，便可以选择更为 粗犷的记录粒度来节省记忆集的存储和维护成本，下面列举了一些可供选择（当然也可以选择这个范围以外的）的记录精度：
（1）字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的32位或64位，这个精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针。
（2）对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
（3）卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针
2.卡表
上面说到的第三种“卡精度”所指的是用一种称为“卡表”（Card Table）的方式去实现记忆集，这也是 目前最常用的一种记忆集实现形式，一些资料中甚至直接把它和记忆集混为一谈。前面定义中提到记忆集其实是一种“抽象”的数据结构，抽象的意思是只定义了记忆集的行为意图，并没有定义其行为的 具体实现。卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等。
卡表最简单的形式可以只是一个字节数组，而HotSpot虚拟机确实也是这样做的。以下这行代
码是HotSpot默认的卡表标记逻辑
CARD_TABLE [this address >> 9] = 0;
字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个
内存块被称作“卡页”（Card Page）。一般来说，卡页大小都是以2的N次幂的字节数，通过上面代码可 以看出HotSpot中使用的卡页是2的9次幂，即512字节（地址右移9位，相当于用地址除以512）
一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代
指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏（Dirty），没有则标识为0。在垃 圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。
五、写屏障
1.概述
我们已经解决了如何使用记忆集来缩减GC Roots扫描范围的问题，但还没有解决卡表元素如何维
护的问题，例如它们何时变脏、谁来把它们变脏等。所以HotSpot通过写屏障（write barrier）来维护卡表
“写屏障”这个词虽然看起来高深，但是它的含义却相当naive——就是对一个对象引用进行写操作（即引用赋值）之前或之后附加执行的逻辑，相当于为引用赋值前后加了一层aop,这样就可以维护卡表了。
2.伪共享
卡表在高并发场景下还面临着“伪共享”（False Sharing）问题。伪共享是处
理并发底层细节时一种经常需要考虑的问题，现代中央处理器的缓存系统中是以缓存行（Cache Line） 为单位存储的，当多线程修改互相独立的变量时，如果这些变量恰好共享同一个缓存行，就会彼此影响（写回、无效化或者同步）而导致性能降低，这就是伪共享问题。
六、并发的可达性分析-三色标记法
1.概述
前面文章中曾经提到了当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象 是否存活的，可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析， 这意味着必须全程冻结用户线程的运行。在根节点枚举这个步骤中，由于GC Roots相比起整个Java堆中全部的对象毕竟还算是极少数，且在各种优化技巧（如OopMap）的加持下，它带来 的停顿已经是非常短暂且相对固定（不随堆容量而增长）的了。

可从GC Roots再继续往下遍历对象 这一步骤的停顿时间就必定会与Java堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长，这听起来是理所当然的事情。 而三色标记法可以优化这部分的耗时

2.垃圾回收的原则
（1）可以把是垃圾的遗漏

（2）不可以把不是垃圾的回收

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

中间状态：

最终状态：

由图所示是关于可达性分析的扫描过程，其实就是黑向白推进的过程，灰色收集过程中的中间状态，最终状态是只有黑和白，白色是可以被回收的黑色是不可被回收的，如果用户线程此时是冻结的，只有收集器线程在工作，那不会有任何问题。但如果用户线程与收集器是并发工作呢？
4.产生不是垃圾的回收的条件

如图所示情况在收集过程中断开了全部引用G的灰色节点引用，并且建立了黑色节点D的引用，此时因为黑色表示子节点全部被收集了所以不会再扫描，而与全部灰色节点的引用全部断开了所以该白色节点永远也无法被扫描到，这就导致最终态该白色对象虽然存在引用不是垃圾但是还是被回收掉，综上所诉把不是垃圾回收掉必须满足以下两个条件

（1）在收集过程中赋值器插入了一条或多条从黑色对象到白色对象的新引用

（2）在收集过程中赋值器删除了全部从灰色对象到该白色对象的直接或间接引用

这两个条件只需破坏一个就可以避免，所以。由此分别 产生了两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB）。

5.增量更新
增量更新要破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新
插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新扫描一次。这可以简化理解为，黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象 了。
6.原始快照
原始快照要破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删
除的引用记录下来，在并发扫描结束之后，再将这些记录过的引用关系中的灰色对象为根，重新扫 一次。这也可以简化理解为，无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来 进行搜索。
7.总结
以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。在 HotSpot虚拟机中，增量更新和原始快照这两种解决方案都有实际应用，譬如，CMS是基于增量更新来做并发标记的，G1、Shenandoah则是用原始快照来实现。
————————————————