Go的三色标记GC

fzu_huang · · 6090 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

三色标记

三色标记的原理如下:
整个进程空间里申请每个对象占据的内存可以视为一个图, 初始状态下每个内存对象都是白色标记,先stop the world,将扫描任务作为多个并发的goroutine立即入队给调度器,进而被CPU处理,第一轮先扫描所有可达的内存对象,标记为灰色放入队列;第二轮可以恢复start the world,将第一步队列中的对象引用的对象置为灰色加入队列,一个对象引用的所有对象都置灰并加入队列后,这个对象才能置为黑色并从队列之中取出。循环往复,最后队列为空时,整个图剩下的白色内存空间即不可到达的对象,即没有被引用的对象; 第三轮再次stop the world,将第二轮过程中新增对象申请的内存进行标记(灰色),这里使用了writebarrier(写屏障)去记录这些内存的身份;

整个gc的流程如下图:

注意到:
mark 有两个过程。

首先从 root 开始遍历,root 包括全局指针和 goroutine 栈上的指针,标记为灰色。遍历灰色队列。

re-scan 全局指针和栈。因为 mark 和用户程序是并行的,所以在过程 1 的时候可能会有新的对象分配,这个时候就需要通过写屏障(write barrier)记录下来。re-scan 再完成检查一下。

Stop The World 有两个过程。

第一个是 GC 将要开始的时候,这个时候主要是一些准备工作,比如 enable write barrier。

第二个过程就是上面提到的 re-scan 过程。如果这个时候没有 stw,那么 mark 将无休止。

mark完毕后start the world进行并行清理,对于并行清理,GC 初始化的时候就会启动 bgsweep()这个协程并一直在后台阻塞, 开始清理时将这个协程唤醒并给主M去做并发的sweep。

内存管理都是基于 span 的,mheap_ 是一个全局的变量,所有分配的对象都会记录在 mheap_ 中。在标记的时候,我们只要找到对对象对应的 span 进行标记,清扫的时候扫描 span,没有标记的 span 就可以回收了。

另外:1.8以后的golang将第一步的stop the world 也取消了,这又是一次优化。

写屏障

关于写屏障的用处 如下面的例子,这个例子修改自知乎上的一个问答,在此表示感谢:

GC前:
stack->a->b ; a为栈中申请的对象,b为堆中申请的对象,a对象中存在对b的引用;

stack->c ; c 也是栈中申请的对象。

stop the world, mark。 这里a,c都会被标记为灰色;b为白色
start the world 反复mark。
由于是并发的mark,我们假设c先被处理,c没有引用其他对象,所以直接置黑,从队列中取出;此时c为黑色,a为灰色,b为白色

假设这时用户做了如下操作:

a=nil
new(d);
c->b; 即,将a中对b的引用置为空(你也可以理解为将a中对其他任何内存对象的引用都清空),随即申请d对象,然后在c中增加对b的引用。

由于c已经是黑色,所以不会再去扫描他,那么本次内存扫描就不可能找得到b;而d对象由于刚申请出来,还没有被引用,所以这里只对a进行了mark:a:黑色,b:白色;c:黑色;d:白色

这时用户又做了:
b->d; 由于b无法被扫描到,这里显然d也不会被扫描到。 这样的状况会一直持续到这轮反复mark结束(即灰色队列为空)。

stop the world, mark termination。 sweep。 整个GC结束, b,d的内存空间都是白色,所以在sweep时会被清理掉。如何避免这种误清理呢?

写屏障的功能就是在 c->b发生时,对b做一个标记, 以及在a->d发生时,对d做一个标记,这样,在进入第二次stop the world, mark termination时,这时候我们确保不会再有新增内存的引用操作,在进行一次反复mark,虽然无法通过c->b->d来扫描b和d,但是由于写屏障的标记,我们就能将b,d这两个残留的白色对象进行扫描,标记为灰色, 并最终标记为黑色。

简而言之,写屏障的作用大致是: 可以捕获 '没有STW的时候并发mark期间对白色对象新建立的内存引用'。


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:fzu_huang

查看原文:Go的三色标记GC

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

6090 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传