引用计数法引入了计数器的概念，表示一个对象被多少个其他对象引用，这是一个无符号的整数值。

算法过程

在其他的GC算法中，当需要进行GC时会调用GC函数来清理垃圾空间。然而在引用计数法中没有明确启动GC的时刻，它在程序运行的过程中通过对象的引用计数器来进行内存管理。计数器在两种情况下会发生变化，一个是创建对象时，一个是更新指针指向时。

创建对象

创建对象调用new_obj函数，和gc标记-清除算法差别不大，同样时遍历空闲链表，然后找到大小合适的分块返回，还额外的做了引用计数的操作：

1
2
3
4
5
6
7
8
9

func new_obj(size) {
    obj = pickup_chunk(size, free_list)
    if (chunk != NULL) {
        remove_node(free_list, obj)
        obj.ref_cnt = 1
        return obj
    }
    allocation_fail()
}

更新指针

更新指针调用update_ptr函数，用于更新指针ptr，使其指向对象obj，同时进行计数器增减：

1
2
3
4
5

func update_ptr(ptr, obj) {
    inc_ref_cnt(obj)
    dec_ref_cnt(*ptr)
    *ptr = obj
}

再来看一下对计数器增量和减量的操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func inc_ref_cnt(obj) {
    if (obj == NULL) {
        return
    }
    obj.ref_cnt++
}

func dec_ref_cnt(obj) {
    obj.ref_cnt--
    if (obj.ref_cnt == 0) {
        for (child in children(obj)) {
            dec_ref_cnt(*child)
        }
        reclaim(obj, free_list)
    }
}

减量操作后，计数器值为0的对象就变成了垃圾，相应由这个对象指向的其他对象都需要进行计数器减量的操作。之后调用reclaim函数将obj链接到空闲链表的中。

在实际更新指针指向之前，进行了2步内存管理的操作：

1. 对指针ptr新引用的对象（obj）计数器进行了增量操作
2. 对指针ptr之前引用的对象（*ptr）计数器进行了减量操作

先增量后减量的操作顺序是不能颠倒的，当*ptr和obj是同一个对象时，如果先进行减量操作，这时该对象计数器值可能先变为0而被错误回收，引发不可预知的bug。

优点

在引用计数法中，每个对象始终都知道自己的被引用数，当被引用数的值为0时，对象马上就会把自己作为空闲空间连接到空闲链表。也就是说，各个对象在变成垃圾的同时就会立刻被回收，这样就极大的缩短了程序的最大暂停时间。

缺点

引用计数法的缺点也很明显，主要有以下两点：

• 计数器处理带来额外开销

  大多数情况下，指针都会频繁的更新，这时候计数器的值增减就会变得很繁重。同时，用于引用计数的值最大必须大于堆中所有对象数，以防止所有对象都指向一个对象的情况，这样对于一个只有很少字段的对象来说，计数器字段就可能占了一半的空间。

• 无法处理循环引用

  

  如上图，当两个对象互相引用，但是有没有其他对象引用这两个对象时，就会造成引用计数器永远都是1，这两个对象就无法被回收，

改进

延迟引用计数法

因为引用计数法会频繁的修改计数器，可能给系统带来额外的开销，可以使用 延迟引用计数法 来延迟由根引用变化所带来的频繁的计数器修改。

在延迟引用计数法中，引入了一个ZCT(Zero Count Table)，会事先记录下计数器在def_ref_cnt()函数下变为0的对象：

计数器值为0的对象不一定是垃圾，所以先暂时保留这些对象，当整个堆空间满时，再统一对ZCT中指向的对象进行回收处理。这样就达到了延迟根引用的计数，将垃圾一并回收，减少了由根引用频繁变化带来的计数器修改。

但是因为延迟处理，失去了引用计数实时回收垃圾的优点，ZCT中的对象越多，暂停时间越长，降低了GC的吞吐量。

部分标记-清除算法

引用计数法最大的缺点就是不能解决循环引用的问题，使得单纯的引用计数法不能用于实际的应用中，部分标记-清除算法就是对这个问题的改进。

部分标记-清除算法只对可能有循环引用的对象群使用标记-清除，对其他对象还继续使用引用计数法。但是与普通的标记-清除算法不同，部分标记-清除算法查找的是非活动对象，这样就可以解决循环引用无法回收的问题了。

但是部分标记-清除算法并不是完美的，执行部分标记-清除过程需要暂停程序，这也失去了引用计数实时回收垃圾的优点。

下面用单独的一篇文章来说明部分标记-清除算法的过程。