垃圾回收的算法与实现——2.1 什么是GC标记- 清除算法

世界上首个值得纪念的GC 算法是GC 标记- 清除算法（Mark Sweep GC）[1]。自其问世以来，一直到半个世纪后的今天，它依然是各种处理程序所用的伟大的算法。 2.1 什么是GC标记- 清除算法 就如它的字面意思一样，GC 标记- 清除算法由标记阶段和清除阶段构成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象回收的阶段。通过这两个阶段，就可以令不能利用的内存空间重新得到利用。首先，标记-清除算法的伪代码如代码清单2.1 所示。 代码清单2.1：mark_sweep()函数 mark_sweep(){ mark_phase() sweep_phase() } 确实分成了标记阶段和清除阶段。接下来我们就对各个阶段进行说明。 在之后的说明中，我们都以对图2.1 中的堆执行GC 为前提。 图2.1　执行GC 前堆的状态 2.1.1 标记阶段 我们用mark_phase() 函数来进行标记阶段的处理。 代码清单2.2：mark_phase()函数 mark_phase(){ for(r : $roots) mark(*r) } 非常简单明了吧。在标记阶段中，collector 会为堆里的所有活动对象打上标记。为此，我们首先要标记通过根直接引用的对象。这里的“对象”就是我们在1.8 节中讲到的“确实活动着的对象”。首先我们标记这样的对象，然后递归地标记通过指针数组能访问到的对象。这样就能把所有活动对象都标记上了。 第3 行出现的mark() 函数的定义如代码清单2.3 所示。 代码清单2.3：mark()函数 mark(obj){ if(obj.mark == FALSE) obj.mark = TRUE for(child : children(obj)) mark(*child) } 在第2 行中，检查作为实参传递的obj 是否已被标记。在引用中包含了循环等的情况下，即使对已被标记的对象，有时程序也会调用mark() 函数。出现类似这种情况的时候，我们就要避免重复进行标记处理。 如果标记未完成，则程序会在对象的头部进行置位操作。这个位要分配在对象的头之中，并且能用obj.mark 访问。意思是若obj.mark 为真，则表示对象已标记；若obj.mark 为假，则对象没有被标记。 图2.2　设置标志位的处理 标记完所有活动对象后，标记阶段就结束了。标记阶段结束时的堆如图2.3 所示。 图2.3　标记阶段结束后的堆状态 在标记阶段中，程序会标记所有活动对象。毫无疑问，标记所花费的时间是与“活动对象的总数”成正比的。 以上是关于标记阶段的说明。用一句话概括，标记阶段就是“遍历对象并标记”的处理过程。这个“遍历对象”的处理过程在GC 中是一个非常重要的概念，在之后还会多次出现，请务必记牢。 专栏 深度优先搜索与广度优先搜索 我们在搜索对象并进行标记时使用的是深度优先搜索（depth -first search）。这是尽可能从深度上搜索树形结构的方法。 图2.4　深度优先搜索 另一方面，还有广度优先搜索（breadth -first search）方法。这是尽可能从广度上搜索树形结构的方法。 图2.5　广度优先搜索 顺便说一下，图2.4 和图2.5 中各对象旁边的号码表示搜索顺序。 GC 会搜索所有对象。不管使用什么搜索方法，搜索相关的步骤数（调查的对象数量）都不会有差别。 另一方面，比较一下内存使用量（已存储的对象数量）就可以知道，深度优先搜索比广度优先搜索更能压低内存使用量。因此我们在标记阶段经常用到深度优先搜索。 2.1.2 清除阶段 在清除阶段中，collector 会遍历整个堆，回收没有打上标记的对象（即垃圾），使其能再次得到利用。 代码清单2.4：sweep_phase()函数 sweep_phase(){ sweeping = $heap_start while(sweeping < $heap_end) if(sweeping.mark == TRUE) sweeping.mark = FALSE else sweeping.next = $free_list $free_list = sweeping sweeping += sweeping.size } 在此出现了叫作size 的域，这是存储对象大小（字节数）的域。跟mark 域一样，我们事先在各对象的头中定义它们。 在清除阶段，我们使用变量sweeping 遍历堆，具体来说就是从堆首地址$heap_start开始，按顺序一个个遍历对象的标志位。 设置了标志位，就说明这个对象是活动对象。活动对象必然是不能回收的。在第5 行我们取消标志位，准备下一次的GC。 我们必须把非活动对象回收再利用。回收对象就是把对象作为分块，连接到被称为“空闲链表”的单向链表。在之后进行分配时只要遍历这个空闲链表，就可以找到分块了。 我们在sweep_phase() 函数的第7 行、第8 行进行这项操作。 在第7 行新出现了叫作next 的域。我们只在生成空闲链表以及从这个空闲链表中取出分块时才会使用到它。没有必要为各个对象特别准备域，从对象已有的域之中分出来一个就够了。在本章中，next 表示对象（或者分块）最初的域，即field1。也就是说，给field1 这个域起个别名叫next。这跟C 语言中的联合体（union）的概念相同。 这里要注意的是在第7 行重写sweeping 的域这一步。读者可能会有疑问：“GC 重写了对象的域也没事吗？”因为我们知道这个对象已经死了，所以事实上没有任何问题。 图2.6　清除阶段结束后的堆状态