JVM 深入笔记（3）垃圾标记算法
JVM 深入笔记（3）垃圾标记算法- Author: Poechant
- Blog:?blog.CSDN.net/Poechant
- Email: zhongchao.ustc#gmail.com (#->@)
- Date: March 3rd, 2012
如果您还不了解 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）
对，没错，就是“跟搜索算法”。我来介绍以下吧。
其实思路也很简单（算法领域，除了红黑树、KMP等等比较复杂外，大多数思路都很简单），可以概括为如下几步：
- 选定一些对象，作为 GC Roots，组成基对象集（这个词是我自己造的，与其他文献资料的说法可能不一样。但这无所谓，名字只是个代号，理解算法内涵才是根本）；
- 由基对象集内的对象出发，搜索所有可达的对象；
- 其余的不可达的对象，就是可以被回收的对象。
这里的“可达”与“不可达”与图论中的定义一样，所有的对象被看做点，引用被看做有向连接，整个引用关系就是一个有向图。在“引用计数法”中提到的循环引用，其实就是有向图中有环的情况，即构成“有向有环图”。引用计数法不适用于“有向有环图”，而根搜索算法适用于所有“有向图”，包括有环的和无环的。那么是如何解决的呢？
如果你的逻辑思维够清晰，你会说“一定与选取基对象集的方法有关”。是的，没错。选取 GC Roots 组成基对象集，其实就是选取如下这些对象：
- 方法区（Method Area，即 Non-Heap）中的类的 static 成员引用的对象，和 final 成员引用的对象；
- Java 方法栈（Java Method Stack）的局部变量表（Local Variable Table）中引用的对象；
- 原生方法栈（Native Method Stack）中 JNI 中引用的对象。
所以这个算法实施起来有两部分，第一部分就是到 JVM 的几个内存区域中“找对象”，第二部分就是运用图论算法。
3. 废话
JVM 的标记算法并不是 JVM 垃圾回收策略中最重要的。真正的核心，是回收算法，当然标记算法是基础。如果你想复习一下前两篇文章，链接在这里：
JVM 深入笔记（1）内存区域是如何划分的？JVM 深入笔记（2）各内存区溢出场景模拟JVM 深入笔记（3）垃圾标记算法
-
如果这篇文章帮助到了您，欢迎您到我的博客留言，我会很高兴的。
转载请注明来自“柳大的CSDN博客”：blog.csdn.net/Poechant
-
1 楼 zx246212 2012-03-06 LZ写的好哇，再问个，GC一般选取多少个基类呢？如果一个大的项目，有很多的类在内存中，只选取一部分的话，肯定会有正在使用的对象被回收掉，请问GC有类似于第二次审核动作么？ 还是遇到这种情况，直接new对象！ 2 楼 Poechant 2012-03-06 zx246212 写道LZ写的好哇，再问个，GC一般选取多少个基类呢？如果一个大的项目，有很多的类在内存中，只选取一部分的话，肯定会有正在使用的对象被回收掉，请问GC有类似于第二次审核动作么？ 还是遇到这种情况，直接new对象！
你好，首先要明确的是在选择基对象集（roots collection）的时候，选择的不是类（how many classes），而是对象（how many objects）。JVM 不会限制你 roots 的数量，只要满足一定要求，就都是 roots，而这些“要求”已经在文中最后部分提到。
也就是说，当这种充当 roots 的对象特别多的时候，你一定会遭遇一些与内存有关的错误。你可以参见这篇文章：
《JVM 深入笔记（2）内存区溢出场景模拟》
http://poechant.iteye.com/blog/1439361
里面提供了一些关于内存溢出的模拟。对应到这里，就分别是：
（1）运行时常量池内存溢出
（2）Java 方法栈溢出：局部变量表过大造成
（3）原生方法栈溢出：局部变量表过大造成，对于目前的Oracle JVM HotSpot，原生方法栈与Java方法栈是同一块内存区，可参见下面这篇文章：
《JVM 深入笔记（1）内存区域是如何划分的？》
http://poechant.iteye.com/blog/1438286
:)
柳大
如果您还不了解 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）
对，没错，就是“跟搜索算法”。我来介绍以下吧。
其实思路也很简单（算法领域，除了红黑树、KMP等等比较复杂外，大多数思路都很简单），可以概括为如下几步：
- 选定一些对象，作为 GC Roots，组成基对象集（这个词是我自己造的，与其他文献资料的说法可能不一样。但这无所谓，名字只是个代号，理解算法内涵才是根本）；
- 由基对象集内的对象出发，搜索所有可达的对象；
- 其余的不可达的对象，就是可以被回收的对象。
这里的“可达”与“不可达”与图论中的定义一样，所有的对象被看做点，引用被看做有向连接，整个引用关系就是一个有向图。在“引用计数法”中提到的循环引用，其实就是有向图中有环的情况，即构成“有向有环图”。引用计数法不适用于“有向有环图”，而根搜索算法适用于所有“有向图”，包括有环的和无环的。那么是如何解决的呢？
如果你的逻辑思维够清晰，你会说“一定与选取基对象集的方法有关”。是的，没错。选取 GC Roots 组成基对象集，其实就是选取如下这些对象：
- 方法区（Method Area，即 Non-Heap）中的类的 static 成员引用的对象，和 final 成员引用的对象；
- Java 方法栈（Java Method Stack）的局部变量表（Local Variable Table）中引用的对象；
- 原生方法栈（Native Method Stack）中 JNI 中引用的对象。
所以这个算法实施起来有两部分，第一部分就是到 JVM 的几个内存区域中“找对象”，第二部分就是运用图论算法。
3. 废话
JVM 的标记算法并不是 JVM 垃圾回收策略中最重要的。真正的核心，是回收算法，当然标记算法是基础。如果你想复习一下前两篇文章，链接在这里：
JVM 深入笔记（1）内存区域是如何划分的？
JVM 深入笔记（2）各内存区溢出场景模拟
JVM 深入笔记（3）垃圾标记算法
-
如果这篇文章帮助到了您，欢迎您到我的博客留言，我会很高兴的。
转载请注明来自“柳大的CSDN博客”：blog.csdn.net/Poechant
-
1 楼 zx246212 2012-03-06 LZ写的好哇，再问个，GC一般选取多少个基类呢？如果一个大的项目，有很多的类在内存中，只选取一部分的话，肯定会有正在使用的对象被回收掉，请问GC有类似于第二次审核动作么？ 还是遇到这种情况，直接new对象！ 2 楼 Poechant 2012-03-06 zx246212 写道LZ写的好哇，再问个，GC一般选取多少个基类呢？如果一个大的项目，有很多的类在内存中，只选取一部分的话，肯定会有正在使用的对象被回收掉，请问GC有类似于第二次审核动作么？ 还是遇到这种情况，直接new对象！
你好，首先要明确的是在选择基对象集（roots collection）的时候，选择的不是类（how many classes），而是对象（how many objects）。JVM 不会限制你 roots 的数量，只要满足一定要求，就都是 roots，而这些“要求”已经在文中最后部分提到。
也就是说，当这种充当 roots 的对象特别多的时候，你一定会遭遇一些与内存有关的错误。你可以参见这篇文章：
《JVM 深入笔记（2）内存区溢出场景模拟》
http://poechant.iteye.com/blog/1439361
里面提供了一些关于内存溢出的模拟。对应到这里，就分别是：
（1）运行时常量池内存溢出
（2）Java 方法栈溢出：局部变量表过大造成
（3）原生方法栈溢出：局部变量表过大造成，对于目前的Oracle JVM HotSpot，原生方法栈与Java方法栈是同一块内存区，可参见下面这篇文章：
《JVM 深入笔记（1）内存区域是如何划分的？》
http://poechant.iteye.com/blog/1438286
:)
柳大