歡迎大家關注我的微信公眾號【老周聊架構】烘绽，Java后端主流技術棧的原理、源碼分析俐填、架構以及各種互聯(lián)網(wǎng)高并發(fā)安接、高性能、高可用的解決方案英融。

一盏檐、前言

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

這些垃圾收集算法首先做的都是通過可達性分析算法來判定對象是否存活，首先肯定是先進行標記境肾，這個也是理所當然的剔难，你不先標記找到垃圾胆屿，怎么進行垃圾回收？可達性分析算法是通過一系列的 “GC roots” 對象作為根節(jié)點搜索偶宫，如果在 “GC roots” 和一個對象之間沒有可達路徑非迹，則稱該對象是不可達的。

迄今為止纯趋，所有垃圾收集器在根節(jié)點枚舉這一步驟時都是必須暫停用戶線程的憎兽，因此毫無疑問會面臨 ”Stop The World“ 的困擾。俺趁啊纯命？啥是 ”Stop The World“，也就是我們平時說的 STW痹栖，其實就是根節(jié)點枚舉過程中必須在一個能保障一致性的快照中進行亿汞，說白了就相當于持久化的快照一樣，在某個時間點這個過程像被凍結了揪阿。如果根節(jié)點枚舉過程中整個根節(jié)點集合對象引用關系還在變化疗我，那垃圾回收分析的結果也不會準確，所以這就導致垃圾收集過程中必須停頓所有用戶線程南捂。

想要解決或者降低用戶線程的停頓吴裤，三色標記算法就登場了。為了讓大家了解為啥要有三色標記算法的存在溺健，老周在前言這里鋪了很多嚼摩，希望對你看下面的內容會有所幫助，那接下來我們就進入我們的正題了矿瘦。

二枕面、 三色標記算法

2.1 基本算法

事先約定：

在這里插入圖片描述

根據(jù)可達性分析算法，從 GC Roots 開始進行遍歷訪問缚去。

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

在這里插入圖片描述

• 初始標記階段枕荞，GC Roots 標記直接關聯(lián)對象置為灰色。

在這里插入圖片描述

• 并發(fā)標記階段搞动，掃描整個引用鏈躏精。
  • 沒有子節(jié)點的話，將本節(jié)點變?yōu)楹谏?/li>
  • 有子節(jié)點的話鹦肿，則當前節(jié)點變?yōu)楹谏Ｖ颍庸?jié)點變?yōu)榛疑?/li>

在這里插入圖片描述

• 重復并發(fā)標記階段，直至灰色對象沒有其它子節(jié)點引用時結束箩溃。

在這里插入圖片描述

在這里插入圖片描述

• 掃描完成

  此時黑色對象就是存活的對象瞭吃，白色對象就是已消亡可回收的對象碌嘀。

  即（A、D歪架、E股冗、F、G）可達也就是存活對象和蚪，（B止状、C、H）不可達可回收的對象攒霹。

2.2 三色標記算法缺陷

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

三色標記算法也存在缺陷洛口，在并發(fā)標記階段的時候矫付，因為用戶線程與 GC 線程同時運行，有可能會產(chǎn)生多標或者漏標第焰。

2.3 多標

假設已經(jīng)遍歷到 E（變?yōu)榛疑耍┞蛴牛藭r應用執(zhí)行了 objD.fieldE = null (D > E 的引用斷開)

image.png

D > E 的引用斷開之后，E挺举、F杀赢、G 三個對象不可達，應該要被回收的湘纵。然而因為 E 已經(jīng)變?yōu)榛疑酥蓿淙詴划斪鞔婊顚ο罄^續(xù)遍歷下去。最終的結果是：這部分對象仍會被標記為存活梧喷，即本輪 GC 不會回收這部分內存砌左。

這部分本應該回收但是沒有回收到的內存，被稱之為浮動垃圾铺敌。浮動垃圾并不會影響應用程序的正確性汇歹，只是需要等到下一輪垃圾回收中才被清除。

另外偿凭，針對并發(fā)標記開始后的新對象产弹，通常的做法是直接全部當成黑色，本輪不會進行清除弯囊。這部分對象期間可能會變?yōu)槔∈樱@也算是浮動垃圾的一部分硝皂。

2.4 漏標

假設 GC 線程已經(jīng)遍歷到 E（變?yōu)榛疑耍藭r應用線程先執(zhí)行了：

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

在這里插入圖片描述

<figcaption style="line-height: inherit; margin: 0px; padding: 0px; margin-top: 10px; text-align: center; color: rgb(153, 153, 153); font-size: 0.7em;">在這里插入圖片描述</figcaption>

此時切回到 GC 線程作谭，因為 E 已經(jīng)沒有對 G 的引用了稽物，所以不會將 G 置為灰色；盡管因為 D 重新引用了 G折欠，但因為 D 已經(jīng)是黑色了贝或，不會再重新做遍歷處理。

最終導致的結果是：G 會一直是白色锐秦，最后被當作垃圾進行清除咪奖。這直接影響到了應用程序的正確性，是不可接受的酱床。

不難分析羊赵，漏標只有同時滿足以下兩個條件時才會發(fā)生：

• 一個或者多個黑色對象重新引用了白色對象；即黑色對象成員變量增加了新的引用扇谣。
• 灰色對象斷開了白色對象的引用（直接或間接的引用）昧捷；即灰色對象原來成員變量的引用發(fā)生了變化。

如下代碼：

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

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

重新標記是需要 STW 的瓶蝴，因為應用程序一直在跑的話毒返，該集合可能會一直增加新的對象，導致永遠都跑不完舷手。當然饿悬，并發(fā)標記期間也可以將該集合中的大部分先跑了，從而縮短重新標記 STW 的時間聚霜，這個是優(yōu)化問題了狡恬。看到了沒蝎宇？三色標記算法也并不能完全解決 STW 的問題弟劲，只能盡可能縮短 STW 的時間，盡可能達到停頓時間最少姥芥。

三兔乞、讀屏障與寫屏障

針對于漏標問題，JVM 團隊采用了讀屏障與寫屏障的方案。

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

它們攔截的目的很簡單：就是在讀寫前后，將對象 G 給記錄下來淡溯。

3.1 讀屏障

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

讀屏障是直接針對第一步：var G = objE.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); // 記錄讀取到的對象    }}

這種做法是保守的米间，但也是安全的。因為條件一中【一個或者多個黑色對象重新引用了白色對象】膘侮，重新引用的前提是：得獲取到該白色對象屈糊，此時已經(jīng)讀屏障就發(fā)揮作用了。

3.2 寫屏障

我們再來看下第二琼了、三步的寫操作逻锐，給某個對象的成員變量賦值時，底層代碼：

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

所謂的寫屏障，其實就是指給某個對象的成員變量賦值操作前后蹦哼，加入一些處理（類似 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 的成員變量的引用發(fā)生變化時（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); // 記錄新引用的對象    }}

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

增量更新破壞了漏標的條件一：【 一個或者多個黑色對象重新引用了白色對象】，從而保證了不會漏標毅戈。

4.2 原始快照

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

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

當原來成員變量的引用發(fā)生變化之前苇经，記錄下原來的引用對象赘理。

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

比如當時 E 是引用著 G 的施流，那后續(xù)的標記也應該是按照這個時刻的對象圖走（E 引用著 G）响疚。如果期間發(fā)生變化，則可以記錄起來瞪醋，保證標記依然按照原本的視圖來忿晕。

SATB 破壞了漏標的條件二：【灰色對象斷開了白色對象的引用（直接或間接的引用）】，從而保證了不會漏標趟章。

五杏糙、總結

基于可達性分析的 GC 算法，標記過程幾乎都借鑒了三色標記的算法思想蚓土，盡管實現(xiàn)的方式不盡相同宏侍，比如標記的方式有棧、隊列蜀漆、多色指針等谅河。

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

• CMS：寫屏障 + 增量更新
• G1绷耍、Shenandoah：寫屏障 + 原始快照
• ZGC：讀屏障

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

• 原始快照相對增量更新來說效率更高（當然原始快照可能造成更多的浮動垃圾）褂始，因為不需要在重新標記階段再次深度掃描被刪除引用對象。
• 而 CMS 對增量引用的根對象會做深度掃描描函，G1 因為很多對象都位于不同的 region崎苗，CMS 就一塊老年代區(qū)域，重新深度掃描對象的話 G1 的代價會比 CMS 高舀寓，所以 G1 選擇原始快照不深度掃描對象胆数，只是簡單標記，等到下一輪 GC 再深度掃描互墓。
• 而 ZGC 有一個標志性的設計是它采用的染色指針技術必尼，染色指針可以大幅減少在垃圾收集過程中內存屏障的使用數(shù)量，設置內存屏障篡撵，尤其是寫屏障的目的通常是為了記錄對象引用的變動情況判莉，如果講這些信息直接維護在指針中，顯然可以省去一些專門的記錄操作育谬。而 ZGC 沒有使用寫屏障券盅，只使用了讀屏障，顯然對性能大有裨益的斑司。

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