Java
Java虚拟机

Java虚拟机03 - 垃圾收集算法

简介:Java虚拟机在执行Java程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域都有各自的用途,以及创建和销毁的时间,有的区域随着虚拟机进程的启动而存在,有些区域则依赖用户线程的启动和结束而建立和销毁。

1. 垃圾收集算法

这里将简要介绍几种主流的垃圾收集算法的思想。

1.1. 标记 - 清除算法

首先是“标记 - 清除”(Mark - Sweep)算法,分为两个阶段:

  • 首先标记出所有需要回收的对象;
  • 在标记完成后统一回收所有被标记的对象。

该算法是最基础的收集算法,它首先通过GC Root标记所有的可达对象,然后清除所有不可达的对象,完成垃圾回收。后续的收集算法都是基于这种思路进行改进而得到的。它的主要不足有两个:

  • 效率问题,标记和清除两个过程的效率都不高;
  • 空间问题,标记清除之后会产生大量不连续的内存碎片,空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时,无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

标记—清除算法的执行过程下图所示:

1.标记清除算法.png

1.2. 复制算法

“复制”(Copying)收集算法将可用内存按容量划分为大小相等的两块,每次只使用其中的一块。当前这块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把当前块的内存空间一次清理掉。这样每次都是对整个半区进行内存回收,内存分配就不用考虑内存碎片等复杂情况。但这种算法的代价是将内存缩小为了原来的一半。复制算法的执行过程如图下图所示:

2.复制算法.png

在上图中,将内存区域分为相同的A和B两个区域,当A内存区域用完后,将所有的还存活的对象复制到B内存区域中,然后将A区域一次性清除掉。

”复制“算法一般用于收集新生代,因为新生代大部分的对象的存活时间很短,因此新生代中存活的对象远远少于垃圾对象。

新生代:存放年轻对象的堆空间。年轻对象是指刚刚创建,或者经历垃圾回收次数不多的对象。
老年代:存放老年对象的堆空间。老年对象指经历过多次垃圾回收依然存活的对象。

在商业虚拟机中,例如我们常见的HotSpot虚拟机,将新生代分为一个Eden区和两个Survivor区,Eden区与Survivor区的大小比例是8:1,也即是说Eden区占新生代的80%,两个Survivor分别占10%。新生代的”复制“算法执行规则如下:

  • 每次使用”复制“算法进行垃圾回收时,会将Eden区和其中一块Survivor区的所有存活对象复制到另一块空闲Survivor区中,在复制操作中,大对象和老年对象将直接复制到老年代
  • 然后将原来的Eden区和Survivor区的对象一次性清理掉;
  • 如果在执行复制算法时一块空闲Survivor区域不能够容纳原来的Eden区和Survivor区的对象,就需要依赖老年代,将多余的对象直接复制到老年代。

可以发现,这种复制机制保证只有一块Survivor区的内存(仅占新生代内存的10%)是被浪费的。新生代的”复制“算法示意图如下:

3.新生代的复制算法.png

1.3. 标记 - 整理算法

在老年代一般使用“标记-整理”(Mark - Compact)算法,该算法过程如下:

  • 首先标记过程仍然与“标记-清除”算法一样;
  • 然后让所有存活的对象都向一端移动;
  • 接下来直接清理掉端边界以外的内存。

“标记-整理”算法的示意图如下图所示:

4.标记整理算法.png

1.4. 分代收集算法

当前商业虚拟机的垃圾收集都采用“分代收集”(Generational Collection)算法,这种算法根据对象存活周期的不同将内存划分为几块。一般把Java堆分为新生代和老年代,根据各个年代的特点采用最适当的收集算法。在新生代中,每次垃圾收集时都发现有大批对象死去,只有少量存活,那就选用复制算法,只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率高、没有额外空间对它进行分配担保,就必须使用“标记—清理”或者“标记—整理”算法来进行回收。

2. OopMap、Safe Point和Safe Region

可达性分析法中,可作为GC Roots的节点主要在全局性的引用(如常量或类静态属性)与执行上下文(如栈帧中的本地变量表)中,如果要逐个检查这里面的引用会消耗很多时间。另外,可达性分析对执行时间的敏感还体现在GC停顿上,因为这项分析工作必须在一个能确保一致性的快照中进行。

注:这里“一致性”指的是在整个分析期间整个执行系统看起来就像被冻结在某个时间点上,分析过程中不可以出现对象引用关系还在不断变化的情况,否则分析结果准确性就无法得到保证。这是导致GC进行时必须停顿所有Java执行线程(Sun将这件事情称为“Stop The World”)的其中一个重要原因。

因此,在HotSpot虚拟机中就引入了OopMap、Safe Point和Safe Region等概念。

2.1. OopMap

OopMap用于辅助枚举GC Roots。在类加载完成的时候,HotSpot使用一组OopMap记录了栈上或寄存器中的本地变量到堆上对象的引用关系,这样在GC操作时可以避免对整个栈和寄存器全部扫描一遍,以加快枚举根节点的速度并节约时间和资源。同时,OopMap可以帮助HotSpot实现准确式GC,提高GC Roots Enumeration速度。

注:什么叫准确式GC?什么叫保守式GC?什么叫半保守式GC?准确式GC有哪些实现思路?

GC操作在枚举根节点时,递归遍历每个栈帧的OopMap,通过栈中记录的被引用对象的内存地址,即可找到这些对象。

2.2. Safe Point

Safe Point用于解决OopMap内容变化的指令过多导致需要大量额外空间的问题。

一个线程意味着一个栈,一个栈由多个栈帧组成,一个栈帧对应着一个方法,一个方法里面可能有多个安全点。HotSpot没有为每条指令都生成OopMap,只是在“特定的位置”记录了这些信息,这些位置称为安全点(Safe Point),即程序执行时只有在到达Safe Point时才能更新自己的OopMap。Safe Point的选定基本上是以程序“是否具有让程序长时间执行的特征”为标准进行选定的,“长时间执行”的最明显特征就是指令序列复用,例如方法调用、循环跳转、异常跳转等,所以具有这些功能的指令才会产生Safe Point。

对于Safe Point,另一个需要考虑的问题是如何在GC发生时让所有线程(这里不包括执行JNI调用的线程)都运行到最近的安全点上再停顿下来。这里有两种方案可供选择:抢先式中断(Preemptive Suspension)和主动式中断(Voluntary Suspension):

  • 抢先式中断。不需要线程的执行代码主动去配合,在GC发生时,首先把所有线程全部中断,如果发现有线程中断的地方不在安全点上,就恢复线程,让它继续运行到安全点上。现在几乎没有虚拟机实现采用抢先式中断来暂停线程从而响应GC事件。
  • 主动式中断。当GC需要中断线程的时候,不直接对线程操作,仅仅简单地设置一个标志,各个线程执行时主动去轮询这个标志,发现中断标志为真时就自己中断挂起。轮询标志的地方和安全点是重合的,另外再加上创建对象需要分配内存的地方。

2.3. Safe Region

Safe Point机制保证了程序执行时,在不太长的时间内就会遇到可进入GC的Safe Point。但是当线程没有分配CPU时间(如线程处于Sleep状态或者Blocked状态),这时候线程无法响应JVM的中断请求以继续到安全的地方去中断挂起,JVM也显然不太可能等待线程重新被分配CPU时间。对于这种情况,就需要安全区域(Safe Region)来解决。

安全区域是指在一段代码片段之中,引用关系不会发生变化。在这个区域中的任意地方开始GC都是安全的。我们也可以把Safe Region看做是被扩展了的Safepoint。在线程执行到Safe Region中的代码时,首先标识自己已经进入了Safe Region,当在这段时间里JVM要发起GC时,就不用管标识自己为Safe Region状态的线程了。在线程要离开Safe Region时,它要检查系统是否已经完成了根节点枚举(或者是整个GC过程),如果完成了,那线程就继续执行,否则它就必须等待直到收到可以安全离开Safe Region的信号为止。

3. 卡表(Card Table)和Remembered Set

在枚举根节点时,根节点有可能在新生代中,也有可能在老年代中。当只收集新生代时则必要对位于老年代的GC Roots 做全面的可达性分析。但可能存在位于老年代的某个GC Root引用了新生代的某个对象,而这个对象是不能清除的,怎么办呢?这个时候就需要用到Card Table这种数据结构来对该现象进行优化了。卡表作为一个比特位的集合,每一个比特位可以用来表示年老代的某一区域中的所有对象是否持有新生代对象的引用,这样新生代在GC时,可以不用花大量的时间扫描所有年老代对象来确定每一个对象的引用关系,而可以先扫描卡表,只有卡表的标记位为1时,才需要扫描给定区域的年老代对象。而卡表位为0的所在区域的年老代对象,一定不包含有对新生代的引用。

卡表中每一个位表示年老代4K的空间,卡表记录未0的年老代区域没有任何对象指向新生代,只有卡表位为1的区域才有对象包含新生代引用,因此在新生代GC时,只需要扫描卡表位为1所在的年老代空间。使用这种方式,可以大大加快新生代的回收速度。卡表的结构示意图如下:

5.Card Table.png

卡表是个单字节数组,每个数组元素对应堆中的一张卡。每次年老代对象中某个引用新生代的字段发生变化时,HotSpot VM就必须将该卡所对应的卡表元素设置为适当的值,从而将该引用字段所在的卡标记为脏。在Minor GC过程中,垃圾收集器只会在脏卡中扫描查找年老代以确定新生代引用。

HotSpot VM的字节码解释器和JIT编译器使用写屏障维护卡表。写屏障是一小段将卡状态设置为脏的代码。解释器每次执行更新引用的字节码时,都会执行一段写屏障,JIT编译器在生成更新引用的代码后,也会生成一段写屏障。虽然写屏障使得应用线程增加了一些性能开销,但Minor GC变快了许多,整体的垃圾收集效率也提高了许多,通常应用的吞吐量也会有所改善。

注:Minor GC和Major GC / Full GC

  • Minor GC(新生代 GC):指发生在新生代的GC操作,Minor GC非常频繁,回收速度也比较快。
  • Major GC  / Full GC(老年代 GC):指发生在老年代的GC操作,出现了Major GC  / Full GC,经常会伴随至少一次的Minor GC(但非绝对,在Parallel Scavenge收集器的收集策略里就有直接进行Major GC的策略选择过程) 。Major GC  / Full GC的速度一般会比Minor GC慢10倍以上。

注2:G1垃圾回收器比以前的HotSpot GC新增了一种Remembered Set的设计,但是同时也使用了跟以前HotSpot VM里其它GC完全一样的Card Table。关于这部分内容会在后面的章节中讲到。