背景与定义

背景

三色标记法是垃圾回收中用于判断对象是否为存活对象的一种图遍历算法。其理论基础是 根可达性分析（GC Roots Reachability Analysis），该方法定义了对象是否可被程序访问，从而决定是否存活。

传统的标记过程需要 Stop-The-World（STW），即暂停所有用户线程，以保证对象引用关系在标记期间不发生变化，确保准确性。但由于堆内存可能非常大，整个标记过程带来的 STW 停顿时间可能过长，影响应用性能。

因此，为了在保证标记正确性的前提下减少 STW 时间，引入了 三色标记法，它允许在标记阶段与用户线程并发执行，从而提高垃圾回收效率。

定义

三色标记法（Tri-color Marking） 是一种用于垃圾回收的并发标记算法，通过将对象分为三种颜色（白色、灰色、黑色），实现对象图的高效遍历与存活对象的识别。其主要目标是支持并发标记，减少垃圾回收过程中的停顿时间。

颜色	含义
白色	对象尚未被访问，可能为垃圾对象
灰色	对象已被访问，但其引用的对象尚未完全处理
黑色	对象已被访问，且其所有引用对象也已被处理完毕

原因与好处

原因

• 在不并发的情况下，标记过程必须在 STW 状态下进行，以防止对象引用关系变化导致标记不准确。
• 但随着堆内存的增长，单线程标记的耗时显著增加，导致应用停顿时间过长。
• 三色标记法通过对对象图的并发遍历，允许用户线程与垃圾回收线程同时运行，从而降低 STW 的频率和持续时间。

好处

• 支持并发标记，显著减少垃圾回收的停顿时间。
• 适用于大规模堆内存的垃圾回收场景。
• 在保证正确性的前提下，提高了系统整体的响应性和吞吐量。

标记过程的几个阶段

1. 初始标记（Initial Mark）：

   • 遍历所有 GCRoot（如线程栈、静态变量等），仅扫描根对象及其直接引用。
   • 根对象标记为灰色，其直接引用的对象也标记为灰色（避免扫描整个堆）。
   • 此阶段耗时短，需 STW 以确保对象图稳定。

2. 并发标记（Concurrent Mark）：

   • 用户线程与回收器并发执行。回收器从灰色对象开始遍历：
     • 将灰色对象引用的所有白色对象标记为灰色。
     • 将当前灰色对象标记为黑色（表示完成扫描）。
     • 重复过程，直到无灰色对象剩余。
   • 写屏障（Write Barrier）技术用于跟踪引用变更（例如用户线程修改对象引用）。

3. 重新标记（Remark）：

   • 处理并发阶段变更的引用关系（例如新引用或删除引用）。
   • 需短暂 STW，确保标记正确性。

4. 并发清除（Concurrent Sweep）：

   • 清除所有白色对象，用户线程可继续并发执行。

漏标问题与浮动垃圾

漏标问题（对象消失问题）

当两个条件同时满足时，会导致对象漏标：

1. 黑色对象新增对白色对象的引用（黑色对象已经处理完成，不会再次被扫描）。
2. 灰色对象到该白色对象的所有引用路径被断开（白色对象不再能被图遍历算法访问到）。

结果：该白色对象未被标记为存活，却被错误地回收。

解决方案

• CMS（Concurrent Mark Sweep）：

  • 使用 增量更新（Incremental Update） 策略。
  • 当黑色对象新增指向白色对象的引用时，记录该引用变更。
  • 在重新标记阶段重新处理这些新增引用，确保对象被正确标记。

• G1（Garbage-First）：

  • 使用 原始快照（Snapshot-At-The-Beginning, SATB） 策略。
  • 在并发标记开始时记录所有对象的引用快照。
  • 当灰色对象删除对白色对象的引用时，记录该变更，并在最终标记阶段重新处理。

浮动垃圾（多标问题）

• 定义：对象在并发标记开始时被认为是存活的（被标记为黑色），但在标记结束后，该对象不再被任何根节点引用，理应被回收，但由于标记已经完成，仍被保留。
• 原因：三色标记法无法实时感知引用删除。
• 解决方式：不做处理，将浮动垃圾保留到下一次垃圾回收时再处理。

实际应用

三色标记法广泛应用于现代垃圾回收器中，特别是在需要并发执行的场景：

• CMS 垃圾回收器：

  • 使用三色标记 + 增量更新实现低延迟回收。
  • 并发标记和重新标记阶段使用写屏障记录引用变更。

• G1 垃圾回收器：

  • 使用三色标记 + SATB 实现更精确的并发标记。
  • 通过原始快照处理引用删除，避免漏标。