垃圾回收的算法与实现[试读]

本章中将为各位说明GC 中的基本概念。 1.1 对象/ 头/ 域 对象这个词，在不同的使用场合其意思各不相同。比如，在面向对象编程中，它指“具有属性和行为的事物”，然而在GC 的世界中，对象表示的是“通过应用程序利用的数据的集合”。 对象配置在内存空间里。GC 根据情况将配置好的对象进行移动或销毁操作。因此，对象是GC 的基本单位。本书中的所有“对象”都表示这个含义。 一般来说，对象由头（header）和域（field）构成。我们下面将对其逐一说明。 1.1.1 头 我们将对象中保存对象本身信息的部分称为“头”。头主要含有以下信息。 • 对象的大小 ... 查看全部[ 1.1 对象/ 头/ 域 ]

通过GC，对象会被销毁或保留。这时候起到关键作用的就是指针。因为GC 是根据对象的指针指向去搜寻其他对象的。另一方面，GC 对非指针不进行任何操作。 在这里有两点需要我们注意。 首先，要注意语言处理程序是否能判别指针和非指针。要判别指针和非指针需要花费一定的功夫，关于这一点我们会在第6 章详细说明。除第6 章之外，在“算法篇”的各个章节中，我们都以GC 可判别对象各域中的值是指针还是非指针为前提进行解说。 另一点是指针要指向对象的哪个部分。指针如果指向对象首地址以外的部分，GC 就会变得非常复杂。在大多数语言处理程序中，指针都默认指向对象的首地址。因为存在这个制约条件，不仅是... 查看全部[ 1.2 指针 ]

mutator 是Edsger Dijkstra [15] 琢磨出来的词，有“改变某物”的意思。说到要改变什么，那就是GC 对象间的引用关系。不过光这么说可能大家还是不能理解，其实用一句话概括的话，它的实体就是“应用程序”。这样说就容易理解了吧。GC 就是在这个mutator 内部精神饱满地工作着。 mutator 实际进行的操作有以下2 种。 • 生成对象 • 更新指针 mutator 在进行这些操作时，会同时为应用程序的用户进行一些处理（数值计算、浏览网页、编辑文章等）。随着这些处理的逐步推进，对象间的引用关系也会“改变”。伴随这些变化会产生垃圾，而负责回收这些垃圾... 查看全部[ 1.3 mutator ]

堆指的是用于动态（也就是执行程序时）存放对象的内存空间。当mutator 申请存放对象时，所需的内存空间就会从这个堆中被分配给mutator。 GC 是管理堆中已分配对象的机制。在开始执行mutator 前，GC 要分配用于堆的内存空间。一旦开始执行mutator，程序就会按照mutator 的要求在堆中存放对象。等到堆被对象占满后，GC 就会启动，从而分配可用空间。如果不能分配足够的可用空间，一般情况下我们就要扩大堆。 然而，为了让读者能更容易理解，在“算法篇”中我们把堆的大小固定为常量HEAP_SIZE，不会进行扩大。此外，我们把$heap_start 定为指向堆首地址的指针，... 查看全部[ 1.4 堆 ]

我们将分配到内存空间中的对象中那些能通过mutator 引用的对象称为“活动对象”。反过来，把分配到堆中那些不能通过程序引用的对象称为“非活动对象”。也就是说，不能通过程序引用的对象已经没有人搭理了，所以死掉了。死掉的对象（即非活动对象）我们就称为“垃圾”。 这里需要大家注意的是：死了的对象不可能活过来。因为就算mutator 想要重新引用（复活）已经死掉的对象，我们也没法通过mutator 找到它了。 因此，GC 会保留活动对象，销毁非活动对象。当销毁非活动对象时，其原本占据的内存空间会得到解放，供下一个要分配的新对象使用。 图1.4　活动对象和非活动对象... 查看全部[ 1.5 活动对象/ 非活动对象 ]

分配（allocation）指的是在内存空间中分配对象。当mutator 需要新对象时，就会向分配器（allocator）申请一个大小合适的空间。分配器则在堆的可用空间中找寻满足要求的空间，返回给mutator。 像Java 和Ruby 这些配备了GC 的编程语言在生成实例时，会在内部进行分配。另一方面，因为C 语言和C++ 没有配备GC，所以程序员要使用malloc() 函数和new 运算符等进行手动分配。 然而，当堆被所有活动对象占满时，就算运行GC 也无法分配可用空间。这时候我们有以下两种选择。 1. 销毁至今为止的所有计算结果，输出错误信息 2. 扩大堆，分配可... 查看全部[ 1.6 分配 ]

分块（chunk）在GC 的世界里指的是为利用对象而事先准备出来的空间。 初始状态下，堆被一个大的分块所占据。 然后，程序会根据mutator 的要求把这个分块分割成合适的大小，作为（活动）对象使用。活动对象不久后会转化为垃圾被回收。此时，这部分被回收的内存空间再次成为分块，为下次被利用做准备。也就是说，内存里的各个区块都重复着分块→活动对象→垃圾（非活动对象）→分块→ …… 这样的过程。... 查看全部[ 1.7 分块 ]

根（root）这个词的意思是“根基”“根底”。在GC 的世界里，根是指向对象的指针的“起点”部分。 这些都是能通过mutator 直接引用的空间。举个例子，请看下面的伪代码。 $obj = Object.new $obj.field1 = Object.new 在这里$obj 是全局变量。首先，我们在第1 行分配一个对象（对象A），然后把$obj 代入指向这个对象的指针。在第2 行我们也分配一个对象（对象B），然后把$obj.field1 代入指向这个对象的指针。在执行完第2 行后，全局变量空间及堆如图1.5 所示。 图1.5　全局变量空间及堆的示意图 在这... 查看全部[ 1.8 根 ]

评价GC 算法的性能时，我们采用以下4 个标准。 • 吞吐量 • 最大暂停时间 • 堆使用效率 • 访问的局部性 下面我们逐一进行说明。 1.9.1 吞吐量 从一般意义上来讲，吞吐量（throughput）指的是“在单位时间内的处理能力”，这点在GC 的世界中也不例外。 请参照图1.7 的示例。 图1.7　mutator和GC 的执行示意图 在mutator 整个执行过程中，GC 一共启动了3 次，我们把花费的时间分别设为A、B、C。也就是说，GC 总共花费的时间为（A ＋ B ＋ C）。另一方面，我们前面提到过，以GC 为对象的堆大... 查看全部[ 1.9 评价标准 ]

世界上首个值得纪念的GC 算法是GC 标记- 清除算法（Mark Sweep GC）[1]。自其问世以来，一直到半个世纪后的今天，它依然是各种处理程序所用的伟大的算法。 2.1 什么是GC标记- 清除算法 就如它的字面意思一样，GC 标记- 清除算法由标记阶段和清除阶段构成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段。通过这两个阶段，就可以令不能利用的内存空间重新得到利用。首先，标记-清除算法的伪代码如代码清单2.1 所示。 代码清单2.1：mark_sweep()函数 mark_sweep(){ mark... 查看全部[ 2.1 什么是GC标记- 清除算法 ]