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

文章思維導(dǎo)圖

根可達(dá)算法

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

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

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

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

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

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

圖片引用自維基百科

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

三色標(biāo)記算法

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

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

圖片引用自維基百科

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

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

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

多標(biāo)與漏標(biāo)問(wèn)題

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

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

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

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

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

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

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

那么我們的垃圾回收器是怎么解決這個(gè)問(wèn)題的呢？

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

漏標(biāo)解決方案

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

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

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

CMS 解決方案

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

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

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

G1 解決方案

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

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

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

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

總結(jié)

看完了整篇文章，我們?cè)噲D來(lái)回答一些問(wèn)題。

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

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

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

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

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

參考資料

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