00:00
行,那接着咱们往下讲啊,前面的话咱们说清楚了,在这个垃圾标记阶段,咱们用的这个算法叫做引用计数算法和可达性分析算法,那对于咱们Java来讲呢,咱们使用的叫可达性分析算法,对吧,或者也称为呢,叫根搜索算法。嗯,那对于呢,像Python这样语言,它使用的叫引用技术算法,但是Python呢,注意他使用引用技术的时候呢,他需要去解会解决这个循环引用的问题啊,咱们前面呢也给大家讲过了,那么接下来的话呢,咱们来讲第二个环节叫做清除阶段。好,那对于清除阶段的话呢,我们这里边儿主要涉及到了有三种算法,第一个呢叫做标记清除算法,那第二呢叫做复制算法,第三个呢叫标记压缩算法,那包括呢,这三种算法的一个对比啊,在面试当中呢,也是经常会被问到的啊,这个呢,大家都需要啊清楚行,那这块呢,我们就来看一下具体的这个内容。行,先看来这样一个描述,就是呢,当成功的区分出内存当中的存活对象和死亡对象以后呢,JC接下来的任务呢,就是要执行垃圾回收了,哎,释放掉无用的内存啊,无用的这个对象所占用的这个内存,那以便呢有足够的可用空间,内存空间呢,咱们为新对象呢进行分配。
01:12
啊,非常的简单好理解对吧,就像大家呢,你在家里边去清理自己家里边儿这个垃圾一样,啊,屋里边这个折腾的很乱了是吧,说想收拾一下,那这时候呢,你得,诶是不是也分成两个过程啊,第一个过程的话,你得看一看家里边哪些东西不用了,标记一下是吧?哎,我们确定一下说啊这些东西不用了。啊,然后第二个环节呢,诶下边呢,开始收拾了啊,这个我们是想扔了呀,还是给他压缩一下呀,还是送人呢,还是这个在闲鱼上卖了呀,对吧?哎,就是你具体的一个清理的一个过程。那现在呢,也比较流行一个词呢,叫做断舍离是吧,就是家里边这个东西呢,有些你不用了,你长期留着也没有意义啊,该清理就清理,从这个思维上来讲呢,每天回家呢,诶屋里边也比较整洁啊,简洁一些啊,你也有这个比较空闲的这个精力呢,你去想你重点的这个事儿啊,家里乱糟糟的,有时候呢,也会分散你个人的精力,对吧?那换一个角度来讲呢,比如说家里边像北京啊这个租个房子呢,这个价格也不低,家里边儿呢,本身比如说你就租了一个20平的一个空间,那其中呢,五平米放的这个东西呢,你呃一直就不用,那你其五其实呢,这五平米的空间呢,还得付着租金啊,你这个东西呢,还不用,实际上还得浪费的是吧?啊,这叫讲究,叫断舍离啊。
02:25
行,那对于咱们这个垃圾回收也是一样,那你先标记完,然后呢,接下来我们看怎么回收,下边呢,咱们说的就是这个第二个阶段啊,就是回收清除的这个阶段,那常见的三种算法呢,刚才我们也已经提到了,行,那接着咱们往下看。那首先呢,咱们带着大家呢,了解的一个叫做标记清除算法啊,叫mark sweep算法,这个英文的话呢,大家最好也记一下,有的时候呢,我们看网上一些帖子啊,包括一些书当中啊,他就直接说mark sweep。因为我们分成了叫mark阶段和sweep啊两个阶段啊,用英文来表示呢,就是这个,所以呢也稍微对照一下。那首先的话呢,我们看这个算法这个背景,这个算法的话呢,是一个非常基础和常见的垃圾数据算法,那也就是说呢,咱们如果你要自己去写一个垃圾清除阶段的算法的话呢,诶想必大家呢,也是比较直接的呢,会想到这样的一种算法,就是你要想去实现的话,你你的那个思路其实就是这种算法,所以说它是比较基础的,哎,这个算法呢,被这个叫卡西这样的,呃,杰卡西这个人在1960年的时候呢,提出来并应用到这个list的语言当中了。
03:28
这个前面的我们其实提过这个利索语言还记得吗?讲什么时候提过呀。哎,就是咱们讲这个垃圾收集的时候是吧,说到了这个类索语言呢,是世界上第一门啊,在六六年当中就有了第一门语言,它使用了叫动态的内存分配和这个垃圾回收,那自然而然的你涉及到垃圾回收了,哎,我们就涉及到这个标记清除算法,所以呢,它是一脉相承的,OK,那么具体的我们看一下这个执行的过程是什么样子的。所以呢,当最终有效的内存空间啊被耗尽的时候呢,咱们这时候呢,要进行JC了,那要进行JC的时候呢,咱们就会停止整个程序啊把这个过程呢,咱们称为叫stop the word就是咱们简写为呢叫STW。
04:11
这个后边呢,咱们下一章专门呢,有很多的概念给大家去讲解分析,那其中呢,SW呢,诶这是我们要说的其中的一个概念。啊,也就是呢,当我们要进行垃圾标记的,呃,垃圾这个回收的时候呢,我们在标记的时候呢,其实需要呢,把当前应用程序呢给它停掉,也就是呢,所有的这个用户线程呢,先停一停。因为呢,我们时刻程序要运行的话呢,还有可能是不是要制造一些新的垃圾啊,那么这时候我们要保持这个程序的一致性,先停下来,我们的垃圾回收的线程呢,现在呢,就整个标记一下,看看哪些呢是垃圾啊,这呢就成为我们这个叫标记的一个环节。哎,成为一个标记的环节,那么第二个环节呢,我们称为呢,叫清除的一个环节。那就清楚一个环节好,那么标记的时候呢,怎么做呢,说垃圾回收器,它从这个根节点开始呢,进行一个变历,哎,从这个根节点呢,开始进行变历,标记所有被引用的对象。
05:05
这时候大家一定要注意,很多书上呢,包括视频上的讲解都是错误的啊,说呢标记清除啊,先把这个垃圾的这些对象呢,给它标记出来,然后呢,下边一个环节给它清掉,说错了。说错了,标记的是什么呀?注意咱们标记的呢,是被引用的对象,也就是说呢,咱们标记的恰好是垃圾的反面是可达对象,是非垃圾的对象。对吧,哎,但是你想咱们从这个根节点出发,咱们能够关联到的是不是也仅仅是你这些可达的对象,你想通过这个根节点出发,你想关联567,那也不可能,而且说呢,你要真关联到的话呢,那他还就不是垃圾了。是吧,就成这样一个情况了,所以说咱们这个标记的这个环节啊,咱标记的呢,是非垃圾对象,或者也称为呢,叫做可达对象。OK,这个一定要注意啊,很多书中的和视频中讲的是错的,大家一定要别被误导了,行,那么这个标记到哪呢?咱们把这个标记呢,记录在这个对象的header当中,对象头当中,咱们前面呢讲过对象头对吧?OK,下一个叫清除阶段,清除阶段的话呢,我们就对堆当中的所有的对象呢进行一个便利。
06:18
啊,这里所谓的线性变量就是所有的都走一遍,比如我们一个循环,你想便利一百一到100之内的所有的自然数,那就是线性变历,就是100次,对吧。说如果呢,我们发现某个对象呢,还在当中没有标记过,没有标记过意味着你就不是可达对象。那我们就将其回收。对吧,哎,这就是这样个环节,那如果要用个图来表示的话呢,诶大家可以看这个图啊,或者呢,大家看一下这个还是我们爬桑里边画的这些图啊,其实我也是呢,从这里边这个给他这个。诶剪切了一下是吧,哎剪切过来的看这也可以啊,一样的,这个看不全,咱们看这吧,那这呢是我们举的两个根节点的例子,然后呢,在我们下边这个对空间当中,哎,下边这个对空间当中这个白色区域呢,表示的叫空闲区域,那非白色区域呢,剩下的都是我们有对象的这个哎区域行,然后呢,我们通过这个根基点出发呀,咱们就看看哪些对象呢是可达的,我这儿呢,用绿色呢标志出来了,这两个可达,然后这儿呢,诶到这到这,诶这可达,然后黑色的话呢,就属于不可达的,也就是说我们没有在hi的当中进行过标记的对象。
07:24
哎,这是我们说的第一个环节,第一个环节其实类似于一个递归便利是吧,诶那没有便利所有的对象,因为有些呢不可达嘛,然后第二个环节呢,我们称为呢,叫清除阶段,咱们这些时候呢,就线性便利一下,就是我们内存中不是说这儿像这儿这儿这儿这儿这是不是都是我们内存中有空间占用的这些区域,对吧?我们把这些区域呢,全都线性遍历一遍,如果你发现有的对象呢,Hier当中没有过标记,像我们这里边黑色的,咱们就把它清除掉。哎,这个时候呢,就这样子的。这就是咱们所谓的这个标记清除算法,实际上呢,也是非常简单直接的一种算法。
08:02
对吧?诶那举个例子的话呢,就比如说这是一个餐厅,这个餐厅,然后这呢,就是每一个人呗,这个有这个占用的这个位置就相当一个人,然后每个人的话呢,他会用这个餐巾纸啊,餐巾纸的话呢,如果你要用过了,用完了这个呢,其实我们说认为就是个垃圾啊行,咱们现在比如说有个机器人啊,这我画一个,就比如说这个机器人啊,这个机器人的话呢,他现在呢,就在我们这个啊餐厅当中啊进行一个便利,他来回走,看看说哪些呢,这个是垃圾啊哪些这个餐巾纸呢,用过了他就要回收下,那怎么办呀,他就呢,诶走一下,看看这里边每个人啊,走每个人的时候呢,如果说这个人正在用餐巾纸,那这时候人家还还正在用呢,你不能给人家是不是收掉啊,诶你可以在这个人的这个餐巾纸上呢,比如说画一个小圈,画个小圈圈是吧?诶每个人都画一个小圈圈。那就是每个人用的这个是吧,都画个小圈圈,然后接下来的话呢,诶他再去这是第一个环节,我们称为叫标记环节了,第二个环节呢,就是这个机器人呢,他就诶从这个厂子里边把这个所有的这个呃,餐巾纸呢变了一遍,看看哪些餐巾纸上呢画过小圈圈,那画圈圈的那就说明人家还正在用呢,那没有画圈圈的,那就说明已经用过了,那你就把这个垃圾给它收理掉,清理掉。
09:12
就可以了。就是这样的一个逻辑。啊,就是举了一个生活中的例子啊,行,那这呢,就是我们说的这样一个算法的一个算是它的一个执行过程啊,这个过程呢,在面试当中,如果问到了,大家能够说出来,就是标记清楚两个环节。OK。那么标记清楚这个算法它的缺点是什么呀?上来呢就开始说缺点了,来大家顺便体会一下这个优点是啥呀?咱先说说人家优点吧。优点啊。嗯,其实这个优点的话呢,就是说它是比较基础,比较常见,那其实呢,就是我们比较容易去想到。对吧,哎,比较容易去理解啊,应该说这儿呢,就是它的一个优点。啊,这它一点行,那么缺点是什么呢?缺点呢倒是列的挺多啊,缺点第一个啊,说效率呢不算高。
10:00
这我一开始写呢,叫效率比较低,后来我给改了改啊,我说这叫效率不算高,为啥呢?因为咱们后边呢,是不是还要讲两种算法呀,那相较于另外两种算法的话呢,这个算法咱们只能算叫高不成低,不就算是一个居中的一个场景,所以呢,我这就别说人家太低了,你要这块你都太低了,那下边要遇到个更低的怎么办呢?对吧?所以这呢就写了个叫不算高啊,那这里边所谓的不算高,其实还是想强调一下,它不是太高是吧,不是特别好,原因呢,是因为它的这个便利的问题。便利的问题,大家看,就是我们第一个环节呢叫标记,标记的时候呢,咱们需要从那个根节点出发,递归的去便利你所有可达对象。啊,其实它的这个复杂度也算是一个O了是吧?嗯,这个虽然没有便利所有的这个对象啊,但是呢,它这个递归方式变利了,然后再接下来我们这个清除环节呢,你需要把所有的这个对空间当中这个对象呢全遍利一遍,那这呢是一个线性的全表对不对,这个全数据的一个便利,这呢又是个on级别的,所以呢,它相当于是经历过两次的一个全变利,所以呢,这个效率呢不算高,哎是从这个角度来说的,然后下一个在进行这个JC的时候,咱们需要停止整个应用程序,导致呢,用户体验呢就比较差一些。
11:14
啊,咱们刚才呢,是不是提到这个叫STW,叫stop the word这样的一个概念,那这时候呢,咱们需要停止一下用户这个线程,那需要我们垃圾回收线程开始去工作。啊,那显然的话呢,从用户的角度呢,感觉这个程序就稍微停顿了一下,这个体验呢就不是特别好。啊,就体验不太好,尤其对于这个跟客户端打交道的这样的一个场景,对吧?行,然后下个呢,说这种方式啊,清理出来这个空闲内存是不连续的,会产生内存的碎片。会产生一层碎片,那是不是就是这样子的?我们这时候呢,仅仅是把这个不再用的这个垃圾呢给回收掉了,你看这个空间呢,现在就是这种场景。就是这种场景,那这种场景会影响什么呀,就是咱们接下来如果再要是分配对象的话呢,你是不是也只能是在这种空闲的区域里边去挑着位置来用啊,那这里边儿我们就提到一个概念,叫做空闲列表。
12:07
会议列表前边是不是讲过?你看这样我们讲的话呢,咱们前后这个内容啊,是不是就都能给它连到一体了,对吧,咱们在讲这个对象的时候呢,提到这个对象实例化。对象实例化的时候啊,对象实例化诶,在这个对象实例化的时候呢,有一个环节呢,我们称为呢,就是创建对象的这个步骤的时候呢,叫分配这个内存空间,我们在堆里边呢,给人家对象放一个放在一个位置上,对吧,分配空间,分配空间的时候呢,我们提到过两种方式,第一种呢叫做指针碰撞,第二种呢,叫做空闲列表。啊,那区别是什么呀?就是咱们内存如果是规整的话呢,就是连续的这个空白的,那咱们就用指针碰撞,比如说呢,你这个内存占用的位置呢,是在这边啊,已经占用的是吧?没占用的空闲是在这这我们就有个指针,然后你要在分配对象呢,就在这分配,然后指针呢往这块去移,这叫指针碰撞,对吧?那么内存要是不规整的时候啊,你就需要呢,维护一个空闲列表,去记录哪些空间呢?诶被占用了,哪些空间没有被占用啊这呢就是一个空间列表,咱们前面讲过啊,大家并不陌生。
13:09
行,那你想想,你要是维护一个空间列表,本身这个空间列表是不是也要占据内存空间呀。这是一个对吧,你还要去去维护它,这是其一,那其二的话呢,就是说你想想,如果咱们这个内存呢,是这样的碎片化的,我现在呢,来了一个大对象,这个大对象呢,就需要从这个空间列表里边去找,看看哪个空间够,那如果说都不没有都不够,那你这如果是新生代的话呢,我们可以考虑放在老年代,那果已经是老年代了,那这块呢,还都够不够,盛不下,我们就要JC了,JC完以后还不够。咱们现在已经在JC了是吧?哎,已经在JC了,还放不下,那这时候是不是就可能会报这个oom这样的异常了呀。哎,这个大家注意对吧,这呢主要原因是因为你这种算法呢,它的这种碎片问题导致的,导致我们要维护它,导致我们这个大对象呢,有可能还盛不下。哎,这个大家注意一下,这呢都是它的一个缺点啊。
14:00
行,那下个问题的话呢,诶这个大家稍微注意一下,说何为清除啊,那整个呢,关于这个算法咱算是说完了,最后呢,给大家去解释一下怎么叫清,咱们刚才说了,你把不用的这个或者叫是没有在had中标记的那个对象,它就是垃圾了,我们要清除掉,那到底什么意义上呢,叫清除,是完全给它拿掉数据呢,制空还是怎么样的呢?诶你看这里边写了所谓的这个清除啊,并不是真的制空。啊,你说我们把它都改成是0000是吧,哎,不是这样子的,而是呢,把需要清除的对象的地址保存在空闲列表的地址表地址表里边。就说白了就是你这个对象还在那,但是我们没有指针指向你了,然后我把你的这个呃,对象的地址啊,放在我们空间列表里边,就表示呢,我们随时可以会使用,那下次有新对象呢,需要加载的时候呢,就判断垃圾的位置空间是不是够,那如果够呢,咱们就直接呢去覆盖原有的那个数据。能理解吧,就这里边呢,这个黑色呢,就好比是它还在这儿,只是呢,我们把它的地址呢记录到空间列表里了,下次呢,如果有对象就要往这放,直接呢覆盖掉现有的数据就可以。
15:06
那说到这儿呢,大家应该会想到一个问题,就是比如说你自己电脑当中啊,一不小心把你这个举个例子,比如说我这里边这个E盘呢,所有的我一不小心呢,做了一个格式化数据呢,诶从我们意义上来说就全没了,那实际上呢,这个数据呢,并没有给我们完全的清掉,而是说呢,这个我们把它这个地址呢,都回收过来了,那这个时候呢,大家可以使用一些这个硬盘恢复的软件,是把你这个内容完整的再恢复过来,对吧?但是这时候你要出一个点,就是说诶我这个盘里边如果你放了很多的这个东西的话呢,就你之前给格式化了,你不要再往这个盘里再放东西,因为你一放东西呢,是不是就会把原有的那个数据呢,就给它抹掉了呀。包括一些地址指针等等的,一抹掉,你再恢复的话,这个里边就不全了,就乱七八糟的,只要呢,你这个盘里边,你被一不小心格式化了以后呢,你没有往里边再去写入数据,这个时候呢,我们实际上呢,都是可以恢复的。哎,都是可以恢复的啊,这个大家要注意一下这个问题。
16:02
行,这呢,就是咱们所谓的这个叫标记侵入算法,哎,我们就说到这儿。
我来说两句