垃圾回收算法（下）：标记-整理、分代收集

引言：完善的垃圾回收方案

上一篇我们学习了两种基础算法：

标记-清除：简单但有碎片
标记-复制：无碎片但浪费空间

本文将学习另外两种算法，它们解决了前两种算法的缺陷：

标记-整理：无碎片且不浪费空间
分代收集：综合运用多种算法，是现代JVM的主流方案

标记-整理算法（Mark-Compact）

核心思想

分三个阶段：

标记阶段（Mark）：标记所有存活对象
整理阶段（Compact）：将存活对象移动到内存一端
清除阶段（Sweep）：清除边界外的所有内存

与标记-清除的区别

算法	清除方式	内存布局
标记-清除	直接释放死亡对象	分散，有碎片
标记-整理	移动存活对象后清除	紧凑，无碎片

详细流程

阶段1：标记（Mark）

从GC Roots开始，标记所有可达对象。

GC Roots开始遍历
    ↓
标记对象A（可达）
    ↓
标记对象B（A引用）
    ↓
标记对象C（B引用）
    ↓
完成标记

阶段2：整理（Compact）

将所有存活对象移动到内存的一端，使其紧密排列。

整理前:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ A  │ 空 │ C  │ 空 │ E  │ 空 │ 空 │ H  │
└────┴────┴────┴────┴────┴────┴────┴────┘

整理后:
┌────┬────┬────┬────┬────────────────────┐
│ A  │ C  │ E  │ H  │        空          │
└────┴────┴────┴────┴────────────────────┘

阶段3：清除（Sweep）

清除边界后的所有内存。

图解示例

初始状态：

堆内存:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ A  │ B  │ C  │ D  │ E  │ F  │ G  │ H  │
└────┴────┴────┴────┴────┴────┴────┴────┘

存活对象: A, C, E, H

标记阶段：

┌────┬────┬────┬────┬────┬────┬────┬────┐
│ A✓ │ B  │ C✓ │ D  │ E✓ │ F  │ G  │ H✓ │
└────┴────┴────┴────┴────┴────┴────┴────┘

整理阶段：

移动存活对象:
A → 保持不动（已在起始位置）
C → 移动到位置2
E → 移动到位置3
H → 移动到位置4

┌────┬────┬────┬────┬────────────────────┐
│ A  │ C  │ E  │ H  │        空          │
└────┴────┴────┴────┴────────────────────┘

清除阶段：

┌────┬────┬────┬────┬────────────────────┐
│ A  │ C  │ E  │ H  │ 可分配的连续空间    │
└────┴────┴────┴────┴────────────────────┘

结果:
· 存活对象紧密排列
· 无内存碎片
· 空闲内存连续

实现细节

移动对象需要更新引用：

// 伪代码
public void compact() {
    // 1. 计算每个对象的新地址
    for (Object obj : markedObjects) {
        obj.newAddress = calculateNewAddress(obj);
    }

    // 2. 更新所有引用
    for (Object obj : allObjects) {
        if (obj.references != null) {
            for (int i = 0; i < obj.references.length; i++) {
                Object ref = obj.references[i];
                if (ref != null) {
                    obj.references[i] = ref.newAddress;  // 更新引用
                }
            }
        }
    }

    // 3. 移动对象到新地址
    for (Object obj : markedObjects) {
        copyObject(obj, obj.newAddress);
    }

    // 4. 清除旧数据
    clearOldData();
}

优点

1️⃣ 无内存碎片

存活对象紧密排列，空闲内存连续。

2️⃣ 不浪费空间

不需要像复制算法那样预留一半空间。

3️⃣ 适合存活率高的场景

老年代对象存活率高，标记-整理比复制算法更高效。

缺点

1️⃣ 效率低（移动对象开销大）

需要移动存活对象，并更新所有引用。

时间开销：

标记：O(存活对象数)
整理：O(存活对象数) + O(更新引用)
清除：O(1)

2️⃣ Stop The World时间长

移动对象期间，必须暂停所有应用线程（保证引用正确性）。

3️⃣ 实现复杂

需要计算新地址、更新引用、移动对象，实现较复杂。

适用场景

老年代：对象存活率高（通常>70%），标记-整理比复制算法更高效
Full GC：整理内存碎片，为后续分配提供连续空间

优化：标记-清除-整理（Mark-Sweep-Compact）

策略：

平时使用 标记-清除（效率高）
定期使用 标记-整理（清理碎片）

private int gcCount = 0;

public void gc() {
    if (gcCount % 10 == 0) {
        markCompact();  // 每10次GC整理一次
    } else {
        markSweep();    // 平时使用标记-清除
    }
    gcCount++;
}

优势：

平衡效率和碎片问题
CMS收集器采用类似策略

分代收集理论（Generational Collection）

核心思想

根据对象存活周期的不同，将堆分为不同的区域，针对不同区域使用不同的GC算法。

三大假说

分代收集基于以下三个经验假说：

1️⃣ 弱分代假说（Weak Generational Hypothesis）

绝大多数对象都是朝生夕死的。

数据支持：

研究表明，98%的对象生命周期小于1秒
只有2%的对象存活超过1秒

示例：

public void processRequest(Request request) {
    Response response = new Response();  // 短命对象
    Result result = service.handle(request);  // 短命对象
    response.setData(result);
    return response;  // 方法结束，response和result成为垃圾
}

2️⃣ 强分代假说（Strong Generational Hypothesis）

熬过多次GC的对象，越难以消亡。

数据支持：

对象经历的GC次数越多，再次被回收的概率越低
如：全局缓存、单例对象、静态对象

示例：

public class CacheManager {
    private static Map<String, Object> cache = new HashMap<>();  // 长命对象

    public static void put(String key, Object value) {
        cache.put(key, value);  // 对象存活时间长
    }
}

3️⃣ 跨代引用假说（Intergenerational Reference Hypothesis）

跨代引用相对于同代引用来说占极少数。

含义：

老年代对象很少引用新生代对象
大部分引用都是同代之间的

推论：

新生代GC时，不需要扫描整个老年代
只需扫描存在跨代引用的部分

分代结构

┌─────────────────────────────────────────────┐
│              JVM 堆内存                      │
├─────────────────────────────────────────────┤
│                                             │
│  ┌────────────────────────────────────┐    │
│  │       新生代 (Young Generation)     │    │
│  │  ┌─────────┬────────┬────────┐    │    │
│  │  │  Eden   │   S0   │   S1   │    │    │
│  │  │   8     │   1    │   1    │    │    │
│  │  └─────────┴────────┴────────┘    │    │
│  │                                     │    │
│  │  · 对象优先分配                      │    │
│  │  · 存活率低（<10%）                  │    │
│  │  · 使用复制算法                      │    │
│  │  · Minor GC频繁但快                 │    │
│  └────────────────────────────────────┘    │
│                                             │
│  ┌────────────────────────────────────┐    │
│  │       老年代 (Old Generation)       │    │
│  │                                     │    │
│  │  · 存放长期存活对象                  │    │
│  │  · 存活率高（>70%）                  │    │
│  │  · 使用标记-清除或标记-整理          │    │
│  │  · Major/Full GC罕见但慢            │    │
│  └────────────────────────────────────┘    │
│                                             │
└─────────────────────────────────────────────┘

分代GC流程

Minor GC（新生代GC）

触发条件：

Eden区空间不足

回收范围：

新生代（Eden + From Survivor）

使用算法：

复制算法

流程：

标记Eden区和From Survivor区的存活对象
将存活对象复制到To Survivor区
清空Eden区和From Survivor区
From和To互换

特点：

频率高（可能每秒数次）
速度快（几毫秒到几十毫秒）
Stop The World时间短

Major GC（老年代GC）

触发条件：

老年代空间不足
分配担保失败

回收范围：

老年代

使用算法：

标记-清除或标记-整理

特点：

频率低（可能几分钟到几小时一次）
速度慢（几百毫秒到几秒）
Stop The World时间长

Full GC（全堆GC）

触发条件：

老年代空间不足
元空间不足
调用System.gc()（不推荐）
CMS GC出现Concurrent Mode Failure

回收范围：

新生代 + 老年代 + 元空间

特点：

频率最低
速度最慢
Stop The World时间最长
应尽量避免

跨代引用问题

问题：新生代GC时，如何处理老年代对新生代的引用？

朴素方案：扫描整个老年代（效率低）

优化方案：记忆集（Remembered Set）

记忆集（Remembered Set）

定义：记录从非收集区域指向收集区域的引用。

作用：避免扫描整个老年代。

实现：

将老年代划分为若干块（如512字节）
记录哪些块包含跨代引用
新生代GC时，只扫描这些块

示例：

老年代:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ 块1 │ 块2 │ 块3 │ 块4 │ 块5 │ 块6 │ 块7 │ 块8 │
└────┴────┴────┴────┴────┴────┴────┴────┘
   ↓                  ↓
新生代对象          新生代对象

记忆集:
· 块1包含跨代引用
· 块4包含跨代引用

Minor GC时:
· 只扫描块1和块4
· 不扫描其他块

卡表（Card Table）

定义：记忆集的一种实现方式，使用字节数组记录跨代引用。

结构：

// 卡表（伪代码）
byte[] cardTable;  // 每个元素对应老年代的一块区域（512字节）

// 标记
cardTable[index] = DIRTY;  // 1表示该块包含跨代引用

// 清除
cardTable[index] = CLEAN;  // 0表示该块不包含跨代引用

维护：

通过 写屏障（Write Barrier） 维护
老年代对象引用新生代对象时，标记卡表

写屏障（Write Barrier）

定义：在引用更新前后插入的代码片段。

作用：维护记忆集/卡表。

伪代码：

// 引用更新
void updateReference(Object obj, Object newRef) {
    obj.field = newRef;  // 更新引用

    // 写屏障：如果是跨代引用，标记卡表
    if (isInOldGen(obj) && isInYoungGen(newRef)) {
        markCardDirty(obj);  // 标记卡表
    }
}

三种算法总结对比

算法	内存碎片	空间利用率	效率	适用场景
标记-清除	❌ 有碎片	✅ 100%	存活率高时效率高	老年代（配合定期整理）
标记-复制	✅ 无碎片	❌ 50%（标准）✅ 90%（优化）	存活率低时效率高	新生代
标记-整理	✅ 无碎片	✅ 100%	效率低（移动开销大）	老年代（Full GC）

实战场景

观察分代GC

/**
 * VM参数：-Xms20M -Xmx20M -Xmn10M -XX:+PrintGCDetails -XX:SurvivorRatio=8
 */
public class GenerationalGCDemo {
    private static final int _1MB = 1024 * 1024;

    public static void main(String[] args) {
        byte[] allocation1, allocation2, allocation3;

        allocation1 = new byte[2 * _1MB];
        allocation2 = new byte[2 * _1MB];
        allocation3 = new byte[2 * _1MB];

        // 触发Minor GC
        allocation1 = null;
        allocation4 = new byte[4 * _1MB];

        // 继续分配，可能触发Major GC
        allocation5 = new byte[4 * _1MB];
    }
}

GC日志：

[GC (Allocation Failure) [PSYoungGen: 7291K->808K(9216K)] 7291K->6952K(19456K), 0.0031993 secs]
[Full GC (Ergonomics) [PSYoungGen: 808K->0K(9216K)] [ParOldGen: 6144K->6827K(10240K)] 6952K->6827K(19456K), 0.0098765 secs]

常见问题与误区

❌ 误区1：分代收集是一种算法

真相：

分代收集是一种 理论/策略
综合运用多种算法（复制、标记-清除、标记-整理）

❌ 误区2：Full GC = Major GC

真相：

Major GC：只回收老年代
Full GC：回收整个堆（新生代 + 老年代 + 元空间）

❌ 误区3：老年代只使用标记-整理

真相：

平时使用标记-清除（效率高）
碎片积累到一定程度，使用标记-整理（CMS策略）

总结

核心要点

标记-整理：无碎片且不浪费空间，但效率低，适合老年代
分代收集理论基于三大假说：
- 弱分代假说：大部分对象朝生夕死
- 强分代假说：熬过多次GC的对象难以消亡
- 跨代引用假说：跨代引用占少数
分代结构：
- 新生代：复制算法，Minor GC频繁但快
- 老年代：标记-清除或标记-整理，Major GC罕见但慢
记忆集和卡表：解决跨代引用问题，避免扫描整个老年代
写屏障：维护记忆集/卡表，记录跨代引用

与下篇文章的衔接

下一篇文章，我们将学习 垃圾收集器演进史：从Serial到ZGC，理解GC的发展历程、吞吐量vs低延迟的权衡，以及并发vs并行的区别。

参考资料

《深入理解Java虚拟机（第3版）》- 周志明
HotSpot GC算法
Java虚拟机规范

下一篇预告：《垃圾收集器演进史：从Serial到ZGC》深入理解GC的发展历程，吞吐量优先vs低延迟优先的权衡，以及并发vs并行的区别。

引言：完善的垃圾回收方案#

标记-整理算法（Mark-Compact）#

核心思想#

与标记-清除的区别#

详细流程#

阶段1：标记（Mark）#

阶段2：整理（Compact）#

阶段3：清除（Sweep）#

图解示例#

实现细节#

优点#

1️⃣ 无内存碎片#

2️⃣ 不浪费空间#

3️⃣ 适合存活率高的场景#

缺点#

1️⃣ 效率低（移动对象开销大）#

2️⃣ Stop The World时间长#

3️⃣ 实现复杂#

适用场景#

优化：标记-清除-整理（Mark-Sweep-Compact）#

分代收集理论（Generational Collection）#

核心思想#

三大假说#

1️⃣ 弱分代假说（Weak Generational Hypothesis）#

2️⃣ 强分代假说（Strong Generational Hypothesis）#

3️⃣ 跨代引用假说（Intergenerational Reference Hypothesis）#

分代结构#

分代GC流程#

Minor GC（新生代GC）#

Major GC（老年代GC）#

Full GC（全堆GC）#

跨代引用问题#

记忆集（Remembered Set）#

卡表（Card Table）#

写屏障（Write Barrier）#

三种算法总结对比#

实战场景#

观察分代GC#

常见问题与误区#

❌ 误区1：分代收集是一种算法#

❌ 误区2：Full GC = Major GC#

❌ 误区3：老年代只使用标记-整理#

总结#

核心要点#

与下篇文章的衔接#

参考资料#

引言：完善的垃圾回收方案

标记-整理算法（Mark-Compact）

核心思想

与标记-清除的区别

详细流程

阶段1：标记（Mark）

阶段2：整理（Compact）

阶段3：清除（Sweep）

图解示例

实现细节

优点

1️⃣ 无内存碎片

2️⃣ 不浪费空间

3️⃣ 适合存活率高的场景

缺点

1️⃣ 效率低（移动对象开销大）

2️⃣ Stop The World时间长

3️⃣ 实现复杂

适用场景

优化：标记-清除-整理（Mark-Sweep-Compact）

分代收集理论（Generational Collection）

核心思想

三大假说

1️⃣ 弱分代假说（Weak Generational Hypothesis）

2️⃣ 强分代假说（Strong Generational Hypothesis）

3️⃣ 跨代引用假说（Intergenerational Reference Hypothesis）

分代结构

分代GC流程

Minor GC（新生代GC）

Major GC（老年代GC）

Full GC（全堆GC）

跨代引用问题

记忆集（Remembered Set）

卡表（Card Table）

写屏障（Write Barrier）

三种算法总结对比

实战场景

观察分代GC

常见问题与误区

❌ 误区1：分代收集是一种算法

❌ 误区2：Full GC = Major GC

❌ 误区3：老年代只使用标记-整理

总结

核心要点

与下篇文章的衔接

参考资料