垃圾收集算法及实现

标记清除算法

标记清除算法是最基础的收集算法，分为标记和清除两个阶段，标记阶段标记出所有需要回收的对象，清除阶段统一回收所有被标记的对象。之所以说标记清除算法是最基础的收集算法，是因为后续的收集算法都是基于这种思路并对其不足进行改进而得到的。

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

复制算法

复制算法的出现是为了解决效率问题，它将可用内存按容量划分为大小相等的两块，每次只使用其中一块。当这一块使用完了，就将还存活着的对象复制到另一块上面，然后再把已使用过的内存空间一次清理掉。每次都是对整个半区进行内存回收，内存分配时不用考虑内存碎片等复杂情况，只要移动堆顶指针按顺序分配内存即可，实现简单运行高效。但是代价是将内存缩小为原来的一半。

标记复制算法

现在商用虚拟机都采用复制算法来回收新生代，因为新生代对象98%是朝生夕死，所以不需要按1：1来划分内存空间。而是将内存空间分为一块较大的Eden空间和两块较小的Survivor空间（From Survior和To Survovor），HotSpot虚拟机默认Eden：From Survivor：To Survivor的大小比例是8：1：1，每次使用Eden和From Survivor空间。当Eden空间执行Minor GC时会将Eden和From Survivor空间中还存活的对象复制到To Survivor空间中（如果To Survivor空间没有足够空间存放上一次新生代收集下来存活的对象时，这些对象将直接通过分配担保机制进入老年代。），然后清理掉Eden和From Survivor空间，最后将To Survivor空间和From Survivor空间角色互换。

复制算法在对象存活率较高时就要进行较多的复制操作，效率将会变低，老年代一般不能直接选用复制算法。

标记整理算法

根据老年代的特点，提出了标记整理算法，标记过程任然与标记清除算法一样，整理阶段让所有存活的对象都向一端移动，然后直接清理掉边界以外的内存。

标记整理算法

分代收集算法

目前商业虚拟机的垃圾收集都采用分代收集算法，这种算法并没有新思想，只是根据对象存活周期将内存分为几块，一般把堆内存分为新生代和老年代，新生代采用复制算法，老年代采用标记清除算法或标记整理算法进行回收。

注：标记-清除或标记-整理算法会比复制算法慢10倍以上

枚举根节点

主流的Java虚拟机都是采用可达性分析算法来管理内存的。在可达性分析法中对象能被回收的条件是对象到GC Roots是否存在引用链，可作为GC Roots的节点主要是在全局性引用（e.g.常量或静态属性）和执行上下文（e.g.栈帧中本地变量表）。现在很多应用方法区都很大，如果逐个检查非常耗费时间。

而可达性分析算法的分析工作必须在一个能确保一致性的快照中进行，整个分析期间整个执行系统对象引用关系必须保持不变，就像被冻结在某个时间点上。这是导致GC执行时必须停顿所有Java执行线程的一个重要原因，Sun将该事件称为Stop-The-World。在枚举根节点的过程中耗费的时间越多GC停顿时间越长。

目前主流的Java虚拟机使用的都是准确式GC，当执行系统停顿后，并不需要一个不漏地检查完所有执行上下文和全局变量的引用位置，在HotSpot虚拟机实现中，使用一组称为OopMap的数据结构来记录所有执行上下文和全局变量的引用位置，在类加载完成时HotSpot就把对象内偏移量上对应的类型数据计算出来，在JIT编译过程中，也会在特定位置记录下栈和寄存器中哪些位置时引用。

安全点

在OopMap的协助下，HotSpot可以快速且准确地完成GC Roots枚举，但是可能导致引用关系变化或者说OopMap内容变化的指令非常多，如果每条命令都生成对应的OopMap，将会需要大量额外空间，GC空间成本将会变得很高。

HotSpot只是在特定的位置记录生成的OopMap信息，这些位置称为安全点（Safepoint），程序执行时并非在所有地方都能停顿下来开始GC，只有在达到安全点时才能暂停。安全点的选定既不能太少以至于让GC等待时间太长，也不能过于频繁以至于过分增大运行时的负荷。安全点的选定基本上是以程序是否具有让程序长时间执行的特征为标准进行选定的，但是程序不太可能因为指令流太长而过长时间运行，这里的长时间执行实际上是指指令序列复用，例如方法调用、循环跳转、异常跳转等功能的指令才会产生安全点。

如何让所有线程（除执行JNI调用的线程）在GC发生时都运行到最近的安全点停顿下来。有抢占式中断和主动式中断两种方案可供选择。

抢占式中断——GC发生时，首先中断所有线程，如果发现有线程中断地方不在安全点上，就恢复线程让其运行到安全点。抢占式中断不需要线程的执行代码主动区配合，但是目前几乎没有虚拟机实现采用抢占式中断来暂停线程从而响应GC事件。
主动式中断——当GC需要中断线程的时候，不直接对线程操作，仅简单地设置一个轮询标志，各个线程执行时主动轮询整个标志，发现中断标志为真时就自己中断挂起。轮询标志、安全点和创建对象需要分配的内存三个地方是重合的。

安全区域

安全点保证了程序执行时，在不太长时间内就会遇到可进入GC的安全点，但是程序不执行时（没有分配到CPU时间），例如线程处于Sleep状态或Blocked状态时，线程无法响应JVM中断请求并运行到安全的地方中断挂起，针对这种情况就需要安全区来解决。

安全区域时指在一段代码片段中，引用关系不会发生变化，整个区域中的任意地方开始GC都是安全的。线程在执行到安全区域中的代码时，首先标识自己进入了安全区域，当在这段时间里JVM要发起GC时，就不用管标识自己进入安全区域状态的线程了。在线程要离开安全区域时，先检查系统是否已经完成根节点枚举或是整个GC过程，如果没完成就必须等待直到收到可以安全离开安全区域的信号为止。