Lesson 65: 标记-清除垃圾回收

练习任务

难度：中

在包含 16 个对象的固定堆上，实现一个基于标记- 清除 (Mark-Sweep) 算法的微型垃圾回收器。需要完成 5 个核心函数：

mark_recursive(int idx) — DFS 递归标记从 idx 出发的所有可达对象，marked 位充当 visited 集合防止循环引用无限递归
sweep(void) — 线性扫描整个堆，回收所有未标记对象（重置 refs 与 ref_count），返回回收数
print_objects(const char *label) — 格式化打印堆中中所有对象状态
gc_collect(void) — 协调标记与清除两阶段，打印汇总统计
main(void) — 驱动：初始化→打印 GC 前状态→执行 GC→打印 GC 后状态

根集合：roots[] = {OBJ0, OBJ3, OBJ5}。对象图的引用关系包含 OBJ5→OBJ6→OBJ7→OBJ5 循环引用，marked 位检查是处理该循环的核心机制。

./mark_sweep

输出将展示 GC 前后对象状态的变化，标记阶段的三轮 DFS 遍历，清除阶段的 8 个垃圾回收，以及 GC 汇总统计。

提示：marked 位的本质是"visited 集合"——标记不仅要记录存活，更要截断循环引用链防止栈溢出。先检查 heap[idx].marked 再标记自身，顺序不可颠倒。

核心知识点

可达性与根集合 — GC 的核心定理：可达对象=将来可能被访问→保留；不可达对象=垃圾→安全回收。根集合是可达性分析的唯一起点，漏根=错误回收（崩溃），多根=垃圾残留（泄漏）
标记阶段 DFS — 从每个根出发递归遍历引用图，marked 位即 visited 数组，防止循环引用导致的无限递归
清除阶段线性扫描 — O(HEAP_SIZE) 遍历，回收 marked==0 的对象，重置其 refs 和 ref_count
三色标记抽象 — Dijkstra 的理论框架：白(未访问)→灰(已标记子节点未处理)→黑(全部处理完)。本实现的递归调用栈隐式充当"灰色集合"
Stop-the-World — GC 执行时暂停程序(mutator)，因为程序可能在标记期间修改对象图。现代 GC 用写屏障(write barrier) 实现并发标记
碎片问题 — 标记-清除不移对象→回收后空闲空间散布→总空间够但无法分配大对象。标记-整理与复复制 GC 通过移动对象解决
C 语言与 GC — C 标准无 GC，Boehm GC 提供保守式 GC（将栈/寄存器中"像指针"的值都视为根）。本题是精确式 GC 简化版

代码框架

65_mark_sweep_gc.c

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

#define HEAP_SIZE 16

typedef struct {
    int marked;    /* 0=未标记, 1=已标记(可达) */
    int refs[2];   /* 最多 2 个引用(-1=无) */
    int ref_count; /* 实际引用数(0,1,2) */
} Object;

static Object heap[HEAP_SIZE];
static int roots[] = {0, 3, 5};
static int root_count = 3;

/* --- init_heap: 构建对象图 --- */
static void init_heap(void) {
    memset(heap, 0, sizeof(heap));
    for (int i = 0; i < HEAP_SIZE; i++)
        heap[i].refs[0] = heap[i].refs[1] = -1;

    /* OBJ0→OBJ1→OBJ2 */
    heap[0].refs[0] = 1; heap[0].ref_count = 1;
    heap[1].refs[0] = 2; heap[1].ref_count = 1;
    heap[2].ref_count = 0;
    /* OBJ3→OBJ4 */
    heap[3].refs[0] = 4; heap[3].ref_count = 1;
    heap[4].ref_count = 0;
    /* OBJ5→OBJ6→OBJ7→OBJ5 (循环!) */
    heap[5].refs[0] = 6; heap[5].ref_count = 1;
    heap[6].refs[0] = 7; heap[6].ref_count = 1;
    heap[7].refs[0] = 5; heap[7].ref_count = 1;
    /* OBJ8: 孤立; OBJ9-OBJ15: 未使用 */
    heap[8].ref_count = 0;
}

/* TODO 1: DFS 递归标记 */
#error TODO 1: mark_recursive(int idx)

/* TODO 2: 清除未标记对象 */
#error TODO 2: sweep(void)

/* TODO 3: 打印对象状态 */
#error TODO 3: print_objects(const char *label)

/* TODO 4: GC 主流程 */
#error TODO 4: gc_collect(void)

int main(void) {
    /* TODO 5: 初始化、打印、GC、打印 */
    return 0;
}

深度讲解

1. GC 的动机——手动内存管理的四类错误

C 语言 malloc/free 的手动管理天然容易出错：

错误类型	示例	后果
内存泄漏	`malloc` 后忘记 `free`	内存逐渐耗尽
悬空指针	`free` 后继续使用指针	未定义行为/崩溃
双重释放	同一指针 `free` 两次	堆损坏/崩溃
释放错误地址	`free` 栈变量或偏移指针	堆损坏/崩溃

GC 让系统自动判断对象是否不再需要并回收，消除上述所有手动管理错误。1959 年 John McCarthy 在发明 Lisp 时引入 GC 概念，至今几乎所有高级语言都内置 GC。

2. 根集合——可达性分析的唯一起点

程序执行状态:
  ┌──────────┐  ┌──────────┐  ┌──────────┐
  │ 全局变量  │  │ 栈局部变量 │  │ CPU寄存器 │
  │ glob_ptr │  │ loc_ptr  │  │   R1     │
  └────┬─────┘  └────┬─────┘  └────┬─────┘
       │             │             │
       └─────────┬───┴─────────────┘
                 ▼
    根集合 = {这些变量指向的所有对象}

从根集合出发，通过指针引用可以到达的所有对象称为可达对象。根→A→B→C：A、B、C 都可保留留无路径从根到达的 E 即是垃圾。

核心定理：可达对象 = 将来可能被程序访问 → 必须保留；不可达对象 = 垃圾 → 可以安全回收。根集合的准确性直接决定 GC 正确性。

3. 标记阶段——DFS 与循环引用截断

mark_recursive 是标记阶段的核心，本质是图的 DFS 遍历：

mark_recursive_logic.c

void mark_recursive(int idx) {
    // ① 边界检查：防止数组越界
    if (idx < 0 || idx >= HEAP_SIZE) return;
    // ② visited 检查：防止循环引用无限递归
    if (heap[idx].marked) return;
    // ③ 标记当前节点
    heap[idx].marked = 1;
    // ④ 递归标记所有子节点
    for (int i = 0; i < heap[idx].ref_count; i++)
        mark_recursive(heap[idx].refs[i]);
}

marked 检查必须放在标记之前——若先标记再检查，marked==1 始终为真，递归永远不会中止。对于 OBJ5→OBJ6→OBJ7→OBJ5 循环，marked 检查在 OBJ7 试图回到 OBJ5 时立即截断递归链。

4. 三色标记——Dijkstra 的理论抽象

颜色	含义	本实现对应
白色	尚未被访问，可能是垃圾	`marked=0` 的初始/最终垃圾对象
灰色	已标记，但子节点尚未处理	递归调用栈上的帧（隐式表达）
黑色	已标记，且所有子节点已处理	递归返回后的对象

本题简化使用 marked 位实现二色标记，递归调用栈隐式替代灰色队列。这是 DFS 实现的三色标记——栈帧即灰色集合。

5. 清除阶段——线性扫描回收

sweep_logic.c

int sweep(void) {
    printf("Sweeping (reclaiming unmarked objects):\n");
    int collected = 0;
    for (int i = 0; i < HEAP_SIZE; i++) {
        if (heap[i].marked == 0) {
            printf("  OBJ%d reclaimed\n", i);
            heap[i].refs[0] = heap[i].refs[1] = -1;
            heap[i].ref_count = 0;
            collected++;
        }
    }
    return collected;
}

清除阶段线性扫描 O(HEAP_SIZE)，不做任何图遍历。这是标记-清除的优势——标记阶段已经完成了所有识别工作，清除只需一次平淡的遍历。

6. 碎片问题与后续发展

标记-清除除不移动对象，回收后空闲空间散布在存活对象之间：

回收前: [A][B][C][D][E][F][G][H]
回收后: [A][B][C][D][.][.][.][.]
           存活区      空闲区(不连续)

总空闲空间虽够，但可能无法分配大对象——这就是碎片问题。标记-整理 (Mark-Compact) 通过滑动存活对象消除碎片；复制 GC (Copying) 将存活对象搬到新区实现 compact。理解标记-清除才能理解这些优化。

参考解答

练习1: mark_recursive — DFS 递归标记

solution_65_mark_recursive.c

/* mark_recursive: DFS 从 idx 出发标记所有可达对象
 * marked 位充当 visited 集合，防止循环引用无限递归 */
void mark_recursive(int idx) {
    if (idx < 0 || idx >= HEAP_SIZE) return;  /* 边界 */
    if (heap[idx].marked) return;              /* 已访问→截断 */

    heap[idx].marked = 1;  /* 标记存活 */

    for (int i = 0; i < heap[idx].ref_count; i++)
        mark_recursive(heap[idx].refs[i]);
}

要点：marked 检查查必须在标记之前。对于 OBJ5→OBJ6→OBJ7→OBJ5 循环，OBJ7 递归回到 OBJ5 时 marked 已为 1，立即返回。

练习2: sweep — 清除未标记对象

solution_65_sweep.c

int sweep(void) {
    printf("Sweeping (reclaiming unmarked objects):\n");
    int collected = 0;

    for (int i = 0; i < HEAP_SIZE; i++) {
        if (heap[i].marked == 0) {
            printf("  OBJ%d reclaimed\n", i);
            heap[i].refs[0] = -1;
            heap[i].refs[1] = -1;
            heap[i].ref_count = 0;
            collected++;
        }
    }
    return collected;
}

要点：回收对象需重置 refs 和 ref_count。存活对象的 marked 位保留为 1 以便后续输出。

练习3: print_objects — 格式化打印对象状态

solution_65_print_objects.c

void print_objects(const char *label) {
    printf("%s\n", label);
    for (int i = 0; i < HEAP_SIZE; i++)
        printf("  OBJ%-2d: marked=%d  refs=[%2d, %2d]  ref_count=%d\n",
               i, heap[i].marked, heap[i].refs[0],
               heap[i].refs[1], heap[i].ref_count);
}

要点：格式必须精确——OBJ%-2d(左对齐宽度 2)、%2d(右对齐宽度 2)，否则 diff 不通过。

练习4: gc_collect — 协调 Mark+Sweep 两阶段

solution_65_gc_collect.c

void gc_collect(void) {
    printf("=== Mark Phase ===\n");

    for (int i = 0; i < root_count; i++) {
        printf("Marking from root OBJ%d...\n", roots[i]);
        mark_recursive(roots[i]);
    }

    printf("\n=== Sweep Phase ===\n");
    int collected = sweep();
    printf("\n=== GC Summary ===\n");

    int alive = 0;
    for (int i = 0; i < HEAP_SIZE; i++)
        if (heap[i].marked) alive++;

    printf("Objects collected: %d\n", collected);
    printf("Objects alive:     %d\n", alive);
}

要点：alive 计数应遍历统计 marked==1 的对象，而非用 HEAP_SIZE - collected（语义不同）。

练习5: main — 驱动函数

solution_65_main.c

int main(void) {
    init_heap();

    printf("=== Before GC: Initial Object Graph ===\n");
    print_objects("Object states (before marking):");
    printf("\n");

    gc_collect();
    printf("\n");

    printf("=== After GC: Final State ===\n");
    print_objects("Object states (after sweep):");
    return 0;
}

要点：先 init_heap() 不然 heap 全为零；各阶段之间用空行分隔；输出顺序必须一致。

对照检查：marked 检必须在标记之前吗？sweep 重置了 refs 和 ref_count 吗？print 使用 %-2d 和 %2d 格式了吗？alive 统计遍历 marked==1 吗？main 调用了 init_heap() 吗？

课堂讨论

如果去掉 marked 检查检查，程序会发生什么？
三色标记中的灰色集合在本实现中是如何体现的？
碎片问题有多严重？举一个具体例子。

讨论答案

Q1: 去掉 marked 检查的后果

OBJ5→OBJ6→OBJ7→OBJ5 的循环会导致 mark_recursive 无限递归，每次调用消耗栈空间。最终栈溢出，程序收到 SIGSEGV 信号崩溃。这是"图遍历忘记 visited 集合"的经典错误——在处理循环引用时，marked 位不仅是存活标记，更是 DFS 的终止警卫（sentinel）。

Q2: 灰色集合的隐式表达

本实现没有显式的灰色集合。递归调用栈隐式充当灰色集合——栈上的每个帧代表一个"已标记但子节点尚未完全处理"的对象。当 mark_recursive(idx) 开始执行时，idx 进入灰色状态（已标记，正在遍历子节点）；当递归返回时，idx 从灰色变为黑色（子节点全部处理完毕）。这是 DFS 实现的三色标记——栈帧即灰色集合。

Q3: 碎片的具体量化

假设堆 100 字节，分配 10 个 8 字节对象后交替回收 5 个。存活对象位于偏移 0-7、16-23、32-39、48-55、64-71。空闲区间：8-15、24-31、40-47、56-63、72-99。总空闲 = 5×8 + 28 = 68 字节，但最大连续空闲块仅 28 字节。如果要分配 30 字节对象，即使总空闲 68 字节也会失败。这就是"有空间但无法分配"的碎片困境。

课后练习

迭代版标记。将 mark_recursive 改为使用显式栈的迭代版本，消除递归调用栈深度限制。

知识点提示：用 int stack[HEAP_SIZE] 模拟递归，手动 push/pop。先 push 根节点，循环弹出栈顶、标记、push 子节点。

参考解答

ex1_iterative_mark.c

void mark_iterative(int start) {
    int stack[HEAP_SIZE];
    int top = 0;

    stack[top++] = start;

    while (top > 0) {
        int idx = stack[--top];

        if (idx < 0 || idx >= HEAP_SIZE) continue;
        if (heap[idx].marked) continue;

        heap[idx].marked = 1;

        /* 子节点入栈（顺序不影响正确性） */
        for (int i = 0; i < heap[idx].ref_count; i++)
            stack[top++] = heap[idx].refs[i];
    }
}

在生产级 GC 中迭代版本是必选项——对象图深度可能远超调用栈大小。

参考资料

Dijkstra, E.W. et al. "On-the-Fly Garbage Collection." CACM, 1978. (三色标记的原始论文)
Jones, R., Hosking, A., Moss, E. The Garbage Collection Handbook. CRC Press, 2012. (GC 领域权威参考书)
McCarthy, J. "Recursive Functions of Symbolic Expressions." CACM, 1960. (Lisp 与 GC 的起源)
Boehm, H.J., Weiser, M. "Garbage Collection in an Uncooperative Environment." 1988. (C/C++ 保守式 GC)

"自动化不是消除了工作，而是提升了工作层级。" — 改写自 Dijkstra

Lesson 65: 标记-清除垃圾回收 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. GC 的动机——手动内存管理的四类错误 ​

2. 根集合——可达性分析的唯一起点 ​

3. 标记阶段——DFS 与循环引用截断 ​

4. 三色标记——Dijkstra 的理论抽象 ​

5. 清除阶段——线性扫描回收 ​

6. 碎片问题与后续发展 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 65: 标记-清除垃圾回收

练习任务

核心知识点

代码框架

深度讲解

1. GC 的动机——手动内存管理的四类错误

2. 根集合——可达性分析的唯一起点

3. 标记阶段——DFS 与循环引用截断

4. 三色标记——Dijkstra 的理论抽象

5. 清除阶段——线性扫描回收

6. 碎片问题与后续发展

参考解答

课堂讨论

讨论答案

课后练习

参考资料