Golang 垃圾回收-三色标记清除算法

垃圾回收

垃圾回收是释放掉那些不再使用的内存空间的过程.

golang GC算法演变过程

版本 GC算法
v1.1 STW(stop the word)
v1.3 Mark STW,Sweep(标记清除)
v1.5 三色标记
v1.8 hybrid write barrier(三色标记基础上加入写屏障)

标记清除算法(mark and sweep)

主要包含两个步骤:

1.找出不可达对象,然后做上标记
2.回收标记好的对象

mark and sweep 算法在执行的时候,需要程序暂停,即stop the world

标记清除算法存在的问题

  • stop the world 程序暂停,即程序会出现卡顿
  • 标记需要扫描整个堆(heap)
  • 清楚数据会产生heap碎片

三色标记清除算法

三色标记清除算法背后的首要原则就是它把堆中的对象根据它们的颜色分到不同集合里面,颜色是根据算法进行标记的

  • 黑色集合 指针指向白色集合。
  • 白色集合中的对象允许有指针指向黑色集合,白色集合中的对象就是垃圾回收的候选对象。
  • 灰色集合可能会有指针指向白色集合里的对象。

写屏障

每次堆中的指针被修改写屏障都会去执行。如果堆中对象的指针被修改,就意味着那个对象现在是可触达的,写屏障会把它标记为灰色并把它放到灰色集合中。
修改器 运行写屏障,从而保证黑色集合中没有任何元素的指针去指向白色集合中的元素。
写屏障直观作用有两个:
1.process新生成的内存对象会被直接标记成灰色
2.位于黑色集合中的内存对象引用了一个白色集合中的对象,写屏障会将白色集合的这个对象标记为灰色

三色标记过程

1.首先:程序创建的对象都标记为白色。

2.gc开始:扫描所有可到达的对象,标记为灰色

3.从灰色对象中找到其引用对象标记为灰色,把灰色对象本身标记为黑色

4.监视对象中的内存修改,并持续上一步的操作,直到灰色标记的对象不存在

5.此时,gc回收白色对象。

6.最后,将所有黑色对象变为白色,并重复以上所有过程。

gc和用户逻辑如何并行操作

标记-清除(mark and sweep)算法的STW(stop the world)操作,就是runtime把所有的线程全部冻结掉,所有的线程全部冻结意味着用户逻辑是暂停的。这样所有的对象都不会被修改了,这时候去扫描是绝对安全的。
Go如何减短这个过程呢?标记-清除(mark and sweep)算法包含两部分逻辑:标记和清除。
我们知道Golang三色标记法中最后只剩下的黑白两种对象,黑色对象是程序恢复后接着使用的对象,如果不碰触黑色对象,只清除白色的对象,肯定不会影响程序逻辑。所以:清除操作和用户逻辑可以并发。
标记操作和用户逻辑也是并发的,用户逻辑会时常生成对象或者改变对象的引用,那么标记和用户逻辑如何并发呢?
process新生成对象的时候,GC该如何操作呢?不会乱吗?
我们看如下图,在此状态下:process程序又新生成了一个对象,我们设想会变成这样:

但是这样显然是不对的,因为按照三色标记法的步骤,这样新生成的对象A最后会被清除掉,这样会影响程序逻辑。
Golang为了解决这个问题,引入了写屏障这个机制。
写屏障:该屏障之前的写操作和之后的写操作相比,先被系统其它组件感知。
通俗的讲:就是在gc跑的过程中,可以监控对象的内存修改,并对对象进行重新标记。(实际上也是超短暂的stw,然后对对象进行标记)
在上述情况中,新生成的对象,一律都标位灰色!

那么,灰色或者黑色对象的引用改为白色对象的时候,Golang是该如何操作的?
看如下图,一个黑色对象引用了曾经标记的白色对象。

这时候,写屏障机制被触发,向GC发送信号,GC重新扫描对象并标位灰色。

因此,gc一旦开始,无论是创建对象还是对象的引用改变,都会先变为灰色。

参考文章

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!