02.3.1 三色算法
go垃圾回收器的操作都是基于三色算法，这一章节主要来说明此算法。
三色算法并不是go独有的，它也会在其它编程语言中使用到
严格来说，在Go中这个算法的官方名称是叫做三色标记清除算法（tricolor mark-and-sweep algorithm）。它可以和程序一起并发工作并且使用写屏障（write barrier）。这就意味着，当Go程序员运行起来，go调度器去负责应用程序的调度，而垃圾回收器会像调度器处理常规应用程序一样，去使用多个goroutines去进行工作。你可以在第九章了解更多关于goroutines以及go调度器的相关内容，包括Go 并发 - Goroutines，Channels，和管道（Piplines）。
这个算法背后的核心思想是由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垃圾回收这部分对其算法进行进一步说明。
现在让我们来谈谈每种颜色集合代表的含义。黑色集合是为了确保没有任何指针指向白色集合。但是白色集合中的对象允许有指针指向黑色集合，因为这不会对垃圾回收器的操作产生影响。灰色集合可能会有指针指向白色集合里的对象。白色集合中的对象就是垃圾回收的候选对象。
注意到没有任何对象可以从黑色集合进到白色集合，这允许算法能够去操作并且清除白色集合里的对象。此外，没有任何黑色集合里的指针对象能够直接指向白色集合中的对象。
当垃圾回收开始，全部对象标记为白色，然后垃圾回收器会遍历所有根对象并把它们标记为灰色。根对象就是程序能直接访问到的对象，包括全局变量以及栈里面的东西。这些对象大多数取决于特定程序的go代码。在这之后，垃圾回收器选取一个灰色的对象，把它变为黑色，然后开始寻找去确定这个对象是否有指针指向白色集合的对象。这意味着当一个灰色对象由于被其它对象的指针所指而扫描到的时候，这个灰色对象会被标记为黑色。如果扫描发现这个灰色对象有一个或者更多指针指向白色对象时，会把所指向的白色对象放到灰色集合里。只要有灰色集合对象存在，这个过程就会一直进行下去。之后，白色集合里的对象就是没人访问的对象，并且它们所占用的内存可以被回收重用。因此，在这个点上，我们说白色集合里的元素被垃圾回收了。
如果垃圾回收过程中，一个灰色对象在某些情况变为不可达状态，它在那次垃圾回收中就不会被回收了，但是不是说下次也不会回收！尽管这不是最佳情况，但也没有那么糟
在这个过程中，运行应用程序被叫做修改器（mutator）。mutator去运行一个小的方法叫做写屏障(write barrier)，每次堆中的指针被修改写屏障都会去执行。如果堆中对象的指针被修改，就意味着那个对象现在是可触达的，写屏障会把它标记为灰色并把它放到灰色集合中。
mutator负责保持黑色集合中没有任何元素的指针去指向白色集合中的元素。这是在写屏障方法的帮助下完成的。如果维持这个不变状态失败的话，会毁坏垃圾回收过程，并且很可能会以一种丑陋和非预期的方式破坏你的程序。
堆可以看成许多连接对象的图，如下所示，展示了单独一个垃圾回收的过程。
因此，我们有三种不同颜色：黑色、白色和灰色。当算法开始的时候，所有对象标记为白色。随着算法继续进行，白色对象移到了其它两种颜色集合的一种里面。最后留在白色集合里面的对象会在将来某个时间点被清理掉。
在前面的图里，你可以看到白色对象E，它是在白色集合里而且可以访问对象F，E不会被任何其它的对象访问到因为没有其它指向E的指针，这使得E成为了垃圾回收的最佳候选对象！另外，对象A、B和C是根对象而且总是可达的，因此它们不会被垃圾回收掉。
接下来，算法会去处理留下的灰色集合元素，这意味着对象A和F会进入到黑色集合里。对象A会进入到黑色集合是因为它是一个根元素，而F会进入黑色集合是因为它没有指向任何其它对象但是是在灰色集合里。在对象A被垃圾回收之后，对象F会变成不可达状态并且会在下一次垃圾回收器的处理循环中被回收掉。
go垃圾回收也可以应用于其它变量例如channel！当垃圾回收器发现一个channel是不可达的而且channel变量再也不会被访问到，它就会释放掉它的资源甚至说channel还没被关闭！你将会了解更多channels的东西在第九章里，Go并发 - Groutines，Channel和Pipelines。
Go允许你通过在你的Go代码里放一个runtime.GC()的声明来手动去开启一次垃圾回收。但是，要记住一点，runtime.GC()会阻塞调用器，并且它可能会阻塞整个程序，尤其是如果你想运行一个非常繁忙的而且有很多对象的go程序。这种情况发生，主要是因为你不能在其他任何事都在频繁变化的时候去处理垃圾回收，因为这种情况不会给垃圾回收器机会，去清楚地确定白色、黑色和灰色集合里的成员。这种垃圾回收状态也被称作是垃圾回收安全点(garbage collection safe-point)。
你可以在这里找到垃圾回收器相关的高级go代码。你可以学习这个如果你想了解更多关于垃圾回收操作的东西。
go团队一直在优化垃圾回收器，主要是通过降低垃圾回收器所需要处理三种集合上数据的扫描次数来让它更快。但是尽管进行各种优化，其背后算法的整体原理还是一样的。
Last updated
