三色標(biāo)記法
GC 垃圾回收器其主要的目的是為了實(shí)現(xiàn)內(nèi)存的回收崖瞭，在這個(gè)過程中主要的兩個(gè)步驟就是：內(nèi)存標(biāo)記，內(nèi)存回收勿决。
三色標(biāo)記法簡介
三色標(biāo)記法昙楚，主要是為了高效的標(biāo)記可被回收的內(nèi)存塊。
三色標(biāo)記（Tri-color Marking）作為工具來輔助推導(dǎo)科展，把遍歷對象圖過程中遇到的對象均牢，按照“是否訪問過”這個(gè)條件標(biāo)記成以下三種顏色：
- 白色：表示對象尚未被垃圾收集器訪問過。顯然在可達(dá)性分析剛剛開始的階段才睹，所有的對象都是白色的徘跪，若在分析結(jié)束的階段甘邀，仍然是白色的對象，即代表不可達(dá)垮庐。
- 黑色：表示對象已經(jīng)被垃圾收集器訪問過松邪，且這個(gè)對象的所有引用都已經(jīng)掃描過。黑色的對象代 表已經(jīng)掃描過哨查，它是安全存活的逗抑，如果有其他對象引用指向了黑色對象，無須重新掃描一遍寒亥。黑色對 象不可能直接（不經(jīng)過灰色對象）指向某個(gè)白色對象邮府。
- 灰色：表示對象已經(jīng)被垃圾收集器訪問過，但這個(gè)對象上至少存在一個(gè)引用還沒有被掃描過溉奕。
三色標(biāo)記過程
標(biāo)記過程：
- 在 GC 并發(fā)開始的時(shí)候褂傀，所有的對象均為白色；
- 在將所有的 GC Roots 直接應(yīng)用的對象標(biāo)記為灰色集合加勤；
- 如果判斷灰色集合中的對象不存在子引用仙辟，則將其放入黑色集合，若存在子引用對象鳄梅，則將其所有的子引用對象存放到灰色集合叠国，當(dāng)前對象放入灰色集合
- 按照此步驟 3 ，依此類推卫枝，直至灰色集合中所有的對象變黑后煎饼，本輪標(biāo)記完成，并且在白色集合內(nèi)的對象稱為不可達(dá)對象校赤，即垃圾對象吆玖。
- 標(biāo)記結(jié)束后，為白色的對象為 GC Roots 不可達(dá)马篮，可以進(jìn)行垃圾回收沾乘。
誤標(biāo)
什么是誤標(biāo)？當(dāng)下面兩個(gè)條件同時(shí)滿足浑测，會(huì)產(chǎn)生誤標(biāo)：
- 賦值器插入了一條或者多條黑色對象到白色對象的引用
- 賦值器刪除了全部從灰色對象到白色對象的直接引用或者間接引用
誤標(biāo)的解決方案
要解決誤標(biāo)的問題翅阵，只需要破壞這兩個(gè)條件中的任意一種即可，分別有兩種解決方案：增量更新（Incremental Update） 和原始快照（Snapshot At The Beginning, STAB）
增量更新
增量更新要破壞的是第一個(gè)條件迁央，當(dāng)黑色對象插入新的指向白色對象的引用關(guān)系時(shí)岖圈，就將這個(gè)新插入的引用記錄下來顽决，等并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關(guān)系中的黑色對象為根，重新掃描一次汹粤。這可以簡化理解為国葬，黑色對象一旦新插入了指向白色對象的引用之后，它就變回灰色對象 了序宦。
原始快照 (STAB)
原始快照要破壞的是第二個(gè)條件行剂，當(dāng)灰色對象要?jiǎng)h除指向白色對象的引用關(guān)系時(shí)，就將這個(gè)要?jiǎng)h 除的引用記錄下來，在并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關(guān)系中的灰色對象為根客税，重新掃描 一次捏膨。這也可以簡化理解為目胡，無論引用關(guān)系刪除與否，都會(huì)按照剛剛開始掃描那一刻的對象圖快照來進(jìn)行搜索。
漏標(biāo)和多標(biāo)
對于錯(cuò)標(biāo)其實(shí)細(xì)分出來會(huì)有兩種情況，分別是：漏標(biāo)和多標(biāo)
多標(biāo)-浮動(dòng)垃圾
如果標(biāo)記執(zhí)行到 E 此刻執(zhí)行了 object.E = null
在這個(gè)時(shí)候慢宗， E/F/G 理論上是可以被回收的。但是由于 E 已經(jīng)變?yōu)榱?strong>灰色了奔穿，那么它就會(huì)繼續(xù)執(zhí)行下去镜沽。最終的結(jié)果就是不會(huì)將他們標(biāo)記為垃圾對象，在本輪標(biāo)記中存活巫橄。
在本輪應(yīng)該被回收的垃圾沒有被回收淘邻，這部分被稱為“浮動(dòng)垃圾”。浮動(dòng)垃圾并不會(huì)影響程序的正確性湘换，這些“垃圾”只有在下次垃圾回收觸發(fā)的時(shí)候被清理宾舅。
還有在，標(biāo)記過程中產(chǎn)生的新對象彩倚，默認(rèn)被標(biāo)記為黑色筹我，但是可能在標(biāo)記過程中變?yōu)椤袄薄＿@也算是浮動(dòng)垃圾的一部分帆离。
漏標(biāo)-讀寫屏障
寫屏障（Store Barrier）
給某個(gè)對象的成員變量賦值時(shí)蔬蕊，其底層代碼大概長這樣：
/**
* @param field 某個(gè)對象的成員屬性
* @param new_value 新值，如：null
*/
void oop_field_store(oop* field, oop new_value) {
*fieild = new_value // 賦值操作
}
所謂寫屏障哥谷，其實(shí)就是在賦值操作前后岸夯，加入一些處理的邏輯（類似 AOP 的方式）
void oop_field_store(oop* field, oop new_value) {
pre_write_barrier(field); // 寫屏障-寫前屏障
*fieild = new_value // 賦值操作
pre_write_barrier(field); // 寫屏障-寫后屏障
}
寫屏障 + SATB
當(dāng)對象E的成員變量的引用發(fā)生變化時(shí)（objE.fieldG = null;）麻献，我們可以利用寫屏障，將E原來成員變量的引用對象G記錄下來：
void pre_write_barrier(oop* field) {
oop old_value = *field; // 獲取舊值
remark_set.add(old_value); // 記錄 原來的引用對象
}
【當(dāng)原來成員變量的引用發(fā)生變化之前猜扮，記錄下原來的引用對象】
這種做法的思路是：嘗試保留開始時(shí)的對象圖勉吻，即原始快照（Snapshot At The Beginning，SATB） 旅赢，當(dāng)某個(gè)時(shí)刻 的GC Roots確定后齿桃，當(dāng)時(shí)的對象圖就已經(jīng)確定了。
比如 當(dāng)時(shí) D是引用著G的煮盼，那后續(xù)的標(biāo)記也應(yīng)該是按照這個(gè)時(shí)刻的對象圖走（D引用著G）短纵。如果期間發(fā)生變化，則可以記錄起來僵控，保證標(biāo)記依然按照原本的視圖來香到。
值得一提的是，掃描所有GC Roots 這個(gè)操作（即初始標(biāo)記）通常是需要STW的喉祭，否則有可能永遠(yuǎn)都掃不完养渴，因?yàn)椴l(fā)期間可能增加新的GC Roots。
SATB破壞了條件一：【灰色對象 斷開了 白色對象的引用】泛烙，從而保證了不會(huì)漏標(biāo)。
一點(diǎn)小優(yōu)化：如果不是處于垃圾回收的并發(fā)標(biāo)記階段翘紊，或者已經(jīng)被標(biāo)記過了蔽氨，其實(shí)是沒必要再記錄了，所以可以加個(gè)簡單的判斷：
void pre_write_barrier(oop* field) {
// 處于GC并發(fā)標(biāo)記階段 且 該對象沒有被標(biāo)記（訪問）過
if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
oop old_value = *field; // 獲取舊值
remark_set.add(old_value); // 記錄 原來的引用對象
}
}
寫屏障 + 增量更新
當(dāng)對象D的成員變量的引用發(fā)生變化時(shí)（objD.fieldG = G;）帆疟，我們可以利用寫屏障鹉究，將D新的成員變量引用對象G記錄下來：
void post_write_barrier(oop* field, oop new_value) {
if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
remark_set.add(new_value); // 記錄新引用的對象
}
}
【當(dāng)有新引用插入進(jìn)來時(shí)，記錄下新的引用對象】
這種做法的思路是：不要求保留原始快照踪宠，而是針對新增的引用自赔，將其記錄下來等待遍歷，即增量更新（Incremental Update）柳琢。
增量更新破壞了條件二：【黑色對象 重新引用了 該白色對象】绍妨，從而保證了不會(huì)漏標(biāo)陶缺。
讀屏障(Load Barrier)
oop oop_field_load(oop* field) {
pre_load_barrier(field); // 讀屏障-讀取前操作
return *field;
}
讀屏障直接針對第一步 var objF = object.fieldG;,
void pre_load_barrier(oop* field, oop old_value) {
if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
oop old_value = *field;
remark_set.add(old_value); // 記錄讀取到的對象
}
}
這種做法是保守的践盼，但也是安全的。因?yàn)闂l件二中【黑色對象 重新引用了 該白色對象】柱锹，重新引用的前提是：得獲取到該白色對象倒堕，此時(shí)已經(jīng)讀屏障就發(fā)揮作用了灾测。
三色標(biāo)記法與垃圾回收器
增量更新： CMS
原始快照（STAB）： G1，Shenandoah
