JVM05-垃圾收集算法

前言

上一篇我们介绍了JVM04-JVM中内存溢出以及其处理方法。这一篇文章我们来熟悉下JVM中各种垃圾回收算法。这些垃圾收集算法是后面各种垃圾收集器的算法基础。闲话少叙，让我们直入主题。
标记-清除算法

标记-清除算法分为"标记"和"清除"两个阶段，首先标记所有需要回收的对象，在标记完成后，统一回收掉所有被标记的对象，也可以反过来，标记存活的对象，统一回收未标记的对象，标记的过程就是对象是否属于垃圾的判定过程，一般是通过可达性分析算法，也就是说某个对象到GC Root间是否有引用链相连，如果没有则判断该对象不再被使用，也就是说是可以被回收的。如下图所示，标黄的内存块，在标记之后，就被清除了，留下来不少的内存碎片。

标记-清除算法的优点

实现简单
标记-清除算法实现简单， 与其他算法的组合也相应地简单。
与保守式GC算法兼容中，对象是不能被移动的，因此保守式GC算法跟把对象从现在的场所复制算法与标记-压缩算法不兼容。标记-清除算法因为不会移动对象，所以非常适合搭配保守式GC算法。事实上，在很多采用保守式GC算法的处理程序中也用到了标记-清除算法。

标记-清除算法的缺点

分配速度
执行效率不稳定，如果Java堆中包含大量对象，而且这些对象大部分是需要回收的，这是必须进行大量标记和清除动作，导致标记和清除两个过程的执行效率都随着对象数量增长而降低。
碎片化
内存空间的碎片问题、标记、清除之后会产生大量不连续的内存碎片，空间碎片太多会导致当以后在程序运行过程中需要分配较大对象时无法找到足够连续内存而不得不提前触发另一次垃圾收集动作。

标记-复制算法

标记-复制算法将可用的内存容量划分为大小相等的两块，每次只使用其中的一块，当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用的内存空间一次清理掉。如果内存中多数对象都是存活的，这种算法将会产生大量的内存间复制的开销，但对于多数对象都是可回收的情况下，算法需要复制的就是占少数的存活对象。而且每次都是针对整个半区进行内存回收，分配内存时就不用考虑有内存碎片的复杂情况了。如下图所示：回收之后将存活的对象全部移动到原来的保留区域。

标记-复制算法的优点

优秀的吞吐量
标记-清除算法消耗的吞吐量是搜索活动对象（标记阶段）所花费的时间和搜索整体堆（清除阶段）所花费的时间之和。
另一方面，因为标记-复制算法只搜索并复制活动对象，所以跟一般的标记-清除算法相比，它能在较短时间内完成GC，也就是说，其吞吐量优秀。
尤其是堆越大，差距越明显。
可实现高速分配
标记-复制算法不使用空闲链表，这是因为分块是一块连续的内存空间，比起标记-清除算法等使用空闲链表的分配，标记-复制算法明显快得多。
不会发生碎片化
存活对象被几种安排到保留区域，像这样把对象重新集中，放在堆的一端的行为就叫作压缩，在标记-复制算法中，每次运行GC时都会执行压缩。因此复制算法不会发生碎片化。

标记-复制算法的缺点

堆使用效率低下
标记-复制算法把堆二等分，通常只能利用其中的一半来安排对象，也就是说，只有一半的堆能被使用，相比其他能使用整个堆的GC算法而言，这是标记-复制算法的一个重大缺陷。
不兼容保守式GC算法
标记-复制算法因为必须要移动对象重写指针，所以跟保守式GC算法不相容。

Appel式回收

在1989年，Andrew Appel针对具备"朝生夕灭"特点的对象，提出了一种更优化的半区复制分代策略，称之为"Appel式回收"。Appel式回收的具体做法就是把新生代分为一块较大的Eden和Survivor中仍然存活的对象一次性复制到另一块Survivor空间上，然后直接清理掉Eden和已用过的那块Survivor空间，HotSpot虚拟机 默认Eden和Survivor的大小比例是8:1，也即每次新生代可用空间为整个新生代容量的90%（Eden的80%加上一个Survivor的10%），只有一个Survivor空间，即10%的新生代会被"浪费"掉。
标记-整理算法

标记-复制算法在对象存活率较高时就要进行较多的复制操作，效率将会降低。更关键的是，如果不想浪费50%的空间，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都100%存活的极端情况。所以老年代一般不能直接选用这种算法。所以，针对老年代的垃圾收集，有标记-整理算法，首先还是标记所有需要回收的对象，然后让所有存活的对象都向内存一端移动，然后，直接清理掉边界以外的内存。
如果移动存活对象，尤其是在老年代这种每次回收都有大量对象存活区域，移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的操作。而且这种对象移动操作必须全程暂停用户应用程序才能进行。移动对象则内存回收时会更复杂，不移动则内存分配时会更复杂，从垃圾收集的停顿时间来看，不移动对象停顿时间会更短，甚至不需要停顿，但是从整个程序的吞吐量来看，移动对象会更划算。关注吞吐量的Parallel Scavenge收集器是基于标记-整理算法的，而关注延迟的CMS收集器则是基于标记-清除算法的。标记-整理算法清理过程如下图所示：

标记-整理算法的优点

标记-整理算法会执行压缩，和其他算法相比而言，堆利用效率高。而且标记-整理算法不会出现标记-复制算法那样只能利用半个堆的情况。另外，由于有了压缩过程，不会产生碎片化。

标记-整理算法的缺点

压缩花费计算成本
标记-清除算法中，清除阶段也要搜索整个堆，不过搜索1次就够了，但标记-压缩算法要搜索3次，这样就要花费约3倍的时间，这是一个相当巨大的缺陷，特别是堆越大，所消耗的成本也就越大。

保守式GC算法

前面提到了保守式，简单的来说，保守式GC（Conservative GC）指的是"不能识别指针和非指针的GC"。
总结

本文简单的介绍了JVM中几个基本的垃圾回收算法，主要是标记-清除算法，标记-复制算法和标记-整理算法。每个算法都有各自的优缺点。一般而言新生代采用标记-清除算法和标记-复制算法居多，老年代会采用标记-整理算法。