垃圾回收算法

自动内存管理的核心算法——从引用计数到并发增量 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, 用户类)
        标记可达性分析 + 清理不可达循环的引用计数

---