GC

三色標記清除算法

Golang中採用 三色標記清除算法（tricolor mark-and-sweep algorithm） 進行GC。由於支持寫屏障（write barrier)了，GC過程和程序可以併發運行。

三色標記清除算核心原則就是根據每個對象的顏色，分到不同的顏色集合中，對象的顏色是在標記階段完成的。三色是黑白灰三種顏色，每種顏色的集合都有特別的含義：

• 黑色集合

  該集合下的對象沒有引用任何白色對象（即該對象沒有指針指向白色對象）

• 白色集合

  掃描標記結束之後，白色集合裏面的對象就是要進行垃圾回收的，該對象允許有指針指向黑色對象。

• 灰色集合

  可能有指針指向白色對象。它是一箇中間狀態，只有該集合下不在存在任何對象時候，才能進行最終的清除操作。

過程

標記清除算法核心不變要素是沒有黑色的對象能夠指向白色集合對象。當垃圾回收開始，全部對象標記爲白色，然後垃圾回收器會遍歷所有根對象並把它們標記爲灰色。根對象就是程序能直接訪問到的對象，包括全局變量以及棧、寄存器上的裏面的變量。在這之後，垃圾回收器選取一個灰色的對象，首先把它變爲黑色，然後開始尋找去確定這個對象是否有指針指向白色集合的對象，若找到則把找到的對象由標記爲灰色，並將其白色集合中移入到灰色集合中。就這樣持續下去，直到灰色集合中沒有任何對象爲止。

爲了支持能夠併發進行垃圾回收，Golang在垃圾回收過程中採用寫屏障，每次堆中的指針被修改時候寫屏障都會執行，寫屏障會將該指針指向的對象標記爲灰色，然後放入灰色集合（因爲纔對象現在是可觸達的了），然後繼續掃描該對象。

舉個例子說明寫屏障的重要性：

假定標記完成的瞬間，A對象是黑色，B是白色，然後A的對象指針字段f由空指針改成指向B，若沒有寫屏障的話，清除階段B就會被清除掉，那邊A的f字段就變成了懸浮指針，這是有問題的。若存在寫屏障那麼f字段改變的時候，f指向的B就會放入到灰色集合中，然後繼續掃描，B最終也會變成黑色的，那麼清除階段它也就不會被清除了。