三色标记法

什么是三色标记法

三色标记法是一种用于垃圾回收的标记算法，它将堆中的所有对象分为三种颜色状态：

• 白色：未被访问的对象，垃圾回收结束后，白色对象将被回收
• 灰色：已被访问但其引用的对象还未完全扫描的对象
• 黑色：已被访问且其引用的所有对象都已扫描完毕的对象

三色标记的基本流程

初始化阶段

在垃圾回收开始时，所有对象都被标记为白色，除了GC Roots（垃圾回收根对象）。
这些根对象被直接标记为灰色，加入到待处理队列中。

标记阶段

标记阶段是三色标记法的核心：

1. 取出灰色对象：从灰色对象队列中取出一个对象进行处理
2. 扫描引用关系：遍历该对象的所有直接引用
3. 标记子对象：将所有被引用的白色对象标记为灰色，并加入待处理队列
4. 完成标记：将当前对象标记为黑色，表示该对象及其所有引用都已完成扫描
5. 重复处理：重复上述步骤，直到灰色对象队列为空

这个过程保证了所有从GC Roots可达的对象最终都会被标记为黑色，而不可达的对象始终保持白色状态。

清理阶段

标记完成后，整个堆中的对象被明确分为两类：

• 黑色对象：所有可达的存活对象
• 白色对象：所有不可达的垃圾对象

垃圾收集器会遍历整个堆空间，回收所有白色对象占用的内存，并将这些内存重新加入到可分配的内存池中。

并发标记的挑战

在并发垃圾回收场景下，用户线程和GC线程同时运行，可能出现以下问题：

漏标问题

当用户线程在GC标记过程中修改对象引用关系时，可能导致本应存活的对象被错误回收。
产生条件：

1. 黑色对象新增了指向白色对象的引用
2. 灰色对象删除了指向该白色对象的引用

错标问题

错标是指本来应该被回收的对象被错误地标记为存活。
产生原因：在并发标记过程中，用户线程可能会删除一些引用关系，使得某些对象实际上已经不可达，但由于已经被标记为灰色或黑色，这些对象在本轮垃圾回收中不会被回收。

解决方案

增量更新

只要发现黑色对象新增了白色对象的引用，会触发一个回调，把这个白色对象重新标成灰色，加入队列，确保它不会被漏掉。

原始快照

• 在标记开始前，记录所有引用关系的“快照”。
• 当任何对象删除对另一个对象的引用时，若被删对象此时为白色，则将其加入灰色队列。

在JVM中的具体实现

G1垃圾收集器

G1 是现在主流的垃圾回收器，特别适合大堆、低延迟的场景。它把堆分成一个个 Region，标记的时候用三色标记 + 原始快照。记录所有被删除的引用，把这些对象加入原始快照队列，等并发标记阶段再处理。最后在最终标记阶段把所有变动补全，确保准确。

CMS垃圾收集器

CMS 是老一代的并发收集器。在重新标记阶段，它用的是增量更新策略：黑色对象新增引用时，把目标对象标记为灰色。