JVM 中的垃圾回收算法有标记-清除算法、复制算法、标记-整理算法、分代收集算法四种算法。

1. 标记 - 清除算法

标记-清除(Mark-Sweep)算法是现代垃圾回收算法的思想基础,它将垃圾回收分为「标记」和「清除」两个阶段:

  • 1、在标记阶段,通过「可达性分析算法」标记出所有需要回收的对象;

  • 2、在清除阶段,清除所有被标记为可以回收的对象。

算法示意如下图:

标记-清除算法

这个算法的主要缺点有两个:

  • 1、效率问题,标记和清除两个过程的效率都不高;
  • 2、空间问题,标记清除之后会产生大量不连续的内存空间碎片,空间碎片太多可能会导致以后在程序的运行过程中需要分配较大的对象时,会因为无法找到足够大的连续内存空间而不得不提前触发另一次垃圾收集行为。

后续的很多垃圾收集算法都是基于此算法的思路进行改进而得到的。垃圾收集器中的 CMS 是基于标记-清除算法实现的,不过这种收集器也逐渐被取代了。

2. 标记 - 整理算法

标记-整理(Mark-Compact)算法,类似于标记-清除算法,不过它标记完对象后,不是直接对可回收对象进行清除;而是让所有仍会存活的对象都向一端移动,然后直接清理掉边界以外的内存。算法示意如下图所示:

标记-整理算法

相对于标记-清除算法,标记-整理算法的优点是解决了内存空间碎片的问题,使对象创建时的内存分配更快速了(也可以使用 TLAB 进行分配);缺点还是效率问题,标记和整理这两个过程的效率都不高。

基于标记-整理算法实现的垃圾收集器有很多,如 Serial 收集器、ParNew 收集器、Parallel Old 收集器、G1 收集器等。

3. 复制算法

复制(Copying)算法的思路为:它将可用内存按容量分为大小相等的两块,每次只使用其中的一块。当正在使用的内存块 A 的的内存用完了,就将还活着的对象复制到另一块内存 B 上面,然后再把之前使用的内存块 A 的空间一次性清理掉,就这样循环往复。

这样使得每次都是对整个半区进行内存回收,内存分配时也不用考虑内存碎片等复杂情况,只需要移动堆顶指针,按顺序分配内存即可。复制算法的优点是解决了效率问题和内存碎片的问题,算法示意如图:

复制算法

通过上图我们也可以发现,复制算法的缺点就是每次回浪费掉一半的内存空间。而且,在对象存活率较高时就要进行较多的复制操作,效率会变低。

现在很多垃圾收集器都采用复制算法来回收新生代。

4. 分代收集算法

分代收集(Generational Collection)算法并没有什么新的垃圾回收思想,它只是根据对象存活周期的不同将内存划分为几块(一般是把 Java 堆划分为新生代和老年代),然后根据各个块的特点采用最适当的垃圾收集算法。

算法示意如图(其中,Eden、Survivor From 和 Survivor To 空间均属于新生代(Young),Old 空间属于老年代,一般这几个内存空间的大小比例为:Eden : Survivor From : Survivor To = 8 : 1 : 1Young : Old = 1 : 2 ):

分代收集算法

如上图所示,分代收集算法的策略为:

  • 在新生代中,每次垃圾收集都有都发现有大批对象死去,只有少量存活,就选用复制算法。将 Eden 和 Survivor From 空间中还存活着的对象一次性复制到 Survivor To 空间上;当 Survivor To 空间不够用时,需要依赖其它内存(这里指老年代)来进行分配担保(Handle Promotion);最后对刚才用过的 Eden 和 Survivor From 空间进行清理。
  • 在老年代中,因为对象存活率高,也没有额外空间对它进行分配担保,就必须使用「标记-清除」或者「标记-整理」算法来进行回收。

当前的商业虚拟机基本都是采用的分代收集算法。