GC复制算法

Published on 2017 - 05 - 15

GC 复制算法(Copying GC)是 Marvin L. Minsky 在 1963 年研究出来的算法。说得简单点,就是只把某个空间里的活动对象复制到其他空间,把原空间里的所有对象都回收掉。这是一个相当大胆的算法。在此,我们将复制活动对象的原空间称为 From 空间,将粘贴活动对象的新空间称为 To 空间。

什么是 GC 复制算法

本文首先会为大家介绍 Robert R. Fenichel 与 Jerome C. Yochelson 研究出来的 GC 复制算法。

GC 复制算法是利用 From 空间进行分配的。当 From 空间被完全占满时,GC 会将活动对象全部复制到 To 空间。当复制完成后,该算法会把 From 空间和 To 空间互换,GC 也就结束了。From 空间和 To 空间大小必须一致。这是为了保证能把 From 空间中的所有活动对象都收纳到 To 空间里。GC 复制算法的概要如图 1 所示。


[图 1 GC 复制算法的概要]

我们一起来看一下执行 GC 复制算法的 copying() 函数吧。

代码清单 1:copying() 函数

1 copying(){
2   $free = $to_start
3   for(r : $roots)
4     *r = copy(*r)
5 
6   swap($from_start, $to_start)
7 }

$free 是指示分块开头的变量。首先在第 2 行将 $free 设置在 To 空间的开头,然后在第 3 行、第 4 行复制能从根引用的对象。copy() 函数将作为参数传递的对象 *r复制的同时,也将其子对象进行递归复制。复制结束后返回指针,这里返回的指针指向的是 *r 所在的新空间的对象。

在 GC 复制算法中,在 GC 结束时,原空间的对象会作为垃圾被回收。因此,由根指向原空间对象的指针也会被重写成指向返回值的新对象的指针。

最后在第 6 行把 From 空间和 To 空间互换,GC 就结束了。

GC 复制算法的关键当然要数 copy() 函数了。我们来详细看看它吧。

copy() 函数

copy() 函数将作为参数给出的对象复制,再递归复制其子对象。

代码清单 2:copy() 函数

 1 copy(obj){
 2   if(obj.tag != COPIED)
 3     copy_data($free, obj, obj.size)
 4     obj.tag = COPIED
 5     obj.forwarding = $free
 6     $free += obj.size
 7 
 8     for(child : children(obj.forwarding))
 9       *child = copy(*child)
10 
11  return obj.forwarding
12 }

首先函数在第 2 行检查 obj 的复制是否已完成,在这里出现的 obj.tag 是一个域,表示 obj 的复制是否完成。如果 obj.tag == COPIED,则 obj 的复制已经完成。不过这不是什么特别的域。我们只是为了容易把它和已有的域区分开,而特意给它起了个名字而已。这 里的 obj.tag 就是 obj.field1 的别名。

如果 obj 尚未被复制,则函数会在第 3 行到第 9 行复制 obj,返回指向新空间对象的指针。

如果 obj 的复制已经完成,则函数会返回新空间对象的地址。

下面我们将解说第 3 行到第 9 行。首先在第 3 行用 copy_data() 函数将 obj 真正“复制”到 $free 指示的空间。使用 copy_data() 函数后对象的复制情况如图 2 所示。


[图 2 通过 copy_data() 函数复制对象]

如图 2 所示,对象 A 被复制,生成了 A'。

让我们回到代码清单 2。在第 3 行的 copy_data() 函数中,新空间是 $free,原空间是 obj,大小是 obj.size。第 3 行执行完毕时从新空间的对象指出的指针还指向 From 空间,这点请留意。

在第 4 行给 obj.tag 贴上 COPIED 这个标签。这样一来,即使有很多个指向 obj 的指针,obj 也不会被复制很多次。

在第 5 行把指向新空间对象的指针放在 obj.forwarding 里。像这样的指针叫作“forwarding 指针”。之后当找到指向原空间对象的指针时,需要把找到的指针换到新空间,forwarding 指针正是为此准备的。另外,这个叫作 forwarding 的域也同样是个普通的域,这里的 forwarding 是 field2 的别名。

COPIED 标签和 forwarding 指针如图 3 所示。


[图 3 定义 COPIED 标签和设置 forwarding指针]

请注意图 3 中的对象 A。tag 域中添上了一个复选标记。在这里它表示的是 COPIED 标签。此外,forwarding 域中设置了指向 A' 的指针。这就是 forwarding 指针。

我们再次回到代码清单 2,在第 6 行中按照 obj 的长度向前移动 $free,在第 8 行和 第 9 行把新空间对象的子对象作为参数,递归调用 copy() 函数。

因为 copy() 函数会返回指向新空间的指针,所以会把指向子对象的引用重写为这个新的指针。这样一来,从 To 空间指向 From 空间的指针就全部指向 To 空间了。

GC 全部执行完毕后的状态如图 4 所示。


[图 4 copying() 函数执行完毕后]

图 2(a) 中的活动对象 A、C、D 保持着原有的引用关系被从 From 空间复制到了 To 空间。此外,从根指向 A 的指针也被换成了 A'。留在 From 空间里的对象 A 到 D 都被回收了。

在此要实现这个方法有 2 个条件。首先每个对象都至少要有 2 个域,分别用作 COPIED 标签和 forwarding 指针。大多数处理系统应该都能满足这个条件。接下来,COPIED 标签为了挪用 obj 中的域,必须选 1 个 mutator 绝对不会用到的值。这要花些功夫。举个例子,我们可以空着 mutator,不利用最高有效位,设置最高有效位的值为 COPIED。

如果该值mutator用到的话,就会出现一些异常引用。如恰好该值包含在没有被引用的对象中。

new_obj() 函数

跟 GC 标记 - 清除算法等算法不同,GC 复制算法的分配过程非常简单。

代码清单 3:new_obj() 函数

 1 new_obj(size){
 2   if($free + size < $from_start + HEAP_SIZE/2)
 3     copying()
 4     if($free + size > $from_start + HEAP_SIZE/2)
 5       allocation_fail()
 6 
 7   obj = $free
 8   obj.size = size
 9   $free += size
10   return obj
11 }

在 GC 复制算法中,请注意 GC 完成后只有 1 个分块的内存空间。在每次分配时,只要把所申请大小的内存空间从这个分块中分割出来给 mutator 就行了。也就是说,这里的分配跟 GC 标记 - 清除算法中的分配不同,不需要遍历空闲链表。

这里有一点应引起注意,在 GC 复制算法中,HEAP_SIZE 表示的是把 From 空间和 To 空间加起来的大小。也就是说,From 空间和 To 空间的大小一样,都是 HEAP_SIZE 的一半。

如果分块的大小不够,也就是说分块小于所申请的大小的时候,比起启动 GC,首先应分配足够大的分块。不然一旦分块大小不够,分配就会失败。

如果分块足够大,那么程序就会把 size 大小的空间从这个分块中分割出来,交给 mutator。不过别忘了还得把 $free 移动 size 个长度。

执行过程

我们通过别的例子来详细看看 GC 复制算法。请大家特别注意对象被复制的顺序。我们假设堆里对象的配置如图 5 所示。为了给 GC 做准备,这里事先将 $free 指针指向 To 空间的开头。


[图 5 初始状态]

假设就以这种状态开始 GC。首先是从根直接引用的对象 B 和 G,B 先被复制到了 To 空间。B 被复制后的堆状态如图 6 所示。


[图 6 B 被复制之后]

在此我们将 B 被复制后生成的对象称为 B'。我们看图 6 中的 B,field1 已经打上了复制完成的标签,field2 里放了一个指向 B' 的 forwarding 指针。

但是,这里只把 B' 复制了过来,它的子对象 A 还在 From 空间里。下面我们要把这个 A 复制到 To 空间里。

[图 7 A 被复制之后]

这次才可以说在真正意义上复制了 B(图 7)。因为 A 没有子对象,所以对 A 的复制也就完成了。

接下来,我们要复制和 B 一样从根引用的 G,以及其子对象 E。虽然 B 也是 G 的子对象,不过因为已经复制完 B 了,所以只要把从 G 指向 B 的指针换到 B' 上就行了。

最后只要把 From 空间和 To 空间互换,GC 就结束了。GC 结束时堆的状态如图 8 所示。我们在以后还会引用这张图,请务必牢记。


[图 8 GC 结束后]

当然了,对象 C、D、F 因为没法从根查找,所以会被回收。

在这里程序是以 B、A、G、E 的顺序搜索对象的。不知大家发现了没有,这是深度优先搜索。

优点

优秀的吞吐量

GC 标记 - 清除算法消耗的吞吐量是搜索活动对象(标记阶段)所花费的时间和搜索整体堆(清除阶段)所花费的时间之和。

另一方面,因为 GC 复制算法只搜索并复制活动对象,所以跟一般的 GC 标记 - 清除算法相比,它能在较短时间内完成 GC。也就是说,其吞吐量优秀。

尤其是堆越大,差距越明显。GC 标记 - 清除算法在清除阶段所花费的时间会不断增加,但 GC 复制算法就不会产生这种消耗。毕竟它消耗的时间是与活动对象的数量成比例的。

可实现高速分配

GC 复制算法不使用空闲链表。这是因为分块是一个连续的内存空间。因此,调查这个分块的大小,只要这个分块大小不小于所申请的大小,那么移动 $free 指针就可以进行分配了。

比起 GC 标记 - 清除算法和引用计数法等使用空闲链表的分配,GC 复制算法明显快得多。大家想一下,使用空闲链表时为了找到满足要求的分块,需要遍历空闲链表对吧?最坏的情况就是我们不得不从空闲链表中取出最后一个分块,这样就要花大把时间把所有分块都调查一遍。

不会发生碎片化

请再看一下图 8。基于算法性质,活动对象被集中安排在 From 空间的开头对吧。像这样把对象重新集中,放在堆的一端的行为就叫作压缩。在 GC 复制算法中,每次运行 GC 时都会执行压缩。

因此 GC 复制算法有个非常优秀的特点,就是不会发生碎片化。也就是说,可以安排分块允许范围内大小的对象。

另一方面,在 GC 标记 - 清除算法等 GC 算法中,一旦安排了对象,原则上就不能再移动它了,所以多多少少会产生碎片化。

与缓存兼容

不知各位注意到了没有,在 GC 复制算法中有引用关系的对象会被安排在堆里离彼此较近的位置。请再看一下图 8。B' 引用 A',G' 引用 E',图中按照 B'、A'、G'、E' 的顺序排列。

这种情况有一个优点,那就是 mutator 执行速度极快。近来很多 CPU 都通过缓存来高速读取位置较近的对象。这也是借助压缩来完成的,通过压缩来把有引用关系的对象安排在堆中较近的位置。

缺点

堆使用效率低下

GC 复制算法把堆二等分,通常只能利用其中的一半来安排对象。也就是说,只有一半堆能被使用。相比其他能使用整个堆的 GC 算法而言,可以说这是 GC 复制算法的一个重大的缺陷。

通过搭配使用 GC 复制算法和 GC 标记 - 清除算法可以改善这个缺点。

不兼容保守式 GC 算法

GC 标记 - 清除算法有着跟保守式 GC 算法相兼容的优点。因为 GC 标记 - 清除算法不用移动对象。

另一方面,GC 复制算法必须移动对象重写指针,所以有着跟保守式 GC 算法不相容的性质。虽然有限制条件,不过 GC 复制算法和保守式 GC 算法可以进行组合。

递归调用函数

在这里介绍的算法中,复制某个对象时要递归复制它的子对象。因此在每次进行复制的时候都要调用函数,由此带来的额外负担不容忽视。大家都知道比起这种递归算法,迭代算法更能高速地执行 。

此外,因为在每次递归调用时都会消耗栈,所以还有栈溢出的可能。

为了消除这个缺点,我们会在下一节中为大家介绍 Cheney 的 GC 复制算法 —— 迭代进行复制的算法。

Cheney 的 GC 复制算法

C. J. Cheney 于 1970 年研究出了 GC 算法。相比 Fenichel 和 Yochelson 的 GC 复制算法,Cheney 的 GC 复制算法不是递归地,而是迭代地进行复制。

代码清单 4:Cheney的 GC 复制算法

 1 copying(){
 2   scan = $free = $to_start
 3   for(r : $roots)
 4     *r = copy(*r)
 5 
 6   while(scan != $free)
 7     for(child : children(scan))
 8       *child = copy(*child)
 9     scan += scan.size
10 
11   swap($from_start, $to_start)
12 }

在第 2 行将 scan 和 $free 的两个指针初始化。scan 是用于搜索复制完成的对象的指针。 $free 是指向分块开头的指针,跟我们在前面介绍的 GC 复制算法中的用法一样。

首先复制的是直接从根引用的对象,用到的是第 3 行和第 4 行。在第 6 行到第 9 行搜索复制完成的对象,迭代复制其子对象。最后把 From 空间和 To 空间互换就结束了。Cheney 的 GC 复制算法中的关键点仍是 copy() 函数。

copy() 函数

代码清单 5:Cheney的 copy() 函数

1 copy(obj){
2   if(is_pointer_to_heap(obj.forwarding, $to_start) == FALSE)
3     copy_data($free, obj, obj.size)
4     obj.forwarding = $free
5     $free += obj.size
6   return obj.forwarding
7 }

首先在第 2 行检查参数 obj 是不是已经复制完毕了。

对于 is_pointer_to_heap(obj.forwarding, $to_start),如果 obj.forwarding 是指向 To 空间的指针则返回 TRUE,如果不是(即非指针或指向 From 空间的指针)则返回 FALSE。

在第 3 行复制对象,在第 4 行对 forwarding 指针进行设定。forwarding 指针利用的是 field1。

显而易见,在 Fenichel 和 Yochelson 的 GC 复制算法中也有进行复制对象和设定 forwarding 指针的操作。然而 Cheney 的 GC 复制算法中没有用到 COPIED 标签。在 Fenichel 和 Yochelson 的 GC 复制算法中用 COPIED 标签来区分复制完成或未完成。在 Cheney 的 GC 复制算法中使用的则是 forwarding 指针。

那么怎么用 forwarding 指针来判断对象是否复制完毕呢?请大家试着想象一下,GC 没复制的对象,其指针指向哪里呢?当然是指着 From 空间某处的对象喽。反过来就可以这样判断:哪些对象有着指向 To 空间某处的指针,哪些对象就已经复制完毕了。也就是说,可知 obj.field1 指向 To 空间的对象 obj 已经复制完毕了。

执行过程

光用文字和伪代码比较难理解,我们来结合图片详细看一下吧。除了引入了 scan 指针之外,初始状态和图 5 是一样的。


[图 9 初始状态]

在 Cheney 的算法中,首先复制所有从根直接引用的对象,在这里就是复制 B 和 G。


[图 10 复制B 和 G 之后]

在这时,scan 仍然指着 To 空间的开头,$free 从 To 空间的开头向右移动了 B 和 G 个长度。关键是 scan 每次对复制完成的对象进行搜索时,以及 $free 每次对没复制的对象进行复制时,都会向右移动。剩下就是重复搜索对象和复制,直到 scan 和 $free 一致。下面进行对 B' 的搜索。


[图 11 搜索 B' 之后]

搜索 B',然后把被 B' 引用的 A 复制到了 To 空间,同时把 scan 和 $free 分别向右移动了。下面该搜索的是 G'。搜索 G' 后,E 被复制到了 To 空间,从 G' 指向 B 的指针被换到了 B'。

下面该搜索 A' 和 E' 了,不过它们都没有子对象,所以即使搜索了也不能进行复制。因为在 E' 搜索完成时 scan 和 $free 一致,所以最后只要把 From 空间和 To 空间互换,GC 就结束了。


[图 12 GC结束后]

接下来按 B、G、A、E 的顺序来搜索对象。Fenichel 和 Yochelson 的 GC 复制算法采用的是深度优先搜索,而 Cheney 的复制算法采用的则是广度优先搜索。

被隐藏的队列

广度优先搜索需要先入先出(FIFO)结构的队列,即把该搜索的对象保持在队列中,一边取出一边进行搜索。

可是代码清单 4 和代码清单 5 里并没有出现诸如此类的队列。那么我们要怎么进行广度优先搜索呢?

举个例子,请看图 10,这时还没被搜索的对象是 B' 和 G'。

那么图 11 又如何呢? G' 和 A' 还没被搜索,B' 已经搜索完毕了。

细心的读者应该已经注意到了吧。实际上 scan 和 $free 之间的堆变成了队列。scan 左边是已经搜索完毕的对象空间。也就是说,$free 每次向右移动,队列里就会追加对象,scan 每次向右移动,都会有对象被取出和搜索。这样一来就满足了先入先出队列的条件,即把先追加的对象先取出。

像这样把堆兼用作队列,正是 Cheney 算法的一大优点。不用特意为队列留出多余的内存空间就能进行搜索。

优点

Fenichel 和 Yochelson 的 GC 复制算法是递归算法,而 Cheney 的 GC 复制算法是迭代算法,因此它可以抑制调用函数的额外负担和栈的消耗。特别是拿堆用作队列,省去了用于搜索的内存空间这一点,实在是令人赞叹。

缺点

请大家回忆一下,在 Fenichel 和 Yochelson 的 GC 复制算法中,具有引用关系的对象是相邻的,因此才能充分利用缓存的便利。另一方面,就像我们在图 12 中看到的那样,在 Cheney 的 GC 复制算法中,有引用关系的对象,也就是 G' 和 E',B' 和 A' 并不相邻。

因此我们没法说 Cheney 的 GC 复制算法兼容缓存,只能说它比 GC 标记 - 清除算法和引用计数法要好一些而已。

下一节中我们将会为大家介绍近似深度优先搜索的方法,该方法对 Cheney 的 GC 复制算法进行了改善。

近似深度优先搜索方法

Cheney 的 GC 复制算法由于在搜索对象上使用了广度优先搜索,因此存在“没法沾缓存的光”的缺点。

下面我们将为大家介绍 Paul R. Wilson、Michael S. Lam 和 Thomas G. Moher 于 1991 年提出的近似深度优先搜索法。这个方法虽然只是近似深度优先搜索,不过这样一来就能通过深度优先搜索执行 GC 复制算法了。

Cheney 的 GC 复制算法(复习)

首先为了比较两者,我们先来看一下 Cheney 的 GC 复制算法。以图 13 这样的引用关系为例,假设这里所有的对象都是 2 个字。


[图 13 对象间的引用关系]

执行 Cheney 的 GC 复制算法时放置各个对象的“页面”如图 14 所示,据此我们就知道了各对象在内存里的配置情况。


[图 14 Cheney的 GC 复制算法中各个对象的配置]

各页面右上角的数字表示的是该页的编号。不过各页面的容量只有 6 个字,也就是说只能放下 3 个对象。

在 Cheney 的 GC 复制算法中,为了能按 A、B、C、D、E、F、G…… 的顺序搜索对象,对象的配置如上图所示。

这里需要大家注意的是各页面中的对象间的引用关系。不难看出,A 和被 A 引用的 B、C 是相邻摆放的。

不过,其他的对象距离有引用关系的对象较远。这样一来,就降低了本来很有可能被连续读取的对象同时位于缓存中的可能性,降低了缓存命中率。

在第 0 页中,A 和其引用的 B、C 已经配置好了,形成了理想的状态。

不过,在其他的第 1 页至第 4 页中,同一页面里的对象间都没有引用关系。因此每次访问这些对象时,都要浪费时间去从内存上读取包含这些对象的页面。像这样,虽然程序能在广度优先搜索的一开始把对象安排在理想的状态,但随着搜索的推进,对象的安排就逐渐向着不理想的状态发展了。

以上提到的这些对于大家理解近似深度优先搜索方法的算法是不可或缺的,请大家务必记牢。

前提

接下来要为大家介绍的是对 Cheney 的算法改良后的近似深度优先搜索法。在这个方法中,我们要用到下面 4 个重要的变量。

  • $page
  • $local_scan
  • $major_scan
  • $free

首先是 $page,它是将堆分割成一个个页面的数组。$page[i] 指向第 i 个页面的开头。

$local_scan 是将每个页面中搜索用的指针作为元素的数组。$local_scan[i] 指向第 i 个页面中下一个应该搜索的位置。

$major_scan 是指向搜索尚未完成的页面开头的指针。

$free 和在 Cheney 的算法中一样,都是指向分块开头的指针。

执行过程

那么我们趁热打铁,用图来为大家解说一下近似深度优先搜索的方法吧。请看图 13。

首先复制 A 到 To 空间,然后搜索 A,复制 B 和 C。它们都被复制到了第 0 页。到这里跟 Cheney 的算法完全一样。这时候 To 空间的状态如图 15 所示。


[图 15 复制并搜索A,复制 B 和 C 之后]

因为 A 已经搜索完了,所以 $local_scan[0] 指向 B。

$free 在此指向第 1 页的开头,也就是说,在下一次复制中对象会被安排到新的页面。在这种情况下,程序会从 $major_scan 引用的页面的 $local_scan 开始搜索。

此外,当对象被复制到新页面时,程序会根据这个页面的 $local_scan 进行搜索。搜索会一直持续到新页面被对象全部占满为止。

此时因为 $major_scan 还指向第 0 页,所以还跟之前一样从 $local_scan[0] 开始搜索。也就是说,下面要搜索 B。


[图 16 搜索B,复制 D 之后]

首先复制了被 B 引用的 D,在这里 D 被安排到了 $page[1] 的开头。像这样对象被安排到页面开头时,程序会使用该页面的 $local_scan 进行搜索。此时 $local_scan[0] 的搜索暂停,程序根据 $local_scan[1] 开始搜索对象 D。通过对 D 的搜索,复制了 H 和 I。

[图 17 搜索D,复制 H 和 I 之后]

在这里第 1 页已经满了,$free 指着第 2 页的开头。因此 $local_scan[1] 的搜索暂停,程序开始通过 $local_scan[0] 进行搜索。也就是说,再次开始对 B 的搜索。


[图 18 搜索B,复制 E 之后]

对 B 的搜索结束后,E 被复制到了第 2 页。因为程序还要往新页面上复制对象,所以 $local_scan[0] 的搜索再次暂停,开始通过 $local_scan[2] 进行搜索。

因此,下一个要搜索的是 E。通过对 E 的搜索复制 J 和 K。


[图 19 搜索E,复制 J 和 K 之后]

通过对 J 和 K 的搜索,第 2 页被填满了,$free 指向第 3 页的开头。因此我们回到 $major_scan,再次通过 $local_scan[0] 进行搜索。

接下来的操作和上述步骤一样,这里就不再详细说明了。搜索完对象 C,复制完 A 到 O 的所有对象之后的状态如图 20 所示。

这样终于搜索完第 0 页了,$major_scan 指向 $page[1]。虽然还有没搜索过的对象,但这些对象都没有子对象,所以程序不对它们进行复制。

执行结果

那么,此 GC 复制算法是如何通过近似深度优先搜索来安排对象的呢?结果如图 21 所示。请大家将图 21 与图 14(Cheney 的 GC 复制算法的执行结果)相比较看看。


[图 21 通过近似深度优先搜索安排对象]

很明显能够看出,跟 Cheney 的使用广度优先搜索的 GC 复制算法不同,在使用近似深度优先搜索的情况下,不管在哪一个页面里,对象间都存在着引用关系。

为什么会出现这样的结果呢?这是因为此算法采用的不是完整的广度优先搜索,而是在每个页面上分别进行广度优先搜索。这里利用了广度优先搜索的性质,即在搜索一开始把有引用关系的对象安排在同一个页面中。

多空间复制算法

GC 复制算法最大的缺点是只能利用半个堆。这是因为该算法将整个堆分成了两半,每次都要腾出一半。

那么把堆再作细分会如何呢?举个例子,我们不把堆分成 2 份,而是分成 10 份,其中需要拿出 2 块空间分别作为 From 空间和 To 空间来执行 GC 复制算法。反正无论如何都要空出 1 块空间来当 To 空间,那我们就把这个额外负担降到整体的 1/10 就行了。

接下来,我们必须用别的方法对剩下的 8 块空间执行 GC。在这里 GC 标记 - 清除算法又登场了。

多空间复制算法说白了就是把堆 N 等分,对其中 2 块空间执行 GC 复制算法,对剩下的(N-2)块空间执行 GC 标记 - 清除算法,也就是把这 2 种算法组合起来使用。

multi_space_copying() 函数

首先我们用伪代码来看看多空间复制算法吧。multi_space_copying() 函数如代码清单 6 所示。

代码清单 6:multi_space_copying() 函数

 1 multi_space_copying(){
 2   $free = $heap[$to_space_index]
 3   for(r : $roots)
 4     *r = mark_or_copy(*r)
 5 
 6   for(index : 0..(N-1))
 7     if(is_copying_index(index) == FALSE)
 8       sweep_block(index)
 9 
10   $to_space_index = $from_space_index
11   $from_space_index = ($from_space_index + 1) % N
12 }

这里将堆 N 等分,开头分别是 $heap[0], $heap[1], …, $heap[N-1]。这时 $heap[$to_space_index] 表示的是 To 空间。每次执行 GC 时,To 空间都会像 $heap[0], $heap[1], …, $heap[N-1], $heap[0] 这样进行替 换。From 空间在 To 空间的右边,也就是 $heap[1], $heap[2], …, $heap[N-2], $heap[N-1]。

在第 3 行和第 4 行给活动对象打上标记。这个操作一眼看去很像 GC 标记 - 清除算法中的标记阶段。

不过有一点不 同,就是该算法考虑到了对象在 From 空 间($heap[$from_space_index])里的情况。当参数 obj 在 From 空间里时,mark_or_copy() 函数会将其复制到 To 空间,返回其复制完毕的对象。如果 obj 在除 From 空间以外的其他地方,mark_or_copy() 函数会像通常的标记函数一样给对象打上标记,递归标记或者复制它的子对象。关于 mark_or_copy() 函数,我们将在下一节中进行介绍。

第 6 行到第 8 行是清除阶段。这里跟以往的 GC 标记 - 清除算法基本一致,位于 From 空间和 To 空间以外的分块且没被标记的对象会被连接到空闲链表。

最后将 To 空间和 From 空间往右移动一个位置,GC 就结束了。

mark_or_copy() 函数

下面我们来讲讲 mark_or_copy() 函数。

代码清单 7:mark_or_copy() 函数

 1 mark_or_copy(obj){
 2   if(is_pointer_to_from_space(obj) == TRUE)
 3     return copy(obj)
 4   else
 5     if(obj.mark == FALSE)
 6       obj.mark = TRUE
 7       for(child : children(obj))
 8         *child = mark_or_copy(*child)
 9     return obj
10 }

首先在第 2 行调查参数 obj 是否在 From 空间里。如果在 From 空间里,那么它就是 GC 复制算法的对象。这时就通过 copy() 函数复制 obj,返回新空间的地址。

如果 obj 不在 From 空间里,它就是 GC 标记 - 清除算法的对象。这时要设置标志位,对其子对象递归调用 mark_or_copy() 函数。最后不要忘了返回 obj。

copy() 函数

最后我们来看看 copy() 函数。

代码清单 8:多空间复制算法中的 copy() 函数

 1 copy(obj){
 2   if(obj.tag != COPIED)
 3     copy_data($free, obj, obj.size)
 4     obj.tag = COPIED
 5     obj.forwarding = $free
 6     $free += obj.size
 7     for(child : children(obj.forwarding))
 8       *child = mark_or_copy(*child)
 9     return obj.forwarding
10 }

这里的 copy() 函数基本上和 Fenichel 等人提出的 GC 复制算法中的 copy() 函数一样,只有一点不同,那就是不在第 8 行递归调用 copy() 函数,而是调用 mark_or_copy() 函数。如果对象 *child 是复制对象,则通过 mark_or_copy() 函数再次调用这个 copy() 函数。

执行过程

在这里我们用图来更具体地看一下多空间复制算法的流程吧。我们设份数 N 为 4,请看图 22。

2这张图没有考虑到碎片化。


[图 22 在开始执行第 1 次 GC 之前]

To 空间 $heap[0] 空着,其他的 3 个空间都安排有对象。在这个状态下执行 GC 就会变成图 23 这样。


[图 23 第 1 次 GC 结束之后]

我们将 $heap[0] 作为 To 空间,将 $heap[1] 作为 From 空间执行了 GC 复制算法。此外,在 $heap[2] 和 $heap[3] 中执行了 GC 标记 - 清除算法,将分块连接到了空闲链表。当 mutator 申请分块时,程序会从这个空闲链表或 $heap[0] 中分割出分块给 mutator。

接下来,将 To 空间和 From 空间分别移动一个位置,将 $heap[1] 作为 To 空间,将 $heap[2] 作为 From 空间,执行下面的 GC。

mutator 基于这个状态重新开始执行。让我们来设想一下再次没有了分块的情况,请看图 24。


[图 24 在开始执行第 2 次 GC 之前]

请大家注意,这次 $heap[1] 是 To 空间,$heap[2] 是 From 空间。在这种状态下执行 GC,堆就会变成如图 25 所示的状态。


[图 25 第 2 次 GC 结束之后]

$heap[2] 的活动对象都被复制到了 $heap[1] 中,在 $heap[0] 和 $heap[3] 中执行了 GC 标记 - 清除算法。

此外,为了准备下一次 GC,我们将 $heap[2] 设为 To 空间,将 $heap[3] 设为 From 空间。

优点

多空间复制算法没有将堆二等分,而是分割成了更多块空间,从而更有效地利用了堆。以往的 GC 复制算法只能使用半个堆,而多空间复制算法仅仅需要空出一个分块,不能使用的只有 1/N 个堆。

缺点

执行 GC 复制算法的只有 N 等分中的两块空间,对于剩下的(N-2)块空间执行的是 GC 标记 - 清除算法。因此就出现了 GC 标记 - 清除算法固有的问题 —— 分配耗费时间、分块碎片化等。

只要把执行 GC 标记 - 清除算法的空间缩小,就可以缓解这些问题。打个比方,如果让 N = 3,就能把发生碎片化的空间控制在整体堆的 1/3。不过这时候为了在剩下的 2/3 的空间里执行 GC 复制算法,我们就不能使用其中的一半,也就是堆空间的 1/3。

综上,不管是 GC 标记 - 清除算法还是 GC 复制算法,都各有各的缺点。大家也都明白,几乎不存在没有缺点的万能算法。

参考文档