HotSpot的算法实现-蒲公英云

1.根节点的枚举

我们通过可达性分析算法从GC Roots中找到全局性的引用（例如常量或者类静态属性）或者是执行上下文（例如栈帧中的本地变量）中，尽管我们的目标非常明确，但是随着java的不断扩大，光一个方法区内的常量、类静态变量就有很多，我们通过该方法区一个一个查询，肯定效率上就有很大的消耗

在现存的收集器中在根节点枚举这一步骤都是要暂停用户线程的，但这样就会出现“stop the world”的现象（用户感觉到的就是系统的卡顿），我们作为软件的开发者，我们必须要降低“stop the world”现象的发生的次数，根节点枚举必须在一个保障一致性的快照中才得以进行（整个枚举期间执行子系统看起来像是在被冻结在某个时间点上）

现在Java虚拟机用的都是准确式垃圾收集，当所有的用户线程停顿下来的时候，我们不需要一个不漏的去检查所有执行上线文和全局的引用位置，Java虚拟机是使用OopMap的数据结构来直接得到哪些地方是存放着对象的引用，一旦类加载动作完成时，Java虚拟机就会将对象内的偏移量上是什么数据类型计算出来，在即时编译的时候，也会在特定的位置上记录下栈里和寄存器里哪些位置是引用，这样就避免了每次从GC Roots中开始查找

2.安全点

HotSpot没有为每条指令都生成一个OopMap，只是在特定的位置生成OopMap,这些特定的位置就是所谓的“安全点”，有了安全点的设定，也就意味着用户程序不能想当然的在任意位置都可以停顿下来进行垃圾收集，而是必须强制到所谓的安全点才可以停顿进行垃圾回收，安全点的选取也是有一定的说法的

安全点的选取不能太少以至于会让收集器等待时间过长
安全点的选取不能太过于频繁以至于增大运行时的内存负荷

2.1 安全点选取的标准

安全点选取的标准是按照“是否让程序长时间执行的特征”，长时间执行最明显的特征就是指令序列的复用，具有这些功能的指令才会产生安全点

方法调用
循环跳转
异常跳转

2.2 如何让所有的线程跑到最近的安全点、停顿？

2.2.1 抢占式中断

抢占式中断不需要线程的执行代码去主动配合，在垃圾收集发生时，系统会将所有的用户线程全部中断，如果发现某些线程中断的位置不是安全点的位置，然后就恢复这条线程的执行，然后过一会再进行中断，直到跑到安全点上

2.2.2 主动式中断

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

3.安全区域

3.1出现的原因

我们已经通过安全点已经解决了程序执行时让虚拟机进入垃圾回状态的问题，但是在程序不执行（所谓的程序不执行就是没有分配处理器的时间，例如用户线程处于Sleep状态或者Blocked状态）的时候呢？我们又有什么办法去进行垃圾回收呢？这时候我们就引入了安全区域来进行解决

3.2 什么是安全区域？

安全区域就是能够确保在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中的任意地方开始进行垃圾收集都是安全的，我们也可以将安全区域看作为被伸长的一系列安全点

3.3 怎么样安全的退出安全点？

当线程要退出安全点的时候，它要检查虚拟机是否已经完成了根节点的枚举，如果完成了，那线程就当做什么事情也没发生过，继续执行，如果没有发生，它就必须一直等待，直到收到可以离开安全区域的型号为止

4.记忆集与卡片

为了解决对象跨代引用所带来的问题，垃圾收集器在新生代建立了名为记忆集的数据结构，用于避免将整个老年代加进GC Roots扫描范围

记忆集时一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构（记忆集的数据结构可能不是上图我画的这样，感兴趣的同学可以自行下去查询资料进行了解）

4.1 记忆集的记录粒度

在垃圾收集的场景中，收集器只需要判断出某一块非收集区域是否存在有指向了收集区域的指针就可以了，并不需要了解这些指针的细节，所有我们就可以选择一些粗犷的记录粒度来节省记忆集的存储和维护成本

字节精度：每个记录精确到一个机器字长（处理器的寻址位数），该字节包括跨代指针
对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针
卡精度：每个记录精确到一个内存区域，该区域内有对象含有跨代指针

4.2 卡表

在4.1中了解到的卡精度其实就是我们这里的卡页，这是目前最常用的一种记忆集实现形式

卡表最简单的形式只是一个字节数组

CARD_TABLE[this address>>9]=0;

字节数组的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称之为“卡页”，一般来说，卡页大小都是以2的N次幂的字节数，一个卡页中内存中通常包含不止一个对象，只要卡页有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称之为这个元素变脏，没有则标识为0，在垃圾回收的时候，只要筛选出卡表中元素变脏的元素，就可以轻而易举的得出哪些卡页内存中存在跨代指针，将它们假如GC Roots中一并扫描

5.三色标记法

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

5.1 误标

所谓的误标就是将“原本是黑色的对象被误标为白色的对象”，会产生对象消失，应该满足的条件：

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

5.2 误标的解决方法

增量更新（破坏第一个条件）：当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等并发扫描结束之后，再将这些记录过的引用关系中的黑色对象为根，重新再扫描一遍（黑色对象一旦插入了指向白色对象的引用之后，它就变回灰色对象了）
原始快照（破坏第二个条件）：当灰色对象要删除指向白色对象的引用关系时，就要将这个删除的引用记录下来，在并发扫描结束后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次（无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象快照来进行搜索）

在HotSpot虚拟机中，增量更新和原始快照这两种解决方案都是有实际应用的，例如，CMS是基于增量更新来做并发标记的，G1则是用原始快照来实现的