GC算法,java垃圾回收算法分类详解

算法 INFO院院长 96℃ 0评论

GC策略解决了哪些问题?

既然是要进行自动GC,那必然会有相应的策略,而这些策略解决了哪些问题呢,粗略的来说,主要有以下几点。

1、哪些对象可以被回收。

2、何时回收这些对象。

3、采用什么样的方式回收。

GC策略采用的何种算法

有关上面所提到的三个问题,其实最主要的一个问题就是第一个,也就是哪些对象才是可以回收的,有一种比较简单直观的办法,它的效率较高,被称作引用计数算法,其原理是:此对象有一个引用,则+1;删除一个引用,则-1。只用收集计数为0的对象。

缺点是:

(1)无法处理循环引用的问题。如:对象A和B分别有字段b、a,令A.b=B和B.a=A,除此之外这2个对象再无任何引用,那实际上这2个对象已经不可能再被访问,但是引用计数算法却无法回收他们。

(2)引用计数的方法需要编译器的配合,编译器需要为此对象生成额外的代码。如赋值函数将此对象赋值给一个引用时,需要增加此对象的引用计数。还有就是,当一个引用变量的生命周期结束时,需要更新此对象的引用计数器。引用计数的方法由于存在显著的缺点,实际上并未被JVM所使用。想象一下,假设JVM采用这种GC策略,那么程序猿在编写的程序的时候,下面这样的代码就不要指望再出现了。

java default" style="overflow:auto;white-space:nowrap;width:100%;">
public class Object {
   
    Object field = null;
       
    public static void main(String[] args) {
        Thread thread = new Thread(new Runnable() {
            public void run() {
                Object objectA = new Object();
                Object objectB = new Object();//1
                objectA.field = objectB;
                objectB.field = objectA;//2
                //to do something
                objectA = null;
                objectB = null;//3
            }
        });
        thread.start();
        while (true);
    }
       
}

这段代码看起来有点刻意为之,但其实在实际编程过程当中,是经常出现的,比如两个一对一关系的数据库对象,各自保持着对方的引用,最后一个无限循环只是为了保持JVM不退出,没什么实际意义。

对于我们现在使用的GC来说,当thread线程运行结束后,会将objectA和objectB全部作为待回收的对象,而如果我们的GC采用上面所说的引用计数算法,则这两个对象永远不会被回收,即便我们在使用后显示的将对象归为空值也毫无作用。

这里LZ大致解释一下,在代码中LZ标注了1、2、3三个数字,当第1个地方的语句执行完以后,两个对象的引用计数全部为1。当第2个地方的语句执行完以后,两个对象的引用计数就全部变成了2。当第3个地方的语句执行完以后,也就是将二者全部归为空值以后,二者的引用计数仍然为1。根据引用计数算法的回收规则,引用计数没有归0的时候是不会被回收的。

根搜索算法

由于引用计数算法的缺陷,所以JVM一般会采用一种新的算法,叫做根搜索算法。它的处理方式就是,设立若干种根对象,当任何一个根对象到某一个对象均不可达时,则认为这个对象是可以被回收的。

GC算法,java垃圾回收算法分类详解 图1

就拿上图来说,ObjectD和ObjectE是互相关联的,但是由于GC roots到这两个对象不可达,所以最终D和E还是会被当做GC的对象,上图若是采用引用计数法,则A-E五个对象都不会被回收,说到GC roots(GC根),在JAVA语言中,可以当做GC roots的对象有以下几种:

1、虚拟机栈中的引用的对象。

2、方法区中的类静态属性引用的对象。

3、方法区中的常量引用的对象。

4、本地方法栈中JNI的引用的对象。

第一和第四种都是指的方法的本地变量表,第二种表达的意思比较清晰,第三种主要指的是声明为final的常量值。

根搜索算法解决的是垃圾搜集的基本问题,也就是上面提到的第一个问题,也是最关键的问题,就是哪些对象可以被回收,不过垃圾收集显然还需要解决后两个问题,什么时候回收以及如何回收,在根搜索算法的基础上,现代虚拟机的实现当中,垃圾搜集的算法主要有三种,分别是标记-清除算法、复制算法、标记-整理算法,这三种算法都扩充了根搜索算法,不过它们理解起来还是非常好理解的。

首先,我们回想一下上一章提到的根搜索算法,它可以解决我们应该回收哪些对象的问题,但是它显然还不能承担垃圾搜集的重任,因为我们在程序(程序也就是指我们运行在JVM上的JAVA程序)运行期间如果想进行垃圾回收,就必须让GC线程与程序当中的线程互相配合,才能在不影响程序运行的前提下,顺利的将垃圾进行回收。

为了达到这个目的,标记/清除算法就应运而生了,它的做法是当堆中的有效内存空间(available memory)被耗尽的时候,就会停止整个程序(也被成为stop the world),然后进行两项工作,第一项则是标记,第二项则是清除

(1)标记:标记的过程其实就是,遍历所有的GC Roots,然后将所有GC Roots可达的对象标记为存活的对象。

(2)清除:清除的过程将遍历堆中所有的对象,将没有标记的对象全部清除掉。

其实这两个步骤并不是特别复杂,也很容易理解。LZ用通俗的话解释一下标记/清除算法,就是当程序运行期间,若可以使用的内存被耗尽的时候,GC线程就会被触发并将程序暂停,随后将依旧存活的对象标记一遍,最终再将堆中所有没被标记的对象全部清除掉,接下来便让程序恢复运行。

下面LZ给各位制作了一组描述上面过程的图片,结合着图片,我们来直观的看下这一过程,首先是第一张图。

GC算法,java垃圾回收算法分类详解 图2

这张图代表的是程序运行期间所有对象的状态,它们的标志位全部是0(也就是未标记,以下默认0就是未标记,1为已标记),假设这会儿有效内存空间耗尽了,JVM将会停止应用程序的运行并开启GC线程,然后开始进行标记工作,按照根搜索算法,标记完以后,对象的状态如下图。

GC算法,java垃圾回收算法分类详解 图3

可以看到,按照根搜索算法,所有从root对象可达的对象就被标记为了存活的对象,此时已经完成了第一阶段标记。接下来,就要执行第二阶段清除了,那么清除完以后,剩下的对象以及对象的状态如下图所示。

GC算法,java垃圾回收算法分类详解 图4

可以看到,没有被标记的对象将会回收清除掉,而被标记的对象将会留下,并且会将标记位重新归0。接下来就不用说了,唤醒停止的程序线程,让程序继续运行即可,其实这一过程并不复杂,甚至可以说非常简单,各位说对吗。不过其中有一点值得LZ一提,就是为什么非要停止程序的运行呢?这个其实也不难理解,LZ举个最简单的例子,假设我们的程序与GC线程是一起运行的,各位试想这样一种场景。

假设我们刚标记完图中最右边的那个对象,暂且记为A,结果此时在程序当中又new了一个新对象B,且A对象可以到达B对象,但是由于此时A对象已经标记结束,B对象此时的标记位依然是0,因为它错过了标记阶段,因此当接下来轮到清除阶段的时候,新对象B将会被苦逼的清除掉。如此一来,不难想象结果,GC线程将会导致程序无法正常工作。上面的结果当然令人无法接受,我们刚new了一个对象,结果经过一次GC,忽然变成null了,这还怎么玩?

标记/清除算法缺点

1、首先,它的缺点就是效率比较低(递归与全堆对象遍历),而且在进行GC的时候,需要停止应用程序,这会导致用户体验非常差劲,尤其对于交互式的应用程序来说简直是无法接受。试想一下,如果你玩一个网站,这个网站一个小时就挂五分钟,你还玩吗?

2、第二点主要的缺点,则是这种方式清理出来的空闲内存是不连续的,这点不难理解,我们的死亡对象都是随即的出现在内存的各个角落的,现在把它们清除之后,内存的布局自然会乱七八糟。而为了应付这一点,JVM就不得不维持一个内存的空闲列表,这又是一种开销。而且在分配数组对象的时候,寻找连续的内存空间会不太好找。

复制算法

我们首先一起来看一下复制算法的做法,复制算法将内存划分为两个区间,在任意时间点,所有动态分配的对象都只能分配在其中一个区间(称为活动区间),而另外一个区间(称为空闲区间)则是空闲的,当有效内存空间耗尽时,JVM将暂停程序运行,开启复制算法GC线程。接下来GC线程会将活动区间内的存活对象,全部复制到空闲区间,且严格按照内存地址依次排列,与此同时,GC线程将更新存活对象的内存引用地址指向新的内存地址。此时,空闲区间已经与活动区间交换,而垃圾对象现在已经全部留在了原来的活动区间,也就是现在的空闲区间。事实上,在活动区间转换为空间区间的同时,垃圾对象已经被一次性全部回收,LZ给各位绘制一幅图来说明问题,如下所示。

GC算法,java垃圾回收算法分类详解 图5

其实这个图依然是上一章的例子,只不过此时内存被复制算法分成了两部分,下面我们看下当复制算法的GC线程处理之后,两个区域会变成什么样子,如下所示。

GC算法,java垃圾回收算法分类详解 图6

可以看到,1和4号对象被清除了,而2、3、5、6号对象则是规则的排列在刚才的空闲区间,也就是现在的活动区间之内。此时左半部分已经变成了空闲区间,不难想象,在下一次GC之后,左边将会再次变成活动区间。很明显,复制算法弥补了标记/清除算法中,内存布局混乱的缺点。不过与此同时,它的缺点也是相当明显的。

1、它浪费了一半的内存,这太要命了。

2、如果对象的存活率很高,我们可以极端一点,假设是100%存活,那么我们需要将所有对象都复制一遍,并将所有引用地址重置一遍。复制这一工作所花费的时间,在对象存活率达到一定程度时,将会变的不可忽视。

所以从以上描述不难看出,复制算法要想使用,最起码对象的存活率要非常低才行,而且最重要的是,我们必须要克服50%内存的浪费。

标记/整理算法

标记/整理算法与标记/清除算法非常相似,它也是分为两个阶段:标记和整理。

(1)标记:它的第一个阶段与标记/清除算法是一模一样的,均是遍历GC Roots,然后将存活的对象标记。

(2)整理:移动所有存活的对象,且按照内存地址次序依次排列,然后将末端内存地址以后的内存全部回收。因此,第二阶段才称为整理阶段。

它GC前后的图示与复制算法的图非常相似,只不过没有了活动区间和空闲区间的区别,而过程又与标记/清除算法非常相似,我们来看GC前内存中对象的状态与布局,如下图所示。

GC算法,java垃圾回收算法分类详解 图7

这张图其实与标记/清楚算法一模一样,只是LZ为了方便表示内存规则的连续排列,加了一个矩形表示内存区域。倘若此时GC线程开始工作,那么紧接着开始的就是标记阶段了。此阶段与标记/清除算法的标记阶段是一样一样的,我们看标记阶段过后对象的状态,如下图。

GC算法,java垃圾回收算法分类详解 图8

没什么可解释的,接下来,便应该是整理阶段了,我们来看当整理阶段处理完以后,内存的布局是如何的,如下图。

GC算法,java垃圾回收算法分类详解 图9

可以看到,标记的存活对象将会被整理,按照内存地址依次排列,而未被标记的内存会被清理掉。如此一来,当我们需要给新对象分配内存时,JVM只需要持有一个内存的起始地址即可,这比维护一个空闲列表显然少了许多开销,不难看出,标记/整理算法不仅可以弥补标记/清除算法当中,内存区域分散的缺点,也消除了复制算法当中,内存减半的高额代价,标记/整理算法唯一的缺点就是效率也不高,不仅要标记所有存活对象,还要整理所有存活对象的引用地址。从效率上来说,标记/整理算法要低于复制算法。这里LZ给各位总结一下三个算法的共同点以及它们各自的优势劣势,让各位对比一下,想必会更加清晰,它们的共同点主要有以下两点。

1、三个算法都基于根搜索算法去判断一个对象是否应该被回收,而支撑根搜索算法可以正常工作的理论依据,就是语法中变量作用域的相关内容。因此,要想防止内存泄露,最根本的办法就是掌握好变量作用域,而不应该使用前面内存管理杂谈一章中所提到的C/C++式内存管理方式。

2、在GC线程开启时,或者说GC过程开始时,它们都要暂停应用程序(stop the world)。

它们的区别LZ按照下面几点来给各位展示。(>表示前者要优于后者,=表示两者效果一样)

效率:复制算法>标记/整理算法>标记/清除算法(此处的效率只是简单的对比时间复杂度,实际情况不一定如此)。

内存整齐度:复制算法=标记/整理算法>标记/清除算法。

内存利用率:标记/整理算法=标记/清除算法>复制算法。

可以看到标记/清除算法是比较落后的算法了,但是后两种算法却是在此基础上建立的,俗话说“吃水不忘挖井人”,因此各位也莫要忘记了标记/清除这一算法前辈。而且,在某些时候,标记/清除也会有用武之地。

到此我们已经将三个算法了解清楚了,可以看出,效率上来说,复制算法是当之无愧的老大,但是却浪费了太多内存,而为了尽量兼顾上面所提到的三个指标,标记/整理算法相对来说更平滑一些,但效率上依然不尽如人意,它比复制算法多了一个标记的阶段,又比标记/清除多了一个整理内存的过程。最后介绍GC算法中的神级算法—–分代搜集算法。那么分代搜集算法是怎么处理GC的呢?

对象分类

上一章已经说过,分代搜集算法是针对对象的不同特性,而使用适合的算法,这里面并没有实际上的新算法产生。与其说分代搜集算法是第四个算法,不如说它是对前三个算法的实际应用。首先我们来探讨一下对象的不同特性,接下来LZ和各位来一起给这些对象选择GC算法。内存中的对象按照生命周期的长短大致可以分为三种,以下命名均为LZ个人的命名。

1、夭折对象:朝生夕灭的对象,通俗点讲就是活不了多久就得死的对象。例子:某一个方法的局域变量、循环内的临时变量等等。

2、老不死对象:这类对象一般活的比较久,岁数很大还不死,但归根结底,老不死对象也几乎早晚要死的,但也只是几乎而已。例子:缓存对象、数据库连接对象、单例对象(单例模式)等等。

3、不灭对象:此类对象一般一旦出生就几乎不死了,它们几乎会一直永生不灭,记得,只是几乎不灭而已。例子:String池中的对象(享元模式)、加载过的类信息等等

对象对应的内存区域

还记得前面介绍内存管理时,JVM对内存的划分吗?我们将上面三种对象对应到内存区域当中,就是夭折对象和老不死对象都在JAVA堆,而不灭对象在方法区,之前的一章中我们就已经说过,对于JAVA堆,JVM规范要求必须实现GC,因而对于夭折对象和老不死对象来说,死几乎是必然的结局,但也只是几乎,还是难免会有一些对象会一直存活到应用结束,然而JVM规范对方法区的GC并不做要求,所以假设一个JVM实现没有对方法区实现GC,那么不灭对象就是真的不灭对象了。由于不灭对象的生命周期过长,因此分代搜集算法就是针对的JAVA堆而设计的,也就是针对夭折对象和老不死对象

JAVA堆的对象回收(夭折对象和老不死对象)

有了以上分析,我们来看看分代搜集算法如何处理JAVA堆的内存回收的,也就是夭折对象与老不死对象的回收。夭折对象:这类对象朝生夕灭,存活时间短,还记得复制算法的使用要求吗?那就是对象存活率不能太高,因此夭折对象是最适合使用复制算法的。小疑问:50%内存的浪费怎么办?答疑:因为夭折对象一般存活率较低,因此可以不使用50%的内存作为空闲,一般的,使用两块10%的内存作为空闲和活动区间,而另外80%的内存,则是用来给新建对象分配内存的,一旦发生GC,将10%的活动区间与另外80%中存活的对象转移到10%的空闲区间,接下来,将之前90%的内存全部释放,以此类推。为了让各位更加清楚的看出来这个GC流程,LZ给出下面图示。

GC算法,java垃圾回收算法分类详解 图10

图中标注了三个区域中在各个阶段,各自内存的情况。相信看着图,它的GC流程已经不难理解了。不过有两点LZ需要提一下,第一点是使用这样的方式,我们只浪费了10%的内存,这个是可以接受的,因为我们换来了内存的整齐排列与GC速度。第二点是,这个策略的前提是,每次存活的对象占用的内存不能超过这10%的大小,一旦超过,多出的对象将无法复制。

为了解决上面的意外情况,也就是存活对象占用的内存太大时的情况,高手们将JAVA堆分成两部分来处理,上述三个区域则是第一部分,称为新生代或者年轻代,而余下的一部分,专门存放老不死对象的则称为年老代。是不是很贴切的名字呢?下面我们看看老不死对象的处理方式。老不死对象:这一类对象存活率非常高,因为它们大多是从新生代转过来的,就像人一样,活的年月久了,就变成老不死了。

通常情况下,以下两种情况发生的时候,对象会从新生代区域转到年老带区域。

1、在新生代里的每一个对象,都会有一个年龄,当这些对象的年龄到达一定程度时(年龄就是熬过的GC次数,每次GC如果对象存活下来,则年龄加1),则会被转到年老代,而这个转入年老代的年龄值,一般在JVM中是可以设置的。

2、在新生代存活对象占用的内存超过10%时,则多余的对象会放入年老代。这种时候,年老代就是新生代的“备用仓库”。

针对老不死对象的特性,显然不再适合使用复制算法,因为它的存活率太高,而且不要忘了,如果年老代再使用复制算法,它可是没有备用仓库的。因此一般针对老不死对象只能采用标记/整理或者标记/清除算法。

方法区的对象回收(不灭对象)

以上两种情况已经解决了GC的大部分问题,因为JAVA堆是GC的主要关注对象,而以上也已经包含了分代搜集算法的全部内容,接下来对于不灭对象的回收,已经不属于分代搜集算法的内容。不灭对象存在于方法区,在我们常用的hotspot虚拟机(JDK默认的JVM)中,方法区也被亲切的称为永久代,又是一个很贴切的名字不是吗?其实在很久很久以前,是不存在永久代的。当时永久代与年老代都存放在一起,里面包含了JAVA类的实例信息以及类信息。但是后来发现,对于类信息的卸载几乎很少发生,因此便将二者分离开来。幸运的是,这样做确实提高了不少性能,于是永久代便被拆分出来了这一部分区域的GC与年老代采用相似的方法,由于都没有“备用仓库”,二者都是只能使用标记/清除和标记/整理算法

回收的时机

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。

转载请注明:INFO院 » GC算法,java垃圾回收算法分类详解

喜欢 (0)or分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽