Go 垃圾回收（三）——三色標記法是什麼鬼？

作者：由張三毛發表于攝影時間：2020-02-15

前言

當我們說 Go 的垃圾回收的時候，通常會提到三色標記法。有的同學可能聽到演算法裡有顏色就會開始慌，因為另一個同樣有顏色的演算法就是紅黑樹。紅黑樹的各種規則各種旋轉讓人各種頭疼，現在更可怕的是三色標記法竟然有三種顏色。那麼事實上真的這樣嗎？並不是，顏色多不一定難，因為這個三色標記法一分鐘就可以學會了。

追蹤式垃圾回收

（

Tracing garbage collection）

主流的兩類垃圾回收演算法有兩種，分別是追蹤式垃圾回收演算法

［1］

和引用計數法（ Reference counting ）。而三色標記法是屬於追蹤式垃圾回收演算法的一種。

追蹤式演算法的核心思想是判斷一個物件是否可達，因為一旦這個物件不可達就可以立刻被 GC 回收了。那麼我們怎麼判斷一個物件是否可達呢？很簡單，第一步找出所有的全域性變數和當前函式棧裡的變數，標記為可達。第二步，從已經標記的資料開始，進一步標記它們可訪問的變數，以此類推，專業術語叫傳遞閉包。

為什麼需要三色標記法？

在三色標記法之前有一個演算法叫

Mark-And-Sweep

（標記清掃），這個演算法就是嚴格按照追蹤式演算法的思路來實現的。這個演算法會設定一個標誌位來記錄物件是否被使用。最開始所有的標記位都是 0，如果發現物件是可達的就會置為 1，一步步下去就會呈現一個類似樹狀的結果。等標記的步驟完成後，會將未被標記的物件統一清理，再次把所有的標記位設定成 0 方便下次清理。

這個演算法最大的問題是 GC 執行期間需要把整個程式完全暫停，不能非同步進行 GC 操作。因為在不同階段標記清掃法的標誌位 0 和 1 有不同的含義，那麼新增的物件無論標記為什麼都有可能意外刪除這個物件。對實時性要求高的系統來說，這種需要長時間掛起的標記清掃法是不可接受的。所以就需要一個演算法來解決 GC 執行時程式長時間掛起的問題，那就三色標記法。

三色標記法好在哪裡？

相比傳統的標記清掃演算法，三色標記最大的好處是可以非同步執行，從而可以以中斷時間極少的代價或者完全沒有中斷來進行整個 GC。

三色標記法很簡單

［2］

。首先將物件用三種顏色表示，分別是白色、灰色和黑色。最開始所有物件都是白色的，然後把其中全域性變數和函式棧裡的物件置為灰色。第二步把灰色的物件全部置為黑色，然後把原先灰色物件指向的變數都置為灰色，以此類推。等發現沒有物件可以被置為灰色時，所有的白色變數就一定是需要被清理的垃圾了。

三色標記法（來自維基百科）

三色標記法因為多了一個白色的狀態來存放不確定的物件，所以可以非同步地執行。當然非同步執行的代價是可能會造成一些遺漏，因為那些早先被標記為黑色的物件可能目前已經是不可達的了。所以三色標記法是一個 false negative（假陰性）的演算法。

除了非同步標記的優點，三色標記法掌握了更多當前記憶體的資訊，因此可以更加精確地按需排程，而不用像標記清掃法那樣只能定時執行。

總結

所以三色標記法就是這麼簡單。在下一篇文章中我們會詳細講講一次完整的垃圾回收過程，順便解答一下在第一篇文章中埋下的問題——為什麼那兩個 goroutine 不能併發執行？