我們都知道， 當JVM判斷對象不再存活的時候，便會在下一次GC時候將該對象回收掉，為堆騰出空間，而JVM判斷對象存活的算法大家比較熟知的有兩種，分別是引用計數法和可達性分析算法

• 引用計數法：給對象中添加一個引用計數器，每當有一個地方引用它，計數器就加 1；當引用失效，計數器就減 1；任何時候計數器為 0 的對象就是不可能再被使用的。這個方法實現簡單，效率高，但是目前主流的虛擬機中并沒有選擇這個算法來管理內存，其最主要的原因是它很難解決對象之間相互循環引用的問題。
• 可達性分析算法：這個算法的基本思想就是通過一系列的稱為 “GC Roots” 的對象作為起點，從這些節點開始向下搜索，節點所走過的路徑稱為引用鏈，當一個對象到 GC Roots 沒有任何引用鏈相連的話，則證明此對象是不可用的。

但是這兩種算法其實并不完美，主要存在以下問題：

1、循環引用問題，如果兩個對象互相引用，就形成了一個環形結構，如果采用引用計數法的話，那么這兩個對象將用于無法被回收。

2、誤標記的問題，在多線程環境下，如果一個線程正在遍歷對象圖，而另一個線程在同時修改對象圖，就會導致遍歷結果不準確。

3、STW時間長，可達性分析的整個過程都需要STW，以避免對象的狀態發生改變，這就導致GC停頓時長很長，大大影響應用的整體性能。

為了解決上面這些問題，就引入了三色標記算法

什么是三色標記法

三色標記法將對象分為三種狀態：白色、灰色和黑色。

白色：該對象沒有被標記過。

灰色：該對象已經被標記過了，但該對象的引用對象還沒標記完。

黑色：該對象已經被標記過了，并且他的全部引用對象也都標記完了。

三色標記法的標記過程可以分為三個階段：初始標記（Initial Marking）、并發標記（Concurrent Marking）和重新標記（Remark）。

這三個階段看上去是不是很熟悉，這不就是CMS的四個階段中的前三個么？沒錯，就是他們。

• 初始標記：遍歷所有的根對象，將根對象和直接引用的對象標記為灰色。在這個階段中，垃圾回收器只會掃描被直接或者間接引用的對象，而不會掃描整個堆。因此，初始標記階段的時間比較短。（Stop The World）
• 并發標記：在這個過程中，垃圾回收器會從灰色對象開始遍歷整個對象圖，將被引用的對象標記為灰色，并將已經遍歷過的對象標記為黑色。并發標記過程中，應用程序線程可能會修改對象圖，因此垃圾回收器需要使用寫屏障（Write Barrier）技術來保證并發標記的正確性。（不需要STW）
• 重新標記：重新標記的主要作用是標記在并發標記階段中被修改的對象以及未被遍歷到的對象。這個過程中，垃圾回收器會從灰色對象重新開始遍歷對象圖，將被引用的對象標記為灰色，并將已經遍歷過的對象標記為黑色。（Stop The World）

在重新標記階段結束之后，垃圾回收器會執行清除操作，將未被標記為可達對象的對象進行回收，從而釋放內存空間。這個過程中，垃圾回收器會將所有未被標記的對象標記為白色（White）。

以上三個標記階段中，初始標記和重新標記是需要STW的，而并發標記是不需要STW的。其中最耗時的其實就是并發標記的這個階段，因為這個階段需要遍歷整個對象樹，而三色標記把這個階段做到了和應用線程并發執行，大大降低了GC的停頓時長。

寫屏障

并發標記過程中，應用程序線程可能會修改對象圖，因此垃圾回收器需要使用寫屏障（Write Barrier）技術來保證并發標記的正確性。

寫屏障是一種在對象引用被修改時，將其新的引用信息記錄在特殊數據結構中的機制。在三色標記法中，寫屏障技術被用于記錄對象的標記狀態，并且只對未被標記過的對象進行標記。

當應用程序線程修改了一個對象的引用時，寫屏障會記錄該對象的新標記狀態。如果該對象未被標記過，那么它會被標記為灰色，以便在垃圾回收器的下一次遍歷中進行標記。如果該對象已經被標記為可達對象，那么寫屏障不會對該對象進行任何操作。

通過使用寫屏障技術，三色標記法能夠確保垃圾回收器能夠準確地標記所有可達對象，并且避免了多次標記同一對象的情況。同時，寫屏障技術也會帶來一定的性能開銷，因為每次引用被修改時都需要記錄新的標記狀態。為了減少性能開銷，垃圾回收器通常會使用基于插入式寫屏障的優化技術，來降低寫屏障的開銷。

多標的問題

所謂多標，其實就是這個對象原本應該被回收掉的白色對象，但是被錯誤的標記成了黑色的存活對象。從而導致這個對象沒有被GC回收掉。

這個一般發生在并發標記過程中，該對象還是有引用的，但是在過程中，應用程序執行過程中把他的引用關系刪除了，導致他變成了一個垃圾對象。

多標的話，會產生浮動垃圾，這個問題一般都不太需要解決，因為這種垃圾一般都不會太多，另外在下一次GC的時候也都能被回收掉。

多標的問題

所謂漏標，和多標剛好相反，就是說一個對象本來應該是黑色存活對象，但是沒有被正確的標記上，導致被錯誤的垃圾回收掉了。

這種情況一旦發生是很危險的，一個正常使用的對象被垃圾回收掉了，這對系統來說是災難性的問題，那么如何解決呢？

具體的解決方式，在CSM和G1中也不太一樣。CMS采用的是增量更新方案，G1則采用的是原始快照的方案。

漏標的問題想要發生，需要同時滿足兩個充要條件：

1、至少有一個黑色對象在自己被標記之后指向了這個白色對象

2、所有的灰色對象在自己引用掃描完成之前刪除了對白色對象的引用

那么，增量更新方案就是破壞了第一個條件，而原始快照方案就是破壞了第二個條件。

增量更新

“至少有一個黑色對象在自己被標記之后指向了這個白色對象”，這個條件如果被破壞了，那么就不會出現漏標的問題。所以：

如果有黑色對象在自己標記后，又重新指向了白色對象。那么我就把這個黑色對象的引用記錄下來，在后續「重新標記」階段再以這個黑色對象為根，對其引用進行重新掃描。通過這種方式，被黑色對象引用的白色對象就會變成灰色，從而變為存活狀態。

這種方式有個缺點，就是會重新掃描新增的這部分黑色對象，會浪費多一些時間。但是其實這個浪費還好，因為本來這種漏標的情況就并不是特別常見，所以這部分需要重新掃描的黑色對象也并不多。

原始快照

“所有的灰色對象在自己引用掃描完成之前刪除了對白色對象的引用”，這個條件如果被破壞了，那么就不會出現漏標的問題。所以：

如果灰色對象在掃描完成前刪除了對白色對象的引用，那么我們就在灰色對象取消引用之前，先將灰色對象引用的白色對象記錄下來。

在后續「重新標記」階段再以這些白色對象為根，對它的引用進行掃描，從而避免了漏標的問題。通過這種方式，原本漏標的對象就會被重新掃描變成灰色，從而變為存活狀態。

但是這種放回寺可能會把本來真的要取消引用的對象給錯誤的復活了，從而產生浮動垃圾。但是就像前面說的，多標的問題是可以忽略的。

總結

為了解決傳統的引用計數法和可達性分析算法存在的循環引用問題、誤標記問題以及STW時間長的問題，咋CMS和G1中引入了三色標記算法，其實就是在標記過程中將對象的狀態劃分為白色、灰色、和黑色三種狀態。

同時把一次標記拆分成初始標記、并發標記以及重新標記三個階段。并且只有初始標記和重新標記是STW的，而耗時最長的重新標記不需要STW，可以和應用線程并行。

但是因為并發標記過程中是不需要STW的，這就需要采用寫屏障的方式避免并發。但是還是會存在漏標和多標的問題。

多標的問題我們一般可以忽略，因為下次GC還是可以回收掉的。但是漏標的問題還是要解決的，避免對象使用過程中被回收了，為了解決這個問題，CMS和G1分別采用了增量更新和原始快照兩種方案來實現的，都能幫助我們解決漏標的問題。