我們都知道， 當JVM判斷對象不再存活的時候，便會在下一次GC時候?qū)⒃搶ο蠡厥盏簦瑸槎羊v出空間，而JVM判斷對象存活的算法大家比較熟知的有兩種，分別是引用計數(shù)法和可達性分析算法

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

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

1、循環(huán)引用問題，如果兩個對象互相引用，就形成了一個環(huán)形結(jié)構(gòu)，如果采用引用計數(shù)法的話，那么這兩個對象將用于無法被回收。

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

3、STW時間長，可達性分析的整個過程都需要STW，以避免對象的狀態(tài)發(fā)生改變，這就導(dǎo)致GC停頓時長很長，大大影響應(yīng)用的整體性能。

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

什么是三色標記法

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

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

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

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

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

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

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

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

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

寫屏障

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

寫屏障是一種在對象引用被修改時，將其新的引用信息記錄在特殊數(shù)據(jù)結(jié)構(gòu)中的機制。在三色標記法中，寫屏障技術(shù)被用于記錄對象的標記狀態(tài)，并且只對未被標記過的對象進行標記。

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

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

多標的問題

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

這個一般發(fā)生在并發(fā)標記過程中，該對象還是有引用的，但是在過程中，應(yīng)用程序執(zhí)行過程中把他的引用關(guān)系刪除了，導(dǎo)致他變成了一個垃圾對象。

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

多標的問題

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

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

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

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

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

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

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

增量更新

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

如果有黑色對象在自己標記后，又重新指向了白色對象。那么我就把這個黑色對象的引用記錄下來，在后續(xù)「重新標記」階段再以這個黑色對象為根，對其引用進行重新掃描。通過這種方式，被黑色對象引用的白色對象就會變成灰色，從而變?yōu)榇婊顮顟B(tài)。

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

原始快照

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

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

在后續(xù)「重新標記」階段再以這些白色對象為根，對它的引用進行掃描，從而避免了漏標的問題。通過這種方式，原本漏標的對象就會被重新掃描變成灰色，從而變?yōu)榇婊顮顟B(tài)。

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

總結(jié)

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

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

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

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