JVM探秘:垃圾收集算法

垃圾收集算法

垃圾收集算法主要有标记-清除算法、复制算法、标记-整理算法、分代收集算法这几种,对算法的具体实现不做过多探究,只对他们的设计思想进行介绍。

标记-清除算法

最基础的算法就是标记-清除(Mark-Sweep)算法,同它的名字一样,分为“标记”和“清除”两个阶段:首先标记出所有待回收的对象,标记完后统一回收所有被标记的对象。标记过程其实就是上一篇文章讲到的判断对象是否“死亡”的过程,通过引用计数算法可达性分析算法判断对象是否需要回收。

标记-清除算法是最基础的算法,因为其他算法基本都是基于它进行改进发展而来。标记-清除算法的不足主要有两个:一个是效率问题,标记和清除两个过程的效率都不高;另一个是空间问题,标记清楚后产生大量不连续的碎片空间,碎片空间太多会导致当需要分配大对象时,无法找到足够大的连续空间而不得不提前触发另一次垃圾收集。

标记-清除算法的执行过程如下图:

image

复制算法

复制(Copying)算法是为了解决”标记-清除“算法的效率问题而生,它将内存划分为容量大小相等的两块,每次只使用其中一块,当这一块内存使用完了,就将还存活的对象复制到另外一块当中,然后把原来那一块内存清空。这样每次都是对整个半区进行内存回收,内存分配时也不用考虑空间碎片的情况,只要移动堆顶指针按顺序分配即可,实现简单,运行高效。只是这种算法把内存缩小为原来的一半,代价高昂。

复制算法的执行过程如下图:

image

现代的很多商用虚拟机都是采用的这种收集算法来回收新生代,有研究表明,新生代中的对象98%都是”朝生夕死“的,所以不需要按照1:1的比例来划分内存空间,而是将内存分为一块较大的Eden空间和两块较小的Survivor空间,每次使用Eden空间和其中一块Survivor空间,当回收时,Eden和Survivor中还存活的对象一次性复制到另外一块Survivor中,然后清理掉Eden空间和刚才用过的Survivor空间。

HotSpot虚拟机划分的Eden空间和Survivor空间的比例是8:1,也就是把新生代空间划分为8:1:1的三部分,每次新生代中可以使用的内存为90%,被浪费的只有10%。

当然,98%的对象可回收只是一般场景下的数字,我们不能保证每次回收后只有不多于10%的对象存活,当Survivor空间不够用时,需要依赖其它内存(指老年代)进行分配担保。分配担保就是,当另外一块Survivor空间没有足够空间存放垃圾收集新生代存活下来的对象时,这些对象将直接通过内存分配担保机制进入老年代。

标记-整理算法

复制算法在对象存活率比较高的时候,就要进行非常多的复制操作,使得效率变低。而且如果不想浪费50%的空间,就必须有额外一块空间用作分配担保,所以在老年代一般不会使用这种算法。

根据老年代的特点,标记-整理(Mark-Compact)算法应运而生,标记过程仍然与“标记-清除”算法,但后续步骤不再是直接对可回收对象进行清除,而是让所有存活对象都向一端移动,然后直接清理掉边界以外的内存。

标记-整理算法的执行过程如下图:

image

分代收集算法

“分代收集”(Generational Collection)算法就是根据对象的存活周期的不同,将内存分为相应的几块。一般是把Java堆内存分为新生代和老年代,这样可以根据各个年代的特点采用适合的收集算法。在JDK1.7及之前,还有永久代,不过JDK1.8中已经被取消。

在新生代中,每次垃圾收集都有大批量的对象死去,只有少量存活,那就使用复制算法,只需要付出少量存活对象的复制成本就可以完成收集。而老年代中对象存活率较高,也没有额外空间进行分配担保,所以就必须使用标记-清除或者标记-整理算法来进行回收。

收集算法的高效执行

上面介绍了几个主流的垃圾收集算法,垃圾收集算法中需要判断哪些对象是“存活”的哪些是“死亡”的,以决定具体回收哪些对象。上一篇文章中介绍的引用计数算法以及可达性分析算法,就是进行“对象审判”的依据。虚拟机在实现以上算法的同时,也必须对算法的执行效率进行严格的考量,才能保证虚拟机高效运行。

GC Roots

可达性分析的时候,会从GC Roots节点查找引用链来作为判断依据。而可以作为GC Roots的节点主要是在全局性的引用(例如常量或类静态属性),或者执行上下文(栈帧中的本地变量表)中。

另外,可达性分析的时间敏感还体现在GC停顿上,因为分析工作必须在一个能保证一致性的快照中进行,这里的一致性是指分析期间整个执行系统就像冻结在某个时间点上,不能出现分析过程中对象引用关系还在不断变化的情况。这点是导致GC进行时必须停顿所有执行线程的一个重要原因,这种GC停顿被称作Stop-The-World

目前主流的Java虚拟机采用的都是准确式GC,就是虚拟机可以知道内存中某个位置的数据具体是什么类型,所以当GC停顿时,并不需要一个不漏的检查所有引用,虚拟机有办法可以直接得知哪些地方存放着对象引用。在HotSpot的实现中,是使用一组称为OopMap的数据结构来达到这种目的,在类加载完后,HotSpot就把对象内什么偏移量上是什么类型的数据计算出来,在JIT编译时,也会在特定的位置记录下栈和寄存器中哪些位置是引用,这样在GC扫描时就可以直接得知这些信息了。

安全点

程序执行时并非在所有地方都能停下来开始GC,只有在到达安全点(SafePoint)时才能暂停,因为只有在安全点的位置,才会记录引用关系,才会记录OopMap中的信息。安全点的选取是以“是否具有让程序长时间执行的特征”为标准进行选定,而满足长时间执行的特征就是指令序列复用,例如方法调用、循环跳转、异常跳转等,具有这些功能的指令才会产生SafePoint。

SafePoint的另一个问题就是如何在GC发生时让所有线程都跑到最近的安全点上暂停下来,一般有两种方法,分别是抢先式中断主动式中断。抢先式中断会在GC发生时首先把所有线程全部中断,如果发现有线程中断的地方不在安全点上,就恢复线程,让它跑到安全点上。主动式中断是当GC需要中断线程的时候,不直接对线程操作,仅仅是简单的设置一个标志,各个线程主动去轮询这个标志,发现中断标志为真时就自己中断挂起。比较多使用的是主动式中断。

安全区域

安全点的机制看似已经完美了,但是实际却不是。安全点机制可以保证在程序执行时,在不太长的时间内就能够进入可以GC的SafePoint,但是当程序不执行的时候呢?所谓不执行就是不分配CPU时间,典型的例子就是线程Sleep或者Blocked状态,这时线程无法响应JVM的中断请求,从而跑到安全点去中断挂起。这种情况,就只能通过安全区域(Safe Region)来解决了。

安全区域是指在一段代码片段中,引用关系不会发生变化,在这个区域中的任何地方开始GC都是安全的。SafeRegion也可以看作是扩展了的SafePoint。