GC引用计数算法

Published on 2017 - 05 - 12

GC 原本是一种“释放怎么都无法被引用的对象的机制”。那么人们自然而然地就会想到,可以让所有对象事先记录下“有多少程序引用自己”。让各对象知道自己的“人气指数”,从而让没有人气的对象自己消失,这就是引用计数法(Reference Counting),它是 George E. Collins 于 1960 年钻研出来的。

引用计数的算法

引用计数法中引入了一个概念,那就是“计数器”。计数器表示的是对象的人气指数,也就是有多少程序引用了这个对象(被引用数)。计数器是无符号的整数,用于计数器的位数根据算法和实现而有所不同。引用计数法中的对象如图 1 所示。


[图 1 引用计数法中的对象]

那么,让我们来看看在引用计数法中是怎样进行内存管理的吧。

计数器值的增减

在 GC 标记 - 清除算法等其他 GC 算法中,没有分块时 mutator 会调用下面这样的函数,启动 GC 分配空闲的内存空间。

代码清单 1:garbage_collect() 函数

1 garbage_collect(){
2   ....
3 }

然而在引用计数法中并没有 mutator 明确启动 GC 的语句。引用计数法与 mutator 的执行密切相关,它在 mutator 的处理过程中通过增减计数器的值来进行内存管理。在两种情况下计数器的值会发生增减,这涉及了 new_obj() 函数和 update_ptr() 函数。

new_obj() 函数

代码清单 2:new_obj() 函数

1 new_obj(size){
2   obj = pickup_chunk(size, $free_list)
3 
4   if(obj == NULL)
5     allocation_fail()
6   else
7     obj.ref_cnt = 1
8     return obj
9 }

与 GC 标记 - 清除算法相同,mutator 在生成新对象的时候会调用 new_obj() 函数。

在这里,pickup_chunk() 函数的用法也大致与在 GC 标记 - 清除算法中的用法相同。不过这次当 pickup_chunk() 函数返回 NULL 时,分配就失败了。在引用计数法中,除了连接到空闲链表的对象,其他所有对象都是活动对象。也就是说,在 pickup_chunk() 函数返回 NULL 那一刻,堆中就没有合适大小的分块了,分配就无法进行了。

当通过 pickup_chunk() 函数返回合适大小的对象时,在第 7 行把计数器的值定为 1。很明显,这里新生成了对象,且对象被某处引用了。另外,域 ref_cnt 代表对象 obj 的计数器。

update_ptr() 函数

update_ptr() 函数用于更新指针 ptr,使其指向对象 obj,同时进行计数器值的增减。

代码清单 3:update_ptr() 函数

1 update_ptr(ptr, obj){
2   inc_ref_cnt(obj)
3   dec_ref_cnt(*ptr)
4   *ptr = obj
5 }

虽然在 mutator 更新指针时程序会执行此函数,但事实上进行指针更新的只有第 4 行的 *ptr = obj 部分,第 2 行和第 3 行是进行内存管理的代码。程序具体进行的是以下 2 项操作。

  1. 对指针 ptr 新引用的对象(obj)的计数器进行增量操作
  2. 对指针 ptr 之前引用的对象(*ptr)的计数器进行减量操作

首先我们要介绍的是执行计数器增量操作的 inc_ref_cnt() 函数。

代码清单 4:inc_ref_cnt() 函数

1 inc_ref_cnt(obj){
2   obj.ref_cnt++
3 }

inc_ref_cnt() 函数是一个简单的函数,它只对新引用的对象 obj 的计数器进行增量操作。下面我们再来看看进行计数器减量操作的 dec_ref_cnt() 函数。

代码清单 5:dec_ref_cnt() 函数

1 dec_ref_cnt(obj){
2   obj.ref_cnt--
3   if(obj.ref_cnt == 0)
4     for(child : children(obj))
5       dec_ref_cnt(*child)
6     reclaim(obj)
7 }

首先对更新指针之前引用的对象 *ptr 的计数器进行减量操作。减量操作后,计数器的值为 0 的对象变成了“垃圾”。因此,这个对象的指针会全部被删除。换言之,程序需要对 *ptr 的子对象的计数器进行减量操作。在第 5 行递归调用 dec_ref_cnt() 函数就是为了这个。然后,通过 reclaim() 函数将 obj 连接到空闲链表。reclaim() 函数会在本文中多次出现,请牢记。

那么,看到这里大家会不会心生疑问呢?为什么要先调用 inc_ref_cnt() 函数,后调用 dec_ref_cnt() 函数呢?从引用计数算法的角度来考虑,先调用 dec_ref_cnt() 函数,后调用 inc_ref_cnt() 函数才合适吧。答案就是“为了处理 *ptr和 obj 是同一对象时的情况”。如果按照先 dec_ref_cnt() 后 inc_ref_cnt() 函数的顺序调用,*ptr 和 obj 又是同一对象的话,执行 dec_ref_cnt(*ptr)*ptr 的计数器的值就有可能变为 0 而被回收。这样一来,下面再想执行 inc_ref_cnt(obj) 时 obj 早就被回收了,可能会引发重大的 BUG。因此我们要通过先对 obj 的计数器进行增量操作来回避这种 BUG。

最后结合图片来看一下 update_ptr() 函数执行时的情况。请看图 2(a)。初始状态下从根引用 A 和 C,从 A 引用 B。A 持有唯一指向 B 的指针,假设现在将该指针更新到了 C,请看图 2(b)。


[图 2 update_ptr() 函数执行时的情况]

通过以上的更新,B 的计数器值变成了 0,因此 B 被回收了。且 B 连接上了空闲链表,能够再被利用了。又因为新形成了由 A 指向 C 的指针,所以 C 的计数器的值增量为 2。

在变更数组元素等的时候会进行指针的更新。通过更新指针,可能会产生没有被任何程序引用的垃圾对象。引用计数法中会监督在更新指针的时候是否有产生垃圾,从而在产生垃圾时将其立刻回收。也就是说,这意味着在分配时没有分块的情况下,堆中所有的对象都为活动对象,这时没法新分配对象。另一方面,GC 标记 - 清除算法即使产生了垃圾也不会将其马上回收,只会在没有分块的时候将垃圾一并回收。像这样,可以说将内存管理和 mutator 同时运行正是引用计数法的一大特征。

以上就是对引用计数的算法的说明。

优点

可即刻回收垃圾

在引用计数法中,每个对象始终都知道自己的被引用数(就是计数器的值)。当被引用数的值为 0 时,对象马上就会把自己作为空闲空间连接到空闲链表。也就是说,各个对象在变成垃圾的同时就会立刻被回收。要说这有什么意义,那就是内存空间不会被垃圾占领。垃圾全部都已连接到空闲链表,能作为分块再被利用。

另一方面,在其他的 GC 算法中,即使对象变成了垃圾,程序也无法立刻判别。只有当分块用尽后 GC 开始执行时,才能知道哪个对象是垃圾,哪个对象不是垃圾。也就是说,直到 GC 执行之前,都会有一部分内存空间被垃圾占用。

最大暂停时间短

在引用计数法中,只有当通过 mutator 更新指针时程序才会执行垃圾回收。也就是说,每次通过执行 mutator 生成垃圾时这部分垃圾都会被回收,因而大幅度地削减了 mutator 的最大暂停时间。

没有必要沿指针查找

引用计数法和 GC 标记 - 清除算法不一样,没必要由根沿指针查找。当我们想减少沿指针查找的次数时,它就派上用场了。

打个比方,在分布式环境中,如果要沿各个计算节点之间的指针进行查找,成本就会增大,因此需要极力控制沿指针查找的次数。

所以,有一种做法是在各个计算节点内回收垃圾时使用 GC 标记 - 清除算法,在考虑到节点间的引用关系时则采用引用计数法。

缺点

计数器值的增减处理繁重

虽然依据执行的 mutator 的动作不同而略有差距,我们不能一概而论,不过在大多数情况下指针都会频繁地更新。特别是有根的指针,会以近乎令人目眩的势头飞速地进行更新。这是因为根可以通过 mutator 直接被引用。在引用计数法中,每当指针更新时,计数器的值都会随之更新,因此值的增减处理必然会变得繁重。

计数器需要占用很多位

用于引用计数的计数器最大必须能数完堆中所有对象的引用数。打个比方,假如我们用的是 32 位机器,那么就有可能要让 2 的 32 次方个对象同时引用一个对象。考虑到这种情况,就有必要确保各对象的计数器有 32 位大小。也就是说,对于所有对象,必须留有 32 位的空间。这就害得内存空间的使用效率大大降低了。打比方说,假如对象只有 2 个域,那么其计 数器就占了它整体的 1/3。

实现烦琐复杂

引用计数的算法本身很简单,但事实上实现起来却不容易。

进行指针更新操作的 update_ptr() 函数是在 mutator 这边调用的。打个比方,我们需要把以往写成 *ptr=obj 的地方都重写成 update_ptr(ptr,obj)。因为调用 update_ptr() 函数的地方非常多,所以重写过程中很容易出现遗漏。如果漏掉了某处,内存管理就无法正确进行,就会产生 BUG。

循环引用无法回收

代码清单 6:循环垃圾的生成

 1 class Person{                          # 定义Person 
 2   string name
 3   Person lover
 4 }
 5 
 6 taro = new Person(" 太郎")             # 生成Person 类的实例太郎
 7 hanako = new Person(" 花子")           # 生成Person 类的实例花子
 8 taro.lover = hanako                    # 太郎喜欢花子
 9 hanako.lover = taro                    # 花子喜欢太郎
10 taro = null                            # 将taro 转换为null
11 hanako = null                          # 将hanako 转换为null

上述伪代码表示的是某对情侣。在执行这段伪代码后,对象的情况如图 3 所示。


[图 3 循环引用对象]

像上述这样,因为两个对象互相引用,所以各对象的计数器的值都是 1。但是这些对象组并没有被其他任何对象引用。因此想一并回收这两个对象都不行,只要它们的计数器值都是 1,就无法回收。像这样在两个及两个以上的对象互相循环引用形成对象组的情况下,即使这些对象组都成了垃圾,程序也无法将它们回收。

我们说了很多引用计数法的缺点,像“处理繁重”“内存使用效率低下”等。那么引用计数法是不是一个“完全没法用”的算法呢?不,绝对不是。事实上,很多处理系统和应用都在使用引用计数法。

要说为什么,那是因为引用计数法只要稍加改良,就会变得非常具有实用性了。之后我们将对如何改良引用计数法进行解说。

延迟引用计数法

什么是延迟引用计数法

在讲引用计数法的缺点时,我们提到了其中一项是“计数器值的增减处理繁重”。下面就对改善此缺点的方法进行说明,即延迟引用计数法(Deferred Reference Counting)。这个方法是 L. Peter Deutsch 和 Daniel G. Bobrow [8] 研究出来的。

如前面所述,计数器值增减处理繁重的原因之一是从根的引用变化频繁。

因此,我们就让从根引用的指针的变化不反映在计数器上。打个比方,我们把重写全局变量指针的 update_ptr($ptr,obj) 改写成 *$ptr = obj。

如上所述,这样一来即使频繁重写堆中对象的引用关系,对象的计数器值也不会有所变化,因而大大改善了“计数器值的增减处理繁重”这一缺点。

然而,这样内存管理还是不能顺利进行。因为引用没有反映到计数器上,所以各个对象的计数器没有正确表示出对象本身的被引用数(即人气)。因此,有可能发生对象仍在活动,但却被错当成垃圾回收的情况。


[图 4 实际上仍在活动,但计数器值却为 0 的对象]

于是,我们在延迟引用计数法中使用 ZCT(Zero Count Table)。ZCT 是一个表,它会事先记录下计数器值在 dec_ref_cnt() 函数的作用下变为 0 的对象。ZCT 的示意图如图 5 所示。

[图 5 ZCT]

因为计数器值为 0 的对象不一定都是垃圾,所以暂时先将这些对象保留。由图 5 也能看出,我们必须修正 dec_ref_cnt() 函数,使其适应延迟引用计数法。

dec_ref_cnt() 函数

关于在延迟引用计数法中用到的 dec_ref_cnt() 函数,其定义如代码清单 7 所示。

代码清单 7:延迟引用计数法中的 dec_ref_cnt() 函数

1 dec_ref_cnt(obj){
2   obj.ref_cnt--
3   if(obj.ref_cnt == 0)
4     if(is_full($zct) == TRUE)
5       scan_zct()
6     push($zct, obj)
7 }

当 obj 的计数器值为 0(也就是说 obj 可能是垃圾)时,在第 6 行把 obj 添加到 $zct。不过,如果 $zct 爆满,那么首先就要通过 scan_zct() 函数来减少 $zct 中的对象(第 4 行、第 5 行)。

new_obj() 函数

我们也要稍微修正一下 new_obj() 函数。当无法分配大小合适的分块时,执行 scan_zct() 函数。

代码清单 8:延迟引用计数法中的 new_obj() 函数

 1 new_obj(size){
 2   obj = pickup_chunk(size, $free_list)
 3 
 4   if(obj == NULL)
 5     scan_zct()
 6     obj = pickup_chunk(size, $free_list)
 7     if(obj == NULL)
 8       allocation_fail()
 9 
10   obj.ref_cnt = 1
11   return obj
12 }

如果第一次分配没有顺利进行,就意味着空闲链表中没有了大小合适的分块。此时程序要搜索一遍 $zct,以再次分配分块。如果这样还不行,分配就失败了。

分配顺利进行之后的流程通常与引用计数法完全一样。

scan_zct() 函数

scan_zct() 函数的伪代码如下所示。

代码清单 9:scan_zct() 函数

 1 scan_zct(){
 2   for(r : $roots)
 3     (*r).ref_cnt++
 4 
 5   for(obj : $zct)
 6     if(obj.ref_cnt == 0)
 7       remove($zct, obj)
 8       delete(obj)
 9 
10   for(r : $roots)
11     (*r).ref_cnt--
12 }

在第 2 行和第 3 行,程序把所有通过根直接引用的对象的计数器都进行增量。这样才算把根引用反映到了计数器的值上。

接下来调查所有与 $zct 相连的对象,如果存在计数器值为 0 的对象,则将此对象从 $zct 中删除,并执行以下 2 项操作。

  1. 对子对象的计数器进行减量操作
  2. 回收

负责这 2 项操作的 delete() 函数的定义如代码清单 10 所示。

代码清单 10:delete() 函数

1 delete(obj){
2   for(child : children(obj)
3     (*child).ref_cnt--
4     if((*child).ref_cnt == 0)
5       delete(*child)
6 
7     reclaim(obj)
8 }

对 obj 的子对象的计数器进行减量操作,对计数器值变成 0 的对象执行 delete() 函数,最后回收 obj。

最后把所有根引用的对象的计数器都进行减量操作。

优点

在延迟引用计数法中,程序延迟了根引用的计数,将垃圾一并回收。通过延迟,减轻了因根引用频繁发生变化而导致的计数器增减所带来的额外负担。

缺点

为了延迟计数器值的增减,垃圾不能马上得到回收,这样一来垃圾就会压迫堆,我们也就失去了引用计数法的一大优点 —— 可即刻回收垃圾。

另外,scan_zct() 函数导致最大暂停时间延长了。执行 scan_zct() 函数所花费的时间与 $zct 的大小成正比。$zct 越大,要搜索的对象就越多,妨碍 mutator 运作的时间也就越长。要想缩减因 scan_zct() 函数而导致的暂停时间,就要缩小 $zct。但是这样一来调用 scan_zct() 函数的频率就增加了,也压低了吞吐量。很明显这样就本末倒置了。

Sticky 引用计数法

什么是 Sticky 引用计数法

在引用计数法中,我们有必要花功夫来研究一件事,那就是要为计数器设置多大的位宽。假设为了反映所有引用,计数器需要 1 个字(32 位机器就是 32 位)的空间。但是这样会大量消耗内存空间。打个比方,2 个字的对象就要附加 1 个字的计数器。也就是说,计数器害得对象所占空间增大了 1.5 倍。


[图 6 对象拥有两个 1 个字的域以及一个 1 个字的计数器]

对此我们有个方法,那就是用来减少计数器位宽的“Sticky 引用计数法”。举个例子,我们假设用于计数器的位数为 5 位,那么这种计数器最多只能数到 2 的 5 次方减 1,也就是 31 个引用数。如果此对象被大于 31 个对象引用,那么计数器就会溢出。这跟车辆速度计的指针爆表是一个状况。

针对计数器溢出(也就是爆表的对象),需要暂停对计数器的管理。对付这种对象,我们主要有两种方法。

什么都不做

对于计数器溢出的对象,我们可以这样处理:不再增减计数器的值,就把它放着,什么也不做。不过这样一来,即使这个对象成了垃圾(即被引用数为 0),也不能将其回收。也就是说,白白浪费了内存空间。

然而事实上有很多研究表明,很多对象一生成马上就死了。也就是说,在很多情况下,计数器的值会在 0 到 1 的范围内变化,鲜少出现 5 位计数器溢出这样的情况。

此外,因为计数器溢出的对象在执行中的程序里占有非常重要的地位,所以可想而知,其将来成为垃圾的可能性也很低。也就是说,不增减计数器的值,就把它那么放着也不会有什么大问题。

考虑到以上事项,对于计数器溢出的对象,什么也不做也不失为一个可用的方法。

使用 GC 标记 - 清除算法进行管理

另一个方法是,在适当时机用 GC 标记 - 清除算法来充当引用计数法的后援。但是我们在这里用到的 GC 标记 - 清除算法和以往的有所不同。

代码清单 11:作为备用的GC 标记 - 清除算法

1 mark_sweep_for_counter_overflow(){
2   reset_all_ref_cnt()
3   mark_phase()
4   sweep_phase()
5 }

首先,在第 2 行把所有对象的计数器值都设为 0。下面,我们进入标记阶段和清除阶段。

代码清单 12:标记阶段

 1 mark_phase(){
 2   for(r : $roots)
 3     push(*r, $mark_stack)
 4 
 5   while(is_empty($mark_stack) == FALSE)
 6     obj = pop($mark_stack)
 7     obj.ref_cnt++
 8     if(obj.ref_cnt == 1)
 9       for(child : children(obj))
10         push(*child, $mark_stack)
11 }

在标记阶段,首先把由根直接引用的对象堆到标记栈里,然后按顺序从标记栈取出对象,对计数器进行增量操作。不过,这里必须只把各个对象及其子对象堆进标记栈一次。在第 8 行会检查各个对象是不是只堆进去了一次。(为了防止引用计数溢出)一旦栈为空,则标记阶段结束。

代码清单 13:清除阶段

1 sweep_phase(){
2   sweeping = $heap_top
3   while(sweeping < $heap_end)
4    if(sweeping.ref_cnt == 0)
5      reclaim(sweeping)
6    sweeping += sweeping.size
7 }

在清除阶段,程序会搜索整个堆,回收计数器值仍为 0 的对象。

我们在这里介绍的 GC 标记 - 清除算法和在之前介绍的 GC 标记 - 清除算法主要有以下 3 点不同。

  1. 一开始就把所有对象的计数器值设为 0
  2. 不标记对象,而是对计数器进行增量操作
  3. 为了对计数器进行增量操作,算法对活动对象进行了不止一次的搜索

像这样,只要把引用计数法和 GC 标记 - 清除算法结合起来,在计数器溢出后即使对象成了垃圾,程序还是能回收它。另外还有一个优点,那就是还能回收循环的垃圾。

但是在进行标记处理之前,必须重置所有的对象和计数器。此外,因为在查找对象时没有设置标志位而是把计数器进行增量,所以需要多次(次数和被引用数一致)查找活动对象。考虑到这一点的话,显然在这里进行的标记处理比以往的 GC 标记 - 清除算法中的标记处理要花更多的时间。也就是说,吞吐量会相应缩小。

部分标记 - 清除算法

什么是部分标记 - 清除算法

之前已经讲过,引用计数法存在的一大问题就是不能回收循环的垃圾。这是引用计数法的一大特色,用 GC 标记 - 清除算法就不会有这种问题。那么我们自然会想到,只要跟之前使用延迟引用计数法时一样,利用 GC 标记 - 清除算法不就好了吗?也就是说,可以采用一般情况下执行引用计数法,在某个时刻启动 GC 标记 - 清除算法的方法。

然而,这个方法可以说效率很低。利用 GC 标记 - 清除算法毕竟是单纯为了回收“有循环引用的垃圾”,而一般来说这种垃圾应该很少,单纯的 GC 标记 - 清除算法又是以全部堆为对象的,所以会产生许多无用的搜索。

对此,我们还有个方法,那就是只对“可能有循环引用的对象群”使用 GC 标记 - 清除算法,对其他对象进行内存管理时使用引用计数法。像这样只对一部分对象群使用 GC 标记 - 清除算法的方法,叫作“部分标记 - 清除算法”(Partial Mark & Sweep)。不过它有个特点,执行一般的 GC 标记 - 清除算法的目的是查找活动对象,而执行部分标记 - 清除算法的目的则是查找非活动对象。接下来我们就为大家介绍 Rafael D. Lins 于 1992 年研究出的部分标记 - 清除算法。

前提

在部分标记 - 清除算法中,对象会被涂成 4 种不同的颜色来进行管理。每个颜色的含义如下所示。

  1. 黑(BLACK):绝对不是垃圾的对象(对象产生时的初始颜色)
  2. 白(WHITE):绝对是垃圾的对象
  3. 灰(GRAY):搜索完毕的对象
  4. 阴影(HATCH):可能是循环垃圾的对象

话虽这么说,事实上并没办法去给对象涂颜色,而是往头中分配 2 位空间,然后用 00~11 的值对应这 4 个颜色,以示区分。本书中用 obj.color 来表示对象 obj 的颜色。obj.color 取 BLACK、WHITE、GRAY、HATCH 中的任意一个值。

为了解释算法,我们设一个堆,它里面的对象和引用关系如图 9 所示。


[图 9 初始状态]

有循环引用的对象群是 ABC 和 DE,其中 A 和 D 由根引用。此外,这里这里由 C 和 E 引用 F。所有对象的颜色都还是初始状态下的黑色。

dec_ref_cnt() 函数

接下来,通过 mutator 删除由根到对象 A 的引用。这个引用是由 update_ptr() 函数产生的。跟以往的引用计数法一样,为了将对象 A 的计数器减量,在 update_ptr() 函数中调用 dec_ref_cnt() 函数。不过在部分标记 - 清除算法中,dec_ref_cnt() 函数和以往有少许不同。

代码清单 16:部分标记- 清除算法中的 dec_ref_cnt() 函数

1 dec_ref_cnt(obj){
2   obj.ref_cnt--
3   if(obj.ref_cnt == 0)
4     delete(obj)
5   else if(obj.color != HATCH)
6     obj.color = HATCH
7     enqueue(obj, $hatch_queue)
8 }

第 2 行到第 4 行的 dec_ref_cnt() 函数和以往引用计数法中的没什么不同。不过,如果要删除的对象在队列中,那么这里使用的 delete() 函数也需要将该对象从队列中删除。

我们该注意的是第 5 行之后。算法在对 obj 的计数器进行减量操作后,检查 obj 的颜色。当 obj 的颜色不是阴影的时候,算法会将其涂上阴影并追加到队列中。当 obj 的颜色是阴影的时候,obj 已经被追加到队列中了,所以程序什么都不做。

dec_ref_cnt() 函数执行之后的堆状态如图 10 所示。


[图 10 dec_ref_cnt() 函数执行之后]

由根到 A 的引用被删除了,指向 A 的指针被追加到了队列($hatch_queue)之中。此外,A 被涂上了阴影。这个队列的存在是为了连接那些可能是循环引用的一部分的对象。被连接到队列的对象会被作为 GC 标记 - 清除算法的对象,使得循环引用的垃圾被回收。

new_obj() 函数

在部分标记 - 清除算法中,我们不仅要修改 dec_ref_cnt() 函数,也要修改 new_obj() 函数。

代码清单 17:部分标记- 清除算法中的 new_obj() 函数

 1 new_obj(size){
 2   obj = pickup_chunk(size)
 3   if(obj != NULL)
 4     obj.color = BLACK
 5     obj.ref_cnt = 1
 6     return obj
 7   else if(is_empty($hatch_queue) == FALSE)
 8     scan_hatch_queue()
 9     return new_obj(size)
10   else
11     allocation_fail()
12 }

当可以分配时,对象就会被涂回黑色,执行这项操作的是第 3 行到第 6 行。当分配无法顺利进行的时候,程序会调查队列是否为空。当队列不为空时,程序会通过 scan_hatch_queue() 函数搜索队列,分配分块。scan_hatch_queue() 函数执行完毕后,程序会递归地 调用 new_obj() 函数再次尝试分配。

如果队列为空,则分配将会失败。

scan_hatch_queue() 函数

scan_hatch_queue() 函数在找到阴影对象前会一直从队列中取出对象。

代码清单 18:scan_hatch_queue() 函数

1 scan_hatch_queue(){
2   obj = dequeue($hatch_queue)
3   if(obj.color == HATCH)
4     paint_gray(obj)
5     scan_gray(obj)
6     collect_white(obj)
7   else if(is_empty($hatch_queue) == FALSE)
8     scan_hatch_queue()
9 }

如果取出的对象 obj 被涂上了阴影,程序就会将 obj 作为参数,依次调用 paint_gray() 函数、scan_gray() 函数和 collect_white() 函数(第 4 行到第 6 行),从而通过这些函数找出循环引用的垃圾,将其回收。关于各个函数我们会在之后按顺序解说。

当 obj 没有被涂上阴影时,就意味着 obj 没有形成循环引用。此时程序对 obj 不会进行任何操作,而是再次调用 scan_hatch_queue() 函数(第 8 行)。

paint_gray() 函数

从 scan_hatch_queue() 函数调用的 3 个函数中,首先调用的就是 paint_gray() 函数。它干的事情非常简单,只是查找对象进行计数器的减量操作而已。

代码清单 19:paint_gray() 函数

1 paint_gray(obj){
2   if(obj.color == (BLACK | HATCH))
3     obj.color = GRAY
4     for(child : children(obj))
5       (*child).ref_cnt--
6       paint_gray(*child)
7 }

程序会把黑色或者阴影对象涂成灰色,对子对象进行计数器减量操作,并调用 paint_gray() 函数。把对象涂成灰色是为了防止程序重复搜索。在 scan_hatch_queue() 函数中执 行 paint_gray() 函数后,堆状态如图 11 所示。


[图 11 paint_gray() 函数执行之后]

这里通过 paint_gray() 函数按对象 A、B、C、F 的顺序进行了搜索。下面让我们来详细看一下,请看图 12。

[图 12 通过paint_gray() 函数标记循环对象]

首先,在 (a) 中 A 被涂成了灰色。虽然程序对计数器执行了减量操作,但并不是对 A,而是对 B 的计数器进行了减量操作。下面在 (b) 中 B 也被涂成了灰色,不过这时程序并没有对 B 进行减量操作,而是对 C 进行了减量操作。在 (c) 中 C 被涂成灰色时,程序对 A 和 F 的计数器进行了减量操作。这样一来,A、B、C 的循环垃圾的计数器值都变成了 0。(d) 是 A、B、C、F 各个对象搜索结束后的样子。

部分标记 - 清除算法的特征就是要涂色的对象和要进行计数器减量的对象不是同一对象,据此就可以很顺利地回收循环垃圾。

scan_gray() 函数

执行完 paint_gray() 函数以后,下一个要执行的就是 scan_gray() 函数。它会搜索灰色对象,把计数器值为 0 的对象涂成白色。

代码清单 20:scan_gray() 函数

1 scan_gray(obj){
2   if(obj.color == GRAY)
3     if(obj.ref_cnt > 0)
4       paint_black(obj)
5     else
6       obj.color = WHITE
7       for(child : children(obj))
8         scan_gray(*child)
9 }

打个比方,在图 11 这种情况下,程序会从对象 A 开始搜索,但是搜索的只有灰色对象。如果对象的计数器值为 0,程序就会把这个对象涂成白色,再查找这个对象的子对象。也就是说,A、B、C 都会被涂成白色。计数器值大于 0 的对象会被 paint_black() 函数处理。paint_black() 函数如代码清单 21 所示。

代码清单 21:paint_black() 函数

1 paint_black(obj){
2   obj.color = BLACK
3   for(child : children(obj))
4     (*child).ref_cnt++
5     if((*child).color != BLACK)
6       paint_black(*child)
7 }

在这里对象的计数器会被增量,被涂成黑色。paint_black() 函数在这里进行的操作就是:从那些可能被涂成了灰色的有循环引用的对象群中,找出已知不是垃圾的对象,并将其归回原处。

在 scan_hatch_queue() 函数中执行完 scan_black() 函数后,堆的状态如图 13 所示。


[图 13 scan_gray() 函数执行之后]

不难看出,形成了循环垃圾的对象 A、B、C 被涂成了白色,而有循环引用的非垃圾对象 D、E、F 被涂成了黑色。

collect_white() 函数

剩下就是通过 collect_white() 函数回收白色对象了。

代码清单 22:collect_white() 函数

1 collect_white(obj){
2   if(obj.color == WHITE)
3     obj.color = BLACK
4     for(child : children(obj))
5       collect_white(*child)
6     reclaim(obj)
7 }

该函数只会查找白色对象进行回收。循环垃圾也可喜地被回收了。


[图 14 回收循环垃圾]

这就是部分标记 - 清除算法。通过这个算法就能将引用计数法过去一直让人感到棘手的“有循环引用的垃圾”回收了。

限定搜索对象

部分标记 - 清除算法的优点,就是把要搜索的对象限定在阴影对象及其子对象,也就是“可能是循环垃圾的对象群”中。那么,要怎么发现这样的对象群呢?

问题的关键就在于循环垃圾产生的过程。请看图 15。


[图 15 循环垃圾产生的过程]

初始状态下根引用对象 A,对象 A 引用对象 B,对象 B 引用对象 C。接下来我们创建一个从对象 C 到对象 A 的引用。在这里就形成了 A → B → C → A 的循环引用。最后我们删除从根到对象 A 的引用。这样一来,对象 A 到 C 的循环引用对象群就成了垃圾。

像这样,当满足下面两种情况时,就会产生循环垃圾。

  1. 产生循环引用
  2. 删除从外部到循环引用的引用

在此请注意对象 A 的计数器,其计数器值由 2 变成了 1。

部分标记 - 清除算法中用 dec_ref_cnt() 函数来检查这个值。如果对象的计数器值减量后不为 0,说明这个对象可能是循环引用的一份子。这时会先让这个对象连接到队列,以方便之后搜索它。

paint_gray() 函数的要点

关于部分标记 - 清除算法,我们还有一个要点要说,那就是 paint_gray() 函数。在 paint_gray() 函数中,参数 obj 为黑色或阴影时会把 obj 涂成灰色,然后对 obj 的子对象执行计数器减量,并递归地调用 paint_gray() 函数。obj 自身的计数器并没有被执行减量。这点非常重要。

如果在这里不对 obj 子对象的计数器执行减量,而是对 obj 的计数器执行减量,会怎么样呢?我们将 paint_gray() 函数稍微变换一下,变换成 bad_paint_gray() 函数,看看情况会如何。请看代码清单 23。

代码清单 23:bad_paint_gray() 函数

1 bad_paint_gray(obj){
2   if(obj.color == (BLACK | HATCH))
3     obj.ref_cnt--
4     obj.color = GRAY
5     for(child : children(obj))
6       bad_paint_gray(*child)
7 }

事实上用 bad_paint_gray() 函数也能回收循环垃圾。这是因为仅改变对计数器进行减量操作的时刻,最后就能将循环垃圾的计数器值全部变成 0。不过在如图 16 所示的状况下,bad_paint_gray() 函数无法顺利运行。


[图 16 bad_paint_gray() 函数无法顺利运行的例子]

bad_paint_gray() 函数涂改对象并对计数器进行减量操作的情况如图 17 所示。


[图 17 bad_paint_gray() 的执行过程]

当函数搜索完对象 C 时,对象 A 到 C 都会被涂成灰色,计数器值变为 0。接下来,通过 scan_gray() 函数再次从对象 A 开始搜索,不过因为对象 A 的计数器值已经变成了 0,所以被涂成了白色。当然,对象 B 和 C 也是如此。然后根据 collect_white() 函数,对象 A 到 C 被辨认为垃圾并回收。

为什么会发生这种事情呢?这是因为 bad_paint_gray() 函数突然把已经进入队列的对象(也就是对象 A)的计数器减量了。在这个阶段,程序无法判别对象 A 是否形成了循环引用。只能从 A 找到 B,然后再查找 C,再由 C 回到 A,才能知道 A 到 C 是循环的。

因此在部分标记 - 清除算法中,paint_gray() 函数不是在搜索 A 的时候就首先对 A 的计数器进行减量操作的,而是从 A 的子对象,也就是 B 的计数器开始进行减量操作的。在这种稍不经心就会看漏的地方,居然隐藏着这么重要的关键点呢。


[图 18 paint_gray() 函数的执行过程]

如图 18 所示,当搜索完 C 时对象 A 的计数器值为 1,所以 A 不能被回收。在这之后,paint_black() 函数会把对象 A 到 C 全部涂黑,也会对 B 和 C 的计数器进行增量操作,这样对象就完全回到了原始的状态。

部分标记 - 清除算法的局限性

然而,部分标记 - 清除算法并不是完美的,因为从队列搜索对象所付出的成本太大了。被队列记录的对象毕竟是候选垃圾,所以要搜索的对象绝对不在少数。这个算法总计需要查找 3 次对象,也就是说需要对从队列取出的阴影对象分别执行 1 次 mark_gray() 函数、scan_gray() 函数以及 collect_white() 函数。这大大增加了内存管理所花费的时间。

此外,搜索对象还害得引用计数法的一大优点 —— 最大暂停时间短荡然无存。

参考文档