Hotspot的算法实现

1.枚举根节点

可达性分析中从GC Roots找引用链为例。

可作为GC Roots的节点做要在全局性的引用（例常量或静态属性）与执行上下文（例栈帧中的本地变量表），方法区数据量大，逐个检查引用，时间太长。

可达性分析必须在一个能确保一致性的快照中进行。整个分析期间，整个执行系统就像是被冻结在某个时间点，不能出现分析过程中对象引用在变化的情况。(GC停顿，GC进行时必须停顿所有线程的一个重要原因)

Hotspot使用一组OopMap的数据结构记录对象引用。在类加载完成时，把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中，也会在特定的位置记录下栈和寄存器中哪些位置是引用。

2.安全点

程序执行时并非在所有地方都停顿下来开始GC，只有在到达安全点才能暂停。

安全点的选择是以程序“是否具有让程序长时间执行的特征”来选定的。长时间执行的最明显特征就是指令序列复用、循环跳转、异常跳转等，具有这些功能的指令才会产生安全点（SafePoint）

GC发生时如何让所有线程（不包括执行JNI的线程）都“跑”到安全点停顿下来？

1.抢先式中断：不需要线程的直销代码主动去配合，在GC发生时，先把所有线程全部中断，如果发现有线程中断的地方不在安全点，就恢复线程，让它“跑”到安全点上。（几乎没有虚拟机采用）
2.主动式中断：不直接对线程操作，仅仅简单的设置一个标志，各个线程执行时主动去轮询这个标志，发现中断标志为真时就自己中断挂起。轮询标志的地方和安全点是重合的，再加上创建对象需要分配内存的地方。

3.安全区域

安全区域（Safe Region）：指在一段代码片段中，引用关系不会发生变化。在这个区域中的任意地方开始GC都是安全的。

当线程执行到安全区域时，先标识已经进入安全区域，当发生GC时，不用管安全点状态的标识了。在线程离开安全区域时，要检查系统是否完成了整个GC过程，如果完成了，就继续执行，否则就等待直到收到可以安全离开安全区域的信号为止。

4.记忆集与卡表

记忆集用来缩减GC Roots的扫描范围。

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。

记忆集的记录精度：

字长精度：每个记录精确到一个机器字长(就是处理器的寻址位数)，该字包含跨代指针。
对象精度：每个记录精确到一个对象，该对象里有字段包含跨代指针。
卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。(是指用“卡表”方式实现记忆集，也是最常用的一种实现方式。)

卡表是记忆集的一种具体实现，定义了记忆集的记录精度、与堆内存的映射关系等。

HotSpot中卡表的表现形式为字节数组CARD_TABLE，每一个元素都对应着标识的内存区域中一块特定大小的内存块，称为“卡页”。

一个卡页的内存中包含不止一个对象，只要有对象的字段存在跨带指针，就将对应卡表的数组元素的值标识为1，成这个元素变脏(Dirty)。垃圾收集时，只要筛选出卡表中变脏的元素，就能找到哪些卡页内存块中包含跨代指针，加入GC Roots中一并扫描。

5.写屏障

当其他分代区域中的对象引用到了本区域的对象时，其对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻。通过写屏障技术维护卡表状态。

写屏障可以看做在虚拟机层面对“引用类型字段赋值”这个动作的的AOP切面，在引用对象赋值时会产生一个环形通知，供程序执行额外的动作，也就是赋值的前后都在写屏障的覆盖范畴内。

6.并发的可达性分析

解决一致性的快照上进行对象图的遍历。

白色：标识对象尚未被垃圾收集器访问。
黑色：标识对象已经被垃圾收集器访问，且这个对象的所有引用都已经扫描过。黑色不可能直接指向某个白色。
灰色：标识对象已经被垃圾收集器访问，但这个对象上至少存在一个引用还没有被扫描。

会产生“对象消失”问题条件：

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

解决并发扫描时的对象消失:

1.增量更新：黑色对象一旦插入了指向白色对象的引用之后，就变回了灰色对象。
2.原始快照：无论引用关系删除与否，都会按照刚开始扫描那一刻的对象图快照来进行搜索。