【Go 原理】GC (上)三色标记法

golang GC 有了解吗?GC 时会发生什么?

关于GO的GC发展里程碑如下:

  • GoV1.3- 普通标记清除法,整体过程需要启动STW,效率极低。

  • GoV1.5- 三色标记法, 堆空间启动写屏障,栈空间不启动,全部扫描之后,需要重新扫描一次栈(需要STW),效率普通。

  • GoV1.8-三色标记法+混合写屏障机制, 栈空间不启动,堆空间启动。整个过程几乎不需要STW,效率较高。

什么是标记清除法?它的整体流程有哪些?它最大的缺点是什么?

V1.3 标记清除 (mark and sweep)

Go V1.3 之前的标记清除(mark and sweep)主要有两个主要的步骤:

  • 标记(Mark phase)
  • 清除(Sweep phase)

标记清除的整体流程:

  • 第一步,暂停程序业务逻辑, 找出不不可达的对象(5和6),和可达对象(1-2-3和4-7)。

    image-20211102114745493

  • 第⼆步,开始标记,程序找出它所有可达的对象(1-2-3和4-7),并做上标记。

    image-20211102114850117

  • 第三步,标记完了之后,然后开始清除未标记的对象(5和6)。

    image-20211102114927570

注:mark and sweep算法在执行的时候,需要程序暂停。即 STW(stop the world)STW的过程中,CPU不执行用户代码,全部用于垃圾回收,这个过程的影响很大,所以STW也是一些回收机制最大的难题和希望优化的点。所以在执行第三步的这段时间,程序会暂定停止任何工作,卡在那等待回收执行完毕。

  • 第四步,停⽌暂停,让程序继续跑。然后循环重复这个过程,直到process程序⽣生命周期结束。

Go V1.3版本之前就是按照以上来实施的, 在执行GC的基本流程就是首先启动STW暂停,然后执行标记,再执行数据回收,最后停止STW,如图所示。

image-20211102155242319

Go V1.3 做了简单的优化,将STW的步骤提前,减少STW暂停的时间范围。如下所示:

image-20211102155448530

无论怎么优化,Go V1.3都面临这个一个重要问题,就是mark-and-sweep 算法会暂停整个程序 。

标记-清除(mark and sweep)的缺点:

  • STWstop the world;让程序暂停,程序出现卡顿 (重要问题)
  • 标记需要扫描整个heap
  • 清除数据会产生heap碎片。

Go V1.3都面临这个一个重要问题,就是mark-and-sweep 算法会暂停整个程序。Go是如何面对并这个问题的呢?接下来Go V1.5版本就用三色并发标记法来优化这个问题。

V1.5 三⾊标记法

什么是三色标记法?标记过程中不使用STW将会发生什么事情?如何解决?

三色标记法:通过三个阶段的标记来确定需要清除的对象。具体步骤,① 新创建的对象都标记为白色。② 遍历根节点遍象,将遍历到的对象从白色集合放到灰色集合。③ 遍历灰色集合,将灰色对象引用的白色放到灰色集合,同时灰色对象放入黑色集合。④ 重复第三步,直至灰色集合中无任何对象。⑤ 回收白色对象,也就是回收垃圾。

不使用STW:标记过程中不使用STW将会出现对象丢失现象。

解决方案:插入屏障(强三色不变式)和删除屏障(弱三色不变式)。

所谓三色标记法实际上就是通过三个阶段的标记来确定需要清除的对象都有哪些。

  • 第一步 ,每次新创建的对象,默认的颜色都是标记为白色,如图所示。

    image-20211102160206143

  • 第二步,每次GC回收开始,会从根节点开始遍历所有对象,把遍历到的对象从白色集合放入灰色集合如图所示。

image-20211102160309275

  • 遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,之后将此灰色对象放入黑色集合,如图所示。

image-20211102160409273

  • 第四步, 重复第三步, 直到灰色中无任何对象,如图所示。

    image-20211102160510907

  • 第五步: 回收所有的白色标记表的对象,也就是回收垃圾,如图所示。

image-20211102160549314

以上我们将全部的白色对象进行删除回收,剩下的就是全部依赖的黑色对象。

以上便是三色并发标记法,不难看出,我们上面已经清楚的体现三色的特性。但是这里面可能会有很多并发流程均会被扫描,执行并发流程的内存可能相互依赖,为了在GC过程中保证数据的安全,我们在开始三色标记之前就会加上STW,在扫描确定黑白对象之后再放开STW。但是很明显这样的GC扫描的性能实在是太低了。

如果三色标记法,标记过程不使用STW将会发生什么事情?

第一步,假设目前黑色的有对象1和对象4, 灰色的有对象2和对象7,其他的为白色对象,且对象2是通过指针p指向对象3的,如图所示。

image-20211108085901433

第二步,目前黑色的有对象1和对象4, 灰色的有对象2和对象7,其他的为白色对象,且对象2是通过指针p指向对象3的,如图所示。

image-20211108090012154

第三步,与此同时灰色的对象2将指针p移除,那么白色的对象3实则就是被挂在了已经扫描完成的黑色的对象4下,如图所示。

image-20211108090055077

第四步,正常指向三色标记的算法逻辑,将所有灰色的对象标记为黑色,那么对象2和对象7就被标记成了黑色,如图所示。

image-20211108090134681

第五步,执行了三色标记的最后一步,将所有白色对象当做垃圾进行回收,如图所示。

image-20211108090203490

结果:本来是对象4合法引用的对象3,却被GC给“误杀”回收掉了。如果示例中的白色对象3还有很多下游对象的话,也会一并都清理掉。

在三色标记法中,出现对象丢失现象是不希望被发生的:

  • 条件1: 一个白色对象被黑色对象引用(白色被挂在黑色下);(强三色不变式可解决)
  • 条件2: 灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)。(弱三色不变式可解决)

如果当以上两个条件同时满足时,就会出现对象丢失现象!如果三色标记过程不启动STW,那么在GC扫描过程中,任意的对象均可能发生读写操作,如图所示,在还没有扫描到对象2的时候,已经标记为黑色的对象4,此时创建指针q,并且指向白色的对象3。

image-20211102162254314

为了防止这种现象的发生,最简单的方式就是STW,直接禁止掉其他用户程序对对象引用关系的干扰,但是STW的过程有明显的资源浪费,对所有的用户程序都有很大影响。那么是否可以在保证对象不丢失的情况下合理的尽可能的提高GC效率,减少STW时间呢?答案是可以的,我们只要使用一种机制,尝试去破坏上面的两个必要条件就可以了。

强三色不变式 vs 弱三色不变式

什么是强三色不变式?什么是弱三色不变式?它们为了解决什么问题?

强三色不变式:强制性的不允许黑色对象引用白色对象。

弱三色不变式:黑色对象可以引用白色对象,但是白色对象存在其他灰色对象的引用,或者可达它的链路上游存在灰色对象。

强三色不变式是为了破坏三色标记法中不希望出现现象的条件1,一个白色对象被黑色对象引用(白色被挂在黑色下),而被误杀的情况。

弱三色不变式是为了破坏三色标记法中不希望出现现象的条件2,灰色对象与它之间的可达关系的白色对象遭到破坏(灰色同时丢了该白色)

强三色不变色实际上是强制性的不允许黑色对象引用白色对象,这样就不会出现有白色对象被误删的情况。

image-20211102164352237
弱三色不变式强调,黑色对象可以引用白色对象,但是这个白色对象必须存在其他灰色对象对它的引用,或者可达它的链路上游存在灰色对象。 这样实则是黑色对象引用白色对象,白色对象处于一个危险被删除的状态,但是上游灰色对象的引用,可以保护该白色对象,使其安全。

image-20211102164410280

相关推荐

微信扫一扫,分享到朋友圈

【Go 原理】GC (上)三色标记法
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close