JVM垃圾回收器之Shenandoah收集器

JVM垃圾回收器之Shenandoah收集器

Shenandoah，第一款不由Oracle（包括以前的Sun）公司的虚拟机团队所领导开发的HotSpot垃圾收集器，这个项目的目标 是实现一种能在任何堆内存大小下都可以把垃圾收集的停顿时间限制在十毫秒以内的垃圾收集器。

工作过程：

初始标记（Initial Marking）：

• 首先标记与GC Roots直接关联的对象，这个阶段仍 是“Stop The World”的，但停顿时间与堆大小无关，只与GC Roots的数量相关。

并发标记（Concurrent Marking）：

• 遍历对象图，标记出全部可达的对象，这个阶段 是与用户线程一起并发的，时间长短取决于堆中存活对象的数量以及对象图的结构复杂程度。

最终标记（Final Marking）：

• 处理剩余的SATB扫描，并在这个阶段统计出回收价值 最高的Region，将这些Region构成一组回收集（Collection Set）。最终标记阶段也会有一小段短暂的停顿。

并发清理（Concurrent Cleanup）：

• 这个阶段用于清理那些整个区域内连一个存活对象都没有找到 的Region（这类Region被称为ImmediateGarbage Region）。

并发回收（Concurrent Evacuation）：

• 并发回收阶段是Shenandoah与之前HotSpot中其他收集器的核心差异。在这个阶段，Shenandoah要把回收集里面的存活对象先复制一份到其他未被使用的Region之中。复制对象这件事情如果将用户线程冻结起来再做那是相当简单的，但如果两者必须要同时并发进行的话，就变得复杂起来了。其困难点是在移动对象的同时，用户线程仍然可能不停对被移动的对象 进行读写访问，移动对象是一次性的行为，但移动之后整个内存中所有指向该对象的引用都还是旧对象的地址，这是很难一瞬间全部改变过来的。对于并发回收阶段遇到的这些困难，Shenandoah将会通 过读屏障和被称为“Brooks Pointers”的转发指针来解决（讲解完Shenandoah整个工作过程之后笔者还要 再回头介绍它）。并发回收阶段运行的时间长短取决于回收集的大小。

初始引用更新（Initial Update Reference）：

• 并发回收阶段复制对象结束后，还需要把堆中所有指向旧对象的引用修正到复制后的新地址，这个操作称为引用更新。引用更新的初始化阶段实际上并未做什么具体的处理，设立这个阶段只是为了建立一个线程集合点，确保所有并发回收阶段中进行的收集器线程都已完成分配给它们的对象移动任务而已。初始引用更新时间很短，会产生一个非常短暂的停顿。

并发引用更新（Concurrent Update Reference）：

• 真正开始进行引用更新操作，这个阶段是与用户线程一起并发的，时间长短取决于内存中涉及的引用数量的多少。并发引用更新与并发标记不同，它不再需要沿着对象图来搜索，只需要按照内存物理地址的顺序，线性地搜索出引用类型，把旧值改为 新值即可。

最终引用更新（Final Update Reference）：

• 解决了堆中的引用更新后，还要修正存在于GC Roots 中的引用。这个阶段是Shenandoah的最后一次停顿，停顿时间只与GC Roots的数量相关。

并发清理（Concurrent Cleanup）：

• 经过并发回收和引用更新之后，整个回收集中所有的Region已 再无存活对象，这些Region都变成Immediate Garbage Regions了，最后再调用一次并发清理过程来回收 这些Region的内存空间，供以后新对象分配使用。
• 

SATB（原始快照）

• 主要是为了解决并发扫描时的对象消失问题

什么是对象消失问题？

• 为了帮助理解，首先我们先引入一个概念“三色标记”，假设通过三色标记（Tri-color Marking）作为工具，把遍历对象图过程中遇到的对象，按照“是否访问过”这个条件标记成以下三种颜色：

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

• 

• Wilson于1994年在理论上证明了，当且仅当以下两个条件同时满足时，会产生“对象消失”的问 题，即原本应该是黑色的对象被误标为白色：

• 赋值器（用户程序）插入了一条或多条从黑色对象到白色对象的新引用；

• 赋值器（用户程序）删除了全部从灰色对象到该白色对象的直接或间接引用。

• 因此，我们要解决并发扫描时的对象消失问题，只需破坏这两个条件的任意一个即可。由此分别 产生了两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning， SATB）。

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

• 以上无论是对引用关系记录的插入还是删除，虚拟机的记录操作都是通过写屏障实现的。在 HotSpot虚拟机中，增量更新和原始快照这两种解决方案都有实际应用，譬如，CMS是基于增量更新 来做并发标记的，G1、Shenandoah则是用原始快照来实现。

与G1的关系

相似处

• Shenandoah更像是G1的下一代继承者，它们两者有着相似的堆内存布局，在初始标记、并发标记等许多阶段的处理思路上 都高度一致，甚至还直接共享了一部分实现代码，这使得部分对G1的打磨改进和Bug修改会同时反映 在Shenandoah之上，而由于Shenandoah加入所带来的一些新特性，也有部分会出现在G1收集器中，譬如在并发失败后作为“逃生门”的Full GC[3]，G1就是由于合并了Shenandoah的代码才获得多线程Full GC的支持。

• 改进

  • G1的回收阶段是可以多线程并行的，但却不能与用户线程并发；Shenandoah通过转发指针Brooks Pointer（算法核心实现后续分享）+读写屏障拦截 实现对象移动与用户程序并发
  • Shenandoah（目前）是默认不使用分代收集的，换言之，不会有 专门的新生代Region或者老年代Region的存在，没有实现分代。
  • Shenandoah摒弃了使用连接矩阵”（Connection Matrix）的全局数据结构来记录跨Region的引用关系替代了RSet，降低了处理跨代指针时的记忆集维护消耗，也降低了伪共享问题的发生概率。连接矩阵可以简单理解为一张二维表格，如下图
  •