一文帶你弄懂 JVM 三色標記演算法！

2022 年 8 月 15 日
筆記
JVM

大家好，我是樹哥。

最近和一個朋友聊天，他問了我 JVM 的三色標記演算法。我腦袋一愣發現竟然完全不知道！於是我帶著疑問去網上看了幾天的資料，終於搞清楚啥事三色標記演算法，它是用來幹嘛的，以及它和 CMS 回收器和 G1 回收器的關係了。今天，就讓樹哥帶著大家一起盤一盤它！

根可達演算法

我們要進行垃圾回收，就需要弄明白哪些對象是需要回收的，哪些對象是不需要回收的。針對這個問題，其實業界已經有幾種常見的解決方法了。

第一種是計數法，就是每個對象都有一個計數器，被引用了加一，移除引用減一。但這種方法比較麻煩，而且也會有循環依賴的問題，因此並不被廣泛使用。第二種是根可達演算法，即以 GCRoots 為基礎去掃描整個引用鏈，從而找到所有的可達對象，那剩下的其他對象就是不可達的垃圾對象了。

現在被廣泛使用的是第二種演算法，即根可達演算法。

那怎麼去實現根可達演算法呢？

最簡單的一種實現方案是：從　GCRoots 節點開始，使用「標記-清除」演算法去實現。

這種實現方案分為兩個階段，分別是：標記階段、清除階段。在標記階段，它從 GCRoots 節點開始掃描整個引用鏈，找到所有可達的對象。在清除階段，掃描整個引用鏈的不可達對象，然後將垃圾對象清除掉。整個演算法實現過程如下圖所示。

但這種方式有一個很大的缺點：整個過程必須「Stop the World」。這就導致整個應用程式必須停止，不能做任何改變，這是非常不友好的。 CMS 回收器出現之前的所有回收器，都是用這種方式實現的，因此 GC 停頓時間都比轎長。

三色標記演算法

為了解決上面「標記-清除」演算法的問題，於是就出現了「三色標記演算法」！

三色標記演算法指的是將所有對象分為白色、黑色和灰色三種類型。黑色表示從 GCRoots 開始，已掃描過它全部引用的對象，灰色指的是掃描過對象本身，還沒完全掃描過它全部引用的對象，白色指的是還沒掃描過的對象。

但僅僅將對象劃分成三個顏色還不夠，真正關鍵的是：實現根可達演算法的時候，將整個過程拆分成了初始標記、並發標記、重新標記、並發清除四個階段。

初始標記階段，指的是標記 GCRoots 直接引用的節點，將它們標記為灰色，這個階段需要「Stop the World」。
並發標記階段，指的是從灰色節點開始，去掃描整個引用鏈，然後將它們標記為黑色，這個階段不需要「Stop the World」。
重新標記階段，指的是去校正並發標記階段的錯誤，這個階段需要「Stop the World」。
並發清除，指的是將已經確定為垃圾的對象清除掉，這個階段不需要「Stop the World」。

對比一下「四階段拆分」和「一段式」的實現方式，我們可以看出：通過將最耗時的引用鏈掃描剝離出來作為並發標記階段，將其與用戶執行緒並發執行，從而極大地降低了 GC 停頓時間。 但 GC 執行緒與用戶執行緒並發執行，會帶來新的問題：對象引用關係可能會發生變化，有可能發生多標和漏標問題。

多標與漏標問題

多標問題指的是原本應該回收的對象，被多餘地標記為黑色存活對象，從而導致該垃圾對象沒有被回收。 多標問題會出現，是因為在並發標記階段，有可能之前已經被標記為存活的對象，其引用被刪除，從而變成了不可達對象。例如下圖中，假設我們現在遍歷到了節點 E，此時應用執行了 objD.fieldE = null;。那麼此刻之後，對象 E、F、G 應該是被回收的。但因為節點 E 已經是灰色的，那麼 E、F、G 節點都會被標記為存活的黑色狀態，並不會被回收。

多標問題會導致記憶體產生浮動垃圾，但好在其可以再下次 GC 的時候被回收，因此問題還不算很嚴重。

漏標問題指的是原本應該被標記為存活的對象，被遺漏標記為黑色，從而導致該垃圾對象被錯誤回收。 例如下圖中，假設我們現在遍歷到了節點 E，此時應用執行如下程式碼。這時候因為 E 對象沒有引用了 G 對象，因此掃描 E 對象的時候並不會將 G 對象標記為黑色存活狀態。但由於用戶執行緒的 D 對象引用了 G 對象，這時候 G 對象應該是存活的，應該標記為黑色。但由於 D 對象已經被掃描過了，不會再次掃描，因此 G 對象就被漏標了。

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 斷開引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

漏標問題就非常嚴重了，其會導致存活對象被回收，會嚴重影響程式功能。

那麼我們的垃圾回收器是怎麼解決這個問題的呢？

答案是：增加一個「重新標記」階段。無論是在 CMS 回收器還是 G1 回收器，它們都在並發標記階段之後，新增了一個「重新標記」階段來校正「並發標記」階段出現的問題。只是對於 CMS 回收器和 G1 回收器來說，它們解決的原理不同罷了。

漏標解決方案

正如前面所說，三色標記演算法會造成漏標和多標問題。但多標問題相對不是那麼嚴重，而漏標問題才是最嚴重的。我們經過分析可以知道，漏標問題要發生需要滿足如下兩個充要條件：

有至少一個黑色對象在自己被標記之後指向了這個白色對象
所有的灰色對象在自己引用掃描完成之前刪除了對白色對象的引用

只有當上面兩個條件都滿足，三色標記演算法才會發生漏標的問題。換言之，如果我們破壞任何一個條件，這個白色對象就不會被漏標。這其實就產生了兩種方式，分別是：增量更新、原始快照。CMS 回收器使用的增量更新方案，G1 採用的是原始快照方案。

CMS 解決方案

CMS 回收器採用的是增量更新方案，即破壞第一個條件：「有至少一個黑色對象在自己被標記之後指向了這個白色對象」。

既然有黑色對象在自己標記後，又重新指向了白色對象。那麼我就把這個黑色對象的引用記錄下來，在後續「重新標記」階段再以這個黑色對象為跟，對其引用進行重新掃描。通過這種方式，被黑色對象引用的白色對象就會變成灰色，從而變為存活狀態。

這種方式有個缺點，就是會重新掃描新增的這部分黑色對象，會浪費多一些時間。但是這段時間相對於並發標記整個鏈路的掃描，還是小巫見大巫，畢竟真正發生引用變化的黑色對象是比較少的。

G1 解決方案

G1 回收器採用的是原始快照的方案，即破壞第二個條件：「所有的灰色對象在自己引用掃描完成之前刪除了對白色對象的引用」。

既然灰色對象在掃描完成後刪除了對白色對象的引用，那麼我是否能在灰色對象取消引用之前，先將灰色對象引用的白色對象記錄下來。隨後在「重新標記」階段再以白色對象為根，對它的引用進行掃描，從而避免了漏標的問題。通過這種方式，原本漏標的對象就會被重新掃描變成灰色，從而變為存活狀態。

這種方式有個缺點，就是會產生浮動垃圾。 因為當用戶執行緒取消引用的時候，有可能是真的取消引用，對應的對象是真的要回收掉的。這時候我們通過這種方式，就會把本該回收的對象又復活了，從而導致出現浮動垃圾。但相對於本該存活的對象被回收，這個程式碼還是可以接受的，畢竟在下次 GC 的時候就可以回收了。

對於 CMS 和 G1 這兩種處理方案哪種更好，很多資料說的是 G1 這種解決方案更好。 原因是其覺得 G1 這種方式產生了一些浮動垃圾，但節省了一些時間。但我對比了一下發現：CMS 和 G1 都需要重新對某些元素進行引用鏈掃描。從這點看來，好像差別不大。有弄懂的朋友可以評論區留言討論討論。

總結

看完了整篇文章，我們試圖來回答一些問題。

三色標記演算法是什麼？ 三色標記演算法是根可達演算法的一種實現方案，其目的是為了找出所有可達對象。

為什麼要有三色標記演算法？ 因為傳統的「標記-清除」演算法效率太低，於是採用三色標記演算法通過將對象分成白色、黑色、灰色，以及將整個過程拆分成「初始標記、並發標記、重新標記、並發清除」4 個過程，從而降低 GC 停頓時間。

三色標記演算法有什麼缺陷？ 三色標記演算法會產生多標和漏標問題，其中漏標問題最嚴重。漏標問題會導致本該存活的對象被回收，從而導致嚴重的程式問題。

漏標有什麼解決方案？ 漏標有兩種解決方案，分別是：增量更新和原始快照方式。CMS 回收器採用了增量更新方式，G1 回收器採用了原始快照方式。

漏標哪種解決方案最好？ 江湖傳聞 G1 回收器的原始快照方式效率高，但沒有確切的理論證明，且聽且珍惜。

參考資料

Tags: JVM