Go语言七篇入门教程七GC垃圾回收三色标记

时间:2022-09-03 11:10:20

GC

GC全称Garbage Collection

目前主流的垃圾回收算法有两类,分别是追踪式垃圾回收算法(Tracing garbage collection)和引用计数法( Reference counting )。
而三色标记法是属于追踪式垃圾回收算法的一种。

追踪式算法的核心思想是判断一个对象是否可达,因为一旦这个对象不可达就可以立刻被 GC 回收了。

如何判断一个对象是否可达

分为两步:

  • 第一步找出所有的全局变量和当前函数栈里的变量,标记为可达。
  • 第二步,从已经标记的数据开始,进一步标记它们可访问的变量,周而复始,这一过程也叫传递闭包。

在go推出三色标记法之前,go所使用的gc算法叫Mark-And-Sweep(标记清扫)

这个算法就是严格按照追踪式算法的思路来实现的。

  • 先设置一个标志位来记录对象是否被使用,最开始所有的标记位都是 0。
  • 如果发现对象是可达的就会置为1,一步步下去就会呈现一个类似树状的结果。
  • 等标记的步骤完成后,会将没有被标记的对象统一清理,再次把所有的标记位设置成 0, 以便下次进行清理。

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停,不能异步进行GC操作。因为在不同阶段标记清扫法的标志位 0 和 1 有不同的含义,那么新增的对象无论标记为什么都有可能意外删除这个对象。对实时性要求高的系统来说,这种需要长时间挂起的标记清扫法是不可接受的。所以就需要一个算法来解决 GC 运行时程序长时间挂起的问题,那就三色标记法。

三色标记法

三色标记法是传统 Mark-Sweep 的一个改进,它是一个并发的 GC 算法。on-the-fly

原理如下

整个进程空间里申请每个对象占据的内存可以视为一个图, 初始状态下每个内存对象都是白色标记。

stop the world,将扫描任务作为多个并发的goroutine立即入队给调度器,进而被CPU处理,第一轮先扫描所有可达的内存对象,标记为灰色放入队列

第二轮可以恢复start the world,将第一步队列中的对象引用的对象置为灰色加入队列,一个对象引用的所有对象都置灰并加入队列后,这个对象才能置为黑色并从队列之中取出。循环往复,最后队列为空时,整个图剩下的白色内存空间即不可到达的对象,即没有被引用的对象;

第三轮再次stop the world,将第二轮过程中新增对象申请的内存进行标记(灰色),这里使用了writebarrier(写屏障)去记录这些内存的身份;

这个算法可以实现 on-the-fly,也就是在程序执行的同时进行收集,并不需要暂停整个程序。

简化步骤如下:

Go语言七篇入门教程七GC垃圾回收三色标记

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

Go语言七篇入门教程七GC垃圾回收三色标记

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

Go语言七篇入门教程七GC垃圾回收三色标记

3、然后从根节点开始遍历所有对象(注意这里并不递归遍历),把遍历到的对象从白色集合放入灰色集合。

因为root set 指向了A、F,所以从根结点开始遍历的是A、F,所以是把A、F放到灰色集合中。

Go语言七篇入门教程七GC垃圾回收三色标记

4、之后遍历灰色集合,将灰色对象引用的对象从白色集合放入灰色集合,之后将此灰色对象放入黑色集合
我们可以发现这个A指向了B,C,D所以也就是把BCD放到灰色中,把A放到黑色中,而F没有指任何的对象,所以直接放到黑色中。

Go语言七篇入门教程七GC垃圾回收三色标记

5、重复 4 直到灰色中无任何对象

因为D指向了A所以D也放到了黑色中,而B和C能放到黑色集合中的道理和F一样,已经没有了可指向的对象了。

Go语言七篇入门教程七GC垃圾回收三色标记

6、通过write-barrier检测对象有无变化,重复以上操作

由于这个EGH并没有和RootSet有直接或是间接的关系,所以就会被清除。

Go语言七篇入门教程七GC垃圾回收三色标记

7、收集所有白色对象(垃圾)

Go语言七篇入门教程七GC垃圾回收三色标记

所以我们可以看出这里的情况,只要是和root set根集合直接相关的对象或是间接相关的对象都不会被清楚。只有不相关的才会被回收。

参考文档:

一张图讲解GC
关于write-barrier写屏障

以上就是Go语言七篇入门教程GC垃圾回收三色标记的详细内容,更多关于Go语言GC垃圾回收三色标记的资料请关注服务器之家其它相关文章!

如何学习Go

如果你是小白,你可以这样学习Go语言~

七篇入门Go语言

第一篇:Go简介初识

第二篇:程序结构&&数据类型的介绍

第三篇:函数方法接口的介绍

第四篇:通道与Goroutine的并发编程

第五篇:文件及包的操作与处理

第六篇:网络编程

第七篇:GC垃圾回收三色标记

原文链接:https://blog.csdn.net/weixin_45304503/article/details/119729349