Java 垃圾回收算法

一、概述

说到垃圾回收，我们必须要知道什么是垃圾？为什么要回收？

什么是垃圾：垃圾是在程序运行中没有任何指针指向的对象，这个对象就是需要被回收的垃圾。
为什么要回收：在JVM中如果不及时对垃圾进行回收，那么这些垃圾所占的内存空间会一直保留到程序结束，这部分内存空间无法被其他对象使用，当内存占满的时候就会导致内存溢出。

在Java中垃圾回收分为两个步骤：找到垃圾和回收垃圾。

在找到垃圾的过程中，称为标记阶段，其中有两种算法：引用计数法，可达性分析法。
在回收垃圾的过程中，称为清除阶段，对应的算法有：标记-清除算法，复制算法，标记-整理算法，分代收集算法。

二、引用计数法

原理

对每个对象保存一个整型的引用计数器属性，每当有一个地方引用它时，计数器+1，当引用失效时，计数器-1，当计数器为0时，说明这个对象不再使用，此时被判定为垃圾。

优点：实现简单，判断效率高。
缺点：无法处理循环引用的情况，这是一个致命的缺点，多以Java的垃圾回收器没有使用这种算法。

循环引用：
举一个很简单的例子：链表，链表中有一个Next属性，Next引用的时下一个对象，
A->B->C->D->E->A这种结构。此时将A置空，那么BCDE的引用计数器还为1，这时就会导致BCDE永远无法回收。

三、可达性分析算法

原理

以根对象集合(GC Roots)为起始点，按照从上到下的方式搜索被根对象集合所链接的目标对象是否可达。
搜索的过程中的路径称为引用链。
如果对象没有与任何引用链相连，则是不可达的，就意味着这个对象已经死亡。

可达性分析.jpg

可作为GC Roots的有：

虚拟机栈中引用的对象。
本地方法栈内JNI引用的对象。
方法去区静态属性引用的对象。
方法区中常量引用的对象。

在经过可达性分析之后，仅仅进行了第一次标记，接下来还有第二次标记。

如果对象没有重写finalize()方法，则虚拟机视为没有必要执行，对象被判定不可达。
如果对象重写了finalize()方法，且还未执行过，则对象会被插入到F-Queue队列中，由虚拟机中一个低优先级的Finalizer线程触发finalize()方法执行。
在finalize()执行的过程中，GC会对F-Queue中的对象进行第二次标记，如果此对象与引用链上的任何一个对象建立了联系，那么该对象就会被移出"即将回收"集合，此对象将不会被回收，如果再次出现没有引用链的情况下，finalize()方法不会再调用，对象直接变成不可达，就是说finalize()方法只会执行一次。

四、标记-清除算法

原理

当堆中的有效内存空间被耗尽时，就会停止整个程序(Stop The World)，然后进行两项工作，标记和清除。

标记：GC从引用根节点开始遍历，标记所有被引用的对象。
清除：遍历完成后，如果有对象没有被标记为可达对象，则将其清除。

这里的清除并不是真正的清除，而是把需要清除的对象地址保存在空闲列表，当有新的对象需要插入时，判断垃圾的位置空间是否足够，如果够，则插入。就相当于覆盖。

标记-清除.jpg

优点：实现简单。
缺点：效率不高，清理之后的内存空间不连续，产生内存碎片。需要维护一个空闲列表。

五、复制算法

原理

将内存空间分为两块，每次只使用其中一块，在垃圾回收时将正在使用中的存活对象复制到未使用的内存块中，然后清除正在使用的内存块的所有对象。最终完成垃圾回收。

复制算法.jpg

优点：没有标记和清除过程，实现简单，运行高效。复制后保证了空间连续性，不会出现碎片问题。
缺点：需要两倍的空间或者说牺牲一倍的内存空间。还要维护对象的引用关系，不管是内存还是时间开销都不小。

如果系统中存活对象非常多，复制算法则需要复制更多的对象，反而优点变成缺点，所以复制算法可以用在数据比较小的内存中，比如堆中的新生代。

六、标记-整理算法

原理

标记整理算法分为三个步骤，标记，整理，删除，它比标记-删除算法多了一步：整理。
标记：从根节点开始标记所有被引用的对象。
整理：将所有存活的对象都向一段移动。
删除：清除边界外所有的空间。

标记-整理.jpg

优点：
1. 解决了标记-清除算法的空间不连续的缺点。
2. 解决了复制算法的内存减半的代价。
缺点：
1. 效率低于复制算法
2. 移动对象的同时，还需要调整对象的引用。

七、三种清除算法对比

	标记-清除	标记-整理	复制
速度	中等	最慢	最快
空间开销	少(会堆积碎片)	少(不堆积碎片)	对象的2被大小(不堆积碎片)
移动对象	否	是	是

八、分代收集算法

上面总结了三种回收算法的优缺点，每种算法都有利有弊，比如复制算法，虽然它是最快的，但是它会浪费一半的空间，所以根据这些优缺点，衍生出了分代收集算法。

在JVM堆中，分为新生代和老年代，所以分代收集算法就是针对他们的特点使用最适合的回收算法。

新生代：区域相对较小，对象生命周期短，存活率低，回收频繁。自带Eden和两个Survivor区，适用复制算法。

老年代：区域较大，对象生命周期长，存活率高，回收频率低。因此适用标记-清除或标记-整理算法。