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

1.計數(shù)法

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

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

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

圖片

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

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

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

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

圖片

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

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

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

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

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

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

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

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

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

圖片

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

圖片

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

圖片

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

圖片

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

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

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

圖片

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

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

圖片

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

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

圖片

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

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

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

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

圖片

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

圖片

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

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

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

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

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

    增量更新使用寫后屏障，某個對象新增的引用時，將該對象記錄下來，掃描完后將這個對象變?yōu)榛疑珜ο笾匦聮呙?，在后續(xù)這個重新掃描的階段需要用戶線程STW，如下圖所示：

圖片

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

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

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

    原始快照使用寫前屏障，在刪除引用前保存要刪除的引用，在掃描完畢后將這些刪除的引用變?yōu)榛疑珜ο笾匦聮呙?，并且GC開始后發(fā)生新增引用時，使用TAMS（Top at Mark Start）指針對新增引用進(jìn)行記錄。如下圖所示的過程：

圖片

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

圖片

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

圖片

    原始快照的缺點是會產(chǎn)生浮動垃圾，因為當(dāng)取消對象引用的時候，有可能是真的取消引用，對象是要回收掉的。但是通過這種方式，就會把本該回收的對象又復(fù)活了，從而導(dǎo)致出現(xiàn)浮動垃圾。總體來講，原始快照方式是可以接受的，因為在下次GC的時候垃圾還是會被回收的。

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

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

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

總結(jié)：

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

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

（3）三色標(biāo)記算法會產(chǎn)生多標(biāo)和漏標(biāo)問題，其中漏標(biāo)問題最嚴(yán)重。漏標(biāo)問題會導(dǎo)致本該存活的對象被回收，從而導(dǎo)致嚴(yán)重的程序問題。 CMS垃圾回收器采用了增量更新方式解決漏標(biāo)問題，G1垃圾回收器采用了原始快照方式解決漏標(biāo)問題。