内存资源回收史

本文发表于2004年2月《CSDN开发高手》

写作本文的初衷是想和大家分享资源回收（ Garbage Collection）技术简单而有趣的发展史。动笔之前，我站在窗边，望了望正在小区里装运垃圾的清洁车。和生活中环卫工人们清运垃圾的工作相似，软件开发里的资源回收其实就是一种自动打扫和清除内存垃圾的技术，它可以有效防范动态内存分配中可能发生的两个危险：因内存垃圾过多而引发的内存耗尽（这和生活垃圾太久没清理，堆积成山没有区别），以及不恰当的内存释放所造成的内存侵占（这类似于我们清理垃圾过程中把门堵了，让楼道中人没法进出）。

据历史学家们介绍，公元前2500多年，古印度摩亨约－达罗城已经把垃圾桶放入房间中，一千多年前的中国人更是修筑了当时世界上保洁能力最强的都市 ——长安。今天，当我们在软件开发中体验自动资源回收的便捷与舒适时，我们至少应当知道，这种拒绝杂乱、追求整洁的“资源回收”精神其实是人类自古以来就已经具备了的。

拓荒时代

国内的程序员大多是在 Java 语言中第一次感受到资源回收技术的巨大魅力的，许多人也因此把 Java 和资源回收看成了密不可分的整体。但事实上，资源回收技术早在 Java 语言问世前 30 多年就已经发展和成熟起来了， Java 语言所做的不过是把这项神奇的技术带到了广大程序员身边而已。

如果一定要为资源回收技术找一个孪生兄弟，那么， 历（Lisp）语言才是当之无愧的人选。 1960 年前后诞生于 麻省理工学院 的 历 语言是第一种高度依赖于动态内存分配技术的语言： 历中几乎所有数据都以“串”的形式出现，而“串”所占用的空间则是在堆中动态分配得到的，因此，历 语言先天就具有的动态内存管理特性要求， 历语言的设计者必须解决堆中每一个内存块的自动释放问题（否则， 历 程序员就必然被程序中不计其数的 释放 或 删除语句淹没），这直接导致了资源回收技术的诞生和发展——说句题外话，上大学时，一位老师曾告诉我们， 历是对现代软件开发技术贡献最大的语言。我当时对这一说法不以为然：布满了圆括号，看上去像迷宫一样的 历 语言怎么能比 C 语言或 Pascal 语言更伟大呢？不过现在，当我知道资源回收技术、数据结构技术、人工智能技术、并行处理技术、虚拟机技术、元数据技术以及程序员们耳熟能详的许多技术都起源于 历 语言时，我特别想向那位老师当面道歉，并收回我当时的幼稚想法。

知道了 历 语言与资源回收的密切关系，我们就不难理解，为什么资源回收技术的两位先驱者 约翰 麦卡锡(J. McCarthy) 和 明斯基(M. L. Minsky) 同时也是 历 语言发展史上的重要人物了。 麦卡锡 是 历 之父，他在发明 历 语言的同时也第一次完整地描述了资源回收的算法和实现方式； 明斯基 则在发展 历 语言的过程中成为了今天好几种主流资源回收算法的奠基人——和当时不少技术大师的经历相似， 麦卡锡 和 明斯基 在许多不同的技术领域里都取得了令人艳羡的成就。也许，在 1950 年代那个软件开发史上的拓荒时代里，思维敏捷、意志坚定的研究者更容易开山立派吧。

在了解资源回收算法的起源之前，有必要先回顾一下内存分配的主要方式。我们知道，大多数主流的语言或运行环境都支持三种最基本的内存分配方式，它们分别是：

一、静态分配（ Static Allocation ）：静态变量和全局变量的分配形式。我们可以把静态分配的内存看成是家里的耐用家具。通常，它们无需释放和回收，因为没人会天天把大衣柜当作垃圾扔到窗外。

二、自动分配（ Automatic Allocation ）：在栈中为局部变量分配内存的方法。栈中的内存可以随着代码块退出时的出栈操作被自动释放。这类似于到我们的皮鞋，出门的时候就穿上，回到家就摆鞋柜固定格子里。

三、动态分配（ Dynamic Allocation ）：在堆中动态分配内存空间以存储数据的方式。堆中的内存块好像我们日常使用的餐巾纸，需要了就拿出来用，如果随手就扔，屋内就会满地狼藉，所以，此时最好走到垃圾桶前，扔进去。像我这样的懒人做梦都想有一台家用机器人跟在身边打扫卫生，不用我多走几步或者练投篮。在软件开发中，如果你懒得释放内存，那么你也需要一台类似的机器人——这其实就是一个由特定算法实现的资源回收器。

也就是说，下面提到的所有资源回收算法都是在程序运行过程中收集并清理废旧“餐巾纸”的算法，它们的操作对象既不是静态变量，也不是局部变量，而是堆中所有已分配内存块。

累积计数（ Reference Counting ）法

1960 年以前，人们为胚胎中的 历 语言设计资源回收机制时，第一个想到的算法是累积计数法。拿餐巾纸的例子来说，这种算法的原理大致可以描述为：

午餐时，为了把脑子里突然跳出来的设计灵感记下来，我从餐巾纸袋中抽出一张餐巾纸，打算在上面画出系统架构的蓝图。按照“餐巾纸使用规约之引用计数版”的要求，画图之前，我必须先在餐巾纸的一角写上计数值 1 ，以表示我在使用这张餐巾纸。这时，如果你也想看看我画的蓝图，那你就要把餐巾纸上的计数值加 1 ，将它改为 2 ，这表明目前有 2 个人在同时使用这张餐巾纸（当然，我是不会允许你用这张餐巾纸来擦鼻涕的）。你看完后，必须把计数值减 1 ，表明你对该餐巾纸的使用已经结束。同样，当我将餐巾纸上的内容全部誊写到笔记本上之后，我也会自觉地把餐巾纸上的计数值减 1 。此时，不出意外的话，这张餐巾纸上的计数值应当是 0 ，它会被资源回收器——假设那是一个专门负责打扫卫生的机器人——捡起来扔到垃圾箱里，因为资源回收器的惟一使命就是找到所有最终计数值为 0 的餐巾纸并清理它们。

累积计数法的优点和缺陷同样明显。这一算法在执行资源回收任务时速度较快，但算法对程序中每一次内存分配和指针操作提出了额外的要求（增加或减少内存块的引用计数）。更重要的是，累积计数法无法正确释放循环引用的内存块，就像我们小时候常说的“从前有座山,山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事：从前有座山,山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事：…… ”的故事有异曲同工之妙。

这说明，单是使用累积计数法还不足以解决资源回收中的所有问题。正因为如此，累积计数法也常常被研究者们排除在狭义的资源回收法之外。当然，作为一种最简单、最直观的解决方案，引用计数法本身具有其不可替代的优越性。 1980 年代前后， 弗里德曼(D. P. Friedman) ，外斯( D. S. Wise) ，贝克 （H. G. Baker） 等人对累积计数法进行了数次改进，这些改进使得累积计数法及其变种（如延迟计数法等）在简单的环境下，或是在一些综合了多种算法的现代资源回收系统中仍然可以一展身手。

标记－清除（ Mark-Sweep ）法

第一种实用和完善的资源回收法是 麦卡锡 等人在 1960 年提出并成功地应用于 历 语言的标记－清除法。仍以餐巾纸为例，标记－清除法的执行过程是这样的：

午餐过程中，餐厅里的所有人都根据自己的需要取用餐巾纸。当资源回收机器人想收集废旧餐巾纸的时候，它会让所有用餐的人先停下来，然后，依次询问餐厅里的每一个人：“你正在用餐巾纸吗？你用的是哪一张餐巾纸？”机器人根据每个人的回答将人们正在使用的餐巾纸画上记号。询问过程结束后，机器人在餐厅里寻找所有散落在餐桌上且没有记号的餐巾纸（这些显然都是用过的废旧餐巾纸），把它们统统扔到垃圾箱里。

正如其名称所暗示的那样，标记－清除法的执行过程分为“标记”和“清除”两大阶段。这种分步执行的思路奠定了现代资源回收法的思想基础。与引用计数法不同的是，标记－清除法不需要运行环境监测每一次内存分配和指针操作，而只要在“标记”阶段中跟踪每一个指针变量的指向——用类似思路实现的资源回收器也常被后人统称为追踪回收器（ Tracing Collector ）

伴随着 历 语言的成功，标记－清除法也在大多数早期的 历 运行环境中大放异彩。尽管最初版本的标记－清除法在今天看来还存在效率不高（标记和清除是两个相当耗时的过程）等诸多缺陷，但在后面的讨论中，我们可以看到，几乎所有现代资源回收法都是标记－清除思想的延续，仅此一点， 麦卡锡 等人在资源回收技术方面的贡献就丝毫不亚于他们在 历 语言上的成就了。

复制（ Copying ）法

为了解决标记－清除算法在资源回收效率方面的缺陷， 明斯基 于 1963 年发表了著名的论文“使用阵列存储之后备内存的一种 历 语言资源回收法（ A LISP Garbage Collector Algorithm Using Serial Secondary Storage ）”。 明斯基 在该论文中描述的算法被人们称为复制法，它也被 明斯基 本人成功地引入到了 历 语言的一个实现版本中。

复制法别出心裁地将堆空间一分为二，并使用简单的复制操作来完成资源回收工作，这个思路相当有趣。借用餐巾纸的比喻，我们可以这样理解 明斯基 的复制法：

餐厅分成南区和北区两个部分。午餐时，所有人都先在北区排队购餐，并取餐厅用的餐巾纸，然后到南区吃饭和使用餐巾纸（因为北区被排队占满，而且也没桌子）。这样，吃完饭后，资源回收机器人只要简单地把南区中所有散落的餐巾纸扔进垃圾箱就算完成任务了。下一次资源回收的工作过程也大致类似。如此循环往复，每次资源回收都只需简单地转移（也就是复制）一次，资源回收速度无与伦比。

明斯基的设计绝对算得上一种奇思妙想。分区、复制的思路不仅大幅提高了资源回收的效率，而且也将原本繁纷复杂的内存分配法变得前所未有地简明和扼要（既然每次内存回收都是对整个半区的回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存就可以了），这简直是个奇迹！不过，任何奇迹的出现都有一定的代价，在资源回收技术中，复制法提高效率的代价是内存需要多一倍，现有内存将剩一半可用。

无论优缺点如何，复制法在实践中都获得了可以与标记－清除法相比拟的成功。除了 明斯基 本人在 历 语言中的工作以外，从 1960 年代末到 1970 年代初， 芬尼克乐（R. R. Fenichel ）和尤切尔森（ J. C. Yochelson） 等人也相继在 历 语言的不同实现中对复制法进行了改进， 安伯格（S. Arnborg） 更是成功地将复制法应用到了 Simula 语言中。

至此，资源回收技术的三大传统算法——累积计数法、标记－清除法和复制法——都已在 1960 年前后相继问世，三种算法各有所长，也都存在致命的缺陷。从 1960 年代后期开始，研究者的主要精力逐渐转向对这三种传统法进行改进或整合，以扬长避短，适应程序设计语言和运行环境对资源回收的效率和实时性所提出的更高要求。

走向成熟

从 1970 年代开始，随着科学研究和应用实践的不断深入，人们逐渐意识到，一个理想的资源回收器不应在运行时导致应用程序的暂停，不应额外占用大量的内存空间和 中央处理器 资源，而三种传统的资源回收算法都无法满足这些要求。人们必须提出更新的算法或思路，以解决实践中碰到的诸多难题。当时，研究者的努力目标包括：

第一，提高资源回收的效率。使用标记－清除法的资源回收器在工作时要消耗相当多的 中央处理器 处理能力。早期的 历 运行环境收集内存垃圾的时间竟占到了系统总运行时间的 40% ！——资源回收效率的低下直接造就了 历 语言在执行速度方面的坏名声；直到今天，许多人还条件反射似地误以为所有 历 程序都奇慢无比。

第二，减少资源回收时的内存占用。这一问题主要出现在复制法中。尽管复制法在效率上获得了质的突破，但牺牲一半内存空间的代价仍然是巨大的。在计算机发展的早期，在内存价格以 千字节 计算的日子里，浪费客户的一半内存空间简直就是在变相敲诈或拦路打劫。

第三，寻找实时的资源回收算法。无论执行效率如何，三种传统的资源回收法在执行资源回收任务时都必须打断程序的当前工作。这种因资源回收而造成的延时是许多程序，特别是执行关键任务的程序没有办法容忍的。如何对传统算法进行改进，以便实现一种在后台悄悄执行，不影响——或至少看上去不影响——当前进程的实时资源回收器，这显然是一件更具挑战性的工作。

研究者们探寻未知领域的决心和研究工作的进展速度同样令人惊奇：在 1970 年代到 1980 年代的短短十几年中，一大批在实用系统中表现优异的新算法和新思路脱颖而出。正是因为有了这些日趋成熟的资源回收法，今天的我们才能在 Java 或 .NET 提供的运行环境中随心所欲地分配内存块，而不必担心空间释放时的风险。

标记－收整（ Mark-Compact ）法

标记－收整法是标记－清除法和复制法的有机结合。把标记－清除法在内存占用上的优点和复制法在执行效率上的特长综合起来，这是所有人都希望看到的结果。不过，两种资源回收法的整合并不像 1 加 1 等于 2 那样简单，我们必须引入一些全新的思路。 1970 年前后，斯蒂尔（ G. L. Steele） ， 钱尼（C. J. Cheney） 和 外斯（D. S. Wise） 等研究者陆续找到了正确的方向，标记－收整法的轮廓也逐渐清晰了起来：

在我们熟悉的餐厅里，这一次，资源回收机器人不再把餐厅分成两个南北区域了。需要执行资源回收任务时，机器人先执行标记－清除法的第一个步骤，为所有使用中的餐巾纸画好标记，然后，机器人命令所有就餐者带上有标记的餐巾纸向餐厅的南面集中，同时把没有标记的废旧餐巾纸扔向餐厅北面。这样一来，机器人只消站在餐厅北面，怀抱垃圾箱，迎接扑面而来的废旧餐巾纸就行了。

实验表明，标记－收整法的总体执行效率高于标记－清除法，又不像复制法那样需要牺牲一半的存储空间，这显然是一种非常理想的结果。在许多现代的资源回收器中，人们都使用了标记－收整法或其改进版本。 

增流回收（ Incremental Collecting ）法

对实时资源回收法的研究直接导致了增流回收法的诞生。

最初，人们关于实时资源回收的想法是这样的：为了进行实时的资源回收，可以设计一个多进程的运行环境，比如用一个进程执行资源回收工作，另一个进程执行程序代码。这样一来，资源回收工作看上去就仿佛是在后台悄悄完成的，不会打断程序代码的运行。

在收集餐巾纸的例子中，这一思路可以被理解为：资源回收机器人在人们用餐的同时，寻找废弃的餐巾纸并将它们扔到垃圾箱里。这个看似简单的思路会在设计和实现时碰上进程间冲突的难题。比如说，如果资源回收进程包括标记和清除两个工作阶段，那么，资源回收器在第一阶段中辛辛苦苦标记出的结果很可能被另一个进程中的内存操作代码修改得面目全非，以至于第二阶段的工作没有办法开展。

明斯基和 克努斯（D. E. Knuth） 对实时资源回收过程中的技术难点进行了早期的研究， 斯蒂尔（G. L. Steele） 于 1975 年发表了题为“多进程收整的资源回收（ Multiprocessing compactifying garbage collection ）”的论文，描述了一种被后人称为“明－克－斯法”（ Minsky-Knuth-Steele Algorithm）的实时资源回收法。笛杰斯拉（ E. W. Dijkstra） ， 蓝泊特（L. Lamport） ， 芬尼克乐（R. R. Fenichel） 和 尤切尔森 （J. C. Yochelson） 等人也相继在此领域做出了各自的贡献。 1978 年， 贝克尔（H. G. Baker） 发表了“阵列计算机上的实时串处理技术（ List Processing in Real Time on a Serial Computer ）”一文，系统阐述了多进程环境下用于资源回收的增流回收法。

增流回收法的基础仍是传统的标记－清除和复制法。增流回收法通过对进程间冲突的妥善处理，允许资源回收进程以分阶段的方式完成标记、清理或复制工作。详细分析各种增流回收法的内部机理是一件相当繁琐的事情，在这里，读者们需要了解的仅仅是： 贝克尔（H. G. Baker） 等人的努力已经将实时资源回收的梦想变成了现实，我们再也不用为资源回收打断程序的运行而烦恼了。 

迭代回收（ Generational Collecting ）法

和大多数软件开发技术一样，统计总能在技术发展的过程中起到强力催化剂的作用。 1980 年前后，善于在研究中使用统计分析知识的技术人员发现，大多数内存块的生存周期都比较短，资源回收器应当把更多的精力放在检查和清理新分配的内存块上。这个发现对于资源回收技术的价值可以用餐巾纸的例子概括如下：

如果资源回收机器人足够聪明，事先摸清了餐厅里每个人在用餐时使用餐巾纸的习惯——比如有些人喜欢在用餐前后各用掉一张餐巾纸，有的人喜欢自始至终攥着一张餐巾纸不放，有的人则每打一个喷嚏就用去一张餐巾纸——机器人就可以制定出更完善的餐巾纸回收计划，并总是在人们刚扔掉餐巾纸没多久就把垃圾捡走。这种基于行为统计调查结果的做法当然可以让餐厅的资源回收效率和整洁度得到更大的提高。

克努斯（D. E. Knuth） ， 科奈特（T. Knight） ， 苏斯曼（G. Sussman） 和 斯特尔曼（R. Stallman） 等人对内存垃圾的分类处理做了最早的研究。 1983 年， 利伯曼（H. Lieberman） 和 赫维特（C. Hewitt） 发表了题为“基于对象存续期的一种实时资源回收器（ A real-time garbage collector based on the lifetimes of objects ）”的论文。这篇著名的论文标志着迭代回收法的正式诞生。此后，在 贝克尔（H. G. Baker） ， 胡德森（R. L. Hudson） ， 默斯（J. E. B. Moss） 等人的共同努力下，迭代收集算法逐渐成为了资源回收领域里的主流技术。

迭代收集法通常将堆中的内存块按寿命分为两类，年老的和年轻的。资源回收器使用不同的收集法或收集策略，分别处理这两类内存块，并特别地把主要工作时间花在处理年轻的内存块上。迭代收集法使资源回收器在有限的资源条件下，可以更为有效地工作——这种效率上的提高在今天的 Java 虚拟机中得到了最好的证明。 

应用浪潮

历 是资源回收技术的第一个受益者，但显然不是最后一个。在 历 语言之后，许许多多传统的、现代的、后现代的语言已经把资源回收技术拉入了自己的怀抱。随便举几个例子吧：诞生于 1964 年的 Simula 语言， 1969 年的 Smalltalk 语言， 1970 年的 Prolog 语言， 1973 年的 ML 语言， 1975 年的 Scheme 语言， 1983 年的 Modula-3 语言， 1986 年的 Eiffel 语言， 1987 年的 Haskell 语言……它们都先后使用了自动资源回收技术。当然，每一种语言使用的资源回收算法可能不尽相同，大多数语言和运行环境甚至同时使用了多种资源回收算法。但无论怎样，这些实例都说明，资源回收技术从诞生的那一天起就不是一种曲高和寡的“学院派”技术。

对于我们熟悉的 C 和 C++ 语言，资源回收技术一样可以发挥巨大的功效。正如我们在学校中就已经知道的那样， C 和 C++ 语言本身并没有提供资源回收机制，但这并不妨碍我们在程序中使用具有资源回收功能的函数库或类库。例如，早在 1988 年， 伯翰姆（H. J. Boehm） 和 德默斯（A. J. Demers） 就成功地实现了一种使用俭省资源回收法（ Conservative GC Algorithmic ）的函数库（参见 http://www.hpl.hp.com/personal/Hans_Boehm/gc ）。我们可以在 C 语言或 C++ 语言中使用该函数库完成自动资源回收功能，必要时，甚至还可以让传统的 C/C++ 代码与使用自动资源回收功能的 C/C++ 代码在一个程序里协同工作。

1995 年诞生的 Java 语言在一夜之间将资源回收技术变成了软件开发领域里最为流行的技术之一。从某种角度说，我们很难分清究竟是 Java 从资源回收中受益，还是资源回收技术本身借 Java 的普及而扬名。值得注意的是，不同版本的 Java 虚拟机使用的资源回收机制并不完全相同， Java 虚拟机其实也经过了一个从简单到复杂的发展过程。在 Java 虚拟机的 1.4.1 版中，人们可以体验到的资源回收算法就包括迭代回收、复制回收、增流回收、标记－收整、平行复制（ Parallel Copying ）、平行清除（ Parallel Scavenging ）、并发（ Concurrent ）回收等许多种， Java 程序运行速度的不断提升在很大程度上应该归功于资源回收技术的发展与完善。

尽管历史上已经有许多包含资源回收技术的应用平台和操作系统出现，但 微软 .NET 却是第一种真正实用化的、包含了资源回收机制的通用语言运行环境。事实上， .NET 平台上的所有语言，包括 C# 、 Visual Basic .NET 、 Visual C++ .NET 、 J# 等等，都可以通过几乎完全相同的方式使用 .NET 平台提供的资源回收机制。我们似乎可以断言， .NET 是资源回收技术在应用领域里的一次重大变革，它使资源回收技术从一种单纯的技术变成了应用环境乃至操作系统中的一种内在文化。这种变革对未来软件开发技术的影响力也许要远远超过 .NET 平台本身的商业价值。

前途未卦

今天，致力于资源回收技术研究的人们仍在不懈努力，他们的研究方向包括分布式系统的资源回收、复杂事务环境下的资源回收、数据库等特定系统的资源回收等等。

但在程序员中间，仍有不少人对资源回收技术不屑一顾，他们宁愿相信自己逐行编写的 释放 或 清除 命令，也不愿把资源回收的重任交给那些在他们看来既蠢又笨的资源回收器。

虽然硬件水平不断提升，可能有人开始不再对内存和处理器资源耿耿于怀，但随着各种小型设备的普及，小型设备对资源利用效率极其严苛，因此，已经成形的资源回收器不一定能够胜任，也因此会大大促进资源回收方法的更进一步发展。

[原文：王咏刚，2003年12月]

——————————————————————
2011年黑传说注：上文已经不是原文，本人根据自己的学识进行了大幅度改写，以便用于更精准和易懂。