汀的知识碎片

05 垃圾回收算法——标记清除、复制、标记整理与分代假说

27 min read

05 垃圾回收算法——标记清除、复制、标记整理与分代假说

摘要：

上一篇解决了”哪些对象是垃圾”，本篇解决”如何回收这些垃圾”。现代 GC 的所有算法，都是在三种基础算法——标记-清除（Mark-Sweep）、复制（Copying）、标记-整理（Mark-Compact）——的基础上演化而来的。三种算法各有侧重：标记-清除简单但产生碎片，复制高效但浪费空间，标记-整理不碎片化但移动成本高。没有完美的算法，只有针对特定场景的最优权衡。正是这种权衡，催生了分代收集（Generational Collection） 的设计——将堆分为新生代和老年代，针对不同年龄段对象的生命周期特征，分别选用最合适的算法。本文还深入剖析了分代 GC 的内在矛盾：跨代引用（老对象引用新对象）如何打破分代 GC 的完美假设，以及记忆集（Remembered Set） 和卡表（Card Table） 如何以最小代价解决这个矛盾。

第 1 章 三种基础算法：没有完美，只有权衡

1.1 垃圾回收的两个阶段

无论哪种 GC 算法，都包含两个核心阶段：

  1. 标记（Mark）：通过可达性分析，找出所有存活的对象（或反过来找出所有垃圾对象）
  2. 回收（Sweep/Copy/Compact）：处理已标记的垃圾，让内存可以被重新使用

三种基础算法在”回收”阶段的处理方式不同，由此带来了各自的优缺点。

第 2 章 标记-清除算法（Mark-Sweep）

2.1 什么是标记-清除

标记-清除（Mark-Sweep） 是最早、最基础的垃圾回收算法，1960 年由 John McCarthy 在 Lisp 语言实现中提出。

两个步骤：

  1. 标记阶段（Mark）：从 GC Roots 出发，通过可达性分析遍历所有可达对象，将其标记为”存活”
  2. 清除阶段（Sweep）：遍历整个堆，将所有未被标记的对象（垃圾）的内存空间释放（清除）回空闲列表
标记前（M=存活/标记，□=垃圾）：
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│M │□ │M │M │□ │□ │M │□ │M │□ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

清除后（F=空闲）：
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│M │F │M │M │F │F │M │F │M │F │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
  ↑碎片化：空闲空间不连续，大对象无法分配

2.2 优势：简单，低对象移动开销

标记-清除的最大优势是不移动对象——存活对象在回收后仍留在原位置，只是垃圾对象的内存被标记为”可用”。

不移动对象意味着：

  • 不需要更新所有指向这些对象的引用（更新引用是一个代价高昂的操作）
  • 存活对象的处理速度快（只需标记，不需复制）

2.3 致命缺陷：内存碎片化

标记-清除的致命问题是内存碎片化（Fragmentation）：

回收后，空闲的内存块散布在堆的各个位置，不连续。当需要分配一个大对象时，即使堆的空闲空间总量足够，也可能因为没有连续的足够大的空闲块而触发 Full GC 甚至 OOM。

碎片化导致的连锁问题：

  • 必须使用”空闲列表”来追踪散碎的空闲空间，分配速度比”指针碰撞”慢
  • 随着时间推移，碎片越来越多，大对象分配越来越困难
  • 最终只能通过 Full GC 进行内存整理，引入长时间 STW 停顿

CMS 就是标记-清除算法（并发版本），因此 CMS 也长期受碎片化问题困扰，最终在 JDK 9 被废弃。

第 3 章 复制算法（Copying）

3.1 复制算法的思想来源

复制算法（Copying Collection）由 Cheney 在 1970 年提出，核心思想是：把内存分成两个等大的半空间（From space 和 To space），每次只使用 From space；GC 时将 From space 中的存活对象全部复制到 To space，然后直接清空整个 From space；最后交换 From 和 To 的角色。

GC 前（From 使用中，To 空闲）：
From: │A│B│.│C│.│.│D│.│E│  （A/C/D/E 存活，B 是垃圾，. 是碎片）
To:   │.│.│.│.│.│.│.│.│.│  （空闲）

GC 后（存活对象复制到 To，From 清空）：
From: │.│.│.│.│.│.│.│.│.│  （整个清空，可以直接重用）
To:   │A│C│D│E│.│.│.│.│.│  （连续排列，无碎片）
↑ From 和 To 角色互换，下次 GC 方向反过来

3.2 复制算法的优势

无碎片化：存活对象被紧密地排列在 To space 的开头，内存是连续的，可以用最快的”指针碰撞”方式分配新对象。

GC 速度快：只需处理存活对象（复制），不需要遍历整个堆中的垃圾对象。如果存活对象很少（比如新生代 GC 时大多数对象已死），复制的工作量极小，GC 速度极快。

自动整理：每次 GC 后，对象紧密排列，顺带完成了内存整理。

3.3 代价：空间利用率减半，且不适合高存活率场景

复制算法的代价也很明显：

空间利用率只有 50%：始终有一半内存（To space）是空闲的，作为复制目标缓冲区，被”浪费”掉。如果将整个 8GB 堆用于复制算法，有效可用空间只有 4GB。

存活率越高，代价越大：复制算法的工作量与存活对象数量成正比。如果 90% 的对象都存活（老年代的典型情况），需要复制 90% 的数据，效率极低。

因此，复制算法最适合存活率极低的场景——恰好与新生代的特征完美匹配（弱分代假说：绝大多数对象朝生暮死）。这也是 Java 新生代使用 Eden + S0 + S1 的复制收集方案的根本原因。

3.4 新生代的 Eden + Survivor 改良

直接将堆分成两个等大的半空间，50% 浪费太多。HotSpot 对复制算法做了改良：

将新生代分为 Eden（80%）+ S0（10%）+ S1（10%），比例由 -XX:SurvivorRatio=8 控制。

每次 Minor GC：

  • 存活对象从 Eden + 当前 From Survivor 复制到空的 To Survivor
  • Eden 和 From 全部清空
  • From 和 To 角色互换

浪费的空间只有 10%（一个 Survivor 区），远比 50% 高效。但有一个前提：存活对象的总大小必须不超过 To Survivor 的容量。如果超过了（某次 GC 存活率特别高），溢出的对象直接晋升到老年代（分配担保，Allocation Guarantee）。

第 4 章 标记-整理算法（Mark-Compact）

4.1 什么是标记-整理

标记-整理（Mark-Compact） 是为了解决标记-清除的碎片问题，同时避免复制算法的空间浪费而设计的。

两个步骤：

  1. 标记阶段（Mark）：与标记-清除相同，标记所有存活对象
  2. 整理阶段（Compact）：将所有存活对象向内存的一端移动，紧密排列；移动完成后，端边界之外的所有内存直接清空（更新为空闲状态）
整理前：
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│A │□ │B │C │□ │□ │D │□ │E │□ │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

整理后（所有存活对象向左移动，连续排列）：
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│A │B │C │D │E │F │F │F │F │F │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
                  ↑ 空闲空间：连续大块

4.2 优势：无碎片 + 空间利用率 100%

标记-整理完美解决了标记-清除的碎片问题，同时不像复制算法那样浪费一半空间：

  • 无碎片：存活对象连续排列，大对象可以正常分配
  • 100% 空间利用率：不需要保留一半空间作为复制目标
  • 分配速度快：整理后可以用指针碰撞分配，速度与复制算法相同

4.3 代价：移动对象的高昂成本

标记-整理的问题在于移动对象的成本极高：

更新所有引用：对象移动后，所有指向它的引用（其他对象的字段、栈上的变量、JNI 全局引用等）都必须更新为新地址。这需要遍历整个堆，工作量巨大。

STW 时间长：整理阶段必须在 STW 下进行（否则用户线程可能正在使用旧地址的对象，移动后立即崩溃）。移动大量存活对象（尤其是老年代，存活对象很多）时，STW 时间显著增加。

CPU 缓存效应：移动对象会使 CPU 缓存中的数据失效（对象在新位置，缓存中是旧位置的数据），导致后续访问的缓存命中率短暂下降。

因此，标记-整理更适合老年代——老年代虽然存活率高（移动对象多），但 GC 频率远低于新生代，整体代价是可以接受的。

4.4 三种算法的横向对比

维度标记-清除复制标记-整理
是否移动对象否是是
内存碎片有（严重）无无
空间利用率100%50%100%
GC 速度（高存活率）慢（需遍历垃圾）慢（需复制大量对象）慢（需移动大量对象）
GC 速度（低存活率）中快（复制量少）中
分配速度慢（空闲列表）快（指针碰撞）快（指针碰撞）
最适合老年代（并发版）新生代（低存活率）老年代（低频率 GC）

第 5 章 分代收集假说——算法选择的理论基础

5.1 分代假说的两个核心命题

现代 GC 都遵循分代收集（Generational Collection） 理论，其理论基础是两个基于大量程序统计数据的假说：

弱分代假说（Weak Generational Hypothesis）：绝大多数对象的生命周期极短，在创建后不久就会变成垃圾。统计数据显示，典型的 Java 程序中，超过 90%（有些场景更高）的对象在创建后第一次 GC 之前就已经死亡。

强分代假说（Strong Generational Hypothesis）：经历过越多次 GC 仍然存活的对象，未来继续存活的概率越高。换句话说，“越老越难死”——存活了 100 次 GC 的对象，很可能会继续存活很长时间。

5.2 从假说到工程设计

这两个假说直接推导出了分代 GC 的设计决策：

基于弱分代假说：将大多数新创建的对象集中在新生代（Young Generation）。由于新生代中绝大多数对象很快死亡，GC 后存活的对象极少，特别适合复制算法——复制量少，速度快，且可以高频率执行（因为每次停顿时间短）。

基于强分代假说：将经历多次 GC 仍存活的”老”对象晋升到老年代（Old Generation）。老年代中存活对象多、GC 频率低，标记-整理或标记-清除更合适（复制算法在高存活率时代价过高）。

分代 GC 的核心收益：通过将不同生命周期的对象隔离到不同区域，每次 GC 只需要扫描其中一个区域，大幅降低了单次 GC 的工作量，提高了整体吞吐量。

5.3 Minor GC、Major GC 与 Full GC 的关系

Minor GC（也称 Young GC）：只回收新生代（Eden + Survivor）。触发条件：Eden 区满时。执行时间：通常几毫秒到几十毫秒（新生代小，存活率低，复制快）。频率：高（可能每隔几秒就触发一次）。

Major GC（也称 Old GC）：只回收老年代。并非所有收集器都有单独的 Major GC——CMS 有，G1 在 Mixed GC 阶段也可以只回收老年代。

Full GC：回收整个堆（新生代 + 老年代）以及方法区（元空间）。通常是因为：

  • 老年代空间不足，无法为晋升对象分配内存
  • 系统显式调用 System.gc()（虽然只是建议，JVM 可能执行 Full GC）
  • 元空间（方法区）空间不足
  • 大对象直接分配失败

Full GC 是代价最高的 GC：涉及整个堆，STW 时间最长（可能数秒），是生产系统性能问题的主要来源之一。优化 GC，本质上是减少 Full GC 的频率和持续时间。

生产避坑

System.gc() 是一个陷阱：它触发的 Full GC 往往在业务低峰期没有问题，但在高并发时调用（比如代码中判断内存不足时手动触发）会造成严重的性能抖动。JVM 参数 -XX:+DisableExplicitGC 可以让 JVM 忽略 System.gc() 的调用（但要注意，这会影响 NIO 堆外内存的回收，需要 -XX:+ExplicitGCInvokesConcurrent 配合）。

第 6 章 分代 GC 的内在矛盾——跨代引用

6.1 跨代引用的问题

分代 GC 的假设是：每次 Minor GC 只扫描新生代，不扫描老年代，从而减少工作量。但这个假设有一个隐患：老年代的对象可能持有对新生代对象的引用（跨代引用）。

// 经典的跨代引用场景：
// 老年代中的缓存对象，其值字段引用着新生代中的新创建对象
class Cache {               // Cache 是老年代对象（存活时间长）
    Object value = new Object();  // value 指向的 Object 是新生代对象（刚创建）
}

如果 Minor GC 只扫描新生代的 GC Roots，会遗漏老年代中 Cache.value 这条引用——从 Minor GC 的视角看，新生代中的 value 对象似乎没有任何引用（新生代内部没有指向它的引用），就会被错误地回收！但实际上它通过老年代的 Cache 对象是可达的，不应该被回收。

如果把老年代对象全部加入 GC Roots 集合，相当于每次 Minor GC 都要扫描整个老年代——这完全破坏了分代 GC 的收益，退化为全堆扫描。

6.2 记忆集（Remembered Set）——解决跨代引用的数据结构

记忆集（Remembered Set，RSet） 是分代 GC 为解决跨代引用问题而引入的数据结构。它的核心思想：不需要扫描整个老年代来找跨代引用，只需要记录”哪些老年代对象持有对新生代对象的引用”，Minor GC 时只扫描这些特定的老年代对象。

更准确地说，记忆集记录的是**“跨代引用的来源位置”**（谁引用了新生代对象），使这些位置可以作为 GC Roots 的补充。

6.3 卡表（Card Table）——记忆集的高效实现

记忆集是概念，卡表（Card Table） 是 HotSpot 最常用的记忆集实现：

基本思想：将老年代的内存划分为一系列固定大小的卡页（Card Page，512 字节），用一个字节数组（卡表）来标记每个卡页的状态：

  • 0：干净，该卡页中没有跨代引用
  • 1（脏，Dirty）：该卡页中可能存在跨代引用
老年代内存（假设共 4MB）：
│ 卡页0  │ 卡页1  │ 卡页2  │ 卡页3  │ ... │（每页 512 字节）
│  512B  │  512B  │  512B  │  512B  │

卡表（每个元素对应一个卡页）：
│  0  │  1  │  0  │  1  │ ...│
  ↑         ↑
干净        脏：该区域内有对象引用了新生代中的对象

Minor GC 时：只扫描卡表中标记为”脏”的卡页（而不是整个老年代），找出其中指向新生代的引用，将其作为额外的 GC Roots 加入到扫描集合中。

写屏障（Write Barrier）维护卡表：每次一个老年代对象的引用字段发生写入时（oldObj.field = youngObj），JVM 需要将对应的卡页标记为”脏”。这通过写屏障（Write Barrier） 实现——JIT 编译器在每条对象引用写入指令之后插入额外代码，检查并更新卡表。

// 原始代码：
cache.value = newObj;
 
// JIT 编译后插入写屏障（伪代码）：
cache.value = newObj;
// ↓ 写屏障（额外插入的代码）
int cardIndex = (int) ((address_of_cache) >> 9);  // 512 = 2^9
cardTable[cardIndex] = 1;  // 标记该卡页为"脏"

写屏障有一定的运行时开销（每次引用赋值都需要额外操作），但相比每次 Minor GC 都全扫老年代的代价，这个开销是微不足道的。

6.4 精确卡表 vs 粗粒度卡表

卡页大小是精度与性能的权衡：

  • 卡页过小（如 64B）：精度高，脏卡页少，扫描工作量小；但卡表本身占用内存多，写屏障执行频率高
  • 卡页过大（如 4KB）：卡表小，写屏障不频繁；但一个卡页包含很多对象，“脏”卡页中需要扫描的范围大，效率降低

HotSpot 选择 512 字节为卡页大小，是经验上的折中选择。

第 7 章 并发 GC 的额外挑战——写屏障的扩展应用

7.1 并发标记的漏标问题

前面在 04 垃圾回收基础——可达性分析、安全点与安全区域 中提到，三色标记在并发执行时，用户线程可能修改引用关系，导致漏标（floating garbage 的反面——本该存活的对象被标为垃圾）。

具体地，同时满足以下两个条件时，会发生对象丢失：

  1. 赋值器（应用线程）向黑色对象（已完成扫描的）插入了一条指向白色对象的新引用
  2. 赋值器删除了所有从灰色对象（待扫描的）出发、到达该白色对象的路径

此时白色对象通过黑色对象可达，但 GC 不会再扫描黑色对象，最终白色对象会被误回收。

7.2 写屏障的两种解决方案

解决漏标问题，需要通过写屏障拦截引用关系的变化，有两种理论：

增量更新（Incremental Update）：当黑色对象被赋予新的白色引用时，通过写屏障将该黑色对象重新置为灰色（加回工作队列），等待重新扫描。CMS 使用此方案（维护黑变灰的更新集合，并发标记结束后重新扫描）。

原始快照（SATB，Snapshot At The Beginning）：在并发标记开始时，记录引用关系的”快照”——当灰色对象删除到白色对象的引用时，通过写屏障记录被删除的这条引用，确保被删除引用的白色对象在本次 GC 中不会被回收（将其置为灰色）。G1 和 ZGC 使用此方案。

这是 GC 算法设计中最精妙也最复杂的部分，后续专门讲解 CMS 和 G1 的章节会深入展开。

第 8 章 总结

三种基础算法的本质是在碎片化、空间利用率、移动成本三个维度上的权衡：

标记-清除：不移动、有碎片、100% 空间利用率，适合老年代（并发版：CMS）

复制：移动对象、无碎片、50% 空间利用率，适合新生代（存活率低时效率极高）

标记-整理：移动对象、无碎片、100% 空间利用率，适合老年代（低频率 Full GC 时可以接受移动代价）

分代假说把这三种算法组合成了分代 GC 的经典形态——新生代用复制、老年代用标记-整理或标记-清除——是目前绝大多数生产 JVM 的基础。

跨代引用是分代 GC 的内在矛盾，记忆集/卡表 + 写屏障用精巧的空间换时间策略解决了这个矛盾，使 Minor GC 在不全扫老年代的前提下仍然保持正确性。

下一篇 06 经典垃圾回收器——Serial、Parallel、CMS 深度剖析 将基于本篇的算法理论，进入 HotSpot 历代垃圾回收器的工程实现——从 Serial（单线程）到 Parallel（并行，吞吐量优先）再到 CMS（并发标记，延迟优先），逐步理解 GC 回收器 30 年演进背后的工程哲学。

参考文献

  1. Richard Jones & Rafael Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management”, Wiley, 1996
  2. Richard Jones, Antony Hosking & Eliot Moss, “The Garbage Collection Handbook”, CRC Press, 2012
  3. 周志明, 《深入理解 Java 虚拟机（第三版）》, 第 3.3-3.5 章
  4. Cliff Click & John R. Rose, “Fast Subtype Checking in the HotSpot JVM”, 2002
  5. Paul R. Wilson, “Uniprocessor Garbage Collection Techniques”, 1994
  6. OpenJDK Wiki, “Remembered Sets”, wiki.openjdk.org

思考题

  1. 分代假说（Generational Hypothesis）认为’大多数对象朝生夕灭’。但在缓存密集型应用（如 Redis 客户端的连接池、Guava Cache）中，大量对象存活时间很长。分代假说在这种场景下是否仍然成立？如果 Old Gen 中存活对象占比极高（>90%），标记-整理算法的效率会如何变化？
  2. 复制算法（Copying）将存活对象从 From 区复制到 To 区，然后清空 From 区。它的优点是没有碎片，但代价是浪费一半内存空间。HotSpot 的 Young Gen 使用 Eden + 两个 Survivor 的比例（默认 8:1:1），只浪费 10% 空间。如果某次 Minor GC 时 Survivor 区放不下所有存活对象，会发生什么？这些对象去了哪里？
  3. 标记-清除（Mark-Sweep）算法产生内存碎片，标记-整理（Mark-Compact）需要移动对象（修改引用）。CMS 收集器在老年代使用标记-清除，碎片积累到无法分配大对象时会触发一次 Full GC（Serial Old 的标记-整理）。G1 通过 Region 化设计解决了这个问题——G1 是如何做到’只整理部分 Region 而非整个堆’的？