1.前言

三色標(biāo)記算法，用于垃圾回收器升級(jí)，將STW變?yōu)椴l(fā)標(biāo)記。STW就是在標(biāo)記垃圾的時(shí)候，必須暫停程序，而使用并發(fā)標(biāo)記，就是程序一邊運(yùn)行，一邊標(biāo)記垃圾。

2. 三色標(biāo)記算法

2.1.什么是三色：

首先我們需要知道三色標(biāo)記法就是根據(jù)可達(dá)性分析，從GC Roots開(kāi)始進(jìn)行遍歷訪(fǎng)問(wèn)，在遍歷對(duì)象過(guò)程中，按“是否檢查過(guò)”這個(gè)條件將對(duì)象標(biāo)記成三種顏色：

• 黑色： 代表對(duì)象已經(jīng)檢查過(guò)，且成員對(duì)象也被檢查過(guò)了。如果有其他對(duì)象引用指向了黑色對(duì)象，無(wú)須重新檢查一遍。黑色對(duì)象不可能直接（不經(jīng)過(guò)灰色對(duì)象）指向某個(gè)白色對(duì)象。
• 灰色：代表對(duì)象已經(jīng)檢查過(guò)，但成員還沒(méi)全部檢查完成。
• 白色：代表對(duì)象沒(méi)有被檢查。 在可達(dá)性分析剛剛開(kāi)始的階段， 所有的對(duì)象都是白色的， 若在分析結(jié)束的階段， 仍然是白色的對(duì)象， 即代表不可達(dá)。

2.2.三色標(biāo)記過(guò)程：

假設(shè)現(xiàn)在有白、灰、黑三個(gè)集合（表示當(dāng)前對(duì)象的顏色），其遍歷訪(fǎng)問(wèn)過(guò)程為：

1. 初始時(shí)，所有對(duì)象都在【白色集合】中；
2. 將 GC Roots直接引用到的對(duì)象挪到【灰色集合】中；
3. 從灰色集合中獲取對(duì)象：

3.1. 將本對(duì)象引用到的其他對(duì)象全部挪到【灰色集合】中；

3.2. 將本對(duì)象挪到【黑色集合】里面。

4. 重復(fù)步驟3，直至【灰色集合】為空時(shí)結(jié)束。
5. 結(jié)束后，仍在【白色集合】的對(duì)象即為GC Roots不可達(dá)，可以進(jìn)行回收。

需要注意，傳統(tǒng)標(biāo)記方式發(fā)生Stop The World時(shí)，對(duì)象間的引用是不會(huì)發(fā)生變化的，可以輕松完成標(biāo)記。

而并發(fā)標(biāo)記在標(biāo)記期間應(yīng)用線(xiàn)程還在繼續(xù)跑，對(duì)象間的引用可能發(fā)生變化，就會(huì)出現(xiàn)錯(cuò)標(biāo)和漏標(biāo)的情況就有可能發(fā)生。

3.存在的問(wèn)題

3.1.浮動(dòng)垃圾：標(biāo)記過(guò)不是垃圾的，變成了垃圾

并發(fā)標(biāo)記的過(guò)程中，若一個(gè)已經(jīng)被標(biāo)記成黑色或者灰色的對(duì)象，突然變成了垃圾，此時(shí)，此對(duì)象不是白色的不會(huì)被清除，重新標(biāo)記也不能從GC Root中去找到，所以成為了浮動(dòng)垃圾，這種情況對(duì)系統(tǒng)的影響不大，留給下一次GC進(jìn)行處理即可。

3.2.對(duì)象漏標(biāo)問(wèn)題：需要的對(duì)象被回收

并發(fā)標(biāo)記的過(guò)程中，一個(gè)業(yè)務(wù)線(xiàn)程將一個(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)題。

4.總結(jié)

三色標(biāo)記算法是根可達(dá)算法的一種實(shí)現(xiàn)方案，其目的是為了找出所有可達(dá)對(duì)象。三色標(biāo)記算法會(huì)產(chǎn)生多標(biāo)和漏標(biāo)問(wèn)題，其中漏標(biāo)問(wèn)題最嚴(yán)重。漏標(biāo)問(wèn)題會(huì)導(dǎo)致本該存活的對(duì)象被回收，從而導(dǎo)致嚴(yán)重的程序問(wèn)題。