🔭 嗨，您好 👋 我是 vnjohn，在互聯(lián)網(wǎng)企業(yè)擔任 Java 開發(fā)，CSDN 優(yōu)質創(chuàng)作者
📖 推薦專欄：Spring、MySQL、Nacos、Java，后續(xù)其他專欄會持續(xù)優(yōu)化更新迭代
🌲文章所在專欄：JVM
🤔 我當前正在學習微服務領域、云原生領域、消息中間件等架構、原理知識
💬 向我詢問任何您想要的東西，ID：vnjohn
🔥覺得博主文章寫的還 OK，能夠幫助到您的，感謝三連支持博客🙏
😄 代詞: vnjohn
? 有趣的事實：音樂、跑步、電影、游戲

目錄

前言

回顧 優(yōu)化內存利用：深入了解垃圾回收算法與回收器 一文，介紹了垃圾回收算法、垃圾收集器（垃圾收集算法是內存回收的方法論，那么垃圾收集器就是內存回收的實踐者）

主要談到了 CMS、G1 這兩種垃圾收集器，它們都有一個共同的特征，可支持并發(fā)標記，從此文來介紹它們兩者在并發(fā)標記階段共同所使用的算法

可達性分析算法

當前主流編程語言的垃圾收集器基本上都是依靠可達性分析算法來判定對象是否存活的，可達性分析算法理論上要求全過程都基于一個能保障一致性的快照才能進行分析，這意味著必須全程凍結用戶線程的運行

在 JVM 整個內存結構布局中，堆的大小占比是特別大的，堆越大，存儲的對象就越多，對象圖結構就越復雜，從而就要標記更多的對象而產(chǎn)生的 STW 時間就會越長

“標記階段”是所有垃圾收集算法的共同特征，若這個階段隨著堆變大而增加停頓時間，其所有的垃圾收集器都會在這個階段都會波及到一定影響，若能夠削減這部分帶來的停頓時間，收益也將會是系統(tǒng)性的提高

標記過程

簡要回顧一下 CMS、G1 兩者垃圾收集器在進行垃圾回收時所要發(fā)生的四個階段：

• CMS：初始標記、并發(fā)標記、重新標記、并發(fā)清除
• G1：初始標記、并發(fā)標記、最終標記、篩選回收

CMS、G1 兩者都有并發(fā)標記這個階段，導致了它們兩者在用戶線程、GC 回收線程同時運行時負載會有所不同，同時也會出現(xiàn)一些引用標記的問題「多標、漏標」

三色標記算法

若要解決或降低用戶線程的停頓，首先就會搞清楚為什么必須在一個能保障一致性的快照上同時還能進行對象圖的遍歷操作？

能保障一致性的快照上同時還能進行對象圖的遍歷操作：指的就是并發(fā)標記階段

在垃圾收集器中實踐階段，引入了 “三色標記” 算法作為輔助工具，把遍歷對象圖過程中遇到的對象，按照 “是否訪問過” 這個條件來標記成三種不同顏色的引用對象

1. 白色：表示對象尚未被垃圾收集器訪問過，在根可達分析剛開始的階段，所有對象都是白色的，若在標記階段結束后，仍然是白色的對象，即代表不可達，對象就會被回收 > 處于消亡狀態(tài)
2. 黑色：表示對象以及被垃圾收集器訪問過，且這個對象關聯(lián)的所有引用都已經(jīng)被掃描過；黑色的對象代表已經(jīng)被掃描過，它是安全存活的，若其他對象引用指向了黑色對象，無須再重新掃描一遍
3. 灰色：表示對象已經(jīng)被垃圾收集器訪問過，但這個對象上至少存在一個引用（屬性對象）還沒被掃描過

初始狀態(tài)，只有 GC Roots 是黑色的

標記過程：并發(fā)垃圾收集的標記階段過程中，灰色對象的標記狀態(tài)不斷向前推進，從黑色對象（已完成標記）擴展到白色對象（尚未被訪問）灰色對象是黑、白對象之間的分水嶺

從根對象逐步向下掃描，相當于就是在對象圖上從黑向白推進「灰色對象作為黑、白兩者之間的分水嶺」過程，從 Serial 系列、Parallel 系列垃圾收集器來看，當出現(xiàn)垃圾收集時，它們的用戶線程是處于凍結態(tài)的，只有垃圾收集線程是處于工作態(tài)的，就不會出現(xiàn)對象圖很亂的問題

故而言之，Serial 系列、Parallel 系列收集器無須額外使用三色標記算法去處理，它們采用追蹤式垃圾收集算法（標記-復制、標記-清除、標記-整理）處理即可

標記完成：標記階段完成，此時黑色對象就是存活的對象，白色對象就是已消亡且可回收對象

可是，當使用了 CMS 或 G1 垃圾收集器（并發(fā)垃圾收集器，支持垃圾收集線程、用戶線程并發(fā)執(zhí)行）時，這時候情況就不一樣了，垃圾收集線程會在對象圖結構上進行顏色標記，同時用戶線程也在修改引用關系（即修改對象圖的結構）這時就會出現(xiàn)兩種后果

多標、漏標

多標

多標：將原來消亡的對象錯誤標記為存活，這不是好事，增加了額外的內存空間浪費，但其實是可以容忍的，只不過產(chǎn)生了一些逃過本次垃圾收集產(chǎn)生的浮動垃圾而已，下次再進行清理即可

在顏色狀態(tài)推進的過程中，正在掃描的黑對象引用切斷與灰色對象關系（此時應已被標記為消亡態(tài)），但此時又有另外一個黑色對象將其標記了（此時又由最初的消亡態(tài)變換為存活態(tài)）

漏標

漏標：將原來存活的對象錯誤標記為已消亡，這種情況下就會比較嚴重，程序會因此發(fā)生程序錯誤，例如：Class Xxx Not Found

當且僅有兩個條件同時滿足時，會造成漏標問題的產(chǎn)生，即原本應當是黑色對象的被誤標記為白色對象

1. 插入了一條或多條從黑色對象到白色對象的新引用
2. 刪除了所有從灰色對象到白色對象的新引用

因此，要解決在并發(fā)標記階段所造成的漏標問題，只需要破壞這兩個條件中的任意一個條件即可，分別產(chǎn)生了以下兩種解決方案：增量更新（Increment Update）以及原始快照（Snapshot At The Beginning -> SATB）

我們來看造成漏標問題的第一個條件是如何產(chǎn)生的，如下圖：

結合第一張、第二張圖來看，再看上圖，在顏色狀態(tài)推進的過程中，正在掃描的灰色對象引用切斷與白色對象的聯(lián)系，同時原來白色引用的對象又已經(jīng)跟掃描過的黑對象建立了引用關系

增量更新的方案是破壞了第一個條件，當黑色對象插入新的指向白色對象關系時，就將這個新插入的引用記錄下來，等待并發(fā)標記階段結束以后的下一個階段，再將這些新插入的引用記錄，以黑色對象為根，重新掃描一次

CMS 采用的就是增量更新的方式來處理漏標問題，在它的重新標記階段進行處理，可以簡單理解為，一旦黑色對象插入了新的指向白色對象的引用，它就會變?yōu)榛疑珜ο?/p>

我們來看造成漏標問題的第二個條件是如何產(chǎn)生的，如下圖：

被切斷后的對象重新被黑色對象所引用的對象可能是原有引用鏈中的一部分，由于黑色對象只會掃描一次，這將導致掃描結束后出現(xiàn)兩個被黑色對象所引用的對象仍是白色，所以這兩個白色對象就會消失，這種情況就很嚴重了

原始快照的方案就是破壞了第二個條件，當灰色對象要刪除指向白色對象的引用關系時，就將這個要刪除的引用記錄下來，在并發(fā)標記階段后的下一個階段，再將這些刪除的引用關系以灰色對象為根，重新進行一次掃描工作

G1 采用的就是原始快照 SATB 方式來處理漏標問題的，在它的最終標記階段進行處理，也可以簡單理解為，無論引用關系刪除與否，都會按照剛開始掃描的那一刻對象圖快照記錄來進行重新掃描

Compare

增量更新、原始快照方式，無論是對引用關系的插入還是刪除，它們的記錄操作都是通過寫屏障技術來完成的

寫屏障技術被用于記錄對象的標記狀態(tài)，寫屏障技術一旦有引用關系發(fā)生了變化，它都會進行記錄，但現(xiàn)有的 CMS、G1 都采用了插入式寫屏障技術來進行優(yōu)化，減少了一些性能上的開銷工作

考慮性能的高低以及兩者之間的權衡來決定以黑為根還是以灰為根來進行一次重新掃描工作

增量更新：會重新以黑色對象為根進行重新掃描（黑色—>白色），會浪費多一些時間，但考慮到發(fā)生漏標問題的情況也不太常見，所以掃描這部分黑色對象自然也就不多
原始快照：可能會把原本要取消引用的對象（灰色—>白色）給錯誤的標記為存活狀態(tài)了，從而會產(chǎn)生一些浮動垃圾，也就是前面所說到的多標問題，能夠被忽略

總結

該篇博文主要介紹了 CMS、G1 在「并發(fā)標記」階段共同使用到的一種算法：三色標記算法，簡要說明了它的多標問題，重點介紹了在使用其算法時會發(fā)生的漏標問題，有兩種方式可以用來解決這種問題：增量更新、原始快照，CMS 使用的是前者，G1 使用的后者，最后對這兩種不同解決方案方式作了一下對比，希望此博文你能夠喜歡！

參考文獻：《深入理解 Java 虛擬機》周志明著

博文放在 JVM 專欄里，歡迎訂閱，會持續(xù)更新！

如果覺得博文不錯，關注我 vnjohn，后續(xù)會有更多實戰(zhàn)、源碼、架構干貨分享！

推薦專欄：Spring、MySQL，訂閱一波不再迷路

大家的「關注?? + 點贊👍 + 收藏?」就是我創(chuàng)作的最大動力！謝謝大家的支持，我們下文見！