10 分钟快速入门垃圾回收机制
自动内存管理是编程语言发展历程上的一项伟大发明。
在没有自动内存管理前，人们都是手动进行内存管理。在 C 语言中，我们申请内存时，会使用 malloc 函数向操作系统申请内存空间，使用结束后，我们使用 free 函数释放内存。
于是，一些写了 C 语言比较久的同学可能会发现，自己的程序经常遇到内存泄漏、double free、use after free 等错误，这都是因为我们在管理这些内存时，没有正确的释放他们导致的。
而带有自动内存管理的编程语言却不一样，它们带来了一个叫做 runtime 的东西，像操作系统一样，帮我们为新对象分配空间、回收不需要的内存空间，为我们减轻了许多负担。
这篇文章将介绍垃圾回收机制的常用策略。我们将不会讨论特定编程语言是怎么实现的，而是只介绍一些通用的方法，这样你在看任何有关垃圾回收的文章时都可以很轻松地去理解它的原理。
清理垃圾这件事其实只有两步：
- 找垃圾
- 丢垃圾
0x01 谁是垃圾？
垃圾的定义就是：没人用的东西。
在发现垃圾这件事上，我们的重点在于怎样确定哪些对象是没用的。
为此，我们有两种常见的方法：
1. Reference Counting GC - 引用计数算法
每个对象都有一个与之关联的引用数目 refCount， 多一个指针引用就 +1，少一个指针引用就 -1。
当一个对象 refCount <= 0 的时候，它就是个没人要的垃圾。
优点一：实现简单
从实现的角度来看，这种垃圾识别的算法实现的过程与 runtime 耦合较小，只要我们能够在一个变量被赋值的时候判断一下，就可以实现 refCount 的更新，所以它简单到可以作为一个单独的库来实现。
C++ 中的智能指针 shared_ptr 就采用了这种引用计数的方法，它重写了 = 操作符，让它拥有了这一能力。
优点二：不需要独立的寻找过程
从执行的角度来看，垃圾的寻找直接绑定在了程序执行过程中。
我们不需要专门地去写一个复杂的体系来替我们发现垃圾，代码在运行的时候自己就能替我们标记出谁是垃圾。
但问题也来了：
缺点一：维护 refCount 的开销其实很大
如果有多个线程都想引用对象 A，那么对象 A 的 refCount 就会被多个线程同时修改。如果一个线程在修改 refCount 时被其他线程打断，那么 refCount 的值就会变得混乱，从而导致并发安全问题。
学过操作系统的同学应该会熟悉：为了避免并发问题，我们需要保证refCount 具有原子性。
保证原子性的手段就是在修改refCount前对它加锁。只要加锁，其他想修改refCount的线程就会停下来等待锁被释放。
但这便带来了另外一个问题：当我们在多线程的环境里引用公共对象时，多线程的效率会严重降低，这是不可忍受的。
缺点二：无法回收循环引用
如果大家写过环形队列，肯定还记得它的核心特点：把头部和尾部连接，形成一个循环引用。
这种操作看似巧妙，但对我们的算法而言将是一个巨大的打击：
假如你不想要这个环形队列了，但它们的 refCount 都是 1，引用计数算法无法认为这是一坨垃圾，它会一直留在内存中，造成内存泄漏。
2. Tracing GC - 追踪垃圾回收算法
对于引用计数算法这一问题的本质其实还是不能鉴别出谁到底有没有用。
如果说我们从头开始遍历所有的对象，看他们现在在用谁，这样不就知道谁是垃圾了嘛！
于是我们便有了 Tracing GC ，它也被称为可达性收集法。
其基本原理就和深度优先搜索一样：
- 标记根对象（如常量、栈空间中的对象等）
- 从根对象出发，扫描所有的可达对象
- 那些不可达的，就都是垃圾了
好吧，这么一看我们是从根源上解决了最大的问题。
但是别急，事情还没这么快结束。
解决一个严重 BUG 的方法就是引入 N 个新的 BUG，接下来我会向你证明这一点。
让我们看看 Tracing GC 在其他方面表现得怎么样：
- ✔ 开销 —— 并发安全：因为我们没有原子性的变量要去维护了，所以现在我们可以想怎么写就怎么写。
- ❌ 实现 —— 与 runtime 高度耦合： 与引用计数不同，根对象的识别在不同的编程语言都不太一样，因此不同的 runtime 实现都不太一样。
- ❌ 执行 —— 复杂的寻找过程：如何在程序运行的同时扫描垃圾？ Tracing GC 的最大挑战就在这里。
复杂的寻找过程
Tracing GC 是通过扫描的方式来识别垃圾的，扫描工作会被安排在一种叫做 GC Thread 的线程中进行。
扫描的过程有三种：
- Serial GC: 只有一个 GC Thread 干活
- Parallel GC: 有多个 GC Thread 同时干活
- Concurrent GC: 业务线程和 GC 线程同时执行
Serial GC 和 Parallel GC 的区别只有线程的个数，它们和业务线程的关系是同步执行。
注意：这里所说的同步执行不是指一起执行，而是一个执行完才能执行下一个。
在 GC 执行期间，所有的业务线程都会被暂停，整个程序看起来会像卡死一样，这被称为 Stop The World。
这听起来太糟糕了，所以我们迫切希望 GC 能够并发执行。
并发 GC 的改造：三色标记法
并发意味着我们的 GC 扫描的过程中，CPU 会在我们的业务代码和 GC 的扫描代码之间不断地进行上下文切换 —— 以保证业务和 GC 都能不断运行。
此外，我们也不希望 GC 一扫就扫半天，我们希望能有多个 GC 线程帮我们一起扫描。
这么一来，我们需要三种不同的颜色来表示对象，代表三种不同的状态：
- 白色：对象从被未访问过
- 灰色：扫描过对象本身，正在扫描它的全部引用的对象
- 黑色：扫描过对象本身，也扫描过它全部引用的对象
我们用三个不同的集合来放这些对象。
在最开始时，所有的对象都在白色集合中。
扫描时，我们还是从根节点开始，先将根对象标为黑色、被根节点引用的对象标为灰色。
接下来，我们的 GC 线程只要不断地从灰色集合里拿对象，扫描之后丢进黑色对象就好了。
当灰色集合为空时，扫描完毕。此时白色集合中的对象就是垃圾，可以被直接清除。
这种改造其实就是把深度优先搜索改造成了广度优先搜索，从而实现了并发。
并发陷阱：误删
我们来看如果业务线程和 GC 线程同时执行会怎么样：
上图表示 GC 运行时的 3 个时刻。
- 时刻 1：我们的 GC 从对象 A 扫描出了对象 B 和 对象 C
- 时刻 2：对象 A 增加了对象 D 的引用
- 时刻 3：对象 B 删除了对象 D 的引用
因为我们只扫描灰色的对象，对象 D 从事实上来说并不是垃圾，但它完美地错过 GC 了，将会遭到误删，是个大问题。
要想解决它，我们就得通过某种操作，让我们的 GC 可以记录下这个白色对象 D。
我们可以从两个不同的角度来分析它：
-
在时刻2：黑色对象增加了一个白色对象的引用
如果想从这个角度解决问题，那就在黑色对象增加引用时，把这个对象 D 记下来，待会扫描它，这被称为增量更新。 -
在时刻3：灰色对象断开了一个白色对象的引用
如果从这个角度解决问题，那就在灰色对象断开引用时，把对象 D 记下来，待会扫描它，这被称为原始快照。它意味着无论对象怎么改变，我们还是按照刚开始 GC 时的对象状态来扫描它。
时间停止：STW
现在，我们有了一个看似没有 BUG 的并发GC，它分为三个阶段：
- 初始化阶段：找到所有的根对象
- 并发标记阶段：三色标记法扫描
- 重新标记阶段：扫描并发标记阶段错过的白色对象
但我们在执行扫描时，还是会遇到 Stop-The-World。
我们的 Stop-The-World 将会发生在扫描的在第一阶段和第三阶段。
-
第一阶段：停止根对象的制造，以确定扫描起点。
-
第三阶段：停止新对象的制造，以保证没有新对象错过 GC。
不过还好，因为根对象和重新扫描的对象数量其实不多，所以这两个 Stop-The-World 的间隔将会很短
0x02 丢垃圾
通常来说，清理垃圾有三种方法，他们都很好理解。
Mark-sweep GC: 将垃圾对象的内存标记为可分配
这种清理垃圾的方法应该是最快的，因为它其实根本没有清理，只是单纯地声明这个地方可以放新对象了。
但清理的时候轻松了，要用的时候就没那么容易了。
我们都知道，对于新来的对象，如果想要找个安家的位置，那必须得挑选一个合适自己大小的空闲空间。
不同的对象变成垃圾的时间肯定不一样，这一通操作清理完以后，会把可用空间变得东一块西一块，甚至有可能出现一种极端的情况：就算总体的可用空间满足对象的需求，但因为被分散到各个角落，所以无法分配。
这种情况我们叫做内存碎片化。
Compact GC: 移动并整理存活对象
和我们平时打扫卫生一样，我们在丢垃圾的时候，也会顺手把房间整理一下。
要解决碎片化的问题，要实现的就是把存活的对象放到内存中的一端。
这样，另外一端就全部都是垃圾，可以用来分配新的对象。
这种操作让我们的可用内存和空闲内存都是连续的，使得我们在分配新对象时可以进行指针碰撞。
指针碰撞指的是：如果我们把内存当作一个线性表，用一个指针cur指向线性表中第一个可用空间的地址，
那么如果要分配一个新的size的对象，就可以直接得知它的起始位置是 cur，分配完完这个对象以后，下一个可用的位置 cur = cur + size。
// 为一个新对象申请空间
// @param size 新对象的大小
// @return 新对象的起始地址
(void*) allocate(int size)
{
if(cur + size <= total_size) { // 判断空间是否足够申请
int addr = cur; // 新对象的起始地址
cur = cur + size; // 下一个对象的起始地址
return addr;
}
return nullptr; // 空间不足，申请失败
}
但这样做其实还有一个问题：整理的过程需要时间。
其实不难理解，扫描完一次垃圾之后的内存空间肯定是东一块西一块，如果想让所有可用的对象乖乖地贴在一端，那肯定得交换。
Copying GC: 将存活对象复制到另外的内存空间
和上一种算法相比，它就简单粗暴的多了。
这种算法在清理垃圾的时候，直接找一块干净的内存空间（现在没有存对象的），然后把前面标记的不是垃圾的对象全部丢进去。
这样，原来的那块空间就全部都是垃圾了。
虽然还是需要复制，但至少它整理的过程少了交换这一步骤。
但这种丢法也有它的缺点，比如说：必须找一块干净的内存空间，奢侈。
如果存活的对象比较多的话，就得复制一堆东西，花时间。
既然这些丢垃圾的方法各有不同的缺点，那么我们在实际中肯定要根据对象的特点来选择合适的清理策略。
混合清理策略 —— 分代假说
这个算法很多编程语言的 runtime 都在用，特别是 Java。
分代假说认为：大部分对象都属于早年夭折的类型。
这也很好理解，毕竟我们现在的编程语言都喜欢认为万物皆对象，你的一个函数里可能就造出了好几个对象，但最终只返回那么一两个。
所以，如果我们为每个对象设置一个“年龄” —— 该对象所经历过的 GC 次数。
这样一来，我们就可以区分出对年轻的对象和老的对象，并为他们分别采用不同的 GC 策略。
-
年轻代： 由于存活对象少，可以采用 Copying GC 的策略来清理。
-
老年代： 由于一直活着，反复复制开销较大，那我们就采用 Mark-sweep 的策略清理。
0x03 编程语言运行时中的垃圾收集器
上面我们说的那些都是理论基础，如果我们从里面挑选一两个进行实现，那就成为了编程语言 runtime 中的 垃圾收集器。
在实现算法的过程中，垃圾收集器会根据编程语言的特性来修改算法，
以 Java 为例， 从 JDK1.1 到 JDK1.8，Java 的开发者们开发出了 6 种 GC 收集器，都是以跟踪标记的方式寻找垃圾，使用分代假说清理垃圾。随着 JDK1.8 发布的 G1 收集器会还通过建立数学模型来预测 Stop-The-World 的时间，让停顿更加可控，被广泛应用于商业领域。
PHP 则是知名的引用算法使用者，这和 PHP 主要使用的 CGI 模式有关，PHP 代码的生命周期主要在一次请求结束，所以它很少有机会开启一个新的进程来清理垃圾。
Python 为了让自己可以适应各种应用场景，直接开放了 gc 模块，允许开发者实现自己的垃圾清理算法。
Go 通过更为先进的内存分配算法 TCMalloc 解决了内存碎片化的问题，通过编译器优化实现逃逸分析，让早期创建的对象直接在栈上销毁，从而不依赖分类假说，让 STW 停顿缩短至微秒级别。这是它迅速走红的原因之一。
本文介绍的垃圾收集算法并不完善，在学习具体的垃圾收集器算法时，可以结合这门编程语言的特征和它的使用场景，再来分析它是如何修改和完善这些算法的，这样可以学习得更快。
参考链接：
