#CMS 并发标记与三色标记

候选人小庞在面试蚂蚁 P7 时，面试官问道：

"三色标记法是什么？为什么并发标记时可能会漏标对象？"

小庞说："有白灰黑三种颜色..."面试官追问："CMS 怎么解决漏标问题？"

小庞答不上来...

#一、核心问题：三色标记与漏标 🔴

#1.1 问题拆解

第一层：三色定义（什么是？）
  "三色标记法中，白/灰/黑色对象分别是什么？"
  考察点：初始标记/扫描过程/完成标记

第二层：漏标原因（怎么漏？）
  "并发标记时为什么会漏标对象？什么情况下发生？"
  考察点：灰色对象到白色对象的引用消失

第三层：解决方案（怎么解决？）
  "CMS 和 G1 分别用什么方案解决漏标？"
  考察点：增量更新 vs SATB

#1.2 ❌ 错误示范

候选人原话 A："并发标记时，三色标记保证不会漏标。"

问题诊断：三色标记本身不能保证并发正确性。需要额外的解决方案（增量更新或 SATB）。

候选人原话 B："CMS 和 G1 用的是同一种方案。"

问题诊断：CMS 使用增量更新，G1 使用 SATB（Snapshot-At-The-Beginning）。

#1.3 标准回答

#P5 级别：三色定义

三色标记法（Tri-Color Marking）：

graph TD
    W[白色对象<br/>未被扫描] -->|扫描后变为灰色| G[灰色对象<br/>已发现但未扫描完成]
    G -->|扫描完成后变为| B[黑色对象<br/>已完全扫描]

    G -->|灰色对象引用白色| W2[白色对象<br/>被灰色对象引用]
    W2 -->|浮动垃圾| GZ[浮动垃圾<br/>并发清除时被回收]

颜色	含义	状态
白色	未被 GC 发现的对象	不可达对象，将被回收
灰色	GC 已发现但尚未完成扫描的对象	正在处理中
黑色	已完成扫描的对象	确定存活

#P6 级别：漏标的原因

漏标的两个必要条件：

1. 灰色对象到白色对象的引用被删除
2. 灰色对象到白色对象之间插入了新的引用（或其他灰色对象指向了该白色对象）

具体场景：

// 并发标记阶段（GC 线程和用户线程同时运行）
Object A = new Object();  // A 是灰色
Object B = new Object();  // B 是白色

// GC 线程看到：A → B（A 引用 B）

// 用户线程执行：
A.ref = null;            // 步骤 1：删除 A → B 引用
// 此时 B 还是白色（因为 A 是灰色，只扫描了 A 的引用）

// 另一个用户线程执行：
C.ref = B;              // 步骤 2：新增 C → B 引用（C 是黑色）
// B 本应该是灰色，但现在被跳过了

// 结果：B 被误标为白色，在并发清除时被回收

CMS 的解决方案：增量更新（Incremental Update）：

当一个黑色对象新增指向白色对象的引用时，将这个引用记录下来。在重新标记阶段，重新扫描这些被记录的黑色对象。

#P7 级别：SATB vs 增量更新

CMS：增量更新（Incremental Update）：

• 记录黑色 → 白色的新增引用
• 重新标记时，从这些黑色对象重新出发扫描
• 优点：更保守（不会漏标）
• 缺点：需要额外扫描（可能多扫描已确认存活的对象）

G1：SATB（Snapshot-At-The-Beginning）：

SATB 在并发标记开始时创建堆内存的快照，所有在快照中存在的引用关系都被视为"有效"：

• 在并发标记期间，灰色 → 白色的引用被删除时，将这个关系记录
• 删除的白色对象被视为"在快照中存活"
• 重新标记时，扫描这些被记录的白色对象

SATB 的特点：

• 更快的重新标记（只需要处理被删除的引用）
• 更保守（可能产生浮动垃圾，因为快照中存在的引用被保留）

// SATB 写屏障的实现
// 当灰色 → 白色 引用被删除时：
void writeBarrier(object, field, newValue) {
    if (object is black && field is white) {
        enqueue(object.field);  // 记录到 SATB 队列
    }
}

【面试官心理】 这道题我能问到 P7 级别，是因为 SATB vs 增量更新是现代 GC 设计的核心技术差异。能说清两者原理的候选人说明他理解了并发 GC 的理论挑战。

#1.4 追问升级

追问：为什么 G1 选择 SATB 而不是增量更新？

G1 使用 SATB 是因为 SATB 的重新标记阶段更快（只需扫描被删除的引用）。G1 的目标是可预测的停顿时间，SATB 更适合这个目标。但代价是会产生更多浮动垃圾。

#二、生产避坑 🟢

#2.1 并发标记期间的写屏障开销

# 写屏障（Write Barrier）的开销
# 每次对象字段赋值都需要触发写屏障
# G1 的 SATB 写屏障开销约 1~5%

#2.2 浮动垃圾的影响

CMS 和 G1 都会产生浮动垃圾。浮动垃圾在下次 GC 时被回收，不会造成内存泄漏，但会增加 GC 频率。