企业官网建设流程全解析

三色标记算法详解（面试题）

本文档涵盖以下面试题，逐题给出详细答案：

1. 三色标记算法了解吗？

1. 三色标记优点？

1. 标记过程？

1. 产生的问题？

一、三色标记算法了解吗？

1.1 什么是三色标记算法

三色标记算法（Tri-color Marking）是一种并发垃圾标记算法，最早由 Dijkstra 等人提出。它的核心思想是：在 GC 标记阶段，将堆中的所有对象分为三种颜色，通过颜色的流转来追踪对象的存活状态，从而在不停止用户线程（或极短停顿）的情况下完成对象可达性分析。

三色标记是现代垃圾收集器（如 CMS、G1、ZGC、Shenandoah）实现并发标记的理论基础。

1.2 三种颜色的定义

1.3 颜色流转规则

初始状态：所有对象为白色 ↓ GC Root 直接引用的对象 → 变为灰色 ↓ 从灰色集合中取出一个灰色对象 → 扫描其引用的所有白色对象 → 被引用的白色对象变为灰色 → 该对象自身变为黑色 ↓ 重复上述过程，直到灰色集合为空 ↓ 标记结束：黑色对象 = 存活对象，白色对象 = 可回收对象

核心不变式（三色不变性 / Tri-color Invariant）：

强三色不变性：黑色对象永远不能直接指向白色对象（不允许黑色→白色引用存在）。

弱三色不变性：黑色对象可以指向白色对象，但前提是存在一条从灰色对象出发、经过若干黑色对象到达该白色对象的路径（即白色对象被灰色对象间接保护）。

只要满足上述任一不变性，就能保证标记的正确性——所有存活对象都不会被误回收。

二、三色标记优点？

2.1 支持并发标记，大幅降低 STW 时间

这是三色标记最核心的优点。传统的标记-清除算法需要在 STW（Stop-The-World）期间完成全部标记工作，应用线程必须暂停。而三色标记算法允许 GC 线程与用户线程并发执行：

• 标记阶段大部分时间不需要暂停用户线程
• 只需在初始标记（标记 GC Roots 直接引用）和最终标记（处理并发期间的引用变更）这两个极短阶段暂停

这使得 CMS、G1 等收集器能够实现低延迟垃圾回收，适用于对响应时间敏感的在线服务。

2.2 算法正确性有理论保证

三色标记通过三色不变式提供了严格的理论正确性保证：

• 只要不变式成立，就不会把存活对象误判为可回收对象
• 不会发生"漏标"（即不会漏掉存活对象的标记）
• 可以安全地回收所有白色对象

2.3 适用于分代收集和 Region 级收集

三色标记不依赖整个堆的快照，而是逐个对象追踪引用关系，因此：

• G1可以在 Region 级别进行并发标记，不需要扫描整个堆
• ZGC / Shenandoah可以实现染色指针（colored pointer）来记录对象颜色状态，进一步降低停顿
• 适用于增量式标记（incremental marking）——标记工作可以分多次小批量完成

2.4 内存开销可控

三色标