11 内存管理

11.1 垃圾

垃圾（garbage）指的是已分配但是不再需要的内存。典型的编程语言的运行时系统采用两种不同的内存分配方式。一种是分配给环境；这种分配方式要和静态作用域保持一致，所以它只需要支持推入（push）和弹出（pop）操作。函数调用返回时，为其环境分配的空间也被返回，供后续函数使用，看似没有成本。【注释】与之相对，在贮存中分配的内存必须伴随某个值的一生，可能要超过其创建位置的作用域——事实上，它可能一直存活下去。因此，我们需要不同的策略来回收在贮存中分配空间所产生的垃圾。

并非没有成本。硬件必须执行“弹出”指令。这不见得就一定比其他内存管理策略更高效。

空间回收的方法有很多，大体可以分到两个阵营中：人工和自动。人工的方式依赖于开发者能够了解内存的使用，并正确的释放不需要的内存。一般认为，人并不擅长做这种事（虽然在某些情况下，人类拥有机器所无法获取的知识）。因此，几十年来，自动化的方法越来越普及。

11.2 什么样的垃圾回收是“正确的”？

垃圾回收既不应该太早地收回空间（可靠性，soundness）也不能太晚（完备性，completeness）。虽然两者都可以被视为缺陷，但是它们的影响并不是对称的：可以说，过早收回糟糕得多。这是因为，如果过早回收了某个贮存地址，计算将继续，并可能将其他数据写入该地址，从而访问到无意义的数据。往好了说，这会导致程序不正确，极端情况下后果更严重，比如可能会导致安全问题。反之，过迟收回会导致性能损失，并且可能最终导致程序终止，尽管此时存在理论上可用的内存。这种性能损失以及程序过早终止很令人讨厌，在某些关键任务系统中可能会导致重大问题，不过，至少程序不会进行无意义的运算。

理想情况下，我们希望拥有所有的这三项：自动化（automation），可靠性和完备性。然而，这里我们面对的是不可兼得的情形，最多只能选择两项。理想的人类能够做到可靠性和完备性，但实践中实现其中一个都很少见。【注释】计算机可以实现自动化，同时可以提供可靠性和完备性中的一个，但可计算性论证表明，自动化的计算过程不能同时达成这两者。实践中，自动化技术一般选择实现可靠性，出于以下原因：（a）它造成的损害最小；（b）它相对更容易实现；（c）在添加一些人工帮助的情况下，可以接近完备性。

你当然是完美的，但是你的程序员同行呢？顺便说一下，经济学理论在等你验证呢。

11.3 人工回收

人工的最彻底的方式是将所有内存回收交由人操作。例如，在C语言中提供了两个基本指令：malloc用于分配内存，free用于释放内存。malloc的输入是（内存的）大小，返回是对贮存的引用；free的输入是这种引用，释放其占用的内存。

        “在当代欧美语言，"Moloch"摩洛这个词有特定的引申义，指代需要极大牺牲的人物或者事业。”——[维基百科，摩洛词条](http://en.wikipedia.org/wiki/Moloch)
        “我不认为这个名字听起来像malloc是巧合。”——Ian Barland

11.3.1 完全人工回收的代价

先来考虑一下这些操作的复杂度。首先我们假设malloc有个指向贮存的关联寄存器（比如new-loc），每次分配的时候直接获取下一个可用地址。这个模型非常简单——可惜只是看上去简单而已。问题出在当你需要用free释放内存时。如果调用free针对的是最后一次malloc分配的内存，那么没有问题；但是贮存中数据一般不遵堆栈的规律。如果释放的不是最新分配的内存，将会在贮存中留下空洞。空洞会导致碎片化（fragmentation），最坏的情况下，即使贮存中有足够的空间，也无法分配任何对象——许多分割的碎片，没有一个足够大。

练习

原则上，我们可以通过使所有空余空间相邻来解决碎片化的问题。怎么达成这一点？仔细考虑所有的后果，然后描述一下如何手工进行这项工作。

在大多数手动内存管理方案中，碎片化仍然是个不可克服的问题，不过在这个看上去很简单的方案里还有其他东西值得考虑。释放某个值之后会发生什么？运行时系统需要用某种方式记录这块内存可被分配。它是通过维护空闲表——空闲空间的链表——来达成这点的。稍作思考就会想到问题，空闲表存在哪，它的内存又由谁来管理呢？答案是空闲表存放在空闲的内存单元格中，这就意味着内存分配时存在最小分配单元。

那么，原则上，每次malloc现在必须遍历空闲表以找到合适的位置。说“合适”是因为分配者必须做出复杂的决定。遇到第一个匹配的空间就分配呢还是继续找找？而且“匹配”又是怎么定义的呢？应该选取那些大小刚好的空间，还是将大些的空间拆分成小块（从而增加创建不可用的小空间的可能性）？还有其它诸多问题。

程序员希望内存分配高效。【注释1】因此，实践中，分配系统倾向于只使用一组固定的尺寸，通常是2的幂。这样我们就可以不是只维护一个空闲表，而是为每个尺寸（都是2的幂）维护一个空闲表。然后再维护一个指向这些表的数组，位操作可以减小数组索引的代价。当然，这样会浪费一些空间，因为当需要那些不是2的幂尺寸的内存时，最终分配给其的内存尾部将会有空余。（这是计算机科学中经典的取舍(trade-off)：空间换时间）。free需要将释放的内存放到合适的链表中，有时候还需要将较大块的内存分割成小块以为将来的分配做准备。这个模型中的任何部分都不像看上去的那样高效。【注释2】

如果内存分配不够高效，开发者会尝试各种奇技赢巧来重用程序中的值，这会降低代码的清晰性，很有可能会导致错误。

特别地，free并不免费（译注：双关）。

当然，所有这些都基于程序员可以写出可靠（忽略完备）程序的基础上。但是他们做不到。

11.3.2 引用计数

由于完全手工内存回收给程序员带来极大的负担，一些半自动化技术被广为使用，最为人知的便是引用计数（reference counting）。

使用引用计数的方式，每个值都关联一个计数，记录对其引用的个数。程序员负责负责递增和递减这些计数。当计数降为0时，该值的空间可以安全的回收供未来使用。

请注意，上面简单的定义中隐藏了两个重要假设：

程序员可以记录每一次引用。回忆一下，别名也是引用。因此，当写出下面的代码时，
```
 (let ([x <some value>])
   (let ([y x])
     ..))
```
程序员需要记住y是对x引用的那个值的第二次引用，因此要增加该值的引用计数。
每个值只有有限个引用。如果数据中存在环路，这条假设不成立。

由于需要手动递增和递减引用，这种技术缺乏可靠性与完备性。事实上，上述第二个假设自然导致完备性的丧失，而第一个假设则指出了最简单的方式来打破可靠性。

手工管理内存的弊端还可以更为深层隐晦。由于程序员负责释放内存（或者，等效的，管理引用计数），内存管理策略必须成为每个库接口的一部分：即，“库中分配的值谁来释放？库会否释放传递给它的值？”很不幸，用文档准确记录、并遵守这种策略信息极其困难，更糟的是，它会导致文档中充斥关于底层的细节，它们通常与库要封装的行为毫无关系。

一个有趣的想法是将计数值的增减自动化。另一个想法是在实现中添加循环检测（cycle-detection）。引入这两者将解决上述的很多问题，但是引用计数还有一些其它问题：

引用计数会增加每个对象的大小。计数器需要足够大以防止溢出，又要足够小以避免过多的内存占用。
对这些计数器值的增减花费的时间会相当可观。
如果一个对象的引用计数降至0，那么它所引用的所有内容的计数值都需要减一，这种行为可能会是递归的。这意味着一次释放操作可能会花费大量时间，除非使用聪明的“惰性（lazy）”技巧（这样的话又会导致内存占用增加）。
为了减少计数值，我们需要遍历已经是垃圾的对象。这看上去很违反直觉：遍历我们已经不感兴趣的对象。工程实践中这会产生后果：这些我们不感兴趣的对象有可能已经很久没有被访问过了，这意味着它们可能被换页换出内存了。引用计数器需要将它们换页回内存，仅为了告诉它们它们不再被需要了。

出于所有这些原因，应谨慎引用计数。你不应接受它作为默认，而是应该问自己，为什么拒绝通常被认为更好的自动化技术。

练习

如果引用计数溢出了，哪些正确性属性被破坏，是怎么被破坏的？权衡利弊。

11.4 自动回收，或垃圾收集

有些人认为引用计数是“垃圾收集”技术的一种。我更喜欢用后一个术语来指完全自动的技术。但是浏览网页时请注意可能的混淆。

现在让我们来简要地考察一下让语言的运行时系统自动化回收垃圾的过程。我们将使用缩写GC（Garbage Collection）同时指代垃圾回收的算法与垃圾回收的过程，上下文可以帮你区分具体指代哪个。

11.4.1 概览

所有GC算法的核心是通过值间引用关系遍历内存。遍历从根集（root set）开始，也就是是程序可能引用贮存中值的所有地方。通常，根集由环境中的绑定变量以及全局变量组成。在实际实现中，还需要考虑到类似寄存器中的引用这种易逝值。从根集开始，算法使用一系列算法——通常是深度优先搜索【注释】的变体——来遍历所有可访问的值，以识别所有存活的值（即，通过一些程序操作的序列可用到的值）。按定义所有其它数据就是垃圾。不同的算法使用不同的方式回收这些空间。

通常选用深度优先搜索，因为它适用于基于堆栈的实现。当然，你可能（也应该）想知道GC自己的栈存储在哪里！

11.4.2 事实和可证性

如果你仔细阅读的话，你会发现上面我描述了一个算法。这是实现的细节，而不是规范的一部分！垃圾回收的规范是事实（truth）的表述：我们要准确地回收所有是垃圾的值，不多也不少。但是对于任何图灵完备的编程语言，我们都没法得出这一事实，于是我们退而求其次，寻求可证性（provability）。上述的算法描述提供了存活性的有效“证明”，其补集就是垃圾。这个方案当然还有变种，收集更多或更少的垃圾，取决于证明“垃圾性”的不同强度。

上面的说的最后一点指出了严格规范术语描述中的缺陷，对于要回收多少垃圾它完全没有说明。考虑一下极端情况实际上是有益的。

思考题

定义一个可靠的垃圾回收策略很简单。同样，定义一个完备的的垃圾回收策略也非常简单。你能想到怎么做吗？

要做到可靠，我们只要确保不会错误的移除任何可能存活的数据。一种确保无疑的方式就是完全不回收垃圾。与之对应，完备的GC回收所有东西。显然这两者都是无用的（后者显然极其危险）。这为我们的工程实践指明了一点，我们不仅需要GC是可靠的，也希望它足够完备，同时还要足够高效。

11.4.3 核心假设

能够可靠地执行GC依赖于两条关键的假设。一条有关语言的实现，另一条有关语言的语义。

对语言中的值，GC需要知道该值的类型以及它在内存中的表示法。例如，当遍历到cons单元，它必须知道：
1. 这是一个cons单元；因此，
2. 它的first在哪里，例如位于4个字节的偏移量的地方，
3. 它的rest在哪里，例如位于8个字节的偏移量的地方。
显然，这个属性必须递归地保持，使得遍历算法能够正确映射内存中的值。
程序不能通过下面两种方式生成引用：
1. 对象引用不能发生在语言实现预先定义的根集之外。
2. 对象引用只能指向对象中明确定义的点。
违反第二条时，GC将完全乱套，错误的解释数据。第一条看上去显而易见，如果它被违反，意味着运行时系统错误地理解语言的语义。然而这条的后果有点微妙，下面将会讨论。

11.5 保守垃圾回收

上文说过，一般根集包含环境、全局变量和一些易逝值。引用还可能出现在什么地方？

在大部分语言中，没有其他地方了。但是有些语言（说的就是你们，C和C++）允许将引用转换成数，以及将任意数转换成引用。因此，原则上，程序中的任何数值（由于C和C++类型系统的特性，程序中几乎任何值）都可以被视为引用。

两个原因使得它问题重重。首先，GC不能只将其注意力集中到一个较小的根集；现在整个贮存都是潜在的根集。其次，如果GC试图以任何方式修改某个对象——例如在遍历时记录一个“访问”位——这时它可能修改了一个非引用值：例如，它可能实际上改变了程序中某个（看似无关的）数型常量。因此，像C和C++这样的语言中的特征组合起来，使得合理而有效的GC非常困难。

但并不是不可能。一个令人兴奋的研究方向——称为保守GC——成功的为此类语言创造了足够高效的GC系统。保守（conservative）GC背后的基本原则是，尽管理论上每个贮存地址都可能属于根集，但实际上它们大部分都不是。它会通过一系列聪明的观察来推断出哪些位置肯定不是引用（这点和传统GC相反），然后将它们安全地忽略掉：例如，在字节对齐的体系架构中，奇数值不可能为引用。通过忽略大部分贮存，通过对程序行为作出一些基本的假定（例如程序不可能产生某种类型的引用），并且小心操作不去修改贮存（例如，不改变值中的比特，不移动数据）的情况下，可以得到一个还算有效的GC策略。

刻鹄类鹜。

保守GC在那些使用或者依赖C和C++实现的编程语言中比较常见。例如，早期的Racket就完全依靠它。这是基于以下原因：

它是种便捷的自举技术，语言实现者能得以将精力集中在其它更富革新性的特性上。
如果语言能控制所有的引用（比如Racket），那么可以使用便于提高GC效率的内存表示法（例如，用1填充所有(真正的)数的最低有效位）。
它使得该语言和C以及C++实现的库交互变得容易（当然前提是这些库也符合该技术的要求）。

这里需要解释一下名词。如前所述，所有实用的GC技术都是“保守的”，也就是说它们用（潜在的）可访问性代替真实中的是否访问。然而，“保守”这个词已经成为专门的术语，指在不合作（但不是故意对抗）的运行时系统中工作的GC技术。

11.6 精确垃圾回收

在传统的GC术语中，“保守”的反义词是精确（precise）。这也是误称，因为GC不可是精确的，即同时做到可靠和完备。这里精确更多是对识别引用能力的表述：当面对值时，精确GC知道什么是和不是引用，以及引用的位置在哪。相对保守GC，这省去了猜测哪些值不是引用（并以此尽可能多地消除潜在引用）这项繁重的工作。

大多数当代语言的运行时系统使用精确GC，而精确GC领域中存在大量的实现技术。我推荐Paul Wilson 的调查报告（虽然这份材料有点显老，但在这个快速发展的领域中仍是很好的资源）和Richard Jones 的书和资料。最后，对于世代垃圾收集器的概述，可以读一下简单的世代垃圾收集器和快速分配。

11. 内存管理