三色標(biāo)記法是一種垃圾回收法，它可以讓JVM不發(fā)生或僅短時間發(fā)生STW(Stop The World)叔汁，從而達(dá)到清除JVM內(nèi)存垃圾的目的叹坦。JVM中的CMS、G1垃圾回收器所使用垃圾回收算法即為三色標(biāo)記法扇雕。

三色標(biāo)記算法思想

三色標(biāo)記法將對象的顏色分為了黑拓售、灰、白镶奉，三種顏色础淤。

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

灰色：該對象已經(jīng)被標(biāo)記過了哨苛，但該對象下的屬性沒有全被標(biāo)記完鸽凶。（GC需要從此對象中去尋找垃圾）

黑色：該對象已經(jīng)被標(biāo)記過了，且該對象下的屬性也全部都被標(biāo)記過了建峭。（程序所需要的對象）

算法流程

從我們main方法的根對象（JVM中稱為GC Root）開始沿著他們的對象向下查找玻侥，用黑灰白的規(guī)則，標(biāo)記出所有跟GC Root相連接的對象,掃描一遍結(jié)束后亿蒸，一般需要進行一次短暫的STW(Stop The World)凑兰，再次進行掃描掌桩，此時因為黑色對象的屬性都也已經(jīng)被標(biāo)記過了，所以只需找出灰色對象并順著繼續(xù)往下標(biāo)記（且因為大部分的標(biāo)記工作已經(jīng)在第一次并發(fā)的時候發(fā)生了姑食，所以灰色對象數(shù)量會很少波岛，標(biāo)記時間也會短很多）, 此時程序繼續(xù)執(zhí)行，GC線程掃描所有的內(nèi)存音半，找出掃描之后依舊被標(biāo)記為白色的對象（垃圾）,清除则拷。

具體流程:

首先創(chuàng)建三個集合：白、灰曹鸠、黑煌茬。

將所有對象放入白色集合中。

然后從根節(jié)點開始遍歷所有對象（注意這里并不遞歸遍歷）物延，把遍歷到的對象從白色集合放入灰色集合宣旱。

之后遍歷灰色集合仅父，將灰色對象引用的對象從白色集合放入灰色集合叛薯，之后將此灰色對象放入黑色集合

重復(fù) 4 直到灰色中無任何對象

通過write-barrier檢測對象有變化，重復(fù)以上操作

收集所有白色對象（垃圾）

三色標(biāo)記存在問題

浮動垃圾：并發(fā)標(biāo)記的過程中笙纤，若一個已經(jīng)被標(biāo)記成黑色或者灰色的對象耗溜，突然變成了垃圾，由于不會再對黑色標(biāo)記過的對象重新掃描,所以不會被發(fā)現(xiàn)省容，那么這個對象不是白色的但是不會被清除抖拴，重新標(biāo)記也不能從GC Root中去找到，所以成為了浮動垃圾腥椒，浮動垃圾對系統(tǒng)的影響不大阿宅，留給下一次GC進行處理即可。

對象漏標(biāo)問題（需要的對象被回收）：并發(fā)標(biāo)記的過程中笼蛛，一個業(yè)務(wù)線程將一個未被掃描過的白色對象斷開引用成為垃圾（刪除引用）洒放，同時黑色對象引用了該對象（增加引用）（這兩部可以不分先后順序）；因為黑色對象的含義為其屬性都已經(jīng)被標(biāo)記過了滨砍，重新標(biāo)記也不會從黑色對象中去找往湿，導(dǎo)致該對象被程序所需要，卻又要被GC回收惋戏，此問題會導(dǎo)致系統(tǒng)出現(xiàn)問題领追，而CMS與G1，兩種回收器在使用三色標(biāo)記法時响逢，都采取了一些措施來應(yīng)對這些問題绒窑，CMS對增加引用環(huán)節(jié)進行處理（Increment Update），G1則對刪除引用環(huán)節(jié)進行處理(SATB)舔亭。

解決辦法

在JVM虛擬機中有兩種常見垃圾回收器使用了該算法：CMS(Concurrent Mark Sweep)些膨、G1(Garbage First) 散罕，為了解決三色標(biāo)記法對對象漏標(biāo)問題各自有各自的法:

CMS回顧

CMS(Concurrent Mark Sweep)收集器是一種以獲取最短回收停頓時間為目標(biāo)的收集器。目前很大一部分的Java應(yīng)用集中在互聯(lián)網(wǎng)網(wǎng)站或者基于瀏覽器的B/S系統(tǒng)的服務(wù)端上傀蓉，這類應(yīng)用通常都會較為關(guān)注服務(wù)的響應(yīng)速度欧漱，希望系統(tǒng)停頓時間盡可能短，以給用戶帶來良好的交互體驗葬燎。CMS收集器就非常符合這類應(yīng)用的需求(但是實際由于某些問題,很少有使用CMS作為主要垃圾回收器的)误甚。

從名字（包含“Mark Sweep”）上就可以看出CMS收集器是基于標(biāo)記-清除算法實現(xiàn)的，它的運作過程相對于前面幾種收集器來說要更復(fù)雜一些谱净，整個過程分為四個步驟窑邦，包括：

1）初始標(biāo)記（CMS initial mark）

2）并發(fā)標(biāo)記（CMS concurrent mark）

3）重新標(biāo)記（CMS remark）

4）并發(fā)清除（CMS concurrent sweep）

其中初始標(biāo)記、重新標(biāo)記這兩個步驟仍然需要“Stop The World”壕探。初始標(biāo)記僅僅只是標(biāo)記一下GCRoots能直接關(guān)聯(lián)到的對象冈钦，速度很快；

并發(fā)標(biāo)記階段就是從GC Roots的直接關(guān)聯(lián)對象開始遍歷整個對象圖的過程李请，這個過程耗時較長但是不需要停頓用戶線程瞧筛，可以與垃圾收集線程一起并發(fā)運行；

重新標(biāo)記階段則是為了修正并發(fā)標(biāo)記期間导盅，因用戶程序繼續(xù)運作而導(dǎo)致標(biāo)記產(chǎn)生變動的那一部分對象的標(biāo)記記錄较幌，這個階段的停頓時間通常會比初始標(biāo)記階段稍長一些，但也遠(yuǎn)比并發(fā)標(biāo)記階段的時間短白翻；

最后是并發(fā)清除階段乍炉，清理刪除掉標(biāo)記階段判斷的已經(jīng)死亡的對象，由于不需要移動存活對象滤馍，所以這個階段也是可以與用戶線程同時并發(fā)的岛琼。由于在整個過程中耗時最長的并發(fā)標(biāo)記和并發(fā)清除階段中，垃圾收集器線程都可以與用戶線程一起工作巢株，所以從總體上來說槐瑞，CMS收集器的內(nèi)存回收過程是與用戶線程一起并發(fā)執(zhí)行的。

CMS解決辦法:增量更新

在應(yīng)對漏標(biāo)問題時纯续，CMS使用了增量更新(Increment Update)方法來做：

在一個未被標(biāo)記的對象（白色對象）被重新引用后随珠，引用它的對象若為黑色則要變成灰色，在下次二次標(biāo)記時讓GC線程繼續(xù)標(biāo)記它的屬性對象猬错。

但是就算時這樣窗看，其仍然是存在漏標(biāo)的問題：

在一個灰色對象正在被一個GC線程回收時，當(dāng)它已經(jīng)被標(biāo)記過的屬性指向了一個白色對象（垃圾）

而這個對象的屬性對象本身還未全部標(biāo)記結(jié)束倦炒，則為灰色不變

而這個GC線程在標(biāo)記完最后一個屬性后显沈，認(rèn)為已經(jīng)將所有的屬性標(biāo)記結(jié)束了，將這個灰色對象標(biāo)記為黑色，被重新引用的白色對象拉讯，無法被標(biāo)記

CMS另兩個致命缺陷

CMS采用了Mark-Sweep算法涤浇，最后會產(chǎn)生許多內(nèi)存碎片，當(dāng)?shù)揭欢〝?shù)量時魔慷，CMS無法清理這些碎片了只锭，CMS會讓Serial Old垃圾處理器來清理這些垃圾碎片，而Serial Old垃圾處理器是單線程操作進行清理垃圾的院尔，效率很低蜻展。所以使用CMS就會出現(xiàn)一種情況，硬件升級了邀摆，卻越來越卡頓纵顾，其原因就是因為進行Serial Old GC時，效率過低栋盹。解決方案：使用Mark-Sweep-Compact算法施逾，減少垃圾碎片調(diào)優(yōu)參數(shù)（配套使用）：-XX:+UseCMSCompactAtFullCollection 開啟CMS的壓縮 -XX:CMSFullGCsBeforeCompaction 默認(rèn)為0，指經(jīng)過多少次CMS FullGC才進行壓縮

當(dāng)JVM認(rèn)為內(nèi)存不夠例获，再使用CMS進行并發(fā)清理內(nèi)存可能會發(fā)生OOM的問題汉额，而不得不進行Serial Old GC，Serial Old是單線程垃圾回收躏敢，效率低解決方案：降低觸發(fā)CMS GC的閾值闷愤，讓浮動垃圾不那么容易占滿老年代調(diào)優(yōu)參數(shù)：-XX:CMSInitiatingOccupancyFraction 92% 可以降低這個值，讓老年代占用率達(dá)到該值就進行CMS GC

G1回顧

G1(Garbage First)物理內(nèi)存不再分代件余，而是由一塊一塊的Region組成,但是邏輯分代仍然存在。G1不再堅持固定大小以及固定數(shù)量的分代區(qū)域劃分遭居，而是把連續(xù)的Java堆劃分為多個大小相等的獨立區(qū)域（Region）啼器，每一個Region都可以根據(jù)需要，扮演新生代的Eden空間俱萍、Survivor空間端壳，或者老年代空間。收集器能夠?qū)Π缪莶煌巧腞egion采用不同的策略去處理枪蘑，這樣無論是新創(chuàng)建的對象還是已經(jīng)存活了一段時間损谦、熬過多次收集的舊對象都能獲取很好的收集效果。

Region中還有一類特殊的Humongous區(qū)域岳颇，專門用來存儲大對象照捡。G1認(rèn)為只要大小超過了一個Region容量一半的對象即可判定為大對象。每個Region的大小可以通過參數(shù)-XX：G1HeapRegionSize設(shè)定话侧，取值范圍為1MB～32MB栗精，且應(yīng)為2的N次冪。而對于那些超過了整個Region容量的超級大對象，將會被存放在N個連續(xù)的Humongous Region之中悲立，G1的大多數(shù)行為都把Humongous Region作為老年代的一部分來進行看待鹿寨，如圖所示

G1前置知識

Card Table（多種垃圾回收器均具備）

由于在進行YoungGC時，我們在進行對一個對象是否被引用的過程薪夕，需要掃描整個Old區(qū)脚草，所以JVM設(shè)計了CardTable，將Old區(qū)分為一個一個Card原献，一個Card有多個對象玩讳；如果一個Card中的對象有引用指向Young區(qū)，則將其標(biāo)記為Dirty Card嚼贡，下次需要進行YoungGC時熏纯，只需要去掃描Dirty Card即可。

Card Table 在底層數(shù)據(jù)結(jié)構(gòu)以?Bit Map實現(xiàn)粤策。

RSet(Remembered Set)

是輔助GC過程的一種結(jié)構(gòu)樟澜，典型的空間換時間工具，和Card Table有些類似叮盘。

后面說到的CSet(Collection Set)也是輔助GC的秩贰，它記錄了GC要收集的Region集合，集合里的Region可以是任意年代的柔吼。

在GC的時候毒费，對于old->young和old->old的跨代對象引用，只要掃描對應(yīng)的CSet中的RSet即可愈魏。 邏輯上說每個Region都有一個RSet觅玻，RSet記錄了其他Region中的對象引用本Region中對象的關(guān)系，屬于points-into結(jié)構(gòu)（誰引用了我的對象）培漏。

而Card Table則是一種points-out（我引用了誰的對象）的結(jié)構(gòu)溪厘，每個Card 覆蓋一定范圍的Heap（一般為512Bytes）。G1的RSet是在Card Table的基礎(chǔ)上實現(xiàn)的：每個Region會記錄下別的Region有指向自己的指針牌柄，并標(biāo)記這些指針分別在哪些Card的范圍內(nèi)畸悬。 這個RSet其實是一個Hash Table，Key是別的Region的起始地址珊佣，Value是一個集合蹋宦，里面的元素是Card Table的Index。每個Region中都有一個RSet咒锻，記錄其他Region到本Region的引用信息冷冗；使得垃圾回收器不需要掃描整個堆找到誰引用當(dāng)前分區(qū)中的對象，只需要掃描RSet即可虫碉。

CSet(Collection Set)

一組可被回收的分區(qū)Region的集合, 是多個對象的集合內(nèi)存區(qū)域贾惦。

新生代與老年代的比例

5% - 60%，一般不使用手工指定，因為這是G1預(yù)測停頓時間的基準(zhǔn),這地方簡要說明一下,G1可以指定一個預(yù)期的停頓時間,然后G1會根據(jù)你設(shè)定的時間來動態(tài)調(diào)整年輕代的比例,例如時間長,就將年輕代比例調(diào)小,讓YGC盡早行须板。

G1解決辦法:SATB

SATB(Snapshot At The Beginning), 在應(yīng)對漏標(biāo)問題時碰镜，G1使用了SATB方法來做,具體流程：

在開始標(biāo)記的時候生成一個快照圖標(biāo)記存活對象

在一個引用斷開后，要將此引用推到GC的堆棧里习瑰，保證白色對象（垃圾）還能被GC線程掃描到(在write barrier(寫屏障)里把所有舊的引用所指向的對象都變成非白的)绪颖。

配合Rset，去掃描哪些Region引用到當(dāng)前的白色對象甜奄，若沒有引用到當(dāng)前對象柠横，則回收

SATB詳細(xì)流程

SATB是維持并發(fā)GC的一種手段。G1并發(fā)的基礎(chǔ)就是SATB课兄。SATB可以理解成在GC開始之前對堆內(nèi)存里的對象做一次快照牍氛，此時活的對像就認(rèn)為是活的，從而開成一個對象圖烟阐。在GC收集的時候搬俊，新生代的對象也認(rèn)為是活的對象，除此之外其他不可達(dá)的對象都認(rèn)為是垃圾對象蜒茄。如何找到在GC過程中分配的對象呢唉擂？每個region記錄著兩個top-at-mark-start(TAMS)指針，分別為prevTAMS和nextTAMS檀葛。在TAMS以上的對象就是新分配的玩祟，因而被視為隱式marked。通過這種方式我們就找到了在GC過程中新分配的對象屿聋，并把這些對象認(rèn)為是活的對象空扎。解決了對象在GC過程中分配的問題，那么在GC過程中引用發(fā)生變化的問題怎么解決呢胜臊？G1給出的解決辦法是通過Write Barrier勺卢。Write Barrier就是對引用字段進行賦值做了額外處理。通過Write Barrier就可以了解到哪些引用對象發(fā)生了什么樣的變化象对。mark的過程就是遍歷heap標(biāo)記live object的過程，采用的是三色標(biāo)記算法宴抚，這三種顏色為white（表示還未訪問到）勒魔、gray（訪問到但是它用到的引用還沒有完全掃描）、back（訪問到而且其用到的引用已經(jīng)完全掃描完）菇曲。整個三色標(biāo)記算法就是從GC roots出發(fā)遍歷heap冠绢，針對可達(dá)對象先標(biāo)記white為gray，然后再標(biāo)記gray為black常潮；遍歷完成之后所有可達(dá)對象都是balck的弟胀，所有white都是可以回收的。SATB僅僅對于在marking開始階段進行“snapshot”(marked all reachable at mark start)，但是concurrent的時候并發(fā)修改可能造成對象漏標(biāo)記孵户。對black新引用了一個white對象萧朝，然后又從gray對象中刪除了對該white對象的引用，這樣會造成了該white對象漏標(biāo)記夏哭。對black新引用了一個white對象检柬，然后從gray對象刪了一個引用該white對象的white對象，這樣也會造成了該white對象漏標(biāo)記竖配。對black新引用了一個剛new出來的white對象何址，沒有其他gray對象引用該white對象，這樣也會造成了該white對象漏標(biāo)記进胯。

SATB效率高于增量更新的原因用爪？

因為SATB在重新標(biāo)記環(huán)節(jié)只需要去重新掃描那些被推到堆棧中的引用，并配合Rset來判斷當(dāng)前對象是否被引用來進行回收胁镐；

并且在最后G1并不會選擇回收所有垃圾對象偎血，而是根據(jù)Region的垃圾多少來判斷與預(yù)估回收價值（指回收的垃圾與回收的STW時間的一個預(yù)估值），將一個或者多個Region放到CSet中希停，最后將這些Region中的存活對象壓縮并復(fù)制到新的Region中烁巫，清空原來的Region。

G1會不會進行Full GC?

會宠能，當(dāng)內(nèi)存滿了的時候就會進行Full GC亚隙；且JDK10之前的Full GC，為單線程的违崇，所以使用G1需要避免Full GC的產(chǎn)生阿弃。

解決方案：

加大內(nèi)存；

提高CPU性能羞延，加快GC回收速度渣淳，而對象增加速度趕不上回收速度，則Full GC可以避免伴箩；

降低進行Mixed GC觸發(fā)的閾值入愧，讓Mixed GC提早發(fā)生（默認(rèn)45%）