Junedayday Blog

六月天天的个人博客

0%

五分钟技术小分享 - 2022Week13

2020-03

2022-03-28 Go1.5的GC概览3 - Tri-color

在标记阶段,Go语言使用了 tri-color,也就是著名的三色标记法。在这篇文章里,详细地描述了这部分的实现。

原文链接 - https://go.dev/blog/go15gc

三色标记法是一种堆上对象的图算法。这里图的边Edge即指针,所以这里的关系是单向的。

In a tri-color collector, every object is either white, grey, or black and we view the heap as a graph of connected objects.

接下来,就是具体的三色标记法的工作了:

At the start of a GC cycle all objects are white. The GC visits all roots, which are objects directly accessible by the application such as globals and things on the stack, and colors these grey. The GC then chooses a grey object, blackens it, and then scans it for pointers to other objects. When this scan finds a pointer to a white object, it turns that object grey. This process repeats until there are no more grey objects. At this point, white objects are known to be unreachable and can be reused.

这一段内容很长,但描述得很直白,我简单概括下:

  • GC初始化
    • 将所有的对象设置为 白色
  • Mark的初始化
    • 将全局变量和栈上的对象,标记为 灰色
    • 这些灰色对象会被放入队列中
  • Mark的核心流程
    • 从队列中弹出一个灰色对象
    • 访问这个灰色对象的指针,将白色对象的转变为灰色对象,并加入到队列中
    • 将这个灰色对象标记为黑色,表示访问完毕
    • 重复上述过程,直到队列为空
  • 清理阶段
    • 将所有剩余的 白色对象 进行垃圾回收

我们重点看这里的 Mark的核心流程,里面有个关键问题:mutator(也就是运行中的程序)在不停地修改对象的指针,所以会出现各种异常情况,比如说让一个黑色对象指向白色对象(正常情况下,黑色对象指向的是黑色或者灰色)。

网上有很多关于三色标记的资料,不太清楚的朋友需要自行搜索,比如 https://segmentfault.com/a/1190000022030353

重点可以结合写屏障要解决的问题,进行理解。

这个时候,就引入了我们前面说的内容 - 写屏障write barrier

Go’s write barrier colors the now-reachable object grey if it is currently white, ensuring that the garbage collector will eventually scan it for pointers.

写屏障即会在每次发生指针变更时,加入一小段代码:比如检测到新的被指向的对象是白色,就将它修改为灰色,需要扫描。这只是一个简单例子,后续Go语言对写屏障进行了迭代,采用的写屏障技术是 混合写屏障,也就是 插入写屏障+删除写屏障

Github: https://github.com/Junedayday/code_reading

Blog: http://junes.tech/

Bilibili: https://space.bilibili.com/293775192

公众号: golangcoding

二维码