Question

在现实世界中总有这样那样的局限和制约，但计算机将人类从那些局限中解放出来——至少是在试图努力实现这个目标。然而，计算机也是现实世界存在的一部分，当然其本身也会受到制约。因此，计算机只是提供了一种幻觉，让我们人类以为自己已经从这些制约中解放出来了。

看似无限的内存

我们来具体讲讲吧。比如说，内存。大家的电脑上面装了多大的内存呢？最近的电脑内存大多都有几个 GB 吧，我手上的笔记本电脑内存有 8GB。我上高中的时候，电脑只有 32KB 的 RAM，8GB 的容量相当于其 25 万倍了。也就是说，在这 30 年中，一般人可以获得的内存容量是 30 年前的 25 万倍。25 万倍……

不过，无论内存容量有多大，总归不是无限的。实际上，伴随着内存容量的增加，软件的内存开销也在以同样的速率增加着。因此，最近的计算机系统会通过“双重”幻觉，让我们以为内存容量是无限的。

第一重幻觉是垃圾回收（GC）机制。关于这一点我们稍后会详细讲解。

第二重幻觉是操作系统提供的虚拟内存。由于硬盘的容量要远远大于内存（RAM），虚拟内存正是利用这一点，在内存容量不足时将不经常被访问的内存空间中的数据写入硬盘，以增加“账面上”可用内存容量的手段。现在，虽说内存容量已经增加了很多，但也不过是区区几个 GB 而已。相对的，即便是笔记本电脑上的硬盘，也已经有几百 GB 的容量，超过 1TB（1000GB）的也开始出现了。虚拟内存也就是利用了这样的容量差异。

书桌上的文件摊满了，也就没地方放新的文件了。所谓虚拟内存，就好比是将书桌上比较老的文件先暂时收到抽屉里，用空出来的地方来摊开新的文件。

不过，如果在书桌和抽屉之间频繁进行文件的交换，工作效率肯定会下降。如果每次要看一份文件都要先收拾书桌再到抽屉里面拿的话，那工作根本就无法进行了。虚拟内存也有同样的缺点。硬盘的容量比内存大，但相对的，速度却非常缓慢，如果和硬盘之间的数据交换过于频繁，处理速度就会下降，表面上看起来就像卡住了一样，这种现象被称为抖动（Thrushing）。应该有很多人有过计算机停止响应的经历，而造成死机的主要原因之一就是抖动。

GC 的三种基本方式

好了，下面我们来讲讲 GC（Garbage Collection）。在 Java 和 Ruby 这样的语言中，程序在运行时会创建很多对象。从编程语言的角度来看，它们是对象；但从计算机的角度来看，它们也就是一些装有数据的内存空间而已。

在 C 和 C++ 这样的语言中，这些内存空间是由人手动进行管理的。当需要内存空间时，要请求操作系统进行分配，不需要的时候要返还给操作系统。然而，正是“不再需要”这一点，带来了各种各样的麻烦。

因为“不再需要”而返还给操作系统的内存空间，会被操作系统重新利用，如果不小心访问了这些空间的话，里面的数据会被改写，这会造成程序的异常行为，甚至是崩溃。反过来说，如果认为某些内存空间“可能还要用到”而不还给操作系统，或者是用完了却忘记返还，这些无法访问的空间就会一直保留下来，造成内存的白白浪费，最终引发性能下降和产生抖动。从结果来看，让人来管理大量分配的内存空间，是非常困难的。

将内存管理，尤其是内存空间的释放实现自动化，这就是 GC。GC 其实是个古老的技术，从 20 世纪 60 年代就开始研究，还发表了不少论文。这项技术在大学实验室级别的地方已经应用了很长时间，但是可以说，从 20 世纪 90 年代 Java 出现之后，一般的程序员才有缘接触到它。在此之前，这项技术还只是少数人的专利。

术语定义

在讲解 GC 技术之前，我们先来定义两个即将用到的术语。

1. 垃圾

所谓垃圾（Garbage），就是需要回收的对象。作为编写程序的人，是可以做出“这个对象已经不再需要了”这样的判断，但计算机是做不到的。因此，如果程序（通过某个变量等等）可能会直接或间接地引用一个对象，那么这个对象就被视为“存活”；与之相反，已经引用不到的对象被视为“死亡”。将这些“死亡”对象找出来，然后作为垃圾进行回收，这就是 GC 的本质。

2. 根

所谓根（Root），就是判断对象是否可被引用的起始点。至于哪里才是根，不同的语言和编译器都有不同的规定，但基本上是将变量和运行栈空间作为根。

好了，用上面这两个术语，我们来讲一讲主要的 GC 算法。

标记清除方式

标记清除（Mark and Sweep）是最早开发出的 GC 算法（1960 年）。它的原理非常简单，首先从根开始将可能被引用的对象用递归的方式进行标记，然后将没有标记到的对象作为垃圾进行回收。

图 1 显示了标记清除算法的大致原理。

图 1 标记清除算法

图 1 中的 (1) 部分显示了随着程序的运行而分配出一些对象的状态，一个对象可以对其他的对象进行引用。

图中 (2) 部分中，GC 开始执行，从根开始对可能被引用的对象打上“标记”。大多数情况下，这种标记是通过对象内部的标志（Flag）来实现的。于是，被标记的对象我们把它们涂黑。

图中 (3) 部分中，被标记的对象所能够引用的对象也被打上标记。重复这一步骤的话，就可以将从根开始可能被间接引用到的对象全部打上标记。到此为止的操作，称为标记阶段（Mark phase）。标记阶段完成时，被标记的对象就被视为“存活”对象。

图 1 中的 (4) 部分中，将全部对象按顺序扫描一遍，将没有被标记的对象进行回收。这一操作被称为清除阶段（Sweep phase）。在扫描的同时，还需要将存活对象的标记清除掉，以便为下一次 GC 操作做好准备。

标记清除算法的处理时间，是和存活对象数与对象总数的总和相关的。

作为标记清除的变形，还有一种叫做标记压缩（Mark and Compact）的算法，它不是将被标记的对象清除，而是将它们不断压缩。

复制收集方式

标记清除算法有一个缺点，就是在分配了大量对象，并且其中只有一小部分存活的情况下，所消耗的时间会大大超过必要的值，这是因为在清除阶段还需要对大量死亡对象进行扫描。

复制收集（Copy and Collection）则试图克服这一缺点。在这种算法中，会将从根开始被引用的对象复制到另外的空间中，然后，再将复制的对象所能够引用的对象用递归的方式不断复制下去。

图 2 复制收集算法

图 2 的 (1) 部分是 GC 开始前的内存状态，这和图 1 的 (1) 部分是一样的。图 2 的 (2) 部分中，在旧对象所在的“旧空间”以外，再准备出一块“新空间”，并将可能从根被引用的对象复制到新空间中。图中 (3) 部分中，从已经复制的对象开始，再将可以被引用的对象像一串糖葫芦一样复制到新空间中。复制完成之后，“死亡”对象就被留在了旧空间中。图中 (4) 部分中，将旧空间废弃掉，就可以将死亡对象所占用的空间一口气全部释放出来，而没有必要再次扫描每个对象。下次 GC 的时候，现在的新空间也就变成了将来的旧空间。

通过图 2 我们可以发现，复制收集方式中，只存在相当于标记清除方式中的标记阶段。由于清除阶段中需要对现存的所有对象进行扫描，在存在大量对象，且其中大部分都即将死亡的情况下，全部扫描一遍的开销实在是不小。

而在复制收集方式中，就不存在这样的开销。但是，和标记相比，将对象复制一份所需要的开销则比较大，因此在“存活”对象比例较高的情况下，反而会比较不利。

这种算法的另一个好处是它具有局部性（Locality）。在复制收集过程中，会按照对象被引用的顺序将对象复制到新空间中。于是，关系较近的对象被放在距离较近的内存空间中的可能性会提高，这被称为局部性。局部性高的情况下，内存缓存会更容易有效运作，程序的运行性能也能够得到提高。

引用计数方式

引用计数（Reference Count）方式是 GC 算法中最简单也最容易实现的一种，它和标记清除方式差不多是在同一时间发明出来的。

它的基本原理是，在每个对象中保存该对象的引用计数，当引用发生增减时对计数进行更新。

引用计数的增减，一般发生在变量赋值、对象内容更新、函数结束（局部变量不再被引用）等时间点。当一个对象的引用计数变为 0 时，则说明它将来不会再被引用，因此可以释放相应的内存空间。

图 3 引用计数算法

图 3 的 (1) 部分中，所有对象中都保存着自己被多少个其他对象进行引用的数量（引用计数），图中每个对象右上角的数字就是引用计数。

图中 (2) 部分中，当对象引用发生变化时，引用计数也跟着变化。在这里，由对象 B 到对象 D 的引用失效了，于是对象 D 的引用计数变为 0。由于对象 D 的引用计数为 0，因此由对象 D 到对象 C 和 E 的引用数也分别相应减少。结果，对象 E 的引用计数也变为 0，于是对象 E 也被释放掉了。

图 3 的 (3) 部分中，引用计数变为 0 的对象被释放“，存活”对象则保留了下来。大家应该注意到，在整个 GC 处理过程中，并不需要对所有对象进行扫描。

实现容易是引用计数算法最大的优点。标记清除和复制收集这些 GC 机制在实现上都有一定难度；而引用计数方式的话，凡是有些年头的 C++ 程序员（包括我在内），应该都曾经实现过类似的机制，可以说这种算法是相当具有普遍性的。

除此之外，当对象不再被引用的瞬间就会被释放，这也是一个优点。其他的 GC 机制中，要预测一个对象何时会被释放是很困难的，而在引用计数方式中则是立即被释放的。而且，由于释放操作是针对每个对象个别执行的，因此和其他算法相比，由 GC 而产生的中断时间（Pause time）就比较短，这也是一个优点。

引用计数方式的缺点

另一方面，这种方式也有缺点。引用计数最大的缺点，就是无法释放循环引用的对象。图 4 中，A、B、C 三个对象没有被其他对象引用，而是互相之间循环引用，因此它们的引用计数永远不会为 0，结果这些对象就永远不会被释放。

图 4 无法回收，循环引用

引用计数的第二个缺点，就是必须在引用发生增减时对引用计数做出正确的增减，而如果漏掉了某个增减的话，就会引发很难找到原因的内存错误。引用数忘了增加的话，会对不恰当的对象进行释放；而引用数忘了减少的话，对象会一直残留在内存中，从而导致内存泄漏。如果语言编译器本身对引用计数进行管理的话还好，否则，如果是手动管理引用计数的话，那将成为孕育 bug 的温床。

最后一个缺点就是，引用计数管理并不适合并行处理。如果多个线程同时对引用计数进行增减的话，引用计数的值就可能会产生不一致的问题（结果则会导致内存错误）。为了避免这种情况的发生，对引用计数的操作必须采用独占的方式来进行。如果引用操作频繁发生，每次都要使用加锁等并发控制机制的话，其开销也是不可小觑的。

综上所述，引用计数方式的原理和实现虽然简单，但缺点也很多，因此最近基本上不再使用了。现在，依然采用引用计数方式的语言主要有 Perl 和 Python，但它们为了避免循环引用的问题，都配合使用了其他的 GC 机制。这些语言中，GC 基本上是通过引用计数方式来进行的，但偶尔也会用其他的算法来执行 GC，这样就可以将引用计数方式无法回收的那些对象处理掉。

进一步改良的应用方式

GC 的基本算法，大体上都逃不出上述三种方式以及它们的衍生品。现在，通过对这三种方式进行融合，出现了一些更加高级的方式。这里，我们介绍一下其中最有代表性的三种，即分代回收、增量回收和并行回收。有些情况下，也可以对这些方法中的几种进行组合使用。

分代回收

首先，我们来讲讲高级 GC 技术中最重要的一种，即分代回收（Generational GC）。

由于 GC 和程序处理的本质是无关的，因此它所消耗的时间越短越好。分代回收的目的，正是为了在程序运行期间，将 GC 所消耗的时间尽量缩短。

分代回收的基本思路，是利用了一般性程序所具备的性质，即大部分对象都会在短时间内成为垃圾，而经过一定时间依然存活的对象往往拥有较长的寿命。如果寿命长的对象更容易存活下来，寿命短的对象则会被很快废弃，那么到底怎样做才能让 GC 变得更加高效呢？如果对分配不久，诞生时间较短的“年轻”对象进行重点扫描，应该就可以更有效地回收大部分垃圾。

在分代回收中，对象按照生成时间进行分代，刚刚生成不久的年轻对象划为新生代（Young generation），而存活了较长时间的对象划为老生代（Old generation）。根据具体实现方式的不同，可能还会划分更多的代，在这里为了讲解方便，我们就先限定为两代。如果上述关于对象寿命的假说成立的话，那么只要仅仅扫描新生代对象，就可以回收掉废弃对象中的很大一部分。

像这种只扫描新生代对象的回收操作，被称为小回收（Minor GC）。小回收的具体回收步骤如下。

首先从根开始一次常规扫描，找到“存活”对象。这个步骤采用标记清除或者是复制收集算法都可以，不过大多数分代回收的实现都采用了复制收集算法。需要注意的是，在扫描的过程中，如果遇到属于老生代的对象，则不对该对象继续进行递归扫描。这样一来，需要扫描的对象数量就会大幅减少。

然后，将第一次扫描后残留下来的对象划分到老生代。具体来说，如果是用复制收集算法的话，只要将复制目标空间设置为老生代就可以了；而用标记清除算法的话，则大多采用在对象上设置某种标志的方式。

对来自老生代的引用进行记录

这个时候，问题出现了，从老生代对象对新生代对象的引用怎么办呢？如果只扫描新生代区域的话，那么从老生代对新生代的引用就不会被检测到。这样一来，如果一个年轻的对象只有来自老生代对象的引用，就会被误认为已经“死亡”了。因此，在分代回收中，会对对象的更新进行监视，将从老生代对新生代的引用，记录在一个叫做记录集（remembered set）的表中（图 5）。在执行小回收的过程中，这个记录集也作为一个根来对待。

图 5 分代回收方式中的小回收

从任何地方都没有进行引用的老生代中的 F 对象，会通过大回收操作进行回收。

要让分代回收正确工作，必须使记录集的内容保持更新。为此，在老生代到新生代的引用产生的瞬间，就必须对该引用进行记录，而负责执行这个操作的子程序，需要被嵌入到所有涉及对象更新操作的地方。

这个负责记录引用的子程序是这样工作的。设有两个对象：A 和 B，当对 A 的内容进行改写，并加入对 B 的引用时，如果① A 属于老生代对象，② B 属于新生代对象，则将该引用添加到记录集中。

这种检查程序需要对所有涉及修改对象内容的地方进行保护，因此被称为写屏障（Write barrier）。写屏障不仅用于分代回收，同时也用在很多其他的 GC 算法中。

虽说老生代区域中的对象一般来说寿命都比较长，但也决不是“不老不死”的。随着程序的运行，老生代区域中的“死亡”对象也在不断增加。为了避免这些死亡的老生代对象白白占用内存空间，偶尔需要对包括老生代区域在内的全部区域进行一次扫描回收。像这样以全部区域为对象的 GC 操作被称为完全回收（Full GC）或者大回收（Major GC）。

分代回收通过减少 GC 中扫描的对象数量，达到缩短 GC 带来的平均中断时间的效果。不过由于还是需要进行大回收，因此最大中断时间并没有得到什么改善。从吞吐量来看，在对象寿命假说能够成立的程序中，由于扫描对象数量的减少，可以达到非常不错的成绩。但是，其性能会被程序行为、分代数量、大回收触发条件等因素大幅度左右。

增量回收

在对实时性要求很高的程序中，比起缩短 GC 的平均中断时间，往往更重视缩短 GC 的最大中断时间。例如，在机器人的姿势控制程序中，如果因为 GC 而让控制程序中断了 0.1 秒，机器人可能就摔倒了。或者，如果车辆制动控制程序因为 GC 而延迟响应的话，后果也是不堪设想的。

在这些对实时性要求很高的程序中，必须能够对 GC 所产生的中断时间做出预测。例如，可以将“最多只能中断 10 毫秒”作为附加条件。

在一般的 GC 算法中，作出这样的保证是不可能的，因为 GC 产生的中断时间与对象的数量和状态有关。因此，为了维持程序的实时性，不等到 GC 全部完成，而是将 GC 操作细分成多个部分逐一执行。这种方式被称为增量回收（Incremental GC）。

在增量回收中，由于 GC 过程是渐进的，在回收过程中程序本身会继续运行，对象之间的引用关系也可能会发生变化。如果已经完成扫描和标记的对象被修改，对新的对象产生了引用，这个新对象就不会被标记，明明是“存活”对象却被回收掉了。

在增量回收中为了避免这样的问题，和分代回收一样也采用了写屏障。当已经被标记的对象的引用关系发生变化时，通过写屏障会将新被引用的对象作为扫描的起始点记录下来。

由于增量回收的过程是分步渐进式的，可以将中断时间控制在一定长度之内。另一方面，由于中断操作需要消耗一定的时间，GC 所消耗的总时间就会相应增加，正所谓有得必有失。

并行回收

最近的计算机中，一块芯片上搭载多个 CPU 核心的多核处理器已经逐渐普及。不仅是服务器，就连个人桌面电脑中，多核 CPU 也已经成了家常便饭。例如美国英特尔公司的 Core i7 就拥有 6 核 12 个线程。

在这样的环境中，就需要通过利用多线程来充分发挥多 CPU 的性能。并行回收正是通过最大限度利用多 CPU 的处理能力来进行 GC 操作的一种方式。

并行回收的基本原理是，是在原有的程序运行的同时进行 GC 操作，这一点和增量回收是相似的。不过，相对于在一个 CPU 上进行 GC 任务分割的增量回收来说，并行回收可以利用多 CPU 的性能，尽可能让这些 GC 任务并行（同时）进行。由于软件运行和 GC 操作是同时进行的，因此就会遇到和增量回收相同的问题。为了解决这个问题，并行回收也需要用写屏障来对当前的状态信息保持更新。不过，让 GC 操作完全并行，而一点都不影响原有程序的运行，是做不到的。因此在 GC 操作的某些特定阶段，还是需要暂停原有程序的运行。

在多核化快速发展的现在，并行回收也成了一个非常重要的话题，它的算法也在不断进行改善。在硬件系统的支持下，无需中断原有程序的完全并行回收器也已经呼之欲出。今后，这个领域相当值得期待。

GC 大统一理论

像标记清除和复制收集这样，从根开始进行扫描以判断对象生死的算法，被称为跟踪回收（Tracing GC）。相对的，引用计数算法则是当对象之间的引用关系发生变化时，通过对引用计数进行更新来判定对象生死的。

美国 IBM 公司沃森研究中心的 David F. Bacon 等人，于 2004 年发表了一篇题为“垃圾回收的统一理论”（A Unified Theory of Garbage Collection）的论文，文中阐述了一种理论，即：任何一种 GC 算法，都是跟踪回收和引用计数回收两种思路的组合。两者的关系正如“物质”和“反物质”一样，是相互对立的。对其中一方进行改善的技术之中，必然存在对另一方进行改善的技术，而其结果只是两者的组合而已。

例如，用于改善分代回收和增量回收等跟踪回收算法的写屏障机制，从对引用状态变化进行记录这个角度来看，就是吸收了引用计数回收的思路。相对的，引用计数算法也吸收了分代回收算法的思路而进行了一些改进，如来自局部变量的引用变化不改变引用计数等。

Unified Theory 来源于物理学中的大统一理论（Grand Unified Theory，简称 GUT）一词。正如试图统一解释自然界中四种基本作用力的大统一理论一样，这个试图统一解释跟踪回收和引用计数回收的理论，也就被命名为 GC 大统一理论了。