前言

这一节来专门讨论一下HotSpot的算法的细节内容，内容说难也不难，说容易也确实不容易，有很多要理解的内容，个人在写这次文章的时候，有了更深的理解。

思维导图

如果懒得看文字，这里整理了一份思维导图帮助理解：

地址：www.mubucm.com/doc/1qTH77X…

概述

1. 可达性算法的大致内容和简述，以及JAVA固定GC ROOT的判定条件
2. 根节点枚举的实现细节，讲述什么事安全点和安全区域，以及他们的实际作用
3. 记忆集和卡集，一个是抽象一个是具体实现，在内部通过写屏障来维持引用关系的改动，介绍关于伪共享问题的解决方案
4. 并发可达性分析当中的三色标记是一个高频“考点”，以及Hotspot是如何应对对象消失问题的。

可达性算法

在介绍具体的内容之前，这里先补充一下基础内容：什么是可达性算法呢？简单来讲本质就是判断对象是否已死？一般实现的方式有下面这几种：

引用计数法

实现的方式和原理十分简单，同样也十分的高效，就是当为每一个对象绑定一个引用计数器，当对象存活，则引用计数器+1，引用失效，则计数器-1，虽然这个计数器要消耗一定的空间，但是确实是效率十分高的方式。当然他的缺点也十分明显，如果存在 循环引用，会导致对象永远不能判定为死亡。

循环引用：A引用B，B引用C，C引用D，D引用A

JAVA固定作为GC Root的判定条件

这里单纯作为笔记进行记录：

• 虚拟机栈引用的对象
  
• 方法区的静态属性引用对象，也就是static对象属性
  
• 方法区的常量引用，比如final引用的静态常量
  
• 本地方法栈的JNI，即Native方法引用对象
  
• 虚拟机内部的，基本类型对应的Class对象，常驻异常对象Null...等
  
• 同步锁（Syncronized）持有对象

根节点枚举

介绍

在可达性算法当中是通过GC ROOT的引用找到存活对象的方式，在现代的收集器基本可以做到和用户线程一起并发执行的程度，但是根节点枚举要保证某个时间点的“快照”，这也意味着根节点枚举需要暂停用户线程。

OopMap数据结构

在HotSpot中使用的是OopMap的结构，用于存储对象的类型，或者存储特定位置记录栈里面的寄存器哪些位置是引用，垃圾收集器扫描的时候就可以直接从对应的位置开始，不需要大范围的扫描动作。

这种结构会存在哪些问题？

这里可以看到，如果每一次对象的读取变化，都需要往OopMap里面存储内容，会导致OopMap的内容不断臃肿扩大，垃圾收集器的扫描成本会变得非常的昂贵。

为了应对这一类问题，HotSpot引入了“安全点这一机制进行处理”

安全点

OopMap不会在任意的位置都收集相关的指令，而是使用一个安全点的东西，这个安全点用通俗的话理解就是高速上的“收费点”，而设置安全点的条件是：是否具备程序长时间运行特征。

安全点有什么用？

毫无疑问，安全点是为了减轻OopMap存储结构的压力，同时保证垃圾回收的时候不需要扫描过多的GC ROOT。

缺点：这也决定了JVM虚拟机不能在任意的位置进行垃圾收集，而是要进入预先设定的“收费站”进行垃圾回收

如何触发安全点?

实现方式有两种：抢断式中断和主动式中断

需要注意的是现代已经没有虚拟机使用“抢先式中断”暂停线程来响应GC事件，也就意味着垃圾收集的行为都是虚拟机主动执行的，而不是通过争抢的方式处理。

安全点采用主动式中断，当垃圾收集器需要中断线程，会预先设置标志，并且各个线程会轮询标志位，一旦到达安全点附近就中断挂起（有点像检查站通知检查）为了保证运行的高效性，JVM将使用 内存保护陷阱的方式进行自陷中断，并且这条汇编指令精简为一条，可以大大提高轮询的效率。当线程收到自陷信号，就自然会触发线程中断了。

但是这里是存在问题的，如果线程本身存在阻塞等待，或者睡眠的情况下，安全点不可能一直等待线程中断，所以这里又引入了安全区域的概念

安全区域

安全区域的主要作用是确保安全点一段的时间内，引用的关系不发生改变，为了完成判断，他做了下面的事情：

• 判断当前线程是否进入了安全区域，如果进入了进行下面的判断

• 如果没有完成根节点枚举，则需要等待完成根节点枚举才能放行
• 如果已经完成根节点枚举，则会直接放行线程。

这里你可以想象在高速上等待出站，在这个区间内你要完成节点的根枚举操作才准许放行

记忆集与卡表

在了解这两个名词之前，我们需要记住 他们的目的是解决对象跨代引用的问题，在传统的分代系统中，存在老年代引用新生代之间的相互引用，那么JVM是如何判断哪些对象引用是失效，哪些对象引用需要存活保留呢？

记忆集(RememberedSet)

首先来看下**记忆集（RememberedSet）**是什么东西，在源代码的结构中他被声明为一个Object[]的数组结构，可以看到维护这种结构的代价是十分高昂的，所以为了节省记忆集的维护成本，存在如下的解决方案：

• 字长精度：精确到机器字长（处理器的寻址位数）
• 对象精度：顾名思义，精确到一个对象
• 卡精度：精确到一块内存区域，实现最简单的方式是一个字节数组

卡表

注意卡表是记忆集的一种实现方式，切忌和记忆集混为一谈，他们的关系和方法区以及永久代或者元空间的关系类似，是一种 抽象与实现的关系。

既然卡精度是针对一块内存区域，而JVM刚好又是采用了固定分代来完成垃圾回收的，所以毫无疑问使用的是卡精度来实现。

HotSpot使用的卡精度实现恰好也是使用一个字节数组来完成，卡页是2个N次幂数，最终使用的是2的9次方也就是512长度的字节数组来构建一个卡表。

如何操作？

HotSpot检测到对象存在跨代指针的时候，就会把数组的标志为1，没有就会标志位0，这个过程称为**“变脏”**，如果垃圾收集器开启并且扫描到当前的元素变脏，聚会放入到GC ROOT当中进行扫描。

写屏障

后续的内容，请在心里记住如下的问题：

1. 卡表如何维护？
2. 写屏障的伪共享问题
3. 谁来让元素变脏
4. 什么是写屏障
5. 如何维护整个卡表

定义：

我们知道了卡表如何定义，并且如何进行判断的，但是我们还不清楚卡表是如何进行维护的，那么什么是写屏障呢？写屏障可以认为是虚拟机层面对于“引用字段类型”的AOP的切面，写屏障还分为写前屏障和写后屏障。这里后续在进行讨论。

作用：

写屏障的作用是：维护卡表以及让卡表变脏，并且把维护卡表的操作放置到每一次赋值操作当中。

那么他是如何做到的呢，我们上一小节讲了HotSpot通过卡表变脏实现跨代引用和GC ROOT的判断。那么写屏障的作用就是在赋值的操作之前完成卡表的维护。

总结：

1. 卡表如何维护？使用写屏障进行维护
2. 谁来让元素变脏？在写屏障中通过AOP的切面在赋值操作中通过指令完成
3. 什么是写屏障？赋值操作的AOP切面
4. 如何维护整个卡表？OopMap和写屏障

这里肯定会有疑问，在赋值操作之前加入写屏障会不会有性能问题？

JVM设计团队是肯定考虑过这个问题的，最终的结果是虽然要消耗一定的赋值操作效率和性能，但是和频繁的Minor GC相比代价还是要小很多的。

写前和写后屏障是什么？

其实就是在赋值操作的AOP切面的前面或者后面操作，也就是通常AOP环绕前面的前置操作和后置操作，伪代码如下：

doSomethingFront(); //写前屏障
proxy.proxy();
doSomethingAfter(); //写后屏障
复制代码

另外再提一点，CMS使用了写后屏障，而G1既使用了写前屏障，又使用了写后屏障。

伪共享问题

什么是伪共享？在处理底层并发的时候需要考虑的问题，由于现代处理器因为缓存等问题，指令其实是打乱之后执行的，如果多个变量共享一个缓存行，他们就会彼此之间发生影响。

解决办法：

解决办法比较简单的一种是 检查卡表标记，只有卡表元素检查之后才会让元素发生变脏，当然这样又会损失一定的性能，但是是可以接受的。针对这一点JDK7增加了一个：+UseCondCardMark参数来控制表更新元素的条件。

并发可达性分析：

通过上面的分析，我们了解了JVM是如何实现对象之间的引用存放，以及如何实现GC ROOT以及如何让线程等待垃圾收集等一系列问题，下面我们来看下更细节的部分，我们都知道对象的引用不是一成不变的，比如在GC ROOT之前对象引用突然失效，垃圾对象突然变为存活对象....这些情况都是有可能的，那么面对复杂多变的 引用关系变化HotSpot是如何解决这个复杂的问题的呢？

要解决这个问题的关键如何保证“一致性快照”，针对这一点，HotSpot虚拟机使用了“三色标记”这一个重要的概念。

三色标记

为了维护一个对象的访问状态，在遍历对象过程中，Hotspot会将对象标记为下面的三种状态：

• 白色：表示尚未被垃圾收集器访问过
• 黑色：表示对象已经被垃圾收集器访问过，并且 所有的引用都扫描过，意味着他不可能直接指向某个白色对象
• 灰色（重点）：表示已经被垃圾收集器访问过，至少有一个引用没有被扫描完。

“对象消失”的成立条件

在书本165页左右（个人看的是PDF）有一张示意图，这里简要说明一下“对象消失”的问题：

• 垃圾变为存活对象：被切断的引用灰色对象即将变为白色对象经过并发线程修改和黑色对象产生引用。
• 存活对象变垃圾：被标记为白色的对象突然与扫描过的黑色对象产生引用。

这里有个不能容忍的问题是原本存活的对象被标记为死亡。会直接导致系统出现委托，这是不能容忍的。

有大神总结了会出现对象消失问题的两个条件，只要排除任意一个就可以防止对象消失的问题：

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

增量更新和原始快照

解决上面的问题，JVM有两种方式，分别是“增量更新”和“原始快照”，增量更新是排除第一个条件，原始快照排除第二个条件。

增量更新：记录下黑色引用插入到白色对象的引用关系，并发标记结束之后以记录过的引用对象为根重新扫描。CMS的“重新标记”阶段的底层就是在做这个事情。

原始快照：原始快照指的是灰色对象删除白色引用的时候，把要删除的引用记录下来，并发扫描之后，再根据记录过引用关系的灰色对象为根进行扫描。G1和Shenandoah 收集器就是使用这种方式实现的。

这里的简化理解就是，增量更新是尝试将白色对象变为灰色对象，而原始快照则是让灰色对象真的变回白色对象

总结：

HotSpot的细节包括三个难点，一个是根节点枚举，我们讲述了底层结构OopMap，可以看到他本质就是一个数组，之后我们讲到了安全点的设计类似收费站检查的方式提高根节点枚举的效率，接着我们讲述了安全区域，好比收费出站，对于没有进行过根节点枚举的就会阻塞等待进行处理，这些设计的根本目的是保证垃圾收集器停顿用户线程的时候拥有一份不会改变引用的快照。

接着我们讲述了抽象的记忆集以及Hotspot的实现卡表这一结构，卡表的作用是保存对象的引用关系以及跨代引用等，而修改和维护的工作则是由写屏障完成，写屏障的任务是在赋值操作的前后对于卡表里面的对应引用进行调整，保证对象可以正确归类为垃圾对象和存活对象。

最后，我们讲述了并发修改的时候，Hotspot如何保证快照的正确性以及防止用户线程并发修改"篡改"对象的状态，首先是使用三色标记，将对象标记为垃圾对象，未扫描完成的对象，和已扫描完成的对象，同时为了对抗对象消失的问题，提出了“原始快照”和“增量更新”的解决方案。