三色标记算法通过将对象分为白色、灰色、黑色三种状态，来实现垃圾回收的标记过程，在并发标记场景中，由于用户线程和标记线程同时运行，很容易出现变量漏标的情况，需要特定的机制来规避这个问题。
三色标记算法基础概念
三色标记算法对对象的标记状态定义如下：
- 白色：对象尚未被标记线程访问过，初始状态下所有对象都是白色
- 灰色：对象已经被标记线程访问过，但是该对象引用的其他对象还没有被全部扫描
- 黑色：对象已经被标记线程访问过，且该对象引用的所有对象都已经被扫描完成
标记过程从GC Roots出发，先将GC Roots直接引用的对象标记为灰色，然后不断从灰色对象集合中取出对象，将其引用的白色对象标记为灰色，自身标记为黑色，直到灰色集合为空，剩余的白色对象就是需要回收的垃圾对象。
并发标记漏标问题的产生原因
在并发标记阶段，标记线程和用户线程同时运行，会出现两种破坏三色标记规则的情况，进而导致漏标：
情况一：黑色对象插入了指向白色对象的引用
原本黑色对象不会再次被扫描，如果它新引用了白色对象，而这个白色对象没有被其他灰色对象引用，就会导致该白色对象被漏标，最终被错误回收。
情况二：灰色对象删除了指向白色对象的引用
灰色对象原本引用了某个白色对象，在标记完成前删除了这个引用，同时没有其他灰色或黑色对象引用该白色对象，这个白色对象也会被漏标。
漏标问题的两种解决方案
增量更新（Incremental Update）
增量更新的思路是当黑色对象新插入了指向白色对象的引用时，就将这个新插入的引用记录下来，等并发标记完成之后，再将这些记录过的引用关系中的黑色对象重新标记为灰色，重新扫描一遍。
以下是增量更新记录引用关系的简化代码逻辑：
// 记录新增的引用关系，key是黑色对象，value是该黑色对象新引用的白色对象集合
Map<Object, Set<Object>> newReferenceRecords = new HashMap<>();
// 当黑色对象obj新增对whiteObj的引用时触发
public void onReferenceAdd(Object obj, Object whiteObj) {
// 仅当obj是黑色，whiteObj是白色时才记录
if (isBlack(obj) && isWhite(whiteObj)) {
Set<Object> refs = newReferenceRecords.getOrDefault(obj, new HashSet<>());
refs.add(whiteObj);
newReferenceRecords.put(obj, refs);
}
}
// 重新标记阶段处理记录的新引用
public void processNewReferences() {
for (Map.Entry<Object, Set<Object>> entry : newReferenceRecords.entrySet()) {
Object blackObj = entry.getKey();
// 将黑色对象重新标记为灰色
markGray(blackObj);
// 扫描其引用的白色对象
for (Object whiteObj : entry.getValue()) {
markGray(whiteObj);
}
}
}
原始快照（Snapshot At The Beginning，SATB）
原始快照的思路是当灰色对象要删除指向白色对象的引用时，就将这个要删除的引用记录下来，并发标记结束后，再将这些记录下来的引用关系中，被删除引用的白色对象标记为灰色，保证这些对象不会被漏标。
以下是原始快照记录引用删除的简化代码逻辑：
// 记录删除的引用关系，key是灰色对象，value是该灰色对象删除引用的白色对象集合
Map<Object, Set<Object>> deletedReferenceRecords = new HashMap<>();
// 当灰色对象obj删除对whiteObj的引用时触发
public void onReferenceDelete(Object obj, Object whiteObj) {
// 仅当obj是灰色，whiteObj是白色时才记录
if (isGray(obj) && isWhite(whiteObj)) {
Set<Object> refs = deletedReferenceRecords.getOrDefault(obj, new HashSet<>());
refs.add(whiteObj);
deletedReferenceRecords.put(obj, refs);
}
}
// 重新标记阶段处理记录删除的引用
public void processDeletedReferences() {
for (Map.Entry<Object, Set<Object>> entry : deletedReferenceRecords.entrySet()) {
for (Object whiteObj : entry.getValue()) {
// 将被删除引用的白色对象标记为灰色
markGray(whiteObj);
}
}
}
两种方案的对比
两种方案各有适用场景，具体差异如下：
| 对比维度 | 增量更新 | 原始快照 |
|---|---|---|
| 核心思路 | 关注黑色对象的新增引用 | 关注灰色对象的引用删除 |
| 重新标记开销 | 需要重新扫描新增引用的黑色对象及其引用链 | 仅需要扫描被删除引用的白色对象 |
| 适用场景 | 引用新增操作较多的场景 | 引用删除操作较多的场景 |
| 典型应用 | CMS垃圾回收器的并发标记阶段 | G1垃圾回收器的并发标记阶段 |
实际应用注意事项
在实际的垃圾回收器实现中，还需要配合写屏障来捕获引用变化的操作，保证新增或删除的引用能被正确记录。同时，重新标记阶段通常是需要停顿用户线程的，因此要尽量减少重新标记的范围，降低对应用性能的影响。
如果应用中出现频繁的漏标导致的对象误回收问题，可以先排查是否是垃圾回收器的漏标处理机制没有正确开启，或者是否自定义了特殊的引用处理逻辑破坏了默认的标记规则。