---
title: 垃圾回收
url: https://doc.liz6.com/compilers/07-runtime/01-garbage-collection
locale: zh
area: compilers
tags:
- compilers
- 运行时
date: 2026-06-30
modified: 2026-06-30
description: 运行时自动判定哪些对象不再可达并回收——从 mark-sweep 到分代到并发三色标记,每种 GC 算法都在吞吐和延迟之间取不同的平衡点,而 write barrier 必须由编译器嵌入到每处指针写入。
---

# 垃圾回收

> 运行时自动判定哪些对象不再可达并回收——从 mark-sweep 到分代到并发三色标记,每种 GC 算法都在吞吐和延迟之间取不同的平衡点,而 write barrier 必须由编译器嵌入到每处指针写入。

## 概述

手动内存管理(C/C++ 的 `malloc`/`free`,Rust 的所有权系统)把释放内存的责任放在程序员或类型系统上。垃圾回收(GC)换了一条路:**运行时自动判定哪些对象不再可达,回收它们占用的内存**。GC 是所有带 GC 的语言(JVM/Go/.NET/JS/Python)的运行时基础——编译器不仅要生成代码,还要在生成代码里**嵌入 GC 协作点**(safepoint、write barrier),这篇讲四个核心 GC 算法和它们给编译器施加的要求。

## 核心概念:可达性与根集

GC 的基础问题是:**哪些对象还是活的**?定义:从**根集(root set)**——全局变量、栈上的局部变量、寄存器——出发,通过指针能到达的所有对象是活的;其余是垃圾。

```
根集 = {全局变量, 各线程的栈上的每个 word, 活跃寄存器}
从根集出发, BFS/DFS 追踪指针 → 到达的对象标记为 live
未到达的 → 垃圾, 可回收
```

任何 GC 都做这个遍历。区别在于**什么时候做、怎么回收未到达的对象、以及对 mutator(应用程序代码)的影响**。

## 四个核心算法

### 1. Mark-Sweep:基础

```
mark 阶段:
  从根集出发, 遍历对象图, 对每个到达的对象设置 mark-bit

sweep 阶段:
  遍历整个堆, 回收所有未标记的对象, 清空 mark-bit (为下一轮)
```

- 代价:mark 阶段遍历活对象的量;sweep 遍历整个堆(含死对象),大量未使用内存也要扫。
- 不移动对象 → 无需更新指针 → 简单,适合 C/C++ 这类不能移动对象的语言(如 Boehm GC)。
- 致命缺陷:**碎片化**——分配和回收交替进行,堆逐渐碎成小块,即使总空闲足够,大对象也可能分配失败。

### 2. Copying (Semispace, Cheney):用空间换时间和紧凑

把堆分成两半(from-space 和 to-space),任何时刻只用一半:

```
收集:
  从根集出发, BFS/DFS 遍历活对象
  把活对象从 from-space 复制到 to-space (紧凑地排在一端)
  更新所有指向这些对象的指针 (从旧地址 → 新地址)
  回收整个 from-space (对 OS 来说就是一大块内存)
  from 和 to 角色互换
```

- **紧凑(compaction)**——活对象被紧密排布,没有碎片。
- 遍历过程就是 BFS − Cheney 的 copying collector 用 BFS 遍历,同时自然做到了紧凑。
- 代价:**只用一半堆**,内存利用率 50%。对带 GC 的语言(JVM, Go),这个代价换来无碎片 + 分配只挪指针(bump allocator),取舍值得。

### 3. Generational GC:利用"大多数对象早死"

经验观察(weak generational hypothesis):**绝大多数对象在分配后很快就变成垃圾**(如循环体里分配的临时对象);少数活久的对象倾向于继续活下去。

分代 GC 把堆分成**年轻代(nursery)**和**老年代(tenured)**:

```
年轻代: 频繁收集(如每几 MB 分配就触发), 用 copying——活下来的少, 复制代价低
老年代: 低频收集(如内存快满才触发), 用 mark-sweep 或 mark-compact
对象在年轻代活过 N 次收集 → 晋升到老年代
```

关键工程:**跨代引用**。老年代对象指向年轻代对象时,只扫年轻代会漏掉这条引用(因为根集不包括老年代)。解法:老年代有个 **remembered set**——记录"哪些老年代卡片(card)可能含指向年轻代的指针"。年轻代 GC 时,remembered set 中的老年代卡片被加到根集。

### 写入屏障(write barrier):维护跨代引用

每次指针写入(`*p = q`)被编译器插入一段小代码:

```
write_barrier(p, q):
    if p 在老年代 and q 在年轻代:
        标记 p 所在的 card 为 dirty → GC 会扫这块
    *p = q
```

这个屏障直接由**编译器在每次指针写入时生成**——不是在运行时解释执行,而是作为机器码嵌入。JVM 的 G1/Shenandoah、Go 的 GC、V8 的 Oilpan,都靠编译器插入 write barrier。

编译器优化对 write barrier 友好:如果编译器能证明 p 是刚分配的(一定在年轻代),就跳过 barrier;如果在循环里同一 p 写多次,编译器可能只保留第一次 barrier(后续写不改变 card 状态)。

## 并发 GC:mutator 不暂停(或短暂停)

mark-sweep 和 copying 都要求"扫描时 mutator 不能修改对象图"——这意味 **stop-the-world(STW)** 暂停。现代 GC 的大部分工作允许与 mutator 并发运行:

### 三色不变量(tri-color invariant)

并发 mark 算法的理论基础,把对象分三类:

- **白色**:尚未被标记(初始状态,也可能是垃圾)
- **灰色**:已被标记,但其内部的指针还未扫描(在 worklist)
- **黑色**:已被标记且所有内部指针已被扫描

**不变量:在 mark 结束时,没有任何黑色对象持有指向白色对象的指针。** 一旦这个不变量被违反(如 mutator 把白色对象指针写到已标记完成的黑色对象里),那个白色对象就可能被漏标→被错误回收。

维持不变量的方式:要么**在扫描过程中拦截破坏不变量的写**(用 write barrier 捕获"黑→白"的指针联系),要么**允许短暂漏标,后续 fix-up**(当 mutator 写 `p.field = q` 且 p 是黑色,q 是白色,把 q 标记为灰色重新入队)。Go 的 GC 用第二种。

### 读屏障(read barrier)

write barrier 拦截"写",read barrier 拦截"读":**读取一个白色对象时,先把它标记为灰色**。Baker 的 concurrent copying collector 用 read barrier——mutator 读到的所有指针必须指向 to-space,在读的瞬间做 forwarding。

选择 write barrier vs read barrier 取决于**写多还是读多**——大多数系统选 write barrier(写比读少,barrier 开销更低)。

## GC 对编译器的要求

GC 不是编译器写完就行的独立模块——编译器必须在生成代码时嵌入 GC 支持:

- **safepoint**:不是任何时刻都能 GC——编译器在回边(循环头)或函数调用处插入 safepoint 检查,GC 只在 safepoint 挂起线程。
- **根映射(root map)**:编译器为每个 safepoint 生成本地变量/寄存器的**活跃指针映射**(哪些寄存器/栈位置当前存的是 GC 可见指针),GC 据此扫根集。
- **write barrier 内联**:barrier 如果做过大开销(每次都函数调用)会把写密集代码拖慢 10×→ 编译器把 barrier 做成内联的几条指令,只在需记录时才走 slow path。

## 参考

- **Jones/Hosking/Moss**: "The Garbage Collection Handbook" — GC 领域的权威参考
- **Wilson (1992)**: "Uniprocessor Garbage Collection Techniques" — GC 早期综述
- **Go GC**: `src/runtime/mgc.go` — 工业级并发标记,有清晰设计文档

*Keywords: garbage collection, GC, mark-sweep, copying, semispace, Cheney, generational GC, weak generational hypothesis, write barrier, read barrier, card marking, remembered set, tri-color invariant, concurrent GC, stop-the-world, STW, safepoint, root map, compaction, fragmentation, bump allocator, nursery, tenure*