垃圾回收面面观

2015-06-18

下一篇准备写Go1.5的垃圾回收的,所以这一篇先做一些垃圾回收相关的基础知识的铺垫。

基本垃圾回收算法

实际上大多数的垃圾回收算法,都是下面三种基本垃圾回收算法之上的变种。

引用计数(reference counting)

基本思路是为每个对象加一个计数器,记录指向这个对象的引用数量。每次有一个新的引用指向这个对象,计数器加一;反之每次有一个指向这个对象引用被置空或者指向其他对象,计数器减一。当计数器变为 0 的时候,自动删除这个对象。

引用计数的优点是:

  1. 相对简单,不需要太多运行时的支持,可以在原生不支持GC的语言里实现。
  2. 对象会在成为垃圾的瞬间被释放,不会给正常程序的执行带来额外中断。

它的问题是循环引用,对象A包含一个引用指向对象B,同时对象B包含一个引用指向对象A,计数器就抓瞎了。另外,引用计数对正常程序的执行性能有影响(每次引用赋值都要改计数器),特别是在多线程环境下(改计数器要加锁同步)。

标记-清扫(mark-sweep)

基本思路是先按需分配,等到没有空闲内存的时候从寄存器和程序栈上的引用出发,遍历以对象为节点、以引用为边构成的图,把所有可以访问到的对象打上标记,然后清扫一遍内存空间,把所有没标记的对象释放。

标记-清扫不存在无法处理循环引用的问题,但它的问题是当内存耗尽触发GC时,需要中断正常程序一段时间来清扫内存(stop the world),在内存大对象多的时候这个中断可能很长。

节点复制(copying)

基本思路是把整个内存空间一分为二,不妨记为fromspace和tospace。所有对象的内存先在fromspace中分配,当fromspace满的时候,同样从寄存器和程序栈上的引用出发,遍历以对象为节点、以引用为边构成的图,把所有可以访问到的对象复制到tospace中,然后对调fromspace和tospace的角色。

相对于标记-清扫,节点复制的主要缺点是总有一半空间空闲着无法利用。另一个比较隐晦的缺点是它使用内存的方式与现有的内存换页、Cache 换入换出机制有潜在的冲突。

它有一些的优点:

  1. 内存局部性好。节点复制时相当于做了一次内存整理的紧缩工作,从内存使用角度,会带来比较好的局部性。
  2. 分配算法友好。所有的对象在内存中永远都是紧密排列的,所以分配内存的任务变得极为简单,只要移动一个指针即可。这对于内存分配频繁的环境来说,性能优势相当大。
  3. 不需要清扫整个内存空间。如果内存中存活对象很少而垃圾对象很多的话,触发GC造成的中断会小于标记-清扫。

STW

STW是stop the world的缩写。前面提到的三种基本算法,除了引用计数之外,在垃圾回收时都是STW的。如果垃圾回收的同时,用户程序也在进行内存的使用和修改,垃圾回收的算法会比较复杂。STW的问题是程序会有卡顿,这对一些实时性要求比较高的场合是不能满足的。

分代

分代是指将内存分为不同的区域,按不同的频率来执行垃圾回收。出发点是根据内存使用规律,大部分的对象存活时间很短,会很快成为垃圾。少量存活时间较长的对象,更有可能持久被使用。于是,可以把内存区域划分为新生代和老生代,对新生代的对象执行垃圾回收相对频繁,老生代频率相对较低。新生代中多次回收都没被清除的对象将被移动到老生代。

这样的做法,相对于全区域扫描,分代提升了扫描的效率。另外,由于减少了需要扫描的区域大小,卡顿时间也会相对缩短。

三色标记

标记-清扫可以视为只有两种颜色,初始时都为白色,标记时使用黑色,清扫时所有白色对象成为垃圾。

三色标记是标记-清扫的一个变种算法,对象使用三种颜色:黑色,白色和灰色。

标记过程:

  1. 所有对象最初都是白色
  2. 将所有初始的可达对象,即全局对象或者栈对象(root集合),标记为灰色。
  3. 任意取出一个灰色对象,将所有它引用到的白色对象标记为灰色,然后将它自身标记为黑色。
  4. 重复上一步,直到找不到灰色对象。
  5. 剩下的对象不是白色就是黑色。
  6. 所有黑色对象都是可达的,而白色对象是不可达的。回收掉白色对象。

白色表示不可达对象。灰色表示对象本身被引用到,但是它的孩子结点还没处理完。黑色表示本身被引用,并且已处理对象中的子引用。

最终,标记算法完成后,不会存在灰色对象,黑色表示活跃的对象,而标记白色的对象将会被回收掉。


如果是STW的,上面没什么问题。但是如果允许用户代码跟垃圾回收同时运行,需要维护一条约束条件:

黑色对象绝对不能引用白色对象!

为什么不能让黑色引用白色?因为黑色对象是活跃对象,它引用的对象是也应该属于活跃的,不应该被清理。但是,由于在三色标记算法中,黑色对象已经处理完毕,它不会被重复扫描。那么,这个对象引用的白色对象将没有机会被着色,最终会被误当作垃圾清理。

STW中,一个对象,只有它引用的对象全标记后才会标记为黑色。所以黑色对象要么引用的黑色对象,要么引用的灰色对象。不会出现黑色引用白色对象。

对于垃圾回收和用户代码并行的场景,用户代码可能会修改已经标记为黑色的对象,让它引用白色对象。看一个例子来说明这个问题:

stack -> A.ref -> B

A是从栈对象直接可达,将它标记为灰色。此时B是白色对象。假设这个时候用户代码执行:

localRef = A.ref
A.ref = NULL

localRef是栈上面的一个黑色对象,前一行赋值语句使得它引用到B对象。后一行A.ref被置为空之后,A将不再引用到B。A是灰色但是不再引用到B了,B不会着色。localRef是黑色,处理完毕的对象,引用了B但是不会被再次处理。于是B将永远不再有机会被标记,它会被误当作垃圾清理掉!

增量

三色标记的目的,主要是用于做增量的垃圾回收。注意到,如果只有黑色和白色两种颜色,那么回收过程将不能中断,必须一次性完成,期间用户程序是不能运行的。

而使用三色标记,即使在标记过程中对象的引用关系发生了改变,例如分配内存并修改对象属性域的值,只要满足黑色对象不引用白色对象的约束条件,垃圾回收器就可以继续正常工作。于是每次并不需要将回收过程全部执行完,只是处理一部分后停下来,后续会慢慢再次触发的回收过程,实现增量回收。相当于是把垃圾回收过程打散,减少停顿时间。

write-barrier

前面说到了“黑色对象不能引用白色对象”这个约束条件。如果实现满足这种约束条件呢?write barrier!

来自wiki的对这个术语的解释:"A write barrier in a garbage collector is a fragment of code emitted by the compiler immediately before every store operation to ensure that (e.g.) generational invariants are maintained." 即是说,在每一处内存写操作的前面,编译器会生成的一小段代码段,来确保不要打破一些约束条件。

增量和分代,都需要维护一个write barrier。

先看分代的垃圾回收,跨越不同分代之间的引用,需要特别注意。通常情况下,大多数的交叉引用应该是由新生代对象引用老生代对象。当我们回收新生代的时候,这没有什么问题。但是当我们回收老生代的时候,如果只扫描老生代不扫描新生代,则老生代中的一些对象可能被误当作不可达对象回收掉!为了处理这种情况,可以做一个约定--如果回收老生代,那么比它年轻的新生代都要一起回收一遍。另外一种交叉引用是老生代对象引用到新生代对象,这时就需要write barrier了,所有的这种类型引用都应该记录下来,放到一个集合中,标记的时候要处理这个集合。

再看三色标记中,黑色对象不能引用白色对象。这就是一个约束条件,write barrier就是要维护这条约束。

垃圾回收