垃圾回收算法#

一句话答案#

三种基础算法：标记-清除（碎片）、复制（浪费空间）、标记-整理（移动开销），分代收集结合使用。

阶段1 标记：从 GC Root 出发，标记所有可达对象
阶段2 清除：回收未被标记的对象（不可达对象）

内存布局示意（O=存活, X=待回收, _=空闲）：
回收前：[O][X][O][O][X][X][O]
回收后：[O][_][O][O][_][_][O]  ← 碎片化！

将内存分为两半（from 区 / to 区）
标记：标记 from 区存活对象
复制：将存活对象紧密地复制到 to 区
清空 from 区，交换 from 和 to 角色

from：[O][X][O][O][X][X][O]
to（复制后）：[O][O][O][O]______  ← 无碎片！

标记：标记所有存活对象
整理：将存活对象向一端移动，然后直接清除边界以外的内存

整理后：[O][O][O][O]___________  ← 无碎片，利用率100%

三色标记与并发漏标（闭环主线）#

上面三种算法都默认”标记时世界静止”。但 CMS/G1 的并发标记要让用户线程和标记线程同时跑，对象图会被边标记边修改——这就引出了三色标记法和漏标问题。这是 JVM 并发 GC 最核心的一条线。

1. 三色定义（按”扫描进度”给对象染色）

并发标记如何推进：

• 初始：GC Roots 直接引用的对象置灰，其余全白。
• 推进：从灰色集合取一个对象，把它引用的白色对象染灰，自己扫完后转黑（灰→黑）。
• 结束：灰色集合为空，所有可达对象变黑，剩下的白色对象即垃圾。
• 本质是一次广度/深度优先遍历，灰色是黑白之间的”扫描波面”。

2. 漏标的两个充要条件（必须同时满足，缺一不漏标）

并发期间用户线程改引用，可能导致一个本应存活的白对象被错杀（漏标）。漏标当且仅当同时满足：

条件①：黑对象新增了一条指向某白对象的引用（黑已扫完不会再看它的引用，新引用发现不了）。 条件②：该白对象与所有灰对象之间的引用关系全部被破坏（没有任何灰对象能再触达它）。

• 直觉：白对象唯一的”活路”是被某个还没扫完的灰对象引用到。只要还有一个灰对象引用它（条件②不满足），迟早会被扫到、染灰、存活。
• 只要还没扫到它的黑对象其实没新增引用（条件①不满足），它就和这次快照无关。
• 两条同时成立，白对象既够不到灰、又只挂在已扫完的黑下面 → 永远不会被染色 → 被错误回收。

3. 两种解法，各破坏一个条件（不能搞反！）

• 增量更新（CMS）：盯条件①。一旦黑对象插入对白对象的新引用，写屏障把这个黑对象记下来，remark 时重新扫描它，相当于让它”退回灰色”。
• SATB（G1）：盯条件②。一旦灰/白对象的某条引用被删除（覆盖），写屏障把被删除的那个旧引用推进 SATB 缓冲区，相当于”保留标记开始那一刻的快照”，凡是快照里活着的就当它活着标记。这样即使条件②被破坏（引用被删），旧引用记录仍能让白对象被标活。
• 代价对症：SATB 按快照标记，会把”标记期间本已死掉”的对象也保活 → 这批就是浮动垃圾，留待下次 GC；但它 remark 只需处理缓冲区，停顿短。增量更新不产生这类浮动垃圾，但 remark 要重新扫描黑对象，停顿相对长。

4. 写屏障（Write Barrier）如何拦截

• 写屏障是 JVM 在对象引用字段赋值（如 obj.field = other）时，由 JIT 在赋值指令前后插入的一小段代码（不是硬件内存屏障，是 GC 用的”切面/钩子”）。
• 增量更新用写后屏障：赋值后，若是黑对象新指向白对象，记录该黑对象。
• SATB 用写前屏障：赋值前先把字段的**旧值（即将被覆盖的旧引用）**记入 SATB 缓冲区，再执行赋值。
• 代价：每次引用写入都多几条指令，是并发 GC 换取低停顿付出的吞吐成本。

横向：CMS收集器 用增量更新（破坏条件①）；G1收集器原理 用 SATB（破坏条件②）。