JVM中的垃圾回收算法有很多種，其中三色標(biāo)記算法（Tri-colorMarkingAlgorithm）是一種非常常用的垃圾回收算法，也是現(xiàn)代JVM中垃圾回收器的基礎(chǔ)算法之一。
三色標(biāo)記算法將內(nèi)存中的對(duì)象劃分為三類(lèi)：白色對(duì)象、黑色對(duì)象和灰色對(duì)象。
- 黑色:表示對(duì)象已經(jīng)被垃圾收集器訪問(wèn)過(guò)，且這個(gè)對(duì)象的所有引用都已經(jīng)掃描過(guò)。黑色的對(duì)象代表已經(jīng)掃描過(guò)，它是安全存活的，如果有其他對(duì)象引用指向了黑色對(duì)象，無(wú)須重新掃描一遍。黑色對(duì)象不可能直接(不經(jīng)過(guò)灰色對(duì)象)指向某個(gè)白色對(duì)象。
- 灰色:表示對(duì)象已經(jīng)被垃圾收集器訪問(wèn)過(guò)，但這個(gè)對(duì)象上至少存在一個(gè)引用還沒(méi)有被掃描過(guò)。
- 白色:表示對(duì)象尚未被垃圾收集器訪問(wèn)過(guò)。顯然在可達(dá)性分析剛剛開(kāi)始的階段，所有的對(duì)象都是白色的，若在分析結(jié)束的階段，仍然是白色的對(duì)象，即代表不可達(dá)。
三色標(biāo)記算法的基本流程如下：
- 初始化所有對(duì)象為白色對(duì)象；
- 從根對(duì)象開(kāi)始遍歷整個(gè)對(duì)象圖，將所有可達(dá)對(duì)象標(biāo)記為灰色對(duì)象；
- 從灰色對(duì)象集合中取出一個(gè)對(duì)象，將其標(biāo)記為黑色對(duì)象，并將它所有引用的對(duì)象加入灰色對(duì)象集合中；
- 重復(fù)步驟3，直到灰色對(duì)象集合為空；
- 將所有未標(biāo)記為黑色對(duì)象的白色對(duì)象進(jìn)行回收。
在三色標(biāo)記算法中，灰色對(duì)象集合可以用一個(gè)隊(duì)列來(lái)實(shí)現(xiàn)。JVM中的垃圾回收器會(huì)定期啟動(dòng)垃圾回收線程來(lái)執(zhí)行三色標(biāo)記算法，并且盡量保證垃圾回收的停頓時(shí)間較短。
三色標(biāo)記算法的優(yōu)點(diǎn)是可以準(zhǔn)確地判斷出所有可達(dá)對(duì)象，并且能夠避免誤判問(wèn)題。缺點(diǎn)是需要耗費(fèi)一定的時(shí)間進(jìn)行掃描和標(biāo)記，并且在標(biāo)記階段需要暫停應(yīng)用程序的執(zhí)行，可能會(huì)引起一定的性能問(wèn)題。
在并發(fā)標(biāo)記的過(guò)程中，多標(biāo)和漏標(biāo)的情況就有可能發(fā)生。
原因
這是由于CMS采用的是“標(biāo)記-清除”算法，其中清除階段會(huì)與應(yīng)用程序并發(fā)運(yùn)行。在標(biāo)記階段，CMS需要在多線程下標(biāo)記所有的存活對(duì)象，這一過(guò)程稱(chēng)為并發(fā)標(biāo)記。在這個(gè)過(guò)程中，應(yīng)用程序線程仍在運(yùn)行，并在不斷地產(chǎn)生新的對(duì)象。因此，CMS可能會(huì)遺漏一些存活對(duì)象，導(dǎo)致漏標(biāo)記。同時(shí)，由于對(duì)象圖中存在環(huán)狀結(jié)構(gòu)，CMS可能會(huì)多次掃描同一個(gè)對(duì)象，導(dǎo)致多標(biāo)記。
多標(biāo)記的原因是由于在標(biāo)記過(guò)程中，CMS需要對(duì)跨代引用（即從年輕代指向老年代的引用）進(jìn)行處理，但由于對(duì)象的移動(dòng)或?qū)ο笠冒l(fā)生變化等原因，CMS可能會(huì)在多次掃描對(duì)象圖時(shí)重復(fù)標(biāo)記同一對(duì)象。這樣一來(lái)，某些對(duì)象可能會(huì)被標(biāo)記多次，這就是多標(biāo)記的情況。
漏標(biāo)記的原因則是由于CMS需要在應(yīng)用程序繼續(xù)運(yùn)行的情況下標(biāo)記對(duì)象，但應(yīng)用程序可能會(huì)在標(biāo)記期間不斷地創(chuàng)建新的對(duì)象，這些新的對(duì)象可能會(huì)被遺漏，導(dǎo)致漏標(biāo)記。例如，在并發(fā)標(biāo)記期間，一個(gè)對(duì)象已經(jīng)被標(biāo)記為存活對(duì)象，但由于它的引用已經(jīng)被修改，導(dǎo)致它被誤認(rèn)為是垃圾對(duì)象，從而被回收掉。這就是漏標(biāo)記的情況。
漏標(biāo)會(huì)導(dǎo)致被引用的對(duì)象被當(dāng)成垃圾誤刪除，這是嚴(yán)重bug，必須解決，有兩種解決方案:增量更新(IncrementalUpdate)和原始快照(SnapshotAtTheBeginning，SATB)。
增量更新就是當(dāng)黑色對(duì)象插入新的指向白色對(duì)象的引用關(guān)系時(shí)，就將這個(gè)新插入的引用記錄下來(lái)，等并發(fā)掃描結(jié)束之后，再將這些記錄過(guò)的引用關(guān)系中的黑色對(duì)象為根，重新掃描一次。這可以簡(jiǎn)化理解為，黑色對(duì)象一旦新插入了指向白色對(duì)象的引用之后，它就變回灰色對(duì)象了。
原始快照就是當(dāng)灰色對(duì)象要?jiǎng)h除指向白色對(duì)象的引用關(guān)系時(shí)，就將這個(gè)要?jiǎng)h除的引用記錄下來(lái)，在并發(fā)掃描結(jié)束之后，再將這些記錄過(guò)的引用關(guān)系中的灰色對(duì)象為根，重新掃描一次，這樣就能掃描到白色的對(duì)象，將白色對(duì)象直接標(biāo)記為黑色(目的就是讓這種對(duì)象在本輪gc清理中能存活下來(lái)，待下一輪gc的時(shí)候重新掃描，這個(gè)對(duì)象也有可能是浮動(dòng)垃圾)以上無(wú)論是對(duì)引用關(guān)系記錄的插入還是刪除，虛擬機(jī)的記錄操作都是通過(guò)寫(xiě)屏障實(shí)現(xiàn)的。
