垃圾回收（3）G1的結構和概念

G1介紹

G1（Garbage First）算法，通過參數-XX:+UseG1GC來啟用，該算法在JDK 7u4版本被正式推出,G1可以通過參數-XX:MaxGCPauseMillis控制GC暫停時間。

Region

在G1算法中，采用了另外一種完全不同的方式組織堆內存，堆內存被劃分為多個大小相等的內存塊（Region），每個Region是邏輯連續的一段內存，結構如下：

每個Region被標記了E、S、O和H，說明每個Region在運行時都充當了一種角色，其中H是以往算法中沒有的，它代表Humongous，這表示這些Region存儲的是巨型對象（humongous object，H-obj），當新建對象大小超過Region大小一半時，直接在新的一個或多個連續Region中分配，并標記為H。

堆內存中一個Region的大小可以通過-XX:G1HeapRegionSize參數指定，大小區間只能是1M、2M、4M、8M、16M和32M，總之是2的冪次方，默認把堆內存按照2048份均分，也就是默認2048個Region。比如-Xmx16g -Xms16g，G1就會采用16G / 2048 = 8M 的Region。

GC模式

G1中提供了三種模式垃圾回收模式，Young gc、Mixed gc 和 Full gc，在不同的條件下被觸發。

1、Young gc

發生在年輕代的GC算法，一般對象（除了巨型對象）都是在eden region中分配內存，當所有eden region被耗盡無法申請內存時，就會觸發一次young gc，這種觸發機制和之前的young gc差不多，執行完一次young gc，活躍對象會被拷貝到survivor region或者晉升到old region中。
年輕代，默認占用堆大小由以下參數控制：

2、Mixed gc

當越來越多的對象晉升到老年代old region時，為了避免堆內存被耗盡，虛擬機會觸發一個混合的垃圾收集器，即mixed gc，該算法并不是一個old gc，除了回收整個young region，還會回收一部分的old region，這里需要注意：是一部分老年代，而不是全部老年代，可以選擇哪些old region進行收集，一般是選擇回收效益最高的，也就是垃圾最多的region，從而可以對垃圾回收的耗時時間進行控制。

mixed gc中也有一個閾值參數 -XX:InitiatingHeapOccupancyPercent，當老年代大小占整個堆大小百分比達到該閾值時，會觸發一次mixed gc.

3、Full gc

如果對象內存分配速度過快，mixed gc來不及回收，導致老年代被填滿，就會觸發一次full gc，G1的full gc算法就是單線程執行的serial old gc，會導致異常長時間的暫停時間，需要進行不斷的調優，盡可能的避免full gc.

G1中的數據結構

1、TLAB（線程本地分配緩沖區Thread Local Allocation Buffer）

由于堆內存是應用程序共享的，應用程序的多個線程在分配內存的時候需要加鎖以進行同步。為了避免加鎖，提高性能每一個應用程序的線程會被分配一個TLAB。TLAB中的內存來自于G1年輕代中的內存分段。當對象不是Humongous對象，TLAB也能裝的下的時候，對象會被優先分配于創建此對象的線程的TLAB中。這樣分配會很快，因為TLAB隸屬于線程，所以不需要加鎖。當TLAB的剩余空間不滿足分配需求，則重新申請一塊TLAB空間。

2、Card (卡表)

1、很小的內存區域，G1將Java堆劃分為相等大小的一個個區域，這個小的區域大小是512 Byte，稱為Card
2、Card Table維護著所有的Card。Card Table的結構是一個字節數組，Card Table用這個數組映射著每一個Card
3、Card中對象的引用發生改變時，Card在Card Table數組中對應的值被標記為dirty，就稱這個Card被臟化了
4、分配對象會占用物理上連續若干個卡片

3、Rset(已記憶集合)

1、每個Region初始化時，會初始化一個remembered set
2、RSet里面記錄了引用——就是其他Region中指向本Region中所有對象的所有引用，也就是誰引用了我的對象即RSet需要記錄的東西應該是 xx Region的 xx Card。
3、RSet其實是一個Hash Table，Key是其他的Region的起始地址，Value是一個集合，里面的元素是Card Table 數組中的index，既Card對應的Index，映射到對象的Card地址。

Region1和Region3中有對象引用了Region2的對象，則在Region2的Rset中記錄了這些引用。

Rset實現過程

為了維護這些RSet，如果每次給引用類型的字段賦值都要更新RSet，這帶來的額外開銷實在太大，G1中采用post-write barrier（寫后柵欄）和concurrent refinement threads（并發后臺線程）實現了RSet的更新。

//假設對象young和old分別在不同的Region中
Object young = new Object();
old.p = young;

Java層面給old對象的p字段賦值young對象的前后，JVM會插入一個pre-write barrier（寫前柵欄）和post-write barrier（寫后柵欄）。

1、寫前柵欄 Pre-Write Barrrier：即將執行一段賦值語句時，等式左側對象將修改引用到另一個對象，那么JVM就需要在賦值語句生效之前，記錄喪失引用的對象。
2、寫后柵欄 Post-Write Barrrier：當執行一段賦值語句后，等式右側對象獲取了左側對象的引用，同樣需要記錄

其中post-write barrier的最終動作如下：
1、找到該字段所在的位置(Card)，并設置為dirty_card
2、如果當前是應用線程，每個Java線程有一個dirty card queue，把該card插入隊列
3、除了每個線程自帶的dirty card queue，還有一個全局共享的queue

賦值動作到此結束，接下來的RSet更新操作交由多個ConcurrentG1RefineThread并發完成，每當全局隊列集合超過一定閾值后，ConcurrentG1RefineThread會取出若干個隊列，遍歷每個隊列中記錄的card，并進行處理，邏輯如下：

1、根據card的地址，計算出card所在的Region
2、如果Region不存在，或者Region是Young區，或者該Region在回收集合（CSet）中，則不進行處理
3、處理該card中的對象，將應用關系寫入Rset中。

RSet有什么好處？
進行垃圾回收時，如果Region1有根對象A引用了Region2的對象B，顯然對象B是活的，如果沒有Rset，就需要掃描整個Region1或者其它Region，才能確定對象B是活躍的，有了Rset可以避免對整個堆進行掃描。

4、CSet（回收集合Collection Set）

1、它記錄了GC要收集的Regions集合
2、在任意一次收集暫停中，CSet所有分區都會被釋放，內部存活的對象都會被轉移到分配的空閑Region中。
3、CSet包括需要收集的Eden Regions、Survivor Regions，而且還包括部分(1/8)Old Regions（混合收集的時候，收集年輕代的時候，會收集一部分老年代的Region）。

5、SATB(snapshot-at-the-beginning)

為了解決在并發標記過程中，存活對象漏標的情況，GC HandBook把對象分成三種顏色：

1、黑色：自身以及可達對象都已經被標記
2、灰色：自身被標記，可達對象還未標記
3、白色：還未被標記

所以，漏標的情況只會發生在白色對象中，且滿足以下任意一個條件：

1、并發標記時，應用線程給一個黑色對象的引用類型字段賦值了該白色對象
2、并發標記時，應用線程刪除所有灰色對象到該白色對象的引用

對于第一種情況，利用post-write barrier，記錄所有新增的引用關系，然后根據這些引用關系為根重新掃描一遍
對于第二種情況，利用pre-write barrier，將所有即將被刪除的引用關系的舊引用記錄下來，最后以這些舊引用為根重新掃描一遍

1、SATB的概念

1、SATB是增量式標記清除垃圾收集器設計的一個標記算法。
2、SATB的標記優化主要針對標記-清除垃圾收集器的并發標記階段。
3、CMS的i設計使得它在remark階段必須重新掃描所有線程棧和整個young gen作為root。G1的SATB設計在remark階段則只需要掃描剩下的satb_mark_queue。

2、SATB的作用

1、SATB保證了在并發標記過程中新分配對象不會漏標。
2、SATB中的stab_mark_queue，在引用關系發生變化時，利用pre-write barrier，把原引用保存到stab_mark_queue中，每個應用線程都有一個stab_mark_queue。

總結

SATB的算法，每個region有5個指針，比較復雜，沒有找到太好的文章，沒有太理解，還有待進一步了解~~~