三色标记法（标记算法）

1.基本概念

白色（未被标记，默认）、灰色（还有引用的对象）、黑色（被标记完的）。

2.背景

原始的垃圾标记算法比如计数器法（无法解决循环依赖问题）、可达性分析法（整个分析都需要STW，停顿时间长）。

3.标记过程：

3.1 初始标记（Initial Marking）

• 目标：标记从 GC Roots 直接可达的对象。
• 过程：
  • 从 GC Roots（如栈帧、静态变量、JNI 引用等）出发，标记所有直接引用的对象为 灰色。
  • 这些对象会被加入待扫描队列。
• 特点：
  • 这个阶段是 停顿的（Stop-the-World），因为需要快速确定 GC Roots 的直接引用。
  • 停顿时间通常很短。

3.2 并发标记（Concurrent Marking）

• 目标：在应用程序运行的同时，遍历所有对象图，标记所有存活对象。
• 过程：
  • 从初始标记阶段得到的 灰色 对象开始，递归遍历所有引用链。
  • 将遍历到的对象标记为 灰色 或 黑色。
  • 这个阶段是 并发执行的，不会暂停应用程序。
• 特点：
  • 由于是并发执行的，应用程序可能会修改对象图（例如新增引用或删除引用）。
  • 这可能导致 漏标 或 多标 的问题。

3.3 重新标记（Remark）

• 目标：修正并发标记阶段由于应用程序运行导致的标记错误。
• 过程：
  • 暂停应用程序（Stop-the-World），确保对象图不再变化。
  • 重新扫描并发标记期间可能被修改的部分：
  • 使用 写屏障（Write Barrier） 记录的对象引用变化。
  • 重新标记这些对象，确保所有存活对象都被正确标记为 黑色。
• 特点：
  • 这个阶段是 停顿的，但通常比初始标记阶段长。
  • 它是并发标记的补充，确保标记结果的准确性
     

4.并发标记的写屏障

（以下两种方式：增量更新 or 原始快照）

用于记录并发标记期间对象的修改状态，如果增加了一个引用，并且没有被标记过则标记为灰色在第三阶段重新标记。

可能会发生多标，影响不大，下一次GC会清理掉。不会发生漏标。

5.漏标问题

过程：

• A（黑）-> B （灰）-> C（白） ①初始状态

• A（黑） -> C（白） <- B（灰） ②增加A到C

• A（黑）-> C（白） B（灰） ③删除B到C

• 此时C就是一个活跃对象但是将会被回收

原因及方案：

• 至少有一个黑色对象在自己被标记之后指向了这个白色对象

  • 增量更新：检测到A->C，将C标记为灰色

• 所有的灰色对象在自己引用扫描完成之前删除了对白色对象的引用

  • 原始快照：检测到B删除C，将C标记为灰色，最后C被扫描