C# 运行时与垃圾回收

1. 托管堆

1.1 栈和堆

在 C++ 中，程序在内存上的空间，可以简单的分为栈和堆。

栈的内存由系统分配和管理，大小固定的（Windows 默认 1MB），用于存储局部变量、函数形参、函数返回值。

堆的内存由用户手动分配和管理，大小是动态的（在 64 位 Windows 上运行 32 位程序，其堆最大为 4GB），用于存储由 new 动态分配的对象。

	栈（Stack）	堆（Heap）
分配和管理	系统分配管理	手动分配和管理
大小	固定	动态
存储内容	局部变量、函数形参、函数返回值	由 new 动态分配的对象

在 C++ 对于堆内存的管理完全由程序员自己负责，很容易出现 内存泄漏（可用内存越来越少），最终导致 内存溢出 程序崩溃。

比如，忘记释放一个对象，它将一直存在于堆中，直到程序终止。亦或者，访问已经被释放的内存，即 使用无效/野指针 。

C# 程序的托管堆就是为了解决这些问题。不过在了解托管堆之前先要知道 CLR 是什么。

1.2 公共语言运行时（CLR）

公共语言运行时（Common Language Runtime，CLR）是 .NET 标准（.NET Standard）下的各类平台（.NET Core、Mono等）的执行环境（引擎）。

CLR 负责管理程序的执行：

内存管理和垃圾回收；
代码安全验证；
代码执行、线程管理和异常处理；

.NET 平台所支持的各种代码如 C#、F#、VB等，通过其对应编译器，生成对应的 程序集（assembly） 。程序集要么是可执行的，要么是 DLL。

程序集所包含的信息有：

公共中间语言（Common Intermediate Language，CIL）

正如其名，CIL 并不是原生代码（本机机器码）而是一种中间语言，这么做是为了更好的跨平台；

CIL，有时也被称作 IL （中间语言）或者 MSIL（Microsoft 中间语言）。

程序中使用的类型的元数据

对其他程序集引用的元数据

当我们运行一个已经编译完成的 C# 程序集的可执行文件或 DLL 的时候，操作系统会先调用 CLR，之后 CLR 中的 即时编译器（just-in-time， JIT） 会将程序集中的一部分 CIL （需要的部分）编译为原生代码（本机代码）。

一旦 CIL 被编译为原生代码，CLR 就会在它运行时管理它，比如内存管理和垃圾回收等。因此在运行的时候需要被 CLR 管理的代码也被称为 托管代码 。与之对应的，C/C++ 所生成的可执行程序或者 DLL 中的代码为 非托管代码 。

下图为 C# 代码从编译到运行时所经历的过程：

1.3 托管堆

托管堆 是由 CLR 的内存管理器自动管理的一段内存。初始化新进程时，CLR 会为进程保留一个连续的地址空间区域。这个保留的地址空间被称为托管堆。

托管堆维护着一个指针，用它指向将在堆中分配的下一个对象的地址。应用程序创建第一个引用类型时，将为托管堆的基址中的类型分配内存。应用程序创建下一个对象时，运行时在紧接第一个对象后面的地址空间内为它分配内存。只要地址空间可用，运行时就会继续以这种方式为新对象分配空间。

CLR 通过 垃圾回收器（Garbage Collector，GC） 来管理托管堆上的内存。当满足以下条件时会触发垃圾回收：

系统具有 低的物理内存；
托管堆上已分配的对象使用的内存 超出可接受的阈值（随着进程的运行，此阈值会不断地进行调整）；
主动调用垃圾回收方法。

触发垃圾回收的时候，不同 CLR 下的垃圾回收器会按照 不同的垃圾回收算法 回收非活动对象的内存。

2. 不同类型的垃圾回收算法

垃圾收集器将内存视为一张 有向可达图（reachability graph） ，如下所示：

该图中的结点被分为 根结点 和 堆结点。每个堆结点对应堆中一个已分配块。当存在从任意根节点出发并到达结点 p 的有向路径时，说明该结点为可达的（活动对象）。

垃圾回收器的任务是 维护可达图的某种表示，并在程序需要在堆上申请新空间的时候，释放符合申请大小的不可达结点对应的块内存，然后重新分配。

下面列出 5 种常见的垃圾回收算法。

2.1 标记-清除（Mark-Sweep）

标记-清除算法主要分为标记和清除两个阶段。通常使用块头部中空闲的低位中的一位用来表示该块是否被标记。

标记阶段：

从每个根结点调用 mark 函数，标记下一个可达结点对应的块，然后对当前块内每个字节递归的调用 mark 函数。

伪代码如下所示：

// 如果 p 指向一个已分配块中的某个字节
// 则返回改块的首字节的指针
// 否则返回 NULL
ptr isPtr(ptr p);

// 返回块是否已经被标记，防止环引起无限递归
bool blockMarked(ptr b);

void mark(ptr p)
{
    b = isPtr(p)
    if (b == NULL)
        return;
    if (blockMarked(b))
        return;
    // 标记块首部然后对块中每个字递归
	markBlock(b);
    for (i = 0; i < length(b); i++)
        mark(b[i]);
    return;
}

清除阶段

遍历所有块，如果块已分配且已经被标记，则取消它的标记，否则该块为垃圾，需要将其回收内存然后添加到空闲链表。

伪代码如下所示：

void sweep(ptr b, ptr end)
{
    while (b < end)
    {
        if (blockMarked(b))
            unmarkBlock(b);
        else if (bloackAllocated(b))
            free(b);
        b = nextBlock(b);
    }
    return;
}

优点

容易实现，不需要移动任何块；

缺点

容易造成 内存碎片，导致尽管有足够的内存但是无法找到满足申请大小的连续块；

2.2 标记-压缩（Mark-Compact）

该算法就是为了解决标记-清除算法中 内存碎片 的问题。标记阶段后，会将所有活动对象紧密的排在堆的一侧（压缩），然后清理边界以外的垃圾。

优点

解决了碎片化的问题；

缺点

压缩过程需要花费更多的时间；

2.3 分代垃圾回收（Generational GC）

分代算法是基于 GC 算法以下几个特点来设计的：

压缩托管堆的一部分内存要比压缩整个托管堆速度快；
较新的对象生存期较短，而较旧的对象生存期则较长；
较新的对象趋向于相互关联，并且大致同时由应用程序访问。

将托管堆分为三代：第 0 代、第 1 代和第 2 代，从而可以单独处理长生存期和段生存期的对象，然后针对某一代进行托管堆的部分压缩。

当触发垃圾回收时，垃圾回收器会优先回收第 0 代，如果没有回收足够的内存，则会执行第 1 代的垃圾回收以此类推。

幸存和提升

垃圾回收中未回收的对象也称为幸存者，并会被提升到下一代。

第 0 代垃圾回收中未被回收的对象将会升级至第 1 代；
第 1 代垃圾回收中未被回收的对象将会升级至第 2 代；
第 2 代垃圾回收中未被回收的对象将仍保留在第 2 代。

在 .NET CLR 中，垃圾回收器通过以下信息来确定对象是否为活动对象：

堆栈根：由 JIT 编译器和堆栈查看器提供的堆栈变量。

垃圾回收句柄：指向托管对象且可由用户代码或公共语言运行时分配的句柄。

静态数据：应用程序域中可能引用其他对象的静态对象。每个应用程序域都会跟踪其静态对象。

2.4 复制（Copy and Collection）

复制 GC 算法将堆分为了两个大小相同的空间 From 和 To。

From 空间用于分配；
From 空间无法再分配时，垃圾回收器将其中活动对象复制到 To 空间（这个过程实际上也实现了压缩）；
交换 From 和 To 。

该方法的缺点主要在于需要使用双倍的空间。

2.5 增量式垃圾回收（Incremental GC）

GC 触发的时候，会暂停程序直到 GC 结束。GC 任务越繁重，暂停时间越长。这对于注重实时性的程序，如游戏，是不能忍受的。

因此出现了 增量式垃圾回收，它并不会等GC执行完，才将控制权交回程序。二是在程序运行中穿插进行，逐步完成垃圾回收。极大地降低了GC的最大暂停时间。

3. 不同 C# 运行时对比

常见的基于 .NET 标准的 CLR 有：

微软推出的 .NET Framework、 .NET Core、.NET 5 及之后版本
- 其中 .NET Framework 仅针对 windows 平台。
Xamarin 推出的 Mono

	Mono 2.10之前	Mono 2.10之后	.NET 系列
GC 算法	标记-清除（Mono 自己实现的 Boehm GC，libgc）	分代（Simple Generational GC，SGen GC）	分代

值得一提的是，Unity 使用的 Mono 由于版权问题，一直用的 Mono 2.10 之前的版本。但是这不代表 Unity 的 Mono 垃圾回收算法只有标记-清除。

Unity 在 GitHub 上 fork 了 Mono 项目，并且使用了另一个的 Boehm GC 库，这个库是可以开启增量式 GC 和分代 GC 功能的。

此外，Unity 自己实现的 IL2CPP 的垃圾回收器也是使用的这个库。