Mark-Sweep 标记清除算法

标记清除算法是最基础的回收算法，回收过程包括“标记”和“清除”两个阶段，过程大概是这样的：

mark_sweep

1：标记阶段时，标识出可回收的引用。

2：清除阶段时，对标记阶段所标识为的对像进行回收。

这个算法存在的最大问题是，通过该算法回收的内存区域是不连续的，会产生大量的无法被利用的内存碎片，而如果找不到连续足够多的空间，就需要触发另一个GC来进去回收。

另外，sweep阶段，当所管理的内存区域很大时（无论是否全部使用），效率也会受到影响。

但是，GC算法只是一些理论算法，而GC回收器则是基于这些算法的具体实现，通过对回收器机制的扩展和加入一些补偿措施，可以规避算法自身的缺陷。例如标记清除算法，当前最稳定高效的tenure代的回收器 ，CMS回收器，便是基于这种算法。CMS通过利用多核/线程，将并发标记阶段、并发清除阶段变为并行，通过通过一些额外的补偿方案实现内存碎片的整理，使其成为很优秀的垃圾回收器。

后续会单独用一篇博客来描述具体垃圾回收器，本文还是继续描述回收算法。需记住加收算法本身缺陷是可以通过具体实现来规避的就行了，并不是基于某种回收算法实现的回收器，就一定有该种算法存在的缺陷，如CMS。

Copying 复制算法

复制算法的出现，是为了解决标记清除所存存的问题。复制算法将容量划分两块区域，其过程如下：

gc_copying

注：这里着重描述复制算法的原理，在一些基于复制算法实现的GC回收器中，并不会只有两块区域，在Hotspot中，默认是由Eden、Survivor 0、Survivor 1和Tenure(晋升)之间相互复制，它们的大小也不尽相同，复制逻辑也更为复杂。之后专门写一篇文章描述。 // TODO

在复制算法中，两个内存区域中只有一块区域处于激活状态。新的对像都会分配在激活区域。 当激活区域写满之后，将当前区域中存活的对像复制到另一个区域，同时将目标区域置为激活，原区域置为空闲，同时直接清空原区域。新的对像仍然在激活区域进行分配。

在复制到目标区域的过程中，同时将内存区域进行整理排列，这样就解决了碎片内存的问题。

复制算法存在的缺陷便是将空间对半分，导致实际利用的内存只有一半：内存的利用率不高，同时在对像存活率高的场景中，会进行较多且价值低的复制，效率将会变低（所以这种算法的GC回收器更能满足年轻代的特点）。但这只是算法的缺陷，如之前的描述，这在具体实现中并不是不可规避的。

Mark-Compact 标记整理算法

为了补强复制算法存在的问题，后来就提出了标记整理算法。分为“标记”和“整理”两个阶段，其中“标记”阶段和标记清除算法一致，而“整理”阶段则不相同，如图所示：

mark_compact

在整理阶段，不在是对标记的对像做回收，而是通过所有存活对像都向一段移动，然后直接清除边界以外的内存。

这种算是是根据老年代的特点而提出来的（相对于复制算法），但却并不一定适用老年代使用, 老年代的内存区域普遍较大，且对像存活率高的阶段: 由于老年代对像数据量多，mark阶段并不一定高效，同时对这么多对像做移动操作，compact阶段的效率也会受到影响。

分代回收

由于JVM将内存结构分为多个不同的区域（具体划分又根据jvm实现各不相同，本文多以hotspot为例），这些段会都有各自的特点。所以针对各自特点，对每一个内存区域使用不同的算法以达到最优的整体回收效率。(需要注意，下面描述经典的分代回收被更为先进G1回收器(Garbage First)所打破，G1对内存的划分有很大不同)

年轻代(Young Gen)  

年轻代特点是区域相对tenure较小（默认推荐与tenure比例是3:8，但需要系统特点可调整），对像存活率低。

这种情况复制算法的回收整理，速度是最快的。复制算法的效率只和当前存活对像大小有关，因而很适用于年轻代的回收。而复制算法内存利用率不高的问题，通过hotspot中的两个survivor的设计得到缓解。

老年代(Tenure Gen)

老年代的特点是区域较大，对像存活率高。

这种情况，存在大量存活率高的对像，复制算法明显变得不合适。一般是由标记清除或者是标记清除与标记整理的混合实现。

Mark阶段的开销与存活对像的数量成正比，这点上说来，对于老年代，标记清除或者标记整理有一些不符，但可以通过多核/线程利用，对并发、并行的形式提标记效率。

Sweep阶段的开销与所管理区域的大小形正相关，但Sweep“就地处决”的特点，回收的过程没有对像的移动。使其相对其它有对像移动步骤的回收算法，仍然是效率最好的。但是需要解决内存碎片问题。

Compact阶段的开销与存活对像的数据成开比，如上一条所描述，对于大量对像的移动是很大开销的，做为老年代的第一选择并不合适。

基于上面的考虑，老年代一般是由标记清除或者是标记清除与标记整理的混合实现。以hotspot中的CMS回收器为例，CMS是基于Mark-Sweep实现的，对于对像的回收效率很高，而对于碎片问题，CMS采用基于Mark-Compact算法的Serial Old回收器做为补偿措施：当内存回收不佳（碎片导致的Concurrent Mode Failure时），将采用Serial Old执行Full GC以达到对老年代内存的整理。

持久代（Perm Gen）

Perm Gen的内存回收默认是关闭的。以由于越多越多的动态技术的使用（Groovy、Cglib、ASM、Drools等）、以及模块化技术。 Perm Gen也可以通过GC实现内存回收。而其对像存活特点与老年代相似（更甚），所以同样可以使用标记清除算法，Hotspot中的CMS回收器就有回上持久代的功能。