记录点滴
我们的回忆

GC的三大基础算法

基本术语

1. 垃圾(Garbage)

就是需要回收的对象。

作为编写程序的人,是可以做出“这个对象已经不再需要了”这样的判断,但计算机是做不到的。因此,如果程序(通过某个变量等等)可能会直接或间接地引用一个对象,那么这个对象就被视为“存活”;与之相反,已经引用不到的对象被视为“死亡”。将这些“死亡”对象找出来,然后作为垃圾进行回收,这就是GC的本质。

2、根(Root)

就是判断对象是否可被引用的起始点。

至于哪里才是根,不同的语言和编译器都有不同的规定,但基本上是将变量和运行栈空间作为根。好了,用上面这两个术语,我们来讲一讲主要的GC算法。

三大基础GC算法

1、标记清除法/标记压缩法

标记清除(Mark and Sweep)是最早开发出的GC算法(1960年)。它的原理非常简单,首先从根开始将可能被引用的对象用递归的方式进行标记,然后将没有标记到的对象作为垃圾进行回收。

mark-and-sweep

图1显示了标记清除算法的大致原理。图1中的(1)部分显示了随着程序的运行而分配出一些对象的状态,一个对象可以对其他的对象进行引用。图中(2)部分中,GC开始执行,从根开始对可能被引用的对象打上“标记”。大多数情况下,这种标记是通过对象内部的标志(Flag)来实现的。于是,被标记的对象我们把它们涂黑。图中(3)部分中,被标记的对象所能够引用的对象也被打上标记。重复这一步骤的话,就可以将从根开始可能被间接引用到的对象全部打上标记。到此为止的操作,称为标记阶段(Mark phase)。

标记阶段完成时,被标记的对象就被视为“存活”对象。图1中的(4)部分中,将全部对象按顺序扫描一遍,将没有被标记的对象进行回收。这一操作被称为清除阶段(Sweep phase)。

在扫描的同时,还需要将存活对象的标记清除掉,以便为下一次GC操作做好准备。标记清除算法的处理时间,是和存活对象数与对象总数的总和相关的。

作为标记清除的变形,还有一种叫做标记压缩(Mark and Compact)的算法,它不是将被标记的对象清除,而是将它们不断压缩。

2、复制收集算法

标记清除算法有一个缺点,就是在分配了大量对象,并且其中只有一小部分存活的情况下,所消耗的时间会大大超过必要的值,这是因为在清除阶段还需要对大量死亡对象进行扫描。复制收集(Copy and Collection)则试图克服这一缺点。在这种算法中,会将从根开始被引用的对象复制到另外的空间中,然后,再将复制的对象所能够引用的对象用递归的方式不断复制下去。

copy-and-collection

图2的(1)部分是GC开始前的内存状态,这和图1的(1)部分是一样的。图2的(2)部分中,在旧对象所在的“旧空间”以外,再准备出一块“新空间”,并将可能从根被引用的对象复制到新空间中。图中(3)部分中,从已经复制的对象开始,再将可以被引用的对象像一串糖葫芦一样复制到新空间中。复制完成之后,“死亡”对象就被留在了旧空间中。图中(4)部分中,将旧空间废弃掉,就可以将死亡对象所占用的空间一口气全部释放出来,而没有必要再次扫描每个对象。下次GC的时候,现在的新空间也就变成了将来的旧空间。

通过图2我们可以发现,复制收集方式中,只存在相当于标记清除方式中的标记阶段。由于清除阶段中需要对现存的所有对象进行扫描,在存在大量对象,且其中大部分都即将死亡的情况下,全部扫描一遍的开销实在是不小。而在复制收集方式中,就不存在这样的开销。

但是,和标记相比,将对象复制一份所需要的开销则比较大,因此在“存活”对象比例较高的情况下,反而会比较不利。这种算法的另一个好处是它具有局部性(Lo-cality)。在复制收集过程中,会按照对象被引用的顺序将对象复制到新空间中。于是,关系较近的对象被放在距离较近的内存空间中的可能性会提高,这被称为局部性。局部性高的情况下,内存缓存会更容易有效运作,程序的运行性能也能够得到提高。

3、引用计数法

引用计数(Reference Count)方式是GC算法中最简单也最容易实现的一种,它和标记清除方式差不多是在同一时间发明出来的。它的基本原理是,在每个对象中保存该对象的引用计数,当引用发生增减时对计数进行更新。引用计数的增减,一般发生在变量赋值、对象内容更新、函数结束(局部变量不再被引用)等时间点。当一个对象的引用计数变为0时,则说明它将来不会再被引用,因此可以释放相应的内存空间。

reference-count

图3的(1)部分中,所有对象中都保存着自己被多少个其他对象进行引用的数量(引用计数),图中每个对象右上角的数字就是引用计数。图中(2)部分中,当对象引用发生变化时,引用计数也跟着变化。在这里,由对象B到对象D的引用失效了,于是对象D的引用计数变为0。由于对象D的引用计数为0,因此由对象D到对象C和E的引用数也分别相应减少。结果,对象E的引用计数也变为0,于是对象E也被释放掉了。图3的(3)部分中,引用计数变为0的对象被释放,“存活”对象则保留了下来。大家应该注意到,在整个GC处理过程中,并不需要对所有对象进行扫描。

实现容易是引用计数算法最大的优点。标记清除和复制收集这些GC机制在实现上都有一定难度;而引用计数方式的话,凡是有些年头的C++程序员(包括我在内),应该都曾经实现过类似的机制,可以说这种算法是相当具有普遍性的。除此之外,当对象不再被引用的瞬间就会被释放,这也是一个优点。其他的GC机制中,要预测一个对象何时会被释放是很困难的,而在引用计数方式中则是立即被释放的。而且,由于释放操作是针对每个对象个别执行的,因此和其他算法相比,由GC而产生的中断时间(Pause time)就比较短,这也是一个优点。

引用计数方式的缺点另一方面,这种方式也有缺点。引用计数最大的缺点,就是无法释放循环引用的对象。

reference-count-cycle

图4中,A、B、C三个对象没有被其他对象引用,而是互相之间循环引用,因此它们的引用计数永远不会为0,结果这些对象就永远不会被释放。引用计数的第二个缺点,就是必须在引用发生增减时对引用计数做出正确的增减,而如果漏掉了某个增减的话,就会引发很难找到原因的内存错误。引用数忘了增加的话,会对不恰当的对象进行释放;而引用数忘了减少的话,对象会一直残留在内存中,从而导致内存泄漏。如果语言编译器本身对引用计数进行管理的话还好,否则,如果是手动管理引用计数的话,那将成为孕育bug的温床。

最后一个缺点就是,引用计数管理并不适合并行处理。如果多个线程同时对引用计数进行增减的话,引用计数的值就可能会产生不一致的问题(结果则会导致内存错误)。为了避免这种情况的发生,对引用计数的操作必须采用独占的方式来进行。如果引用操作频繁发生,每次都要使用加锁等并发控制机制的话,其开销也是不可小觑的。综上所述,引用计数方式的原理和实现虽然简单,但缺点也很多,因此最近基本上不再使用了。现在,依然采用引用计数方式的语言主要有Perl和Python,但它们为了避免循环引用的问题,都配合使用了其他的GC机制。这些语言中,GC基本上是通过引用计数方式来进行的,但偶尔也会用其他的算法来执行GC,这样就可以将引用计数方式无法回收的那些对象处理掉。

引用

未经允许不得转载:我们的回忆 » GC的三大基础算法

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我们的回忆 记录点滴

标签云会员中心