垃圾回收算法

自动内存管理的核心算法——从引用计数到并发增量 GC。

概念

垃圾回收 (Garbage Collection) 是托管运行时的基础设施。与 C 的 malloc/free 不同，GC 自动判定对象何时不再可达并回收其内存。在游戏引擎、数据库和操作系统中，极致的 GC 暂停时间是关键设计目标。本文件覆盖七种核心 GC 策略。

GC 算法矩阵

算法	回收精度	内存碎片	Stop-The-World	典型应用
引用计数 (Ref Counting)	精确	低 (可配合 compact)	无 (分散到每次操作)	CPython, Objective-C, Swift (ARC)
标记-清除 (Mark-Sweep)	精确	高	全程 STW	Ruby MRI, 早期 Lisp
标记-压缩 (Mark-Compact)	精确	无	全程 STW	.NET 大对象堆
复制 (Copying / Scavenge)	精确	无	全程 STW (但短)	V8 新生代, JVM Survivor
分代 (Generational)	精确	低	仅新生代 STW	V8, JVM, .NET
并发标记 (Concurrent Mark)	精确	高	仅快照/remark	G1GC, ZGC, Go GC
引用计数 + 循环检测	精确	低	循环检测时 STW	CPython 循环收集

标记-清除

算法 Mark-Sweep:
 标记阶段:
 从 GC Roots (栈变量, 全局变量, 寄存器) 出发
 深度优先或广度优先遍历对象图
 每个可达对象打上标记 (mark bit = 1)

 清除阶段:
 线性遍历整个堆:
 IF 对象未标记:
 free(object) # 加入空闲链表
 ELSE:
 清除标记 (为下次 GC 做准备)

标记-压缩

算法 Mark-Compact (二指法):
 # 第一阶段: 标记 (同 Mark-Sweep)
 # 第二阶段: 计算新地址
 free = heap_start
 FOR 每个存活对象 obj (按地址顺序):
 obj.forwarding_address = free
 free += obj.size

 # 第三阶段: 修正指针
 FOR 每个存活对象 obj:
 FOR 每个引用字段 ref IN obj:
 ref = ref.forwarding_address

 # 第四阶段: 移动对象
 FOR 每个存活对象 obj:
 memmove(obj.forwarding_address, obj, obj.size)

复制 GC (Scavenge)

算法 Cheney 复制:
 # 堆分为 From 空间和 To 空间
 scan = To_start
 free = To_start

 # 复制所有 GC Roots 指向的对象到 To 空间
 FOR 每个 root:
 obj = *root
 *root = copy_to_tospace(obj) # 复制 + 设置 forwarding

 # 广度优先复制
 WHILE scan < free:
 遍历 scan 指向对象的每个引用字段 ref:
 IF ref 在 From 空间:
 *ref = copy_to_tospace(*ref)
 scan = scan + scan->size

 # 完成后, From 空间整块释放
 swap(From, To)

分代 GC

算法 分代假说:
 "大多数对象朝生夕死" (Weak Generational Hypothesis)
 "老对象很少引用新对象"

 堆分为:
 Nursery (新生代 / Young Generation):
 新分配的对象
 频繁 GC (Minor GC)
 使用复制算法 (Scavenge)

 Tenured (老生代 / Old Generation):
 经历了若干次新生代 GC 后存活的对象
 低频 GC (Major GC / Full GC)
 使用标记-压缩或并发标记

 写屏障 (Write Barrier):
 当老对象引用新对象时触发记录
 避免 Minor GC 扫描整个老生代

引用计数

算法 朴素引用计数:
 每个对象有一个 ob_refcnt 字段

 INCREF(obj):
 obj.ob_refcnt += 1

 DECREF(obj):
 obj.ob_refcnt -= 1
 IF obj.ob_refcnt == 0:
 # 级联释放
 FOR 每个 obj 引用的 child:
 DECREF(child)
 free(obj)

 问题: 循环引用
 a.next = b; b.prev = a
 a.ob_refcnt = 2 (来自: 栈变量, b.prev)
 b.ob_refcnt = 2 (来自: a.next, 栈变量)
 栈变量离开作用域:
 DECREF(a) → a.ob_refcnt = 1 (b.prev 仍引用)
 DECREF(b) → b.ob_refcnt = 1 (a.next 仍引用)
 两者永不回收 → 内存泄漏!

 解决: 循环检测器 (CPython 的 gc 模块)
 只检测容器类型 (list, dict, set, 用户类)
 标记可达性分析 + 清理不可达循环的引用计数

---