内存回收 | Penge666

如果应用程序申请内存的速度，超过内存回收的速度，内存就会被用满。当内存用满，操作系统就开始需要频繁地切换页面，进行频繁地磁盘读写。所以我们观察到的系统性能下降，往往是一种突然的崩溃，因为一旦内存被占满，系统性能就开始雪崩式下降。

什么是 GC

通常意义上我们说的垃圾回收器（Garbage Collector，GC），和多数同学的理解会有出入。你可能认为 GC 是做内存回收用的模块，而事实上程序语言提供的 GC 往往是应用的实际内存管理者。刚刚入门咱们就遇到了一个容易出现理解偏差的问题，所以 GC 是值得花时间细学的。

如上图所示，一方面 GC 要承接操作系统虚拟内存的架构，另一方面 GC 还要为应用提供内存管理。GC 有一个含义，就是 Garbage Collection 内存回收的具体动作。无论是名词的回收器，还是动词的回收行为，在下文中我都称作 GC。

下面我们具体来看一下 GC 都需要承担哪些“工作”，这里我总结为以下 4 种。

GC 要和操作系统进行交互，负责申请内存，并把不用的内存还给操作系统（释放内存）。
应用会向 GC 申请内存。
GC 要承担我们通常意义上说的垃圾回收能力，标记不用的对象，并回收他们。
GC 还需要针对应用特性进行动态的优化。

所以现在程序语言实现的 GC 模块通常是实际负责应用内存管理的模块。在程序语言实现 GC 的时候，会关注下面这几个指标。

吞吐量（Throughput）：执行程序（不包括 GC 执行的时间）和总是间的占比。注意这个吞吐量和通常意义上应用去处理作业的吞吐量是不一样的，这是从 GC 的角度去看应用。只要不在 GC，就认为是吞吐量的一部分。
足迹（FootPrint）：一个程序使用了多少硬件的资源，也称作程序在硬件上的足迹。GC 里面说的足迹，通常就是应用对内存的占用情况。比如说应用运行需要 2G 内存，但是好的 GC 算法能够帮助我们减少 500MB 的内存使用，满足足迹这个指标。
暂停时间（Pause Time）： GC 执行的时候，通常需要停下应用（避免同步问题），这称为 Stop The World，或者暂停。不同应用对某次内存回收可以暂停的时间需求是不同的，比如说一个游戏应用，暂停了几毫秒用户都可能有很大意见；而看网页的用户，稍微慢了几毫秒是没有感觉的。

GC 目标的思考

如果单纯从让 GC 尽快把工作做完的角度来讲，其实是提升吞吐量。比如利用好多核优势就是一种最直观的方法。

因为涉及并行计算，我这里给你讲讲并行计算领域非常重要的阿姆达定律，这个定律用来衡量并行计算对原有算法的改进，公式如下：

S = 1 / (1- P)

你现在看到的是一个简化版的阿姆达定律，P 是任务中可以并发执行部分的占比，S 是并行带来的理论提速倍数的极限。比如说 P 是 0.9，代入公式可得：

S = 1 / （1 - 0.9） = 10

上面表达式代表着有 90% 的任务可以并行，只有 10% 的任务不能够并行。假设我们拥有无限多的 CPU 去分担 90% 可以并行的任务，其实就相当于并行的任务可以在非常短的时间内完成。但是还有 10% 的任务不能并行，因此理论极限是 1⁄0.1=10 倍。

通常我们设计 GC，都希望它能够支持并行处理任务。因为 GC 本身也有着繁重的工作量，需要扫描所有的对象，对内存进行标记清除和整理等。

经过上述分析，那么我们在设计算法的时候是不是应该尽量做到高并发呢？

很可惜并不是这样。如果算法支持的并发度非常高，那么和单线程算法相比，它也会带来更多的其他开销。比如任务拆分的开销、解决同步问题的开销，还有就是空间开销，GC 领域空间开销通常称为 FootPrint。理想情况下当然是核越多越好，但是如果考虑计算本身的成本，就需要找到折中的方案。

还有一个问题是，GC 往往不能拥有太长的暂停时间（Pause Time），因为 GC 和应用是并发的执行。如果 GC 导致应用暂停（Stop The World，STL）太久，那么对有的应用来说是灾难性的。比如说你用鼠标的时候，如果突然卡了你会很抓狂。如果一个应用提供给百万级的用户用，假设这个应用帮每个用户每天节省了 1s 的等待时间，那么按照乔布斯的说法每天就为用户节省了 11 天的时间，每年是 11 年——5 年就相当于拯救了一条生命。

如果暂停时间只允许很短，那么 GC 和应用的交替就需要非常频繁。这对 GC 算法要求就会上升，因为每次用户程序执行后，会产生新的变化，甚至会对已有的 GC 结果产生影响。后面我们在讨论标记-清除算法的时候，你会感受到这种情况。

所以说，吞吐量高，不代表暂停时间少，也不代表空间使用（FootPrint）小。同样的，使用空间小的 GC 算法，吞吐量反而也会下降。正因为三者之间存在类似相同成本代价下不可兼得的关系，往往编程语言会提供参数让你选择根据自己的应用特性决定 GC 行为。

引用计数算法（Reference Counter）

接下来我们说说，具体怎么去实现 GC。实现 GC 最简单的方案叫作引用计数，下图中节点的引用计数是 2，代表有两个节点都引用了它。

如果一个节点的引用计数是 0，就意味着没有任何一个节点引用它——此时，理论上这个节点应该被回收。GC 不断扫描引用计数为 0 的节点进行回收，就构成了最简单的一个内存回收算法。

但是，这个算法可能会出现下图中循环引用的问题（我们写程序的过程中经常会遇到这样的引用关系）。下图中三个节点，因为循环引用，引用计数都是 1。

引用计数是 1，因此就算这 3 个对象不会再使用了，GC 不会回收它们。

另一个考虑是在多线程环境下引用计数的算法一旦算错 1 次（比如因为没有处理好竞争条件），那么就无法再纠正了。而且处理竞争条件本身也比较耗费性能。

还有就是引用计数法回收内存会产生碎片，当然碎片不是只有引用计数法才有的问题，所有的 GC 都需要面对碎片。下图中内存回收的碎片可以通过整理的方式，清理出更多空间出来。

综上，引用计数法出错概率大，比如我们编程时会有对象的循环引用；另一方面，引用计数法容错能力差，一旦计算错了，就会导致内存永久无法被回收，因此我们需要更好的方式。

Root Tracing 算法

下面我再给你介绍一种更好的方式—— Root Tracing 算法。这是一类算法，后面我们会讲解的标记-清除算法和 3 色标记-清除算法都属于这一类。

Root Tracing 的原理是：从引用路径上，如果一个对象的引用链中包括一个根对象（Root Object），那么这个对象就是活动的。根对象是所有引用关系的源头。比如用户在栈中创建的对象指针；程序启动之初导入数据区的全局对象等。在 Java 中根对象就包括在栈上创建指向堆的对象；JVM 的一些元数据，包括 Method Area 中的对象等。

在 Root Tracing 工作过程中，如果一个对象和根对象间有连通路径，也就是从根节点开始遍历可以找到这个对象，代表有对象可以引用到这个对象，那么这个节点就不需要被回收。所以算法的本质还是引用，只不过判断条件从引用计数变成了有根对象的引用链。

如果一个对象从根对象不可达，那么这个对象就应该被回收，即便这个对象存在循环引用。可以看到，上图中红色的 3 个对象循环引用，并且到根集合没有引用链，因此需要被回收。这样就解决了循环引用的问题。

Root Tracing 的容错性很好，GC 通过不断地执行 Root Tracing 算法找到需要回收的元素。如果在这个过程中，有一些本来应该回收的元素没有被计算出（比如并发原因），也不会导致这些对象永久无法回收。因为在下次执行 Root Tracing 的时候，GC 就会通过执行 Root Tracing 算法找到这些元素。不像引用计数法，一旦算错就很难恢复。

补充：

在 Root Tracing 算法中，根节点通常指的是垃圾收集器（Garbage Collector, GC）在执行标记过程时的起始点。这些根节点通常是全局变量或者是当前执行的函数的参数和局部变量，因为它们是可以直接访问的。垃圾收集器从这些根节点开始遍历，找出所有它们能直接或间接引用到的对象，这些对象被认为是"活动的"，也就是说它们在当前的程序执行中仍然有可能被用到。而那些不能从根节点达到的对象，就被认为是"死亡的"，也就是说它们在后续的程序执行中不会再被用到，因此可以被垃圾收集器回收。

标记-清除（Mark Sweep）算法

下面我为你具体介绍一种 Root Tracing 的算法，就是标记清除-算法。标记-清除算法中，用白色代表一种不确定的状态：可能被回收。黑色代表一种确定的状态：不会被回收。算法的实现，就是为所有的对象染色。算法执行结束后，所有是白色的对象就需要被回收。

算法实现过程中，假设有两个全局变量是已知的：

heapSet 中拥有所有对象
rootSet 中拥有所有 Root Object

算法执行的第一步，就是将所有的对象染成白色，代码如下：

for obj in heapSet {

    obj.color = white

}

接下来我们定义一个标记函数，它会递归地将一个对象的所有子对象染成黑色，代码如下：

func mark(obj) {

  if obj.color == white {

    obj.color = black

    for v in references(obj) {

      mark(v)

    }

  }

}

补充知识1

上面的 mark 函数对 obj 进行了深度优先搜索。深度优先搜索，就是自然的递归序。随着递归函数执行，遇到子元素就遍历子元素，就构成了天然的深度优先搜索。还有一个相对的概念是广度优先搜索（Breadth First Serach），如果你不知道深度优先搜索和广度优先搜索，可以看下我下面的图例。

上图中，深度优先搜索优先遍历完整的子树（递归），广度优先搜索优先遍历所有的子节点（逐层）。

然后我们从所有的 Root Object 开始执行 mark 函数：

for root in rootSet {

  mark(root)

}

以上程序执行结束后，所有和 Root Object 连通的对象都已经被染成了黑色。然后我们遍历整个 heapSet 找到白色的对象进行回收，这一步开始是清除（Sweep）阶段，以上是标记（Mark）阶段。

for obj in heapSet {
  if obj.color == white {
    free(obj)
  }
}

以上算法就是一个简单的标记-清除算法。相比引用计数，这个算法不需要维护状态。算法执行开始所有节点都被标记了一遍。结束的时候，算法找到的垃圾就被清除了。算法有两个阶段，标记阶段（Mark），还有清除阶段（Sweep），因此被称为标记-清除算法。

这里请你思考：如果上面的 GC 程序在某个时刻暂停了下来，然后开始执行用户程序。如果用户程序删除了对某个已经标记为黑色对象的所有引用，用户程序没办法通知 GC 程序。这个节点就会变成浮动垃圾（Floating Garbage），需要等待下一个 GC 程序执行。

假设用户程序和 GC 交替执行，用户程序不断进行修改（Mutation），而 GC 不断执行标记-清除算法。那么这中间会产生大量浮动垃圾影响 GC 的效果。

另一方面，考虑到 GC 是一个非常消耗性能程序，在某些情况下，我们希望 GC 能够增量回收。比如说，用户仅仅是高频删除了一部分对象，那么是否可以考虑设计不需要从整个 Root 集合进行遍历，而是增量的只处理最近这一批变更的算法呢？答案是可以的，我们平时可以多执行增量 GC，偶尔执行一次全量 GC。

补充知识2

C++语言本身不提供自动垃圾回收（Garbage Collection, GC）机制，但有一些第三方库可以为C++添加垃圾回收功能。以下是一些常见的C++垃圾回收库：

Boehm-Demers-Weiser Garbage Collector (Boehm GC)

Boehm GC 是最常用的 C++ 垃圾回收库之一。它支持 C 和 C++，并且可以在许多平台上运行。Boehm GC 是一个保守的垃圾回收器，适用于那些不希望手动管理内存或者不想使用智能指针的项目。

特点
- 支持多线程
- 兼容性强，支持多种平台
- 可以替代 malloc 和 new 的内存分配机制

git clone https://github.com/ivmai/bdwgc.git

sudo apt-get update
sudo apt-get install build-essential libtool

cd bdwgc
./autogen.sh
./configure
make
sudo make install

为了确保系统能够找到新安装的Boehm GC库，你可能需要更新动态链接库路径。你可以通过以下命令将/usr/local/lib添加到/etc/ld.so.conf文件中，并更新动态链接库缓存：

1 2	echo "/usr/local/lib" \| sudo tee -a /etc/ld.so.conf sudo ldconfig

使用实例

#include <stdio.h>
#include <gc.h>

int main() {
    // 初始化Boehm GC
    GC_init();

    // 分配内存
    int *p = (int *)GC_malloc(sizeof(int));
    *p = 42;

    // 输出值
    printf("Value: %d\n", *p);

    // 不需要手动释放内存，Boehm GC会自动回收

    return 0;
}

执行

1 2	gcc -o test test.c -lgc ./test

在编译Boehm GC时，你可以通过./configure命令的选项来配置库的行为。例如：

1	./configure --enable-threads --enable-parallel-mark

这些选项可以启用多线程支持和并行标记功能。

Boehm GC 通过结合保守指针识别、标记-清除算法、分代收集、写屏障、多线程支持等技术。

保守性 (Conservatism)

Boehm GC 是一个保守式垃圾回收器，这意味着它并不要求程序显示地标记哪些内存是动态分配的，也不要求指针类型是精确的。相反，它假设内存中的某些比特模式可能是指针，并据此进行垃圾回收。

指针识别: Boehm GC 使用保守的策略来识别指针。这意味着它会扫描堆栈、寄存器和全局变量，检查是否存在看似指向堆内存的值。如果一个值看起来像是一个指向堆内存的指针，Boehm GC 就会假设它是一个指针，并将相应的内存块标记为“活跃”状态以避免回收。

标记-清除算法 (Mark-and-Sweep)

Boehm GC 的核心垃圾回收算法是标记-清除算法。这种算法分为两个阶段：

标记阶段: 在标记阶段，GC 从根对象（根集）出发，遍历所有可达的对象，并将它们标记为“活跃”。
- 根集包括堆栈中的局部变量、全局变量、寄存器中的值等。
- 遍历的过程通常采用深度优先搜索（DFS）或广度优先搜索（BFS）来查找所有从根集出发可达的对象。
清除阶段: 在清除阶段，GC 遍历堆中的所有对象，释放那些未被标记为“活跃”的对象，因为这些对象已经不可达。

分代收集 (Generational Collection)

为了提高性能，Boehm GC 还可以选择性地使用分代收集策略。分代收集假设大多数对象的生命周期较短，因此将内存区域分为“新生代”和“老年代”：

新生代: 新生代内存区域中主要存储刚刚分配的对象。GC 会更频繁地对新生代进行垃圾回收，因为这些对象中大多数很快就会变为垃圾。
老年代: 老年代内存区域中主要存储存活时间较长的对象。GC 会较少地对老年代进行回收，以减少不必要的开销。

写屏障 (Write Barrier)

为了支持增量式垃圾回收和分代收集，Boehm GC 使用了写屏障技术。写屏障是一种在程序写入指针时插入的特殊代码，它能够记录指针的变动，从而帮助垃圾回收器跟踪对象引用的变化。

增量垃圾回收: 增量式垃圾回收允许程序在垃圾回收进行的同时继续运行。这种方式减少了垃圾回收对程序响应时间的影响。

内存分配器的集成 (Memory Allocator Integration)

Boehm GC 替代了标准的 malloc 和 free 函数，以便在分配和释放内存时进行垃圾回收管理。它还提供了自己的内存分配函数，如 GC_MALLOC，用于分配由 GC 管理的内存。

分配和回收策略: Boehm GC 使用了分块分配（chunk allocation）和空闲列表（free list）等技术来高效管理内存分配和回收。

多线程支持

Boehm GC 支持多线程环境，能够在多线程程序中正确地管理并回收内存。它的实现包括：

线程本地存储: Boehm GC 维护线程本地的根集，以正确追踪每个线程的栈和寄存器中的指针。
同步和锁定: 在多线程环境中，GC 需要在标记和清除过程中正确同步，避免竞争条件。

弱引用和最终化 (Finalization)

Boehm GC 支持弱引用和对象的最终化（finalization）。弱引用不会阻止对象被回收，而最终化则允许在对象被回收之前执行一些清理操作。

三色标记-清除算法（Tri-Color Mark Sweep）

接下来，我会和你讨论这种有三个颜色标记的算法，通常称作三色标记-清除算法。首先，我们重新定义黑、白、灰三种颜色的含义：

白色代表需要 GC 的对象；
黑色代表确定不需要 GC 的对象；
灰色代表可能不需要 GC 的对象，但是还未完成标记的任务，也可以认为是增量任务。

在三色标记-清除算法中，一开始所有对象都染成白色。初始化完成后，会启动标记程序。在标记的过程中，是可以暂停标记程序执行 Mutation。

算法需要维护 3 个集合，白色集合、黑色集合、灰色集合。3 个集合是互斥的，对象只能在一个集合中。执行之初，所有对象都放入白色集合，如下图所示：

第一次执行，算法将 Root 集合能直接引用的对象加入灰色集合，如下图所示：

接下来算法会不断从灰色集合中取出元素进行标记，主体标记程序如下：

while greySet.size() > 0 {

  var item = greySet.remove();

  mark(item);

}

标记的过程主要分为 3 个步骤：

如果对象在白色集合中，那么先将对象放入灰色集合；
然后遍历节点的所有的引用对象，并递归所有引用对象；
当一个对象的所有引用对象都在灰色集合中，就把这个节点放入为黑色集合。

伪代码如下：

func mark(obj) {

  if obj in whiteSet {

    greySet.add(obj)

    for v in refs(obj) {

      mark(v)

    }

    greySet.remove(obj)

    blackSet.add(obj)

  }

}

你可以观察下上面的程序，这是一个 DFS 的过程。如果多个线程对不同的 Root Object 并发执行这个算法，我们需要保证 3 个集合都是线程安全的，可以考虑利用 ConcurrentSet（这样性能更好），或者对临界区上锁。并发执行这个算法的时候，如果发现一个灰色节点说明其他线程正在处理这个节点，就忽略这个节点。这样，就解决了标记程序可以并发执行的问题。

当标记算法执行完成的时候，所有不需要 GC 的元素都会涂黑：

标记算法完成后，白色集合内就是需要回收的对象。

以上，是类似双色标记-清除算法的全量 GC 程序，我们从 Root 集合开始遍历，完成了对所有元素的标记（将它们放入对应的集合）。

接下来我们来考虑增加 GC（Incremental GC）的实现。首先对用户的修改进行分类，有这样 3 类修改（Mutation）需要考虑：

创建新对象
删除已有对象
调整已有引用

如果用户程序创建了新对象，可以考虑把新对象直接标记为灰色。虽然，也可以考虑标记为黑色，但是标记为灰色可以让 GC 意识到新增了未完成的任务。比如用户创建了新对象之后，新对象引用了之前删除的对象，就需要重新标记创建的部分。

如果用户删除了已有的对象，通常做法是等待下一次全量 Mark 算法处理。下图中我们删除了 Root Object 到 A 的引用，这个时候如果把 A 标记成白色，那么还需要判断是否还有其他路径引用到 A，而且 B,C 节点的颜色也需要重新计算。关键的问题是，虽然可以实现一个基于 A 的 DFS 去解决这个问题，但实际情况是我们并不着急解决这个问题，因为内存空间往往是有富余的。

在调整已有的引用关系时，三色标记算法的表现明显更好。下图是对象 B 将对 C 的引用改成了对 F 的引用，C,F 被加入灰色集合。接下来 GC 会递归遍历 C,F，最终然后 F,E,G 都会进入灰色集合。

内存回收就好比有人在随手扔垃圾，清洁工需要不停打扫。如果清洁工能够跟上人们扔垃圾的速度，那么就不需要太多的 STL（Stop The World）。如果清洁工跟不上扔垃圾的速度，最终环境就会被全部弄乱，这个时候清洁工就会要求“Stop The World”。三色算法的优势就在于它支持多一些情况的 Mutation，这样能够提高“垃圾”被并发回收的概率。

目前的 GC 主要都是基于三色标记算法。至于清除算法，有原地回收算法，也有把存活下来的对象（黑色对象）全部拷贝到一个新的区域的算法。

总结

好处

用于垃圾回收器升级，将STW变为并发标记。STW就是在标记垃圾的时候，必须暂停程序，而使用并发标记，就是程序一边运行，一边标记垃圾。
避免重复扫描对象，提升标记阶段的效率。

存在问题

浮动垃圾:并发标记的过程中，若一个已经被标记成黑色或者灰色的对象，突然变成了垃圾，由于不会再对黑色标记过的对象重新扫描,所以不会被发现，那么这个对象不是白色的但是不会被清除，重新标记也不能从GCRoot中去找到，所以成为了浮动垃圾，浮动垃圾对系统的影响不大，留给下一次GC进行处理即可。
对象漏标问题（需要的对象被回收)︰并发标记的过程中，一个业务线程将一个未被扫描过的白色对象断开引用成为垃圾（删除引用)，同时黑色对象引用了该对象（增加引用)(这两部可以不分先后顺序);因为黑色对象的含义为其属性都已经被标记过了，重新标记也不会从黑色对象中去找，导致该对象被程序所需要，却又要被GC回收，此问题会导致系统出现问题，而CMS与G1，两种回收器在使用三色标记法时，都采取了一些措施来应对这些问题，CMS对增加引用环节进行处理(Increment Update)，G1则对删除引用环节进行处理(SATB)。