JVM在進(jìn)行垃圾回收時(shí)候，首先需要確定哪些對(duì)象是需要回收的，哪些對(duì)象是不需要回收的，確認(rèn)一個(gè)對(duì)象是否可以收回有以下的方案：

1.計(jì)數(shù)法

    每個(gè)對(duì)象都有一個(gè)計(jì)數(shù)器，被引用了加一，移除引用減一。計(jì)數(shù)法實(shí)現(xiàn)簡(jiǎn)單，判斷高效，但是無(wú)法解決對(duì)象之間相互循環(huán)引用的問(wèn)題，這個(gè)是此算法的邏輯漏洞，因此它并不被廣泛使用。

2.可達(dá)性分析法（引用鏈法）

    以GCRoots為基礎(chǔ)去掃描整個(gè)引用鏈，從而找到所有的可達(dá)對(duì)象，那剩下的其他對(duì)象就是不可達(dá)的垃圾對(duì)象了，如下所示：

圖片

可達(dá)性分析法是現(xiàn)在被廣泛使用的判斷對(duì)象是否存活的算法。

1.為什么要使用三色標(biāo)記算法

    可達(dá)性分析法的一種實(shí)現(xiàn)方案是從GCRoots節(jié)點(diǎn)開(kāi)始，使用標(biāo)記-清除算法來(lái)實(shí)現(xiàn)。這種實(shí)現(xiàn)方案有兩個(gè)階段，分別是：標(biāo)記階段、清除階段。

    在標(biāo)記階段，從GCRoots節(jié)點(diǎn)開(kāi)始掃描整個(gè)引用鏈，找到所有可達(dá)的對(duì)象，如下圖所示的標(biāo)記可達(dá)對(duì)象：

圖片

    在清除階段中掃描整個(gè)引用鏈的不可達(dá)對(duì)象，然后將不可達(dá)的垃圾對(duì)象清除掉。這種實(shí)現(xiàn)方案有一個(gè)很大的缺點(diǎn)，那就是整個(gè)過(guò)程必須STW。CMS回收器出現(xiàn)之前的所有回收器，都是用這種方式實(shí)現(xiàn)的，因此GC停頓時(shí)間都比較長(zhǎng)。

    為了解決標(biāo)記-清除算法中的問(wèn)題，于是就產(chǎn)生了三色標(biāo)記算法，目前JVM中的CMS與G1垃圾回收器所使用垃圾回收算法即為三色標(biāo)記法。

2.三色標(biāo)記算法的工作原理

    三色標(biāo)記算法是一種用于垃圾回收的標(biāo)記算法，主要用于標(biāo)記-清除類型的垃圾回收器。它通過(guò)將對(duì)象分為三種顏色（白色、灰色、黑色）來(lái)表示對(duì)象的狀態(tài)，并通過(guò)顏色轉(zhuǎn)換來(lái)判斷哪些對(duì)象是可回收的。如下是幾種顏色的含義：

    白色：表示對(duì)象未被標(biāo)記，默認(rèn)情況下所有對(duì)象都是白色的。白色對(duì)象是垃圾回收的目標(biāo)。

    灰色：表示對(duì)象被標(biāo)記過(guò)，但它的引用尚未被檢查。即該對(duì)象是存活的，但它引用的對(duì)象可能仍未被標(biāo)記。

    黑色：表示對(duì)象已經(jīng)被標(biāo)記并且它引用的所有對(duì)象也都已經(jīng)標(biāo)記過(guò)。即該對(duì)象以及它引用的對(duì)象都被認(rèn)為是存活的。

    三色標(biāo)記算法的執(zhí)行步驟如下所示：

（1）首先創(chuàng)建三個(gè)集合（白、灰、黑），初始的時(shí)候將所有對(duì)象放入白色集合中。

圖片

（2）從根節(jié)點(diǎn)開(kāi)始遍歷所有對(duì)象，把可達(dá)的對(duì)象從白色集合放入灰色集合，如下圖所示：

圖片

（3）遍歷灰色集合，將灰色對(duì)象引用的可達(dá)的對(duì)象從白色集合放入灰色集合，之后將此灰色對(duì)象放入黑色集合，如下圖所示：

圖片

（3）重復(fù) 3這個(gè)步驟，直到灰色中無(wú)任何對(duì)象，最后剩余的所有白色對(duì)象即為無(wú)用的對(duì)象，如下圖所示的最終標(biāo)記結(jié)果：

圖片

    三色標(biāo)記算法通過(guò)將對(duì)象分為白色、灰色和黑色三個(gè)階段，利用標(biāo)記和清理機(jī)制來(lái)判斷哪些對(duì)象是垃圾并進(jìn)行回收。

3.三色標(biāo)記算法的問(wèn)題

    以CMS垃圾收集器中使用的是三色標(biāo)記算法，現(xiàn)在以CMS執(zhí)行過(guò)程為例，如下是CMS工作圖：

圖片

    CMS存在并發(fā)標(biāo)記過(guò)程，當(dāng)與用戶線程一起執(zhí)行的情況下標(biāo)記時(shí)，由于用戶線程可能會(huì)隨時(shí)修改對(duì)象的引用狀態(tài)，這就導(dǎo)致三色標(biāo)記出現(xiàn)多標(biāo)和漏標(biāo)的問(wèn)題。

（1）漏標(biāo)的問(wèn)題的產(chǎn)生

圖片

    在t1時(shí)刻，C對(duì)象被標(biāo)記成灰色并且C下存在一個(gè)白色對(duì)象D；在t2時(shí)刻C不在持有D對(duì)象，但是B持有D對(duì)象，此時(shí)B由于是黑色的，那么D就不會(huì)在被標(biāo)記；t3時(shí)刻由于D是白色的，那么垃圾收集就會(huì)將D清理掉。這就產(chǎn)生了漏標(biāo)的問(wèn)題。

（2）多標(biāo)問(wèn)題的產(chǎn)生

圖片

    在t1時(shí)刻A持有灰色對(duì)象C，在t2時(shí)刻A不再持有C對(duì)象，此時(shí)雖然C對(duì)象不可達(dá)，但是C對(duì)象被標(biāo)記成灰色，那么就產(chǎn)生了多標(biāo)問(wèn)題。

4.三色標(biāo)記算法中問(wèn)題的解決方案

漏標(biāo)問(wèn)題要發(fā)生需要滿足如下兩個(gè)充要條件：

（1）有至少一個(gè)黑色對(duì)象在自己被標(biāo)記之后指向了這個(gè)白色對(duì)象，如下圖中的B對(duì)象：

圖片

（2）所有的灰色對(duì)象在自己引用掃描完成之前刪除了對(duì)白色對(duì)象的引用，如下所示的C對(duì)象：

圖片

    只有當(dāng)上面兩個(gè)條件都滿足，三色標(biāo)記算法才會(huì)發(fā)生漏標(biāo)的問(wèn)題。那么如果我們破壞任何一個(gè)條件，這個(gè)白色對(duì)象就不會(huì)被漏標(biāo)。

    CMS和G1垃圾回收器，它們都在并發(fā)標(biāo)記階段之后新增了一個(gè)重新標(biāo)記階段來(lái)校正并發(fā)標(biāo)記階段中未被正確標(biāo)記的對(duì)象，CMS垃圾回收器使用的增量更新方案來(lái)解決漏標(biāo)的問(wèn)題，G1垃圾收集器采用的是原始快照方案來(lái)解決漏標(biāo)的問(wèn)題。

    無(wú)論是增量更新還是原始快照都會(huì)借助寫(xiě)屏障來(lái)協(xié)助標(biāo)記，寫(xiě)屏障可以理解成Spring中的AOP，寫(xiě)屏障可以分為寫(xiě)前屏障和寫(xiě)后屏障。

4.1 CMS解決漏標(biāo)的方案

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

    增量更新使用寫(xiě)后屏障，某個(gè)對(duì)象新增的引用時(shí)，將該對(duì)象記錄下來(lái)，掃描完后將這個(gè)對(duì)象變?yōu)榛疑珜?duì)象重新掃描，在后續(xù)這個(gè)重新掃描的階段需要用戶線程STW，如下圖所示：

圖片

    這種方式的缺點(diǎn)是會(huì)重新掃描新增的這部分對(duì)象，會(huì)浪費(fèi)多一些時(shí)間。但是這段時(shí)間相對(duì)于并發(fā)標(biāo)記整個(gè)鏈路的掃描來(lái)講還是可以接受的。

4.2 G1解決漏標(biāo)的方案

    G1垃圾回收器采用的是原始快照的方案解決漏標(biāo)問(wèn)題，即破壞了“所有的灰色對(duì)象在自己引用掃描完成之前刪除了對(duì)白色對(duì)象的引用”的條件。

    原始快照使用寫(xiě)前屏障，在刪除引用前保存要?jiǎng)h除的引用，在掃描完畢后將這些刪除的引用變?yōu)榛疑珜?duì)象重新掃描，并且GC開(kāi)始后發(fā)生新增引用時(shí)，使用TAMS（Top at Mark Start）指針對(duì)新增引用進(jìn)行記錄。如下圖所示的過(guò)程：

圖片

    E對(duì)象目前引用了F對(duì)象，C對(duì)象已標(biāo)記完成，在下一個(gè)時(shí)刻的時(shí)候，E對(duì)象刪除了對(duì)F對(duì)象的引用，D對(duì)象添加了對(duì)C對(duì)象的引用

圖片

    此時(shí)通過(guò)寫(xiě)前屏障將C對(duì)象置為灰色，F(xiàn)對(duì)象標(biāo)記成灰色，但是F其實(shí)是浮動(dòng)垃圾，等到一下時(shí)刻，從灰色隊(duì)列中拉取對(duì)象重新標(biāo)記，最后的結(jié)果如下所示：

圖片

    原始快照的缺點(diǎn)是會(huì)產(chǎn)生浮動(dòng)垃圾，因?yàn)楫?dāng)取消對(duì)象引用的時(shí)候，有可能是真的取消引用，對(duì)象是要回收掉的。但是通過(guò)這種方式，就會(huì)把本該回收的對(duì)象又復(fù)活了，從而導(dǎo)致出現(xiàn)浮動(dòng)垃圾。總體來(lái)講，原始快照方式是可以接受的，因?yàn)樵谙麓蜧C的時(shí)候垃圾還是會(huì)被回收的。

4.3、三色標(biāo)記中多標(biāo)的問(wèn)題

    在并發(fā)標(biāo)記階段，有可能之前已經(jīng)被標(biāo)記為存活的對(duì)象，其引用被刪除，從而變成了不可達(dá)對(duì)象。

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

總結(jié)：

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

（2）由于標(biāo)記-清除算法效率太低，所以推出了三色標(biāo)記算法，通過(guò)將對(duì)象分成白色、黑色、灰色來(lái)標(biāo)記哪些對(duì)象是存活的，哪么對(duì)象需要回收。

（3）三色標(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)題。 CMS垃圾回收器采用了增量更新方式解決漏標(biāo)問(wèn)題，G1垃圾回收器采用了原始快照方式解決漏標(biāo)問(wèn)題。