垃圾回收算法详解

垃圾回收解决两个问题：哪些对象该回收、如何回收。前者靠可达性分析，后者靠具体的收集算法。理解四种基础算法与并发标记方案，是看懂各种垃圾回收器实现的前提。

可达性分析

从一组 GC Roots 出发，沿引用链遍历，凡不可达的对象即为可回收对象。GC Roots 包括：

虚拟机栈中引用的对象
静态属性引用的对象
常量引用的对象
本地方法栈中 JNI 引用的对象
活跃线程

可达性分析需要"枚举根节点"并"递归遍历对象图"，这两步都要暂停用户线程（STW）。

三种基础算法

标记-清除（Mark-Sweep）

最基础的算法，分两阶段：

标记阶段：从 GC Roots 出发，标记所有可达对象
清除阶段：遍历堆，回收未被标记的对象

优点	缺点
实现简单，不需要移动对象	产生大量内存碎片
对不连续空间友好	分配新对象时需遍历空闲链表，效率下降

内存碎片积累后，大对象可能因找不到连续空间而提前触发 Full GC。

标记-复制（Mark-Copy）

将可用内存等分为两块，每次只用一块。GC 时把存活对象复制到另一块，再整块清除当前块。

┌─────────────┬─────────────┐
│  使用中 A     │  空闲 B      │  ← GC 前
└─────────────┴─────────────┘
┌─────────────┬─────────────┐
│  空闲 A      │  存活对象 B   │  ← GC 后（存活对象复制到 B）
└─────────────┴─────────────┘

优点	缺点
复制后空间连续，无碎片	内存利用率只有一半
存活对象少时效率极高	存活对象多时复制开销大

因此它适合"朝生夕灭"的新生代。HotSpot 新生代把空间划分为 Eden:S0:S1 = 8:1:1，只浪费 10% 空间，比对半分更经济。

标记-整理（Mark-Compact）

标记存活对象后，将所有存活对象向一端移动，再清理边界以外的内存。

标记后：▓存活▓  ▓存活▓   ▓存活▓   （▓ 为存活对象）
整理后：▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓         （存活对象紧凑排列，其余整块清除）

优点	缺点
内存连续无碎片	移动对象 + 更新引用代价高
空间利用率 100%	STW 时间长

适用于存活率高、碎片化严重的老年代。

三种算法对比

算法	内存利用率	碎片	适合场景
标记-清除	100%	有	老年代（CMS 用）
标记-复制	低（50% 或 90%）	无	新生代
标记-整理	100%	无	老年代

分代收集理论

分代理论依据弱分代假设（大多数对象朝生夕灭）与强分代假设（越老的对象越难死亡），把堆划分为新生代与老年代，各自使用不同算法：

新生代：存活率低 → 标记-复制，Minor GC
老年代：存活率高、无额外空间 → 标记-清除或标记-整理，Major GC / Full GC

同时引入跨代引用问题：老年代对象引用新生代对象时，Minor GC 若扫描整个老年代成本太高，于是引入记忆集（Remembered Set）：记录老年代中指向新生代的引用，GC 时只扫描这部分，而不是整个老年代。

三色标记与并发标记

可达性分析需要遍历整个对象图，若全程 STW，大堆停顿难以接受。并发标记把"遍历对象图"与用户线程并行，通过三色标记描述对象状态：

颜色	含义
白色	未被访问，可能是垃圾
灰色	已被访问，但其引用尚未全部扫描
黑色	已被访问，且其所有引用都已扫描

白色对象 ← 正在扫描的灰色对象 → 已完成的黑色对象

并发标记过程中用户线程可能修改引用，产生两种问题：

漏标（错杀）：本应存活的对象被误判为垃圾——黑色对象新增了指向白色对象的引用，且该灰色引用路径已被扫描完，导致白色对象永远无法变灰。这是必须避免的错误。
错标（误活）：本应回收的对象被当成存活——对正确性无害，只是多保留一轮。

消除漏标需要满足任一条件（写屏障）：

方案	做法	使用方
增量更新（Incremental Update）	记录黑色对象新增的引用，之后重新扫描该黑色对象	CMS
原始快照（SATB）	记录被删除的灰色→白色引用，按快照标记（保留删除前引用指向的对象）	G1、ZGC

增量更新

黑色对象在并发标记阶段新增指向白色对象的引用时，把该黑色对象重新标记为灰色，等待重新扫描。相当于"记录新引用，追查新目标"。

原始快照（Snapshot At The Beginning）

当灰色对象删除指向白色对象的引用时，将删除前的引用记录下来，保证这些白色对象在本次 GC 中仍被标记为存活。相当于"记录旧引用，保住旧目标"。缺点是可能保留本轮本可回收的对象（浮动垃圾），但保证了正确性。

浮动垃圾

并发标记期间产生的新垃圾（本轮无法回收，留到下轮），以及 SATB 保守保留的对象，统称浮动垃圾。它占用的空间在下一轮 GC 才会被回收，是并发回收器特有的代价。

小结

新生代用复制、老年代用标记-清除/整理，这是分代收集的基石
并发回收必须解决"并发修改导致漏标"问题
CMS 用增量更新，G1/ZGC 用原始快照，两种方案各有取舍

垃圾回收算法详解 ​

可达性分析 ​

三种基础算法 ​

标记-清除（Mark-Sweep） ​

标记-复制（Mark-Copy） ​

标记-整理（Mark-Compact） ​

三种算法对比 ​

分代收集理论 ​

三色标记与并发标记 ​

增量更新 ​

原始快照（Snapshot At The Beginning） ​

浮动垃圾 ​

小结 ​