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會變成不可達狀态并且會在下一次垃圾回收器的處理循環中被回收掉。