04-垃圾收集算法

type

status

date

slug

summary

1️⃣ 分代收集理论

分代收集理论（Generational Garbage Collection）是一种垃圾回收策略，基于对象的生命周期特性将堆内存划分为不同代（Generation），对不同代采用不同回收算法，以提高回收效率和性能。

1. 核心假设

弱分代假说（Weak Generational Hypothesis）：

大多数对象生命周期短，很快变得不可达。
示例：方法内的临时对象（如局部变量）通常在方法结束时不可达。

强分代假说（Strong Generational Hypothesis）：

对象存活时间越长，越不容易被回收。
示例：缓存对象、单例对象（如RedisUtils的连接池）往往长期存活。

2. 分代设计

新生代（Young Generation）：

存放新创建的对象，通常生命周期短。
分为：

Eden 区：新对象分配区域。
Survivor 区（S0、S1）：存放 Minor GC 后存活的对象。

使用 复制算法（Copying Algorithm） 进行垃圾回收（Minor GC），效率高。

老年代（Old Generation）：

存放生命周期长的对象（如多次 Minor GC 后存活的对象）。
使用 标记-清除（Mark-Sweep） 或 标记-整理（Mark-Compact） 算法，回收频率较低。

元空间（Metaspace, JDK 8+）：

存储类元信息，垃圾回收较少（如类卸载）。
RedisUtils和StringUtils的类元信息存储在此。

3. 分代收集的核心思想

隔离生命周期：

短生命周期对象在新生代快速分配和回收，减少对老年代的干扰。
长生命周期对象逐步晋升到老年代，减少频繁扫描。

优化回收效率：

新生代使用复制算法，回收速度快（因为存活对象少）。
老年代使用标记算法，适合存活率高的场景。

4. 分代收集的实现

(1) 新生代（Young Generation）

Eden 区：

新对象默认分配在 Eden 区（除非大对象或栈上分配）。
String 和 Picture 对象通常分配在 Eden 区。

Survivor 区（S0、S1）：

Minor GC 时，Eden 和 From Survivor（S0）的存活对象复制到 To Survivor（S1）。
S0 和 S1 角色互换。
存活对象年龄（Age）加 1，记录在对象头。

Minor GC：

Eden 区满时触发，回收不可达对象。
存活对象移动到 Survivor 区，或晋升到老年代（若年龄超过 -XX:MaxTenuringThreshold，默认15）。

(2) 老年代（Old Generation）

对象晋升：

Survivor 区对象经过多次 Minor GC 仍存活，晋升到老年代。
大对象（超过 -XX:PretenureSizeThreshold）直接分配到老年代。
大String，可能直接进入老年代。

Major GC / Full GC：

回收老年代不可达对象，可能涉及整个堆（新生代+老年代+元空间）。
使用标记-清除或标记-整理，耗时较长。

(3) 元空间（Metaspace）

类卸载：

回收无引用的类元信息（如动态加载的类）。
反射或动态代理，可能增加元空间压力。

触发：

元空间满时触发 Full GC，回收类和常量池。

(4) 垃圾回收算法

新生代（复制算法）：

将存活对象复制到 Survivor 区，清空 Eden 和 From Survivor。
效率高，适合存活率低的场景。

老年代（标记-清除/标记-整理）：

标记-清除：标记存活对象，清除不可达对象，可能产生碎片。
标记-整理：标记后整理存活对象，消除碎片。
代码中长期存活对象（如 Redis 连接）可能触发标记-整理。

5. 分代收集的优势

高效回收：

新生代 Minor GC 快速回收短生命周期对象，减少暂停时间。

隔离生命周期：

短生命周期对象不干扰老年代，减少Full GC频率。

内存利用优化：

新生代占堆的较小部分（默认约 1/3），老年代占较大部分（约 2/3）。
灵活配置（如 -XX:NewRatio 设置新生代与老年代比例）。

适应性：

不同代使用不同算法，平衡吞吐量和延迟。

当前虚拟机的垃圾收集都采用分代收集算法，这种算法没有什么新的思想，只是根据对象存活周期的不同将内存分为几块。一般将Java堆分为新生代和老年代，可以根据各个年代的特点选择合适的垃圾收集算法。

在新生代中，每次收集都会有大量对象(近99%)死去，所以可以选择复制算法，只需要付出少量对象的复制成本就可以完成每次垃圾收集。

而老年代的对象存活几率是比较高的，而且没有额外的空间对它进行分配担保，所以选择“标记-清除”或“标记-整理”算法进行垃圾收集。

标记-清除标记-整理 会比复制算法慢10倍以上。

2️⃣ 标记-复制算法

结合了标记阶段和复制阶段，主要用于 JVM 新生代（Young Generation）的垃圾回收（Minor GC）。它基于分代收集理论的弱分代假说，即大多数对象生命周期短，存活对象较少。

标记阶段（Mark）：

遍历堆中对象，标记存活对象（从 GC Roots 开始，如栈帧中的引用、静态变量）。
使用 可达性分析，确定哪些对象仍在使用。
标记信息存储在对象头的 Mark Word 中。

复制阶段（Copy）：

将标记为存活的对象从当前区域（Eden 区和 From Survivor 区）复制到目标区域（To Survivor 区）。
复制后更新引用（调整指向新地址）。
清空原区域（Eden 和 From Survivor），释放不可达对象的内存。

角色交换：

From Survivor 和 To Survivor 角色互换（例如，S0 变为To，S1变为From）。
存活对象年龄（Age）加 1，记录在对象头。

1. 标记-复制算法的实现

(1) 新生代结构

Eden 区：新对象分配区域，占新生代大部分空间（默认 Eden:S0:S1 = 8:1:1，-XX:SurvivorRatio=8）。

Survivor 区（S0、S1）：存放 Minor GC 后的存活对象，两区交替使用。

(2) Minor GC 流程

触发条件：

Eden 区满（无法分配新对象）。

标记存活对象：

从 GC Roots（如栈帧、静态变量）开始，标记 Eden 和 From Survivor 中的存活对象。

复制存活对象：

将存活对象复制到To Survivor区。

更新引用（如栈帧中的局部变量引用）。

对象年龄加 1。

清空区域：

清空 Eden 和 From Survivor，释放不可达对象内存。

角色交换：

From Survivor和To Survivor交换角色，为下次 GC 准备。

晋升老年代：

如果对象年龄超过-XX:MaxTenuringThreshold（默认15），或 Survivor 区不足，存活对象晋升到老年代。

(3) 内存分配

TLAB（Thread Local Allocation Buffer）：

线程在 Eden 区预分配小块内存，加速对象分配。

大对象：

超过 -XX:PretenureSizeThreshold 的对象直接分配到老年代，绕过标记-复制。

2. 标记-复制算法的优缺点

(1) 优点

高效回收：

只复制存活对象，存活率低时（新生代典型场景）效率高。

无碎片：

复制到 Survivor 区时整理内存，消除碎片。
对比标记-清除算法（可能产生碎片），标记-复制更适合新生代。

简单实现：

复制算法逻辑清晰，适合新生代的复制式 GC。

(2) 缺点

内存利用率低：

Survivor 区需要预留空间（S0、S1 各占一半），浪费内存。
默认 Eden:S0:S1 = 8:1:1，Survivor 区仅占 1/10。

复制开销：

存活对象多时，复制和引用更新成本高。

依赖 Survivor 空间：

Survivor 区不足时，对象可能过早晋升到老年代，增加 Full GC 压力。

不适合老年代：

老年代存活率高，复制算法效率低（需复制大量对象）。

3️⃣ 标记-清除算法

通过标记存活对象和清除不可达对象来回收内存。它是 JVM 老年代垃圾回收（Major GC 或 Full GC）常用的算法，适合存活率较高的场景。

标记阶段（Mark）：

从 GC Roots（如栈帧中的引用、静态变量、常量池）开始，遍历堆中对象，标记存活对象。
标记信息存储在对象头的 Mark Word 中（例如，设置 GC 标记位）。
不可达对象（未被标记）视为垃圾。

清除阶段（Sweep）：

扫描堆（或老年代），识别未标记的对象，回收其内存。
将回收的内存加入空闲列表（Free List），供后续分配使用。
不移动存活对象，保持其地址不变。

1. 标记-清除算法的实现

(1) 老年代结构

老年代：

存放长期存活对象，如：

经过多次 Minor GC 仍存活的对象（年龄超过-XX:MaxTenuringThreshold，默认 15）。
大对象（超过-XX:PretenureSizeThreshold）。

与新生代的关系：

新生代（Eden、Survivor）使用标记-复制算法，存活对象晋升到老年代。
老年代使用标记-清除（或标记-整理），回收频率较低。

(2) Major GC / Full GC 流程

触发条件：

老年代满（无法分配新对象）。

新生代晋升对象时老年代空间不足。

元空间（Metaspace）满触发 Full GC。

频繁创建对象可能导致新生代对象快速晋升，间接触发 Full GC。

标记存活对象：

从 GC Roots 开始，标记老年代（或整个堆）的存活对象。

清除不可达对象：

扫描老年代，回收未标记对象的内存。

更新空闲列表，记录可用内存块。

内存分配：

新对象分配使用空闲列表（对比 Eden 区的指针碰撞）。

可能因碎片导致分配效率降低。

(3) 与其他算法的结合

标记-整理（Mark-Compact）：

标记-清除可能产生内存碎片，JVM 结合标记-整理算法，在清除后移动存活对象，整理内存。
示例：CMS（Concurrent Mark-Sweep）GC 使用标记-清除，碎片严重时触发标记-整理。

你的上下文：

Redis连接池或缓存对象可能触发标记-清除，长期运行可能需要标记-整理。

2. 标记-清除算法的优缺点

(1) 优点

适合高存活率：

老年代存活对象多，标记-清除只需处理少量垃圾，效率高。

无需复制：

对比标记-复制算法，标记-清除不移动存活对象，避免复制开销。
老年代对象多，复制成本高，标记-清除更合适。

简单实现：

标记和清除逻辑清晰，易于实现。

(2) 缺点

内存碎片：

清除不可达对象后，内存可能出现不连续的空闲块，导致碎片。
大对象分配可能失败，即使总空闲内存足够。

扫描开销：

清除阶段需扫描整个老年代，存活对象多时开销大。
Full GC 涉及整个堆（新生代 + 老年代），暂停时间长。

分配效率低：

空闲列表分配（对比 Eden 区的指针碰撞）效率较低，可能需查找合适的内存块。

4️⃣ 标记-整理算法

通过标记存活对象、清除不可达对象，并整理存活对象来回收内存和消除碎片。它是标记-清除算法的改进版本，主要用于 JVM 老年代的垃圾回收（Major GC 或 Full GC），特别适合需要解决内存碎片的场景。

(1) 算法步骤

标记阶段（Mark）:

从 GC Roots（如栈帧中的引用、静态变量、常量池）开始，遍历堆中对象，标记存活对象。

标记信息存储在对象头的 Mark Word 中（例如，设置 GC 标记位）。

不可达对象（未被标记）视为垃圾。

整理阶段（Compact）:

将标记为存活的对象移动到内存的一端（通常是堆的低地址端），使存活对象连续排列。

更新所有引用（包括栈帧、其他对象的字段等），指向存活对象的新地址。

清除剩余区域（不可达对象的内存），形成连续的空闲内存块。

内存分配:

新对象分配使用 指针碰撞（Bump the Pointer），在连续空闲内存中移动指针，效率高。

(2) 应用场景

老年代（Old Generation）:

用于 Major GC 或 Full GC，回收长期存活的对象并解决内存碎片。

分代收集理论:

强分代假说表明老年代对象存活率高，标记-整理适合处理少量垃圾并优化内存布局。
对比标记-清除（产生碎片）和标记-复制（复制开销大），标记-整理平衡了效率和内存利用率。

特定 GC 实现:

CMS（Concurrent Mark-Sweep）: 默认使用标记-清除，碎片严重时回退到标记-整理（Serial Old GC）。
G1 GC: 使用标记-整理在区域（Region）级别整理内存。
Serial Old GC: 默认使用标记-整理。

1. 标记-整理算法的实现

(1) 老年代结构

老年代:

经过多次 Minor GC 仍存活的对象（年龄超过 -XX:MaxTenuringThreshold，默认 15）。
大对象（超过 -XX:PretenureSizeThreshold）。

与新生代的关系:

新生代（Eden、Survivor）使用标记-复制算法，存活对象晋升到老年代。
老年代使用标记-清除或标记-整理，标记-整理解决碎片问题。

(2) Major GC / Full GC 流程

触发条件:

老年代满（无法分配新对象）。

新生代晋升对象时老年代空间不足。

标记-清除后碎片严重，无法分配大对象。

元空间（Metaspace）满触发 Full GC。

频繁创建大对象可能导致碎片，触发标记-整理。

标记存活对象:

从 GC Roots 开始，标记老年代（或整个堆）的存活对象。

整理存活对象:

移动存活对象到内存一端，形成连续内存块。

更新引用（如栈帧中的局部变量、其他对象的字段）。

清除剩余区域:

不可达对象的内存被清空，形成单一连续空闲块。

内存分配:

新对象分配使用指针碰撞，效率高于标记-清除的空闲列表。

(3) 与其他算法的结合

标记-清除:

标记-整理在标记-清除基础上增加整理步骤，解决碎片。
CMS GC 默认标记-清除，碎片严重时触发标记-整理。

标记-复制:

标记-复制用于新生代，整理内存但浪费空间（Survivor 区）。
标记-整理用于老年代，适合高存活率场景。

2. 标记-整理算法的优缺点

(1) 优点

消除碎片:

整理存活对象后，内存连续，适合大对象分配。

高效分配:

连续内存支持指针碰撞，分配速度快（类似 Eden 区的分配）。

适合高存活率:

老年代存活对象多，标记-整理只需处理少量垃圾，效率较高。

对比标记-清除:

解决碎片问题，提高内存利用率。

(2) 缺点

整理开销:

移动存活对象和更新引用增加 CPU 和时间开销，尤其存活对象多时。
Full GC 使用标记-整理可能导致较长暂停时间。

暂停时间长:

标记-整理是 Stop-The-World操作，暂停时间随老年代大小和存活对象数量增加。

对比标记-复制:

标记-复制适合新生代低存活率，整理内存但浪费空间。
标记-整理适合老年代高存活率，但整理开销高于复制。

5️⃣ 标记-压缩

标记：遍历对象图，标记所有可达对象。

压缩：将所有存活对象移动到堆的一端，并更新所有引用地址。

移动过程中会紧凑排列对象，消除碎片。

会改变对象在堆中的地址（需修正引用）。

整个压缩过程通常是线性的、顺序排列。

不仅清理垃圾，也消除了内存碎片。

项目	标记-压缩（Mark-Compact）	标记-整理（Mark-Sweep-Compact）
是否移动对象	是，移动所有存活对象	是，但不一定全部移动（按需移动）
是否压缩到底	是，通常压缩至堆顶（紧凑）	否，可能仅整理部分，保持块状分布
是否清除碎片	是，完全清除	是，部分清除（视策略而定）
适用收集器	Serial Old、G1 Full GC 等	G1、Shenandoah、ZGC 等现代收集器
开销/停顿	较高，全堆压缩，STW 明显	通常开销更低，有时可并发或增量处理
对象地址变化	会	可能会

6️⃣ 标记-整理、与标记-清除、标记-复制的对比

特性	标记-整理（Mark-Compact）	标记-清除（Mark-Sweep）	标记-复制（Mark-Copy）
应用场景	老年代（Major/Full GC）	老年代（Major/Full GC）	新生代（Minor GC）
存活率适用性	高存活率（老年代对象长期存活）	高存活率	低存活率（新生代对象短生命周期）
内存操作	标记存活对象，移动整理，清除不可达对象	标记存活对象，清除不可达对象	标记存活对象，复制到 Survivor，清理原区域
内存碎片	无碎片（整理后连续）	可能产生碎片	无碎片（复制整理）
性能开销	标记+整理+引用更新，暂停时间较长	标记+扫描，暂停时间中等	复制少量对象，暂停时间短
内存利用率	高（无碎片，无预留空间）	高（但碎片影响分配）	低（Survivor 区预留空间）

标记-复制: 处理新生代的 String（如 toLowerCase）、Long（如Long.valueOf），快速回收。

标记-清除: 处理老年代缓存对象，可能导致碎片。

标记-整理: 解决标记-清除的碎片问题，优化老年代内存布局。