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

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

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

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

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

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

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

什么是三色標(biāo)記法

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

白色：該對象沒有被標(biāo)記過。

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

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

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

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

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

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

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

寫屏障

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

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

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

通過使用寫屏障技術(shù)，三色標(biāo)記法能夠確保垃圾回收器能夠準(zhǔn)確地標(biāo)記所有可達(dá)對象，并且避免了多次標(biāo)記同一對象的情況。同時(shí)，寫屏障技術(shù)也會(huì)帶來一定的性能開銷，因?yàn)槊看我帽恍薷臅r(shí)都需要記錄新的標(biāo)記狀態(tài)。為了減少性能開銷，垃圾回收器通常會(huì)使用基于插入式寫屏障的優(yōu)化技術(shù)，來降低寫屏障的開銷。

多標(biāo)的問題

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

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

多標(biāo)的話，會(huì)產(chǎn)生浮動(dòng)垃圾，這個(gè)問題一般都不太需要解決，因?yàn)檫@種垃圾一般都不會(huì)太多，另外在下一次GC的時(shí)候也都能被回收掉。

多標(biāo)的問題

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

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

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

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

1、至少有一個(gè)黑色對象在自己被標(biāo)記之后指向了這個(gè)白色對象

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

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

增量更新

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

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

這種方式有個(gè)缺點(diǎn)，就是會(huì)重新掃描新增的這部分黑色對象，會(huì)浪費(fèi)多一些時(shí)間。但是其實(shí)這個(gè)浪費(fèi)還好，因?yàn)楸緛磉@種漏標(biāo)的情況就并不是特別常見，所以這部分需要重新掃描的黑色對象也并不多。

原始快照

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

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

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

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

總結(jié)

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

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

但是因?yàn)椴l(fā)標(biāo)記過程中是不需要STW的，這就需要采用寫屏障的方式避免并發(fā)。但是還是會(huì)存在漏標(biāo)和多標(biāo)的問題。

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