go 垃圾回收：三色算法

三色算法

go垃圾回收器的操作都是基于三色算法，这篇文章主要来说明此算法。

注意：三色算法并不是go独有的，它也会在其它编程语言中使用到

严格来说，在Go中这个算法的官方名称是叫做三色标记清除算法（tricolor mark-and-sweep algorithm）。它可以和程序一起并发工作并且使用写屏障（write barrier）。这就意味着，当Go程序员运行起来，go调度器去负责应用程序的调度，而垃圾回收器会像调度器处理常规应用程序一样，去使用多个goroutines去进行工作。

这个算法背后的核心思想是由Edsger W. Dijkstra，Leslie Lamport，A.J.Martin，C.S.Scholten和E.F.M.Steffens这些大佬提出的。算法首先发表在论文On-the-fly Garbage Collection：An Exercise in Cooperation上面。三色标记清除算法背后的首要原则就是它把堆中的对象根据它们的颜色分到不同集合里面。

现在让我们来谈谈每种颜色集合代表的含义。黑色集合是为了确保没有任何指针指向白色集合。但是白色集合中的对象允许有指针指向黑色集合，因为这不会对垃圾回收器的操作产生影响。灰色集合可能会有指针指向白色集合里的对象。白色集合中的对象就是垃圾回收的候选对象。

注意到没有任何对象可以从黑色集合进到白色集合，这允许算法能够去操作并且清除白色集合里的对象。此外，没有任何黑色集合里的指针对象能够直接指向白色集合中的对象。

当垃圾回收开始，全部对象标记为白色，然后垃圾回收器会遍历所有根对象并把它们标记为灰色。根对象就是程序能直接访问到的对象，包括全局变量以及栈里面的东西。这些对象大多数取决于特定程序的go代码。在这之后，垃圾回收器选取一个灰色的对象，把它变为黑色，然后开始寻找去确定这个对象是否有指针指向白色集合的对象。这意味着当一个灰色对象由于被其它对象的指针所指而扫描到的时候，这个灰色对象会被标记为黑色。如果扫描发现这个灰色对象有一个或者更多指针指向白色对象时，会把所指向的白色对象放到灰色集合里。只要有灰色集合对象存在，这个过程就会一直进行下去。之后，白色集合里的对象就是没人访问的对象，并且它们所占用的内存可以被回收重用。因此，在这个点上，我们说白色集合里的元素被垃圾回收了。

如果垃圾回收过程中，一个灰色对象在某些情况变为不可达状态，它在那次垃圾回收中就不会被回收了，但是不是说下次也不会回收！

在这个过程中，运行应用程序被叫做修改器（mutator）。mutator去运行一个小的方法叫做写屏障（write barrier），每次堆中的指针被修改写屏障都会去执行。如果堆中对象的指针被修改，就意味着那个对象现在是可触达的，写屏障会把它标记为灰色并把它放到灰色集合中。

mutator负责保持黑色集合中没有任何元素的指针去指向白色集合中的元素。这是在写屏障方法的帮助下完成的。如果维持这个不变状态失败的话，会毁坏垃圾回收过程，并且很可能会以一种丑陋和非预期的方式破坏你的程序。

堆可以看成许多连接对象的图，如下所示，展示了单独一个垃圾回收的过程。

我们有三种不同颜色：黑色、白色和黑色。当算法开始的时候，所有对象标记为白色。随着算法继续进行，白色对象移到了其它两种颜色集合的一种里面。最后留在白色集合里面的对象会在将来某个时间点被清理掉。

在前面的图里，你可以看到白色对象E，它是在白色集合里而且可以访问对象F，E不会被任何其它的对象访问到因为没有其它指向E的指针，这使得E成为了垃圾回收的最佳候选人！另外，对象A、B和C是根对象而且总是可达的，因此它们不会被垃圾回收掉。

接下来，算法会去处理留下的灰色集合元素，这意味着对象A和F会进入到黑色集合里。对象A会进入到黑色集合是因为它是一个根元素，而F会进入黑色集合是因为它没有指向任何其它对象但是是在灰色集合里。在对象A被垃圾回收之后，对象F会变成不可达状态并且会在下一次垃圾回收器的处理循环中被回收掉。