Go语言的GC是一个值得探讨深究的问题,从V1.3的标记清除法到V1.5的三色标记法,再到V1.8并沿用至今的三色标记法+混合写屏障机制,它的发展过程十分有趣。那么具体是怎样实现的呢?一起和野生菌来看看吧~
Go v1.3 之前的标记清除法(mark and weep)
GC :Garbage Collection 垃圾回收
STW :Stop the world —–>目的:减小这个时间
标记清除法流程
- 暂停程序业务逻辑,找出可达对象和不可达对象
- 开始标记,程序找出所有可达对象,并做上标记
- 标记完后,开始清除未标记的对象
- 停止暂停,程序继续运行,循环重复这个过程直到进程生命周期结束
标记清除法缺点
STW :让程序暂停,程序出现卡顿(主要问题)
标记需要扫描整个heap
清除数据会产生heap碎片
解决办法
原有:
方法一:那么我们考虑将3、4互换位置?
先停止 再清除,使清除异步,减小STW的时间范围
但是标记的时间仍然很长
方法二: 尝试采用新的标记模式来替代标记清除法
即三色标记法
Go v1.5 三色标记法
三色标记法流程
三色标记法中,我们在GC中统计3个集合:白色标记表、灰色标记表、黑色标记表
- 程序起初创建,全部标记为白色,将所有对象放入白色集合中
这里我们将程序的根节点集合展开的形式
- 遍历Root Set(非递归形式,只遍历一次),得到灰色节点
- 遍历灰色标记表,将可达的对象从白色标记为灰色;遍历后的灰色标记为黑色
重复上一步,直到灰色标记表中无任何对象
收集所有白色对象(垃圾)
循环多次,逐层将垃圾清除
三色标记如果不使用STW会存在问题吗?
答案是会的,举一个例子:
此时对象1、4已遍历标记完成,2、7已加入灰色标记表中
可以看出,已经标记为灰色的对象2,有指针p指向白的的对象3
现在还没有扫描对象2
但这时,由于无STW的保护,可能并发会有黑色对象4引用到了对象3,即q指针指向了对象3
与此同时,对象2将指针p移除,这样对象3就被挂在了已经扫描完成的黑色对象4下
再继续正常执行算法逻辑,对象2、7标记为黑色,而对象3因为对象4已经不会再扫描了,被当作垃圾回收清除了
这是就发生了三色标记法最不希望发生的事,总结来说就是两个被同时满足的条件:
条件1. 一个白色对象被黑色对象引用
条件2. 灰色对象不再引用这个白色对象
这时就发生了对象丢失的现象!
那么怎么解决呢?很直接的方式就是继续利用我们之前的STW,但是它浪费了很多资源,对用户程序有很大的影响
那么如何在保证对象不丢失的情况下尽可能的提高GC效率,减少STW时间呢?
这就需要提出强弱三色不变式了
强弱三色不变式
强三色不变式
强制性的不允许黑色对象引用白色对象(破坏条件1)
弱三色不变式
黑色对象可以引用白色,但白色对象存在其他灰色对象对它引用,或者可达它的链路上游存在灰色(破坏条件2)
所以可以看出,只要满足强/弱之一,即可保证对象不丢失
那么如何实现呢?这里就用到了屏障机制
屏障机制
屏障:就是加入额外的判断机制,不打扰正常的业务
插入写屏障
对象被引用时,触发的机制
具体操作
在黑色A对象引用B对象时,B对象被标记为灰色(满足强三色不变式)
为了不影响性能,不在栈上使用
这里,对象8,9是黑色对象新引用的对象,但只将8标记为了灰色,对象9仍然是白色
在准备回收白色前,重新遍历扫描一次栈空间,此时加STW暂停保护栈,防止有新的白色被黑色引用
不足
结束时需要STW重新扫描栈,大约消耗10-100ms
删除写屏障
对象被删除时,触发的机制
具体操作
被删除的对象,如果自身为灰色或白色,那么被标记为灰色(满足弱三色不变式)
但可能出现问题,如图中对象5未被删除
不足
回收精度低,一个对象即使被删除了最后一个指向它的指针也依旧可以存活过这一轮,在下一轮GC中被清理掉
Go v1.8混合写屏障机制
之前我们可以看到插入写屏障和删除写屏障都有一些不足
因此提出了混合写屏障机制
满足:变形的弱三色不变式
流程
- GC开始将栈上的对象全部扫描并标记为黑色(之后不再进行二次扫描,无需STW)
- GC期间,任何在栈上创建的新对象,均为黑色
- 被删除的对象标记为灰色
- 被添加的对象标记为灰色
真实场景
场景一:对象被一个堆对象删除引用,成为另一个栈对象的下游
场景二:对象被一个栈对象删除引用,成为另一个栈对象的下游
场景三:对象被一个堆对象删除引用,成为另一个堆对象的下游
场景四:对象被一个栈对象删除引用,成为另一个堆对象的下游