三色标记：CMS 与 G1 的并发标记

上一篇讲了 CMS 和 G1 为什么能做到低停顿：它们把“标记哪些对象存活”这个最耗时的阶段，从“暂停所有线程”改成了“和业务线程并发执行”。但并发带来一个新问题——标记到一半，业务线程还在改引用，标记结果可能错。三色标记（Tri-color Marking）就是用来描述和解决这个问题的模型。

三色标记不复杂，却是一个很好的例子：它把“并发 GC 怎么保证正确性”这个看似玄乎的问题，收敛到“一个对象什么时候会从黑变白、以及怎么防住它”这样具体的问题上。理解了它，CMS 的增量更新和 G1 的 SATB 就不再是两个需要死记的名词，而是“破坏漏标两个条件”的两种必然选择。

本文回答一个问题：三色标记怎么标记对象，并发下为什么会漏标，CMS 和 G1 分别怎么防。它是 Java 系列的最后一篇，接着上一篇 GC 收集器，也接着第一篇里“对象在堆里怎么被回收”的伏笔。

一、三种颜色：白、灰、黑

三色标记把对象分成三种状态，用三种颜色标记：

• 白色：还没被访问过，可能是垃圾（标记结束后，仍是白色的就是垃圾）；
• 灰色：已经被访问过，但它直接引用的对象还没全部访问完；
• 黑色：已经被访问过，而且它直接引用的对象也都访问完了。

整个标记过程，就是从 GC Roots 出发，把对象从白变灰、再从灰变黑。灰对象是“正在处理中”的边界——它引用的对象还没被看全，所以不能急着把它变黑。

这张图要记住的核心是那个“不变式”：标记过程中，黑色对象不能直接指向白色对象。只要这条不变式被打破，就可能漏标——黑色对象以为自己都处理完了，却悄悄多了一个指向白色对象的引用，这个白色对象就逃过了标记、被当成垃圾回收。所有并发 GC 的正确性，最终都是围绕“怎么维护这条不变式”展开的。

二、标记过程：从 GC Roots 出发

标记从 GC Roots（第一篇讲过：栈里的引用、静态变量等）开始，规则很简单：

1. 初始所有对象是白色，把 GC Roots 直接引用的对象标灰；
2. 从灰集合里取出一个对象，把它引用的白色对象标灰，然后把它自己标黑；
3. 重复第 2 步，直到灰集合清空；
4. 最后剩下的白色对象，就是不可达的垃圾。

拿一个具体例子走一遍，就清楚这套“白 → 灰 → 黑”到底在干什么了。假设对象图是这样：

GC Roots ──▶ A ──▶ B ──┬──▶ C
                       └──▶ D

标记开始前，A、B、C、D 全是白色（一个都还没访问过）。然后按规则推进：

步骤	动作	标记结果	灰集合（待办清单）
1	从 GC Roots 出发，把直接引用的 A 标灰	A 灰，B/C/D 白	[A]
2	取出 A：把它的引用 B 标灰，A 自己标黑	A 黑，B 灰，C/D 白	[B]
3	取出 B：把它的引用 C、D 标灰，B 自己标黑	A/B 黑，C/D 灰	[C, D]
4	取出 C：它没有引用别的对象，直接标黑	A/B/C 黑，D 灰	[D]
5	取出 D：同样标黑，灰集合清空	全部黑色	[]

整个过程里，灰集合就是“待办清单”：取一个出来、看它引用了谁、把那些白色对象加入清单、自己标黑——直到清单清空。走完之后如果还有白色对象，说明没有任何引用链能到达它，那就是垃圾。

单线程、无并发时，这套流程是安全的：标记结束时，黑色对象引用的都是黑色，白色对象一定不可达。问题出在并发——CMS 和 G1 的标记阶段，业务线程还在跑、还在改引用，规则就可能被破坏。

三、并发标记的坑：漏标

并发下，业务线程在标记过程中可能做两类修改：新增一条引用、删掉一条引用。这两类修改，恰好对应漏标的两个条件。

漏标要发生，两个条件必须同时满足：

1. 业务线程新增了一条从黑色对象到白色对象的引用（黑 → 白）；
2. 业务线程删掉了从灰色对象到那个白色对象的所有可达路径（灰 → 白断了）。

两个条件缺一不可，可以这样理解：如果只有条件 1（黑 → 白），那个白色对象可能还被别的灰色对象引用着，标灰的灰色对象后续会处理到它，不会漏；如果只有条件 2（灰 → 白断了），那说明它本来就不可达了，回收它是对的。只有两个条件同时成立——它既失去了“被灰对象看到”的机会，又搭上了“黑对象”这条新线——它才真正“活生生地被漏掉”。

漏标的后果是致命的：一个还活着的对象被当成垃圾回收，之后程序访问它，读到的是被回收的内存，轻则数据错乱、重则崩溃。所以并发 GC 必须防住它。

四、两种解法：CMS 增量更新，G1 原始快照

既然漏标要两个条件同时成立，那么破坏任意一个条件就能防住。CMS 和 G1 正好各选了一个。

CMS 用增量更新（Incremental Update），破坏条件 1。当业务线程新增一条“黑色对象指向白色对象”的引用时，CMS 通过写屏障拦截这个赋值，把这个黑色对象重新标灰，让它回到“待处理”状态、重新处理它引用的对象。于是“黑 → 白”这条新边一出现就被拆掉，条件 1 永远不成立。

G1 用原始快照（Snapshot At The Beginning，SATB），破坏条件 2。SATB 的思路是“标记开始时，哪些对象是活的，就保证哪些对象最后一定是活的”。当业务线程删掉“灰色对象指向白色对象”的引用时，G1 通过写屏障把这个被删的引用记录下来，当作“这个白色对象还活着”，于是条件 2 造成的“失去引用”被无视了。

两者的差别在于“宁可多标、不可漏标”的偏向：增量更新让“新增的黑→白引用”重新被处理，SATB 让“被删的灰→白引用”仍然算数。SATB 会多保留一些“其实已经死了”的对象（等下一轮再回收），换来的是“绝不错杀活对象”。这个“宁可多标、不可漏标”的取舍，是所有并发 GC 正确性设计的核心——多标只是浪费一点内存，漏标是程序崩溃。

无论增量更新还是 SATB，实现上都靠写屏障（write barrier）：在每次引用赋值时插入一小段额外的代码，去记录或修复。这解释了为什么并发 GC 有额外的 CPU 开销——那个“额外代码”就是写屏障，它维护着三色不变式，是并发 GC 正确性的代价。

两者的写屏障逻辑完全不同，分开看更清楚。

CMS 的增量更新屏障——盯住“新增的引用”：

// CMS 写屏障（增量更新）：赋值时检查「黑 → 白」
void writeBarrier(Object field, Object newValue) {
    if (marking && isBlack(field.owner) && isWhite(newValue)) {
        markGray(field.owner);   // 把这个黑对象重新标灰，放回待办清单
    }
    field = newValue;            // 真正的赋值
}

逐行看：marking 判断“当前是否在并发标记阶段”（不在标记阶段就什么都不用做，这也是写屏障的开销主要在标记期）；isBlack(field.owner) && isWhite(newValue) 正是漏标条件 1 的形态——黑色对象新增了一条指向白色对象的引用；命中就 markGray，把那个黑对象打回灰色、重新放回待办清单，让它下次被处理时会把 newValue 也标上。于是“黑 → 白”这条边刚出现就被拆掉了。

G1 的 SATB 屏障——盯住“被删掉的引用”：

// G1 写屏障（SATB）：赋值时先把「旧值」记录下来
void writeBarrier(Object field, Object newValue) {
    Object oldValue = field;                  // 先读旧值
    if (marking && oldValue != null && !isBlack(oldValue)) {
        enqueueForMarking(oldValue);          // 把旧值记进 SATB 队列，当作它还活着
    }
    field = newValue;                         // 真正的赋值（旧引用就此断开）
}

逐行看：关键在于**“先读旧值”**——Object oldValue = field; 必须在赋值之前执行，否则旧引用就丢了。marking 同样是“只在并发标记阶段才干活”；!isBlack(oldValue) 表示这个即将被断开引用的对象还没被标记完，它可能因此失去最后的可达路径；于是把它塞进 SATB 队列，后续当作存活对象继续标记。这样即使条件 2 真的发生了（灰 → 白断了），那个白色对象也已经被记下来、不会被漏掉。

对比着看，两者的落点恰好相反：

	CMS 增量更新	G1 SATB
拦截哪种修改	新增引用时	删除引用时
拦截时读什么	新值（newValue）	旧值（赋值前先存下来）
命中条件	黑对象 → 白对象	被删的对象还没标黑
动作	把黑对象打回灰色，重新处理	把旧值记入队列，当作存活
破坏的漏标条件	条件 1（黑 → 白）	条件 2（灰 → 白断）
副作用	可能重复标记，但不会有额外垃圾	多标（已死的对象被保住），下轮才回收

写屏障就是那一两行“额外代码”，它在每一次引用赋值时检查并修复三色不变式——并发 GC 的正确性，就藏在这几行不起眼的检查里。

五、一条主线串起整个 Java 系列

三色标记把“并发 GC 的正确性”讲成了一个很具体的故事：标记时对象分三色，并发修改可能打破“黑不指白”的不变式导致漏标，漏标要两个条件同时成立，CMS 和 G1 各破坏一个、用写屏障兜底。

到这里，Java 系列九篇就串成了一条完整的主线：JVM 内存结构讲了对象和变量放在哪、堆是 GC 的主战场；HashMap 讲了堆里的一个具体对象怎么组织；动态代理讲了怎么在运行时生成新的类；volatile 和 JMM 讲了并发下共享数据怎么可见；锁讲了怎么互斥；ThreadLocal 讲了怎么把数据隔离到线程；线程池讲了怎么复用线程；GC 算法和收集器讲了堆怎么回收；三色标记讲了回收时的标记怎么在并发下保持正确。

这条主线从“数据放在哪”走到“数据怎么被回收”，每一篇都是下一块拼图。如果把这个系列当成一张 Java 心智地图，三色标记就是最后落下的那一块——它把“并发”和“GC”这两个最难的领域，用一根“三色不变式”的线缝在了一起。

参考资料

• Uniprocessor Garbage Collection Techniques（Wilson，1992）
• JEP 363：Remove the Concurrent Mark Sweep (CMS) Collector
• Oracle：G1 Garbage Collector
• OpenJDK：G1 SATB 相关源码