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回收器就有回上持久代的功能。