垃圾回收机制中,引用计数法是如何维护所有对象引用的?

以前看JVM的时候总有个问题:讲到垃圾回收肯定会提到引用计数法,其优缺点都说了很多,但都没说要如何去实现它,我想问的是,引用计数法通过如何维护所有对象引用的?
关注者
1,128
被浏览
50,065

13 个回答

收录于 编辑推荐 ·
从楼主的问题看来,楼主似乎把GC的几个术语混为一谈了。在回答楼主问题之前先提一点:介绍自动内存管理的科普文章可能会提到引用计数(reference-counting)方式,但现在主流的JVM无一使用引用计数方式来实现Java对象的自动内存管理。

楼主提到的“扫描”与“整理”都与引用计数方式无关。楼主所说的“扫描”可能指的是“trace”,而“整理”指的肯定是“compaction”。这些都是基于可到达性来判断对象是否存活的tracing GC里会出现的概念,具体来说通常出现在mark-compact GC(“标记-整理GC”)中。

基于引用计数与基于trace这两大类别的自动内存管理方式最大的不同之处在于:前者只需要局部信息,而后者需要全局信息。

引用计数方式最基本的形态就是让每个被管理的对象与一个引用计数器关联在一起,该计数器记录着该对象当前被引用的次数,每当创建一个新的引用指向该对象时其计数器就加1,每当指向该对象的引用失效时计数器就减1。当该计数器的值降到0就认为对象死亡。每个计数器只记录了其对应对象的局部信息——被引用的次数,而没有(也不需要)一份全局的对象图的生死信息。由于只维护局部信息,所以不需要扫描全局对象图就可以识别并释放死对象;但也因为缺乏全局对象图信息,所以无法处理循环引用的状况。更高级的引用计数实现会引入“弱引用”的概念来打破某些已知的循环引用,但那是另一个话题了。
在实际实现中,引用计数存在什么地方是个有趣的话题。可以侵入式的存在对象内,例如CPython就把引用计数存在每个受自动内存管理的Python对象的对象头里(PyObject的ob_refcnt字段),或者COM的IUnknown::AddRef()/Release();也可以非侵入式的存在对象外面,例如C++11标准库里的std::shared_ptr
计数器的管理(自增/自减)可能由人工完成,例如老的Objective-C,或者是从C++里使用COM,等等;也可能是自动管理,例如CPython、使用“自动引用计数”(ARC)的Objective-CC++/CX的“hat”、前面提到的C++11的std::shared_ptr等等。如果能自动管理,那么必然有一套明确的规则说明何种情况下一个引用会被认为失效;以std::shared_ptr为例的话,其析构函数被调用(例如离开作用域时)或者其指向别的对象时,原本指向的对象的引用计数就会减1。

Tracing GC与引用计数正好相反,需要全局的对象图信息,从对象图的“根”(也就是必然活的引用)出发扫描出去,基于引用的可到达性来判断对象的生死。这使得对象的生死状态只能批量的被识别出来,然后批量释放死对象。Tracing GC不显式维护对象的引用计数,只在trace的时候才能回答“有”还是“没有”活引用指向某个对象

实际上,在内存充裕的前提下,tracing GC的整体开销比引用计数方式更低一些,所以吞吐量(throughput)高一些。因为引用计数方式通常需要统计冗余的局部信息,而tracing GC则可以通过全局信息一口气批量判断对象的生死;如果是带整理的tracing GC,则其内存分配通常也会更快。
不过tracing GC通常会比引用计数方式的延迟(latency)大一些,而且内存越紧张的时候tracing GC的效率反而越低,所以在内存不太充裕的地方使用引用计数仍然是个合理的选择(例如iOS5上的ARC)。
The Garbage Collection Handbook的第6章有对各种基本GC方式的详细对比,这边就不赘述了。

GC相关的书我在豆瓣上整理了一份书单,[Garbage Collection][垃圾回收][自动无用内存单元回收]相关读物
其中ガベージコレクションのアルゴリズムと実装这本书有对几种语言实现里的GC做源码剖析,值得一读。书是日文的,不过我有在推动国内出版社引进和翻译它。请期待它的中文版的面世。
前面回答者@RednaxelaFX 从事JVM研发工作,对虚拟机理解很深,但往往超出多数Java工程师的理解与工作范畴。

下面我从一段代码来分析整个过程,并结合模型图来简易讲解,希望能让大家对彻底明白。

在正式回答这个问题之前,先简单说说 Java运行时内存区,划分为线程私有区和线程共享区:
  • (1)线程私有区:
    • 程序计数器,记录正在执行的虚拟机字节码的地址;
    • 虚拟机栈:方法执行的内存区,每个方法执行时会在虚拟机栈中创建栈帧;
    • 本地方法栈:虚拟机的Native方法执行的内存区;
  • (2)线程共享区:
    • Java堆:对象分配内存的区域,这是垃圾回收的主战场;
    • 方法区:存放类信息、常量、静态变量、编译器编译后的代码等数据,另外还有一个常量池。当然垃圾回收也会在这个区域工作。
有兴趣进一步了解的,可查看我的博文 Jvm内存模型

---------------------------------------------分割线 进入正题----------------------------------------------------

目前虚拟机基本都是采用可达性算法,为什么不采用引用计数算法呢?下面就说说引用计数法是如何统计所有对象的引用计数的,再对比分析可达性算法是如何解决引用技术算法的不足。先简单说说这两个算法:

  • 引用计数算法reference-counting) :每个对象有一个引用计数器,当对象被引用一次则计数器加1,当对象引用失效一次则计数器减1,对于计数器为0的对象意味着是垃圾对象,可以被GC回收。
  • 可达性算法(GC Roots Tracing):从GC Roots作为起点开始搜索,那么整个连通图中的对象便都是活对象,对于GC Roots无法到达的对象便成了垃圾回收的对象,随时可被GC回收。
采用引用计数算法的系统只需在每个实例对象创建之初,通过计数器来记录所有的引用次数即可。而可达性算法,则需要再次GC时,遍历整个GC根节点来判断是否回收。

下面通过一段代码来对比说明:
 public class GcDemo {

    public static void main(String[] args) {
        //分为6个步骤
        GcObject obj1 = new GcObject(); //Step 1
        GcObject obj2 = new GcObject(); //Step 2

        obj1.instance = obj2; //Step 3
        obj2.instance = obj1; //Step 4

        obj1 = null; //Step 5
        obj2 = null; //Step 6
    }
}

class GcObject{
    public Object instance = null;
}

很多文章以及Java虚拟机相关的书籍,都会告诉你如果采用引用计数算法,上述代码中obj1和obj2指向的对象已经不可能再被访问,彼此互相引用对方导致引用计数都不为0,最终无法被GC回收,而可达性算法能解决这个问题。

但这些文章和书籍并没有真正从内存角度来阐述这个过程是如何统计的,很多时候大家都在相互借鉴、翻译,却也都没有明白。或者干脆装作讲明白,或者假定读者依然明白。 其实很多人并不明白为什么引用计数法不为0,引用计数到底是如何维护所有对象引用的,可达性是如何可达的? 接下来结合实例,从Java内存模型以及数学的图论知识角度来说明,希望能让大家彻底明白该过程。

情况
(一)引用计数算法
如果采用的是引用计数算法:

再回到前面代码GcDemo的main方法共分为6个步骤:
  • Step1:GcObject实例1的引用计数加1,实例1的引用计数=1;
  • Step2:GcObject实例2的引用计数加1,实例2的引用计数=1;
  • Step3:GcObject实例2的引用计数再加1,实例2的引用计数=2;
  • Step4:GcObject实例1的引用计数再加1,实例1的引用计数=2;
执行到Step 4,则GcObject实例1和实例2的引用计数都等于2。

接下来继续结果图:

  • Step5:栈帧中obj1不再指向Java堆,GcObject实例1的引用计数减1,结果为1;
  • Step6:栈帧中obj2不再指向Java堆,GcObject实例2的引用计数减1,结果为1。
到此,发现GcObject实例1和实例2的计数引用都不为0,那么如果采用的引用计数算法的话,那么这两个实例所占的内存将得不到释放,这便产生了内存泄露。

情况(二):可达性算法
这是目前主流的虚拟机都是采用GC Roots Tracing算法,比如Sun的Hotspot虚拟机便是采用该算法。 该算法的核心算法是从GC Roots对象作为起始点,利用数学中图论知识,图中可达对象便是存活对象,而不可达对象则是需要回收的垃圾内存。这里涉及两个概念,一是GC Roots,一是可达性。

那么可以作为GC Roots的对象(见下图):
  • 虚拟机栈的栈帧的局部变量表所引用的对象;
  • 本地方法栈的JNI所引用的对象;
  • 方法区的静态变量和常量所引用的对象;
关于可达性的对象,便是能与GC Roots构成连通图的对象,如下图:


从上图,reference1、reference2、reference3都是GC Roots,可以看出:
  • reference1-> 对象实例1;
  • reference2-> 对象实例2;
  • reference3-> 对象实例4;
  • reference3-> 对象实例4 -> 对象实例6;
可以得出对象实例1、2、4、6都具有GC Roots可达性,也就是存活对象,不能被GC回收的对象。
而对于对象实例3、5直接虽然连通,但并没有任何一个GC Roots与之相连,这便是GC Roots不可达的对象,这就是GC需要回收的垃圾对象。

到这里,相信大家应该能彻底明白引用计数算法和可达性算法的区别吧

再回过头来看看最前面的实例,GcObject实例1和实例2虽然从引用计数虽然都不为0,但从可达性算法来看,都是GC Roots不可达的对象。

总之,对于对象之间循环引用的情况,引用计数算法,则GC无法回收这两个对象,而可达性算法则可以正确回收。

看完觉得可以,也请点个赞啊,画图容易么!O(∩_∩)O~