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

文章思維導(dǎo)圖

根可達(dá)算法

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

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

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

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

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

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

圖片引用自維基百科

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

三色標(biāo)記算法

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

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

圖片引用自維基百科

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

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

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

多標(biāo)與漏標(biāo)問題

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

圖片來自網(wǎng)絡(luò)

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

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

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

圖片來自網(wǎng)絡(luò)

漏標(biāo)問題就非常嚴(yán)重了，其會導(dǎo)致存活對象被回收，會嚴(yán)重影響程序功能。

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

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

漏標(biāo)解決方案

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

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

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

CMS 解決方案

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

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

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

G1 解決方案

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

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

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

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

總結(jié)

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

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

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

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

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

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

參考資料

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