三色標(biāo)記法是一種垃圾回收法舵鳞，它可以讓JVM不發(fā)生或僅短時(shí)間發(fā)生STW(Stop The World)震檩，從而達(dá)到清除JVM內(nèi)存垃圾的目的。JVM中的CMS蜓堕、G1垃圾回收器所使用垃圾回收算法即為三色標(biāo)記法抛虏。

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

三色標(biāo)記法將對(duì)象的顏色分為了黑、灰套才、白迂猴，三種顏色。

白色：該對(duì)象沒(méi)有被標(biāo)記過(guò)背伴。（對(duì)象垃圾）

灰色：該對(duì)象已經(jīng)被標(biāo)記過(guò)了沸毁，但該對(duì)象下的屬性沒(méi)有全被標(biāo)記完。（GC需要從此對(duì)象中去尋找垃圾）

黑色：該對(duì)象已經(jīng)被標(biāo)記過(guò)了傻寂，且該對(duì)象下的屬性也全部都被標(biāo)記過(guò)了息尺。（程序所需要的對(duì)象）

算法流程

從我們main方法的根對(duì)象（JVM中稱為GC Root）開(kāi)始沿著他們的對(duì)象向下查找，用黑灰白的規(guī)則疾掰，標(biāo)記出所有跟GC Root相連接的對(duì)象,掃描一遍結(jié)束后搂誉，一般需要進(jìn)行一次短暫的STW(Stop The World)，再次進(jìn)行掃描静檬，此時(shí)因?yàn)楹谏珜?duì)象的屬性都也已經(jīng)被標(biāo)記過(guò)了炭懊，所以只需找出灰色對(duì)象并順著繼續(xù)往下標(biāo)記（且因?yàn)榇蟛糠值臉?biāo)記工作已經(jīng)在第一次并發(fā)的時(shí)候發(fā)生了，所以灰色對(duì)象數(shù)量會(huì)很少拂檩，標(biāo)記時(shí)間也會(huì)短很多）, 此時(shí)程序繼續(xù)執(zhí)行侮腹，GC線程掃描所有的內(nèi)存，找出掃描之后依舊被標(biāo)記為白色的對(duì)象（垃圾）,清除广恢。

具體流程:

1. 首先創(chuàng)建三個(gè)集合：白凯旋、灰、黑钉迷。
2. 將所有對(duì)象放入白色集合中至非。
3. 然后從根節(jié)點(diǎn)開(kāi)始遍歷所有對(duì)象（注意這里并不遞歸遍歷），把遍歷到的對(duì)象從白色集合放入灰色集合糠聪。
4. 之后遍歷灰色集合荒椭，將灰色對(duì)象引用的對(duì)象從白色集合放入灰色集合，之后將此灰色對(duì)象放入黑色集合
5. 重復(fù) 4 直到灰色中無(wú)任何對(duì)象
6. 通過(guò)write-barrier檢測(cè)對(duì)象有變化舰蟆，重復(fù)以上操作
7. 收集所有白色對(duì)象（垃圾）

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

1. 浮動(dòng)垃圾：并發(fā)標(biāo)記的過(guò)程中趣惠，若一個(gè)已經(jīng)被標(biāo)記成黑色或者灰色的對(duì)象狸棍，突然變成了垃圾，由于不會(huì)再對(duì)黑色標(biāo)記過(guò)的對(duì)象重新掃描,所以不會(huì)被發(fā)現(xiàn)味悄，那么這個(gè)對(duì)象不是白色的但是不會(huì)被清除草戈，重新標(biāo)記也不能從GC Root中去找到，所以成為了浮動(dòng)垃圾侍瑟，浮動(dòng)垃圾對(duì)系統(tǒng)的影響不大唐片，留給下一次GC進(jìn)行處理即可。
2. 對(duì)象漏標(biāo)問(wèn)題（需要的對(duì)象被回收）：并發(fā)標(biāo)記的過(guò)程中涨颜，一個(gè)業(yè)務(wù)線程將一個(gè)未被掃描過(guò)的白色對(duì)象斷開(kāi)引用成為垃圾（刪除引用）费韭，同時(shí)黑色對(duì)象引用了該對(duì)象（增加引用）（這兩部可以不分先后順序）；因?yàn)楹谏珜?duì)象的含義為其屬性都已經(jīng)被標(biāo)記過(guò)了庭瑰，重新標(biāo)記也不會(huì)從黑色對(duì)象中去找星持，導(dǎo)致該對(duì)象被程序所需要，卻又要被GC回收弹灭，此問(wèn)題會(huì)導(dǎo)致系統(tǒng)出現(xiàn)問(wèn)題督暂，而CMS與G1，兩種回收器在使用三色標(biāo)記法時(shí)鲤屡，都采取了一些措施來(lái)應(yīng)對(duì)這些問(wèn)題损痰，CMS對(duì)增加引用環(huán)節(jié)進(jìn)行處理（Increment Update），G1則對(duì)刪除引用環(huán)節(jié)進(jìn)行處理(SATB)酒来。

解決辦法

在JVM虛擬機(jī)中有兩種常見(jiàn)垃圾回收器使用了該算法：CMS(Concurrent Mark Sweep)卢未、G1(Garbage First) ，為了解決三色標(biāo)記法對(duì)對(duì)象漏標(biāo)問(wèn)題各自有各自的法:

CMS回顧

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

從名字（包含“Mark Sweep”）上就可以看出CMS收集器是基于標(biāo)記-清除算法實(shí)現(xiàn)的就乓，它的運(yùn)作過(guò)程相對(duì)于前面幾種收集器來(lái)說(shuō)要更復(fù)雜一些汉匙，整個(gè)過(guò)程分為四個(gè)步驟，包括：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)記這兩個(gè)步驟仍然需要“Stop The World”噩翠。初始標(biāo)記僅僅只是標(biāo)記一下GCRoots能直接關(guān)聯(lián)到的對(duì)象，速度很快邦投；

并發(fā)標(biāo)記階段就是從GC Roots的直接關(guān)聯(lián)對(duì)象開(kāi)始遍歷整個(gè)對(duì)象圖的過(guò)程伤锚，這個(gè)過(guò)程耗時(shí)較長(zhǎng)但是不需要停頓用戶線程，可以與垃圾收集線程一起并發(fā)運(yùn)行志衣；

重新標(biāo)記階段則是為了修正并發(fā)標(biāo)記期間屯援，因用戶程序繼續(xù)運(yùn)作而導(dǎo)致標(biāo)記產(chǎn)生變動(dòng)的那一部分對(duì)象的標(biāo)記記錄猛们，這個(gè)階段的停頓時(shí)間通常會(huì)比初始標(biāo)記階段稍長(zhǎng)一些，但也遠(yuǎn)比并發(fā)標(biāo)記階段的時(shí)間短狞洋；

最后是并發(fā)清除階段弯淘，清理刪除掉標(biāo)記階段判斷的已經(jīng)死亡的對(duì)象，由于不需要移動(dòng)存活對(duì)象徘铝，所以這個(gè)階段也是可以與用戶線程同時(shí)并發(fā)的耳胎。由于在整個(gè)過(guò)程中耗時(shí)最長(zhǎng)的并發(fā)標(biāo)記和并發(fā)清除階段中，垃圾收集器線程都可以與用戶線程一起工作惕它，所以從總體上來(lái)說(shuō)，CMS收集器的內(nèi)存回收過(guò)程是與用戶線程一起并發(fā)執(zhí)行的废登。

CMS解決辦法:增量更新

在應(yīng)對(duì)漏標(biāo)問(wèn)題時(shí)淹魄，CMS使用了增量更新(Increment Update)方法來(lái)做：

在一個(gè)未被標(biāo)記的對(duì)象（白色對(duì)象）被重新引用后，引用它的對(duì)象若為黑色則要變成灰色堡距，在下次二次標(biāo)記時(shí)讓GC線程繼續(xù)標(biāo)記它的屬性對(duì)象甲锡。

但是就算是這樣，其仍然是存在漏標(biāo)的問(wèn)題：

• 在一個(gè)灰色對(duì)象正在被一個(gè)GC線程回收時(shí)羽戒，當(dāng)它已經(jīng)被標(biāo)記過(guò)的屬性指向了一個(gè)白色對(duì)象（垃圾）
• 而這個(gè)對(duì)象的屬性對(duì)象本身還未全部標(biāo)記結(jié)束缤沦，則為灰色不變
• 而這個(gè)GC線程在標(biāo)記完最后一個(gè)屬性后，認(rèn)為已經(jīng)將所有的屬性標(biāo)記結(jié)束了易稠，將這個(gè)灰色對(duì)象標(biāo)記為黑色缸废，被重新引用的白色對(duì)象，無(wú)法被標(biāo)記

CMS另兩個(gè)致命缺陷

1. CMS采用了Mark-Sweep算法驶社，最后會(huì)產(chǎn)生許多內(nèi)存碎片企量，當(dāng)?shù)揭欢〝?shù)量時(shí)，CMS無(wú)法清理這些碎片了亡电，CMS會(huì)讓Serial Old垃圾處理器來(lái)清理這些垃圾碎片届巩，而Serial Old垃圾處理器是單線程操作進(jìn)行清理垃圾的，效率很低份乒。所以使用CMS就會(huì)出現(xiàn)一種情況恕汇，硬件升級(jí)了，卻越來(lái)越卡頓或辖，其原因就是因?yàn)檫M(jìn)行Serial Old GC時(shí)瘾英，效率過(guò)低。
2. 解決方案：使用Mark-Sweep-Compact算法孝凌，減少垃圾碎片
3. 調(diào)優(yōu)參數(shù)（配套使用）：-XX:+UseCMSCompactAtFullCollection 開(kāi)啟CMS的壓縮
   -XX:CMSFullGCsBeforeCompaction 默認(rèn)為0方咆，指經(jīng)過(guò)多少次CMS FullGC才進(jìn)行壓縮
4. 當(dāng)JVM認(rèn)為內(nèi)存不夠，再使用CMS進(jìn)行并發(fā)清理內(nèi)存可能會(huì)發(fā)生OOM的問(wèn)題蟀架，而不得不進(jìn)行Serial Old GC瓣赂，Serial Old是單線程垃圾回收榆骚，效率低
5. 解決方案：降低觸發(fā)CMS GC的閾值，讓浮動(dòng)垃圾不那么容易占滿老年代
6. 調(diào)優(yōu)參數(shù)：-XX:CMSInitiatingOccupancyFraction 92% 可以降低這個(gè)值煌集，讓老年代占用率達(dá)到該值就進(jìn)行CMS GC

G1回顧

G1(Garbage First)物理內(nèi)存不再分代妓肢，而是由一塊一塊的Region組成,但是邏輯分代仍然存在。G1不再堅(jiān)持固定大小以及固定數(shù)量的分代區(qū)域劃分苫纤，而是把連續(xù)的Java堆劃分為多個(gè)大小相等的獨(dú)立區(qū)域（Region）碉钠，每一個(gè)Region都可以根據(jù)需要，扮演新生代的Eden空間卷拘、Survivor空間喊废，或者老年代空間。收集器能夠?qū)Π缪莶煌巧腞egion采用不同的策略去處理栗弟，這樣無(wú)論是新創(chuàng)建的對(duì)象還是已經(jīng)存活了一段時(shí)間污筷、熬過(guò)多次收集的舊對(duì)象都能獲取很好的收集效果。

Region中還有一類特殊的Humongous區(qū)域乍赫，專門用來(lái)存儲(chǔ)大對(duì)象瓣蛀。G1認(rèn)為只要大小超過(guò)了一個(gè)Region容量一半的對(duì)象即可判定為大對(duì)象。每個(gè)Region的大小可以通過(guò)參數(shù)-XX：G1HeapRegionSize設(shè)定雷厂，取值范圍為1MB～32MB惋增，且應(yīng)為2的N次冪。而對(duì)于那些超過(guò)了整個(gè)Region容量的超級(jí)大對(duì)象改鲫，將會(huì)被存放在N個(gè)連續(xù)的Humongous Region之中诈皿，G1的大多數(shù)行為都把Humongous Region作為老年代的一部分來(lái)進(jìn)行看待，如圖所示

JVM垃圾回收的“三色標(biāo)記算法”實(shí)現(xiàn)钩杰，內(nèi)容太干

G1前置知識(shí)

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

• 由于在進(jìn)行YoungGC時(shí)纫塌，我們?cè)谶M(jìn)行對(duì)一個(gè)對(duì)象是否被引用的過(guò)程，需要掃描整個(gè)Old區(qū)讲弄，所以JVM設(shè)計(jì)了CardTable措左，將Old區(qū)分為一個(gè)一個(gè)Card，一個(gè)Card有多個(gè)對(duì)象避除；如果一個(gè)Card中的對(duì)象有引用指向Young區(qū)怎披，則將其標(biāo)記為Dirty Card，下次需要進(jìn)行YoungGC時(shí)瓶摆，只需要去掃描Dirty Card即可凉逛。
• Card Table 在底層數(shù)據(jù)結(jié)構(gòu)以 Bit Map實(shí)現(xiàn)。

RSet(Remembered Set)

是輔助GC過(guò)程的一種結(jié)構(gòu)群井，典型的空間換時(shí)間工具状飞，和Card Table有些類似。

后面說(shuō)到的CSet(Collection Set)也是輔助GC的，它記錄了GC要收集的Region集合诬辈，集合里的Region可以是任意年代的酵使。

在GC的時(shí)候，對(duì)于old->young和old->old的跨代對(duì)象引用焙糟，只要掃描對(duì)應(yīng)的CSet中的RSet即可口渔。邏輯上說(shuō)每個(gè)Region都有一個(gè)RSet，RSet記錄了其他Region中的對(duì)象引用本Region中對(duì)象的關(guān)系穿撮，屬于points-into結(jié)構(gòu)（誰(shuí)引用了我的對(duì)象）缺脉。

而Card Table則是一種points-out（我引用了誰(shuí)的對(duì)象）的結(jié)構(gòu)，每個(gè)Card 覆蓋一定范圍的Heap（一般為512Bytes）悦穿。G1的RSet是在Card Table的基礎(chǔ)上實(shí)現(xiàn)的：每個(gè)Region會(huì)記錄下別的Region有指向自己的指針攻礼，并標(biāo)記這些指針?lè)謩e在哪些Card的范圍內(nèi)。這個(gè)RSet其實(shí)是一個(gè)Hash Table咧党，Key是別的Region的起始地址秘蛔，Value是一個(gè)集合，里面的元素是Card Table的Index傍衡。每個(gè)Region中都有一個(gè)RSet，記錄其他Region到本Region的引用信息负蠕；使得垃圾回收器不需要掃描整個(gè)堆找到誰(shuí)引用當(dāng)前分區(qū)中的對(duì)象蛙埂，只需要掃描RSet即可。

CSet(Collection Set)

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

新生代與老年代的比例

5% - 60%绣的，一般不使用手工指定，因?yàn)檫@是G1預(yù)測(cè)停頓時(shí)間的基準(zhǔn),這地方簡(jiǎn)要說(shuō)明一下,G1可以指定一個(gè)預(yù)期的停頓時(shí)間,然后G1會(huì)根據(jù)你設(shè)定的時(shí)間來(lái)動(dòng)態(tài)調(diào)整年輕代的比例,例如時(shí)間長(zhǎng),就將年輕代比例調(diào)小,讓YGC盡早行欲账。

G1解決辦法:SATB

SATB(Snapshot At The Beginning), 在應(yīng)對(duì)漏標(biāo)問(wèn)題時(shí)屡江，G1使用了SATB方法來(lái)做,具體流程：

1. 在開(kāi)始標(biāo)記的時(shí)候生成一個(gè)快照?qǐng)D標(biāo)記存活對(duì)象
2. 在一個(gè)引用斷開(kāi)后，要將此引用推到GC的堆棧里赛不，保證白色對(duì)象（垃圾）還能被GC線程掃描到(在write barrier(寫屏障)里把所有舊的引用所指向的對(duì)象都變成非白的)惩嘉。
3. 配合Rset，去掃描哪些Region引用到當(dāng)前的白色對(duì)象踢故，若沒(méi)有引用到當(dāng)前對(duì)象文黎，則回收

SATB詳細(xì)流程

1. SATB是維持并發(fā)GC的一種手段。G1并發(fā)的基礎(chǔ)就是SATB殿较。SATB可以理解成在GC開(kāi)始之前對(duì)堆內(nèi)存里的對(duì)象做一次快照耸峭，此時(shí)活的對(duì)像就認(rèn)為是活的，從而開(kāi)成一個(gè)對(duì)象圖淋纲。
2. 在GC收集的時(shí)候劳闹，新生代的對(duì)象也認(rèn)為是活的對(duì)象，除此之外其他不可達(dá)的對(duì)象都認(rèn)為是垃圾對(duì)象。
3. 如何找到在GC過(guò)程中分配的對(duì)象呢本涕？每個(gè)region記錄著兩個(gè)top-at-mark-start(TAMS)指針业汰，分別為prevTAMS和nextTAMS。在TAMS以上的對(duì)象就是新分配的偏友，因而被視為隱式marked蔬胯。
4. 通過(guò)這種方式我們就找到了在GC過(guò)程中新分配的對(duì)象，并把這些對(duì)象認(rèn)為是活的對(duì)象位他。
5. 解決了對(duì)象在GC過(guò)程中分配的問(wèn)題氛濒，那么在GC過(guò)程中引用發(fā)生變化的問(wèn)題怎么解決呢？
6. G1給出的解決辦法是通過(guò)Write Barrier鹅髓。Write Barrier就是對(duì)引用字段進(jìn)行賦值做了額外處理舞竿。通過(guò)Write Barrier就可以了解到哪些引用對(duì)象發(fā)生了什么樣的變化。
7. mark的過(guò)程就是遍歷heap標(biāo)記live object的過(guò)程窿冯，采用的是三色標(biāo)記算法骗奖，這三種顏色為white（表示還未訪問(wèn)到）含鳞、gray（訪問(wèn)到但是它用到的引用還沒(méi)有完全掃描）祭玉、back（訪問(wèn)到而且其用到的引用已經(jīng)完全掃描完）再菊。
8. 整個(gè)三色標(biāo)記算法就是從GC roots出發(fā)遍歷heap朵栖，針對(duì)可達(dá)對(duì)象先標(biāo)記white為gray讼载，然后再標(biāo)記gray為black作儿；遍歷完成之后所有可達(dá)對(duì)象都是balck的饭于，所有white都是可以回收的伸蚯。
9. SATB僅僅對(duì)于在marking開(kāi)始階段進(jìn)行“snapshot”(marked all reachable at mark start)缠沈，但是concurrent的時(shí)候并發(fā)修改可能造成對(duì)象漏標(biāo)記膘壶。
10. 對(duì)black新引用了一個(gè)white對(duì)象，然后又從gray對(duì)象中刪除了對(duì)該white對(duì)象的引用洲愤，這樣會(huì)造成了該white對(duì)象漏標(biāo)記颓芭。
11. 對(duì)black新引用了一個(gè)white對(duì)象，然后從gray對(duì)象刪了一個(gè)引用該white對(duì)象的white對(duì)象柬赐，這樣也會(huì)造成了該white對(duì)象漏標(biāo)記亡问。
12. 對(duì)black新引用了一個(gè)剛new出來(lái)的white對(duì)象，沒(méi)有其他gray對(duì)象引用該white對(duì)象躺率，這樣也會(huì)造成了該white對(duì)象漏標(biāo)記玛界。

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

因?yàn)镾ATB在重新標(biāo)記環(huán)節(jié)只需要去重新掃描那些被推到堆棧中的引用悼吱，并配合Rset來(lái)判斷當(dāng)前對(duì)象是否被引用來(lái)進(jìn)行回收慎框；

并且在最后G1并不會(huì)選擇回收所有垃圾對(duì)象，而是根據(jù)Region的垃圾多少來(lái)判斷與預(yù)估回收價(jià)值（指回收的垃圾與回收的STW時(shí)間的一個(gè)預(yù)估值）后添，將一個(gè)或者多個(gè)Region放到CSet中笨枯，最后將這些Region中的存活對(duì)象壓縮并復(fù)制到新的Region中，清空原來(lái)的Region。

G1會(huì)不會(huì)進(jìn)行Full GC?

會(huì)馅精，當(dāng)內(nèi)存滿了的時(shí)候就會(huì)進(jìn)行Full GC严嗜；且JDK10之前的Full GC，為單線程的洲敢，所以使用G1需要避免Full GC的產(chǎn)生漫玄。

解決方案：

• 加大內(nèi)存；
• 提高CPU性能压彭，加快GC回收速度睦优，而對(duì)象增加速度趕不上回收速度，則Full GC可以避免壮不；
• 降低進(jìn)行Mixed GC觸發(fā)的閾值汗盘，讓Mixed GC提早發(fā)生（默認(rèn)45%）