三色標記算法?

簡介?

????????三色標記算法是一種常見的垃圾收集的標記算法，屬于根可達算法的一個分支，垃圾收集器CMS，G1在標記垃圾過程中就使用該算法

????????三色標記法（Tri-color Marking）是垃圾回收中用于并發標記存活對象的核心算法，通過顏色狀態跟蹤對象可達性，解決并發標記期間因應用線程修改引用導致的漏標或多標問題

1. 白色（White）?：未訪問對象（可能是垃圾）
2. ?灰色（Grey）?：已訪問對象，但其子引用（成員變量）未被掃描
3. ?黑色（Black）?：已訪問對象，且其子引用已完全掃描

核心規則：

• 黑色對象不會直接指向白色對象?（否則會漏標）
• 所有存活對象最終會被標記為黑色，白色對象可安全回收

運行過程

①開始前，所有對象都在白集合中

?②被根對象GC ROOT直接引用的對象變成灰色，放進灰集合中

?③上一步灰色的對象全部變成黑色，進黑色集合中，而灰色的直接引用對象變成灰色進灰集合

④依舊參照上一步?

?⑤直到灰集合中沒有對象，所有的要存活對象都被掃描過了，白色的對象為垃圾會被回收掉?

?多標和漏標問題

????????在并發標記階段，垃圾收集器線程和用戶線程同時運行，此時E，F已經被掃描了，E變成黑色，F變成灰色，但是接下來用戶線程執行了E.F = null，會導致EF之間連線斷開，但是此時F已經變成灰色，但現在實際上F要成為白色的，又不能從灰->白，黑->灰，所以F就是多標了(本應該是垃圾，但是被標記救活了)，F就成了浮動垃圾，但是多標問題危害不大，因為下個垃圾回收周期就會把他們清除掉

????????依舊是在并發標記階段，垃圾收集器線程和用戶線程同時運行，此時E，F已經被掃描了，E變成黑色，F變成灰色，但是接下來用戶線程執行F.G = null? ?E.G = G，會導致FG之間連線斷開，而EG之間建立連線，因為黑色對象不能指向白色對象(因為黑色對象的意思就是已經被掃描過，不會再掃描)，就會導致G一直是白色最后會被回收掉，但實際上G是有用的對象，所以G就是漏標了(本應該是存活對象，但是沒被標記被回收了)，這個漏標的危害就會很高，因為在實際上這個對象還是要用的，就可能會導致空指針NullpointException

漏標問題是如何解決的

首先漏標必須保證兩個必要條件：

? ? ? ? ①至少有一個黑色對象指向白色對象（黑色對象E? ----> 白色對象G?之間有連線）

? ? ? ? ②所有指向該對象的灰色對象都斷開連接（灰色對象 F ----> 白色對象G 之間的連線斷開）

所以CMS和G1就是破壞其中一個條件來解決漏標問題。? ? ??

CMS解決漏標問題---增量更新方案

? ? ? ? 就是把黑色對象指向白色對象 中的黑色對象變成灰色，然后以灰色對象D為根節點，掃描整個引用鏈

G1解決漏標問題---原始快照方案

? ? ? ? ?在并發標記階段，灰色對象對白色對象的連接斷開了，會把白色對象給記錄下來，在最終標記階段，會把白色對象變成灰色，然后再以灰色對象為根節點，去掃描整個引用鏈

CMS(Concurrent Mark-Sweep)

?簡介

CMS（Concurrent Mark Sweep）收集器是一種以獲取最短回收停頓時間為目標的收集器。它通過并發標記-清除算法，減少應用程序的停頓時間，適合對延遲敏感的應用場景。

在CMS之前的垃圾回收器，要么就是串行垃圾回收方式(Serial GC)，要么就是關注系統吞吐量(Parallel Scavenge)。

工作流程

????????①初始標記(STW)：標記所有的GC ROOT以及被根對象直接引用的對象

????????②并發標記：垃圾回收器將遍歷對象圖，從GC Roots向下追溯，標記所有可達的對象。這個過程是四個階段中耗時最長的，但是不需要停頓用戶線程，可以與垃圾收集線程一起并發運行。

特點：

????????與應用線程并發執行。

????????可能產生浮動垃圾?（標記期間應用程序新產生的垃圾）

為了解決這個問題，CMS采用了卡表。當應用線程試圖修改老年代的某個對象引用時，把這些發生變化的對象所在的Card標識為Dirty，這樣后續就只需要掃描這些Dirty Card的對象，從而避免掃描整個老年代。

????????③重新標記(STW)：修正并發標記期間因應用線程運行導致的對象引用變化，實際上是要掃描整個堆內存的，但是實際上，由于各種優化技術，比如增量更新（Incremental Update）和卡表(Card Table)，重新標記階段可以只掃描部分區域。

????????④并發清除：垃圾回收器刪除未被標記的對象，并回收他們占用的內存空間，同樣，該步驟也是與應用線程并發執行的

優缺點分析

? ? ? ? 優點：①低停頓，是以響應時間優先的垃圾回收器

? ? ? ? ? ? ? ? ? ?②適用延遲敏感場景：如實時交易系統、Web服務

? ? ? ?缺點：①使用的是標記-清除算法，會產生內存碎片

? ? ? ? ? ? ? ? ? ②比較消耗CPU資源的，對處理器資源是比較敏感的，在并發階段，它不會導致用戶線程停頓，但會占用一部分線程（或者說處理器的計算能力）來進行垃圾回收，從而導致應用程序變慢，降低總吞吐量。

G1(Garbage First)

?簡介

G1，全名叫：Garbage First。是垃圾收集器技術發展歷史上的里程碑式的成果，從整體來看是基于標記-整理算法實現的收集器，但從局部（兩個Region之間）上看又是基于復制算法實現。開創了收集器面向局部收集的設計思路和基于Region的內存布局形式。所以G1相對于CMS的最主要的兩大特點：

? ? ? ? ①基于Region的內存布局

每一個Region都可以扮演不同的角色，并且當一個對象超過0.5個Region大小的時候，就會被判定為大對象，會放到Humorous區域中

? ? ? ? ②可預測的停頓時間模型

G1將Region作為單次回收的最小單元，即每次收集到的內存空間都是Region大小的整數倍

G1收集器會去跟蹤各個Region里面的垃圾堆積的「價值」大小，價值即回收所獲得的空間大小以及回收所需時間的經驗值，然后在后臺維護一個優先級列表。

每次根據用戶設定允許的收集停頓時間（-XX：MaxGCPauseMillis指定，默認值是200毫秒），優先處理回收價值收益最大的那些Region，保證了G1收集器在有限的時間內獲取盡可能高的收集效率。

? ? ? ? 并且對于跨Region之間對象引用是通過在每一個Region中維護一個記憶集RSet去存儲對象之間的引用關系

工作流程

????????①初始標記(STW)：標記從 GC Roots 直接可達的對象

? ? ? ? ②并發標記：根據引用鏈去標記所有存活對象，使用原始快照方式處理并發期間的對象變化

? ? ? ? ③最終標記(STW)：處理 SATB 中的剩余引用，修正標記結果

????????④篩選回收(STW)：根據用戶期望的停頓時間來制定回收計劃

優缺點分析

? ? ? ? 優點：①不會產生內存碎片

? ? ? ? ? ? ? ? ? ?②可預測的時間停頓模型

? ? ? ? 缺點：①內存占用，RSet和卡表會占用一定的內存

? ? ? ? ? ? ? ? ? ?②寫屏障開銷，維護 RSet 和卡表引入額外 CPU 開銷。