05.2 - GC 基本算法（标记-清除 / 标记-复制 / 标记-整理）
定位: 判定对象存活后，GC 以何种方式回收和整理堆空间——所有收集器都基于这三种基本算法 面试高频度: ⭐⭐⭐⭐⭐ 考查方式: 三算法对比、复制算法为什么适合新生代、标记-整理解决了标记-清除的什么问题
一、这是什么？为什么需要它？
**对象存活判定算法** 解决了"谁死了"的问题。接下来的问题是：怎么把死掉的对象腾出的空间再利用起来？
三种基本算法就是三种不同的"腾空间"策略，各有优劣。现代垃圾收集器是这三种基本算法的组合与变体。理解它们是理解 Serial/G1/ZGC 的基石。
二、原理拆解
2.1 标记-清除（Mark-Sweep）——最直观，但有碎片化问题
原理
Phase 1 — 标记: 从 GC Roots 遍历对象图，标记所有存活对象
Phase 2 — 清除: 线性遍历堆，回收所有未标记对象的内存
内存状态变化:
前 (对象分配满): 后 (标记-清除完成):
┌─────┬─────┬─────┬─────┬─────┐ ┌─────┬─────┬─────┬─────┬─────┐
│ A │ B │ C │ D │ E │ │ A │ │ C │ │ E │
│ 活 │ 死 │ 活 │ 死 │ 活 │ → │ 活 │ 空 │ 活 │ 空 │ 活 │
└─────┴─────┴─────┴─────┴─────┘ └─────┴─┬───┴─────┴─┬───┴─────┘
│ │
▼ ▼
碎片1 碎片2
(不能连续分配大对象)为什么碎片化是致命问题？
标记-清除不移动存活对象。随着多次 GC 的进行，可用空间越来越碎片化。假设总空闲空间还有 100KB，但最大连续空闲只有 15KB → 无法分配一个 20KB 的对象 → 触发 Full GC，即使空间实际充足。
这个缺陷是推动其它算法产生的核心动力。
优点和缺点
| 维度 | 评估 |
|---|---|
| 速度 | 标记和清除都只需遍历堆一次，O(N) |
| 空间开销 | 不需要额外空间（不像复制算法浪费一半） |
| 碎片化 | 严重。GC 次数越多，碎片越多 |
| 大对象分配 | 碎片化后大对象分配失败率升高 |
| 适合场景 | 存活对象少、不追求大对象连续分配（早期 CMS 的老年代） |
2.2 标记-复制（Mark-Copy）——解决了碎片化，但浪费空间
原理（Semispace / Cheney 算法）
将堆分成两个等大的半区（From 和 To）。只从 From 分配。From 满时：
Step 1 — 标记: 标记 From 中的存活对象
Step 2 — 复制: 将存活对象按顺序复制到 To 半区（紧贴放置）
Step 3 — 交换: From 和 To 角色互换
图解过程:
初始状态: 复制完成 (角色互换):
┌──────────────┬──────────────┐ ┌──────────────┬──────────────┐
│ From │ To │ │ To (空的) │ From │
│ A B C D │ (空闲) │ │ │ A C E │
│ 死 活 死 活 │ │ → │ │ (连续排列) │
│ 活 死 │ │ │ │ │
│ │ │ │ 存活对象紧贴 │
│ 存活: B, D │ │ │ 无碎片 │
│ ↑ 这里碎片化 │ │ │ ↑ 下次 GC 用 │
└──────────────┴──────────────┘ └──────────────┴──────────────┘Cheney 算法的精妙之处：使用两个指针（scan 和 free）实现广度优先复制，free 始终指向 To 空间下一个可用位置，新复制的对象到 free 处，free += 对象大小。既不需要队列也不需要递归，每个存活对象恰好被处理一次。
为什么适合新生代？
关键观察：新生代 90%+ 的对象都是朝生夕死。复制算法需要复制所有存活对象，存活对象越少，复制成本越低。
| 场景 | 存活对象比例 | 复制成本 | 内存浪费 |
|---|---|---|---|
| 新生代 | ~10% | 低 — 只复制 10% 的对象 | 表面浪费 50%，但实际只浪费存活对象所占的空间（~10%） |
| 老年代 | ~80%+ | 高 — 复制 80%+ 的对象 | 不可接受 |
这就是"复制算法与新生代是天生一对"的原因：死亡得多活得少 → 复制成本低。
优点和缺点
| 维度 | 评估 |
|---|---|
| 碎片化 | 完全解决。存活对象在 To 空间连续排列 |
| 空间开销 | 需要一个空闲半区（50% 空间"浪费"）。新生代中实际浪费约 10%（因存活对象少） |
| 复制成本 | 正比于存活对象数量。存活越多越慢 |
| 分配速度 | 快。持续在 From 区 bump-the-pointer |
| 适合场景 | 新生代（低存活率） |
2.3 标记-整理（Mark-Compact）——老年代的答案
原理
Phase 1 — 标记: 同标记-清除，从 GC Roots 标记存活
Phase 2 — 整理: 将存活对象滑向堆一端，更新所有引用
图解过程:
整理前 (碎片化): 整理后 (无碎片, 连续空闲):
┌─────┬─────┬─────┬─────┐ ┌─────┬─────┬────────────────────┐
│ A │ │ B │ │ │ A │ B │ │
│ 活 │ 空 │ 活 │ 空 │ → │ 活 │ 活 │ 连续空闲空间 │
│ │ │ │ │ │ │ │ │
└─────┴─────┴─────┴─────┘ └─────┴─────┴────────────────────┘
↑
B 被移到这里, A→B 的引用要更新为什么需要标记-整理？
老年代的特点是：对象存活率高、堆空间大。
- 不用 Mark-Sweep → 碎片化导致频繁 Full GC
- 不用 Mark-Copy → 存活率 80%+ 意味着复制 80% 的堆，成本高；且需要浪费 50% 空间
Mark-Compact 在碎片化和空间浪费之间取得了平衡：不浪费空间，整理后无碎片，但代价是移动对象和更新指针的 CPU 成本。
不同整理算法
| 方式 | 做法 | 优缺点 |
|---|---|---|
| 滑动整理 | 存活对象全部滑向一端 | 速度快（线性移动），但需要精确计算新地址 |
| 碎片清理 | 只把碎片空间中的存活对象移到空闲处 | 更复杂，碎片分布不规则时效果好 |
| 表格整理 | 使用转发地址表记录对象移动前后位置 | 引用更新效率高，但需要额外的表空间 |
2.4 三种算法对比总结
| 维度 | 标记-清除 | 标记-复制 | 标记-整理 |
|---|---|---|---|
| 碎片化 | 严重 | 无碎片 | 无碎片 |
| 额外空间 | 无 | 50% 空闲半区 | 无 |
| 移动对象 | 不移 | 移 | 移 |
| 引用更新 | 无需 | 需要更新 | 需要更新 |
| STW 时间 | 正比于堆大小 | 正比于存活对象量 | 正比于存活对象量 + 移动开销 |
| 分配方式 | 空闲列表（复杂） | bump-the-pointer（极快） | bump-the-pointer（快） |
| 适合代际 | 老年代（CMS） | 新生代 | 老年代 |
| 吞吐量损失 | 低（不移动） | 中（复制成本） | 中高（移动+更新引用） |
三算法在分代堆中的协作关系:
┌────────────────────────────────────────────────────────────────┐
│ 分代堆中的算法分配 │
│ │
│ ├──────────── 年轻代 ────────────┤├──────── 老年代 ───────────┤│
│ │ 标记-复制 标记-整理 / 标记-清除 ││
│ │ 每秒执行多次 Minor GC 数小时执行一次 Full GC ││
│ │ STW: 1-100ms STW: 0.5-30s ││
│ │ 存活对象少 → 复制成本低 存活对象多 → 整理成本高 ││
│ └──────────────────────────────────┘└────────────────────────┘│
│ │
│ 对象从新生代晋升到老年代: │
│ Eden → S0 ↔ S1 (复制) → Old (标记-整理) │
└────────────────────────────────────────────────────────────────┘三、图解全景
三种算法并排对比:
① 标记-清除 (Mark-Sweep) ② 标记-复制 (Mark-Copy)
┌──────┬──────┬──────┐ ┌──────┬──────┐
│ A │ B │ C │ ← 标记前 │ A │ │ ← From: A存活, B存活
│ 存活 │ 死亡 │ 存活 │ │ 存活 │ │ To: 空闲
└──────┴──────┴──────┘ │ B │ │
↓ 标记 │ 存活 │ │
┌──────┬──────┬──────┐ └──────┴──────┘
│ A │ │ C │ ← 清除后 ↓ 复制
└──────┴──────┴──────┘ ┌──────┬──────┐
↑ 碎片区域，A和C之间有空洞 │ │ A B │ ← From 清空, To 连续排列
└──────┴──────┘
③ 标记-整理 (Mark-Compact)
┌──────┬──────┬──────┐
│ A │ B │ C │ ← 标记前
│ 存活 │ 死亡 │ 存活 │
└──────┴──────┴──────┘
↓ 整理
┌──────┬────────────┐
│ A │ C │ ← 存活对象滑向一端
└──────┴────────────┘
↑ 连续空闲空间四、实战验证
复制算法在新生代的实际效果
bash
# 通过 GC 日志观察复制算法行为
# VM 参数: -Xms20m -Xmx20m -Xmn10m -XX:SurvivorRatio=8 -XX:+PrintGCDetails -XX:+UseSerialGC
public class CopyDemo {
public static void main(String[] args) throws Exception {
byte[] a = new byte[2 * 1024 * 1024]; // 2MB 进入 Eden
byte[] b = new byte[2 * 1024 * 1024]; // 2MB 进入 Eden
byte[] c = new byte[2 * 1024 * 1024]; // 触发第一次 Minor GC
Thread.sleep(1000);
}
}GC 日志:
[GC (Allocation Failure) [DefNew
Desired Survivor size 524288 bytes, new threshold 15 (max 15)
- age 1: 611312 bytes, 611312 total
: 6144K->597K(9216K), 0.0052892 secs]
6144K->4693K(19456K), 0.0053735 secs]
↑ ↑
Eden+一个Survivor清空 另一个 Survivor 空间中有 597K 存活对象关键观察：Eden 从 6MB 降到接近 0（清空），存活对象 597K 复制到空闲的 Survivor。复制成本 ~5ms。如果换做标记-清除，碎片化将很快到来。
三种算法的性能对比（理论值）
| 操作 | Mark-Sweep | Mark-Copy | Mark-Compact |
|---|---|---|---|
| 标记阶段 | 遍历整个活对象图 | 遍历整个活对象图 | 遍历整个活对象图 |
| 回收阶段 | 扫描整个堆（O(堆大小)） | 只复制存活对象（O(存活数)） | 移动存活对象+更新指针（O(存活数) + O(引用数)) |
| 分配新对象 | 空闲列表搜索 | 指针 bump | 指针 bump |
五、面试视角
| 追问 | 答案要点 |
|---|---|
| 三种 GC 算法的优缺点？ | Mark-Sweep 简单但有碎片；Mark-Copy 无碎片但浪费空间；Mark-Compact 无碎片不浪费空间但移动开销大 |
| 为什么新生代用标记-复制？ | 弱分代假说：90%+ 对象朝生夕死 → 存活对象少 → 复制成本低；表面浪费 50% 空间但实际只有存活量（~10%）的浪费；且实现简单，bump-the-pointer 分配极快 |
| 复制算法为什么适合朝生夕死的对象？ | 复制成本完全由存活对象数量决定。存活对象越少，复制越少，效率越高。新生代正符合这个特征 |
| 标记-整理解决了标记-清除的什么问题？ | 碎片化问题。标记-清除多次 GC 后产生大量内存碎片，无法分配大对象，需要触发 Full GC。标记-整理把存活对象滑到一端，消除碎片 |
| CMS 为什么用标记-清除不用标记-整理？ | CMS 追求低延迟，标记-清除不移动对象，STW 时间更短。代价是碎片化后并发模式失败（Concurrent Mode Failure）→ 退化为 Serial Old 单线程 Full GC |
| 老年代为什么不用标记-复制？ | 老年代存活率高（80%+），复制那么多对象成本太高；而且需要额外 50% 空间，老年代较大时不可接受 |
| 什么情况下 Mark-Sweep 反而优于其它？ | 存活对象极少且分配模式不需要大对象时（比如刚启动时）。不移动对象 → 无开销 |
📚 相关链接
- **对象存活判定算法** — 先判定存活，再选择算法回收
- **Java堆** — 分代结构决定了算法选择（新生代复制、老年代整理）
- **垃圾收集器详解(Serial到ZGC)** — 各收集器对这三种基本算法的组合使用
- ← 返回 **GC索引**