Chapter 3.3-3.4 - 垃圾收集算法 && HotSpot 的算法实现细节

Created by : Mr Dk.

2020 / 01 / 25 21:24 🧨🧧

Ningbo, Zhejiang, China

3.3 垃圾收集算法

对于如何判定对象是否消亡，有两种方法：

  • 引用计数式垃圾收集 (Reference Counting GC)
  • 追踪式垃圾收集 (Tracing GC)

下面主要介绍的是追踪式垃圾收集。

3.3.1 分代收集理论

大多数 JVM 都遵循 分代收集 (Generational Collection) 理论进行设计。实际上是一套符合大多数程序实际运行情况的经验法则，建立在两个分代假说之上：

  • 弱分代假说 (Weak Generational Hypothesis) - 绝大多数对象都是朝生夕灭的
  • 强分代假说 (Strong Generational Hypothesis) - 熬过越多次 GC 的对象越难消亡

两个假说共同奠定了 GC 的设计原则：应该将 Java Heap 划分成不同的区域，将回收对象依据年龄放到不同的区域中。

  • 大多数难以熬过 GC 的对象放在一起，每次回收只关注如何保留少量的存活对象
  • 难以消亡的对象放在一起，JVM 用较低的频率来回收这个区域

在 Java Heap 划分出不同区域后，垃圾回收器可以只回收某一区域。分代理论中，至少会把 Java Heap 分为新生代 (Young Generation) 和老年代 (Old Generation) 两个区域：

  • 在新生代中，每次 GC 都有大量对象死去
  • 存活的对象将逐步晋升到老年代中

如果一次 GC 仅限于某一区域，会存在不同代的对象互相引用的问题。比如，新生代对象会被老年代对象引用，GC 时还要扫描所有老年代来确保可达性分析的正确性。

第三条经验法则：跨代引用假说 (Intergenerational Reference Hypothesis)：跨代引用相对于同代引用占极少数。存在相互引用关系的对象倾向于同时生存或同时消亡。

解决方式：不再为少量跨代引用而扫描整个老年代。在新生代上建立一个全局的 记忆集 (Remembered Set)，标识出老年代的哪一块内存存在跨代引用。GC 时，只将包含跨代引用的老年代内存加入 GC Roots 进行扫描。

3.3.2 标记 - 清除 (Mark-Sweep) 算法

首先标记出所有需要回收的对象，在标记完成之后，统一回收掉所有被标记的对象。标记过程就是对象是否属于垃圾的判定过程。缺点：

  1. 执行效率不稳定
  2. 内存空间碎片化 - 导致无法分配较大块的连续内存

3.3.3 标记 - 复制算法

半区复制 (Semispace Copying)：

  • 将可用内存划分为大小相等的两块，每次只使用其中的一块
  • 一块内存用完，就进行 GC，把还存活的对象复制到另一块上，将原来的半块清空

算法开销主要来自于复制这一过程。好处是，复制实际上解决了内存碎片的问题；代价是，可用内存缩小为原来的一半。现在的商用 JVM 主要使用这种算法回收 新生代 对象。IBM 提出，新生代对象中有 98% 熬不过第一轮 GC - 因此不需要按照 1:1 来划分内存。HotSpot 虚拟机中使用 Appel 式回收：

  • 将新生代分为较大的 Eden 空间和两块较小的 Survivor 空间
  • 每次只使用 Eden 和一块 Survivor
  • GC 时，将存活的对象复制到另一块 Survivor 上，清空 Eden 和原 Survivor
  • 默认 Eden:Survivor 为 8:1，新生代可用空间达到 90%

当然并没有办法保证每次存活的对象大小低于剩下的 10% 的 Survivor 空间。Appel 回收还有一个 逃生门 设计：若另一个 Survivor 不够容纳一次 Minor GC 之后存活的对象时，就从其它内存区域 (比如老年代) 进行分配担保 (Handle Promotion)。这些对象通过该机制直接进入老年代。

3.3.4 标记 - 整理 (Mark-Compact) 算法

针对老年代对象的存亡特征，在标记后，让所有存活的对象向内存的一端进行移动，然后直接清理掉边界以外的内存。由于老年代每次 GC 后都有大量对象存活，移动实际上是极为负重的，因为必须全程暂停用户应用程序才能进行。但如果不移动，就要使用分区空闲分配链表来分配内存：由于内存访问很频繁，这个环节上的开销也会影响程序的吞吐量。因此，移动对象会使整体吞吐率更高些。

3.4 HotSpot 的算法细节实现

3.4.1 根结点枚举

可达性分析算法的过程中，所有垃圾收集器在根结点枚举这一步骤上都必须暂停用户线程。

3.4.2 安全点 (Safepoint)

代码指令流并非在任意位置都能停顿下来开始 GC，而是需要到达安全点后才能暂停。如何在 GC 时使所有线程都跑到最近的安全点，并停顿下来？

  • 抢先式中断：将线程全部中断，将未跑到安全点的线程恢复执行，直至跑到安全点 (现已不使用)
  • 主动式中断：当 GC 需要中断线程时，设置一个标志位，各线程执行时主动轮询该标志，轮询操作精简至只有一条汇编指令

3.4.3 安全区域

当程序没有被分配 CPU 时间时，就无法响应 JVM 的中断请求。安全区域指能够确保某一段代码片段中，引用关系不会发生变化。在这个区域中的任意地方开始 GC 都是安全的，当线程执行到安全区域中的代码时，会标识自己已经进入安全区域。JVM 要开始 GC 时，不必去管已经在安全区中的线程；当线程要离开安全区时，要检查 JVM 是否已经完成了根结点枚举如果没有完成，则要一直等待至可以离开安全区为止。

3.4.4 记忆集与卡表

记忆集 是一种从非收集区域指向收集区域的指针集合组成的数据结构。垃圾收集器只需要根据记忆集判断出某一块非收集区域是否存在指向收集区域的指针。记忆的粒度各异。

卡表 (Card Table) 是一种实现方式。卡表最简单的形式可以是一个字节数组，数组中的每个字节代表非收集区域的一个内存块：卡页 (Card Page)。该字节的标识值代表了该卡页中是否存在对收集区域对象的引用。在 GC 时，只需筛选卡表标识的内存块，就能得出哪个卡页包含跨代指针，并将其加入 GC Roots 一同扫描。

3.4.5 写屏障 (Write Barrier)

解决如何维护卡表的问题？即，卡表被置位应当发生在引用被赋值的那一刻，如何在对象赋值的那一刻更新维护卡表呢？写屏障技术可以在引用对象赋值时产生一个环形通知，供程序执行额外的动作。写屏障覆盖了赋值前后：

  • 写前屏障
  • 写后屏障

每次只要对引用进行更新，就会产生额外的开销。

3.4.6 并发的可达性分析

可达性分析算法理论上要求在一个一致性的快照中进行，意味着必须要冻结所有的线程。在根结点枚举中带来的线程停顿已经很短暂且固定了：从 GC Roots 开始遍历对象，停顿时间与堆的容量成正比。引入三色标记来表示一个堆上的对象是否被访问过：

  • 白色：尚未被垃圾收集器访问；若在分析结束后依旧是白色，则该对象不可达
  • 黑色：对象已被垃圾收集器访问过，且该对象的所有引用都已被扫描过
    • 黑色对象安全存活
    • 黑色对象不能直接 (不经过黑色对象) 指向白色对象
  • 灰色：对象已被垃圾收集器访问过，但该对象至少还存在一个引用没有被扫描过

在可达性分析过程中，垃圾收集器以黑色结点为起点，以灰色的波纹，从黑向白推进，如果可达性分析过程中所有线程都静止，那没有任何问题 (只会导致线程停顿时间过长)。因此可达性分析与线程运行是并发的，这就会产生两种问题：

  1. 把本应该消亡的对象重新标记为存活
  2. 把本应该存活的对象错误标记为死亡

后者将会带来严重错误。理论证明，在两个条件同时满足时，才会产生该错误：

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

原本引用它的灰色对象还没有扫描到它，重新引用它的黑色对象已经完成扫描不再会扫描到它，那么这个本该存活的对象会被 GC。为了避免该问题，只需破坏其中的一个条件即可：

  • 增量更新 (Incremental Update) 破坏第一个条件
    • 黑色对象插入新的指向白色对象的引用时，记录下来
    • 并发扫描结束后，从记录的这些黑色结点开始，重新扫描一次
    • 相当于黑色对象在插入新的引用后退化为灰色对象
  • 原始快照 (Snapshot At The Beginning, SATB) 破坏第二个条件
    • ？