增量式地垃圾回收: 火车算法

时间：2010-10-09 来源：nileader

本文翻译自 Thomas Wurthinger论文《Incremental Garbage Collection: The Train Algorithm 》概述

在传统编程语言中, 程序员负责回收无用对象(没有引用指向这个对象)占据的内存空间.这导致了两个常见的程序错误: 首先, 对一个已经被回收的对象的再次操作将会导致内存异常; 其次, 如果在一个对象被回收前已经没有引用指向它时, 那么, 知道程序终止前, 它将一直占据内存空间. (这样的错误对于一个生命周期短的程序可能影响不大), 但是对于一个运行时候长的应用程序而言, 这样的漏洞将会导致消耗越来越多的内存空间. 显然, 最终将会导致所有内存都被分配完而使程序被迫终止. “垃圾” (garbage)通常指的是那些在程序中不会再被用到(不可及)的对象——因此可以安全的释放他们占据的内存空间. 为了使程序员从回收无用对象所占内存空间的工作中解脱出来, 研究出了一些自动监测无用对象并将他们释放的算法.——这个算法就是垃圾收集.

在一些诸如Java、C#等的现代编程语言中, 自动化内存管理被广泛地使用. 使用这个方法回收无用对象的最大不足是非增量式的(垃圾回收)算法需要在垃圾回收过程中停掉主程序的运行. (这样一来,)当对内存的需求增大的过程中, 程序被停掉的时间也将变得越来越长.这就是为什么增量式的垃圾回收变得越来越重要. 一些实时应用常常需要在几毫秒时间内作出响应, 一些与用户交互的应用也仅仅允许极短时间的停顿.(这个时间通常是一秒的小部分). 那么垃圾回收将不可能使用在一些在线角色扮演的游戏中, 因为没有玩家能够接受每一次垃圾回收带来的延时.

另外, 将一次垃圾回收分成一个个微小的步骤还有其它好处. 很多时候, 对象可能会分布在一些不同的系统中, 如果采用非增量式的垃圾回收, 那么, 这将导致在进行垃圾回收的时候, 所有系统都将停止运行. 在这种情况下, 火车算法往往可以解决问题. 基本思想接下来将会描述一些常见的垃圾回收算法背后的主要思想, 以及火车算法. 垃圾回收基本上包含两个主要任务: 第一: 检测. 无论如何, 垃圾收集器需要区分出”活”的对象和”垃圾”. 算法通常使用另一种方法而不是去搜寻所有无用对象: “活”的对象都会被标记并被保留下来. 来看对象空间外部指向一个对象的引用称为”根引用”. 所有被这样的引用指向的对象会被标记为”活”对象. 当然, 所有被这些”活”对象引用的对象同样被标记为”活”的. 当所有被引用的对象都已经被标记,那么算法结束. 此时可以保证的一点是所有的无用对象都没有标记并且无法被程序访问了.

第二:释放. 有两个可行的方法来删除”垃圾”.

- 通过复制这些活着的对象到一个安全的地方来保留他们, 并将被无用对象占据的内存块释放.

- 释放所有没有被标记为活着的对象空间.

在上图中, 假设监测到了所有活着的对象. 首先是对象G, 根引用直接指向这两个对象, 当然要标记. 同样, 由于通过对象A能够(让程序操作), 所以对象B也被保留下来了. 值得一提的是, 图中对象C, D和E的引用构成了一个圈(自循环)的话, 那么这些对象也应该被看作是无用对象(垃圾).

通过拷贝那些存在引用的对象来保留它们的做法, 一眼看下去, 似乎是相当耗费性能的. 但是这个技术也有它的优点: 每次垃圾回收后, 内存是连续的, 因此, 各个对象都是紧密排列的, 于是程序能够执行得更快.

图2显示了一部分空闲的内存空间, 保留下了所有被引用的对象. 所谓”from space”指的是在垃圾回收以前, 当前程序正在使用的内存空间. 而”to space” 则是表示了垃圾回收后, 保留下来的内存空间.

当垃圾回收正在进行的过程中, 被中断很长一段时间是不允许的, 其中(垃圾对象的)监测是一个很大的问题. 几乎很难找到这样一个能将这个过程分成一个个小步骤的算法——一般来说这就是所谓的增量式垃圾回收——火车算法提供了这样一个解决方案.