Golang GC

“标记-清扫”算法如同它的名字一样，算法分为“标记”和“清除”两个阶段：先“标记”出所有可以回收的对象，在标记完成后统一“清除”所有被标记的对象。

“标记-清扫”算法有下面缺点：
1、算法在执行的时候，需要暂停整个程序！即 stop the world, STW。
2、清除不用的内存时会产生内存碎片。

其中，STW 是最主要的缺点，Golang 中采用了一些措施来尽量缩短 STW 的时间。

Golang GC 如图 1 （摘自 Go GC: Latency Problem Solved）所示。

Golang GC 历史如表 1 所示（摘自：用 GODEBUG 看 GC）。

在“标记-清扫”算法中，如何标记可回收对象呢？先介绍一种朴素的方法：初始时，所有对象都是白色，从 GC Root 出发，把 GC Root 可达的所有对象都标记为黑色，标记结束后，还处于白色的对象是可以回收的。

三色标记法增加了灰色中间状态。在三色标记法中，对象有三种颜色：
黑色（Black）：表示对象是 GC Root 可达的，即使用中的对象，黑色是“已经被扫描的对象”。
灰色（Grey）：表示被黑色对象直接引用的对象，但还没对它进行扫描。
白色（White）：白色是对象的初始颜色，如果扫描完成后，对象依然还是白色的，说明此对象是垃圾对象。

三色标记法中有约束规则：黑色对象不能直接指向白色对象。 即黑色可以指向灰色，灰色可以指向白色。

三色标记法的主要流程如下：

1、初始时，所有对象被标记为白色。
2、寻找所有 GC Root 对象（比如被线程直接引用的对象），把 GC Root 对象标记为灰色。
3、把某个灰色对象标记为“黑色”，同时把它们引用的对象标记为“灰色”。
4、持续遍历每一个灰色对象，直到没有灰色对象。剩余“白色”对象为垃圾对象。

图 2 （摘自：Wikipedia）是三色标记法的一个示例。一轮标记结束后（即没有灰色对象时），对象 E、G、H 还处于白色，可以被安全地回收掉。

三色标记法的标记过程可以增量式（Incremental）地运行：GC 线程在遍历一部分的灰色对象后，应用线程可以接着运行，然后 GC 线程接着遍历其它灰色对象。这样， STW 的时间被拆为了多个小段。

注：三色标记法增量式运行时，应用线程可能会破坏三色标记法的约束规则（黑色对象不能直接指向白色对象），需要“写屏障”来避免这种情况出现。

为什么要有写屏障（Write Barrier）呢？前面提到过，是为了防止标记过程增量进行时，应用线程（goroutine）破坏三色标记法的约束规则（黑色对象不能直接指向白色对象）。

在 Go 1.7 的版本是“Dijkstra 写屏障” ，这个写屏障只监控堆上指针数据的变动，由于成本原因，没有监控栈上指针的变动，由于应用 goroutine 和 GC 的标记 goroutine 都在运行，当栈上的指针指向的对象变更为白色对象时，这个白色对象应当标记为黑色，需要再次扫描全局变量和栈，以免释放这类不该释放的对象。

在 Go 1.8 及以后的版本引入了“混合写屏障”，这个写屏障依然不监控栈上指针的变动，但是它的策略，使得无需再次扫描栈和全局变量，不过依然需要STW然后进行一些检查。