垃圾回收算法全景

手动内存管理是 C/C++ 程序员的日常——malloc/free、RAII、智能指针，每一种都在试图回答同一个问题：一块内存什么时候可以安全释放？答错了，要么内存泄漏，要么 use-after-free。垃圾回收（Garbage Collection，GC）把这个问题交给运行时自动处理，但”自动”不意味着”简单”。从 1960 年 John McCarthy 在 Lisp 中实现第一个 GC 算法至今，垃圾回收已经演变成编程语言运行时中最复杂的子系统之一。

本文覆盖 GC 的全部核心算法：引用计数、标记-清除、标记-整理、复制 GC、分代 GC、并发三色标记，以及现代工业级实现（G1、ZGC、Go GC、Shenandoah）。每种算法都附带完整的工程分析，最后给出 Cheney 复制 GC 和分代 GC 的 C 语言实现。

一、引用计数（Reference Counting）

引用计数是最直观的 GC 策略：为每个对象维护一个计数器，记录有多少指针指向它。当计数归零时，立即释放。

1.1 基本原理

分配对象 obj:
    obj.refcount = 1

增加引用 (ptr = obj):
    obj.refcount++

减少引用 (ptr 不再指向 obj):
    obj.refcount--
    if obj.refcount == 0:
        for each child in obj.children:
            decrease_ref(child)
        free(obj)

引用计数有两个显著优点：即时回收（对象变成垃圾的瞬间就被回收，不需要等待 GC 周期）和增量开销（回收工作分散在程序运行的每一步，不会产生长时间的 STW 暂停）。

1.2 C 实现

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_CHILDREN 4

typedef struct Object {
    int refcount;
    int num_children;
    struct Object *children[MAX_CHILDREN];
    char name[16];
} Object;

Object *object_new(const char *name)
{
    Object *obj = (Object *)calloc(1, sizeof(Object));
    if (!obj) {
        fprintf(stderr, "OOM\n");
        exit(1);
    }
    obj->refcount = 1;
    strncpy(obj->name, name, sizeof(obj->name) - 1);
    return obj;
}

void object_release(Object *obj);

void object_add_child(Object *parent, Object *child)
{
    if (parent->num_children >= MAX_CHILDREN) return;
    child->refcount++;
    parent->children[parent->num_children++] = child;
}

void object_release(Object *obj)
{
    if (!obj) return;
    obj->refcount--;
    if (obj->refcount == 0) {
        printf("释放对象: %s\n", obj->name);
        for (int i = 0; i < obj->num_children; i++) {
            object_release(obj->children[i]);
        }
        free(obj);
    }
}

1.3 循环引用问题

引用计数的致命缺陷是无法处理循环引用：

A.child = B    // B.refcount = 2
B.child = A    // A.refcount = 2

释放外部对 A 和 B 的引用后:
A.refcount = 1  (B 仍然引用 A)
B.refcount = 1  (A 仍然引用 B)
// 两个对象都不会被释放，内存泄漏!

解决循环引用的方案有几种：

1.4 Python 的引用计数 + 分代 GC

Python 的内存管理是引用计数与追踪 GC 的混合体。CPython 中每个 PyObject 都有 ob_refcnt 字段：

// CPython 对象头（简化）
typedef struct _object {
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;

引用计数处理大部分回收工作。但对于容器对象（列表、字典、自定义类实例），Python 额外维护一条双向链表，用分代追踪 GC 检测循环引用：

• 第 0 代：新分配的容器对象。分配计数超过阈值（默认 700）时触发。
• 第 1 代：经历过一次第 0 代 GC 仍存活的对象。
• 第 2 代：经历过一次第 1 代 GC 仍存活的对象。

分代 GC 使用试删法：将每个容器对象的引用计数临时减去来自其他容器的引用，如果计数归零则可以回收。

1.5 Swift 的 ARC（Automatic Reference Counting）

Swift 选择了一条不同的路：编译器在编译期自动插入 retain/release 调用，不需要运行时的追踪 GC。

class Node {
    var name: String
    var next: Node?        // 强引用
    weak var prev: Node?   // 弱引用，不增加引用计数

    init(name: String) {
        self.name = name
    }

    deinit {
        print("释放 \(name)")
    }
}

var a: Node? = Node(name: "A")
var b: Node? = Node(name: "B")
a?.next = b     // B.refcount = 2
b?.prev = a     // 弱引用，A.refcount 仍为 1
a = nil         // A.refcount = 0，释放 A; B.prev 自动置 nil
b = nil         // B.refcount = 0，释放 B

ARC 的优势在于确定性析构和零运行时开销（没有 GC 暂停）。代价是程序员需要理解强引用/弱引用/无主引用的语义。ARC 的引用计数操作是原子的，在高并发场景下可能成为性能瓶颈。

二、标记-清除（Mark-Sweep）

1960 年 John McCarthy 提出的标记-清除算法是所有追踪式 GC 的基础。

2.1 算法概述

分两个阶段：

1. 标记阶段：从根集合（GC roots）出发，通过 DFS 或 BFS 遍历所有可达对象，标记为”存活”。
2. 清除阶段：遍历整个堆，回收所有未标记的对象。

GC roots 包括：栈上的局部变量、全局变量/静态变量、寄存器中的指针、JNI 全局引用（JVM）等。

2.2 伪代码

mark_sweep():
    // 标记阶段
    worklist = roots
    while worklist is not empty:
        obj = worklist.pop()
        if obj is not marked:
            mark(obj)
            for each child in obj.children:
                worklist.push(child)

    // 清除阶段
    for each obj in heap:
        if obj is not marked:
            free(obj)
        else:
            unmark(obj)  // 为下一次 GC 做准备

2.3 DFS vs BFS 标记

标记阶段可以用 DFS（深度优先）或 BFS（广度优先）遍历对象图。选择哪种策略会影响内存局部性：

实际实现中，JVM 的大部分 GC 使用显式栈的 DFS，因为递归 DFS 可能栈溢出。

2.4 优缺点

优点：能处理循环引用；不需要额外的引用计数空间；实现相对简单。

缺点：STW 暂停——标记和清除期间程序必须停止；内存碎片——回收后的空闲空间不连续；与堆大小成正比——清除阶段必须扫描整个堆。

三、标记-整理（Mark-Compact）

标记-整理在标记阶段之后，不是简单地清除垃圾，而是将所有存活对象移动到堆的一端，消除碎片。

3.1 算法步骤

mark_compact():
    // 第一遍：标记
    mark_all_reachable()

    // 第二遍：计算新地址
    free_ptr = heap_start
    for each obj in heap (地址顺序):
        if obj is marked:
            obj.forwarding = free_ptr
            free_ptr += obj.size

    // 第三遍：更新引用
    for each obj in heap:
        if obj is marked:
            for each pointer p in obj:
                *p = (*p).forwarding

    // 更新根引用
    for each root r:
        *r = (*r).forwarding

    // 第四遍：移动对象
    for each obj in heap (地址顺序):
        if obj is marked:
            move(obj, obj.forwarding)

3.2 Lisp 2 算法

Edwards 在 1974 年提出的 Lisp 2 算法是最经典的标记-整理实现。它利用对象头部的一个额外字段存储转发地址（forwarding address），只需要三次堆遍历：

1. 计算转发地址
2. 更新所有指针
3. 移动对象

3.3 Trade-offs

Mark-Compact 消除了碎片，使得内存分配变成简单的指针递增（bump allocation），这在分配密集的场景下是巨大优势。但移动对象意味着所有指向被移动对象的指针都必须更新，开销不小。

四、Cheney 复制 GC

C. J. Cheney 在 1970 年提出的半空间复制算法是一种优雅的 GC 方案，它将堆分为两半，只使用其中一半（from-space），GC 时将存活对象复制到另一半（to-space）。

4.1 算法精髓

Cheney 算法的精妙之处在于它用 BFS 遍历对象图，但不需要显式队列——to-space 本身就是队列：

cheney_collect():
    scan = free = to_space_start

    // 复制根引用的对象
    for each root r:
        *r = copy(r)

    // BFS 扫描
    while scan < free:
        obj = object_at(scan)
        for each child pointer p in obj:
            *p = copy(*p)
        scan += obj.size

copy(obj):
    if obj.forwarding is in to_space:
        return obj.forwarding  // 已复制
    new_obj = free
    memcpy(free, obj, obj.size)
    free += obj.size
    obj.forwarding = new_obj   // 在 from-space 留下转发地址
    return new_obj

• scan 指针是 BFS 的”队首”——下一个要扫描子节点的对象
• free 指针是”队尾”——下一个空闲位置
• 当 scan 追上 free 时，BFS 结束

4.2 优缺点

优点：无碎片（存活对象紧凑排列）；无递归（BFS 遍历用两个指针实现）；分配极快（指针碰撞）；只遍历存活对象。

缺点：空间浪费（只能用一半堆）；复制开销（存活对象多时复制开销大）；缓存不友好（复制后对象地址改变）。

4.3 完整 C 实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

/* ============ Cheney 半空间复制 GC ============ */

#define HEAP_SIZE    (1024 * 1024)  /* 1MB per semi-space */
#define MAX_FIELDS   8
#define MAX_ROOTS    256

typedef struct ObjHeader {
    uint32_t    size;            /* 对象总大小（含 header） */
    uint32_t    num_fields;      /* 指针字段数 */
    struct ObjHeader *forwarding; /* 转发地址 */
} ObjHeader;

typedef struct {
    uint8_t *from_space;
    uint8_t *to_space;
    uint8_t *free_ptr;           /* from-space 中下一个空闲位置 */
    uint8_t *scan_ptr;           /* to-space 中 BFS 队首 */

    ObjHeader **roots;
    int num_roots;
    int total_collections;
    size_t total_copied_bytes;
} CheneyHeap;

static CheneyHeap *cheney_create(void)
{
    CheneyHeap *heap = (CheneyHeap *)calloc(1, sizeof(CheneyHeap));
    heap->from_space = (uint8_t *)malloc(HEAP_SIZE);
    heap->to_space   = (uint8_t *)malloc(HEAP_SIZE);
    heap->free_ptr   = heap->from_space;
    heap->roots      = (ObjHeader **)calloc(MAX_ROOTS, sizeof(ObjHeader *));
    if (!heap->from_space || !heap->to_space || !heap->roots) {
        fprintf(stderr, "无法分配堆空间\n");
        exit(1);
    }
    return heap;
}

static void cheney_destroy(CheneyHeap *heap)
{
    free(heap->from_space);
    free(heap->to_space);
    free(heap->roots);
    free(heap);
}

static inline bool in_from_space(CheneyHeap *heap, void *ptr)
{
    return (uint8_t *)ptr >= heap->from_space &&
           (uint8_t *)ptr < heap->from_space + HEAP_SIZE;
}

static inline bool in_to_space(CheneyHeap *heap, void *ptr)
{
    return (uint8_t *)ptr >= heap->to_space &&
           (uint8_t *)ptr < heap->to_space + HEAP_SIZE;
}

static inline ObjHeader **obj_fields(ObjHeader *obj)
{
    return (ObjHeader **)((uint8_t *)obj + sizeof(ObjHeader));
}

/* 复制单个对象到 to-space，返回新地址 */
static ObjHeader *cheney_copy(CheneyHeap *heap, ObjHeader *obj)
{
    if (!obj) return NULL;

    /* 如果已经复制过，forwarding 指向 to-space */
    if (in_to_space(heap, obj->forwarding))
        return obj->forwarding;

    /* 复制到 to-space */
    ObjHeader *new_obj = (ObjHeader *)heap->free_ptr;
    memcpy(new_obj, obj, obj->size);
    heap->free_ptr += obj->size;
    heap->total_copied_bytes += obj->size;

    /* 在 from-space 留下转发地址 */
    obj->forwarding = new_obj;
    new_obj->forwarding = new_obj; /* 自指表示已在 to-space */

    return new_obj;
}

/* 执行 GC */
static void cheney_collect(CheneyHeap *heap)
{
    heap->total_collections++;
    heap->free_ptr = heap->to_space;
    heap->scan_ptr = heap->to_space;

    /* 复制所有根引用的对象 */
    for (int i = 0; i < heap->num_roots; i++) {
        if (heap->roots[i]) {
            heap->roots[i] = cheney_copy(heap, heap->roots[i]);
        }
    }

    /* BFS：扫描 to-space 中已复制的对象 */
    while (heap->scan_ptr < heap->free_ptr) {
        ObjHeader *obj = (ObjHeader *)heap->scan_ptr;
        ObjHeader **fields = obj_fields(obj);
        for (uint32_t i = 0; i < obj->num_fields; i++) {
            if (fields[i] && in_from_space(heap, fields[i])) {
                fields[i] = cheney_copy(heap, fields[i]);
            }
        }
        heap->scan_ptr += obj->size;
    }

    /* 交换 from-space 和 to-space */
    uint8_t *temp = heap->from_space;
    heap->from_space = heap->to_space;
    heap->to_space = temp;

    printf("[GC #%d] 复制了 %zu 字节到 to-space\n",
           heap->total_collections, heap->total_copied_bytes);
}

/* 在 from-space 中分配对象 */
static ObjHeader *cheney_alloc(CheneyHeap *heap, uint32_t num_fields)
{
    uint32_t size = sizeof(ObjHeader) + num_fields * sizeof(ObjHeader *);
    /* 8 字节对齐 */
    size = (size + 7) & ~7u;

    if (heap->free_ptr + size > heap->from_space + HEAP_SIZE) {
        cheney_collect(heap);
        if (heap->free_ptr + size > heap->from_space + HEAP_SIZE) {
            fprintf(stderr, "GC 后仍然无法分配 %u 字节\n", size);
            return NULL;
        }
    }

    ObjHeader *obj = (ObjHeader *)heap->free_ptr;
    memset(obj, 0, size);
    obj->size = size;
    obj->num_fields = num_fields;
    obj->forwarding = obj;
    heap->free_ptr += size;
    return obj;
}

/* 添加根引用 */
static int cheney_add_root(CheneyHeap *heap, ObjHeader *obj)
{
    if (heap->num_roots >= MAX_ROOTS) return -1;
    heap->roots[heap->num_roots] = obj;
    return heap->num_roots++;
}

这段代码完整实现了 Cheney 复制 GC 的核心逻辑。cheney_copy 是关键函数——它将对象复制到 to-space 并留下转发地址。cheney_collect 中的 while 循环就是 BFS：scan_ptr 是队首，free_ptr 是队尾。

五、分代假说与分代 GC（Generational GC）

5.1 分代假说（Generational Hypothesis）

1984 年 David Ungar 在论文 “Generation Scavenging” 中提出了分代假说：

大多数对象朝生暮死（Most objects die young）。

这个观察在各种语言和工作负载中都得到了验证。典型的对象生命周期分布：

对象存活率
  |
  |*
  |**
  |****
  |********
  |*****************
  |************************************************
  +-----------------------------------------------→ 对象年龄
   0     1     2     3     4     5     ...

90% 以上的对象在第一次 GC 时就已经死亡。基于这个观察，分代 GC 将堆分为：

• 年轻代（Young Generation）：新分配的对象。频繁 GC，使用复制算法（成本与存活对象成正比，存活率低则成本低）。
• 老年代（Old/Tenured Generation）：经历过多次年轻代 GC 仍存活的对象。不频繁 GC，使用标记-清除或标记-整理。

5.2 Minor GC vs Major GC

5.3 晋升（Promotion）

对象在年轻代中存活超过一定次数（晋升阈值，JVM 默认 15），就被移动到老年代。这里有个微妙的 trade-off：

• 阈值太低：大量中短命对象被过早晋升到老年代，增加 Major GC 压力
• 阈值太高：年轻代中长命对象被反复复制，浪费 CPU

JVM 的自适应策略会根据年轻代存活率动态调整晋升阈值。

5.4 写屏障（Write Barrier）

分代 GC 的一个关键问题：Minor GC 只扫描年轻代，但老年代中的对象可能引用年轻代的对象。如果不追踪这种跨代引用，就会错误地回收被老年代引用的年轻代对象。

写屏障拦截所有指针写操作，记录跨代引用：

/* 写屏障伪代码 */
void write_barrier(Object *parent, Object **slot, Object *child)
{
    if (is_old(parent) && is_young(child)) {
        /* 记录到 remembered set */
        remember(parent);
    }
    *slot = child;
}

记录跨代引用的数据结构有几种：

JVM 的 Serial/Parallel/CMS GC 使用卡表——将堆划分为 512B 的卡页，每个卡页用一个字节表示是否包含跨代引用。写屏障只需要一次内存写入：

/* JVM 卡表写屏障 */
void card_table_barrier(Object *parent, Object *child)
{
    /* card_table 是一个字节数组 */
    card_table[(uintptr_t)parent >> 9] = DIRTY;
}

5.5 分代 GC 的 C 实现

下面在 Cheney 复制 GC 的基础上实现一个简单的两代 GC：

/* ============ 分代 GC（基于 Cheney 复制 GC） ============ */

#define YOUNG_SIZE   (256 * 1024)   /* 256KB 年轻代 */
#define OLD_SIZE     (1024 * 1024)  /* 1MB 老年代 */
#define PROMOTE_AGE  3              /* 晋升年龄阈值 */
#define CARD_SHIFT   9              /* 512B 卡页 */
#define CARD_COUNT   (OLD_SIZE >> CARD_SHIFT)

typedef struct GenObjHeader {
    uint32_t    size;
    uint32_t    num_fields;
    uint8_t     age;               /* 存活代数 */
    uint8_t     generation;        /* 0 = young, 1 = old */
    struct GenObjHeader *forwarding;
} GenObjHeader;

typedef struct {
    /* 年轻代：两个半空间 */
    uint8_t *young_from;
    uint8_t *young_to;
    uint8_t *young_free;

    /* 老年代 */
    uint8_t *old_space;
    uint8_t *old_free;

    /* 卡表 */
    uint8_t *card_table;

    /* 根集合 */
    GenObjHeader **roots;
    int num_roots;

    /* 统计 */
    int minor_gc_count;
    int major_gc_count;
    size_t promoted_bytes;
} GenerationalHeap;

static GenerationalHeap *gen_create(void)
{
    GenerationalHeap *h = (GenerationalHeap *)calloc(1, sizeof(*h));
    h->young_from  = (uint8_t *)malloc(YOUNG_SIZE);
    h->young_to    = (uint8_t *)malloc(YOUNG_SIZE);
    h->old_space   = (uint8_t *)malloc(OLD_SIZE);
    h->card_table  = (uint8_t *)calloc(CARD_COUNT, 1);
    h->roots       = (GenObjHeader **)calloc(MAX_ROOTS, sizeof(GenObjHeader *));
    h->young_free  = h->young_from;
    h->old_free    = h->old_space;
    return h;
}

static void gen_destroy(GenerationalHeap *h)
{
    free(h->young_from);
    free(h->young_to);
    free(h->old_space);
    free(h->card_table);
    free(h->roots);
    free(h);
}

static inline bool in_young(GenerationalHeap *h, void *ptr)
{
    return (uint8_t *)ptr >= h->young_from &&
           (uint8_t *)ptr < h->young_from + YOUNG_SIZE;
}

static inline bool in_old(GenerationalHeap *h, void *ptr)
{
    return (uint8_t *)ptr >= h->old_space &&
           (uint8_t *)ptr < h->old_space + OLD_SIZE;
}

static inline GenObjHeader **gen_obj_fields(GenObjHeader *obj)
{
    return (GenObjHeader **)((uint8_t *)obj + sizeof(GenObjHeader));
}

/* 晋升到老年代 */
static GenObjHeader *promote_to_old(GenerationalHeap *h, GenObjHeader *obj)
{
    if (h->old_free + obj->size > h->old_space + OLD_SIZE) {
        fprintf(stderr, "老年代空间不足\n");
        return NULL;
    }
    GenObjHeader *new_obj = (GenObjHeader *)h->old_free;
    memcpy(new_obj, obj, obj->size);
    h->old_free += obj->size;
    h->promoted_bytes += obj->size;
    new_obj->generation = 1;
    obj->forwarding = new_obj;
    return new_obj;
}

/* Minor GC：复制年轻代存活对象 */
static GenObjHeader *minor_copy(GenerationalHeap *h,
                                uint8_t **free_ptr,
                                GenObjHeader *obj)
{
    if (!obj) return NULL;

    /* 已经复制过 */
    if (obj->forwarding != obj)
        return obj->forwarding;

    /* 如果不在年轻代，直接返回 */
    if (!in_young(h, obj))
        return obj;

    obj->age++;

    /* 年龄达标，晋升到老年代 */
    if (obj->age >= PROMOTE_AGE) {
        GenObjHeader *promoted = promote_to_old(h, obj);
        obj->forwarding = promoted;
        return promoted;
    }

    /* 复制到 young_to */
    GenObjHeader *new_obj = (GenObjHeader *)*free_ptr;
    memcpy(new_obj, obj, obj->size);
    *free_ptr += obj->size;
    obj->forwarding = new_obj;
    new_obj->forwarding = new_obj;
    return new_obj;
}

static void minor_gc(GenerationalHeap *h)
{
    h->minor_gc_count++;
    uint8_t *free_ptr = h->young_to;
    uint8_t *scan_ptr = h->young_to;

    /* 从根集合复制 */
    for (int i = 0; i < h->num_roots; i++) {
        if (h->roots[i] && in_young(h, h->roots[i])) {
            h->roots[i] = minor_copy(h, &free_ptr, h->roots[i]);
        }
    }

    /* 扫描卡表：找到老年代中引用年轻代的对象 */
    for (int c = 0; c < CARD_COUNT; c++) {
        if (h->card_table[c]) {
            uint8_t *card_start = h->old_space + ((size_t)c << CARD_SHIFT);
            uint8_t *card_end = card_start + (1 << CARD_SHIFT);
            if (card_end > h->old_free) card_end = h->old_free;

            uint8_t *p = card_start;
            while (p < card_end) {
                GenObjHeader *obj = (GenObjHeader *)p;
                if (obj->size == 0) break;
                GenObjHeader **fields = gen_obj_fields(obj);
                for (uint32_t f = 0; f < obj->num_fields; f++) {
                    if (fields[f] && in_young(h, fields[f])) {
                        fields[f] = minor_copy(h, &free_ptr, fields[f]);
                    }
                }
                p += obj->size;
            }
            h->card_table[c] = 0;
        }
    }

    /* BFS 扫描 young_to */
    while (scan_ptr < free_ptr) {
        GenObjHeader *obj = (GenObjHeader *)scan_ptr;
        GenObjHeader **fields = gen_obj_fields(obj);
        for (uint32_t f = 0; f < obj->num_fields; f++) {
            if (fields[f] && in_young(h, fields[f])) {
                fields[f] = minor_copy(h, &free_ptr, fields[f]);
            }
        }
        scan_ptr += obj->size;
    }

    /* 交换年轻代半空间 */
    uint8_t *temp = h->young_from;
    h->young_from = h->young_to;
    h->young_to = temp;
    h->young_free = free_ptr;

    printf("[Minor GC #%d] 晋升 %zu 字节\n",
           h->minor_gc_count, h->promoted_bytes);
}

/* 写屏障 */
static void gen_write_barrier(GenerationalHeap *h,
                              GenObjHeader *parent,
                              GenObjHeader *child)
{
    if (in_old(h, parent) && in_young(h, child)) {
        size_t card_idx = ((uint8_t *)parent - h->old_space) >> CARD_SHIFT;
        h->card_table[card_idx] = 1;
    }
}

/* 分配（年轻代） */
static GenObjHeader *gen_alloc(GenerationalHeap *h, uint32_t num_fields)
{
    uint32_t size = sizeof(GenObjHeader) + num_fields * sizeof(GenObjHeader *);
    size = (size + 7) & ~7u;

    if (h->young_free + size > h->young_from + YOUNG_SIZE) {
        minor_gc(h);
        if (h->young_free + size > h->young_from + YOUNG_SIZE) {
            fprintf(stderr, "Minor GC 后年轻代仍不足\n");
            return NULL;
        }
    }

    GenObjHeader *obj = (GenObjHeader *)h->young_free;
    memset(obj, 0, size);
    obj->size = size;
    obj->num_fields = num_fields;
    obj->forwarding = obj;
    obj->generation = 0;
    h->young_free += size;
    return obj;
}

六、并发三色标记

STW（Stop-The-World）暂停是 GC 的最大痛点。并发 GC 允许 mutator（应用线程）和 collector（GC 线程）同时运行，但这引入了一个根本性的挑战：mutator 在 GC 标记的同时修改对象图。

6.1 三色抽象

三色标记将所有对象分为三种颜色：

• 白色：未访问。GC 结束时，白色对象即为垃圾。
• 灰色：已发现但子节点未扫描完毕。灰色对象在”标记波前”上。
• 黑色：已扫描完毕。黑色对象及其直接子节点都已被标记。

标记过程可以理解为一个波前从根集合向外扩展：灰色对象构成波前，黑色在波前后方（已确认存活），白色在波前前方（待确认）。

6.2 三色不变量

并发标记的正确性依赖于维护以下不变量之一：

强三色不变量（Strong Tri-Color Invariant）： > 黑色对象不得直接指向白色对象。

如果违反，GC 可能认为白色对象不可达而回收它——但实际上黑色对象仍在引用它。

弱三色不变量（Weak Tri-Color Invariant）： > 白色对象被黑色对象引用是允许的，但前提是该白色对象同时被某个灰色对象保护（即存在从灰色对象到该白色对象的路径）。

强不变量是弱不变量的特例。在弱不变量下，黑色可以指向白色，只要有灰色”护航”。

6.3 什么时候会违反不变量？

考虑以下场景：

初始状态：
  A(黑) -> B(灰) -> C(白)

mutator 执行：
  A.field = C    // 黑色 A 直接引用白色 C
  B.field = nil  // 断开 B -> C

最终：
  A(黑) -> C(白)
  B(灰) -> (nil)

GC 扫描 B 时，发现 B 没有子节点，B 变黑。C 始终是白色——被当做垃圾回收。但 A 仍然引用 C！这就是”丢失对象”问题。

Wilson 定理指出，漏标需要同时满足两个条件： 1. mutator 将一个白色对象的引用存入黑色对象 2. mutator 删除了所有从灰色对象到该白色对象的路径

只要打破其中一个条件，就能保证正确性。

6.4 Dijkstra 写屏障（插入屏障）

打破条件 1：当 mutator 将指针写入对象时，将新引用的目标染灰。

/* Dijkstra 插入屏障 */
void dijkstra_write_barrier(Object **slot, Object *new_ptr)
{
    shade(new_ptr);      /* 将 new_ptr 标记为灰色 */
    *slot = new_ptr;
}

这维护了强三色不变量：黑色对象新增的引用目标立即变灰（不再是白色），因此黑色永远不会直接指向白色。

代价：可能产生浮动垃圾（临时引用过的对象存活到下一轮 GC）。

6.5 Yuasa 写屏障（删除屏障 / SATB）

打破条件 2：当 mutator 删除引用时，将被删除引用的旧目标染灰。这相当于保护 GC 开始时的快照——Snapshot-At-The-Beginning（SATB）。

/* Yuasa 删除屏障（SATB） */
void yuasa_write_barrier(Object **slot, Object *new_ptr)
{
    shade(*slot);        /* 将旧值标记为灰色 */
    *slot = new_ptr;
}

这维护了弱三色不变量：即使灰色对象 B 断开对白色对象 C 的引用，C 仍被染灰，GC 会继续扫描 C 的子节点。

代价：浮动垃圾更多（GC 开始时存活的对象本轮不会被回收）。

6.6 混合写屏障

Go 1.8 引入了混合写屏障，结合了 Dijkstra 和 Yuasa 两种屏障的优点：

/* Go 混合写屏障 */
void hybrid_write_barrier(Object **slot, Object *new_ptr)
{
    shade(*slot);       /* 删除屏障：保护旧值 */
    shade(new_ptr);     /* 插入屏障：保护新值 */
    *slot = new_ptr;
}

混合写屏障的关键优势：不需要在 GC 开始时对所有 goroutine 栈进行重新扫描。Go 1.7 之前使用纯 Dijkstra 插入屏障，栈上的写操作不经过屏障（为了性能），因此需要在标记结束前 STW 重新扫描所有栈。混合写屏障消除了这个需求。

6.7 三种写屏障对比

七、现代 GC 实现

7.1 G1 GC（Java，JDK 9+ 默认）

G1（Garbage First）是 JVM 的里程碑式 GC，由 David Detlefs 等人在 2004 年的论文中提出。

核心设计：

• Region-based：将堆划分为大小相等的 Region（默认 1-32MB），每个 Region 可以独立地属于年轻代或老年代。
• 可预测暂停：用户通过 -XX:MaxGCPauseMillis 设定暂停时间目标（默认 200ms），G1 根据每个 Region 的回收价值（垃圾比例 * Region 大小）选择最有价值的 Region 优先回收。

GC 阶段：

1. 初始标记（Initial Mark）：STW，标记从根直接可达的对象。与 Minor GC 同步进行。
2. 并发标记（Concurrent Marking）：与 mutator 并发，使用 SATB 写屏障追踪变化。
3. 最终标记（Final Mark/Remark）：STW，处理 SATB 缓冲区中的残余引用。
4. 清理（Cleanup）：STW，按回收价值排序 Region，回收全空 Region。
5. 混合回收（Mixed GC）：选择部分老年代 Region 和所有年轻代 Region 一起回收。

堆布局示意：
+---+---+---+---+---+---+---+---+---+---+---+---+
| E | S |   | O |   | S | O | H | O |   | E |   |
+---+---+---+---+---+---+---+---+---+---+---+---+
  E = Eden    S = Survivor    O = Old    H = Humongous
              空白 = Free

Remembered Set（RSet）：每个 Region 维护一个 RSet，记录其他 Region 中指向本 Region 的引用。这使得 G1 能够只扫描 CSet（Collection Set）中的 Region 和它们的 RSet，而不是整个堆。RSet 的空间开销通常占堆的 5-10%。

7.2 ZGC（Java，JDK 15+ 生产就绪）

ZGC 的目标是将 GC 暂停控制在 1ms 以内，不随堆大小增长。它使用两项关键技术：

着色指针（Colored Pointers）：

ZGC 在 64 位指针中”借用”几个位来存储 GC 元数据：

  63                  47 46 45 44 43 42 41          0
+---------------------+--+--+--+--+--+--------------+
|     unused (17)     |M0|M1|Re|Fn|  | offset (42)  |
+---------------------+--+--+--+--+--+--------------+
  M0, M1 = Marked bits
  Re     = Remapped bit
  Fn     = Finalizable bit
  offset = 对象地址（最大 4TB 堆）

这些元数据位使得 GC 可以在不修改对象内容的情况下追踪对象状态。

读屏障（Load Barrier）：

ZGC 使用读屏障而非写屏障。每次从堆中加载引用时，检查指针的颜色位：

/* ZGC 读屏障（概念） */
Object *load_barrier(Object **slot)
{
    Object *ptr = *slot;
    if (is_bad_color(ptr)) {
        /* 指针颜色过时，需要修复 */
        ptr = remap_and_mark(ptr);
        *slot = ptr;  /* 自愈：更新指针 */
    }
    return ptr;
}

读屏障的”自愈”特性确保每个过时的指针只触发一次修复。

并发阶段：

ZGC 的 STW 暂停只扫描根集合，不遍历对象图，因此暂停时间与堆大小无关。在 TB 级堆上仍能保持亚毫秒暂停。

7.3 Go GC：并发标记，为什么没有分代？

Go 的 GC 是一个并发的、非压缩的、非分代的标记-清除收集器。这在现代语言中是独特的选择。

为什么不分代？

Go 团队在多个场合解释了原因：

1. 值语义减少了堆分配：Go 的结构体是值类型，小对象经常在栈上分配。
2. 编译器逃逸分析：不逃逸的对象分配在栈上，函数返回后直接回收。
3. 写屏障开销：分代 GC 需要写屏障记录跨代引用，Go 追求低延迟。
4. 复杂度：分代 GC 增加大量实现复杂度。Go 团队倾向于用更简单的方式达到”足够好”的性能。

Go GC 流程：

                   ┌─── 并发标记 ───┐
       STW         │   (mutator     │         STW          并发清除
  标记准备阶段 ─→  │    同时运行)    │  ─→  标记终止阶段 ─→ (后台)
  （开启写屏障）    │               │     （关闭写屏障）
                   └───────────────┘

Go 1.5 引入并发 GC，大幅降低了暂停时间。Go 1.8 引入混合写屏障，消除了栈重扫描。到 Go 1.12，STW 暂停通常在 1ms 以内。

GOGC 参数：控制 GC 触发频率。默认值 100 表示当堆增长到上次 GC 后存活大小的 2 倍时触发 GC。GOGC=200 表示 3 倍时触发，GOGC=50 表示 1.5 倍时触发。

7.4 Shenandoah GC（OpenJDK）

Shenandoah 是 Red Hat 主导开发的低延迟 GC，目标与 ZGC 类似但实现方式不同。

核心特性：并发整理（在 mutator 运行的同时移动对象）；Brooks 转发指针（每个对象前面有一个额外的指针字段，指向对象自身或新位置）。

未移动的对象：
+-------------+----------+
| fwd_ptr (→自身) | 对象内容 |
+-------------+----------+

已移动的对象（from-space 中的残影）：
+-------------+----------+
| fwd_ptr (→新位置) | 旧内容 |
+-------------+----------+

与 ZGC 的对比：

八、GC 算法对比总表

九、工程陷阱与最佳实践

9.1 工程陷阱表

9.2 GC 调优基本流程

1. 开启 GC 日志
   JDK 17+: -Xlog:gc*:file=gc.log:time,level,tags
   Go:      GODEBUG=gctrace=1

2. 确定目标
   - 吞吐量优先 → Parallel GC / 增大堆
   - 延迟优先   → ZGC / Shenandoah / Go GC
   - 内存优先   → Serial GC / 压缩堆

3. 分析日志
   - Minor GC 频率和暂停时间
   - Major GC 频率和暂停时间
   - 晋升速率
   - 堆使用曲线

4. 调整参数
   - 堆大小（-Xms, -Xmx）
   - 年轻代比例（-XX:NewRatio）
   - GC 算法选择

5. 验证
   - 压测环境回归
   - P99 延迟对比
   - 内存使用对比

9.3 各语言 GC 选择建议

十、GC 的理论极限

10.1 时空 Trade-off

GC 存在一个基本的时空权衡，Appel 在 1987 年证明了：

给定足够大的堆（2 倍活跃数据），复制 GC 的摊销 GC 时间可以任意接近零。

直觉很简单：如果堆足够大，每次 GC 时存活对象只占堆的很小比例，复制开销很低。但代价是内存使用量翻倍。

实际表现：

吞吐量
  |                          ___________
  |                    _____/
  |              _____/
  |        _____/
  |  _____/
  | /
  |/
  +------------------------------------------→
  1x    2x    3x    4x    5x     堆/活跃数据 比率

10.2 并发 GC 的开销

并发 GC 并非”免费”——它用吞吐量换延迟。典型开销：

• 写/读屏障：每次指针操作增加 2-5 条指令。吞吐量下降 5-15%。
• 并发整理的 CPU 占用：GC 线程与 mutator 竞争 CPU。通常占 25% 的 CPU。
• 浮动垃圾：并发 GC 无法回收标记阶段新产生的垃圾，必须等到下一轮。
• 内存开销：SATB 缓冲区、标记位图、RSet 等辅助数据结构。

10.3 GC 暂停的理论下界

GC 暂停的下界取决于根集合大小。并发 GC 仍需在 STW 中扫描根集合：暂停时间 ≥ O(|roots|)。Go 通过减少全局变量和优化栈扫描将根集合降到最小。ZGC 通过分批处理根集合进一步缩短暂停。

十一、GC 的历史与演进

垃圾回收的历史是计算机科学中最有趣的演化之一。

十二、个人思考

写完这篇文章，有几点感想：

1. GC 设计反映了语言的价值取向。 Go 选择简单的并发标记-清除而非分代 GC，不是因为分代不好，而是因为 Go 的值语义和逃逸分析已经大幅减少了堆上的短命对象。Java 选择复杂的分代 + 并发方案，是因为 Java 的一切都是堆分配的对象。Swift 选择 ARC，是因为移动端需要确定性的内存行为。每种选择在自己的上下文中都是合理的。

2. “没有 GC 暂停”是个不精确的说法。 即使是 ZGC 和 Go GC，也有极短的 STW 暂停（微秒到毫秒级）。区别在于暂停时间是否与堆大小相关。对于硬实时系统，任何 GC 都不够好——只有手动内存管理或 Arena 分配才能满足需求。

3. GC 调优是经验科学。 理论上的最优参数取决于工作负载的分配模式和对象生命周期分布。我见过太多团队花数周调优 GC 参数，最终发现问题出在应用代码——减少不必要的分配比调任何 GC 参数都有效。

4. Rust 的所有权系统是 GC 的另一个极端。 编译期证明所有权和生命周期，运行时零开销。代价是学习曲线。从理论角度看，Rust 将运行时问题转化为编译时问题——但这只在语言从设计之初就支持这种模型时才可行。

5. 分代假说不是普遍真理。 在某些工作负载中（例如缓存服务器），大部分对象都是长命的。分代 GC 在这种场景下表现不如非分代方案——年轻代频繁 GC 但几乎所有对象都晋升，徒增开销。Go 团队不采用分代 GC，部分原因正在于此。

参考资料

1. McCarthy, J. “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.” Communications of the ACM, 1960.
2. Cheney, C. J. “A Nonrecursive List Compacting Algorithm.” Communications of the ACM, 1970.
3. Ungar, D. “Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm.” ACM SIGPLAN Notices, 1984.
4. Wilson, P. R. “Uniprocessor Garbage Collection Techniques.” IWMM, 1992.
5. Detlefs, D. et al. “Garbage-First Garbage Collection.” ISMM, 2004.
6. Blackburn, S. M. and McKinley, K. S. “Immix: A Mark-Region Garbage Collector.” PLDI, 2008.
7. Go Team. “Getting to Go: The Journey of Go’s Garbage Collector.” blog.golang.org, 2018.
8. Lidén, P. and Karlsson, S. “ZGC: A Scalable Low-Latency Garbage Collector.” Oracle, 2018.
9. Flood, C. H. et al. “Shenandoah: An Open-Source Concurrent Compacting Garbage Collector.” PPPJ, 2016.
10. Jones, R., Hosking, A., and Moss, E. “The Garbage Collection Handbook.” CRC Press, 2011.

算法系列导航：上一篇：SSA 形式与编译器优化 | 下一篇：缓存无关算法

相关阅读：Epoch-Based Reclamation | Hazard Pointers