钝刀的家

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://3705.blogbus.com/logs/3786086.html

引用计数（ Reference Counting ）算法
1960 年以前，人们为胚胎中的 Lisp 语言设计垃圾收集机制时，第一个想到的算法是引用计数算法。拿餐巾纸的例子来说，这种算法的原理大致可以描述为：

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

引用计数算法的优点和缺陷同样明显。这一算法在执行垃圾收集任务时速度较快，但算法对程序中每一次内存分配和指针操作提出了额外的要求（增加或减少内存块的引用计数）。更重要的是，引用计数算法无法正确释放循环引用的内存块，对此， D. Hillis 有一段风趣而精辟的论述：

一天，一个学生走到 Moon 面前说：“我知道如何设计一个更好的垃圾收集器了。我们必须记录指向每个结点的指针数目。” Moon 耐心地给这位学生讲了下面这个故事：“一天，一个学生走到 Moon 面前说：‘我知道如何设计一个更好的垃圾收集器了……’”

D. Hillis 的故事和我们小时候常说的“从前有座山，山上有个庙，庙里有个老和尚”的故事有异曲同工之妙。这说明，单是使用引用计数算法还不足以解决垃圾收集中的所有问题。正因为如此，引用计数算法也常常被研究者们排除在狭义的垃圾收集算法之外。当然，作为一种最简单、最直观的解决方案，引用计数算法本身具有其不可替代的优越性。 1980 年代前后， D. P. Friedman ， D. S. Wise ， H. G. Baker 等人对引用计数算法进行了数次改进，这些改进使得引用计数算法及其变种（如延迟计数算法等）在简单的环境下，或是在一些综合了多种算法的现代垃圾收集系统中仍然可以一展身手。

标记－清除（ Mark-Sweep ）算法
第一种实用和完善的垃圾收集算法是 J. McCarthy 等人在 1960 年提出并成功地应用于 Lisp 语言的标记－清除算法。仍以餐巾纸为例，标记－清除算法的执行过程是这样的：

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

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

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