Javaer 面試必背系列！超高頻八股之三色標記法
可達性分析可以分成兩個階段
- 根節點枚舉
- 從根節點開始遍歷對象圖
前文提到過，在可達性分析中，第一階段 」根節點枚舉「 是必須 STW 的，不然如果分析過程中用戶進程還在運行，就可能會導致根節點集合的對象引用關係不斷變化，這樣可達性分析結果的準確性顯然也就無法保證了；而第二階段 」從根節點開始遍歷對象圖「，如果不進行 STW 的話，會導致一些問題，由於第二階段時間比較長，長時間的 STW 很影響性能，所以大佬們設計了一些解決方案，從而使得這個第二階段可以不用 STW，大幅減少時間
上篇文章已經介紹過第一階段 「根節點枚舉」，本篇就來分析第二階段 」從根節點開始遍歷對象圖「~
老規矩，背誦版在文末
前言
事實上，GC Roots 相比起整個 Java 堆中全部的對象畢竟還算是極少數，且在各種優化技巧（比如 OopMap）的加持下，它帶來的停頓已經是非常短暫且相對固定的了，也就是說，「根節點枚舉」 階段的停頓時間不會隨著堆容量的增長而增加。
當我們枚舉完了所有的 GC Roots，就得進入第二階段繼續往下遍歷對象圖了，這一步驟同樣需要 STW，並且停頓時間與 Java 堆容量直接成正比例關係：堆越大，存儲的對象越多，對象圖結構越複雜，要標記更多對象而產生的停頓時間自然就更長，這是理所當然的事情
也就是說，「從根節點開始遍歷對象圖」 階段的停頓時間隨著堆容量的增長而增加。
要知道包含「標記」階段（也就是可達性分析）是所有追蹤式垃圾收集演算法的共同特徵，如果這個階段會隨著堆變大而等比例增加停頓時間，其影響就會波及幾乎所有的垃圾收集器。如果能夠減少這部分停頓時間的話，那收益也將會是巨大的
想降低 STW 時間甚至是避免 STW，我們就要先搞清楚為什麼必須在一個能保障一致性的快照上才能進行對象圖的遍歷？
為了能解釋清楚這個問題，大佬們引入了三色標記法（Tri-color Marking）這個工具
需要注意的是，三色標記法只是輔助我們分析的工具，並不是某個垃圾收集器具體使用的演算法！！！！！更不是降低 STW 時間 or 消除 STW 的方法，具體解決方法下面還會介紹
在這裡，三色標記法可以幫助我們搞清楚在可達性分析的第二階段（也就是遍歷對象圖），如果用戶執行緒和垃圾收集執行緒同時進行，會出現什麼問題
輔助分析的工具：三色標記法
所謂三色標記法，就是把遍歷對象圖過程中遇到的對象，按照 「是否訪問過」 這個條件標記成以下三種顏色：
-
白色：表示對象尚未被垃圾收集器訪問過。顯然在可達性分析剛剛開始的階段，所有的對象都是白色的，若在分析結束的階段，仍然是白色的對象，即代表不可達（可達性分析到不了的對象，就是死亡對象，需要被回收）
-
黑色：表示對象已經被垃圾收集器訪問過，且這個對象的所有引用都已經掃描過。黑色的對象代表已經掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對象不可能直接（不經過灰色對象）指向某個白色對象。
-
灰色：表示對象已經被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過
灰色可能不好理解，這裡舉個例子：A(GC roots) → B → C，如果 B 已經被掃描過，但是 B 的引用 C 還沒有被掃描過，那麼 B 就是灰色的，C 由於還沒有被掃描，所以是白色的
所以對象圖遍歷的過程，其實就是由灰色從黑向白推進的過程，灰色是黑和白的分界線。
下面我們就用三色標記法來分析下，如果在對象圖遍歷這個階段用戶執行緒與收集器並發工作會出現什麼問題
問題 1：浮動垃圾
所謂浮動垃圾，就是由於垃圾收集和用戶執行緒是並行的，這個對象實際已經死亡了，已經沒有其他人引用它了，但是被垃圾收集器錯誤地標記成了存活對象
舉個例子，a 引用了 b，此時 b 被掃描為可達，但是用戶執行緒隨後又執行了 a.b = null，這個時候其實 b 已經是死亡的垃圾對象了，但是由於黑色對象不會被重新掃描，所以在垃圾收集里 b 依然作為存活對象被標記成黑色，因此就成了浮動垃圾。如下圖所示：
浮動垃圾當然不是一件好事，但其實是可以容忍的，因為這只不過產生了一點逃過本次收集的浮動垃圾而已，反正還會有下一次垃圾收集，到時候就會被標記為垃圾被清理掉了
問題 2：對象消失
對象消失和浮動垃圾恰恰相反，對象消失是把原本存活的對象錯誤標記為已消亡，這就是非常致命的後果了，程式肯定會因此發生錯誤，下面表演示了這樣的致命錯誤具體是如何產生的
如上圖所示，b -> c 的引用被切斷，但同時用戶執行緒建立了一個新的從 a -> c 的引用，由於已經遍歷到了 b，不可能再回去遍歷 a（黑色對象不會被重新掃描），再遍歷 c，所以這個 c 實際是存活的對象，但由於沒有被垃圾收集器掃描到，被錯誤地標記成了白色。
總結下對象消失問題的兩個條件：
- 插入了一條或多條從黑色對象到白色對象的新引用
- 刪除了全部從灰色對象到該白色對象的直接或間接引用
Wilson 於 1994 年在理論上證明了，當且僅當以上兩個條件同時滿足時，才會產生 「對象消失」 的問題，即原本應該是黑色的對象被誤標為白色
遍歷對象圖不需要 STW 的解決方案
如上所述，如果遍歷對象圖的過程不 STW 的話，第一個浮動垃圾的問題很好處理，但是第二個對象消失問題就很棘手了。
但是呢，遍歷對象圖的過程又實在太長，設計 JVM 的大佬們不得不想出一些辦法來解決對象消失問題，使得在遍歷對象圖的過程中不用進行 STW（也就是用戶執行緒和對象執行緒可以同時工作），從而提升可達性分析的效率
上面總結了對象消失問題的兩個條件，所以說，如果我們想要解決並發掃描時的對象消失問題，只需破壞這兩個條件的任意一個即可。由此分別產生了兩種解決方案：
- 增量更新（Incremental Update）：增量更新破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關係時（就是上圖中的 a -> c 引用關係），就將這個新插入的引用記錄下來，等並發掃描結束之後，再將這些記錄過的引用關係中的黑色對象（a）為根，重新掃描一次。這可以簡化理解為，黑色對象一旦新插入了指向白色對象的引用之後，它就變回灰色對象了。
- 原始快照（Snapshot At The Beginning，SATB）：原始快照要破壞的是第二個條件，當灰色對象要刪除指向白色對象的引用關係時（上圖中的 b -> c 引用關係），就將這個要刪除的引用記錄下來，在並發掃描結束之後，再將這些記錄過的引用關係中的灰色對象（b）為根，重新掃描一次。這也可以簡化理解為，無論引用關係刪除與否，都會按照剛剛開始掃描那一刻的對象圖快照來進行搜索。
在 HotSpot 虛擬機中，增量更新和原始快照這兩種解決方案都有實際應用，CMS 是基於增量更新來做並發標記的，G1、Shenandoah 則是用原始快照來實現
最後放上這道題的背誦版：
🥸 面試官：講一講三色標記法？
😎 小牛肉：在可達性分析中，第一階段 」根節點枚舉「 是必須 STW 的，不然如果分析過程中用戶進程還在運行，就可能會導致根節點集合的對象引用關係不斷變化，這樣可達性分析結果的準確性顯然也就無法保證了。不過 GC Roots 相比起整個 Java 堆中全部的對象算是極少數，且在各種優化技巧（比如 OopMap）的加持下，它帶來的停頓已經是非常短暫且相對固定的了，也就是說，「根節點枚舉」 階段的停頓時間不會隨著堆容量的增長而增加。
當我們枚舉完了所有的 GC Roots，就得進入第二階段繼續往下遍歷對象圖了，這一步驟同樣需要 STW，並且停頓時間與 Java 堆容量直接成正比例關係，三色標記法就是幫助我們搞清楚在這個階段如果用戶執行緒和垃圾收集執行緒同時進行，會出現什麼問題，的這麼一個工具方法
所謂三色標記法，就是把遍歷對象圖過程中遇到的對象，按照 「是否訪問過」 這個條件標記成以下三種顏色：
- 白色：表示對象尚未被垃圾收集器訪問過。顯然在可達性分析剛剛開始的階段，所有的對象都是白色的，若在分析結束的階段，仍然是白色的對象，即代表不可達（可達性分析到不了的對象，就是死亡對象，需要被回收）
- 黑色：表示對象已經被垃圾收集器訪問過，且這個對象的所有引用都已經掃描過。黑色的對象代表已經掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對象不可能直接（不經過灰色對象）指向某個白色對象。
- 灰色：表示對象已經被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過
所以對象圖遍歷的過程，其實就是由灰色從黑向白推進的過程，灰色是黑和白的分界線。
在 「對象圖遍歷」 這個階段用戶執行緒與收集器並發工作會出現兩個問題：
1）浮動垃圾：所謂浮動垃圾，就是由於垃圾收集和用戶執行緒是並行的，這個對象實際已經死亡了，已經沒有其他人引用它了，但是被垃圾收集器錯誤地標記成了存活對象。
舉個例子，a 引用了 b，此時 b 被掃描為可達，但是用戶執行緒隨後又執行了 a.b = null，這個時候其實 b 已經是死亡的垃圾對象了，但是由於黑色對象不會被重新掃描，所以在垃圾收集里 b 依然作為存活對象被標記成黑色，因此就成了浮動垃圾
浮動垃圾不是一件好事，但其實是可以容忍的，因為這只不過產生了一點逃過本次收集的浮動垃圾而已，反正還會有下一次垃圾收集，到時候就會被標記為垃圾被清理掉了
2）對象消失：對象消失和浮動垃圾恰恰相反，對象消失是把原本存活的對象錯誤標記為已消亡（原本應該是黑色的對象被誤標為白色），產生對象消失問題需要滿足兩個條件：
- 插入了一條或多條從黑色對象到白色對象的新引用
- 刪除了全部從灰色對象到該白色對象的直接或間接引用
對象消失是一個很致命的問題，程式肯定會因此發生錯誤，所以 「對象圖遍歷」 這個階段最好是進行 STW 的，但是這個階段的時間又很長，所以我們需要想出一些辦法來解決對象消失問題，使得在遍歷對象圖的過程中不用進行 STW（也就是用戶執行緒和對象執行緒可以同時工作），從而提升可達性分析的效率
上面總結了對象消失問題的兩個條件，所以說，如果我們想要解決並發掃描時的對象消失問題，只需破壞這兩個條件的任意一個即可。由此分別產生了兩種解決方案：
- 增量更新（Incremental Update）：增量更新破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關係時（就是上圖中的 a -> c 引用關係），就將這個新插入的引用記錄下來，等並發掃描結束之後，再將這些記錄過的引用關係中的黑色對象（a）為根，重新掃描一次。這可以簡化理解為，黑色對象一旦新插入了指向白色對象的引用之後，它就變回灰色對象了。
- 原始快照（Snapshot At The Beginning，SATB）：原始快照要破壞的是第二個條件，當灰色對象要刪除指向白色對象的引用關係時（上圖中的 b -> c 引用關係），就將這個要刪除的引用記錄下來，在並發掃描結束之後，再將這些記錄過的引用關係中的灰色對象（b）為根，重新掃描一次。這也可以簡化理解為，無論引用關係刪除與否，都會按照剛剛開始掃描那一刻的對象圖快照來進行搜索。
在 HotSpot 虛擬機中，增量更新和原始快照這兩種解決方案都有實際應用，CMS 是基於增量更新來做並發標記的，G1、Shenandoah 則是用原始快照來實現
小夥伴們大家好呀，我是小牛肉，公眾號【飛天小牛肉】定期推送大廠面試題，提供背誦版 + 詳細版，知其然而知其所以然，讓八股文變得有價值！）
