垃圾回收算法

自动内存管理(Automated Memory Management)

上面的C++代码中,我们要显式地声明什么时候需要进行内存管理。但不能让所有的对象都具备这种特征呢? 那样就太方便了, 开发者不再耗费脑细胞, 去考虑要在何处进行内存清理。运行时环境会自动算出哪些内存不再使用,并将其释放。换句话说, 自动进行收集垃圾。第一款垃圾收集器是1959年为Lisp语言开发的, 此后 Lisp 的垃圾收集技术也一直处于业界领先水平。

引用计数(Reference Counting)

刚刚演示的C++共享指针方式, 可以应用到所有对象。许多语言都采用这种方法, 包括 Perl、Python 和 PHP 等。下图很好地展示了这种方式:

01_01_Java-GC-counting-references1.png

图中绿色的云(GC ROOTS) 表示程序正在使用的对象。从技术上讲, 这些可能是当前正在执行的方法中的局部变量,或者是静态变量一类。在某些编程语言中,可能叫法不太一样,这里不必抠名词。

蓝色的圆圈表示可以引用到的对象, 里面的数字就是引用计数。然后, 灰色的圆圈是各个作用域都不再引用的对象。灰色的对象被认为是垃圾, 随时会被垃圾收集器清理。

看起来很棒, 是吧! 但这种方式有个大坑, 很容易被循环引用(detached cycle) 给搞死。任何作用域中都没有引用指向这些对象,但由于循环引用, 导致引用计数一直大于零。如下图所示:

01_02_Java-GC-cyclical-dependencies.png

看到了吗? 红色的对象实际上属于垃圾。但由于引用计数的局限, 所以存在内存泄漏。

当然也有一些办法来应对这种情况, 例如 “弱引用”(‘weak’ references), 或者使用另外的算法来排查循环引用等。前面提到的 Perl、Python 和PHP 等语言, 都使用了某些方式来解决循环引用问题, 但本文不对其进行讨论。下面介绍JVM中使用的垃圾收集方法。

可达性分析法

在主流的商用程序语言(Java、C#)的主流实现中,都是通过可达性分析来判定对象是否存活的。这个算法的基本思路就是通过一系列的称为”GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots没有任何引用链相连时,则证明此对象是不可用的。


image.png

在Java语言中,可作为GC Roots的对象包括:

  • 虚拟机栈(栈帧中的本地变量表)中的引用对象
  • 方法区中类静态属性引用的对象
  • 方法区中常量引用的对象
  • 本地方法栈中JNI(即一般说的Native方法)引用对象

Java中的引用

判定对象是否存活都与”引用”有关,在JDK 1.2之后,Java对引用的概念进行了扩充,将引用分为强引用(Strong Reference)、软引用(Soft Reference)、弱引用(Weak Reference)、虚引用(Phantom Reference)4种,这4种引用强度依次逐渐减弱

  • 强引用就是指程序代码中普通存在的,类似”Object obj = new Object()”这类的引用,只要强引用还存在,垃圾收集器永远不会回收掉被引用的对象
  • 软引用是用来描述一些还有用但并非必需的对象,对于软引用关联着的对象,在系统将要发生内存溢出异常之前,将会把 这些对象列进回收范围之中进行第二次回收
  • 弱引用也是用来描述非必需对象的,但是它的强度比软引用更弱一些,被弱引用关联的对象只能生存到下一次垃圾收集发生之前,当垃圾收集器工作时,无论当前内存是否足够,都会回收掉只被弱引用关联的对象
  • 虚引用是最弱的一种引用关系,无法通过虚引用来取得一个对象实例,为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知

什么时候回收?

如果对象在进行可达性分析后发现没有与GC Roots相连接的引用链,那它将会被第一次标记并且进行一次筛选,筛选的条件是此对象是否有必要执行finalize()方法。当对象没有覆盖finalize()方法,或finalize()方法已经被虚拟机调用过,虚拟机将这两种情况都视为”没有必要执行”

如果这个对象被判断为有必要执行finalize()方法, 那么找个对象会放置在一个叫做F-Queue的队列中,并在稍后由一个虚拟机自动建立的、低优先级的Finalizer线程去执行它,这里所谓的”执行”是指虚拟机会触发这个方法,但并不承诺会等待它运行结束,这样做的原因是,如果一个对象在finalize()方法中执行缓慢,或者发生了死循环,将很可能会导致F-Queue队列中其他对象永久处于等待,甚至导致整个内存回收系统崩溃。

finalize()方法是对象逃脱死亡命运的最后一次机会,稍后GC将对F-Queue中的对象进行第二次小规模的标记,如果对象要在finalize()中成功拯救自己——只要重新与引用链上任何一个对象建立关联即可,譬如把自己(this关键字)赋值给某个类变量或者对象的成员变量,那在第二次标记时它将被移除出”即将回收”的集合,如果对象这时候还没有逃脱,那基本上它就真的被回收了

注意:任何一个对象的finalize()方法都只会被系统自动调用一次,如果对象面临下一次回收,它的finalize()方法不会被再次执行

回收方法区

Java虚拟机规范中不要求虚拟机在方法区实现垃圾收集,而且在方法区中进行垃圾收集的”性价比”一般比较低,在堆中,尤其是在新生代中,常规应用进行一次垃圾收集一般可以回收70%~95%的空间,而永久代的垃圾收集效率远低于此。
永久代的垃圾收集主要回收两部分内容:废弃常量和无用的类,回收废弃常量与回收Java堆中的对象非常类似,判定一个常量是否是”废弃常量”比较简单”(只要其他地方没有引用这个字面量),而要判定一个类是否是”无用的类”的条件要相对苛刻许多,需同时满足

  • 该类所有的实例都已经被回收,也就是Java堆中不存在该类的任何实例
  • 加载该类的ClassLoader已经被回收
  • 该类对象的java.lang.Class对象没有在任何地方被引用,无法在任何地方通过反射访问该类的方法
    以上3个条件才”可以”被回收。

如何回收

标记-清除(Mark and Sweep)

首先, JVM 明确定义了什么是对象的可达性(reachability)。我们前面所说的绿色云这种只能算是模糊的定义, JVM 中有一类很明确很具体的对象, 称为 垃圾收集根元素(Garbage Collection Roots),包括:

  • 局部变量(Local variables)
  • 活动线程(Active threads)
  • 静态域(Static fields)
  • JNI引用(JNI references)
  • 其他对象(稍后介绍 …)

JVM使用标记-清除算法(Mark and Sweep algorithm), 来跟踪所有的可达对象(即存活对象), 确保所有不可达对象(non-reachable objects)占用的内存都能被重用。其中包含两步:

  • Marking(标记): 遍历所有的可达对象,并在本地内存(native)中分门别类记下。

  • Sweeping(清除): 这一步保证了,不可达对象所占用的内存, 在之后进行内存分配时可以重用。

    image.png

JVM中包含了多种GC算法, 如Parallel Scavenge(并行清除), Parallel Mark+Copy(并行标记+复制) 以及 CMS, 他们在实现上略有不同, 但理论上都采用了以上两个步骤。
标记-清除-压缩(Mark-Sweep-Compact)
将所有被标记的对象(存活对象), 迁移到内存空间的起始处, 消除了标记-清除算法的缺点。 相应的缺点就是GC暂停时间会增加, 因为需要将所有对象复制到另一个地方, 然后修改指向这些对象的引用。此算法的优势也很明显, 碎片整理之后, 分配新对象就很简单, 只需要通过指针碰撞(pointer bumping)即可。使用这种算法, 内存空间剩余的容量一直是清楚的, 不会再导致内存碎片问题。

image.png

标记-复制算法(Mark and Copy)
标记-整理算法(Mark and Compact) 十分相似: 两者都会移动所有存活的对象。区别在于, 标记-复制算法是将内存移动到另外一个空间: 存活区。标记-复制方法的优点在于: 标记和复制可以同时进行。缺点则是需要一个额外的内存区间, 来存放所有的存活对象。

image.png

标记清除算法最重要的优势, 就是不再因为循环引用而导致内存泄露:


01_03_Java-GC-mark-and-sweep.png

而不好的地方在于, 垃圾收集过程中, 需要暂停应用程序的所有线程。假如不暂停,则对象间的引用关系会一直不停地发生变化, 那样就没法进行统计了。这种情况叫做 STW停顿(Stop The World pause, 全线暂停), 让应用程序暂时停止,让JVM进行内存清理工作。有很多原因会触发 STW停顿, 其中垃圾收集是最主要的因素。

在本手册中,我们将介绍JVM中垃圾收集的实现原理,以及如何高效地利用GC。
请继续阅读下一章:
2. Java中的垃圾收集 - GC参考手册
原文链接: What Is Garbage Collection?
翻译人员: 铁锚 http://blog.csdn.net/renfufei
翻译时间: 2015年10月26日
参考:
[1]. http://cmsblogs.com/?p=3776
[2]. http://blog.sina.com.cn/s/blog_df25c55f0102wxh3.html

推荐阅读更多精彩内容