什么是三色标记算法？

回答重点

三色标记算法 是现代垃圾回收器中常用的一种 增量标记算法，它通过“白-灰-黑”三种颜色标记对象的状态可以与应用线程并发执行的同时确保程序的内存管理安全。

它用于标记哪些对象需要被回收，哪些对象需要保留，减少一次性停顿带来的性能影响。非常适合 低延迟 和 实时垃圾回收 的场景。

它通过将对象分为三种颜色来进行标记和追踪。

三色标记的基本概念：

• 白色对象：表示还没有被垃圾回收器访问到的对象，这些对象有可能是垃圾。
• 灰色对象：表示已经被访问到，但其引用的其他对象还没有被处理完。
• 黑色对象：表示已经被访问到且其引用的所有对象也都已经标记完毕，这些对象不会被回收。

标记过程：

• 初始状态：所有对象都是白色。
• 标记阶段：从 根对象（GC Roots） 开始，把根对象变为 灰色，然后递归扫描所有灰色对象，将其引用的对象变成灰色，标记为 “已访问”。当灰色对象的所有引用都处理完毕时，灰色对象会变成 黑色。
• 最终状态：经过扫描，所有存活的对象最终都会变成 黑色，未被访问的白色对象即为垃圾，会被清除。

以下动图来自维基百科 ：

扩展知识

通俗解释什么是三色标记算法

想象你是一个房东，想要检查房子里哪些房间还在用，哪些可以腾空清理。房子里有很多房间，每个房间可能会有钥匙通往其他房间。为了高效地完成这项工作，你决定采用以下步骤：

1）三种颜色的便签纸：

• 白色：代表房间还没检查，可能是空房，待清理。
• 灰色：代表房间已经进去了，但它里面可能还有钥匙通往其他房间，检查未完成。
• 黑色：代表房间已经检查完了，确定还在用。

2）检查流程：

• 一开始，所有房间都贴白色便签。
• 从房东的起点（比如客厅），贴灰色便签，开始检查。
• 每到一个灰色房间，把里面的所有钥匙对应的房间改为灰色，同时把当前房间改成黑色。
• 重复以上步骤，直到所有灰色房间都变成黑色。

3）清理房间：

• 最后，所有还贴着白色便签的房间都没人用，可以腾空清理。

如果没有三色标记算法会怎么样？

假如没有三色标记算法，垃圾回收可能遇到以下问题：

1）误回收（丢东西）：

• 如果房东在检查过程中，不记录哪些房间已经检查过，可能会把仍然有人用的房间误认为是空房间，从而错误地清理掉。

2）程序停顿时间过长：

• 不用三色标记算法的垃圾回收通常需要“暂停整个程序”（Stop-The-World，STW），从头到尾一次性检查所有内存对象，程序无法并行工作，用户可能会感受到明显的卡顿。

3）低效处理引用关系：

• 如果房间之间的钥匙（即对象之间的引用）特别复杂，比如一个房间有很多钥匙通往其他房间，或者房间之间形成循环引用，垃圾回收会变得非常难以高效完成。

所以三色标记算法带来的好处是：

1. 可并发执行：垃圾回收器可以和程序同时工作，而不需要完全停止程序运行（只需要短暂的暂停）。
2. 避免误回收：通过颜色标记，可以确保垃圾回收器不会回收那些还有其他房间钥匙指向的对象。
3. 效率高：三色标记算法分阶段处理不同对象，避免了一次性全量检查的开销。

三色标记中漏标和多标问题

首先了解一个 GC 专业名词，在垃圾收集场景下将应用程序称为 mutator。

漏标问题来看下图。

第一个阶段搜索到 A 的子对象 B了，因此 A 被染成了黑色，B 为灰色。此时需要搜索 B。

但是在 B 开始搜索时，A 的引用被 mutator 换给了 C，然后此时 B 到 C 的引用也被删了。

接着开始搜索 B ，此时 B 没有引用因此搜索结束，这时候 C 就被当垃圾了，因此 A 已经黑色了，所以不会再搜索到 C 了。

这就是出现漏标的情况，把还在使用的对象当成垃圾清除了，非常严重，这是 GC 不允许的，宁愿放过，不能杀错。

还有一种情况多标，比如 A 变成黑色之后，根引用被 mutator 删除了，那其实 A 就属于垃圾，但是已经被标记为黑色了，那就得等下次 GC 清除了。

这其实就是标记过程中没有暂停 mutator 而导致的，但这也是为了让 GC 减少对应用程序运行的影响。

多标其实还能接受，漏标的话就必须处理了，我们可以总结一下为什么会发生漏标：

1. mutator 插入黑色对象 A 到白色对象 C 的一个引用
2. mutator 删除了灰色对象 B 到白色对象 C 的一个引用

只要打破这两个条件任意一个就不会发生漏标的情况。

这时候可以通过以下手段来打破两个条件：

利用写屏障在黑色引用白色对象时候，将白色对象置为灰色，这叫增量更新。

利用写屏障在灰色对象删除对白色对象的引用时，将白色对象置为灰，其实就是保存旧的引用关系。这叫STAB（snapshot-at-the-beginning）。

三色标记问题总结：

• 漏标问题：如果某个白色对象被黑色对象直接引用，但在标记阶段未被扫描，可能会被错误地认为是垃圾。写屏障通过跟踪修改，避免这种情况发生。
• 冗余标记问题：有些对象可能在标记结束后被标记为灰色，但实际已经不再被使用，这种对象在下一次 GC 时仍然会被扫描。虽然会影响效率，但不影响正确性。

垃圾回收器的三色标记算法应用

• CMS（Concurrent Mark-Sweep）和 G1 GC 都使用了三色标记算法，因为它能够在 并发环境 下执行垃圾回收，不影响应用程序的正常运行。