懒人听书,梦入神机

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

聊聊JVM三色標(biāo)記法

三色標(biāo)記（Tri-Color-Marking）

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：申請域名、雅安服務(wù)器托管、營銷軟件、網(wǎng)站建設(shè)、正安網(wǎng)站維護(hù)、網(wǎng)站推廣。

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

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

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

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

public class TriColorMarking {

    public static void main(String[] args){
        A a = new A();
        //開始做并發(fā)標(biāo)記
        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)建引用關(guān)系 A -> B ，B-> C , B -> D;
2. 當(dāng)我們做并發(fā)標(biāo)記的時候，垃圾收集器訪問過 A、B、C、D 最終都標(biāo)記為黑色。但是這個時候程序執(zhí)行了一個 a.b.d = null 就標(biāo)識 D 其實(shí)是沒有引用，理論上 D 對象可以被回收。這種情況就產(chǎn)生了 “浮動垃圾”。
3. 當(dāng)我們發(fā)現(xiàn)了 D 沒有引用，標(biāo)記為白色，但是在標(biāo)記完成過后發(fā)現(xiàn) a.d = d 。又新增了對象引用如果將 d 回收掉程序就會報錯肯定是不行的。這是一個典型的 “多標(biāo)” 場景。

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

漏標(biāo)

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

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

標(biāo)記過程中從圖1到下圖

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

多標(biāo)

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

這種情況是不可以接受的，如果正在被使用的程序?qū)ο蟊?JVM 回收，會導(dǎo)致程序運(yùn)行錯誤，是不可以接受的會導(dǎo)致嚴(yán)重 BUG。

解決漏標(biāo)和多標(biāo)

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

增量更新（Incremental Update）

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

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

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

寫屏障（Write Barrier）

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

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

寫屏障可以看做是虛擬機(jī)執(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

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

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

寫屏障，增量更新

當(dāng)對象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，當(dāng)讀取成員變量時，一律記錄下來：

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

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

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

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

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

卡表的維護(hù)

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

收集器采用的解決方案

CMS : 寫屏障，增量更新

G1，Shednandoah: 寫屏障 + STAB

ZGC：讀屏障

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

因?yàn)镾ATB相對增量更新效率會高(當(dāng)然SATB可能造成更多的浮動垃圾)，因?yàn)椴恍枰谥匦聵?biāo)記階段再次深度掃描被刪除引用對象，而CMS對增量更新的根對象會做深度掃描，G1因?yàn)楹芏鄬ο蠖嘉挥诓煌膔egion，CMS就一塊老年代區(qū)域，重新深度掃描對象的話G1的代價會比CMS高，所以G1選擇SATB不深度掃描對象，只是簡單標(biāo)記，等到下一輪GC再深度掃描。

參考資料

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

分享名稱：聊聊JVM三色標(biāo)記法
轉(zhuǎn)載來于：http://m.fisionsoft.com.cn/article/cdgjhei.html