2.1　GC算法分类

垃圾回收中对象的标记一般有两种实现：引用计数（reference count）法和可达性分析（tracing）法（也称为根引用分析法、追踪式分析法）。

引用计数法指的是为每一个对象设计一个计数器，用于统计对象被引用的次数，如果对象引用次数为0，则表示没有任何引用就可以释放该对象。引用计数法实现简单，能立即回收无用内存。

引用计数通常在对象引用关系改变时修改引用值。算法伪代码如下：

void object_ref_mod(Object* obj, Object* field) {
    inc_ref(filed); //注意引用计数需要先增后减，如果是先减后增，则可能出现bug
    def_ref(obj);
    obj= filed;
}
void inc_ref(Object* obj) {
    obj->ref_count++;
}
void def_ref(Object* obj) {
    obj->ref_count--;
    if(obj->ref_count == 0) {
        collect(obj); //释放对象占用的空间
        //针对对象obj的成员变量依次遍历，只处理引用类型的成员变量
        for(Object* ref_filed = obj->first_ref_field;
            ref_field != NULL;
            ref_field = ref_filed->next_ref_field) {
            def_rec(ref_field);[1]
        }
    }
}

虽然引用计数法很简单，但是引用计数法也存在一些问题，主要有：

1）并发场景中，对象引用计数器的修改需要与对象引用关系的修改保持同步，这往往需要加锁实现或者使用非常复杂的无锁算法。

2）引用计数在对象回收时会引发链式反应，例如根对象的引用计数值为0，需要递归地将成员变量的引用值更新。同时对于满足回收条件的对象进行内存回收，所以回收时间可能不可控。

3）引用计数无法有效解决循环引用的问题，例如两个对象A和B相互引用，即使没有任何其他对象引用对象A和B，但对象A和B的引用值都为1，这会导致本应该释放的对象因为算法缺陷而无法回收。另外，有关研究表明，以Java为例，循环依赖的比例并不低，所以使用引用计数算法一般还需要辅以可达性分析法的垃圾回收算法。

虽然引用计数法存在这些缺点，但是因为其简单，在一些语言（如Python）中也有使用。

JVM采用的是可达性分析法。可达性分析法的基本思路就是通过根（root）作为起始点，从这些节点出发根据引用关系开始搜索，搜索所走过的路径称为引用链，当搜索完成后所有活跃对象都被识别，而一个对象没有被任何引用链访问到时，则证明此对象是不活跃的，可以被回收。示意图如图2-1所示。

图2-1中只有一个对象完全是死亡对象，当识别完活跃对象后，就可以知道哪个是不活跃对象。

图2-1　可达性分析法示意图

本书不讨论引用技术式的内存管理技术，仅讨论可达性分析法内存管理的相关知识。

[1] 实现中通常不会采用递归的方式，主要原因是递归的效率不高，同时递归算法隐含栈溢出风险，通常会将递归算法修改为非递归实现。