三色标记法

定义

三色标记法(Tri-color Marking)是追踪式垃圾回收的标记阶段抽象,由 Dijkstra 等人提出:把对象染成三色——白色(未访问,回收候选)、灰色(自身已达,子引用未扫描)、黑色(自身与子引用均已处理),从根集合出发把灰色对象逐个变黑,直至无灰色,剩余白色即垃圾。

并发问题

若用户程序(mutator)与标记并发运行,可能出现「黑色对象新指向白色对象、且原有灰色路径被切断」的情形,导致存活对象被误回收。破坏该条件需借助写屏障:增量更新(Dijkstra 屏障,把新引用目标标灰)或原始快照 SATB(Yuasa 屏障,记录被覆盖的旧引用)。

应用

Go 运行时的并发 GC 采用三色标记加混合写屏障;JVM 的 G1 使用 SATB,ZGC 则以染色指针与读屏障达成类似目标。

意义

三色抽象为推理并发 GC 的正确性提供了简洁的不变式语言,是现代低停顿垃圾回收器的理论基石。