JVM探秘：垃圾收集算法

本系列笔记主要基于《深入理解java虚拟机：jvm高级特性与最佳实践 第2版》，是这本书的读书笔记。

垃圾收集算法

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

标记-清除算法

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

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

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

复制算法

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

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

现代的很多商用虚拟机都是采用的这种收集算法来回收新生代，有研究表明，新生代中的对象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）算法应运而生，标记过程仍然与“标记-清除”算法，但后续步骤不再是直接对可回收对象进行清除，而是让所有存活对象都向一端移动，然后直接清理掉边界以外的内存。

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

分代收集算法

“分代收集”（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。