淡海水头像
关注
02-01-原理篇-Mark-Sweep与变种算法封面图

02-01-原理篇-Mark-Sweep与变种算法

Mark-Sweep 与变种算法

篇章：02-原理篇
阅读时间：约 40 分钟
前置知识：了解 GC 基本概念

一、引言

垃圾回收（Garbage Collection，简称 GC）的核心使命可以归结为一个问题：如何自动识别并回收不再被程序使用的内存？ 在数十年的 GC 发展史中，最基础也最经典的算法家族就是 Mark-Sweep（标记-清扫） 及其变种。

Mark-Sweep 由 John McCarthy 在 1960 年为 Lisp 语言首次提出，它是所有追踪式 GC（Tracing GC）的鼻祖。在此之后，为了解决 Mark-Sweep 的内存碎片化问题，衍生出了 Mark-Compact（标记-压缩） 算法；为了解决压缩开销大的问题，又诞生了 Copying（复制） 算法。这三种算法构成了现代 GC 的基石，几乎所有工业级 GC 实现（包括 .NET 的 GC、Java HotSpot 的 G1/ZGC、V8 的 Orinoco）都是在这三种算法的基础上组合演变而来。

本章将从原理层面深入剖析这三种算法的工作机制，并通过对比矩阵帮助读者建立清晰的选型直觉。

二、Mark-Sweep 算法

Mark-Sweep 算法分为两个阶段：标记阶段（Mark Phase） 和 清扫阶段（Sweep Phase）。顾名思义，先标记出所有存活对象，再清扫掉未被标记的垃圾对象。

2.1 标记阶段

标记阶段从 GC Roots 出发，遍历整个对象图（Object Graph），将所有可达对象标记为"存活"。这个过程本质上是一次图遍历（BFS 或 DFS）。

标记阶段伪代码：

function Mark(rootSet):
    worklist = new Queue()
    for root in rootSet:
        if root != null && !root.marked:
            root.marked = true
            worklist.enqueue(root)
    
    while !worklist.isEmpty():
        obj = worklist.dequeue()
        for ref in obj.references:
            if ref != null && !ref.marked:
                ref.marked = true
                worklist.enqueue(ref)

关键细节：

  1. 标记位存储：每个对象头部需要一个 bit 来记录是否被标记。在 .NET 中，这个标记位存储在对象头的 SyncBlock 中，不会额外占用对象体空间。
  2. 遍历方式：.NET 的 GC 使用 BFS（广度优先搜索）配合一个灰色队列（mark queue），而非递归 DFS，以避免栈溢出。
  3. STW（Stop-The-World）：在非并发 GC 中，标记阶段需要暂停所有应用线程，否则对象引用关系可能在遍历过程中变化导致漏标。

在 C# 中，你可以通过以下代码观察标记阶段的行为：

using System;
using System.Runtime;

class MarkPhaseDemo
{
    static void Main()
    {
        // 创建对象图：root -> A -> B -> C
        // root -> D（独立分支）
        var a = new Node("A");
        var b = new Node("B");
        var c = new Node("C");
        var d = new Node("D");
        
        a.Next = b;
        b.Next = c;
        
        // 此时 A、B、C、D 均可达
        GC.Collect();
        Console.WriteLine($"After GC (all reachable): Gen0={GC.CollectionCount(0)}");
        
        // 断开 A 的引用链
        a = null;
        GC.Collect();
        // A、B、C 变为不可达，被回收；D 仍可达
        
        d = null;
        GC.Collect();
        // D 也被回收
    }
}

class Node
{
    public string Name { get; }
    public Node Next { get; set; }
    public Node(string name) => Name = name;
    ~Node() => Console.WriteLine($"{Name} finalized");
}

2.2 清扫阶段

清扫阶段遍历整个堆，检查每个对象的标记位：

  • 已标记 → 清除标记位，保留对象（下一轮 GC 重新标记）
  • 未标记 → 该对象是垃圾，将其空间加入空闲链表（Free List）
清扫阶段伪代码：

function Sweep(heap):
    for each block in heap:
        if block.marked:
            block.marked = false  // 重置标记，为下次GC准备
        else:
            freeList.add(block)   // 加入空闲链表

空闲链表（Free List）的结构：

在 Mark-Sweep 中，被回收的内存块不会立即被归还给操作系统，而是被组织成一个空闲链表。后续分配时，GC 从空闲链表中寻找合适大小的块：

  • First-Fit：找到第一个足够大的块就分配（速度快，但可能浪费）
  • Best-Fit：找到最接近请求大小的块（减少浪费，但搜索慢）
  • Next-Fit：从上次搜索位置继续找（折中方案）

.NET 的 SOH（Small Object Heap）使用的是类似 Next-Fit 的策略，以减少搜索开销。

2.3 优缺点分析

优点：

优点说明
实现简单两阶段流程清晰，不需要移动对象
对象地址稳定对象不会被移动，不需要更新引用
适合大对象不需要复制大对象，避免复制开销

缺点：

缺点说明
内存碎片化回收后产生不连续的空闲块，无法分配大对象
分配速度慢需要遍历空闲链表寻找合适块
STW 时间长标记和清扫都需要遍历整个堆
空间利用率低碎片化导致有效可用空间减少

碎片化问题图示：

堆内存布局（Mark-Sweep 后）：

[存活A] [空闲] [存活B] [空闲] [空闲] [存活C] [空闲] [存活D]
  16B     8B    32B    16B     8B     24B    16B    16B

总空闲 = 48B，但最大连续空闲块仅 16B
→ 无法分配 32B 的新对象！

这就是 Mark-Sweep 最大的痛点——明明有足够的总空闲空间，却因为碎片化而无法分配。

三、Mark-Compact 算法

为了解决 Mark-Sweep 的碎片化问题，Mark-Compact 在标记阶段之后增加了一个 压缩（Compact）阶段，将所有存活对象移动到堆的一端，形成连续的内存空间。

3.1 压缩阶段

压缩阶段分为三步：

步骤 1：计算新地址

遍历堆，为每个存活对象计算压缩后的新地址。使用一个"空闲指针"（free pointer）从堆起始位置开始，依次为存活对象分配新地址：

计算新地址伪代码：

function ComputeNewAddresses(heap):
    free = heap.start
    for each block in heap:
        if block.marked:
            block.newAddress = free
            free += block.size
    
    return free  // 压缩后的空闲指针位置

步骤 2：更新引用

遍历所有存活对象，将其内部引用更新为指向对象的新地址：

更新引用伪代码：

function UpdateReferences(heap):
    for each block in heap:
        if block.marked:
            for ref in block.references:
                if ref != null:
                    ref.target = ref.target.newAddress

步骤 3：移动对象

将每个存活对象从旧地址复制到新地址：

移动对象伪代码：

function MoveObjects(heap):
    for each block in heap:
        if block.marked:
            memcpy(block.newAddress, block, block.size)
            block.marked = false  // 重置标记

压缩效果图示：

压缩前：
[存活A] [空闲] [存活B] [空闲] [空闲] [存活C] [空闲] [存活D]
  16B     8B    32B    16B     8B     24B    16B    16B

压缩后：
[存活A] [存活B] [存活C] [存活D] [========== 连续空闲 ==========]
  16B     32B     24B     16B        48B（可分配任意大小 ≤ 48B）

在 .NET 中，GC 在执行压缩时会使用一个 Brick Table（砖块表） 来记录对象移动的映射关系，以高效地更新引用。Brick Table 将堆划分为固定大小的"砖块"，每个砖块记录该区域内第一个对象的新地址，通过砖块表可以快速定位任意对象的新位置。

3.2 优缺点分析

优点：

优点说明
消除碎片化压缩后内存连续，分配效率高
分配速度快空闲空间连续，只需移动空闲指针（Bump Allocation）
空间利用率高不存在碎片浪费

缺点：

缺点说明
移动开销大需要复制对象数据，大对象移动代价极高
引用更新复杂需要更新所有指向移动对象的引用
STW 时间更长三步操作都需要暂停应用线程
不适合大对象移动大对象（如数组）的内存复制成本很高

C# 代码示例——观察压缩行为：

using System;
using System.Runtime.InteropServices;

class CompactDemo
{
    static void Main()
    {
        // 分配大量小对象制造碎片
        var objects = new WeakReference[100];
        for (int i = 0; i < 100; i++)
        {
            objects[i] = new WeakReference(new byte[100]);
        }
        
        // 释放一半对象制造碎片
        for (int i = 0; i < 100; i += 2)
        {
            objects[i] = null;
        }
        
        // 触发GC并压缩
        GC.Collect();
        GC.WaitForPendingFinalizers();
        GC.Collect();
        
        // 检查压缩后的内存布局
        // 注意：实际开发中不应依赖对象地址
        var settings = new GCMemorySettings();
        Console.WriteLine($"GC 内存信息:");
        Console.WriteLine($"  堆大小: {GC.GetTotalMemory(false)} bytes");
        Console.WriteLine($"  Gen0 回收次数: {GC.CollectionCount(0)}");
        Console.WriteLine($"  Gen1 回收次数: {GC.CollectionCount(1)}");
        Console.WriteLine($"  Gen2 回收次数: {GC.CollectionCount(2)}");
    }
}

四、Copying 算法

Copying 算法由 C.J. Cheney 在 1970 年提出，它用一种更优雅的方式同时解决了碎片化和压缩问题——将堆分成两个半区，每次只使用一个半区，GC 时将存活对象复制到另一个半区。

4.1 半区复制

工作原理：

堆布局：
┌──────────────── From 区 ────────┬──────── To 区 ────────┐
│ [A] [B] [垃圾] [C] [垃圾] [D]  │                       │
└──────────────────────────────────┴───────────────────────┘

GC 后：
┌──────────────────────────────────┬──── To 区 ───────────┐
│                                  │ [A] [B] [C] [D] [空闲]│
└──────────────────────────────────┴───────────────────────┘
                                   ↑ 新的 From 区

Cheney 复制算法：

Cheney 算法伪代码：

function Copy(rootSet, fromSpace, toSpace):
    // scan 指针：已复制但未扫描引用的对象
    // free 指针：下一个可分配位置
    scan = toSpace.start
    free = toSpace.start
    
    // 复制根直接引用的对象
    for root in rootSet:
        root.target = copy(root.target, free)
    
    // 扫描已复制对象的引用
    while scan < free:
        obj = scan
        for ref in obj.references:
            ref.target = copy(ref.target, free)
        scan += obj.size
    
    // 交换半区
    swap(fromSpace, toSpace)

function copy(obj, free):
    if obj == null:
        return null
    if obj.forwarded:
        return obj.forward  // 已复制，返回转发地址
    
    // 复制对象到新空间
    newAddr = free
    memcpy(newAddr, obj, obj.size)
    obj.forwarded = true
    obj.forward = newAddr
    free += obj.size
    
    return newAddr

关键特性：

  1. BFS 遍历：Cheney 算法天然使用 BFS 遍历对象图，scan 指针和 free 指针之间的对象就是"灰色"对象（已复制但未扫描引用）。
  2. 转发指针（Forward Pointer）：被复制的对象在旧空间留下转发指针，指向新空间中的副本，确保多次引用同一对象时只复制一次。
  3. 无碎片化：复制后新空间天然连续。
  4. 无标记位：不需要标记位，存活对象通过是否被复制来区分。

4.2 优缺点分析

优点：

优点说明
无碎片化复制后天然连续
分配极快Bump Allocation，只需移动指针
无标记开销不需要标记位和清扫遍历
访问局部性好存活对象在复制时被重新排列，引用关系更紧凑

缺点：

缺点说明
空间利用率 50%始终有一半空间空闲
移动开销需要复制存活对象
不适合存活率高的堆存活对象越多，复制开销越大
不适合大对象复制大对象代价极高

存活率与效率关系：

Copying 算法的效率与存活率的关系：

存活率 = 10% → 复制 10% 的对象，效率极高
存活率 = 50% → 复制 50% 的对象，效率一般
存活率 = 90% → 复制 90% 的对象，效率极低（几乎全在复制）

→ Copying 算法最适合"朝生夕灭"的新生代！

这正是分代 GC 中新生代使用 Copying 算法的理论依据。

五、三种算法的对比矩阵

维度Mark-SweepMark-CompactCopying
碎片化严重无无
空间利用率高（可用全部堆）高（可用全部堆）低（50%，半区复制）
分配速度慢（空闲链表搜索）快（Bump Allocation）极快（Bump Allocation）
回收速度中等（遍历堆清扫）慢（三步压缩）快（只复制存活对象）
对象移动不移动移动移动
引用更新不需要需要需要
标记位需要需要不需要
适合存活率任意任意低存活率最佳
适合对象大小任意中小对象中小对象
STW 时间中等长短（存活率低时）
实现复杂度低中中
典型应用早期 Lisp GC.NET Gen2 部分.NET Gen0/Gen1, Java Young

选型决策树：

是否需要避免移动对象？
├── 是 → Mark-Sweep（但需接受碎片化）
└── 否 → 存活率是否较低？
         ├── 是（< 30%）→ Copying（高效复制少量存活对象）
         └── 否（> 30%）→ Mark-Compact（压缩但避免复制开销）

六、实际 GC 中的组合使用

工业级 GC 几乎不会单独使用某一种算法，而是根据堆的不同区域特征组合使用。

6.1 .NET GC 的组合策略

.NET 的堆分为三个代（Gen0、Gen1、Gen2）加上大对象堆（LOH）：

区域算法原因
Gen0Copying新生代存活率极低，复制开销小
Gen1Copying同 Gen0，作为 Gen0 到 Gen2 的缓冲
Gen2Mark-Sweep + 可选 Compact老年代存活率高，复制开销大；默认只 Sweep，碎片严重时才 Compact
LOHMark-Sweep + 可选 Compact大对象移动代价极高，默认不压缩
// .NET GC 策略验证代码
using System;
using System.Runtime;

class GCStrategyDemo
{
    static void Main()
    {
        // Gen0 对象：快速分配，Copying 回收
        var smallObj = new byte[100];
        Console.WriteLine($"小对象代: {GC.GetGeneration(smallObj)}"); // 0
        
        // 触发多次 GC 使对象晋升
        for (int i = 0; i < 10; i++)
        {
            GC.Collect();
            GC.WaitForPendingFinalizers();
        }
        Console.WriteLine($"多次GC后小对象代: {GC.GetGeneration(smallObj)}"); // 2
        
        // LOH 对象：≥ 85000 bytes，直接分配在 LOH
        var largeObj = new byte[85000];
        Console.WriteLine($"大对象代: {GC.GetGeneration(largeObj)}"); // 2（LOH 算作 Gen2）
        
        // .NET 4.5.1+ 可以手动请求 LOH 压缩
        GCSettings.LargeObjectHeapCompactionMode = GCLargeObjectHeapCompactionMode.CompactOnce;
        GC.Collect(); // 这次 GC 会压缩 LOH
        Console.WriteLine("LOH 已压缩");
    }
}

6.2 Java HotSpot 的组合策略

区域算法说明
Eden + SurvivorCopying新生代，存活率低
Old GenMark-Compact老年代，存活率高
Metaspace不会回收元数据区，类元数据

6.3 Unity Mono/Boehm GC 的策略

Unity 早期默认使用 Boehm GC（Boehm-Demers-Weiser GC），它是一种 Mark-Sweep 变体：

  • 不移动对象：纯 Mark-Sweep，不压缩
  • 保守式 GC：不依赖精确的类型信息，将栈上看起来像指针的值都当作引用
  • 碎片化严重：长时间运行的游戏容易出现碎片化问题
// Unity 中检测 Boehm GC 碎片化的示例
// 注意：此代码仅在 Unity Mono 后端有效
#if UNITY_EDITOR
using UnityEngine;
using System;

public class BoehmGCDemo : MonoBehaviour
{
    void Start()
    {
        // 分配大量不同大小的对象
        var objects = new System.WeakReference[1000];
        for (int i = 0; i < 1000; i++)
        {
            objects[i] = new System.WeakReference(new byte[UnityEngine.Random.Range(64, 512)]);
        }
        
        // 随机释放一半
        for (int i = 0; i < 1000; i += 2)
        {
            objects[i] = null;
        }
        
        // 触发 GC
        GC.Collect();
        
        // Boehm GC 不会压缩，碎片化会累积
        Debug.Log("Boehm GC 完成回收，但碎片未压缩");
        Debug.Log($"堆大小: {GC.GetTotalMemory(false) / 1024 / 1024} MB");
    }
}
#endif

6.4 Unity IL2CPP + Boehm vs .NET Core 的差异

特性Unity Boehm.NET Core Server GC
算法Mark-Sweep（保守式）分代 + Copying/Compact
压缩不支持支持（Gen2 + LOH 可选）
分代不分代3 代 + LOH
并发部分支持完全并发（Background GC）
碎片化严重可控
STW长短（分代 + 并发）

七、总结

本章深入剖析了三种基础 GC 算法：

  1. Mark-Sweep：最基础的算法，标记存活对象后清扫垃圾。优点是不移动对象、实现简单；缺点是碎片化严重、分配速度慢。Unity 的 Boehm GC 就是这一算法的保守式变体。

  2. Mark-Compact：在 Mark-Sweep 基础上增加压缩阶段，消除碎片化。优点是分配快、空间利用率高；缺点是移动开销大、STW 时间长。.NET 的 Gen2 回收在碎片严重时会触发压缩。

  3. Copying：将堆分为两个半区，GC 时复制存活对象到另一半区。优点是无碎片、分配极快；缺点是空间利用率仅 50%、不适合高存活率场景。.NET 的 Gen0/Gen1 使用此算法。

核心洞察：

  • 没有一种算法是万能的，工业级 GC 都是 组合策略。
  • 算法选择的关键因素是 存活率：低存活率用 Copying，高存活率用 Mark-Sweep/Compact。
  • 大对象不适合移动，因此 LOH 通常使用 Mark-Sweep + 可选压缩。
  • .NET 的分代策略是教科书级的组合实践，而 Unity 的 Boehm GC 则展示了 Mark-Sweep 的局限性。

理解这三种算法是理解后续分代 GC、并发 GC、区域 GC 等高级主题的基础。在下一章中，我们将探讨 .NET 如何利用 分代假说 将这三种算法组合成一个高效的 GC 系统。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/chenghai37/article/details/166689967

文章来源转载

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--