GC #

三色标记清除算法 #

Golang中采用 三色标记清除算法（tricolor mark-and-sweep algorithm） 进行GC。由于支持写屏障（write barrier)了，GC过程和程序可以并发运行。

三色标记清除算核心原则就是根据每个对象的颜色，分到不同的颜色集合中，对象的颜色是在标记阶段完成的。三色是黑白灰三种颜色，每种颜色的集合都有特别的含义：

• 黑色集合

  该集合下的对象没有引用任何白色对象（即该对象没有指针指向白色对象）

• 白色集合

  扫描标记结束之后，白色集合里面的对象就是要进行垃圾回收的，该对象允许有指针指向黑色对象。

• 灰色集合

  可能有指针指向白色对象。它是一个中间状态，只有该集合下不在存在任何对象时候，才能进行最终的清除操作。

过程 #

标记清除算法核心不变要素是没有黑色的对象能够指向白色集合对象。当垃圾回收开始，全部对象标记为白色，然后垃圾回收器会遍历所有根对象并把它们标记为灰色。根对象就是程序能直接访问到的对象，包括全局变量以及栈、寄存器上的里面的变量。在这之后，垃圾回收器选取一个灰色的对象，首先把它变为黑色，然后开始寻找去确定这个对象是否有指针指向白色集合的对象，若找到则把找到的对象由标记为灰色，并将其白色集合中移入到灰色集合中。就这样持续下去，直到灰色集合中没有任何对象为止。

为了支持能够并发进行垃圾回收，Golang在垃圾回收过程中采用写屏障，每次堆中的指针被修改时候写屏障都会执行，写屏障会将该指针指向的对象标记为灰色，然后放入灰色集合（因为才对象现在是可触达的了），然后继续扫描该对象。

举个例子说明写屏障的重要性：

假定标记完成的瞬间，A对象是黑色，B是白色，然后A的对象指针字段f由空指针改成指向B，若没有写屏障的话，清除阶段B就会被清除掉，那边A的f字段就变成了悬浮指针，这是有问题的。若存在写屏障那么f字段改变的时候，f指向的B就会放入到灰色集合中，然后继续扫描，B最终也会变成黑色的，那么清除阶段它也就不会被清除了。