技術文章 » Javaer 面試必背系列！超高頻八股之三色標記法

Javaer 面試必背系列！超高頻八股之三色標記法

2022-06-15 12:01:39

可達性分析可以分成兩個階段

  1. 根節點列舉
  2. 從根節點開始遍歷物件圖

前文提到過，在可達性分析中，第一階段 」根節點列舉「 是必須 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 實際是存活的物件，但由於沒有被垃圾收集器掃描到，被錯誤地標記成了白色。

總結下物件消失問題的兩個條件：

  1. 插入了一條或多條從黑色物件到白色物件的新參照
  2. 刪除了全部從灰色物件到該白色物件的直接或間接參照

Wilson 於 1994 年在理論上證明了，當且僅當以上兩個條件同時滿足時，才會產生 「物件消失」 的問題，即原本應該是黑色的物件被誤標為白色

遍歷物件圖不需要 STW 的解決方案

如上所述，如果遍歷物件圖的過程不 STW 的話，第一個浮動垃圾的問題很好處理，但是第二個物件消失問題就很棘手了。

但是呢，遍歷物件圖的過程又實在太長，設計 JVM 的大佬們不得不想出一些辦法來解決物件消失問題，使得在遍歷物件圖的過程中不用進行 STW（也就是使用者執行緒和物件執行緒可以同時工作），從而提升可達性分析的效率

上面總結了物件消失問題的兩個條件，所以說，如果我們想要解決並行掃描時的物件消失問題，只需破壞這兩個條件的任意一個即可。由此分別產生了兩種解決方案：

  1. 增量更新（Incremental Update）：增量更新破壞的是第一個條件，當黑色物件插入新的指向白色物件的參照關係時（就是上圖中的 a -> c 參照關係），就將這個新插入的參照記錄下來，等並行掃描結束之後，再將這些記錄過的參照關係中的黑色物件（a）為根，重新掃描一次。這可以簡化理解為，黑色物件一旦新插入了指向白色物件的參照之後，它就變回灰色物件了。
  2. 原始快照（Snapshot At The Beginning，SATB）：原始快照要破壞的是第二個條件，當灰色物件要刪除指向白色物件的參照關係時（上圖中的 b -> c 參照關係），就將這個要刪除的參照記錄下來，在並行掃描結束之後，再將這些記錄過的參照關係中的灰色物件（b）為根，重新掃描一次。這也可以簡化理解為，無論參照關係刪除與否，都會按照剛剛開始掃描那一刻的物件圖快照來進行搜尋。

在 HotSpot 虛擬機器器中，增量更新和原始快照這兩種解決方案都有實際應用，CMS 是基於增量更新來做並行標記的，G1、Shenandoah 則是用原始快照來實現

最後放上這道題的背誦版：