垃圾收集算法一直都是影响GC工作效率的重要因素,在本篇博客中博主就与大家一起来学习一下几种经典的垃圾收集算法。由于它的实现涉及到了大量的程序细节,博主在这里就只用抽象的方式将垃圾收集算法的原理与大家分享啦。

1. 标记-清除算法

标记-清除算法(Mark-Sweep)是垃圾收集算法中最基础的算法了,正如它的名字所示,这个算法主要分为两个阶段:“标记”与“清除”。

大家回想一下我们在之前的博客中介绍的可达性分析算法,该算法是用来判断哪些对象应该被GC所回收。而标记-清除算法的“标记”阶段正是使用了这个算法标记出所有存活的对象,之后就进入“清除”阶段,清除掉所有没有被标记存活的对象。

整个标记-清除的过程如下图所示:

d034445228834093bf3a985710a4ee98.jpg

我们假设每个对象的标记位0为未标记,1为已标记。初始情况下,每个对象的标记位都为0。当GC需要工作时,GC首先会停止所有的执行线程(Stop the World),否则你正要进行标记或清除时对象的可达性发生变化的话,回收结果就无法得到保证了。之后GC开始进入标记阶段,将所有GC Roots可达的对象都标记为存活对象(标记位为1).

45e0aec82b674ae7be5c0d53f2198b3b.jpg

在将所有的对象进行了标记之后,GC就可以进入到清除阶段,清除掉所有的没有被标记存活(标记位不为1)的对象,并将存活的对象标记位重新置为0.

fe06d5151f0d482a847796c9f76686c0.jpg

这样一次垃圾收集就完成了,对于整个发生内存回收的区域来看,完成一次标记-清除式的内存回收,变化如下:

77983dd96231449396850628b5987a17.jpg

这种垃圾回收算法的问题主要有两个:

  1. 效率问题:无论是标记或是清除阶段,GC都必须要遍历所有的对象来完成对应的操作,对于需要频繁回收的内存区域来说,效率十分较低。
  2. 空间问题:由于清除阶段直接将所有的非存活对象的内存进行清除,内存区域中必然会出现大量不连续的内存碎片,而过多的内存空间碎片会导致在需要为较大对象分配内存时无法找到足够大的内存空间,而不断地进行垃圾回收动作。

为了解决标记-清除算法的效率问题,一种新的算法——复制算法应运而生:

2. 复制算法

复制算法(Copying)的出现一定程度上解决了标记-清除算法的效率问题。它的核心思想就是将可用的内存(Available Memory)分为大小相等的两块,每次为对象分配内存时只使用其中的一块,一旦当前正在使用的内存空间的不足了,我们就将该块内存空间中的存活对象全部复制到另一块内存空间上,然后再将之前的整块内存空间清空即可。整个复制算法的过程如下:

cbc5c46196054ea5918a2e79d90c528a.jpg

初始情况下,所有对象都只会被分配在活动内存空间中。当GC需要工作时,GC首先会将所有的存活对象都复制在空闲空间中,然后在清空整个原来的活动空间,此时旧的空闲空间就变成了新的活动空间了。

ae02c17b5b5f4074836aca63f7a57261.jpg

由于这种垃圾收集算法直接对半个内存区域进行回收,因此不用担心内存碎片的情况,在分配内存时只需移动堆顶指针,按顺序分配内存即可,实现简单,运行高效。

这种垃圾回收算法的问题主要有两个:

  1. 内存浪费:这种收集算法最大的问题就在于将内存一分为二,相当于我们总在使用一半的内存。
  2. 复制效率:如果复制算法被用在了对象存活率相当高的内存区域,我们就不得不大量的进行复制操作,此时复制操作的效率就很低了。

由于复制算法不太适合在对象存活率高的内存区域进行内存回收,因此又诞生了一种新的算法——标记-整理算法:

3. 标记-整理算法

标记-整理算法(Mark-Compact)的标记过程于标记-清除算法相同,但是后续的算法不是直接清除可回收对象,而是将所有的存活对象都向一端移动,然后再清理掉边界以外的所有内存。算法如图所示:

e4c068c65c534ef7bfa405bcb24882cb.jpg

标记-整理算法虽然不会造成内存碎片也不会浪费内存空间,但是需要整理对象的内存地址,因此效率上并不如复制算法。

4.分代收集算法

在有了前几种特点鲜明的垃圾收集算法之后,虚拟机的开发者们仍然没有停下脚步,他们根据对象存活周期将内存分为了几个不同的区域,并根据不同的区域的特点采取最适当的收集算法,这种算法就被称为分代收集算法(Generational Collection)。

简单来说,堆内存作为主要为对象分配空间的内存可以被分为新生代和老年代。由于在新生代中98%的对象都是“朝生夕死”的,此时我们就应该采用复制算法,但是我们没有必要将内存一分为二,那样做太浪费内存了。通常我们将新生代的内存按照8:1:1的比例分为一块较大的Eden空间和两块较小的Survivor空间,如下图所示。

8b6faa2e9f104334adb7b9a4b3a179fa.png

当GC需要回收对象时,将Eden空间和Survivor空间(from)中存活着的对象全部复制到另一块Survivor空间(to)上,最后清理掉Eden空间和from空间。使用这样的复制算法,内存空间只有10%会被“浪费”掉。

但是使用这种复制算法仍然有一个问题,那就是如果Eden空间和Survivor空间(from)中存活着的对象较多超过了另一块Survivor空间(to)的大小该怎么办?此时我们需要依赖其它内存也就是老年代内存,将一部分对象复制到老年代中,剩下的对象复制到to空间去。那么GC又该怎么确定哪些对象应该去老年代内存,哪些对象应该去to空间呢?

原来虚拟机给每个对象定义了一个年龄(Age)计数器,对象在Eden区出生后年龄为0,当它经历了一次GC,并被复制到Survivor区后,它的年龄变成了1。这些对象没熬过一次GC年龄就会增加1岁,当年龄达到阈值(默认15)之后,它就变成了老年对象,并被复制到老年代中。

除此之外,大对象(需要大量连续内存空间的Java对象如数组)也可以直接被放入老年代。

由于老年代存放的都是一些年龄较大的或者比较大的对象,他们的存活率都比较高,所以在老年代中通常采用标记-整理算法。

除了新生代与老年代之外,在JavaSE 7 之前还存在着永久代,用来存储一些存活期超长通常不需要被回收的对象,如字符串常量,类信息等等,这些对象在Java运行时内存区域中都属于方法区,因此很多人就将方法区等同于了永久代。但是在Java 8之后,永久代被废弃,取而代之的是在本地内存中的元空间MetaSpace。

0b272d2329ab442093bbdacff3b4f789.jpg

很多人认为永久代或者现在的元空间并不需要垃圾收集,这其实是错误的,只是因为回收废弃常量和废弃的类的条件比较苛刻,因此在永久代的垃圾收集进行的不是那么的频繁。因此在永久代中通常采用标记-整理算法

JVM在进行GC时,并非每次都对上面三个内存区域一起回收的,大部分时候回收的都是指新生代。因此GC按照回收的区域又分了两种类型,一种是普通GC(minor GC),一种是全局GC(major GC or Full GC),它们所针对的区域如下。

  • 普通GC(minor GC):只针对新生代区域的GC。
  • 全局GC(major GC or Full GC):针对年老代的GC,偶尔伴随对新生代的GC以及对永久代的GC。

由于年老代与永久代相对来说GC效果不好,而且二者的内存使用增长速度也慢,因此一般情况下,需要经过好几次普通GC,才会触发一次全局GC。

5.总结

在本篇博客中,博主与大家一起学习了几种不同垃圾收集算法,以及它们各个的特点。其实我们可以说没有最好的收集算法,只有最合适的算法。针对不同内存区域对象存活的特点,选择不同垃圾收集算法,这也许就是为什么分代收集算法几乎是所有商业虚拟机都采用的垃圾收集算法了吧。好了,讲了这么多,今天的博客就到这里了,咱们下次再见~。