钝刀的家

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

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

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

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

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

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

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

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

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

增量收集（ Incremental Collecting ）算法
对实时垃圾收集算法的研究直接导致了增量收集算法的诞生。

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

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

M. L. Minsky 和 D. E. Knuth 对实时垃圾收集过程中的技术难点进行了早期的研究， G. L. Steele 于 1975 年发表了题为“多进程整理的垃圾收集（ Multiprocessing compactifying garbage collection ）”的论文，描述了一种被后人称为“ Minsky-Knuth-Steele 算法”的实时垃圾收集算法。 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 等人的努力已经将实时垃圾收集的梦想变成了现实，我们再也不用为垃圾收集打断程序的运行而烦恼了。