垃圾回收器的算法,垃圾回收算法与实现

1.引用计数算法

“参照计数”(Reference Counting )算法计算每个对象指向它的指针数，并在一个指针指向自己时将计数值加1。 删除指向自己的指针后，计数值将减少1。 如果计数值减少到0，则指向该对象的指针将不再存在，因此可以安全地丢弃。 可以直观地用下图表示。

引用计数算法的优点是内存管理开销在APP应用程序运行时分散，非常“平滑”，不需要因为垃圾回收而停止APP应用程序的运行。 另一个优点是空间参考的局部性很高。 当一个对象的引用计数值变为0时，系统不需要访问堆中其他页面上的设备。 此外，后面介绍的一些垃圾回收算法在回收之前遍历所有生存单元。 这可能会引起页面转换操作。 最后的引用计数算法提供了类似堆栈分配的方式，丢弃就回收。 接下来看到的一些垃圾回收算法是对象废弃后生存一段时间再回收。

引用计数算法有很多优点，但其缺点也很明显。 首先，您可以看到的是时间开销，每次创建或释放对象时都会计算引用计数值，从而产生额外的开销。 第二种空间开销，每个对象必须留出额外的空间来存储参考计数值，以保持自己参考的数目； 引用计数算法的最大缺点是无法处理环引用，如下图所示。

这里蓝色的两个对象既不能到达也不能回收。 因为它们互相参照，各自的计数值不是0。 这对引用计数算法来说是无能为力的，但其他垃圾回收算法能很好地处理环引用。

引用算法最有名的运用莫过于微软的COM技术，著名的IUnknown接口：

interfaceiunknown { virtual hresult _ stdcallqueryinterface，void**PPV}=0； virtualulong_stdcalladdref(=0； virtualulong_stdcallrelease(=0； }

这里的AddRef和Release是为了让组件本身能够管理生命周期，客户端程序只关心接口，而不需要关心组件的生命周期。 以下是一个简单的使用案例。

int main () { IUnknown* pi=CreateInstance )； IX* pix=NULL； hresult HR=pi-query接口(iid _ IX，) void * (pix )； if (安全(HR ) ) { pix-DoSomething； pix-Release (； (} pi-Release )； }上的客户端程序已经在CreateInstance中调用了AddRef，因此不需要再次调用，而是在使用接口后调用Release。 这将改变组件自身维护的计数值。 以下代码显示了一个简单的实现AddRef和Release的示例。

ULONG _stdcall AddRef () { return m_cRef； }ULONG _stdcall Release () if(-m_cref==0) { delete this； 返回0； } return m_cRef； }

在编程语言Python中，使用也是一种引用计数算法，如果对象的引用计数值为0，则调用__del__函数。 至于为什么Python选择引用计数算法，我读的文章说，因为Python是脚本语言，所以经常与C/C等语言进行交互，通过使用引用计数算法避免对象在内存中的更改因为Python还引入了gc模块来解决环引用问题，所以本质上python GC的方案是混合引用计数和跟踪(后面介绍的三种算法)两种垃圾回收机制。

2.标记-清除算法

“标记-清除”(朴素的黑猫-Sweep )算法依赖于确定可以通过一次全局遍历回收所有存活对象的对象。 遍历过程从根中找到所有可到达的对象，其他不可到达的对象是垃圾对象，可以回收。 整个过程分为两个阶段。 标记阶段会找到所有的生存对象。 逐步清除所有垃圾对象。

标记阶段

清除舞台

      相比较引用计数算法，标记-清除算法可以非常自然的处理环形引用问题，另外在创建对象和销毁对象时时少了操作引用计数值的开销。它的缺点在于标记-清除算法是一种“停止-启动”算法，在垃圾回收器运行过程中，应用程序必须暂时停止，所以对于标记-清除算法的研究如何减少它的停顿时间，而分代式垃圾收集器就是为了减少它的停顿时间，后面会说到。另外，标记-清除算法在标记阶段需要遍历所有的存活对象，会造成一定的开销，在清除阶段，清除垃圾对象后会造成大量的内存碎片。

3.标记-缩并算法

     标记-缩并算法是为了解决内存碎片问题而产生的一种算法。它的整个过程可以描述为：标记所有的存活对象；通过重新调整存活对象位置来缩并对象图；更新指向被移动了位置的对象的指针。

标记阶段：

清除阶段：

标记-压缩算法最大的难点在于如何选择所使用的压缩算法，如果压缩算法选择不好，将会导致极大的程序性能问题，如导致Cache命中率低等。一般来说，根据压缩后对象的位置不同，压缩算法可以分为以下三种：

1. 任意：移动对象时不考虑它们原来的次序，也不考虑它们之间是否有互相引用的关系。
2. 线性：尽可能的将原来的对象和它所指向的对象放在相邻位置上，这样可以达到更好的空间局部性。
3. 滑动：将对象“滑动”到堆的一端，把存活对象之间的自由单元“挤出去”，从而维持了分配时的原始次序。

4.节点拷贝算法

节点拷贝算法是把整个堆分成两个半区（From，To）， GC的过程其实就是把存活对象从一个半区From拷贝到另外一个半区To的过程，而在下一次回收时，两个半区再互换角色。在移动结束后，再更新对象的指针引用，GC开始前的情形：

GC结束后的情形：

      节点拷贝算法由于在拷贝过程中，就可以进行内存整理，所以不会再有内存碎片的问题，同时也不需要再专门做一次内存压缩。，而它最大的缺点在于需要双倍的空间。

5.总结

      本文总共介绍了四种经典的垃圾回收算法，其中后三种经常称之为跟踪垃圾回收，因为引用计数算法能够平滑的进行垃圾回收，而不会出现“停止”现象，经常出现于一些实时系统中，但它无法解决环形问题；而基于跟踪的垃圾回收机制，在每一次垃圾回收过程中，要遍历或者复制所有的存活对象，这是一个非常耗时的工作，一种好的解决方案就是对堆上的对象进行分区，对不同区域的对象使用不同的垃圾回收算法，分代式垃圾回收器正是其中一种，CLR和JVM中都采用了分代式垃圾回收机制，但它们在处理上又有些不同，后面的文章再详细介绍这两种垃圾回收器的区别。

 更加详细请参见于：http://www.cnblogs.com/Terrylee/

更多内容：http://blog.csdn.net/wallwind