面试题：什么是三色标记算法？

三色标记算法（Tri-color Marking Algorithm） 是一种用于垃圾回收的标记算法，主要用于追踪和标记存活对象。它是现代垃圾回收器（如 G1、CMS、ZGC 等）的核心算法之一。三色标记算法通过将对象标记为三种颜色（白色、灰色、黑色）来表示对象的状态，从而高效地完成垃圾回收。

1. 三色标记算法的基本概念

三色标记算法将对象分为三种颜色：

白色：
- 表示对象尚未被垃圾回收器访问过，可能是垃圾。
- 初始状态下，所有对象都是白色。
灰色：
- 表示对象已经被垃圾回收器访问过，但其引用的对象还未被完全扫描。
- 灰色对象是待处理的对象，需要进一步扫描其引用的对象。
黑色：
- 表示对象已经被垃圾回收器访问过，并且其引用的对象也已经被扫描。
- 黑色对象是存活对象，不会被回收。

2. 三色标记算法的过程

三色标记算法的工作过程可以分为以下几个步骤：

(1) 初始标记（Initial Marking）

从 GC Roots（如栈帧、静态变量等）开始，标记所有直接可达的对象为灰色。
这一阶段需要暂停所有用户线程（Stop-The-World, STW），但时间很短。

(2) 并发标记（Concurrent Marking）

从灰色对象开始，递归扫描其引用的对象。
将扫描过的对象标记为黑色，新发现的对象标记为灰色。
这一阶段与用户线程并发执行，不会暂停用户线程。

(3) 重新标记（Remark）

在并发标记阶段，用户线程可能会修改对象的引用关系，导致一些对象被漏标或误标。
重新标记阶段会暂停用户线程，修复这些漏标或误标的对象。
这一阶段是 STW 的，但时间通常比初始标记阶段长。

(4) 并发清除（Concurrent Sweep）

清除所有白色对象（即未被标记的对象），回收它们占用的内存。
这一阶段与用户线程并发执行。

3. 三色标记算法的优势

高效并发：
- 三色标记算法支持并发标记，减少了垃圾回收的停顿时间。
增量标记：
- 可以将标记过程分为多个小步骤，与用户线程交替执行，进一步减少停顿时间。
适应性强：
- 适用于多种垃圾回收器（如 CMS、G1、ZGC 等）。

4. 三色标记算法的挑战

漏标问题（Floating Garbage）：
- 在并发标记阶段，用户线程可能会修改对象的引用关系，导致一些对象被漏标。
- 这些漏标的对象会在下一次垃圾回收中被回收。
误标问题：
- 在并发标记阶段，用户线程可能会将已经标记为黑色的对象重新引用白色对象，导致白色对象被误标为存活。
- 通过重新标记阶段可以修复这一问题。

5. 三色标记算法的应用

三色标记算法广泛应用于现代垃圾回收器中，例如：

CMS（Concurrent Mark-Sweep）：
- 使用三色标记算法进行并发标记和重新标记。
G1（Garbage-First）：
- 使用三色标记算法进行并发标记和重新标记。
ZGC（Z Garbage Collector）：
- 使用三色标记算法进行并发标记，并通过染色指针（Colored Pointers）技术减少停顿时间。

6. 总结

三色标记算法是一种高效的垃圾回收标记算法，通过将对象标记为白色、灰色和黑色来表示对象的状态。它的核心优势在于支持并发标记，减少了垃圾回收的停顿时间，适用于现代垃圾回收器（如 CMS、G1、ZGC 等）。尽管存在漏标和误标的问题，但通过重新标记阶段可以有效地修复这些问题。三色标记算法是现代 JVM 垃圾回收的核心技术之一。

THE END

Java 虚拟机