1.引用计数算法

  引用计数(Reference Counting)算法是每个对象计算指向它的指针的数量,当有一个指针指向自己时计数值加1;当删除一个指向自己的指针时,计数值减1,如果计数值减为0,说明已经不存在指向该对象的指针了,所以它可以被安全的销毁了。可以很直观的用下面的图表示:

  引用计数算法的优点在于内存管理的开销分布于整个应用程序运行期间,非常的“平滑”,无需挂起应用程序的运行来做垃圾回收;而它的另外一个优势在于空间上的引用局部性比较好,当某个对象的引用计数值变为0时,系统无需访问位于堆中其他页面的单元,而后面我们将要看到的几种垃圾回收算法在回收前都回遍历所有的存活单元,这可能会引起换页(Paging)操作;后引用计数算法提供了一种类似于栈分配的方式,废弃即回收,后面我们将要看到的几种垃圾回收算法在对象废弃后,都会存活一段时间,才会被回收。

  引用计数算法有着诸多的优点,但它的缺点也是很明显的。首先能看到的一点是时间上的开销,每次在对象创建或者释放时,都要计算引用计数值,这会引起一些额外的开销;第二是空间上的开销,由于每个对象要保持自己被引用的数量,必须付出额外的空间来存放引用计数值;引用计数算法大的缺点在于它无法处理环形引用,如下图所示:

   此 处蓝色的这两个对象既不可达也无法回收,因为彼此之间互相引用,它们各自的计数值都不为0,这种情况对引用计数算法来说是无能为力的,而其他的垃圾回收算法却能很好的处理环形引用。

  引用计数算法的运用,莫过于微软的COM技术,大名鼎鼎的IUnknown接口:

 

interface IUnknown
{
    virtual HRESULT _stdcall QueryInterface
        (const IID& iid, void* * ppv) = 0;
    virtual ULONG _stdcall AddRef() = 0;
    virtual ULONG _stdcall Release() = 0;
}