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

1.計數法

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

2.可達性分析法（引用鏈法）

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

圖片

可達性分析法是現在被廣泛使用的判斷對象是否存活的算法。

1.為什么要使用三色標記算法

    可達性分析法的一種實現方案是從GCRoots節點開始，使用標記-清除算法來實現。這種實現方案有兩個階段，分別是：標記階段、清除階段。

    在標記階段，從GCRoots節點開始掃描整個引用鏈，找到所有可達的對象，如下圖所示的標記可達對象：

圖片

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

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

2.三色標記算法的工作原理

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

    白色：表示對象未被標記，默認情況下所有對象都是白色的。白色對象是垃圾回收的目標。

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

    黑色：表示對象已經被標記并且它引用的所有對象也都已經標記過。即該對象以及它引用的對象都被認為是存活的。

    三色標記算法的執行步驟如下所示：

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

圖片

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

圖片

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

圖片

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

圖片

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

3.三色標記算法的問題

    以CMS垃圾收集器中使用的是三色標記算法，現在以CMS執行過程為例，如下是CMS工作圖：

圖片

    CMS存在并發標記過程，當與用戶線程一起執行的情況下標記時，由于用戶線程可能會隨時修改對象的引用狀態，這就導致三色標記出現多標和漏標的問題。

（1）漏標的問題的產生

圖片

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

（2）多標問題的產生

圖片

    在t1時刻A持有灰色對象C，在t2時刻A不再持有C對象，此時雖然C對象不可達，但是C對象被標記成灰色，那么就產生了多標問題。

4.三色標記算法中問題的解決方案

漏標問題要發生需要滿足如下兩個充要條件：

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

圖片

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

圖片

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

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

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

4.1 CMS解決漏標的方案

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

    增量更新使用寫后屏障，某個對象新增的引用時，將該對象記錄下來，掃描完后將這個對象變為灰色對象重新掃描，在后續這個重新掃描的階段需要用戶線程STW，如下圖所示：

圖片

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

4.2 G1解決漏標的方案

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

    原始快照使用寫前屏障，在刪除引用前保存要刪除的引用，在掃描完畢后將這些刪除的引用變為灰色對象重新掃描，并且GC開始后發生新增引用時，使用TAMS（Top at Mark Start）指針對新增引用進行記錄。如下圖所示的過程：

圖片

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

圖片

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

圖片

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

4.3、三色標記中多標的問題

    在并發標記階段，有可能之前已經被標記為存活的對象，其引用被刪除，從而變成了不可達對象。

    多標問題會導致內存產生浮動垃圾，但是其可以在下次GC的時候被回收，因此問題還不算很嚴重。

總結：

（1）三色標記算法是根可達算法的一種實現方案，其目的是為了找出所有可達對象。

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

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