垃圾回收(GC)算法介绍(5)——分代垃圾回收

本文介绍分代垃圾回收策略的基础。

分代垃圾回收概述

在之前的垃圾回收算法介绍中,我们提到大部分对象创建后没多久就“死了”,也就是被垃圾回收掉了。因此很容易联想到可以将堆上的对象分为新生代对象和老年代对象,相应的区域就是新生代空间和老年代空间,针对不同区域执行不同的GC算法。可以说分代垃圾回收有一种分而治之的意思在里面。

在分代垃圾回收策略中,我们在每个对象上维护一个“年龄”域,在新生代区中每进行一次GC,那些没有被回收的对象的年龄就自增1。当对象的年龄达到一个上限后,将其移动到老年代空间。老年代空间里都是一些经历过多次GC而没有被回收的对象。

需要注意的一点是,分代垃圾回收并不是一种具体的GC算法,而是一种策略,在新生代空间和老年代空间中执行的GC算法还是之前讨论的那三种基本算法。

堆的结构

一个叫David Ungar的人提出了一种分代垃圾回收策略,这种策略在新生代空间中使用GC复制算法,在老年代空间使用标记-清除算法。

下面是对的结构示意图:

分代垃圾回收中的堆

解释一下上图中几个空间的含义。其中生成空间就是创建新对象所在的空间。当生成空间满了的时候,会对新生代进行GC。有两个幸存空间,对应于GC复制算法的from空间和to空间,每次只利用其中的一个。当进行新生代GC时,会将生成空间和幸存from空间的活跃对象都复制到幸存to空间中。只有在一定次数的新生代GC过程中幸存下来的对象才会被复制到老年代空间中去。

记录集

上图中还有一个$rs_set,这是做什么的呢?现在考虑一个问题,当我们在新生代中执行GC时,要如何找到活跃对象?有两种方式,一是从根出发,寻找新生代中的根引用对象和其子对象,二是从老年代中的对象出发,查找那些位于新生代的对象。因为完全可能存在这样的新生代对象:既不是根直接引用的新生代对象,也不是根直接引用的新生代对象的子对象,这种对象是被老年代对象所引用的对象。如果想找到这些对象,最直接的办法是遍历一遍老年代空间,递归地判断它们的子对象是否是新生代对象。但是这样一来,GC新生代空间时还要去查看一遍老年代对象,效率很低。$rs_set就是用来保存那些引用了新生代对象的老年代对象的。

$rs_set一般可以是一个数组,其中保存了引用了新生代对象的老年代对象的指针。在新生代GC时只需要遍历一次$rs_set,找出那些新生代对象,对其做处理就可以了。

写入屏障

在更新一个对象的指针时,要判断对象是否是老年代对象,且指针指向的对象是否是新生代的对象,我们需要一个叫做“写入屏障”的东西。写入屏障会判断这种情况,并在条件为真时将该老年代对象加入$rs_set中,方便下次新生代GC时使用。下面是写入屏障的伪代码:

1
2
3
4
5
6
7
8
write_barrier(obj, field, new_obj){
if(&obj >= $old_start && &new_obj < $old_start && obj.rememberd == FALSE){
$rs[$rs_index] = obj
$rs_index++
obj.rememberd = TRUE
}
obj.field = new_obj
}

对象的结构

在Ungar的分代垃圾回收中,对象头需要包含三个信息:

  1. age: 对象的年龄
  2. forwarded:已经复制完成的标志
  3. remembered:已经向记录集记录完毕的标志

这里age是记录新生代对象经历过的GC次数,当达到一定次数后就要被移动到老年代空间。forwarded用来标记是否已经完成复制,防止重复复制对象。remembered用来标记是否已经添加到记录集中,防止重复添加。

优点和缺点

分代垃圾回收使用了分而治之的方式,对存活时间不同的对象采用不同的处理方案,不需要每次GC都遍历整个堆空间,吞吐率得到了提高。

它的缺点是写入屏障会对指针更新操作带来额外的负担。另外如果一个程序中大部分对象存活时间都很长的话,会增加新生代GC的压力,并且导致老年代GC频繁地运行。