三色標記（Tri-Color-Marking）

垃圾收集器在并發(fā)標記的過程中，執(zhí)行標記期間應用線程還在并行運行，對象間的引用關系時刻發(fā)生變化，垃圾收集器在標記過程中就容易發(fā)生多標和漏標（其實多標和漏標我們統(tǒng)稱為誤標）。

針對這一問題我們通過 “三色標記 （Tri-Color-Marking）” 作為理論工具來輔助推導，將垃圾收集器遍歷對象引用的過程中，“按照是否訪問過” 這個條件標記成三種顏色。

• 黑色：表示對象已經(jīng)被垃圾收集器訪問過，并且這個對象的所有引用都被掃描過。它是安全存活的，如果有其他的對象指向了黑色的對象，無須重新掃描一遍。黑色對象不能直接（ 不經(jīng)過灰色對象）指向白色對象。
• 灰色：表示已經(jīng)被垃圾收集器訪問過，但是這個對象至少存在一個引用還沒有被掃描過。
• 白色：表示對象尚未被垃圾收集器訪問過。顯然在可達性分析的開始階段，所有的對象都是白色的，若在分析結束的時候還是白色的表示對象不可達。

三色標記示例代碼（示例來源于網(wǎng)絡）：

public class TriColorMarking {

    public static void main(String[] args){
        A a = new A();
        //開始做并發(fā)標記
        D d = a.b.d;   // 1.讀
        a.b.d = null;  // 2.寫
        a.d = d;       // 3.寫
    }
}

class A {
    B b = new B();
    D d = null;
}

class B {
    C c = new C();
    D d = new D();
}

class C {
}

class D {
}

例子的一個簡單說明：
1. 在 new A() 的時候會創(chuàng)建引用關系 A -> B ，B-> C , B -> D;
2. 當我們做并發(fā)標記的時候，垃圾收集器訪問過 A、B、C、D 最終都標記為黑色。但是這個時候程序執(zhí)行了一個 a.b.d = null 就標識 D 其實是沒有引用，理論上 D 對象可以被回收。這種情況就產(chǎn)生了 “浮動垃圾”。
3. 當我們發(fā)現(xiàn)了 D 沒有引用，標記為白色，但是在標記完成過后發(fā)現(xiàn) a.d = d 。又新增了對象引用如果將 d 回收掉程序就會報錯肯定是不行的。這是一個典型的 “多標” 場景。

下面我們會通過并發(fā)標記的過程中出現(xiàn)的漏標和多標場景進行分析。

漏標

在并發(fā)標記過程中，將原本消亡的對象標記為存活對象，這就是漏標。就會產(chǎn)生浮動垃圾，需要等到下次 GC 的時候清理。產(chǎn)生過程：

• 程序刪除了全部從灰色對象到該白色對象的直接或者間接引用

標記過程中從圖1到下圖

其實浮動垃圾是可以接受的只會影響垃圾收集器的效率，或者說是收集的比率。

多標

在并發(fā)標記過程中，將原本存活的對象標記為需要回收的對象。產(chǎn)生過程：程序插入一條或者多條從黑色對象到白色對象的新引用 標記過程中從圖1到下圖

這種情況是不可以接受的，如果正在被使用的程序對象被 JVM 回收，會導致程序運行錯誤，是不可以接受的會導致嚴重 BUG。

解決漏標和多標

解決漏標和多標分別有兩種解決方案：增量更新（Incremental Update） 和原始快照（Snapshot At The Beginning, STAB）

增量更新（Incremental Update）

這并發(fā)標記過程中，當黑色對象插入了新的指向白色引用關系時，就將這個插入引用記錄下來，并發(fā)標記結束后，再將這些記錄過的引用關系中的黑色對象為根，重新掃描一次。簡化理解, 黑色對象一旦新插入了指向白色對象的引用之后， 它就變成灰色對象。

原始快照（Snapshot At The Beginning, STAB）

這并發(fā)標記過程中，當灰色對象要刪除白色對象的引用關系時，就將這個需要刪除的記錄下來，在并發(fā)掃描結束后，再將這些記錄過的引用關系中的灰色對象為根，重新掃描一次，這樣就能掃描到白色對象，將白色的對象直接標記為黑色（目的就是為了讓這種對象在本輪 GC 清理中能夠存活下來，待下一輪 GC 的時候重新掃描，這個對象也可能成為浮動垃圾） 總之，無論是引用關系記錄插入還是刪除，虛擬機的記錄操作都是通過寫屏障來實現(xiàn)的。

寫屏障（Write Barrier）

JVM 通過寫屏障（Write Barrier）來維護卡表，卡表是記憶集的實現(xiàn)。記憶集是用來縮小 GC Root 的掃描范圍，我們在 GC 的時候只需要去過濾卡表變臟（Dirty）的元素，找到具體一塊卡頁內存塊，放入 GC Root 中一塊掃描。這是大概的一個流程，后續(xù)會講到，先有一個印象。再回到寫屏障，下面是一個對象賦值操作：

/**
* @param field 某對象的成員變量，如 a.b.d 
* @param new_value 新值，如 null
*/
void oop_field_store(oop* field, oop new_value){ 
    *field = new_value; // 賦值操作
}

寫屏障可以看做是虛擬機執(zhí)行對象字段賦值的一個攔截，類比 Spring AOP 的切面思想。

void oop_field_store(oop* field, oop new_value){  
    pre_write_barrier(field);          // 寫前屏障
    *field = new_value; 
    post_write_barrier(field, value);  // 寫后屏障
}

寫屏障，SATB

當對象B的成員變量的引用發(fā)生變化時，比如引用消失（a.b.d = null），我們可以利用寫屏障，將B原來成員變量的引用對象D記錄下來：

void pre_write_barrier(oop* field){
    oop old_value = *field;    // 獲取舊值
    remark_set.add(old_value); // 記錄原來的引用對象
}

寫屏障，增量更新

當對象A的成員變量的引用發(fā)生變化時，比如新增引用（a.d = d），我們可以利用寫屏障，將A新的成員變量引用對象D記錄下來：

void post_write_barrier(oop* field, oop new_value){  
    remark_set.add(new_value);  // 記錄新引用的對象
}

讀屏障（Load Barrier）

oop oop_field_load(oop* field){
    pre_load_barrier(field); // 讀屏障-讀取前操作
    return *field;
}

讀屏障是直接針對第一步：D d = a.b.d，當讀取成員變量時，一律記錄下來：

void pre_load_barrier(oop* field){  
    oop old_value = *field;
    remark_set.add(old_value); // 記錄讀取到的對象
}

記憶集和卡表（Remembered Set And Card Table）

垃圾收集器在新生代建立了記憶集（Remembered Set）的數(shù)據(jù)結構，用來避免把整個老年代的 GC root 掃描一遍。事實上并不只是新生代、 老年代之間才有跨代引用的問題， 所有涉及部分區(qū)域收集（Partial GC） 行為的垃圾收集器， 典型的如G1、 ZGC 和 Shenandoah 收集器， 都會面臨相同的問題。記憶集是一種記錄非收集區(qū)域指向收集區(qū)域的指針集合抽象的數(shù)據(jù)結構。

Hotspot 中使用一種叫做 “卡表” （Card Table）的方式來實現(xiàn)記憶集，也是目前最常用的一種方式。卡表和記憶集的關系，可以類比 Java 語言中 HashMap 和 Map 之間的關系。卡表是一個字節(jié)數(shù)組實現(xiàn)：CARD_TABLE[]， 每個元素都對應著一個標識的內存區(qū)域一塊特定大小的內存塊，稱為“卡頁”。Hotsport 卡頁的大小是 2^9 也就是 512 字節(jié)。

一個卡頁中可以包含多個對象，只要卡頁內一個或者多個對象的字段存在跨代引用，其對應的卡表的元素標識就變成了1，表示該元素變臟，否則為 0。GC 時，只需要篩選卡表中變臟的元素加入到 GCRoot 中。

卡表的維護

如何讓卡表變臟，即發(fā)生引用字段賦值時，如何更新卡表對應的標識為 1。Hotspot使用寫屏障維護卡表狀態(tài)。

收集器采用的解決方案

CMS : 寫屏障，增量更新 

G1，Shednandoah: 寫屏障 + STAB 

ZGC：讀屏障

為什么 G1 采用 SATB，CMS 使用增量更新? 

因為SATB相對增量更新效率會高(當然SATB可能造成更多的浮動垃圾)，因為不需要在重新標記階段再次深度掃描被刪除引用對象，而CMS對增量更新的根對象會做深度掃描，G1因為很多對象都位于不同的region，CMS就一塊老年代區(qū)域，重新深度掃描對象的話G1的代價會比CMS高，所以G1選擇SATB不深度掃描對象，只是簡單標記，等到下一輪GC再深度掃描。

參考資料

1.《深入理解 JAVA 虛擬機-第三版》周志明