### 三色算法 Go 基于三色算法的垃圾回收器。 > Tip: 请注意，三色算法不是 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*的论文中得到了说明。 三色标记和清除算法背后的主要原理是，它根据堆的颜色将堆的对象划分为三个不同的集合，这些颜色由算法分配。现在是时候讨论每种颜色集的含义了。保证**黑色集合**的对象没有指向**白色集合**的任何对象的指针。 但是，白色集合的对象可以具有指向黑色集的对象的指针，因为这对垃圾收集器的操作没有影响。**灰色集合**的对象可能具有指向白色集合的某些对象的指针。最后，白色集合的对象是垃圾收集的候选对象。 请注意，没有对象可以直接从黑色集合转到白色集合，这允许算法进行操作并能够清除白色集合上的对象。此外，黑色集合的任何对象都不能直接指向白色集合的对象。 此后，垃圾收集器选择一个灰色对象，使其变为黑色，然后开始查看该对象是否具有指向白色集合中其他对象的指针。这意味着在扫描灰色对象以寻找指向其他对象的指针时，它会被涂成黑色。如果该扫描发现该特定对象具有一个或多个指向白色对象的指针，则会将该白色对象放入灰色集合中。只要灰色集合中存在对象，此过程就会持续进行。之后，白色集合中的对象将无法访问，并且它们的存储空间可以被重用。因此，在这一点上，我们说白色集合里的元素被垃圾回收了。 > Tip: 请注意，如果在垃圾回收周期的某个时刻灰色集合的对象变得不可访问，则不会在该垃圾回收周期中将其收集，而是在下一个垃圾回收中将其收集！尽管这不是最佳情况，但还不错。 在此过程中，正在运行的应用程序称为**修改器(mutator)**。 mutator 运行一个名为**写屏障(write barrier)**的小函数，每次修改堆中的指针时都会执行该函数。如果修改了堆中某个对象的指针，这意味着该对象现在可以访问，则写入屏障将其着色为灰色并将其放入灰色集合中。 > mutator 负责保持黑色集合中没有任何元素的指针去指向白色集合中的元素。这是在写屏障方法的帮助下完成的。如果维持这个不变状态失败的话，会毁坏垃圾回收过程，并且很可能会以一种丑陋和非预期的方式破坏你的程序！ 结果堆显示为已连接对象的图形，如图 2.1 所示，该图演示了垃圾回收周期的单个阶段。  因此，我们有三种不同颜色：黑色、白色和灰色。当算法开始的时候，所有对象标记为白色。随着算法继续进行，白色对象移到了其它两种颜色集合的一种里面。最后留在白色集合里面的对象会在将来某个时间点被清理掉。 在前面的图里，你可以看到白色对象 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)**。 你可以在https://github.com/golang/go/blob/master/src/runtime/mgc.go里找到垃圾回收器相关的go代码。你可以进一步了解这个，如果你想了解更多关于垃圾回收操作的东西。 > Tip: go 团队一直在优化垃圾回收器，主要是通过降低垃圾回收器所需要处理三种集合上数据的扫描次数来让它更快。但是尽管进行各种优化，其背后算法的整体原理还是一样的。