### 三色算法 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 團隊一直在優化垃圾回收器，主要是通過降低垃圾回收器所需要處理三種集合上數據的掃描次數來讓它更快。但是盡管進行各種優化，其背后算法的整體原理還是一樣的。