# 8.1 垃圾回收的基本想法 Go 實現的垃圾回收器是無分代（對象沒有代際之分）、 不整理（回收過程中不對對象進行移動與整理）、并發（與用戶代碼并發執行）的三色標記清掃算法。 從宏觀的角度來看，Go 運行時的垃圾回收器主要包含五個階段： | 階段 | 說明 | 賦值器狀態 | | :-: | :-- | :-: | | 清掃終止 | 為下一個階段的并發標記做準備工作，啟動寫屏障 | STW | | 標記 | 與賦值器并發執行，寫屏障處于開啟狀態 | 并發 | | 標記終止 | 保證一個周期內標記任務完成，停止寫屏障 | STW | | 內存清掃 | 將需要回收的內存歸還到堆中，寫屏障處于關閉狀態 | 并發 | | 內存歸還 | 將過多的內存歸還給操作系統，寫屏障處于關閉狀態 | 并發 | 對象整理的優勢是解決內存碎片問題以及“允許”使用順序內存分配器。 但 Go 運行時的分配算法基于 tcmalloc，基本上沒有碎片問題。 并且順序內存分配器在多線程的場景下并不適用。 Go 使用的是基于 tcmalloc 的現代內存分配算法，對對象進行整理不會帶來實質性的性能提升。 在這五個階段中，只有標記、內存清掃和內存歸還三個階段的寫屏障狀態是保持不變的。 在清掃終止過程中，寫屏障先出于關閉狀態， 而后對上個垃圾回收階段進行一些收尾工作（例如清理緩存池、停止調度器等等）， 然后才被啟動；在標記終止階段，寫屏障先出于啟動狀態，完成標記階段的收尾工作后， 寫屏障被關閉，并隨后對整個 GC 階段進行的各項數據進行統計等等收尾工作。 而在實際實現過程中，垃圾回收器通過`_GCoff`、`_GCMark`和`_GCMarktermination`三個標記來確定寫屏障狀態，這時寫屏障的啟動狀態嚴格的在`_GCoff`到`_GCMark`到`_GCMarktermination`再到`_GCoff`的切換中進行變化。 分代 GC 依賴分代假設，即 GC 將主要的回收目標放在新創建的對象上（存活時間短，更傾向于被回收）， 而非頻繁檢查所有對象。但 Go 的編譯器會通過逃逸分析將大部分新生對象存儲在棧上（棧直接被回收）， 只有那些需要長期存在的對象才會被分配到需要進行垃圾回收的堆中。 也就是說，分代 GC 回收的那些存活時間短的對象在 Go 中是直接被分配到棧上， 當 goroutine 死亡后棧也會被直接回收，不需要 GC 的參與，進而分代假設并沒有帶來直接優勢。 并且 Go 的垃圾回收器與用戶代碼并發執行，使得 STW 的時間與對象的代際、對象的 size 沒有關系。 Go 團隊更關注于如何更好地讓 GC 與用戶代碼并發執行（使用適當的 CPU 來執行垃圾回收）， 而非減少停頓時間這一單一目標上。 # 4.2 標記清掃法與三色抽象 自動內存管理的另一個重要的組成部分便是自動回收。在自動內存回收中， 垃圾回收器扮演一個十分重要的角色。通常， 垃圾回收器的執行過程可根據代碼的行為被劃分為兩個半獨立的組件： 賦值器（Mutator）和回收器（Collector）。 賦值器一詞最早由 Dijkstra 引入 \[Dijkstra et al., 1978\]，意指用戶態代碼。 因為對垃圾回收器而言，需要回收的內存是由用戶態的代碼產生的， 用戶態代碼僅僅只是在修改對象之間的引用關系（對象之間引用關系的一個有向圖，即對象圖） 進行操作。回收器即為程序運行時負責執行垃圾回收的代碼。 ## 4.2.1 串行標記清掃 原始的標記清掃方法將回收過程分為兩個階段： 1. 標記追蹤：從根集合（寄存器、執行棧、全局變量）開始遍歷對象圖，標記遇到的每個對象； ``` func mark() { worklist.Init() // 初始化標記 work 列表 for root := range roots { // 從根開始掃描 ref := *root if ref != nil && !isMarked(ref) { // 標記每個遇到的對象 setMarked(ref) worklist.Add(ref) for !worklist.Empty() { ref := worklist.Remove() // ref 已經標記過 for fld := range Pointers(ref) { child := *fld if child != nil && !isMarked(child) { setMarked(child) worlist.Add(child) } } } } } } ``` 2. 清掃回收：檢查堆中每一個對象，將所有未標記的對象當做垃圾進行回收。 ``` func sweep() { // 檢查堆區間內所有的對象 for scan := worklist.Start(); scan < worklist.End(); scan = scan.Next { if isMarked(scan) { unsetMarked(scan) } else { free(scan) // 將未標記的對象釋放 } } } ``` ## 4.2.2 三色抽象及其不變性 原始的標記清理是一個串行的過程，這種方法能夠簡化回收器的實現，因為只需要讓回收器開始執行時， 將并發執行的賦值器掛起。這種情況下，對用戶態代碼而言，回收器是一個原子操作。 那么能不能讓上面描述的過程并發執行呢？也就是說當賦值器在執行時，同時執行回收器呢？ 這就面臨一個非常嚴峻的問題：程序的正確性。當我們談論一個垃圾回收程序的正確性時， 實際上是在描述用戶態代碼必須保障回收器不會將存活的對象進行回收， 而回收器也必須保證賦值器能夠正確的訪問到已經被重新整理和移動的對象。 三色抽象只是一種描述追蹤式回收器的方法，在實踐中并沒有實際含義， 它的重要作用在于從邏輯上嚴密推導標記清理這種垃圾回收方法的正確性。 也就是說，當我們談及三色標記法時，通常指標記清掃的垃圾回收。 從垃圾回收器的視角來看，三色抽象規定了三種不同類型的對象，并用不同的顏色相稱： * 白色對象（可能死亡）：未被回收器訪問到的對象。在回收開始階段，所有對象均為白色，當回收結束后，白色對象均不可達。 * 灰色對象（波面）：已被回收器訪問到的對象，但回收器需要對其中的一個或多個指針進行掃描，因為他們可能還指向白色對象。 * 黑色對象（確定存活）：已被回收器訪問到的對象，其中所有字段都已被掃描，黑色對象中任何一個指針都不可能直接指向白色對象。 **圖 4.2.1: 垃圾回收器中的波面抽象** 這樣三種不變性所定義的回收過程其實是一個**波面（Wavefront）**不斷前進的過程， 這個波面同時也是黑色對象和白色對象的邊界，灰色對象就是這個波面。 當垃圾回收開始時，只有白色對象。隨著標記過程開始進行時，灰色對象開始出現（著色），這時候波面便開始擴大。當一個對象的所有子節點均完成掃描時，會被著色為黑色。當整個堆遍歷完成時，只剩下黑色和白色對象，這時的黑色對象為可達對象，即存活；而白色對象為不可達對象，即死亡。這個過程可以視為以灰色對象為波面，將黑色對象和白色對象分離，使波面不斷向前推進，直到所有可達的灰色對象都變為黑色對象為止的過程，如圖 4.2.1 所示。 對象的三種顏色可以這樣來判斷： ```` func isWhite(ref interface{}) bool { return !isMarked(ref) } func isGrey(ref interface{}) bool { return worklist.Find(ref) } func isBlack(ref interface{}) bool { return isMarked(ref) && !isGrey(ref) } ``` ## 4.2.3 并發標記清掃 并發標記的思想可以簡要描述如下： ``` func markSome() bool { if worklist.empty() { // 初始化回收過程 scan(Roots) // 賦值器不持有任何白色對象的引用 if worklist.empty() { // 此時灰色對象已經全部處理完畢 sweep() // 標記結束，立即清掃 return false } } // 回收過程尚未完成，后續過程仍需標記 ref = worklist.remove() scan(ref) return true } func scan(ref interface{}) { for fld := range Pointers(ref) { child := *fld if child != nil { shade(child) } } } func shade(ref interface{}) { if !isMarked(ref) { setMarked(ref) worklist.add(ref) } } ``` 在這個過程中，回收器會首先掃描 worklist，而后對根集合進行掃描并重新建立 worklist。 在根集合掃描過程中賦值器現場被掛起時，掃描完成后則不會再存在白色對象。 并發清掃的思想可以簡要描述如下： ``` func New() (interface{}, error) { collectEnough() ref := allocate() if ref == nil { return nil, errors.New("Out of memory") } return ref, nil } func collectEnough() { stopTheWorld() defer startTheWorld() for behind() { // behind() 控制回收工作每次的執行量 if !markSome() { return } } } ```