引用计数（Reference Counting）算法

• 引用计数算法在每个对象都维护着一个内存字段来统计它被多少”部分”使用—引用计数器,每当有一个新的引用指向该对象时,引用计数器就+1 ,每当指向该引用对象失效时该计数器就-1 ,当引用数量为0的时候,则说明对象没有被任何引用指向,可以认定是”垃圾”对象.

• 由于只维护局部信息，所以不需要扫描全局对象图就可以识别并释放死对象；但也因为缺乏全局对象图信息，所以无法处理循环引用的状况。更高级的引用计数实现会引入“弱引用”的概念来打破某些已知的循环引用，但那是另一个话题了。

• 至于存放引用计数器的位置放在哪? RednaxelaFX介绍了两种方案. 可以侵入式的存在对象内，例如CPython就把引用计数存在每个受自动内存管理的Python对象的对象头里（PyObject的ob_refcnt字段），或者COM的IUnknown::AddRef()/Release()；也可以非侵入式的存在对象外面，例如C++11标准库里的std::shared_ptr。

• 下面通过网上一段非常常见的代码来分析为什么会产生循环引用的问题,目前只看到Gityuan有一段说明感觉是非常清晰地说明了这段代码:

public static void main(String[] args) {
        GcObject obj1 = new GcObject(); //Step1
        GcObject obj 2 = new GcObject();//Step2
        obj1.instance = obj2; //Step3
        obj2.instance = obj1;// //Step4
        obj1 = null; //Step5
        obj2 = null; //Step6
    }

  当采用引用计数算法时:

第一步:GcObject实例1被obj1引用,所以它的引用数+1,为1

第二步:GcObject实例2被obj2引用,所以它的引用数+1,为1

第三步:obj1的instance属性指向obj2,而obj2指向GcObject实例2,故GcObject实例2引用+1,为2

第四步:obj2的instance属性指向obj1,而obj1指向GcOjbect实例1,故GcObject实例1引用+1,为2
到此前4步, GcOjbect实例1和GcOjbect实例2的引用数量均为2,此时结果图如下.

PS:注意想一下,为什么是obj的instance属性,而不是写成obj本身?

5.第五步:obj1不再指向GcOjbect实例1,其引用计数减1,结果为1.

6.第六步:obj2不再指向GcOjbect实例2,其引用计数减1,结果为1.

到此,发现GcObject实例1和实例2的计数引用都不为0,那么如果采用的引用计数算法的话,那么这两个实例所占的内存将得不到释放,这便产生了内存泄露。

引用计数算法常用来说明垃圾回收算法的机制,但是很少为各种语言所有,其中COM采用的就是引用计数算法.

前面引用RednaxelaFX的话时,他提到过一种高级的引用计数算法采用了”弱引用”来解决了部分已知的循环引用.

标记一清除（ Mark-Sweep ）算法：

• 首先标记出存活的对象，那些没有被标记的就可以 被收集了。此算法执行分两阶段。第一阶段从引用根节点开始标记所有被引用的对象， 第二阶段遍历整个堆，把未标记的对象清除。他的主要不足有两个：一个是效率问题，标记和清除两个过程的效率都不高；另一个是空间问题，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能会导致以后在程序运行过程中需要分配较大的对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作， 此算法需要暂停整个应用；

复制（ Copying ）算法：

• 将内存分成两部分，收集的时候，存活的对象从一部分被移动 到另一个部分，如此往复。此算法把内存空间划分为两个相等的区域，每次只使用其中 一个区域。垃圾回收时，遍历当前使用区域， 把正在使用中的对象复制到另外一个区域 中。然后清理使用过得内存空间，此算法每次只处理正在使用中的对象，因此复制成本比较小，同时复制过去以后还 能进行相应的内存整理，不会出现“碎片”问题，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。当然，此算法的缺点也是很明显的， 就是需要两倍的内存空间（或者将内存缩小为了原来的一半）。

标记－整理（ Mark-Compact ）算法：

• 此算法结合了“标记，清除”和“复制”两个算法 的优点。也是分两阶段，第一阶段从根节点开始标记所有被引用对象，第二阶段遍历整 个堆，清除未标记对象并且把存活对象“压缩”到堆的其中一块连续的区域，按顺序排放。此算法 避免了“标记－清除”的碎片问题，同时也避免了“复制”算法的空间问题。标记，整理 算法

分代收集（ Generational Collecting ）算法：

• 这种算法并没有什么新的思想，只是根据对象存活周期的不同将内存划分为几块。一般是把Java堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适合的收集算法。在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成。而老年代中因为对象存活率高、没有额外空间对他进行分配担保，就必须使用“标记-清理”或者“标记-整理”算法来进行回收。
  ————————————————

备注：