GC reference count algorithm

偏执的太偏执、 2022-03-27 13:38 153阅读 0赞

> 本文主要介绍GC的引用计数算法，包括引用计数算法过程、优缺点、以及优化过程。

### GC reference count algorithm ###

*  1.引用计数算法
 *   *  1.1 计数器的增减
     *   *  new\_obj() 函数
         *  update\_ptr() 函数
 *  2.引用计数算法的优缺点
 *  3. 引用计数的优化
 *   *  3.1 延迟引用计数法
     *  3.2 Sticky 引用计数法
     *  3.3 一位引用计数法
     *  3.4 部分标记 - 清除算法

# 1.引用计数算法 #

核心思想就是：释放怎么都无法被引用的对象的机制。

引用计数算法引入了计数器的概念，表示有多少对象引用了这个对象。

## 1.1 计数器的增减 ##

与其余GC算法不同，引用计数算法的GC管理是在程序执行过程中，通过增减计数器的值来进行内存管理。

有以下两种情况计数器的值会发生增减，这涉及了new\_obj() 函数和 update\_ptr() 函数。

### new\_obj() 函数 ###

当我们新建对象的时候，会调用 new\_obj() 函数，伪代码如下：

new_obj(size){
    	obj = pickup_chunk(size, $free_list)
    	if(obj == NULL) 
    		allocation_fail()
    	else
    		obj.ref_cnt = 1
    		 return obj
    }

pickup\_chunk() 函数的用法也大致与在 GC 标记 - 清除算法中的用法相同。不过这次当 pickup\_chunk() 函数返回 NULL 时，分配就失败了。

在引用计数法中，除了连接到空闲链表的对象，其他所有对象都是活动对 象。也就是说，在 pickup\_chunk() 函数返回 NULL 那一刻，堆中就没有合适大小的分块了，分配就无法进行了。

当通过 pickup\_chunk() 函数返回合适大小的对象时，在第 7 行把计数器的值定为 1。很明显，这里新生成了对象，且对象被某处引用了。

### update\_ptr() 函数 ###

update\_ptr() 函数用于更新指针 ptr，使其指向对象 obj，同时进行计数器值的增减。

伪代码如下:  
···  
update\_ptr(ptr, obj)\{  
inc\_ref\_cnt(obj)  
dec\_ref\_cnt(\*ptr)  
\*ptr = obj  
\}  
···

更新指针时程序会执行此函数，但事实上进行指针更新的只有第 4 行的 \*ptr = obj 部分，第 2 行和第 3 行是进行内存管理的代码。主要的功能如下：

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

对于inc\_ref\_cnt函数没啥说的，就是把对象的引用计数器自加1，但是对于dec\_ref\_cnt就比较复杂了，因为可能会涉及到对象计数归0然后进行回收。

dec\_ref\_cnt伪代码如下：

dec_ref_cnt(obj){ 
    	obj.ref_cnt-- 
    	if(obj.ref_cnt == 0){
    		for(child : children(obj)) 
    			dec_ref_cnt(*child)
    	}
    	reclaim(obj)

首先对更新指针之前引用的对象 \*ptr 的计数器进行减量操作。减量操作后，计数器的值为 0 的对象变成了“垃圾”。因此，这个对象的指针(包括其引用的子域)会全部被删除。换言之，程序需要对 \*ptr 的子对象的计数器进行减量操作。在第 5 行递归调用 dec\_ref\_cnt() 函数就是为了这个。 然后，通过 reclaim() 函数将 obj 连接到空闲链表。reclaim() 函数会在本章中多次出现， 请牢记。

为了避免对象自己给自己赋值的情况下导致BUG，前面的操作必须是先increase然后再decrease。

从前面的引用计数算法过程我们可以知道，引用计数法的GC算法对于垃圾是会马上进行回收的。但是对于标记清除算法来说，只有当没有分块可以分配时才会触发GC。

# 2.引用计数算法的优缺点 #

优点：  
（1）即刻回收垃圾算法：当被引用数 的值为 0 时，对象马上就会把自己作为空闲空间连接到空闲链表。  
（2）STW暂停时间短：在引用计数法中，只有当程序更新指针时才会执行垃圾回收，因而大幅度地削减了程序的最大暂停时间。  
（3）没有必要沿指针查找

缺点：  
（1）计数器值的增减处理繁重：在我们的程序处理中指针的变换是非常高频的操作，所以每次操作都进行增减处理，非常消耗性能。  
（2）计数器需要占用很多位：用于引用计数的计数器最大必须能数完堆中所有对象的引用数，占用额外的内存太多。  
（3）循环引用无法回收：因为两个对象互相引用，所以各对象的计数器的值都是 1，就无法回收。

# 3. 引用计数的优化 #

## 3.1 延迟引用计数法 ##

## 3.2 Sticky 引用计数法 ##

## 3.3 一位引用计数法 ##

## 3.4 部分标记 - 清除算法 ##