Java虚拟机垃圾回收技术
1 概述
垃圾回收技术是一个充满矛盾的技术：它有悠久的历史，在20世纪60年，在LISP语言中就开始进行应用，而后的smaltalk，effiel，Java，.NET等 语言更是一步一步地将其推向新的高潮。它广受技术专家的推崇，并被高度的评价，被认为是提高软件质量和生产力的一个有效的银弹，是一个具有不亚于从汇编语 言到高级语言的革命性技术。但另外一个方面，垃圾回收技术始终跟低效率关联在一起，直到今天还在接受众多的咒骂，并成为继续扩展推广的一个巨大阻力。
这一点在Java上尤其获得了验证，实际上，Java的广为成功的应用在相当大的一个程度上与GC技术有关，从而保证了在Java程序中不再存在万恶的非法内存访问错误，极大地提高了开发人员的生产力。可以这么说，在Java时代成长的技术人员，将很难在回到C/C++编程的时代，忍受内存管理给你带来的巨大复杂性和精神的折磨。这一点无论是对于专家、高手还是初学者，都是完全一致的。但另外一方面，Java最被人攻击的两个角度：速度慢、消耗内存太大实际上都跟GC有着密切的关系，现代的编译技术已经能够保证对Java字节码的执行速度，能够尽可能的接近C/C++的执行速度（但Java提供一些更高的语义和安全检查），甚至借助于AdaptiveCompiler技术，在很多方面能够超越C/C++的静态编译的效果，GC技术仍然在相当的程度上阻碍了Java的执行效率，或者带来了不可接受的障碍。
举个例子，Java在桌面端的发展极为缓慢，Swing技术更是被广为评击，原因有二：内存消耗太大，没有
实际上，自1995年Java诞生以来，从JDK1.0到最新的JDK5.0，在垃圾回收技术上已经有了相当的改进，这种改进导致了Java的广泛成功，包括在服务器端的高度成功（因为服务器有更多的内存，也可以接受更长的停顿时间，只要总体处理能力还可以的话），在桌面端的局部成功（应该说，还没有完全失败，至少还有像eclipse、jbuilder、甚至于过国产的永中Office等应用）。据了解，新的GC技术也在Internet上广泛的获得研究，并有望把GC的效率、性能提高到一个更高的档次，这个或许可以等到JDK6.0（Mustang）或者更后的版本中得到质的突破，也许到了那个时候，Java真的就象野马一样，快速、狂野。
了解GC的主要概念，算法，对于开发Java来说，可能不会直接或者快速的受益，但可以帮助我们更好的认识高效率编写Java应用的方式，同时，可以帮助我们解决在Java中存在的Memory Leak的问题。在产品性能调优阶段，更可以直接通过对GC的分析，发现应用中存在的瓶颈，从而采取相应的措施，提高GC的效率，达到提高应用的效率、吞吐能力的目的。但在本文中，我不会对这些问题展开讨论。
本文将以Sun Hotspot虚拟机为基础，介绍在Hotspot虚拟机中应用的GC技术，而后，在结合其他的一些GC技术，尤其是很可能在未来的GC技术进行介绍，力争给各位一个对各种GC技术的简要认识。
值得一提的是，一本专业的《垃圾回收》图书，已经由人民邮电出版社在国内出版发行了，该书对多种垃圾回收的算法有非常详细的阐述，是一本非常全面的介绍GC技术的著作，如果希望对垃圾回收算法的细节有更深入的了解，应当拜读该书籍。
另外，在Internet上有相当多的GC实现的源代码，可以通过研究、学习这些源代码来获得更多的GC研究，在此，我列举几个主要的项目：
1、IBM JikesRVM。http://www-124.ibm.com/developerworks/oss/jikesrvm/
JikesRVM是一个实验性质的JVM，最大的特色是这个虚拟机95%以上的代码是用Java编写的，其执行效率跟IBM JDK1.3基本相当，目前，已经可以运行eclipse等大型的Java应用。不到5%的代码是用C/C++编写的，但这些代码主要是处理根平台相关的东西，包括JVM的启动代码。
由于代码采用Java实现，因此，Java程序员可以比较方便的阅读、理解，甚至对其修改。
2、SableVM http://sablevm.org/
SableVM是McGill大学计算机系的一个研究性质的JVM，其特点是教学性质的，采用优化的解释技术，原代码的结构、可读性非常强，便于进行JVM相关的研究。
3、Hotspot JVM。
Sun对Java的开放支持终于又迈开了一大步，现在大家可以在dev.java.net上下载、并参与到JDK6.0（Mustang）的开发中去。OpenSource的力量真的不是一家公司所能持有的，在Internet上有更多的技术精英，他们不需要Sun发薪水，却能给Java带来更多的技术，何乐而不为？
2 基本的GC技术
作为后续的GC算法的一个基础，本节将简要的介绍基本的GC算法，实际上，各种GC算法都是在这些基础算法上进行改良、组合的。因此，对这些基本算法的理解是基础。
2.1 引用计数
这种技术非常简单，也易于理解，在COM中就使用引用计数技术来维持COM对象的生命周期。
优点：
1、 在对象变成垃圾时，可以马上进行回收，回收的效率和成本都是最低。因此，内存使用率最高，基本上没有停顿时间。
缺点：
1、 引用计数会影响执行的效率，每次获得一个对象的引用（在Java中这种频率极高），都需要更新引用计数。
2、 无法解决环形引用对象的回收问题。比如说一个环形的双向链表，每一个节点都被前后接点引用，但可能整个链表已经成为垃圾。引用计数法无法解决这个问题。
2.2 Mark Sweep算法
最经典的GC算法，几乎在所有的GC中都有使用到，下面简要描述该算法(摘自《垃圾回收》)：
mark_sweep() =
for R in Roots
mark(R)
sweep()
mark(N) =
if mark_bit(N) == unmarked
mark_bit(N) = marked
for M in children(N)
mark(*M)
sweep() =
N = Heap_bottom
While N <>
If mark_bit(N) == unmarked
free(N)
else
mark_bit(N) == unmarked -- 复位
这个算法简单，易于理解，但时间效率和空间效率都不高，很少在实际的实现中直接使用（如果这样，GC也就太简单了）。
实际上，上述的算法只是一个最简单的实现，和原形的算法，在实际的GC设计中，会对这个算法进行一定的优化，最基本的，就是把Mark的实现从递归方式转变为迭代模式，从而避免对栈的深度使用导致的低效率和栈溢出。不过，这些优化是上面这个算法的数学变换而已，并没有概念上的区别。
2.3 SemiSpace Copy算法
SemiSpace Copy算法把整个的堆空间分为相等的两半，成为Fromspace和Tospace，对象总是在Tospace中分配，当Tospace使用完后，开始进行一次垃圾收集。
垃圾收集遍历Root集合，把对象复制到另一个空间中，并且把对象引用到的其他对象也复制到其他空间中，在复制过程中，垃圾收集需要维护一个对象的forward地址，这样，在别的对象中引用到原有的地址时，可以更新指向新的地址。
下面是这个算法的伪码表示：
init() =
Tospace = Heap_bottom -- 从这里分配对象
space_size = Heap_size / 2 -- 只使用1/2的堆空间
top_of_space = Tospace + space_size -- 可分配的结束地址
Fromspace = top_of_space -- 保留
free = Tospace -- 可分配的地址
New(n) =
If free + n > top_of_space -- 内存不够
flip()
if free + n > top_of_space
abort “OutOfMemory”
newcell = free -- 从free处分配对象
free = free + n
return newcell
flip() =
Fromspace, ToSpace = Tospace, Fromspace -- 现在，Fromspace中包含要GC的对象
top_of_space = ToSpace + space_size
free = Tospace
for R in Roots
R = copy(R) -- 把对象复制到Tospace中
copy(P) =
if not_forwarded(P)
n = size(P)
p’ = free -- 复制后的地址
free = free + n
forwarding_address(P) = P’
for M in children(P’)
M = copy(M)
return forwarding_address(P)
SemiSpace Copy算法最大的优势就是快速，尤其是当大部分的对象成为垃圾的情况下，此时，其时间开销基本上就是复制存活对象的开销。而外的优势是堆中的对象总是连续分配的，分配对象总是在堆的最上面进行，不需要搜索freelist，分配对象的开销跟堆栈中分配的开销是一样的。
其最大的缺点是：内存的利用率不高，在任何时候，都只能使用1/2的堆空间。衍生的缺点包括：如果存货的对象较多而且生命周期很长的话，这些对象会被反复的从一个半区复制到另外一个半区中，徒劳无功。这种情况对于很多的成熟对象而言是很明显的。
3 Hotspot中的GC算法
3.1 Hotspot虚拟机的内存管理
本文将以JDK1.4中的Hotspot虚拟机为例，介绍其GC算法。
Hotspot虚拟机是一个非常不错的产品，有关Hotspot虚拟机的历史，大家可以在李维的《Borland传奇》一书中获得很多有趣的故事。
Hotspot采用的对象内存模型如下：
1、Handless Object。
所有的对象引用是一个直接指向对象的指针，而不指向一个中间的句柄。这种做法在一定程度上加大了GC的开销（不便于移动对象），优势则是提高了对象的访问速度，也占用更少的内存。
2、2 Word Header
除了数组对象外，所有的对象都使用2个字的对象头。第一个字包含了hash信息和GC相关信息，第二个字指向对象的class对象。数组对象有第3个字，保存数组的长度。
3、Reflective Data Represents as Object
所有的Class、Method以及其他内部反射对象也是以对象的方式在Heap中分配管理，在GC上与普通的Java对象完全相同。既简化疗内存的管理，同时也使得这些内存也可以被垃圾回收。
4、精确回收。
在垃圾回收的策略上，有精确回收和保守回收两种策略，很多的JVM采 用保守策略：对堆栈或者寄存器中的值，它有可能是一个对象的指针，但也可能仅仅是一个整数、或者浮点数，或者是一个完全没有意义的数，保守策略则假定如果 这可能是一个对象的指针（因为它确实指向了一个分配的对象）的话，那么就保守的认为它是一个对象指针，虽然它可能只是一个整数，但碰巧具有跟这个指针相同 的值。（在Java中，我们不可能把一个整数转换成为一个指针，因此，即使存在这样的一个整数，理论上不应该阻止这个对象被回收）。而精确的策略则需要知道这个堆栈、寄存器的类型，如果他是一个对象指针的话，才能引用到相应的对象，具有相同值的整数是不会被当作对象指针的。
保守策略的一个不利因素是，如果一个对象被保守引用的话，那么这个对象是不能移动的，因为移动这个动向需要更新相应的指针，但一个保守引用可能根本不是一个引用，此时如果更新，则会带来语义上的错误：假设经过一次GC后，你的一个整数变量的值忽然变成了另外的一个值，那这个程序还可能正确执行吗？
Hotspot采用精确回收的策略，从而使得每一个对象在GC中可以根据需要进行移动，从而更好的对内存进行压缩，提高内存的使用效率。通过把相关的对象移动到一起，还可以提高程序的空间相关性，提高执行的速度。（Hotspot中的火车算法更加的利用一个技巧化的对象移动，从而实现一整块区域的对象集中的销毁，从而提高GC效率）。
3.2 分代GC
在Java等面向对象的语言中，由于不再使用C/C++中的全局变量、栈对象，换之，所有的对象都是在堆中分配的。但实际上，绝大部分的对象都只具备很短的生存时间，一般的，在一个方法中分配的对象，在这个方法结束后，这个对象就已经变成垃圾，而不会被别人使用了。
观察一个最简单的实例：
/**
* 在一个字符串中替换字符串
*/
public static String Replace(String oriStr,String findStr,String tagStr )
{
if(findStr.equals(""))
return oriStr;
java.util.Vector vv = new java.util.Vector();
while(true){
int pos = oriStr.indexOf(findStr);
if(pos == -1) break;
String part1 = oriStr.substring(0, pos);
String part2 = oriStr.substring(pos + findStr.length() );
vv.add(part1);
vv.add(tagStr);
findStr = part2
}
for(int i=0; i
str = str + vv.get(i);
return str;
}
在调用Replace这个方法中，除了最后返回的那个字符串对象在返回后仍然是存活的之外，其余所有的对象，包括vv，substring产生的新对象，str加操作产生的中间对象，都已经不再是存活的。对一个包含10个匹配替换的情况下，新的创建对象，新创建的对象数会超过80个，而存活的对象仅为1个。
根据应用的不同，这个比例会有所不同，大部分的应用中，50%到80%的对象都是具有这种特性的，其生存周期非常的短。
参考上述的SemiSpace Copy的算法，这种形式的对象最为适合采用Copy的方式来进行垃圾回收，因为垃圾回收的时间正比于存活的对象数量，而大部分的对象在短时间后就会变成垃圾，存活率非常低，因此，垃圾回收将会是高效率的。
在Hotspot虚拟机中，采用了分代式的垃圾回收技术，Hotspot将内存分为两个代：Tenured（成熟代）、Nurse（年轻代），对象总是在年青代中分配，当年轻代中不再有充足的内存来分配创建一个新的对象时，开始一次对年轻代的垃圾回收，此时，大部分的对象都已经成为垃圾，剩下的对象将仍然保留在年轻代中。
如果一个对象多次的存垃圾回收中存活下来，那么表明这个对象将会具有较长的生命周期，此时，对象将会移动到成熟代中，从而避免在后续的每次年轻代垃圾回收中对这个对象的多次复制。
图表 1：Hotspot虚拟机堆布局
上图是Hotspot中的堆空间的布局：
1、 Perm。永久代。这个代中保存所有的不需要进行垃圾回收的对象。在Java中，所有的从bootstrap及Classpath中装载的类是不会被垃圾回收的，这些对象（主要是Class对象及相应的虚拟机反射对象）被放置到Perm代中。Perm代不参与垃圾收集。
2、 Tenured。成熟代。成熟代中存储成熟的对象。对成熟代的一次垃圾收集包含了对成熟代、年轻代的全部对象的垃圾回收。其回收算法见3.3节。
3、 Young年轻代。年轻代中存储新近分配的对象。年轻代分为3个区域：
a) Eden。
所有的新对象总是在Eden中分配，在Eden中的对象是连续分配的，所有的对象分配都在Eden的顶部进行，不需要搜索freelist。从而使得分配一个对象的开销与在栈中分配空间具有相同的时间开销。
b) Survivor
在上一次年轻代垃圾回收中存活下来的对象。这些对象每逃避一次垃圾回收，其年龄就增加1。
c) Spaces
完全为空的内存。其大小与survivor空间完全相同。
一次年轻代的垃圾回收过程如下：
1、当Eden不具备足够的空间来分配新的对象时，开始进行一次年青代的垃圾回收。
2、使用Copy算法，把Survivor及Eden中的对象复制到Space中。如果本次回收中存活的对象过多，从Space中溢出了，那么溢出的对象被复制到成熟堆中。
3、如果一个对象从一次垃圾回收中存活过来，那么，其年龄增加1，在垃圾回收中，年龄大的对象被优先的复制到成熟堆中。
4、垃圾回收完成后，Eden和Survivor中的存活对象全部被移走，剩余的对象全部是垃圾，可以被垃圾回收掉。原来的Space空间变成后Survivor空间，保存了存活下来的对象。
Hotspot的分代GC与SemiSpaceCopy算法不同，它仅保留了相对较小的Space空间，而无须把整个堆的1/2作为保留空间。由于大部分的成熟对象将及时地转移到成熟对象空间中，可以避免一次又一次的将其从一个半区复制到另外一个半区，从而提高复制的效率。
3.3 成熟堆GC
虽然分代的GC能够高效的清理较短时间的垃圾，但是，随着时间的迁移，有更多的对象会被转移到成熟对象空间中，当成熟对象空间不再有足够的内存时，就需要对成熟队进行GC了。对成熟堆进行GC时，总是对包括成熟堆和年轻代堆一起进行垃圾回收的。
Hotspot对成熟堆GC采用了一种类似于MarkSweep的算法，称之为MarkCompact算法，就是在标记所有的存活对象时，对其进行空间的压缩，释放掉死亡对象占用的空间。也就是说，在Hotspot的成熟堆中，所有的对象也总是连续分配的，不存在空洞，不需要使用freelist方式来记录空闲内存，从而加快了在成熟空间分配对象（在从年轻代复制对象到成熟代时）的速度。显然，这个优势取决于Hotspot的精确回收策略。
对成熟堆进行垃圾回收时，一些不再需要进行垃圾回收的对象被移动到Perm堆中，从而在后续的垃圾回收过程中，将不再对其进行GC。
跟分代复制GC相比，MarkCompact算法的效率是相当的低下的，这也是在很多情况下，会导致Java应用存在相当长时间的停顿时间。
4 其他GC技术
本节介绍其他的一些GC技术，由于对相关技术的资料收集并不非常全面，因此，本文中仅对其进行简单的介绍。
4.1 火车算法
在Hotspot虚拟机中，引入了火车算法。火车算法是一个针对成熟对象空间的GC技术，其主要的出发点是降低MarkCompact算法的巨大时间开销，采用一种增量的迭代的GC方式，在每次垃圾回收时，仅对成熟对象空间中的部分区域进行垃圾回收，从而实现更短的GC时间。
下面简要的描述火车算法的基本思路：
首先，成熟对象空间被组织成为多辆火车，每辆火车挂有多个车厢。每个车厢就是一个固定大小的内存区域。火车按照创建顺序被编号为1，2，3…，车厢也按照创建顺序被编号为1，2，3…。一般的描述一个车厢为n.m，表示为第n辆火车的第m个车厢。
成熟空间的对象总是从年轻代中复制过来的，不论何时需要将对象提升到成熟代时，这些对象总是被挂接到最大火车的最末车厢，或者挂接到新创建的一辆火车中。
火车算法由虚拟机调度，在合适的时间来进行GC。在进行一次火车算法GC中，算法首先检查编号为1的火车（最先创建的火车），是否存在来自外部的对最小火车中对象的引用（包括Root及其他的火车、年轻代的对象等），如果不存在任何的对火车中对象的引用，那么整辆火车中的对象全部是垃圾，可以销毁。第1号火车销毁后，第2号火车变成第1号，与此顺推。
如果存在对最小火车的引用，那么火车算法检查该火车的1号车厢（最早创建的车厢），并把所有被外部车厢引用的对象复制到其他车厢中，当所有的被外部引用的对象都复制完成后，剩余的对象就全部是垃圾，可以被销毁。
复 制过程是这样进行的：如果这个对象被另外一辆火车中对象所引用，那么这个对象被复制到那辆火车中（如果火车已经满了，那么为它新挂一个车厢）。否则，这个 对象被复制到当前火车的尾部（如果需要，为当前火车新挂一个车厢），在复制过程中，所有指向这个对象的引用也全部更新，并指向新的位置。当对象复制到新的 车厢后，所有在对象中引用得再远1号车厢的对象也被全部的复制到该辆火车的尾部。
这个复制过程最大的优势就是对大型环状对象的收集效率，比如说在一次DOM解析过程中，会创建大量的DOM对象，这些对象可能会进入到成熟对象空间中的多辆火车中。由于复制过程总是保持相关联对象在同一列火车中，因此，最后这些对象会放到一辆火车中，当火车中的其他对象被销毁后，剩余的DOM对象会成为整辆火车的全部，而被集中销毁。
由于火车算法每次支队第1号火车或者第1号火车的第1号车厢进行垃圾回收，因此，其时间开销相对较低，导致的停顿时间较短，比较适合于对停顿时间要求苛刻的应用场景。
但实际上，火车算法的效率并不高，在JDK5.0中，就不再推荐使用了。
4.2 Parallel GC
在上述的GC算法中，整个GC的过程都是单线程的，实际上，多CPU在服务器应用中被广泛的应用，即使是桌面平台，超线程的CPU也已经在普及之中，能够在GC过程中支持并发的进行垃圾回收，从而缩短GC的总体时间，是一个自然的发展趋势。
在Hotspot虚拟机（
在后续的版本中，Parallel GC技术还会被应用到成熟代GC中，从而缩短成熟代GC的停顿时间（或许是更为紧迫的要求）。
4.3 Concurrent GC
在上面提及的所有的GC算法都是一种STW（Stop The World）的算法，也就是说，在进行GC时，所有的线程都停止工作，直到GC完成。
Concurrent GC的目标是让GC工作或者部分的GC工作与其他的线程执行并发的进行，而无须STW。通过让STW的时间尽可能的缩短，来提高系统的响应时间。
目前，在Hotspot虚拟机上，还没有一个很好的ConcurrentGC的实现。但在IBM JDK1.4的虚拟机上，实现了一个Concurrent的MarkSweep算法。
4.4 Escape分析
笔者认为，Escape分析将成为Java垃圾回收技术的下一个关键技术，也是将GC的性能提升到一个新的水平的一个关键的手段。如果成功的将Escapse技术引入到JVM中，不仅仅是能够大大的提高GC的效率，降低Java应用的内存需求，而且也能够大大的提高Java的执行效率。
在我们上面提到的示范代码中，在Replace方法中可能会创建数10个对象，却只有1个对象会在方法返回后仍然生存，Escape分析就是试图通过对代码进行分析，找出这些对象：
1、 如果一个对象的生命周期在方法返回后就自然死亡，那么这些对象根本不需要等待下一次垃圾GC，而且也无须在一次复杂的GC中进行标记或者复制。自然死亡具有最高的效率，其GC成本几乎为0。这也正是C/C++等语言在栈上进行对象分配的优势。
2、 如果一个对象的生命周期逃出了创建它的方法，但是不会逃出创建它的线程，也就是说，在其他的线程中仍然是不可能访问它的。这样的对象也根本无须在全局的堆中进行GC，而仅仅需要在当前线程中进行GC就可以了。对一个现成的这些对象进行GC在时间复杂度上比整个堆的复杂性要小1个数量级，而且这些对象一般也具有更小的生命周期，可以更有效的被摧毁。
Escape分析就是试图找出所有的这些对象，其生命周期要么不逃出创建它的方法，要么不逃出创建它的线程，并对这样的对象进行有效的垃圾回收。在.NET中引入了语义层的ValueObject概念，来实现这个类似的目的，但是使用Escape分析后，Java将在不使用ValueObject的情况下，获得更好的内存管理的能力。但遗憾的是，在这方面，还没有一个JVM广泛的应用了Escape分析，来有效的进行内存管理。
