Go垃圾回收之三色標記算法
轉自公衆號“灰子學技術”，原文鏈接：https://mp.weixin.qq.com/s/SFJoSSbvv3KyYKz4osUnFw
三色標記法介紹：
三色標記法(tricolor mark-and-sweep algorithm)是傳統 Mark-Sweep 的一個改進，它是一個併發的 GC 算法，在Golang中被用作垃圾回收的算法，但是也會有一個缺陷，可能程序中的垃圾產生的速度會大於垃圾收集的速度，這樣會導致程序中的垃圾越來越多無法被收集掉。原理如下所示：
step 1: 創建：白、灰、黑 三個集合。
step 2: 將所有對象放入白色集合中。
step 3: 從根節點開始遍歷所有對象，把遍歷到的對象從白色集合放入灰色集合(備註：這裏放入灰色集合的都是根節點的對象)。
step 4: 遍歷灰色集合，將灰色對象引用的對象(備註：這裏指的是灰色對象引用到的所有對象，包括灰色節點間接引用的那些對象)從白色集合放入灰色集合，然後將分析過的灰色對象放入黑色集合。
step 5: 直到灰色中無任何對象。
step 6: 通過寫屏障(write-barrier)檢測對象有變化，重複以上操作(備註：因爲 mark 和用戶程序是並行的，所以在上一步執行的時候可能會有新的對象分配，寫屏障是爲了解決這個問題引入的)。
step 7: 收集所有白色對象（垃圾）。
例子如下所示：
1. 初始階段，假設當前的對象調用情況如下所示，root ->A->B/A->C/A<->D；root->F; E; G->H;
根據算法，會將所有的對象都放到白色集合當中，對應於step 1和step 2。
2. GC開始掃描，這裏會從根節點開始，遍歷發現只有A和F是根節點，於是將A、F從白色集合移動到灰色集合當中，在白色結合中之後剩下B、C、D、E、G、H這些節點，對應於step 3。
3. GC繼續掃描灰色集合，會將灰色集合中的節點中引用的節點移動到灰色集合當中，本例中A節點引用的節點B、C、D會被移動到灰色集合中，緊接着A發現自己引用的所有子節點都已經在灰色集合了，便會被移動到黑色集合中，同時F節點沒有自節點，也會被移動到黑色集合當中，對應於step 4。
4. GC會循環遍歷灰色集合，直到灰色集合之中沒有節點爲止，在本例中，發現B、C、D都沒有子節點在白色集合中，便將B、C、D都移動到黑色集合中，對應於step 5。
5. 此時只剩下E、G、H在白色集合中，剩下的對象都在黑色集合中，GC便清除白色集合中的對象，也就是進行回收這些對象，對應於step 7。
6. 上面的垃圾回收結束之後，GC會在進行一步操作，也就是將黑色集合變色成白色集合，供下一次垃圾回收使用。
參考文檔
一張圖瞭解三色標記法：http://idiotsky.top/2017/08/16/gc-three-color/
golang裏gc相關的write barrier(寫屏障）是個什麼樣的過程或者概念？：https://www.zhihu.com/question/62000722/answer/193462425
02.2跟雨痕看go源碼- 併發清理與三色標記：https://blog.csdn.net/bairongdong1/article/details/52216360
Go的三色標記GC ：https://segmentfault.com/a/1190000012597428
Golang GC(垃圾回收) - 三色標記算法：https://juejin.im/post/5c62d45ee51d457fa44f4404
Golang’s Real-time GC in Theory and Practice ：https://making.pusher.com/golangs-real-time-gc-in-theory-and-practice/
灰子學技術：
