5.2.3　垃圾回收的分类

如果追根溯源的话，显式内存管理的替代方案很早就有了。因为早在1959年前后，约翰·麦肯锡（John McCarthy）就为Lisp语言发明了所谓“垃圾回收”的方法。这里，我们把之前使用过，现在不再使用或者没有任何指针再指向的内存空间就称为“垃圾”。而将这些“垃圾”收集起来以便再次利用的机制，就被称为“垃圾回收”（Garbage Collection）。在编程语言的发展过程中，垃圾回收的堆内存管理也得到了很大的发展。如今，垃圾回收机制已经大行其道，在大多数编程语言中，我们都可以看到对垃圾回收特性的支持，如表5-1所示。

垃圾回收的方式虽然很多，但主要可以分为两大类：

1.基于引用计数（reference counting garbage collector）的垃圾回收器

简单地说，引用计数主要是使用系统记录对象被引用（引用、指针）的次数。当对象被引用的次数变为0时，该对象即可被视作“垃圾”而回收。使用引用计数做垃圾回收的算法的一个优点是实现很简单，与其他垃圾回收算法相比，该方法不会造成程序暂停，因为计数的增减与对象的使用是紧密结合的。此外，引用计数也不会对系统的缓存或者交换空间造成冲击，因此被认为“副作用”较小。但是这种方法比较难处理“环形引用”问题，此外由于计数带来的额外开销也并不小，所以在实用上也有一定的限制。

2.基于跟踪处理（tracing garbage collector）的垃圾回收器

相比于引用计数，跟踪处理的垃圾回收机制被更为广泛地应用。其基本方法是产生跟踪对象的关系图，然后进行垃圾回收。使用跟踪方式的垃圾回收算法主要有以下几种：

（1）标记-清除（Mark-Sweep）

顾名思义，这个算法可以分为两个过程。首先该算法将程序中正在使用的对象视为“根对象”，从根对象开始查找它们所引用的堆空间，并在这些堆空间上做标记。当标记结束后，所有被标记的对象就是可达对象（Reachable Object）或活对象（Live Object），而没有被标记的对象就被认为是垃圾，在第二步的清扫（Sweep）阶段会被回收掉。

这种方法的特点是活的对象不会被移动，但是其存在会出现大量的内存碎片的问题。

（2）标记-整理（Mark-Compact）

这个算法标记的方法和标记-清除方法一样，但是标记完之后，不再遍历所有对象清扫垃圾了，而是将活的对象向“左”靠齐，这就解决了内存碎片的问题。

标记-整理的方法有个特点就是移动活的对象，因此相应的，程序中所有对堆内存的引用都必须更新。

（3）标记-拷贝（Mark-Copy）

这种算法将堆空间分为两个部分：From和To。刚开始系统只从From的堆空间里面分配内存，当From分配满的时候系统就开始垃圾回收：从From堆空间找出所有活的对象，拷贝到To的堆空间里。这样一来，From的堆空间里面就全剩下垃圾了。而对象被拷贝到To里之后，在To里是紧凑排列的。接下来是需要将From和To交换一下角色，接着从新的From里面开始分配。

标记-拷贝算法的一个问题是堆的利用率只有一半，而且也需要移动活的对象。此外，从某种意义上讲，这种算法其实是标记-整理算法的另一种实现而已。

虽然历来C++都没有公开地支持过垃圾回收机制，但垃圾回收并非某些语言的专利。事实上，C++11标准也开始对垃圾回收做了一定的支持，虽然支持的程度还非常有限，但我们已经看到了C++语言变得更为强大的端倪。