1. 什么是三色标记算法？

三色标记算法 是一种用于标记存活对象 (Marking Live Objects) 的图遍历算法。它将堆中的所有对象划分为三种颜色，以表示其在可达性分析过程中的不同状态。通过这种颜色标记，垃圾回收器能够区分出哪些对象是存活的（即不应被回收），哪些是死亡的（即可以被回收的）。

该算法是并发垃圾回收器（如CMS、G1、ZGC、Shenandoah等）能够与应用程序线程并行工作的基础。

三种颜色及其含义：

1. 白色 (White)：

   • 表示对象未被访问过。
   • 在GC开始时，所有对象都是白色的。
   • 在标记阶段结束时，仍是白色的对象被视为垃圾对象，将被回收。
   • 可以理解为“待处理”或“已死亡”的对象。

2. 灰色 (Gray)：

   • 表示对象已被访问过。
   • 但它的一个或多个子对象（它引用的对象）还没有被完全扫描。
   • 可以理解为“正在处理中”的对象。

3. 黑色 (Black)：

   • 表示对象已被访问过。
   • 并且它的所有子对象（它引用的对象）也全部被扫描过并标记（要么是灰色，要么是黑色）。
   • 可以理解为“已处理完成”且“确认存活”的对象。

---

2. 基础三色标记算法流程 (非并发)

为了理解并发场景下的复杂性，我们首先看一个理想化的、非并发（即应用程序停顿）的三色标记过程：

1. 初始化： GC开始时，将所有对象都标记为白色。
2. 根集扫描： 从GC Roots（如虚拟机栈、本地方法栈、方法区中的静态变量、常量等）开始，遍历所有直接被GC Roots引用的对象。将这些对象标记为灰色，并放入一个“待处理列表”（通常是一个队列）。
3. 遍历：
   • 从“待处理列表”中取出一个灰色对象A。
   • 遍历A的所有子对象（字段引用）。
   • 如果子对象B是白色的，则将B标记为灰色，并将其加入“待处理列表”。
   • 当A的所有子对象都被扫描完毕（并相应地被标记为灰色或黑色）后，将对象A标记为黑色。
4. 重复： 重复步骤3，直到“待处理列表”为空。
5. 结束： 此时，所有黑色对象都是存活的，所有灰色对象最终都会变成黑色（或在某些特殊情况下，如果其子对象有环，它们自身也会被处理成黑色）。最终，所有仍然是白色的对象即为不可达的垃圾，可以被回收。

---

3. 并发场景下的挑战：一致性问题

当三色标记算法在GC与应用程序线程并发运行时，事情变得复杂。应用程序线程（也称为Mutator）可能会修改对象图，这可能导致两种基本的一致性问题：

3.1. 漏标 (Missing Live Object) - 最严重的问题

定义： 一个明明是存活的对象，在GC标记结束后却被错误地标记为白色，从而被回收。这是最危险的，因为会导致程序错误甚至崩溃。

发生条件： 当以下两个条件同时满足时，就会发生漏标：

1. 应用程序删除了从“灰色”对象到“白色”对象的引用。 (即A (灰色) 不再引用 C (白色))
2. 应用程序新增了从“黑色”对象到“白色”对象的引用。 (即B (黑色) 开始引用 C (白色))

举例说明：

假设有对象A（灰色），B（黑色），C（白色）。

• 初始状态：GC Roots -> A (灰色已入队)，GC Roots -> B (黑色已处理完毕)。A -> C (C是白色)。
• GC线程正在遍历，B已经是黑色（意味着B及其所有子对象都处理完了）。A是灰色（待处理）。
• 并发过程：
  1. 应用程序线程执行操作：A.field = null; （删除了 A -> C 的引用）。
  2. 应用程序线程执行操作：B.new_field = C; （新增了 B -> C 的引用）。
• 结果：
  • A在处理完其子对象后，发现C不再是其子对象，因此C不会通过A的路径被标记。
  • B已经是黑色，按照三色标记原则，黑色对象不会再被扫描，所以C也不会通过B的路径被标记。
  • 最终，C仍然是白色，被误判为垃圾而回收。

3.2. 错标 (Floating Garbage) - 不那么严重的问题

定义： 一个明明是死亡的对象，在GC标记结束后却被错误地标记为黑色，从而没有被回收。

发生条件： 当以下条件满足时，会发生错标：

• 应用程序删除了所有从“灰色”或“黑色”对象到“白色”对象的引用。 (即一个对象的所有引用链被切断)
• GC线程在删除操作之前已经访问过该对象，并将其标记为灰色或黑色。

举例说明：

假设对象A（灰色）引用了对象C（白色）。

• 初始状态：A (灰色已入队)，A -> C (C是白色)。
• 并发过程：
  1. GC线程正在处理A，A将C标记为灰色并加入待处理列表。
  2. 应用程序线程执行操作：A.field = null; （删除了 A -> C 的引用，C变得不可达）。
• 结果： C已经被GC标记为灰色，最终会被标记为黑色。虽然它已经不可达，但GC不知道，将它作为存活对象保留了下来。这种对象被称为“浮动垃圾”，会在下一次GC周期中被回收。

错标虽然会增加内存占用，但不会导致程序错误，因此通常比漏标更容易接受和处理。

---

4. 屏障机制 (Barrier) - 解决并发问题

为了解决并发标记中的漏标问题，现代GC引入了屏障机制。屏障是JVM在编译器或运行时，在应用程序代码中插入的一小段代码，用于拦截特定内存操作（读或写），从而记录引用变化信息。

4.1. 写屏障 (Write Barrier)

写屏障在对象引用被修改时触发。它分为：

1. 增量更新 (Incremental Update) - 基于后写屏障 (Post-write Barrier)

   • 解决思路： 当一个黑色对象A新增了一个对白色对象C的引用时（B.new_field = C;），认为这种引用关系是新增出来，在标记阶段结束时可以重新扫描。
   • 工作原理： 当一个黑色对象引用了一个白色对象时，后写屏障会把这个黑色对象重新标记为灰色，让GC重新扫描它的子对象，或者将白色对象C标记为灰色加入待处理队列。
   • 效果： 这种机制确保“黑色对象引用白色对象”的链条不会被遗漏。它只避免了漏标，但可能会造成更多的浮动垃圾。
   • 采用者： CMS GC。

2. 原始快照 (Snapshot At The Beginning, SATB) - 基于前写屏障 (Pre-write Barrier)

   • 解决思路： 当一个“灰色”对象A删除一个对“白色”对象C的引用时（A.field = null;），将A在GC开始时指向的引用C记录下来。
   • 工作原理： 当一个引用即将从另一个引用中消失时（即修改一个对象的引用字段前），前写屏障会捕捉到被删除的旧引用，将其指向的对象标记为灰色（即放入待处理队列）。
   • 效果： 确保在GC标记开始时所有可达的对象都被标记。这种方式避免了漏标，但会产生更多的浮动垃圾（因为即使对象不可达了，只要GC开始时它可达，就会被标记为存活）。
   • 采用者： G1 GC。

4.2. 读屏障 (Load Barrier)

读屏障在应用程序读取对象引用时触发。它不是直接解决三色标记的漏标问题，而是为了支持更高级的并发机制（如并发对象移动），但在这种机制下，也顺带解决了标记的一致性问题。

• 解决思路： 应用程序读取引用时，由屏障检查并修正引用状态。
• 工作原理： 当应用程序读取到一个对象引用时，读屏障会拦截该操作，检查该引用所指向的对象的状态（通过染色指针或转发指针）。如果对象在GC过程中已经被移动，或者其状态需要更新，读屏障会自动将引用修正为新地址或更新其标记状态，然后才将修正后的引用返回给应用程序。
• 效果： 在并发对象移动的情况下，确保应用程序总是访问到对象最新、正确的地址，从而避免了因对象移动导致的任何不一致，也就间接解决了标记阶段的正确性。
• 采用者： ZGC (染色指针)，Shenandoah GC (Brooks Pointer)。

---

5. 各GC收集器中的三色标记应用

• CMS GC (Concurrent Mark-Sweep)：
  • 标记算法： 基于三色标记。
  • 屏障： 主要使用增量更新（写屏障）。在并发标记阶段，如果黑色对象引用了白色对象，CMS会通过写屏障将黑色对象置灰，以便重新扫描。这会导致浮动垃圾，但避免了漏标。
  • 暂停： 初始标记和最终标记阶段需要STW。
• G1 GC (Garbage-First)：
  • 标记算法： 基于三色标记。
  • 屏障： 使用SATB（前写屏障）。G1会在并发标记开始时创建堆的逻辑快照，并发标记过程中引用的删除会被记录下来。最终标记时，会处理这些记录。SATB能非常高效地避免漏标，但会产生更多的浮动垃圾。
  • 暂停： 初始标记（通常与Young GC绑定）、最终标记（Remark）、混合GC（Mixed GC）阶段需要STW。
• ZGC (The Z Garbage Collector)：
  • 标记算法： 内部仍基于三色标记思想（通过染色指针的Marked0/Marked1位表示）。
  • 屏障： 核心是读屏障和染色指针。读屏障会在应用程序读取引用时检查染色指针的状态，如果对象正在被移动或标记状态需要更新，屏障会直接修正引用。
  • 暂停： 初始标记、最终标记和转移开始这几个STW阶段的停顿时间与堆大小无关，极短（亚毫秒级）。
• Shenandoah GC：
  • 标记算法： 内部基于三色标记。
  • 屏障： 核心是读屏障和Brooks Pointer（转发指针）。读屏障在读取引用时，通过Brooks Pointer找到对象的最新地址。
  • 暂停： 初始标记和最终标记这几个STW阶段的停顿时间与堆大小无关，极短（亚毫秒级）。

---

6. 总结

三色标记算法是理解现代垃圾回收器并发机制的基石。它通过将对象划分为白、灰、黑三种颜色，清晰地定义了GC的标记过程。然而，在并发GC中，由于应用程序线程对对象图的修改，可能导致漏标（最危险）或错标（浮动垃圾）。各种屏障机制（写屏障的增量更新/SATB、读屏障）被发明出来，以保证并发GC过程中的引用修改不会导致漏标，从而确保GC的正确性，并尽可能地减少STW时间。

不同GC收集器选择不同的屏障机制和并发策略，以在吞吐量、停顿时间和内存/CPU开销之间取得平衡。理解这些机制有助于我们更好地诊断GC问题和进行性能调优。