Java GC算法

对象判定算法

1、引用计数法

给对象添加一个引用计数器，每当一个地方引用它时，计数器的值就加1，当引用失效时，计数器的值就减1，计数器为0的对象就是不可能再被使用， 但是很难解决对象之间相互循环引用的问题

2、可达性分析法

通过一系列的称为’GC Roots’的对象作为起点，从这些节点开始向下搜索，搜索所走的路径称为引用链，当一个对象到GC Roots没有任何引用链 相连，从GC Roots到这个对象不可达，则证明此对象不可用

可作为GC Roots的对象包括

• 虚拟机栈中（栈帧中的本地变量表）引用的对象

• 方法区中类静态属性引用的对象

• 方法区中常量引用的对象

• 本地方法栈中JNI引用的对象

无论是通过引用计数算法判断对象的引用数量，还是通过可达性分析算法判断对象的引用链是否可达，判定对象是否存活都与引用有关

垃圾收集算法

1、标记-清除算法（Mark-Sweep）

最基础的收集算法，后续的所有算法都是基于这种思路对期不足进行优化得到，主要的不足有两点

• 效率问题：标记和清楚两个过程效率都不高
• 空间问题：GC过后会产生大量不连续的内存碎片，空间碎片过多可能会导致需要分配较大对象时，无法找到足够的连续内存空间而触发一次GC

2、复制算法（Copying）

将可用内存容量分为大小相等的两块，每次只使用其中的一块，当一块内存用完了，就将还存活着的对象复制到另一块上面，然后再把已使用过的内存空间 一次清理掉，每次都是对整个半区进行回收，不用考虑会出现内存碎片，代价是将内存缩小了一半

一般用于新生代，因为该区域的对象98%都是‘朝生夕死’，所以将内存分为较大的Eden空间和两块较小的From Survivor和To Survivor空间，每次使用Eden和From Survivor， 当回收时，将Eden和From Survivor中还存活的对象一次性复制到To Survivor空间，最后清理掉Eden和From Survivor，Eden和Survivor的默认大小比例是8:1，当Survivor 空间不够用时，需要老年代进行分配担保

3、标记-整理法（Mark-Sweep）

一般用于老年代，有大量对象长期存活，一次GC回收的内存很少，标记过程和‘标记-清除’算法一样，在标记可清除对象后，不直接对可回收对象进行清理，而是让 所有存活对象都向一端移动，然后清理掉边界以外的内存

4、分代收集算法（Generational Collection）

当前商业虚拟机都采用该算法，根据对象存活周期的不同，一般把堆划分为新生代和老年代，然后根据各个年代的特点采用最合适的GC算法

• 新生代：每次收集都会有大量对象死去，少量存活，选用复制算法
• 老年代：对象存活率高，没有额外空间分配担保，就必须使用’标记-清理’或’标记-整理’算法

算法实现

1、枚举根节点

可达性分析中从GC Roots节点找引用链这个操作，可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性） 与执行上下文（例如栈帧中的本地变量表）中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查这里面的引用，那么必然会消耗很多时间。

分析过程中要在一个能确保一致性的快照中进行

这里”一致性”是指在整个分析期间整个执行系统看起来就像被冻结在某个时间点上， 不可以出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。 这点是导致GC进行时必须停顿所有Java执行线程（Stop The World）的其中一个重要原因， 即使是在号称（几乎）不会发生停顿的CMS收集器中，枚举根节点时也是必须要停顿的

为了让虚拟机有办法直接得知哪些地方存放着对象引用。在HotSpot的实现中，使用一组称为OopMap的数据结构， 在类加载完成的时候，HotSpot就把对象内什么偏移量上是什么类型的数据计算出来，在JIT编译过程中， 也会在特定的位置记录下栈和寄存器中哪些位置是引用。这样，GC在扫描时就可以直接得知这些信息了。

2、安全点

为了可以快速准确的完成GC Roots枚举，减少Stop The World的时间，OopMap只是在特定的位置记录这些信息，这些位置就是安全点（Safepoint）,使得程序并不是在所有地方都 停顿下来开始GC，只有到达安全点时才暂停，安全点的选定是以是否具有让程序长时间执行的特征为标准，因为每条指令执行的时间都非常短暂， 程序不太可能因为指令流长度太长这个原因而过长时间运行，既不能太少也不能让GC等待时间太长，安全点太多，GC 过于频繁，增大运行时负荷，安全点太少，GC 等待时间太长

一般会在如下几个位置选择安全点

• 循环的末尾

• 方法临返回前

• 调用方法之后

• 抛异常的位置

为什么选用这些位置最为安全点

主要的目的就是避免程序长时间无法进入Safepoint，比如JVM在做GC之前要等所有的应用线程进入安全点， 如果有一个线程一直没有进入安全点，就会导致GC时JVM停顿时间延长，比如超大的循环，就具有让程序长时间执行的特征

在GC发生时让所有线程（这里不包括执行JNI调用的线程）都“跑”到最近的安全点上再停顿下来，有以下两种方案

• 抢先式中断（Preemptive Suspension）：在GC发生时，首先中断所有线程，如果发现线程未执行到Safepoint，就恢复线程让其运行到Safepoint上

• 主动式中断（Voluntary Suspension）：在GC发生时，不直接操作线程中断，而是简单地设置一个标志，让各个线程执行时主动轮询这个标志，发现中断标志为真时就自己中断挂起

JVM 采取的就是主动式中断。轮询标志的地方和安全点是重合的

3、安全区域

Safepoint是对正在执行的线程设定的，如果一个线程处于Sleep或中断状态，它就不能响应JVM的中断请求，再运行到Safepoint上,因此 JVM引入了Safe Region。

Safe Region 是指在一段代码片段中，引用关系不会发生变化。在这个区域内的任意地方开始GC都是安全的。

线程在进入Safe Region的时候先标记自己已进入了Safe Region，等到被唤醒时准备离开Safe Region时，它要检查系统是否已经完成了根节点枚举（或者是整个GC过程）， 如果GC完成了，那么线程可以离开，否则它必须等待直到收到安全离开的信号为止。

垃圾收集算法的具体实现