42. 垃圾回收算法：标记清除、分代与增量回收

1. 手动内存管理的困境

C/C++ 把内存释放的责任交给程序员，代价是三类顽固缺陷：内存泄漏（忘记 free）、悬垂指针（释放后仍访问）、双重释放（double free 导致堆破坏）。垃圾回收（Garbage Collection，GC）把「判断对象是否还活着」这件事自动化，用可达性代替人工记账。

但 GC 并非免费午餐：它引入了停顿（Stop-The-World）、吞吐量下降与内存放大。现代 GC 设计的全部张力，就是在「低停顿、高吞吐、省内存」三者之间取舍。

2. 可达性与根集合

GC 的判定标准不是「对象是否被引用计数为 0」，而是「从根集合出发能否到达」。可达即存活，不可达即可回收。

2.1 根集合（Root Set）

根集合包括：

• 线程栈上的局部变量与参数
• 寄存器中的临时引用
• 全局变量与静态字段
• 常量池中的引用
• JNI / native 句柄
• 正在被监视器锁定的对象

2.2 可达性传播

从根出发做图遍历（DFS 或 BFS），标记所有可达对象；未被标记的即垃圾。这一步决定了算法是「追踪式（Tracing）」还是「引用计数式（Reference Counting）」。

根集合
  ├─ 线程栈变量 ──▶ A ──▶ B ──▶ C
  ├─ 静态字段   ──▶ D
  └─ 常量池     ──▶ E
未标记的 F、G 即使互相引用，也整体回收

3. 三种基础回收算法

3.1 标记-清除（Mark-Sweep）

先标记存活对象，再遍历堆释放未标记对象。

3.2 标记-整理（Mark-Compact）

标记后把所有存活对象压缩到堆的一端，消除碎片。

• 优点：无碎片，分配用指针碰撞（bump pointer）极快。
• 缺点：需要移动对象，必须更新所有引用，停顿更长。

3.3 复制（Copying）

把堆分成两块，只用一个；回收时把存活对象复制到另一块，整块清空原半区。

[ 存活 A B C | 垃圾 D E ]  ──复制──▶  [ A B C |              ]
      From 半区                          To 半区（清空 From）

• 优点：无碎片、分配快、回收只遍历存活对象。
• 缺点：空间利用率仅 50%；存活率高时复制开销大。

3.4 三者对比

4. 分代假说与分代回收

4.1 弱分代假说

观察发现：绝大多数对象朝生夕死（弱分代假说），且越老的对象越可能继续存活（强分代假说）。据此把堆分为新生代与老年代，对不同代采用不同算法。

4.2 新生代布局

新生代进一步分为 Eden 与两个 Survivor（S0、S1），默认比例 8:1:1：

新生代 = Eden(8) + S0(1) + S1(1)
- 新对象分配在 Eden
- Minor GC：Eden + S0 的存活对象复制到 S1，然后清空 Eden 与 S0
- 对象每熬过一次 Minor GC，年龄 +1
- 年龄达到阈值（默认 15）晋升老年代
- 大对象直接进入老年代，避免在 Survivor 反复复制

4.3 跨代引用与卡表

老年代对象可能引用新生代对象，若 Minor GC 只扫描新生代，会漏标存活对象。解决方案是记忆集（Remembered Set），用**卡表（Card Table）**把老年代按 512 字节分块，只要块内有指向新生代的引用就标记为脏卡，Minor GC 只需扫描脏卡。

// 写屏障：老年代对象引用被修改时标记脏卡（伪代码）
void oop_field_store(oop* field, oop value) {
    *field = value;
    if (is_old(field) && is_young(value)) {
        card_table.mark_dirty(field); // 记录跨代引用
    }
}

4.4 对象分配：TLAB 与指针碰撞

新生代用指针碰撞分配：维护一个 top 指针，分配即 obj = top; top += size，仅两条指令。为避免多线程争抢，每个线程在 Eden 里预分配一块本地分配缓冲（TLAB，Thread-Local Allocation Buffer），绝大多数分配无需同步。

Eden
[ 已分配 | 线程A TLAB | 线程B TLAB | ... | top ──▶ 空闲 ]

当对象大于 TLAB 剩余空间时，走慢路径：要么在 Eden 新开 TLAB，要么直接在老年代分配（大对象）。

5. 并发与增量回收

5.1 三色标记

把对象抽象为三种颜色，是并发标记的理论基础：

标记从灰集合开始：取出灰色对象，将其引用的白色对象涂灰，自己变黑；灰集合空时，白色即垃圾。

5.2 漏标与读写屏障

并发标记时，用户线程可能同时修改引用，导致漏标（存活对象被误判为垃圾）。漏标需同时满足：黑色对象新增了指向白色对象的引用，且该白色对象到根的所有灰色路径都被断开。

两种屏障方案：

• 增量更新（Incremental Update，CMS 采用）：黑色对象新增对白色的引用时，把该白色记录，重新涂灰。
• SATB（Snapshot-At-The-Beginning，G1 采用）：在标记开始时刻做逻辑快照，只要引用被删除就把旧引用记录下来，保证快照时刻的可达对象全部存活。

增量更新关注「新增引用」：黑色 ──▶ 白色  ⇒ 记录白色
SATB    关注「删除引用」：黑色 ──✗─ 白色  ⇒ 记录白色（旧值）

5.3 并发回收的停顿分解

以 G1 为例，一次回收的停顿被拆成若干短段：

初始标记(STW，短暂) ─▶ 并发标记(与应用并行) ─▶ 最终标记(STW，短暂)
   ─▶ 筛选回收(STW，可并行) 

目标是把单次停顿控制在用户设定的 MaxGCPauseMillis 以内。

5.4 Region 化堆与 G1

G1 把堆切成约 2048 个等大 Region（默认 1~32 MB），每个 Region 动态扮演 Eden、Survivor 或 Old 角色。回收时优先挑选「垃圾最多」的 Region（Garbage-First），因此得名。

堆 = [E][E][S][O][O][E][O][S]...  ← 每个格子是一个 Region
- Young GC：回收全部 Eden + Survivor Region
- Mixed GC：在 Young 之外，额外回收垃圾占比高的 Old Region
- Humongous：超过 Region 一半的大对象单独占用连续 Region

Region 化让 G1 能预测停顿：根据 MaxGCPauseMillis 反推本次最多回收几个 Region。

6. 引用计数与循环引用

引用计数（Reference Counting）为每个对象维护引用数，归零即回收。

# 引用计数的核心：计数归零立即释放
def incref(obj): obj.refcount += 1
def decref(obj):
    obj.refcount -= 1
    if obj.refcount == 0:
        for child in obj.children:
            decref(child)   # 递归释放
        free(obj)

• 优点：回收及时（无长停顿）、增量自然。
• 缺点：无法处理循环引用、每次赋值都要改计数、并发下计数需原子操作。

Python 的做法是「引用计数 + 标记清除兜底」：日常靠计数即时回收，周期性用分代标记清除处理循环垃圾。CPython 的 gc 模块把对象分为三代（gen0/gen1/gen2），阈值由 gc.set_threshold(700, 10, 10) 控制。

6.1 四种引用类型

Java 用引用强度精细控制回收时机，是「追踪式 GC」对引用计数的语义补充：

// 弱引用：key 被回收后条目自动消失，避免长生命周期 Map 泄漏
Map<Key, Value> cache = new WeakHashMap<>();
// 软引用缓存：内存紧张时自动让位
SoftReference<byte[]> ref = new SoftReference<>(loadBigObject());
byte[] data = ref.get(); // 可能返回 null

7. 实战调参

7.1 Go GC

Go 采用并发三色标记 + 混合写屏障，无分代。核心旋钮是 GOGC：

GOGC=100    # 默认：堆增长 100% 时触发 GC
GOGC=200    # 放宽到 200%，吞吐更高、内存占用更大
GOGC=off    # 关闭 GC（仅调试）
GOMEMLIMIT=4GiB   # 软内存上限，配合 GOGC 抑制内存尖峰

Go 1.19 起引入 GOMEMLIMIT，在容器内存受限时比单纯调 GOGC 更稳。

7.2 JVM GC

# G1（默认，适合大堆、低停顿）
java -XX:+UseG1GC -XX:MaxGCPauseMillis=200 \
     -XX:InitiatingHeapOccupancyPercent=45 -jar app.jar

# ZGC（超低停顿，JDK 15+ 生产可用）
java -XX:+UseZGC -XX:+ZGenerational -Xmx16g -jar app.jar

# 查看 GC 日志（JDK 9+ 统一日志）
java -Xlog:gc*,gc+heap=debug:file=gc.log:time,uptime -jar app.jar

7.3 读懂一条 GC 日志

[2.345s][info][gc] GC(12) Pause Young (Normal) (G1 Evacuation Pause)
    145M->32M(512M) 8.213ms

逐段解读：

• GC(12)：第 12 次 GC 事件编号，便于关联同一轮的各阶段。
• Pause Young (Normal)：一次正常的年轻代 STW 回收。
• 145M->32M(512M)：回收前 145 MB、回收后 32 MB、堆总容量 512 MB。
• 8.213ms：本次停顿耗时。

若 FGC 频繁且 O（老年代）回收后仍接近上限，说明存在内存泄漏或晋升过快；若 YGCT 占比高但堆占用不高，则可能是分配速率过大，应优先减少临时对象。

8. GC 性能指标与评估

衡量 GC 不能只看「快不快」，要从三个正交维度评估：

三者不可兼得，称为 GC 三角。此外还应关注：

• 分配速率（Allocation Rate）：MB/s，决定 GC 触发频率。降低分配比调 GC 更有效。
• 晋升速率（Promotion Rate）：对象从新生代进入老年代的速度，过快会频繁触发 Full GC。
• GC 频率与占比：-Xlog:gc 中 GC(n) 的间隔与占比。

# 用 jstat 观察分代容量与 GC 次数（每 1 秒采样一次）
jstat -gcutil <pid> 1000
# S0 S1 E O M CCS YGC YGCT FGC FGCT GCT

诊断思路：先看 FGC 是否频繁（老年代压力），再看 YGCT/YGC（新生代回收效率），最后用堆 dump 定位谁在持续晋升。

9. 常见误区

• 「GC 能防止内存泄漏」：不能。长生命周期容器持有短生命周期对象（如静态 Map 缓存）仍会泄漏。
• 「调大堆就能解决 GC 问题」：堆越大，单次 Full GC 停顿越长，反而更糟。
• 「引用计数比追踪式快」：低负载下是，高并发下原子计数开销与循环引用兜底会抵消优势。
• 「Finalizer 可靠」：不可靠。Java 的 finalize() 已废弃，应改用 Cleaner 或 try-with-resources。

10. 小结

垃圾回收的核心问题链是：如何定义垃圾（可达性分析）→ 如何回收（标记清除/整理/复制）→ 如何降低停顿（分代 + 并发标记 + 屏障）→ 如何调优（GOGC、MaxGCPauseMillis）。三色标记与 SATB 是并发回收的理论骨架，卡表与记忆集让分代回收不必全堆扫描。它与https://plumephp.com/cs-memory-management/的分配策略、https://plumephp.com/cs-process-thread/的线程栈（根集合的主要来源）紧密耦合。

参考文章

• 虚拟内存与页回收：https://plumephp.com/cs-virtual-memory/
• 操作系统整体架构：https://plumephp.com/cs-os-architecture/