最近和一個朋友聊天，他問了我 JVM 的三色標記算法。我腦袋一愣發(fā)現(xiàn)竟然完全不知道！于是我?guī)е蓡柸ゾW(wǎng)上看了幾天的資料，終于搞清楚啥事三色標記算法，它是用來干嘛的，以及它和 CMS 回收器和 G1 回收器的關系了。今天，就讓樹哥帶著大家一起盤一盤它！

文章思維導圖

根可達算法

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

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

現(xiàn)在被廣泛使用的是第二種算法，即根可達算法。

那怎么去實現(xiàn)根可達算法呢？

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

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

圖片引用自維基百科

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

三色標記算法

為了解決上面「標記 - 清除」算法的問題，于是就出現(xiàn)了「三色標記算法」！

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

圖片引用自維基百科

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

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

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

多標與漏標問題

多標問題指的是原本應該回收的對象，被多余地標記為黑色存活對象，從而導致該垃圾對象沒有被回收。 多標問題會出現(xiàn)，是因為在并發(fā)標記階段，有可能之前已經(jīng)被標記為存活的對象，其引用被刪除，從而變成了不可達對象。例如下圖中，假設我們現(xiàn)在遍歷到了節(jié)點 E，此時應用執(zhí)行了 objD.fieldE = null;。那么此刻之后，對象 E、F、G 應該是被回收的。但因為節(jié)點 E 已經(jīng)是灰色的，那么 E、F、G 節(jié)點都會被標記為存活的黑色狀態(tài)，并不會被回收。

圖片來自網(wǎng)絡

多標問題會導致內(nèi)存產(chǎn)生浮動垃圾，但好在其可以再下次 GC 的時候被回收，因此問題還不算很嚴重。

漏標問題指的是原本應該被標記為存活的對象，被遺漏標記為黑色，從而導致該垃圾對象被錯誤回收。 例如下圖中，假設我們現(xiàn)在遍歷到了節(jié)點 E，此時應用執(zhí)行如下代碼。這時候因為 E 對象沒有引用了 G 對象，因此掃描 E 對象的時候并不會將 G 對象標記為黑色存活狀態(tài)。但由于用戶線程的 D 對象引用了 G 對象，這時候 G 對象應該是存活的，應該標記為黑色。但由于 D 對象已經(jīng)被掃描過了，不會再次掃描，因此 G 對象就被漏標了。

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

圖片來自網(wǎng)絡

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

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

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

漏標解決方案

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

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

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

CMS 解決方案

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

既然有黑色對象在自己標記后，又重新指向了白色對象。那么我就把這個黑色對象的引用記錄下來，在后續(xù)「重新標記」階段再以這個黑色對象為跟，對其引用進行重新掃描。通過這種方式，被黑色對象引用的白色對象就會變成灰色，從而變?yōu)榇婊顮顟B(tài)。

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

G1 解決方案

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

既然灰色對象在掃描完成后刪除了對白色對象的引用，那么我是否能在灰色對象取消引用之前，先將灰色對象引用的白色對象記錄下來。隨后在「重新標記」階段再以白色對象為根，對它的引用進行掃描，從而避免了漏標的問題。通過這種方式，原本漏標的對象就會被重新掃描變成灰色，從而變?yōu)榇婊顮顟B(tài)。

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

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

總結(jié)

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

三色標記算法是什么？ 三色標記算法是根可達算法的一種實現(xiàn)方案，其目的是為了找出所有可達對象。

為什么要有三色標記算法？ 因為傳統(tǒng)的「標記 - 清除」算法效率太低，于是采用三色標記算法通過將對象分成白色、黑色、灰色，以及將整個過程拆分成「初始標記、并發(fā)標記、重新標記、并發(fā)清除」4 個過程，從而降低 GC 停頓時間。

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

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

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

參考資料

• 非常好！權(quán)威資料！VIP！！Tracing garbage collection - Wikipedia
• VIP！VIP！講清楚了！三色標記的漏標問題及兩種解決方案_小幻_159 的博客 - CSDN 博客_三色標記漏標
• 三色標記法：多標與漏標 - 愛代碼愛編程
• 三色標記！！！12. 垃圾收集底層算法 -- 三色標記詳解 - 騰訊云開發(fā)者社區(qū) - 騰訊云
• 三色標記！！！GC 中的 三色標記法_騷人貴的博客 - CSDN 博客_gc 三色標記
• 三色標記法：多標與漏標_朱四龍的博客 - CSDN 博客_三色標記漏標