06-垃圾收集底层算法

type

status

date

slug

summary

1️⃣ 三色标记

三色标记算法（Tri-color Marking Algorithm）是一种常用于垃圾回收（Garbage Collection）的标记策略，尤其是在增量式（Incremental）或并发式垃圾回收器中。该算法用于解决在垃圾回收过程中，程序仍在运行（即 mutator 仍在修改对象图）时如何正确标记可达对象的问题。

初始化： 将根对象（GC Roots）标记为灰色，放入灰色集合。

遍历灰色对象：

从灰色集合中取出一个对象o。
将o所引用的白色对象标记为灰色，并加入灰色集合。
将o标记为黑色。

重复步骤 2，直到灰色集合为空。

回收所有白色对象。

三色标记的优势

能适应增量或并发回收场景，GC暂停时间更短。

通过写屏障确保并发修改的引用也能被正确扫描。

是现代垃圾回收器（如 Java 的 G1、ZGC、Shenandoah）中标记阶段的基础算法。

颜色	含义
白色（White）	还未访问过的对象，可能是垃圾（最终将会被回收）。
灰色（Gray）	已经访问过自身，但其引用的对象尚未全部访问。
黑色（Black）	自身已访问完毕，且其引用的对象也都已经访问过。

1. 多标-浮动垃圾

1️⃣ 多标（Over-marking）

定义： 某个对象在 GC 标记阶段被标记了多次，或其实已经是不可达对象，却因为并发写屏障的作用被错误标记为可达。

原因： 多数情况下由于保守策略（为了避免漏标），写屏障可能会将某些其实不可达的对象错误地加入灰色集合。

影响： 多标不会导致程序错误，只是导致 本应被回收的对象暂时无法被回收，造成 浮动垃圾。

2️⃣ 浮动垃圾（Floating Garbage）

定义： 在并发标记过程中产生的、已经不可达但因为某种原因没有被及时回收的垃圾对象。

产生原因：

在并发标记过程中，mutator 删除了对某个对象的最后引用，但 GC 由于“没有看到”这个变化，仍然认为该对象是活的。

为了不阻塞程序，GC 不会暂停整个程序来精准捕捉这些变化。

为保证安全，GC 保守地认为这些对象可能仍然活着，于是不会回收。

特征：

浮动垃圾通常会在下一轮 GC 中被清理。

是并发回收器设计中允许且预期的现象。

2. 漏标-读写屏障

1️⃣ 漏标（Under-marking）

定义： 垃圾回收器错误地遗漏了某个可达对象的标记，最终将其错误地当成垃圾而回收。

影响： 漏标是严重的错误，会导致程序访问已经回收的对象，出现 悬空引用（dangling pointer） 或 崩溃（如 JVM 崩溃）。

产生原因：

三色标记算法在并发标记期间，如果不使用写屏障，会出现下面这种场景：

GC 把对象 A 标为黑（已处理完）
mutator 将 A 的字段指向对象 B（白）
GC 已经处理过 A，不会再扫描 B，B 将被误认为垃圾

2️⃣ 读写屏障（Read/Write Barrier）

定义： 是插入在对象字段访问或修改前的指令，用于在 GC 过程中对对象图变更进行监控，从而避免漏标。

常见屏障类型：

屏障类型	时机	常见用途
写屏障	在对象引用被修改时执行	解决三色标记期间的漏标问题
读屏障	在读取对象引用时执行	ZGC、Shenandoah 等用于“颜色指针”或“转发指针”的一致性维护

概念	定义	影响	关系
多标	不必要的重复标记	内存回收不充分	引入写屏障时可能过度保守引起
浮动垃圾	暂时无法回收的垃圾对象	内存暂时增加	并发标记容忍的结果；多标导致浮动垃圾
漏标	可达对象被错误回收	严重错误，程序崩溃	写屏障或读屏障的目标是防止漏标
写/读屏障	监控字段修改/访问	保证并发GC正确性	解决三色标记下的并发修改问题

在并发或增量 GC 中，mutator（程序线程）可能会在 GC 扫描对象图的同时修改引用关系。可能会出现这样的问题：

已经扫描过一个对象A，并把它变成了黑色

mutator 接着把对象A的引用指向了一个白色对象B

对象B就永远不会被扫描了 —— 这会导致误删活对象！

3. 解决方案：写屏障（Write Barrier）

为了解决上面的问题，三色标记算法引入了写屏障机制，常见的有两种策略：

1️⃣ 插入屏障（Insertion Barrier）

在 mutator 添加新引用时，强制将目标对象 B 标记为灰色，重新加入扫描：

2️⃣ 删除屏障（Deletion Barrier）

当 mutator 删除引用时，保守地将源对象重新标记为灰色：

垃圾收集器处理方案

CMS：写屏障 + 增量更新 G1，Shenandoah：写屏障 + SATB ZGC：读屏障

2️⃣ 记忆集与卡表

1.记忆集（Remembered Set）

记忆集是一种辅助数据结构，用来记录从老年代（Old Generation）对象指向新生代（Young Generation）对象的引用。在垃圾回收时，特别是进行 Minor GC（即只回收新生代）时，为了避免扫描整个老年代，记忆集可以快速定位老年代中指向新生代的引用对象。

当老年代中的某个对象的字段指向了新生代对象（即跨代引用）时，JVM 会将这个引用信息加入到记忆集中。

垃圾收集器在回收新生代时，只需扫描记忆集中记录的老年代对象，而不必全盘扫描老年代。

2.卡表（Card Table）

将堆内存划分为若干个固定大小的区域（称为 卡片 card，典型大小是 512 字节）；

为每个 card 分配一个字节，用于记录该区域是否可能包含指向新生代的引用；

0: 表示对应的内存区域没有发生修改。
1 或 1: 表示该区域可能有跨代引用。

这个记录数组就是卡表（Card Table）本身，是一块紧凑的、连续的内存结构。

例如，如果堆大小为 1 GB，划分为 512 字节一个 card，总共就有约 2M 个 card，对应卡表长度约 2MB。

卡表的更新由写屏障（Write Barrier）实现：

当程序执行类似 object.field = newValue 的写操作时：

JVM 会检查这次写操作是否是老年代对象指向新生代对象；

如果是，则通过写屏障逻辑，将目标地址所在的 card 对应的卡表位置设置为“脏”（dirty）；

后续 GC 可以根据卡表中被标记的区域，快速扫描那些可能含有跨代引用的对象。

如何与写屏障结合

当一个字段发生写操作时（例如某个对象字段从原来的引用指向了另一个对象），写屏障（Write Barrier）机制会被触发，并把对应 card 的状态标记为“脏”（dirty），从而更新卡表。

3️⃣ 三者之间的关系

写屏障：负责在对象字段写操作时通知 JVM，有跨代引用发生。

卡表：记录堆中哪些区域可能含有跨代引用。

记忆集：逻辑上的集合，用于 Minor GC 时快速获取所有跨代引用的来源对象。其底层常通过卡表实现。