### 三色算法
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 團隊一直在優化垃圾回收器,主要是通過降低垃圾回收器所需要處理三種集合上數據的掃描次數來讓它更快。但是盡管進行各種優化,其背后算法的整體原理還是一樣的。
- 介紹
- 1 Go與操作系統
- 01.1 Go的歷史
- 01.2 Go的未來
- 01.3 Go的優點
- 01.3.1 Go是完美的么
- 01.3.2 什么是預處理器
- 01.3.3 godoc
- 01.4 編譯Go代碼
- 2 理解 Go 的內部構造
- Go 編譯器
- Go 的垃圾回收
- 三色算法
- 有關 Go 垃圾收集器操作的更多信息
- Maps, silces 與 Go 垃圾回收器
- Unsafe code
- 有關 unsafe 包
- 另一個 usafe 包的例子
- 從 Go 調用 C 代碼
- 在同一文件用 Go 調用 C 代碼
- 在單獨的文件用 Go 調用 C 代碼
- 從 C 調用 Go 代碼
- Go 包
- C 代碼
- defer 關鍵字
- 用 defer 打印日志
- Panic 和 Recover
- 單獨使用 Panic 函數
- 兩個好用的 UNIX 工具
- strace
- dtrace
- 配置 Go 開發環境
- go env 命令
- Go 匯編器
- 節點樹
- 進一步了解 Go 構建
- 創建 WebAssembly 代碼
- 對 Webassembly 的簡單介紹
- 為什么 WebAssembly 很重要
- Go 與 WebAssembly
- 示例
- 使用創建好的 WebAssembly 代碼
- Go 編碼風格建議
- 練習和相關鏈接
- 本章小結
- 3 Go基本數據類型
- 03.1 Go循環
- 03.1.1 for循環
- 03.1.2 while循環
- 03.1.3 range關鍵字
- 03.1.4 for循環代碼示例
- 03.3 Go切片
- 03.3.1 切片基本操作
- 03.3.2 切片的擴容
- 03.3.3 字節切片
- 03.3.4 copy()函數
- 03.3.5 多維切片
- 03.3.6 使用切片的代碼示例
- 03.3.7 使用sort.Slice()排序
- 03.4 Go 映射(map)
- 03.4.1 Map值為nil的坑
- 03.4.2 何時該使用Map?
- 03.5 Go 常量
- 03.5.1 常量生成器:iota
- 03.6 Go 指針
- 03.7 時間與日期的處理技巧
- 03.7.1 解析時間
- 03.7.2 解析時間的代碼示例
- 03.7.3 解析日期
- 03.7.4 解析日期的代碼示例
- 03.7.5 格式化時間與日期
- 03.8 延伸閱讀
- 03.9 練習
- 03.10 本章小結
- 9 并發-Goroutines,Channel和Pipeline
- 09.1 關于進程,線程和Go協程
- 09.1.1 Go調度器
- 09.1.2 并發與并行
- 09.2 Goroutines
- 09.2.1 創建一個Goroutine
- 09.2.2 創建多個Goroutine
- 09.3 優雅地結束goroutines
- 09.3.1 當Add()和Done()的數量不匹配時會發生什么?
- 09.4 Channel(通道)
- 09.4.1 通道的寫入
- 09.4.2 從通道接收數據
- 09.4.3 通道作為函數參數傳遞
- 09.5 管道
- 09.6 延展閱讀
- 09.7 練習
- 09.8 本章小結