一敏储、為什么需要GC

Java 程序員都知道對象初始化的重要性，我們要使用一個對象抗楔，必須先為其分配內(nèi)存空間進(jìn)行初始化，而使用完了對象后拦坠，我們很少關(guān)注要如何處理那些對象连躏，可能會在明確對象不再使用的地方將對象設(shè)置為 null。而系統(tǒng)內(nèi)存空間是有限的贞滨，操作系統(tǒng)允許一個應(yīng)用程序占用的最大內(nèi)存也是有限制的入热，當(dāng)程序員“不羈放縱愛自由”地創(chuàng)建了很多對象后，JVM 垃圾回收器默默地在后臺維護(hù)和清理了不需要的對象占用的內(nèi)存空間。

垃圾回收器是一種動態(tài)存儲分配器才顿，它自動釋放程序不再需要的已分配的內(nèi)存塊莫湘，這些塊稱為“垃圾”，也就是不再被引用的對象郑气。自動回收垃圾的過程則稱為垃圾回收（Garbage Collection）幅垮，簡稱 GC。在一個支持垃圾收集的語言中尾组，程序顯式地申請內(nèi)存忙芒，但從不需要顯式地釋放它們，垃圾收集器會定期識別垃圾塊讳侨，并將垃圾塊放回空閑鏈表中呵萨。GC 技術(shù)幫助程序員實(shí)現(xiàn)自動管理內(nèi)存，程序員可以將注意力集中在業(yè)務(wù)邏輯跨跨，從繁重的內(nèi)存管理中解放出來潮峦，而像 C 語言的 malloc 是一個不帶 GC 功能的分配器，程序員顯式調(diào)用 malloc 分配內(nèi)存后需要顯式調(diào)用 free 來釋放它勇婴，否則會出現(xiàn)內(nèi)存泄露忱嘹、懸空指針等內(nèi)存問題。

二耕渴、GC的算法分類

引用計數(shù)法

每個對象都有一個引用計數(shù)器拘悦，當(dāng)對象被引用一次則計數(shù)器加1，當(dāng)對象引用失效一次則計數(shù)器減1橱脸，對于引用數(shù)為0的對象意味著是垃圾對象础米，可以被GC回收；python添诉，Go等語言采用該方式回收垃圾屁桑；

可達(dá)性算法

從GC roots開始搜索，整個連通圖中的對象都是活對象吻商，對于GC Roots無法到達(dá)的對象便成了垃圾回收的對象掏颊，隨時可被GC回收。

分代收集理論

• 當(dāng)前商業(yè)虛擬機(jī)的垃圾收集器艾帐，大多數(shù)都遵循了“分代收集”(Generational Collection)的理論進(jìn)行設(shè)計乌叶，分代收集名為理論，實(shí)質(zhì)是一套符合大多數(shù)程序運(yùn)行實(shí)際情況的經(jīng)驗(yàn)法則柒爸，它建立在兩個分代假說之上：
  1. 弱分代假說(Weak Generational Hypothesis): 絕大多數(shù)對象都是朝生夕滅的
  2. 強(qiáng)分代假說(Strong Generational Hypothesis): 熬過越多次垃圾收集過程的對象就越難以消亡准浴。
  3. 根據(jù)以上兩條分代假說可推理出：跨代引用假說 跨代引用相對于同代引用來說僅占極少數(shù)
• 對應(yīng)的可以在Java堆劃分出不同的區(qū)域，垃圾收集器每次只回收其中某一個或者某些部分的區(qū)域 ——因而就有了“Minor GC”捎稚，“Major GC”乐横，“Full GC”這樣的回收類型的劃分;也就能夠針對不同的區(qū)域安排與里面存儲對象存亡特征相匹配的垃圾收集算法——因此發(fā)展出了“標(biāo)記-復(fù)制算法”“標(biāo)記-清除算法”求橄，“標(biāo)記-整理算法”等針對性的垃圾收集算法；

Minor GC/Young GC：針對新生代的垃圾收集
Major GC/Old GC：針對老年代的垃圾收集
MixedGC：針對于新生代與部分老年代的垃圾收集
Full GC：針對于整個Java堆和方法區(qū)(MetaSpace元空間) 的垃圾收集

GC_all_type.jpg

三葡公、經(jīng)典 GC 算法詳解

1罐农、copy算法

• 1963年Marvin Minsky提出：這個算法的基本思想是把某個空間里的活躍對象復(fù)制到其他空間，把原來的空間全部清空催什，這就相當(dāng)于是把活躍的對象從一個空間搬到新的空間涵亏。因?yàn)檫@種復(fù)制具有方向性，所以我們把原空間稱為From空間（分配空間）蒲凶，把新的目標(biāo)空間稱為 To 空間（幸存者空間）
• 最基礎(chǔ)copy算法可以將堆平分兩份气筋，但太浪費(fèi)了，GC年輕代默認(rèn)按照8:1:1分配旋圆；

對象分配

• 碰撞指針分配對象：對象之間沒有任何空隙宠默，不會產(chǎn)生內(nèi)存碎片；

  
  
  copy_top.png

對象回收

• 可達(dá)性分析算法需要找到GCroot灵巧，能作為GCront的對象有：

  1. 虛擬機(jī)棧中的引用的對象
  2. 類靜態(tài)屬性引用的對象
  3. 常量引用的對象
  4. 本地方法棧中的JNI（native方法）引用的對象

• 可達(dá)性基本思想：由以上對象引用鏈構(gòu)成一張圖搀矫，如果從根出發(fā)，開始對圖進(jìn)行遍歷孩等，能夠遍歷到就是活躍對象艾君，否則為垃圾對象；

• 如何將對象之間引用關(guān)系抽象成圖呢肄方？我們看JVM中java對象在內(nèi)存中構(gòu)成：Oop-Klass模型
  

  class_type.png

• 根據(jù)klass快速獲取哪些位置存放為引用字段，若為引用蹬癌，且引用不為null,就表示當(dāng)前對象引用了其他對象权她。這樣從根引用出發(fā)就可以構(gòu)建一張圖；

• 一般對圖遍歷有兩種算法： 深度優(yōu)先遍歷（DFS） 和 廣度優(yōu)先遍歷（BFS）

DFS在Copy中實(shí)現(xiàn)

1. 比如有如下引用關(guān)系A(chǔ),B,C都是活躍對象逝薪，我們?nèi)绾芜M(jìn)行深度優(yōu)先遍歷Copy呢隅要？

   
   
   copy_DFS_01.png

2. 遍歷過程中，A拷貝到To space,然后C又拷貝過去董济，此時空間引用時將是這樣的步清！

   
   
   copy_DFS_02.png

3. 若當(dāng)拷貝B后再將C拷貝一份，則To中又兩個C了虏肾，如何解決呢廓啊？

   • 使用forwarding指針：在每個對象頭部引入一個新的field,即forwarding，正常狀態(tài)下封豪，其值為null,如果一個對象被拷貝谴轮，就把它的新地址設(shè)到From空間對象的forwarding指針中；

     
     
     copy_DFS_03.png

BFS與DFS在copy算法中對比

• 舉例對比方能解釋明晰：

class A {
    public B b1;
    public B b2;
    public A() {
        b1 = new B();
        b2 = new B();
    }
}
class B {
    public C c1;
    public C c2;
    public B() {
        c1 = new C();
        c2 = new C();
    }
}
class C {
}

1. 對于以上對象吹埠，在From空間布局如下所示：

   
   
   copy_BFS_01.png

2. 我們開始從A用DFS遍歷第步，拷貝至TO空間

   
   
   copy_BFS_02.png

3. 對A的屬性擴(kuò)展疮装，先訪問屬性b1引用的對象，即把b1指向?qū)ο罂截愔罷O空間

   
   
   copy_BFS_03.png

4. 接著我們拷貝c1所引用的C對象,這部完成以后開始退棧（DFS依靠棧粘都，BFS依靠隊列實(shí)現(xiàn)）

   
   
   copy_BFS_04.png

5. 依次退棧廓推，直到完成copy后布局如下：

   
   
   copy_BFS_05.png

• 經(jīng)過以上步驟，不知你發(fā)現(xiàn)什么沒有： 對比起始于結(jié)束箭頭翩隧，會發(fā)現(xiàn)變簡約好多啊樊展，箭頭代表了引用關(guān)系，說明具有引用關(guān)系的對象在新空間中距離更近了鸽心！這有啥用呢滚局？

DFS總結(jié)

• 優(yōu)點(diǎn)： 編程中如果訪問一個對象，馬上就會訪問它的屬性顽频，而又因?yàn)镃PU緩存機(jī)制藤肢，在讀取某個對象時，又很大概率會把它后面的對象一起讀進(jìn)來糯景。而經(jīng)過DFS遍歷后嘁圈，擁有引用關(guān)系極大可能會在同一個緩存中，即讀 A 對象的時候蟀淮，把它后面的 B 和 C 對象都能加載進(jìn)緩存最住，那么，a.b1.c1 這種寫法就可以立即命中緩存怠惶；
• 缺點(diǎn)： 需要維護(hù)一個額外的輔助數(shù)據(jù)結(jié)構(gòu)棧涨缚；

BFS總結(jié)

• 你可以對應(yīng)的使用BFS遍歷上方舉例，它的優(yōu)缺點(diǎn)剛好與深度優(yōu)先搜索相反策治；

• 優(yōu)點(diǎn)：無需額外空間脓魏，其所需的隊列，巧妙地隱藏在了 To 空間中通惫；

• 缺點(diǎn)：有引用關(guān)系的對象之間的距離就會比較遠(yuǎn)茂翔，這將不利于業(yè)務(wù)線程運(yùn)行期的緩存命中；

• 深度優(yōu)先搜索的非遞歸寫法需要占用額外的空間履腋，但有利于提高業(yè)務(wù)線程運(yùn)行期的緩存命中率珊燎。而廣度優(yōu)先搜索則與其相反，它不利于運(yùn)行期的緩存命中遵湖，但算法的執(zhí)行效率更高悔政。所以 JDK6 以前的 JVM 使用了廣度優(yōu)先的非遞歸遍歷，而在 JDK8 以后奄侠，已經(jīng)把廣度優(yōu)先算法改為深度優(yōu)先了卓箫，盡管這樣做需要額外引用一個獨(dú)立的棧。

2垄潮、CMS算法

• CMS（Concurrent Mark Sweep）是一款里程碑式的垃圾收集器烹卒，為什么這么說呢闷盔？
  • 在它之前，GC線程和用戶線程是無法同時工作的旅急，即使是Parallel Scavenge逢勾，也不過是GC時開啟多個線程并行回收而已，GC的整個過程依然要暫停用戶線程藐吮，即Stop The World溺拱。這帶來的后果就是Java程序運(yùn)行一段時間就會卡頓一會，降低應(yīng)用的響應(yīng)速度谣辞，這對于運(yùn)行在服務(wù)端的程序是不能被接收的迫摔。

• CMS過程圖大家都很熟悉，但是對于他如何實(shí)現(xiàn)并發(fā)你真的了解嗎泥从？

  
  
  cms_process.png
  
  
  cms_details.png

三色標(biāo)記

• Serial句占、ParNew等垃圾收集器會簡單粗暴的等所有線程進(jìn)行安全點(diǎn)后STW；而CMS躯嫉、G1等垃圾收集器采取了并發(fā)標(biāo)記的策略纱烘；
  • 在并發(fā)標(biāo)記的過程中，對象間的引用關(guān)系也一直在發(fā)生改變：如原本與GCRoots存在間接引用的節(jié)點(diǎn)在并發(fā)標(biāo)記過程中斷連了祈餐，而這會產(chǎn)生并發(fā)的問題擂啥，如何解決？使用三色標(biāo)記算法進(jìn)行分析;

• 三色標(biāo)記帆阳，即通過不同的顏色標(biāo)記處于不同標(biāo)記狀態(tài)的對象

  
  
  three_color.png

漏標(biāo)

• 對于一個本來不應(yīng)該被回收的對象哺壶，卻被標(biāo)記成白色；

public class ThreeColorRemark {

    private static A a ;
    public static void main(String[] args) {
        creatClassA();
        //并發(fā)標(biāo)記
        a.d = a.b.d ;
        a.b.d = null ;
    }
    private static void creatClassA() {
        a = new A();
        return; //安全點(diǎn)
    }
}
class A{
    B b = new B();
    D d = null;
}
class B{
    C c = new C();
    D d = new D();
}
class C{}
class D{}

three_color_missing.png

• 對于以上黑色指向了未被標(biāo)記的白色蜒谤，將會導(dǎo)致白色對象不會再被掃描到而漏標(biāo)变骡，運(yùn)行時會導(dǎo)致空指針；CMS時如何避免呢芭逝？

  
  
  more_miss_type.png

增量更新

• 通過破壞第一條規(guī)則實(shí)現(xiàn)：依靠寫屏障

  
  
  incremental_update.jpg

寫屏障write barrier

• 給某個對象的成員變量賦值前后加入一些處理，類似于AOP. C++源碼

/**
 * @param field ：某對象的屬性 a.b.d
 * @param new_value :新值 如null
 */
void oop_field_store(oop* field , oop new_value){
    pre_write_barrier(field);  //寫屏障 --- 寫前屏障（G1使用）
    *field = new_value ; //賦值操作
    post_write_barrier(field , value); //寫屏障---寫后屏障（CMS使用）
}

//c++ 源碼
template <class T> inline void oop_store(volatile T* p, oop v) {
  update_barrier_set_pre((T*)p, v);   // cast away volatile  寫前屏障
  // Used by release_obj_field_put, so use release_store_ptr.
  oopDesc::release_encode_store_heap_oop(p, v);
  // When using CMS we must mark the card corresponding to p as dirty
  // with release sematics to prevent that CMS sees the dirty card but
  // not the new value v at p due to reordering of the two
  // stores. Note that CMS has a concurrent precleaning phase, where
  // it reads the card table while the Java threads are running.
  update_barrier_set((void*)p, v, true /* release */);    // cast away type 寫后屏障
}

inline void update_barrier_set(void* p, oop v, bool release = false) {
  assert(oopDesc::bs() != NULL, "Uninitialized bs in oop!");
  oopDesc::bs()->write_ref_field(p, v, release);
}

template <class T> inline void update_barrier_set_pre(T* p, oop v) {
  oopDesc::bs()->write_ref_field_pre(p, v);
}

寫屏障實(shí)現(xiàn)增量更新

• 當(dāng)對象A的成員變量的引用發(fā)生變化時渊胸，比如新增引用（a.d = D）,利用寫后屏障將A新的成員變量引用對象D記錄下來（先賦值旬盯，在收集引用）

//CMS 增量更新使用
void post_write_barrier(oop* field , oop new_value){
    remark_set.add(new_value); //記錄新引用的對象
}

• 為何CMS使用寫后屏障，G1使用寫前屏障翎猛？上方三色標(biāo)級的原理相關(guān)胖翰，CMS是將對象重新引用時標(biāo)記，在附值后切厘；G1在對象附值前保存引用關(guān)系萨咳，因此使用寫前屏障；

寫屏障實(shí)現(xiàn)SATB

• 當(dāng)對象B的成員變量的引用發(fā)生變化時疫稿，比如新增引用（b.d = null）,利用寫前屏障將B舊的成員變量引用對象D記錄下來（先收集引用培他，后賦值）

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

• 有興趣同學(xué)可以查看Hotspot實(shí)現(xiàn)類： 存放到子Thread的內(nèi)存隊列中鹃两，避免對當(dāng)前寫操作產(chǎn)生影響；

void G1SATBCardTableModRefBS::enqueue(oop pre_val) {
  // Nulls should have been already filtered.
  assert(pre_val->is_oop(true), "Error");

  if (!JavaThread::satb_mark_queue_set().is_active()) return;
  Thread* thr = Thread::current();
  if (thr->is_Java_thread()) {
    JavaThread* jt = (JavaThread*)thr;
    jt->satb_mark_queue().enqueue(pre_val);  //JavaThread中satb隊列中入隊原來舊值
  } else {
    MutexLockerEx x(Shared_SATB_Q_lock, Mutex::_no_safepoint_check_flag);
    JavaThread::satb_mark_queue_set().shared_satb_queue()->enqueue(pre_val);
  }
}

跨代引用問題

• 對于跨代引用舀凛，比如minor GC/younger GC 遇到老年代引用年輕代對象俊扳，如果每次都掃描老年代效率太低了，如何提效呢猛遍？

記錄集

• 在新生代中可以開辟一塊空間馋记，引入記錄集（Remember Set）的數(shù)據(jù)結(jié)構(gòu)（記錄從非收集區(qū)到收集區(qū)的指針集合），由于以上分析跨代引用相對比較少懊烤，因此記錄集的數(shù)據(jù)有限梯醒，不會特別大；

• 分類：

  1. 字長精度：每個記錄精確到一個機(jī)器字長(就是處理器的尋址位數(shù)腌紧，如常見的32位或64位茸习，這個 精度決定了機(jī)器訪問物理內(nèi)存地址的指針長度)，該字包含跨代指針寄啼。

  2. 對象精度:每個記錄精確到對象逮光，該對象里有字段含跨代指針。

  3. 卡精度:每個記錄精確到一塊內(nèi)存區(qū)域墩划，該內(nèi)存區(qū)域有對象含有跨代指針涕刚。

  • HotSpot JVM置谦，使用了卡標(biāo)記（Card Marking）技術(shù)來解決老年代到新生代的引用問題盛撑。具體是，使用卡表（Card Table）和寫屏障（Write Barrier）來進(jìn)行標(biāo)記并加快對GC Roots的掃描

卡表Card table

• 記憶集是一種抽象的數(shù)據(jù)結(jié)構(gòu)暑塑，卡表是其實(shí)現(xiàn)形式察净，對于上方字長驾茴，對象等會導(dǎo)致隨著對象的增多，記錄集會變得很大氢卡，同時也不易維護(hù)锈至；如何優(yōu)化呢？使用壓縮译秦；

  
  
  card_table_page.png

• 如何維護(hù)卡表呢峡捡？通過寫屏障： 當(dāng)對象的屬性進(jìn)行寫操作時，跨代引用就有可能出現(xiàn)筑悴。所以们拙，我們在這個時候可以檢查是否存在跨代引用；

• 判斷條件分成兩種：

  1. 當(dāng)前老年代屬性賦值時引用了年輕代對象
  2. 原本在年輕代對象minor GC后晉升至老年代阁吝，此時遍歷從這個對象出發(fā)的所有引用判斷是否有年輕代對象

• 若滿足以上兩個條件之一砚婆，就將當(dāng)前card table中對應(yīng)的byte標(biāo)記為1即dirty臟；但是對性能有兩個影響

  1. 無條件寫屏障帶來的性能開銷：虛擬機(jī)會為所有的賦值操作生成相應(yīng)的指令突勇，每次只要對引用進(jìn)行了賦值操作装盯，就會判斷是否需要更新卡表坷虑，從而產(chǎn)生額外的開銷，不過這個開銷與MinorGC時掃描整個老年代的代價要低的多验夯；
  2. 高并發(fā)下虛共享帶來的性能開銷猖吴，偽共享； CPU緩存行一般為64字節(jié)挥转，對應(yīng)卡頁為64*512bytes = 32kb海蔽，不同線程對對象引用的更新操作，恰好位于同一個32KB區(qū)域內(nèi)绑谣，則將會帶來同步性能問題

• 優(yōu)化：先檢查當(dāng)前卡表標(biāo)記党窜，只有當(dāng)該卡表項未被標(biāo)記過才將其標(biāo)記為dirty

  
  
  card-table-dirty.png
  
  
  image.png

• 老年代引用年輕代使用卡表標(biāo)記，且只有唯一一份借宵；反過來不需要處理年輕代引用老年代幌衣，Why?

  • 由于新生代對象具有朝生夕滅的不穩(wěn)定性，引用變化頻繁壤玫，能省下這個區(qū)域維護(hù)開銷非常劃算豁护，代價就是當(dāng)CMS發(fā)生old GC時（針對老年代Old GC）而是將整個年輕代作為GC Root來進(jìn)行掃描;

• 為何使用byte數(shù)組而不是bit位表示卡表：主要是速度上的考量，現(xiàn)代計算機(jī)硬件都是最小按字節(jié)尋址的欲间， 沒有直接存儲一個bit的指令楚里，所以要用bit的話就不得不多消耗幾條shift+mask指令

3、G1算法

1. 既然已經(jīng)有了幾個強(qiáng)大的GC猎贴，為什么還要發(fā)布G1 GC班缎？

隨著應(yīng)用程序的業(yè)務(wù)邏輯越來越龐大、復(fù)雜她渴，用戶訪問也越來越多达址，沒有 GC 就不能保證應(yīng)用程序正常運(yùn)行，而經(jīng)常 STW 的 GC 方案又跟不上實(shí)際的應(yīng)用需求趁耗，所以需要不斷嘗試對 GC 進(jìn)行優(yōu)化沉唠。G1 GC 的目標(biāo)就是為了適應(yīng)現(xiàn)在不斷擴(kuò)大的內(nèi)存和不斷增加的處理器數(shù)量，進(jìn)一步降低 GC 暫停時間苛败，同時兼顧良好的吞吐量右冻。

2. G1 GC 是什么？

官網(wǎng)上對G1 GC 的描述如下：

The Garbage-First (G1) collector is a server-style garbage collector, targeted for multi-processor machines with large memories. It meets garbage collection (GC) pause time goals with a high probability, while achieving high throughput. The G1 garbage collector is fully supported in Oracle JDK 7 update 4 and later releases. The G1 collector is designed for applications that:

* Can operate concurrently with applications threads like the CMS collector.
* Compact free space without lengthy GC induced pause times.
* Need more predictable GC pause durations.
* Do not want to sacrifice a lot of throughput performance.
* Do not require a much larger Java heap.

G1是一種服務(wù)器端的垃圾收集器著拭，應(yīng)用在多處理器和大容量內(nèi)存環(huán)境中，在實(shí)現(xiàn)高吞吐量的同時牍帚，盡可能的滿足垃圾收集對暫停時間的要求儡遮。它是專門針對以下應(yīng)用場景而設(shè)計的:

• 像CMS收集器一樣，能與應(yīng)用程序線程并發(fā)執(zhí)行
• 整理空閑空間更快
• 需要GC停頓時間更好預(yù)測
• 不希望犧牲大量的吞吐性能
• 不需要更大的Java Heap

3. G1 的支持版本是什么暗赶？

在JDK1.7版本中正式啟用 G1鄙币，移除了 Experimental 的標(biāo)識肃叶，JDK 9以后 G1 是默認(rèn)的垃圾回收器，取代了 CMS 回收器以及 Parallel + Parallel 0ld 組合十嘿。G1 被Oracle官方稱為“全功能的垃圾收集器”因惭。

4. G1 中的重要概念和原理有哪些？

在 G1 的實(shí)現(xiàn)中引入了一些新的概念和算法绩衷，來實(shí)現(xiàn) GC 的高吞吐量蹦魔、低內(nèi)存碎片、可預(yù)測的停頓時間等目標(biāo)咳燕。

Region

傳統(tǒng)的 GC 將內(nèi)存空間劃分為新生代勿决、老年代和永久代（JDK 8 中去除了永久代，引入了元空間）招盲，各代的內(nèi)存地址是連續(xù)的低缩。

2021-12-27-22-33-53.png

G1 也是分代的垃圾回收算法，不過 G1 的老年代和年輕代的存儲地址是不連續(xù)的曹货，每一代都使用了n個不連續(xù)的大小相同的Region咆繁，每個Region占有一塊連續(xù)的虛擬內(nèi)存地址。這就是 G1 引入的分區(qū)的概念顶籽，Region 的類型有 Eden玩般、Survivor、Old蜕衡、Humongous 四種壤短，而且每個 Region 都可以單獨(dú)進(jìn)行管理。

2021-12-28-10-29-04.png

其中 Humongous 是用來存放大對象的慨仿，如果一個對象的大小大于一個 Region 的 50%（默認(rèn)值）久脯，那么我們就認(rèn)為這個對象是一個大對象。為了防止大對象的頻繁拷貝镰吆，我們可以將大對象直接放到 Humongous 中帘撰。

H-obj有如下幾個特征：

• H-obj直接分配到了老年代，防止了大對象的反復(fù)拷貝移動
• H-obj在全局并發(fā)標(biāo)記階段的cleanup 和 full GC階段回收
• 在分配H-obj之前先檢查是否超過 initiating heap occupancy percent和the marking threshold, 如果超過的話万皿，就啟動global concurrent marking摧找，為的是提早回收，防止 evacuation failures 和 full GC牢硅。

一個Region的大小可以通過參數(shù)-XX:G1HeapRegionSize設(shè)定蹬耘，取值范圍從1M到32M，且是2的指數(shù)减余。如果不設(shè)定综苔，那么G1會根據(jù)Heap大小自動決定。

SATB

SATB 的英文全稱是 Snapshot-At-The-Beginning，其字面意思是 GC 開始時活著的對象的一個快照如筛。根據(jù)前面介紹的三色標(biāo)記算法堡牡，發(fā)生白對象漏標(biāo)有兩個前提條件：

1. Mutator賦予一個黑對象該白對象的引用
2. Mutator刪除了所有從灰對象到該白對象的直接或者間接引用

對于第一個條件，在并發(fā)標(biāo)記階段杨刨，如果該白對象是new出來的晤柄，并沒有被灰對象持有，那么它會不會被漏標(biāo)呢妖胀？

2021-12-28-16-05-21.png

每個Region中有兩個標(biāo)記位圖：next和 prev芥颈，next 是本次標(biāo)記的標(biāo) 記位圖，而 prev 是上次標(biāo)記的標(biāo)記位圖做粤，保存了上次標(biāo)記的結(jié)果浇借。上圖中的 bottom 表示 Region 內(nèi)眾多對象的末尾，top 表示開頭怕品。另外有兩個top-at-mark-start（TAMS）指針妇垢，分別為prevTAMS和nextTAMS。nextTAMS 保存了本次標(biāo)記開始時的 top肉康，而 prevTAMS 保存了上次標(biāo)記開始時的 top闯估。在并發(fā)標(biāo)記階段新創(chuàng)建的對象會在 top 之后的區(qū)域分配空間，它將直接被標(biāo)記為黑色吼和，這是一種隱式的標(biāo)記涨薪。所以并發(fā)標(biāo)記階段新生成的對象不會被漏標(biāo)。

而對于在GC時已經(jīng)存在的白對象炫乓，如果它是活著的刚夺，它必然會被另一個對象引用，即條件二中的灰對象末捣。如果灰對象到白對象的直接引用或者間接引用被替換了侠姑，或者刪除了，那個白對象就會被漏標(biāo)箩做，從而導(dǎo)致被回收掉莽红，這是非常嚴(yán)重的錯誤。

在 CMS GC 算法中解決白對象漏標(biāo)問題采用了寫屏障技術(shù)邦邦，當(dāng) B 對象對 C 對象的引用消失時安吁，C 對象將會被標(biāo)記為灰色。這個動作的效率是比較低的燃辖，如果都放在寫屏障中做鬼店，會極大地影響程序性能，因?yàn)閷懫琳系倪壿嬍怯蓸I(yè)務(wù)線程執(zhí)行的黔龟。

為了解決寫屏障的性能問題薪韩，G1 將“C 對象標(biāo)記為灰色”這件事情往后推遲了确沸。業(yè)務(wù)線程只需要把 C 對象記錄到一個本地隊列中就可以了。每個業(yè)務(wù)線程都有一個這樣的線程本地隊列俘陷，它的名字是 SATB 隊列。SATB 專用寫屏障的偽代碼如下所示：

1: def satb_write_barrier(field, newobj): 
2:      if $gc_phase == GC_CONCURRENT_MARK: 
3:          oldobj = *field 
4:          if oldobj != Null: 
5:              enqueue($current_thread.stab_local_queue, oldobj) 
6:
7:          *field = newobj

參數(shù) field 表示被寫入對象的域观谦，參數(shù) newobj 表示被寫入域的值拉盾。第 2 行的 GC_CONCURRENT_MARK 用來表示并發(fā)標(biāo)記階段的標(biāo)志位（flag）。第 4 行會檢查當(dāng)前是否處于并發(fā)標(biāo)記階段且被寫入之前 field 域的值是不是 Null豁状。如果檢查通過捉偏，則在第 5 行將 oldobj 添加到 $current_thread.stab_local_queue 中。然后泻红，在第 7 行進(jìn)行 實(shí)際的寫入操作夭禽。這個算法沒有對 oldobj 進(jìn)行任何標(biāo)記處理。

上述SATB 寫屏障的實(shí)現(xiàn)考慮了多線程環(huán)境的執(zhí)行谊路，第 5 行 $current_thread.stab_local_queue 是 mutator 各自持有的 線程本地隊列讹躯，而非全局的隊列，因此在執(zhí)行 enqueue() 時不用擔(dān)心 線程之間會發(fā)生資源競爭缠劝。 如下圖每個線程有自己的本地 SATB 隊列潮梯，當(dāng)本地隊列滿了之后，就把它交給 SATB 隊列集合惨恭，然后再領(lǐng)取一個空隊列當(dāng)做線程的本地 SATB 隊列秉馏。GC 線程則會將 SATB 隊列集合中的對象標(biāo)記為灰色，至于什么時候標(biāo)記脱羡，并不需要業(yè)務(wù)線程關(guān)心萝究。

2021-12-28-16-46-10.png

在并發(fā)標(biāo)記階段，GC 線程會定期檢查 SATB 隊列集合的大小锉罐。如果發(fā) 現(xiàn)其中有隊列帆竹，則會對隊列中的全部對象進(jìn)行標(biāo)記和掃描。前面已經(jīng)講 過氓鄙，SATB 專用寫屏障并不檢查目標(biāo)對象是否被標(biāo)記馆揉，因此隊列中可能存在已經(jīng)被標(biāo)記的對象，已經(jīng)被標(biāo)記的對象也不會再次被標(biāo)記和掃描抖拦。

Collection Set

G1 的垃圾回收模式有兩種：分別是 young GC 和 mixed GC升酣。

• young GC：只回收年輕代的 Region
• mixed GC：回收全部的年輕代 Region，并回收部分老年代的 Region态罪。

無論是 young GC 還是 mixed GC噩茄，都會回收全部的年輕代，mixed GC 回收的老年代 Region 是需要進(jìn)行決策的（Humongous 在回收時也是當(dāng)做老年代的 Region 處理的）复颈。mixed GC 中選取的老年代對象 Region 的集合稱之為回收集合（Collection Set绩聘，CSet）沥割，那么決定老年代 Region 是否被回收的因素具體有哪些呢？

CSet 的選取要素有以下兩點(diǎn)：

1. 該 Region 的垃圾占比凿菩。垃圾占比越高的 Region机杜，被放入 CSet 的優(yōu)先級就越高，這就是垃圾優(yōu)先策略（Garbage First）衅谷，也是 G1 GC 名稱的由來椒拗。
2. 建議的暫停時間。建議的暫停時間由 -XX:MaxGCPauseMillis 指定获黔，G1 會根據(jù)這個值來選擇合適數(shù)量的老年代 Region蚀苛。

MaxGCPauseMillis 默認(rèn)是 200ms，一般不需要進(jìn)行調(diào)整玷氏，如果需要停頓時間更短可以對它進(jìn)行設(shè)置堵未，但是 MaxGCPauseMillis 設(shè)置的越小，選取的老年代 Region 就會越少盏触，如果 GC 壓力居高不下渗蟹，就會觸發(fā) G1 的 Full GC。

Remember Set 和 Card Table

在 CMS GC 中也用到了 Remember Set（RSet） 和 Card Table（卡表）這兩種記錄集數(shù)據(jù)結(jié)構(gòu)耻陕，它們是用于輔助 GC 的結(jié)構(gòu)拙徽，是一種空間換時間的方式。

邏輯上每個 Region 都有一個對應(yīng)的 RSet诗宣，RSet 中記錄了其他 Region 中的對象引用了本 Region 的對象的關(guān)系膘怕，即誰引用了我，這種記錄集被稱為 point-in 類型召庞，而 Card Table 則記錄我引用了誰的對象岛心，被稱為 point-out 類型。

卡表是由元素大小為 1B 的數(shù)組實(shí)現(xiàn)的篮灼，卡表里的元素稱為卡片忘古。堆中大小適當(dāng)?shù)囊欢未鎯臻g會對應(yīng)卡表中的 1 個元素（卡片）。比如在某個版本 JDK 中诅诱，這個大小被定為 512B髓堪，當(dāng)堆的大小是 1GB 時，可以計算出卡表的大小就是 2MB娘荡。G1 的 RSet 是在卡表的基礎(chǔ)上實(shí)現(xiàn)的：每個 Region 會記錄下別的 Region 有指向自己的指針干旁，并標(biāo)記這些指針分別在哪些 Card 的范圍內(nèi)。 這個RSet其實(shí)是一個哈希表炮沐，Key是別的 Region 的起始地址争群，Value 是一個集合，里面的元素是卡表的 Index大年。

2021-12-29-16-00-31.png

上面圖中表示了RSet换薄、Card和Region的關(guān)系玉雾，每個Region被分成了多個Card，在不同Region中的Card會相互引用轻要，Region1 和 Region3 中的 Card 中的對象引用了 Region2 中的 Card 中的對象复旬，藍(lán)色實(shí)線表示的就是 point-out 的關(guān)系，而在 Region2 的 RSet 中冲泥，記錄了 Region1 和 Region3 的 Card赢底，即紅色虛線表示的關(guān)系，這就是point-in柏蘑。

G1 如何維護(hù)跨區(qū)引用

每個 Region 的專屬 RSet 中記錄了其他 Region 的對象對本 Region 中對象的引用關(guān)系，那么有哪些引用關(guān)系需要加入 RSet 中呢粹庞？

1. 同一個 Region 中的對象之間的相互引用是不必維護(hù)的咳焚，因?yàn)椴淮嬖诳?Region 的問題；
2. 由年輕代 Region 出發(fā)到其他 Region 的庞溜，無論目標(biāo)是年輕代還是老年代革半，這一類引用也都不用維護(hù)。因?yàn)榻Y(jié)合 young GC 和 mixed GC 的策略可以知道流码，無論是什么回收模式又官，年輕代的全部 Region 都會被清理，這就意味著一定會對年輕代的所有對象進(jìn)行遍歷漫试；
3. 從 CSet 集合的 Region 出發(fā)指向其他 Region 的六敬，也不需要維護(hù)，理由和第 2 點(diǎn)是一樣的驾荣。

因此外构，RSet 需要維護(hù)的引用關(guān)系只有兩種：

• 非 CSet 老年代 Region 到年輕代 Region 的引用
• 非 CSet 老年代 Region 到 CSet 老年代 Region 的引用

RSet 中記錄的也是 Card，根據(jù)上面的條件記錄到 RSet 中的 Card 稱為 Dirty Card播掷。和 SATB 相似审编，業(yè)務(wù)線程也不是直接將 dirty card 放到 RSet 中的，而是在業(yè)務(wù)線程中引入一個叫做 dirty card queue（DCQ）的隊列歧匈，在寫屏障中垒酬，業(yè)務(wù)線程只需要將 dirty card 放入 DCQ 中，而不做非常細(xì)致的檢查件炉。然后勘究，在 GC 線程中有一類叫 Refine 線程，它們會從 DCQ 中找到這種 dirty card妻率，然后再去做更精細(xì)的檢查乱顾，只有確實(shí)不屬于上面所描述的三種情況的跨區(qū)引用，才真正放到專屬 RSet 中去宫静。

停頓預(yù)測模型

G1 GC是一個響應(yīng)時間優(yōu)先的 GC 算法走净，它與 CMS 最大的不同是券时，用戶可以設(shè)置整個 GC 過程的期望停頓時間，通過參數(shù) -XX:MaxGCPauseMillis 指定一個 G1 收集過程目標(biāo)停頓時間伏伯，默認(rèn)值200ms橘洞，它不是硬性條件，只是期望值说搅。那么G1怎么滿足用戶的期望呢炸枣？就需要這個停頓預(yù)測模型了。G1根據(jù)這個模型統(tǒng)計計算出來的歷史數(shù)據(jù)來預(yù)測本次收集需要選擇的Region數(shù)量弄唧，從而盡量滿足用戶設(shè)定的目標(biāo)停頓時間适肠。停頓預(yù)測模型是根據(jù)衰減標(biāo)準(zhǔn)偏差實(shí)現(xiàn)的：

//  share/vm/gc_implementation/g1/g1CollectorPolicy.hpp
double get_new_prediction(TruncatedSeq* seq) {
    return MAX2(seq->davg() + sigma() * seq->dsd(),
                seq->davg() * confidence_factor(seq->num()));
}

在這個預(yù)測計算公式中：davg 表示衰減均值，sigma()返回一個系數(shù)候引，表示信賴度侯养，dsd 表示衰減標(biāo)準(zhǔn)偏差，confidence_factor 表示可信度相關(guān)系數(shù)澄干。而方法的參數(shù) TruncateSeq逛揩，表示一個截斷的序列，它只跟蹤了序列中的最新的 n 個元素麸俘。在G1 GC過程中辩稽，每個可測量的步驟花費(fèi)的時間都會記錄到TruncateSeq（繼承了AbsSeq）中，用來計算衰減均值从媚、衰減變量逞泄，衰減標(biāo)準(zhǔn)偏差等。

思考

1. 為何CMS使用增量更新静檬，G1使用SATB?

• 我的理解：SATB相對增量更新效率會高(當(dāng)然SATB會造成更多的浮動垃圾)炭懊，因?yàn)椴恍枰谥匦聵?biāo)記階段再次深度掃描被刪除引用對象，而CMS對增量引用的根對象會做深度掃描拂檩，G1因?yàn)楹芏鄬ο蠖嘉挥诓煌膔egion侮腹，CMS就一塊老年代區(qū)域，重新深度掃描對象的話G1的代價會比CMS高稻励，所以G1選擇SATB不深度掃描對象父阻，只是簡單標(biāo)記，等到下一輪GC再深度掃描望抽。
  • 原始快照只是簡單把要可能消失的對象標(biāo)記為黑色對象加矛，這樣有可能會產(chǎn)生浮動垃圾，而增量更新會把新增的引用關(guān)系都重新掃描一遍煤篙，在重新標(biāo)記階段不會產(chǎn)生浮動垃圾斟览；
  • 原始快照速度快，增量更新速度慢辑奈；

2. G1有哪些優(yōu)化點(diǎn)苛茂？

• 由于G1在回收region時需要復(fù)制移動對象已烤，此時需要STW，雖然可以并行處理但對于回收超大內(nèi)存時性能依然有影響妓羊，該如何優(yōu)化呢胯究，Shenandoah GC在回收時可以做到幾乎并發(fā)（GC Root直接引用對象仍需要STW，但這跟堆大小無關(guān)躁绸，只與程序當(dāng)前棧幀大小相關(guān)）裕循，若你有興趣可以了解最前沿的GC垃圾回收器；

Refers To

Getting Started with the G1 Garbage Collector

Tips for Tuning the Garbage First Garbage Collector