Go垃圾回收之三色标记算法

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

转自公众号“灰子学技术”,原文链接:https://mp.weixin.qq.com/s/SFJoSSbvv3KyYKz4osUnFw

三色标记法介绍:

三色标记法(tricolor mark-and-sweep algorithm)是传统 Mark-Sweep 的一个改进,它是一个并发的 GC 算法,在Golang中被用作垃圾回收的算法,但是也会有一个缺陷,可能程序中的垃圾产生的速度会大于垃圾收集的速度,这样会导致程序中的垃圾越来越多无法被收集掉。原理如下所示:

step 1: 创建:白、灰、黑 三个集合。

step 2: 将所有对象放入白色集合中。

step 3: 从根节点开始遍历所有对象,把遍历到的对象从白色集合放入灰色集合(备注:这里放入灰色集合的都是根节点的对象)。

step 4: 遍历灰色集合,将灰色对象引用的对象(备注:这里指的是灰色对象引用到的所有对象,包括灰色节点间接引用的那些对象)从白色集合放入灰色集合,然后将分析过的灰色对象放入黑色集合。

step 5: 直到灰色中无任何对象。

step 6: 通过写屏障(write-barrier)检测对象有变化,重复以上操作(备注:因为 mark 和用户程序是并行的,所以在上一步执行的时候可能会有新的对象分配,写屏障是为了解决这个问题引入的)。

step 7: 收集所有白色对象(垃圾)。

例子如下所示:

 1. 初始阶段,假设当前的对象调用情况如下所示,root ->A->B/A->C/A<->D;root->F; E; G->H;

根据算法,会将所有的对象都放到白色集合当中,对应于step 1和step 2。

2. GC开始扫描,这里会从根节点开始,遍历发现只有A和F是根节点,于是将A、F从白色集合移动到灰色集合当中,在白色结合中之后剩下B、C、D、E、G、H这些节点,对应于step 3。

3. GC继续扫描灰色集合,会将灰色集合中的节点中引用的节点移动到灰色集合当中,本例中A节点引用的节点B、C、D会被移动到灰色集合中,紧接着A发现自己引用的所有子节点都已经在灰色集合了,便会被移动到黑色集合中,同时F节点没有自节点,也会被移动到黑色集合当中,对应于step 4。

4. GC会循环遍历灰色集合,直到灰色集合之中没有节点为止,在本例中,发现B、C、D都没有子节点在白色集合中,便将B、C、D都移动到黑色集合中,对应于step 5。

5. 此时只剩下E、G、H在白色集合中,剩下的对象都在黑色集合中,GC便清除白色集合中的对象,也就是进行回收这些对象,对应于step 7。

6. 上面的垃圾回收结束之后,GC会在进行一步操作,也就是将黑色集合变色成白色集合,供下一次垃圾回收使用。

参考文档


一张图了解三色标记法:http://idiotsky.top/2017/08/16/gc-three-color/

golang里gc相关的write barrier(写屏障)是个什么样的过程或者概念?:https://www.zhihu.com/question/62000722/answer/193462425

02.2跟雨痕看go源码- 并发清理与三色标记:https://blog.csdn.net/bairongdong1/article/details/52216360

Go的三色标记GC:https://segmentfault.com/a/1190000012597428

Golang GC(垃圾回收) - 三色标记算法:https://juejin.im/post/5c62d45ee51d457fa44f4404

Golang’s Real-time GC in Theory and Practice:https://making.pusher.com/golangs-real-time-gc-in-theory-and-practice/

Garbage Collection In Go : Part I - Semantics:https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html


灰子学技术:


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

本文来自:简书

感谢作者:灰常出色

查看原文:Go垃圾回收之三色标记算法

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

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