在go语言垃圾收集器中如何使用三色算法的原理及过程浅析

2023-06-01 00:00:00 算法 如何使用 浅析

Go垃圾收集器的操作基于三色算法,三色算法不是Go语言独有的,可以在其他编程语言中使用。

Go中使用的算法的正式名称是tricolor mark-and-sweep algorithm。

它可以与程序同时工作并使用编写器屏障。这意味着当一个 Go 程序运行时,Go 调度器负责应用程序和垃圾收集器的调度。

这就好像 Go 调度程序必须处理具有多个goroutine 的常规应用程序!


三色算法背后的核心思想来自

Edsger W. Dijkstra、
Leslie Lamport、
AJ Martin、
CS Scholten 、
EFM Steffens

并首次在名为On-the-Fly Garbage Collection: An Exercise in Cooperation的论文中进行了说明。


三色标记和清除算法背后的主要原理是它根据算法分配的颜色将堆中的对象分成三个不同的集合。

现在是时候谈谈每个颜色集的含义了。

这个黑色集合的对象保证有指向白色集合的任何对象的指针。


然而,白集对象可以具有指向黑集对象的指针,因为这对垃圾收集器的操作没有影响。

灰色集的对象可能具有指向白色集的某些对象的点。

最后。

白色集合的对象是垃圾收集的候选对象。


请注意,没有物体可以直接从黑色集合进入白色集合,这允许算法运行并能够清除白色集合上的对象。

此外,黑色组的任何对象都不能直接指向白色组的对象。


因此,当垃圾收集开始时,所有对象都是白色的,垃圾收集器会访问所有根对象并将它们涂成灰色。

根是应用程序可以直接访问的对象,包括全局变量和堆栈上的其他东西。

这些对象主要依赖于特定程序的 Go 代码。


之后,垃圾收集器选择一个灰色对象,将其设为黑色,并开始查看该对象是否具有指向白色集合中其他对象的指针。

这意味着当一个灰色对象被扫描以寻找指向其他对象的指针时,它是黑色的。

如果该扫描发现该特定对象具有一个或多个指向白色对象的指针,则将该白色对象放入灰色集合中。

只要灰色集中存在对象,此过程就会一直进行。

之后,白色集合中的对象不可达,可以拒绝它们的内存空间。

因此,此时,白色集合的元素被称为垃圾回收。

请注意,如果灰色集合中的某个对象在垃圾回收周期的某个时间点变得无法访问,
那么它将不会在此垃圾回收周期中被回收,而是在下一个周期中被回收!
虽然这不是最佳情况,但也没有那么糟糕。


在此过程中,正在运行的应用程序称为mutator。

mutator 运行一个名为write barrier的小函数,每次修改堆中的指针时都会执行该函数。

如果堆中一个对象的指针被修改,这意味着这个对象现在是可达的,写屏障将它涂成灰色并将它放入灰色集合中

mutator 负责黑色集合中没有元素具有指向白色集合元素的指针这一不变性。
这是在写屏障功能的帮助下完成的。
未能完成这个不变量将破坏垃圾收集过程,
并且很可能会以一种非常糟糕和不受欢迎的方式使您的程序崩溃!

Go垃圾收集也可以应用于通道等变量。

当垃圾收集器发现某个通道不可达时,即通道变量无法再访问时,即使通道没有关闭,它也会释放其资源。


Go允许您通过在Go代码中放置runtime.GC()语句来手动启动垃圾收集。

但是,请记住,runtime.GC()会阻塞调用者并且它可能会阻塞整个程序,尤其是当你正在运行一个包含许多对象的非常繁忙的 Go 程序时。

这主要是因为您无法在其他一切都在快速变化时执行垃圾收集,因为这不会让垃圾收集器有机会清楚地识别白色、黑色和灰色集合的成员。

这种垃圾收集状态称为垃圾收集 sage-point。


请注意,Go 团队一直在改进 Go 垃圾收集器。

他们正试图通过减少对三组数据执行的扫描次数来使其更快。

然而,尽管进行了各种优化,但算法背后的总体思想保持不变。

相关文章