Golang GC(垃圾回收) - 三色标记算法

Go 在 1.5 之后开始使用三色标记清除算法做垃圾回收,这里主要介绍三色标记清楚算法的工作原理。

并行垃圾回收是如何工作的

三色标记清楚算法(tricolor mark-and-sweep algorithm) 能够让系统的 GC 暂停时间成为能够预测的问题。调度器能够在很短的时间内实现 GC 调度,并且对源程序的影响极小。

下面我们来看看三色标记清楚算法是如何工作的
首先假设有下面的代码

var A  LinkedListNode
var B  LinkedListNode
//...
// C
B.next = &LinkedListNode{next:nil} 
//...
// D
A.next = &LinkedListNode{next:nil}
// C.next = E
*(B.next).next = &LinkedListNode{next:nil}
// B.next = E
B.next = *(B.next).next
B.next = nil

第一步,程序运行了一会儿后 GC 开始工作。

假设最开始有三个节点A,B,C。 作为根节点,红色的节点 A 和 B 始终都能够被访问到。然后进行一次赋值

// C
B.next = &LinkedListNode{next:nil}

这个新对象我们认为是 C。

垃圾收集器把所有对象放置到黑色,灰色,白色三个集合里。现在因为垃圾收集器还没有运行起来,所以三个节点都在白色集合中。

第二步,程序创建一个新对象 D。

我们新建一个节点 D,并将其赋值给 A.next。即

// D
A.next = &LinkedListNode{next:nil}

需要注意的是,作为一个新的内存对象,需要将 D 放置在灰色区域中。
为什么要讲新的内存对象放在灰色区域中了,这里有一个规则,如果一个指针域发生了变化,则被指向的对象需要变色。因为所有新建的内存对象都需要将其地址赋值个一个引用,所以他们将会立即变为灰色。(为什么 C 不是灰色?)、

第三步,GC 周期开始。

在开始 GC 的时候,根节点会被移入灰色区域。此时 A,B,D 三个节点都在灰色区域中。由于所有的 Goroutine 要么是程序正常逻辑,要么是 GC 程序,而 GC 和程序逻辑是并行的,所以程序逻辑和 GC 过程应该是交替占用 CPU 资源的。

第四步 GC 继续,扫描内存对象

在扫描内存对象的时候,GC 收集器将会把该内存对象标记为黑色,然后将其子内存对象标记为灰色。在任一阶段,我们都能够计算当前 GC 收集器需要进行的移动步数:2 * |white| + |grey|,在每一次扫描 GC 收集器都至少需要进行一次移动,直到达到当前灰色区域内存对象数目为 0。

第五步,程序创建了一个新对象 E。

程序此时的逻辑为,新赋值一个内存对象 E 给 C.next

// C.next = E
*(B.next).next = &LinkedListNode{next:nil}

按照之前的规则,新建的内存对象需要放置在灰色区域,如图

程序新建了一个对象,这样给垃圾收集器的扫描带来了更多的步骤。这里也说明,程序申请大量的新对象,会延迟 GC 最终的清除操作。值得一提的是,从 GC 开始后白色集合的体积会逐渐减小,直到垃圾收集器真正清理堆空间的后才会再填入新的内存对象。

第六步,程序修改了指针

当执行了

// B.next = E
B.next = *(B.next).next

程序里就没有其他对象可以访问对象 C 了。 这就意味着垃圾收集器将要把 C 留在白色集合,在 GC 的最后环节将回收它。

第七步,GC 扫描对象 D

把 D 移动到 黑色集合,D 没有子内存对象,所以没有需要移动到灰色集合的。

第八步,程序设置变量

程序执行了 B.next = nil,然后 E 变的不可达了(虽然 C 指向 E,但是 C 不可达)。不过 E 在 灰色集合它不会被回收,这是不是就说明 E 会造成内存泄漏了?也不会,E 会在下次 GC 执行时被回收。

三色标记清除法只保证在 GC 开始时不可达的对象,会在 GC 结束时被释放回收。

第九步,GC 扫描对象 E

垃圾收集器将 E 移动到黑色集合。注意 C 没有被移动,因为 C 不是 E 的子内存对象(E 是 C 的子内存对象)。

第十步,GC 扫描对象 B

将 B 移动到黑色集合。之后灰色集合就没有对象了。

第十一步,GC 释放白色集合的对象

现在在灰色集合里没有对象了。垃圾收集器知道白色集合里的所有对象都是不可达的。这里白色集合里只有对象 C,会被 GC 释放回收空间。
不可达的对象 E 将会存活到下一次的 GC,因为它是在 GC 的过程中变的不可达的,而不是 GC 开始前。

第十二步,区域变色

在三色标记清楚算法的实现中,垃圾收集器不需要移动或者给对象重新标记颜色,这里直接将原来代表黑色集合重新解释为代表白色。这里我们可以理解为把黑色集合该做白色集合。简单高效。

总结

这个 GC 过程还是有两次的 STW(stop the world) 过程

  1. 进行 root 内存对象的栈扫描
  2. 标记阶段的终止暂停

另外标记阶段的终止暂停在之后将被去除

参考
Golang’s Real-time GC in Theory and Practice
Go语言实时GC - 三色标记算法