cms垃圾回收演算法

㈠ JVM垃圾回收的「三色標記演算法」實現，內容太干

三色標記法是一種垃圾回收法，它可以讓JVM不發生或僅短時間發生STW(Stop The World)，從而達到清除JVM內存垃圾的目的。JVM中的 CMS、G1垃圾回收器 所使用垃圾回收演算法即為三色標記法。

三色標記法將對象的顏色分為了黑、灰、白，三種顏色。

白色 ：該對象沒有被標記過。（對象垃圾）

灰色 ：該對象已經被標記過了，但該對象下的屬性沒有全被標記完。（GC需要從此對象中去尋找垃圾）

黑色 ：該對象已經被標記過了，且該對象下的屬性也全部都被標記過了。（程序所需要的對象）

從我們main方法的根對象（JVM中稱為GC Root）開始沿著他們的對象向下查找，用黑灰白的規則，標記出所有跟GC Root相連接的對象,掃描一遍結束後，一般需要進行一次短暫的STW(Stop The World)，再次進行掃描，此時因為黑色對象的屬性都也已經被標記過了，所以只需找出灰色對象並順著繼續往下標記（且因為大部分的標記工作已經在第一次並發的時候發生了，所以灰色對象數量會很少，標記時間也會短很多）, 此時程序繼續執行，GC線程掃描所有的內存，找出掃描之後依舊被標記為白色的對象（垃圾）,清除。

具體流程:

在JVM虛擬機中有兩種常見垃圾回收器使用了該演算法：CMS(Concurrent Mark Sweep)、G1(Garbage First) ，為了解決三色標記法對對象漏標問題各自有各自的法:

CMS(Concurrent Mark Sweep)收集器是一種以獲取最短回收停頓時間為目標的收集器。目前很大一部分的Java應用集中在互聯網網站或者基於瀏覽器的B/S系統的服務端上，這類應用通常都會較為關注服務的響應速度，希望系統停頓時間盡可能短，以給用戶帶來良好的交互體驗。CMS收集器就非常符合這類應用的需求(但是實際由於某些問題,很少有使用CMS作為主要垃圾回收器的)。

從名字（包含「Mark Sweep」）上就可以看出CMS收集器是基於標記-清除演算法實現的，它的運作過程相對於前面幾種收集器來說要更復雜一些，整個過程分為四個步驟，包括：1）初始標記（CMS initial mark） 2）並發標記（CMS concurrent mark） 3）重新標記（CMS remark） 4）並發清除（CMS concurrent sweep）

其中初始標記、重新標記這兩個步驟仍然需要「Stop The World」。初始標記僅僅只是標記一下GCRoots能直接關聯到的對象，速度很快；

並發標記階段就是從GC Roots的直接關聯對象開始遍歷整個對象圖的過程，這個過程耗時較長但是不需要停頓用戶線程，可以與垃圾收集線程一起並發運行；

重新標記階段則是為了修正並發標記期間，因用戶程序繼續運作而導致標記產生變動的那一部分對象的標記記錄，這個階段的停頓時間通常會比初始標記階段稍長一些，但也遠比並發標記階段的時間短；

最後是並發清除階段，清理刪除掉標記階段判斷的已經死亡的對象，由於不需要移動存活對象，所以這個階段也是可以與用戶線程同時並發的。由於在整個過程中耗時最長的並發標記和並發清除階段中，垃圾收集器線程都可以與用戶線程一起工作，所以從總體上來說，CMS收集器的內存回收過程是與用戶線程一起並發執行的。

在應對漏標問題時，CMS使用了增量更新(Increment Update)方法來做：

在一個未被標記的對象（白色對象）被重新引用後， 引用它的對象若為黑色則要變成灰色，在下次二次標記時讓GC線程繼續標記它的屬性對象 。

但是就算是這樣，其仍然是存在漏標的問題：

G1(Garbage First)物理內存不再分代，而是由一塊一塊的Region組成,但是邏輯分代仍然存在。G1不再堅持固定大小以及固定數量的分代區域劃分，而是把連續的Java堆劃分為多個大小相等的獨立區域（Region），每一個Region都可以根據需要，扮演新生代的Eden空間、Survivor空間，或者老年代空間。收集器能夠對扮演不同角色的Region採用不同的策略去處理，這樣無論是新創建的對象還是已經存活了一段時間、熬過多次收集的舊對象都能獲取很好的收集效果。

Region中還有一類特殊的Humongous區域，專門用來存儲大對象。G1認為只要大小超過了一個Region容量一半的對象即可判定為大對象。每個Region的大小可以通過參數-XX：G1HeapRegionSize設定，取值范圍為1MB～32MB，且應為2的N次冪。而對於那些超過了整個Region容量的超級大對象，將會被存放在N個連續的Humongous Region之中，G1的大多數行為都把Humongous Region作為老年代的一部分來進行看待，如圖所示

Card Table（多種垃圾回收器均具備）

RSet(Remembered Set)

是輔助GC過程的一種結構，典型的空間換時間工具，和Card Table有些類似。

後面說到的CSet(Collection Set)也是輔助GC的，它記錄了GC要收集的Region集合，集合里的Region可以是任意年代的。

在GC的時候，對於old->young和old->old的跨代對象引用，只要掃描對應的CSet中的RSet即可。邏輯上說每個Region都有一個RSet，RSet記錄了其他Region中的對象引用本Region中對象的關系，屬於points-into結構（誰引用了我的對象）。

而Card Table則是一種points-out（我引用了誰的對象）的結構，每個Card 覆蓋一定范圍的Heap（一般為512Bytes）。G1的RSet是在Card Table的基礎上實現的：每個Region會記錄下別的Region有指向自己的指針，並標記這些指針分別在哪些Card的范圍內。這個RSet其實是一個Hash Table，Key是別的Region的起始地址，Value是一個集合，裡面的元素是Card Table的Index。每個Region中都有一個RSet，記錄其他Region到本Region的引用信息；使得垃圾回收器不需要掃描整個堆找到誰引用當前分區中的對象，只需要掃描RSet即可。

CSet(Collection Set)

一組可被回收的分區Region的集合, 是多個對象的集合內存區域。

新生代與老年代的比例

5% - 60%，一般不使用手工指定，因為這是G1預測停頓時間的基準,這地方簡要說明一下,G1可以指定一個預期的停頓時間,然後G1會根據你設定的時間來動態調整年輕代的比例,例如時間長,就將年輕代比例調小,讓YGC盡早行。

SATB(Snapshot At The Beginning), 在應對漏標問題時，G1使用了SATB方法來做,具體流程：

因為SATB在重新標記環節只需要去重新掃描那些被推到堆棧中的引用，並配合Rset來判斷當前對象是否被引用來進行回收；

並且在最後G1並不會選擇回收所有垃圾對象，而是根據Region的垃圾多少來判斷與預估回收價值（指回收的垃圾與回收的STW時間的一個預估值），將一個或者多個Region放到CSet中，最後將這些Region中的存活對象壓縮並復制到新的Region中，清空原來的Region。

會，當內存滿了的時候就會進行Full GC；且JDK10之前的Full GC，為單線程的，所以使用G1需要避免Full GC的產生。

解決方案：

㈡ CMS 和G1 的區別

CMS收集器是老年代的收集器，可以配合新生代的Serial和ParNew收集器一起使用
G1收集器收集范圍是老年代和新生代。不需要結合其他收集器使用

CMS收集器以最小的停頓時間為目標的收集器。

G1收集器可預測垃圾回收的停頓時間（建立可預測的停頓時間模型）

CMS收集器是使用「標記-清除」演算法進行的垃圾回收，容易產生內存碎片

G1收集器使用的是「標記-整理」演算法，進行了空間整合，降低了內存空間碎片。

初始標記
並發標記
重新標記
並發清理

初始標記階段：會讓線程全部停止，也就是 Stop the World 狀態
並發標記階段：對所有的對象進行追蹤，這個階段最耗費時。但這個階段是和系統並發運行的，所以不會對系統運行造成影響
重新標記階段：由於第二階段是並發執行的，一邊標記垃圾對象，一邊創建新對象，老對象會變成垃圾對象。 所以第三階段也會進入 Stop the World 狀態，並且重新標記，標記的是第二階段中變動過的少數對象，所以運行速度很快
並發清理階段： 這個階段也是會耗費很多時間，但由於是並發運行的，所以對系統不會造成很大的影響

CMS採用 標記-清理 的演算法，標記出垃圾對象，清除垃圾對象。演算法是基於老年代執行的，因為新生代產生無法接受該演算法產生的碎片垃圾。

優點 ：並發收集，低停頓

不足 ：

G1的出現就是為了替換jdk1.5種出現的CMS,這一點已經在jdk9的時候實現了，jdk9默認使用了G1回收器，移除了所有CMS相關的內容。G1和CMS相比，有幾個特點：

G1把Java內存拆分成多等份，多個域（Region），邏輯上存在新生代和老年代的概念，但是沒有嚴格區分

貼圖感受一下：

依舊存在新生代老年代的概念，但是沒有嚴格區分。Region最多分為2048個

除了上面優點之外，還有一個優點，那就是對大對象的處理。在CMS內存中，如果一個對象過大，進入S1、S2區域的時候大於改分配的區域，對象會直接進入老年代。G1處理大對象時會判斷對象是否大於一個Region大小的50%，如果大於50%就會橫跨多個Region進行存放

初始標記： 標記GC Roots 可以直接關聯的對象，該階段需要線程停頓但是耗時短

並發標記： 尋找存活的對象，可以與其他程序並發執行，耗時較長

最終標記： 並發標記期間用戶程序會導致標記記錄產生變動（好比一個阿姨一邊清理垃圾，另一個人一邊扔垃圾）虛擬機會將這段時間的變化記錄在Remembered Set Logs 中。最終標記階段會向Remembered Set合並並發標記階段的變化。這個階段需要線程停頓，也可以並發執行

篩選回收： 對每個Region的回收成本進行排序，按照用戶自定義的回收時間來制定回收計劃

參考官方文檔：

控制G1回收垃圾的時間

-XX:MaxGCPauseMillis=200 （默認200ms）