JVM三色标记垃圾回收算法详解
三色标记算法是现代JVM垃圾回收器(如G1、Shenandoah、ZGC等)中使用的核心算法之一，用于高效地标记存活对象。下面我将详细解释这一算法的工作原理。
基本概念
三色标记算法将对象按照颜色分为三类：
- 白色(White)：初始状态，表示对象未被访问过(即未被标记)，可能是垃圾
- 灰色(Grey)：表示对象已被标记，但其引用的对象还未被检查
- 黑色(Black)：表示对象及其所有引用的对象都已被标记，是确定存活的对象
算法工作流程
- 初始阶段：
- 所有对象初始为白色
- 从GC Roots(栈、寄存器、静态变量等)出发，将直接可达的对象标记为灰色
- 标记阶段：
- 从灰色集合中取出一个对象：
- 将其引用的所有白色对象标记为灰色
- 将该对象本身标记为黑色
- 重复上述过程，直到灰色集合为空
- 回收阶段：
- 所有黑色对象为存活对象
- 所有白色对象为垃圾对象，可被回收
算法伪代码表示
// 初始化
for (obj in roots) {obj.color = GREY
}// 标记阶段
while (!greySet.isEmpty()) {obj = greySet.remove()for (ref in obj.references()) {if (ref.color == WHITE) {ref.color = GREYgreySet.add(ref)}}obj.color = BLACK
}// 回收阶段
for (obj in heap) {if (obj.color == WHITE) {free(obj)}
}并发标记与三色不变式
当垃圾回收器需要与用户线程并发执行时，可能出现对象引用关系变化的问题。为确保正确性，必须维护以下两个不变式之一：
- 强三色不变式：黑色对象不能直接引用白色对象
- 解决方案：增量更新(Incremental Update)
- 当黑色对象引用白色对象时，将黑色对象重新标记为灰色
- 弱三色不变式：黑色对象可以引用白色对象，但必须存在灰色对象到该白色对象的可达路径
- 解决方案：原始快照(Snapshot At The Beginning, SATB)
- 记录引用关系变化前的状态，确保不遗漏标记
实际应用
- CMS收集器：使用写屏障实现增量更新
- G1收集器：使用原始快照(SATB)方式
- Shenandoah/ZGC：使用更复杂的读/写屏障实现并发标记
优点
- 可以高效地并行或并发执行
- 通过颜色标记可以清晰地表示对象状态
- 适合现代大内存应用的垃圾回收需求
局限性
- 需要额外的空间存储颜色信息(通常利用对象头中的标记位)
- 并发标记时需处理对象图变化带来的复杂性
- 写屏障可能带来一定的运行时开销
三色标记算法是现代垃圾回收技术的基石，使得JVM能够在几乎不影响应用线程的情况下完成垃圾回收工作。
)
