JVM深入笔记（3）垃圾标记算法

Author: Poechant
Blog: blog.CSDN.net/Poechant
Email: zhongchao.ustc#gmail.com (#->@)
Date: March 3^rd, 2012
Copyright © 柳大·Poechant

如果您还不了解 JVM 的基本概念和内存划分，请先阅读《JVM 深入笔记（1）内存区域是如何划分的？》一文。然后再回来 :)

因为 Java 中没有留给开发者直接与内存打交道的指针（C++工程师很熟悉），所以如何回收不再使用的对象的问题，就丢给了 JVM。所以下面就介绍一下目前主流的垃圾收集器所采用的算法。不过在此之前，有必要先讲一下 Reference。

1 引用（Reference）

你现在还是 JDK 1.0 或者 1.1 版本的开发者吗？如果是的话，可以告诉你跳过“5 Reference”这一部分吧，甚至跳过本文。如果不是的话，下面这些内容还是有参考价值的。你可能会问，Reference 还有什么可讲的？还是有一点的，你知道 Reference 有四种分类吗？这可不是孔乙己的四种“回”字写法可以类比的。说引用，我们最先想到的一般是：

Object obj = new Object();

这种属于 Strong Reference（JDK 1.2 之后引入），这类 ref 的特点就是，只要 ref 还在，目标对象就不能被干掉。我们可以想一下为什么要干掉一些对象？很简单，因为内存不够了。如果内存始终够用，大家都活着就好了。所以当内存不够时，会先干掉一些“必死无疑的家伙”（下面会解释），如果这时候内存还不够用，就该干掉那些“可死可不死的家伙”了。

JDK 1.2 之后还引入了 SoftReference 和 WeakReference，前者就是那些“可死可不死的家伙”。当进行了一次内存清理（干掉“必死无疑”的家伙）后，还是不够用，就再进行一次清理，这次清理的内容就是 SoftReference 了。如果干掉 Soft Reference 后还是不够用，JVM 就抛出 OOM 异常了。

好像 WeakReference 还没说呢？它是干嘛的？其实它就是那些“必死无疑的家伙”。每一次 JVM 进行清理时，都会将这类 ref 干掉。所以一个 WeakReference 出生后，它的死期，就是下一次 JVM 的清理。

“回”字的最后一种写法，是 PhantomReference，名字很恐怖吧（Phantom是鬼魂的意思，不仅含义恐怖，而且发音也恐怖——“坟头”）。这类 ref 的唯一作用，就是当相应的 Object 被 clean 掉的时候，通知 JVM。

虽然有四种“回”字，但是 Strong Reference 却没有相应的类，java.lang.ref.Reference 只有三个子类。

你可能会发现，在 Reference 这一部分，我经常性地提到“清理”。什么“清理”？就是下面要说的 Garbage Collection 中对”无用”对象的 clean。

这是 JVM 的核心功能之一，同时也是为什么绝大多数 Java 工程师不需要像 C++ 程序员那样考虑对象的生存期问题。至于因此而同时导致 Java 工程师不能够放任*地控制内存的结果，其实是一个 Freedom 与 Effeciency 之间的 trade-off，而 C++ 工程师与 Java 工程师恰如生存在两个国度的人，好像“幸福生活”的天朝人民与“水深火热”的西方百姓之间的“时而嘲笑、时而艳羡”一般。

言归正传，Garbage Collector（GC）是 JVM 中筛选并清理 Garbage 的工具。那么第一个要搞清楚的问题是，什么是 Garbage？严谨的说，Garbage 就是不再被使用、或者认为不再被使用、甚至是某些情况下被选作“牺牲品”的对象。看上去很罗嗦，那就先理解成“不再被使用”吧。这就出现了第二个问题，怎么判断不再被使用？这就是下面首先要介绍的 Object Marking Algorithms。

2 对象标记算法（Object Marking Algorithms）

下面还是先从本质一点的东西开始说吧。一个对象变得 useless 了，其实就是它目前没有称为任何一个 reference 的 target，并且认为今后也不会成为（这是从逻辑上说，实际上此刻没有被引用的对象，今后也没有人会去引用了⋯⋯）

2.1 引用计数法（Reference Counting）

核心思想：很简单。每个对象都有一个引用计数器，当在某处该对象被引用的时候，它的引用计数器就加一，引用失效就减一。引用计数器中的值一旦变为0，则该对象就成为垃圾了。但目前的 JVM 没有用这种标记方式的。为什么呢？

因为引用计数法无法解决循环引用（对象引用关系组成“有向有环图”的情况，涉及一些图论的知识，在根搜索算法中会解释）的问题。比如下面的例子：

package com.sinosuperman.jvm;class _1MB_Data {    public Object instance = null;    private byte[] data = new byte[1024 * 1024 * 1];}public class CycledReferenceProblem {    public static void main(String[] args) {        _1MB_Data d1 = new _1MB_Data();        _1MB_Data d2 = new _1MB_Data();        d1.instance = d2;        d2.instance = d1;        d1 = null;        d2 = null;        System.gc();    }}

在这个程序中，首先在堆内存中创建了两个 1MB 大小的对象，并且其中分别存储的 instance 成员引用了对方。那么即使 d1和 d2 被置为 null 时，引用数并没有变为零。如果这是采用引用计数法来标记的话，内存就被浪费了，gc 的时候不会被回收。好悲催啊 :(

重复一下在《JVM 深入笔记（1）内存区域是如何划分的？》中提到的运行环境：

**Mac OS X 10.7.3**，**JDK 1.6.0   Update 29**，**Oracle Hot Spot 20.4-b02**。

那么我们来试试Oracle Hot Spot 20.4-b02是不是采用引用计数法来标记的。对了，别忘了为CycledReferenceProblem使用的虚拟机开启-XX:+PrintGCDetails参数，然后运行结果如下：

[Full GC (System) [CMS: 0K->366K(63872K), 0.0191521 secs] 3778K->366K(83008K), [CMS Perm : 4905K->4903K(21248K)], 0.0192274 secs] [Times: user=0.03 sys=0.00, real=0.02 secs] Heap par new generation   total 19136K, used 681K [7f3000000, 7f44c0000, 7f44c0000)  eden space 17024K,   4% used [7f3000000, 7f30aa468, 7f40a0000)  from space 2112K,   0% used [7f40a0000, 7f40a0000, 7f42b0000)  to   space 2112K,   0% used [7f42b0000, 7f42b0000, 7f44c0000) concurrent mark-sweep generation total 63872K, used 366K [7f44c0000, 7f8320000, 7fae00000) concurrent-mark-sweep perm gen total 21248K, used 4966K [7fae00000, 7fc2c0000, 800000000)

可以看到，在Full GC时，清理掉了 (3778-366)KB=3412KB 的对象。这一共有 3MB 多，可以确定其中包括两个我们创建的 1MB 的对象吗？貌似无法确定。好吧，那下面我们使用_2M_Data对象来重复上面的程序。

package com.sinosuperman.jvm;class _2MB_Data {    public Object instance = null;    private byte[] data = new byte[1024 * 1024 * 2];}public class CycledReferenceProblem {    public static void main(String[] args) {        _2MB_Data d1 = new _2MB_Data();        _2MB_Data d2 = new _2MB_Data();        d1.instance = d2;        d2.instance = d1;        d1 = null;        d2 = null;        System.gc();    }}

运行结果如下：

[Full GC (System) [CMS: 0K->366K(63872K), 0.0185981 secs] 5826K->366K(83008K), [CMS Perm : 4905K->4903K(21248K)], 0.0186886 secs] [Times: user=0.04 sys=0.00, real=0.02 secs] Heap par new generation   total 19136K, used 681K [7f3000000, 7f44c0000, 7f44c0000)  eden space 17024K,   4% used [7f3000000, 7f30aa4b0, 7f40a0000)  from space 2112K,   0% used [7f40a0000, 7f40a0000, 7f42b0000)  to   space 2112K,   0% used [7f42b0000, 7f42b0000, 7f44c0000) concurrent mark-sweep generation total 63872K, used 366K [7f44c0000, 7f8320000, 7fae00000) concurrent-mark-sweep perm gen total 21248K, used 4966K [7fae00000, 7fc2c0000, 800000000)

这次清理掉了 (5826-366)=5460KB 的对象。我们发现两次清理相差 2048KB，刚好是 2MB，也就是 d1 和 d2 刚好各相差 1MB。我想这可以确定，gc 的时候确实回收了两个循环引用的对象。如果你还不信，可以再试试 3MB、4MB，都是刚好相差 2MB。

这说明Oracle Hot Spot 20.4-b02虚拟机并不是采用引用计数方法。事实上，现在没有什么流行的 JVM 会去采用简陋而问题多多的引用计数法来标记。不过要承认，它确实简单而且大多数时候有效。

那么，这些主流的 JVM 都是使用什么标记算法的呢？

2.2. 根搜索算法（Garbage Collection Roots Tracing）

对，没错，就是“根搜索算法”。我来介绍以下吧。

2.2.1 基本思想

其实思路也很简单（算法领域，除了红黑树、KMP等等比较复杂外，大多数思路都很简单），可以概括为如下几步：

选定一些对象，作为 GC Roots，组成基对象集（这个词是我自己造的，与其他文献资料的说法可能不一样。但这无所谓，名字只是个代号，理解算法内涵才是根本）；
由基对象集内的对象出发，搜索所有可达的对象；
其余的不可达的对象，就是可以被回收的对象。

这里的“可达”与“不可达”与图论中的定义一样，所有的对象被看做点，引用被看做有向连接，整个引用关系就是一个有向图。在“引用计数法”中提到的循环引用，其实就是有向图中有环的情况，即构成“有向有环图”。引用计数法不适用于“有向有环图”，而根搜索算法适用于所有“有向图”，包括有环的和无环的。那么是如何解决的呢？

2.2.2 GC Roots

如果你的逻辑思维够清晰，你会说“一定与选取基对象集的方法有关”。是的，没错。选取 GC Roots 组成基对象集，其实就是选取如下这些对象：

《深入理解 Java 虚拟机：JVM 高级特性与最佳实践》一书中提到的 GC Roots 为：

方法区（Method Area，即 Non-Heap）中的类的 static 成员引用的对象，和 final 成员引用的对象；
Java 方法栈（Java Method Stack）的局部变量表（Local Variable Table）中引用的对象；
原生方法栈（Native Method Stack）中 JNI 中引用的对象。

但显然不够全面，[参考2]中提到的要更全面：（March 6^th,2012 update）

由系统类加载器加载的类相应的对象：这些类永远不会被卸载，且这些类创建的对象都是 static 的。注意用户使用的类加载器加载的类创建的对象，不属于 GC Roots，除非是 java.lang.Class 的相应实例有可能会称为其他类的 GC Roots。
正在运行的线程。
Java 方法栈（Java Method Stack）的局部变量表（Local Variable Table）中引用的对象。
原生方法栈（Native Method Stack）的局部变量表（Local Variable Table）中引用的对象。
JNI 中引用的对象。
同步监控器使用的对象。
由 JVM 的 GC 控制的对象：这些对象是用于 JVM 内部的，是实现相关的。一般情况下，可能包括系统类加载器（注意与“1”不一样，“1”中是 objects created by the classes loaded by system class loaders，这里是 the objects, corresponding instances of system class loaders）、JVM 内部的一些重要的异常类的对象、异常句柄的预分配对象和在类加载过程中自定义的类加载器。不幸的是，JVM 并不提供这些对象的任何额外的详细信息。因此这些实现相关的内容，需要依靠分析来判定。

所以这个算法实施起来有两部分，第一部分就是到 JVM 的几个内存区域中“找对象”，第二部分就是运用图论算法。

3. 废话

JVM 的标记算法并不是 JVM 垃圾回收策略中最重要的。真正的核心，是回收算法，当然标记算法是基础。如果你想复习一下前两篇文章，链接在这里：

参考

http://www.yourkit.com/docs/10/help/gc_roots.jsp
《深入理解 Java 虚拟机：JVM 高级特性与最佳实践》周志明(著)，机械工业出版社

如果这篇文章帮助到了您，欢迎您到我的博客留言，我会很高兴的。

转载请注明来自“柳大的CSDN博客”：blog.csdn.net/Poechant

秒客网

JVM 深入笔记（3）垃圾标记算法