阿里二面：JVM 的三色標(biāo)記算法你了解嗎？

一、前言

不得不說阿里的面試還是挺有質(zhì)量的，這個(gè)問題直接問到了 JVM 的底層算法實(shí)現(xiàn)。在說 JVM 的三色標(biāo)記算法之前，我們先來說下 JVM 對(duì)于常見對(duì)象存活判定算法與垃圾收集算法。常見對(duì)象存活判定算法有引用計(jì)數(shù)算法和可達(dá)性分析算法。引用計(jì)數(shù)法會(huì)產(chǎn)生循環(huán)引用問題，JVM 默認(rèn)是通過可達(dá)性分析算法來判斷對(duì)象是否存活的。而那些垃圾收集算法：標(biāo)記-清除、標(biāo)記-復(fù)制、標(biāo)記-整理算法以及在此基礎(chǔ)上的分代收集算法（新生代/老年代），每代采取不同的回收算法，以提高整體的分配和回收效率。

這些垃圾收集算法首先做的都是通過可達(dá)性分析算法來判定對(duì)象是否存活，首先肯定是先進(jìn)行標(biāo)記，這個(gè)也是理所當(dāng)然的，你不先標(biāo)記找到垃圾，怎么進(jìn)行垃圾回收？可達(dá)性分析算法是通過一系列的 “GC roots” 對(duì)象作為根節(jié)點(diǎn)搜索，如果在 “GC roots” 和一個(gè)對(duì)象之間沒有可達(dá)路徑，則稱該對(duì)象是不可達(dá)的。

迄今為止，所有垃圾收集器在根節(jié)點(diǎn)枚舉這一步驟時(shí)都是必須暫停用戶線程的，因此毫無疑問會(huì)面臨 ”Stop The World“ 的困擾。?。可妒?”Stop The World“，也就是我們平時(shí)說的 STW，其實(shí)就是根節(jié)點(diǎn)枚舉過程中必須在一個(gè)能保障一致性的快照中進(jìn)行，說白了就相當(dāng)于持久化的快照一樣，在某個(gè)時(shí)間點(diǎn)這個(gè)過程像被凍結(jié)了。如果根節(jié)點(diǎn)枚舉過程中整個(gè)根節(jié)點(diǎn)集合對(duì)象引用關(guān)系還在變化，那垃圾回收分析的結(jié)果也不會(huì)準(zhǔn)確，所以這就導(dǎo)致垃圾收集過程中必須停頓所有用戶線程。

想要解決或者降低用戶線程的停頓，三色標(biāo)記算法就登場(chǎng)了。為了讓大家了解為啥要有三色標(biāo)記算法的存在，老周在前言這里鋪了很多，希望對(duì)你看下面的內(nèi)容會(huì)有所幫助，那接下來我們就進(jìn)入我們的正題了。

二、 三色標(biāo)記算法

2.1 基本算法

事先約定：

• 初始狀態(tài)，所有的對(duì)象都是白色的，只有 GC Roots 是黑色的。

• 初始標(biāo)記階段，GC Roots 標(biāo)記直接關(guān)聯(lián)對(duì)象置為灰色。

• 并發(fā)標(biāo)記階段，掃描整個(gè)引用鏈。

• 沒有子節(jié)點(diǎn)的話，將本節(jié)點(diǎn)變?yōu)楹谏?/span>

• 有子節(jié)點(diǎn)的話，則當(dāng)前節(jié)點(diǎn)變?yōu)楹谏?，子?jié)點(diǎn)變?yōu)榛疑?/span>

• 重復(fù)并發(fā)標(biāo)記階段，直至灰色對(duì)象沒有其它子節(jié)點(diǎn)引用時(shí)結(jié)束。

• 掃描完成

  此時(shí)黑色對(duì)象就是存活的對(duì)象，白色對(duì)象就是已消亡可回收的對(duì)象。

  即（A、D、E、F、G）可達(dá)也就是存活對(duì)象，（B、C、H）不可達(dá)可回收的對(duì)象。

2.2 三色標(biāo)記算法缺陷

不知道你是否還記得我們前言說的，所有垃圾收集器在根節(jié)點(diǎn)枚舉這一步驟時(shí)都是必須暫停用戶線程的，產(chǎn)生 STW，這對(duì)實(shí)時(shí)性要求高的系統(tǒng)來說，這種需要長(zhǎng)時(shí)間掛起用戶線程是不可接受的。想要解決或者降低用戶線程的停頓的問題，我們才引入了三色標(biāo)記算法。

三色標(biāo)記算法也存在缺陷，在并發(fā)標(biāo)記階段的時(shí)候，因?yàn)橛脩艟€程與 GC 線程同時(shí)運(yùn)行，有可能會(huì)產(chǎn)生多標(biāo)或者漏標(biāo)。

2.3 多標(biāo)

假設(shè)已經(jīng)遍歷到 E（變?yōu)榛疑耍?，此時(shí)應(yīng)用執(zhí)行了 objD.fieldE = null (D > E 的引用斷開) 。

這部分本應(yīng)該回收但是沒有回收到的內(nèi)存，被稱之為浮動(dòng)垃圾。浮動(dòng)垃圾并不會(huì)影響應(yīng)用程序的正確性，只是需要等到下一輪垃圾回收中才被清除。

另外，針對(duì)并發(fā)標(biāo)記開始后的新對(duì)象，通常的做法是直接全部當(dāng)成黑色，本輪不會(huì)進(jìn)行清除。這部分對(duì)象期間可能會(huì)變?yōu)槔?，這也算是浮動(dòng)垃圾的一部分。

2.4 漏標(biāo)

假設(shè) GC 線程已經(jīng)遍歷到 E（變?yōu)榛疑耍?，此時(shí)應(yīng)用線程先執(zhí)行了：

var G = objE.fieldG; 
objE.fieldG = null;  // 灰色E 斷開引用 白色G 
objD.fieldG = G;  // 黑色D 引用 白色G

最終導(dǎo)致的結(jié)果是：G 會(huì)一直是白色，最后被當(dāng)作垃圾進(jìn)行清除。這直接影響到了應(yīng)用程序的正確性，是不可接受的。

不難分析，漏標(biāo)只有同時(shí)滿足以下兩個(gè)條件時(shí)才會(huì)發(fā)生：

• 一個(gè)或者多個(gè)黑色對(duì)象重新引用了白色對(duì)象；即黑色對(duì)象成員變量增加了新的引用。

• 灰色對(duì)象斷開了白色對(duì)象的引用（直接或間接的引用）；即灰色對(duì)象原來成員變量的引用發(fā)生了變化。

如下代碼：

var G = objE.fieldG; // 1.讀
objE.fieldG = null;  // 2.寫
objD.fieldG = G;     // 3.寫

我們只需在上面三個(gè)步驟中任意一個(gè)中，將對(duì)象 G 記錄起來，然后作為灰色對(duì)象再進(jìn)行遍歷即可。比如放到一個(gè)特定的集合，等初始的 GC Roots 遍歷完（并發(fā)標(biāo)記），該集合的對(duì)象遍歷即可（重新標(biāo)記）。

重新標(biāo)記是需要 STW 的，因?yàn)閼?yīng)用程序一直在跑的話，該集合可能會(huì)一直增加新的對(duì)象，導(dǎo)致永遠(yuǎn)都跑不完。當(dāng)然，并發(fā)標(biāo)記期間也可以將該集合中的大部分先跑了，從而縮短重新標(biāo)記 STW 的時(shí)間，這個(gè)是優(yōu)化問題了?？吹搅藳]？三色標(biāo)記算法也并不能完全解決 STW 的問題，只能盡可能縮短 STW 的時(shí)間，盡可能達(dá)到停頓時(shí)間最少。

三、讀屏障與寫屏障

針對(duì)于漏標(biāo)問題，JVM 團(tuán)隊(duì)采用了讀屏障與寫屏障的方案。

讀屏障是攔截第一步；而寫屏障用于攔截第二和第三步。

它們攔截的目的很簡(jiǎn)單：就是在讀寫前后，將對(duì)象 G 給記錄下來。

3.1 讀屏障

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

讀屏障是直接針對(duì)第一步：var G = objE.fieldG;，當(dāng)讀取成員變量之前，先記錄下來。

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); // 記錄讀取到的對(duì)象
    }
}

這種做法是保守的，但也是安全的。因?yàn)闂l件一中【一個(gè)或者多個(gè)黑色對(duì)象重新引用了白色對(duì)象】，重新引用的前提是：得獲取到該白色對(duì)象，此時(shí)已經(jīng)讀屏障就發(fā)揮作用了。

3.2 寫屏障

我們?cè)賮砜聪碌诙⑷降膶懖僮?，給某個(gè)對(duì)象的成員變量賦值時(shí)，底層代碼：

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

所謂的寫屏障，其實(shí)就是指給某個(gè)對(duì)象的成員變量賦值操作前后，加入一些處理（類似 Spring AOP 的概念）。

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

四、增量更新（Incremental Update）與原始快照（Snapshot At The Beginning，SATB）

4.1  增量更新

當(dāng)對(duì)象 D 的成員變量的引用發(fā)生變化時(shí)（objD.fieldG = G;），我們可以利用寫屏障，將 D 新的成員變量引用對(duì)象 G 記錄下來：

void post_write_barrier(oop* field, oop new_value) {  
    if ($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
        remark_set.add(new_value); // 記錄新引用的對(duì)象
    }
}

這種做法的思路是：不要求保留原始快照，而是針對(duì)新增的引用，將其記錄下來等待遍歷，即增量更新（Incremental Update）。

增量更新破壞了漏標(biāo)的條件一：【 一個(gè)或者多個(gè)黑色對(duì)象重新引用了白色對(duì)象】，從而保證了不會(huì)漏標(biāo)。

4.2 原始快照

當(dāng)對(duì)象 E 的成員變量的引用發(fā)生變化時(shí)（objE.fieldG = null;），我們可以利用寫屏障，將 E 原來成員變量的引用對(duì)象 G 記錄下來：

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

當(dāng)原來成員變量的引用發(fā)生變化之前，記錄下原來的引用對(duì)象。

這種做法的思路是：嘗試保留開始時(shí)的對(duì)象圖，即原始快照（Snapshot At The Beginning，SATB），當(dāng)某個(gè)時(shí)刻的 GC Roots 確定后，當(dāng)時(shí)的對(duì)象圖就已經(jīng)確定了。

比如當(dāng)時(shí) E 是引用著 G 的，那后續(xù)的標(biāo)記也應(yīng)該是按照這個(gè)時(shí)刻的對(duì)象圖走（E 引用著 G）。如果期間發(fā)生變化，則可以記錄起來，保證標(biāo)記依然按照原本的視圖來。

SATB 破壞了漏標(biāo)的條件二：【灰色對(duì)象斷開了白色對(duì)象的引用（直接或間接的引用）】，從而保證了不會(huì)漏標(biāo)。

五、總結(jié)

基于可達(dá)性分析的 GC 算法，標(biāo)記過程幾乎都借鑒了三色標(biāo)記的算法思想，盡管實(shí)現(xiàn)的方式不盡相同，比如標(biāo)記的方式有棧、隊(duì)列、多色指針等。

對(duì)于讀寫屏障，以 Java HotSpot VM 為例，其并發(fā)標(biāo)記時(shí)對(duì)漏標(biāo)的處理方案如下：

• CMS：寫屏障 + 增量更新

• G1、Shenandoah：寫屏障 + 原始快照

• ZGC：讀屏障

上面的的方案為啥是這樣的，你有想過為什么嗎？

• 原始快照相對(duì)增量更新來說效率更高（當(dāng)然原始快照可能造成更多的浮動(dòng)垃圾），因?yàn)椴恍枰谥匦聵?biāo)記階段再次深度掃描被刪除引用對(duì)象。

• 而 CMS 對(duì)增量引用的根對(duì)象會(huì)做深度掃描，G1 因?yàn)楹芏鄬?duì)象都位于不同的 region，CMS 就一塊老年代區(qū)域，重新深度掃描對(duì)象的話 G1 的代價(jià)會(huì)比 CMS 高，所以 G1 選擇原始快照不深度掃描對(duì)象，只是簡(jiǎn)單標(biāo)記，等到下一輪 GC 再深度掃描。

• 而 ZGC 有一個(gè)標(biāo)志性的設(shè)計(jì)是它采用的染色指針技術(shù)，染色指針可以大幅減少在垃圾收集過程中內(nèi)存屏障的使用數(shù)量，設(shè)置內(nèi)存屏障，尤其是寫屏障的目的通常是為了記錄對(duì)象引用的變動(dòng)情況，如果講這些信息直接維護(hù)在指針中，顯然可以省去一些專門的記錄操作。而 ZGC 沒有使用寫屏障，只使用了寫屏障，顯然對(duì)性能大有裨益的。

好了，這道面試題就說到這里，相信你跟著老周的文章看下來，心里有了自己想要的答案，我們下期再見。