垃圾回收面面观

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就是要维护这条约束。

有疑问加站长微信联系（非本文作者）