本文核心主要是講述：JVM 中的幾種垃圾回收算法理論，以及多種垃圾收集器，并且詳細參數 CMS 垃圾收集器的實現、優缺點等，最后也會解釋一下三色標記法與讀寫屏障。

垃圾收集算法

收集算法.png

分代收集理論 (Generational Collection)

當前商業虛擬機的垃圾收集都是采用 "分代收集" (Generational Collecting)算法，根據對象不同的存活周期將內存劃分為多塊

一般是把 Java 堆分作新生代和老年代, 這樣就可以根據各個年代的特點采用最適當的收集算法，譬如新生代每次GC都有大批量對象死去，只有少量存活， 那就選用復制算法只需要付出少量存活對象的復制成本就可以完成收集。

綜合前面幾種GC算法的優缺點，針對不同生命周期的對象采用不同的GC算法

• 新生代采用 Copying
• 老年代采用 Mark-Sweep or Mark-Compact

標記-復制算法 (Copying)

為了解決效率問題，“復制” 收集算法出現了。他可以將內存分為大小相同的兩塊，每次使用其中一塊。當這塊的內存使用完成后，就將存活的對象復制到另外一邊去，然后再把使用的空間一次清理掉。這樣就使每次的內存回收都是對內存區間的一半進行回收。

標記復制算法.png

標記-清除算法(Mark-Sweep)

算法分為 "標記" 和 "清除" 兩階段，首先標記出所有需要回收的對象，然后回收所有需要回收的對象

缺點

• 效率問題, 標記和清理兩個過程效率都不高
• 空間問題, 標記清理之后會產生大量不連續的內存碎片，空間碎片太多可能會導致后續使用中無法找到足夠的連續內存而提前觸發一次的垃圾收集動作。

標記清除算法.png

標記-整理算法 (Mark-Compact)

• 標記過程仍然一樣，但后續步驟不是進行直接清理，而是令所有存活的對象一端移動，然后直接清理掉這端邊界以外的內存。
• 沒有內存碎片
• 對 Mark-Sweep(標記清除) 耗費更多的時間進行 compact(整理)

標記整理算法.png

垃圾收集器

垃圾收集器.png

如果說垃圾收集算法是內存回收的方法理論，那么垃圾收集器就是內存回收的具體實現。

雖然我們對各收集器進行比較，但并非為了挑選出一個最好的收集器，因為直到現在為止還沒有最好的垃圾收集器出現， 更加沒有萬能的垃圾收集器，我們能做的就是根據具體應用場景選擇適合自己的收集器，試想一下：如果有一個完美無暇的垃圾收集器適用于所有場景，那么我們 Java 虛擬機就不會去實現那么多的垃圾收集器了。

查詢當前使用的 JVM 信息查詢命令 java -XX:+PrintCommandLineFlags -version

?  ~ java -XX:+PrintCommandLineFlags -version
-XX:InitialHeapSize=134217728 -XX:MaxHeapSize=2147483648 -XX:+PrintCommandLineFlags -XX:+UseCompressedClassPointers -XX:+UseCompressedOops -XX:+UseParallelGC 
java version "1.8.0_281"
Java(TM) SE Runtime Environment (build 1.8.0_281-b09)
Java HotSpot(TM) 64-Bit Server VM (build 25.281-b09, mixed mode)

Serial 收集器

單線程收集器，收集時會暫停所有工作線程(Stop The World, 簡稱 STW)，使用復制收集算法，虛擬機運行在 Client 模式的默認新生代收集器

• 最早的收集器，單線程進行GC
• New 和 Old Generation 都可以使用
• 在新生代, 采用復制算法; 在老年代，采用Mark-Compact算法
• 因為使用單線程GC，沒有多線程切換的額外開銷，簡單實用。
• Hotspot Client 模式缺省的收集器
• Safepoint 安全點

JVM 參數：-XX:+UseSerialGC -XX:+UseSerialOldGC

Serial收集器.png

PerNew 收集器

ParNew 收集器就是 Serial 的多線程版本，除了使用多個收集線程外，其余行為包括算法、STW、對象分配規則、回收策略等都與Serial 收集器一模一樣

對應的這種收集器是虛擬機運行在 Server 模式的默認新生代收集器，在單 CPU 的環境下，ParNew 收集器的效果并不會比Serial收集器有更好的效果

• Serial 收集器的在新生代的多線程版本
• 使用復制算法(因為針對新生代)
• 只有在多CPU的環境下，效率才會比Serial收集器高
• 可以通過-XX:ParallelGCThreads來控制GC線程數的多少。需要結合CPU的個數
• Server模式下新生代的缺省收集器。

JVM 參數：-XX:UseParNewGC

ParNew收集器.png

Parallel Scavenge 收集器(1.8 默認)

• Parallel Scavenge 收集器也是一個多線程收集器，也是使用復制算法，但它的對象分配規則與收集策略都與ParNew收集器有所不同，它是以吞吐量最大化(即GC時間占總運行時間最小)為目標的收集器實現，它允許較長的STW換取總吞吐量最大化。
• 默認收集器線程數跟 CPU 核數相同，也可以通過參數指定
• JDK 1.8 默認垃圾收集器
• JVM 參數：`-XX:UseParallelGC(年輕代) -XX:UseParallelOldGC(老年代)

Serial Old 收集器

Serial Old收集器是單線程收集器，使用標記-整理算法，是老年代的收集器

Parallel Old 收集器(1.8 默認)

老年代版本吞吐量優先的收集器，使用多線程和標記-整理算法，JVM 1.6提供，在此之前，新生代使用了PS收集器的話，老年代除Serial Old外別無選擇， 因為PS無法與CMS收集器配合工作。

• Parallel Scavenge 在老年代的實現
• 在 JVM 1.6 才出現 Parallel Old
• 采用多線程，Mark-Compact 算法
• 更注重吞吐量
• Parallel Scavenge + Parallel Old = 高吞吐量，但是GC停頓可能不理想

Parallel Old收集器.png

CMS (Concurrent Mark Sweep) 收集器

CMS 是一種以最短停頓時間為目標的收集器，使用CMS并不能達到GC效率最高(總體GC時間最小)，但它能盡可能降低GC時服務的停頓時間， CMS收集器使用的是標記-清除算法

CMS 收集器.png

CMS 垃圾收集器步驟

CMS 收集器是基于標記-清除算法實現的，它的運作過程相對于前面幾種收集器來說要更復雜一些，整個過程分為四個步驟，包括：

1)初始標記(CMS initial mark) 暫停所有的其他線程(STW)。記錄下 GC ROOT 直接引用對象，速度很快。

2)并發標記(CMS concurrent mark) 并發標記階段就是從 GC ROOT 行的直接關聯對象開始遍歷整個對象的過程，這個過程耗時比較長但是不需要停頓用戶線程，可以與垃圾收集器一起并發運行。因此用戶程序繼續運行，可能會導致已經標記過的對象狀態發生變化。

3)重新標記(CMS remark) 重新標記階段就是為了修正并發標記期間，因為用戶程序繼續運行而導致標記產生變動，的那一部分對象的標記記錄。這個階段的停頓時間一般比初始標記階段的時間稍長，遠遠比并發標記階段時間短。主要是用到三色標記里的增量更新算法

4)**并發清除(CMS concurrent sweep)**開啟用戶線程，同時 GC 線程開始對未標記的區域做清掃，這個階段如果有新增對象會被標記為黑色不做任何處理(見下面三色標記算法詳解)。

CMS 垃圾收集器優缺點

從它的名字可以看出他是一款優秀的垃圾收集器，主要優點：并發收集、低停頓 。但是它有以下幾個明顯的缺點：

• 對于 CPU 資源敏感(會和服務搶資源);
• 無法處理 浮動垃圾(在并發標記和并發清理階段又產生垃圾，這種浮動垃圾只能等到下次 gc 的時候在進行清理了)
• 它使用的收集算法 “標記-清除” 算法 會導致結束時候又大量空間碎片產生，當然通過參數 -XX:UseCMSCompactAtFullCollection 可以讓 JVM 在執行標記清除完成后再做整理。
• 執行過程中的不確定性，會存在一次垃圾回收還沒有執行完成，然后垃圾回收又被觸發的情況，特別是在并發標記和并發清理階段出現，一邊回收，系統一邊運行，也許沒回收完成就再次觸發 Full GC, 這就是 “concurrent mode failure” 此時會進入 stop the world . 用 serial old 垃圾器來回收。

CMS 垃圾收集器的參數

三色標記和讀寫屏障

三色標記算法

提到并發標記，我們不得不了解并發標記的三色標記算法。它是描述追蹤式回收器的一種有效的方法，利用它可以推演回收器的正確性。

因為在并發標記期間應用線程還在繼續跑，對象間的引用可能發生變化，**多標 **和 漏標 的情況還可能發生。

三色標記法.gif

我們將對象分為三種類型：

• 黑色：根對象，或者該對象與它的子對象都被掃描過(對象被標記了，且它的所有field也被標記完了)
• 灰色：對象本身被掃描，還沒有掃描完該對象中的子對象(它的field還沒有被標記或標記完)
• 白色：未被掃描對象，掃描完成所有對象之后，最終為白色的為不可達對象，即垃圾對象(對象沒有被標記到)

三色標記過程

• 第一步，三色標記算法，如果將根對象設置為黑色，那么下級節點的為灰色，再下面的的為白色
• 第二步，灰色掃描完畢后，那么剩下的白色變為灰色
• 第三步，灰色掃描完畢后，那么全部被標記為黑色，不可達的還是為白色

三色標記算法的對象丟失

但是如果在標記過程中，應用程序也進行，那么對象的指針就有可能改變。這樣的話，我們就會遇到一個問題：對象丟失。

例子：

• A.c = C
• B.c = null
• 第一步，初始 Root(黑)-> A(黑) Root(黑)-> B(灰)-> C(白)
• 第二步，在當前場景下執行如下操作

Root(黑)-> A(黑)-> C(白) Root(黑)-> B(黑)

第三步，如果內存回收的時候，就會將 C 回收掉，會導致 C 對象丟失。

SATB 原始快照(Snapshot-At-The-Beginning)

• SATB是維持并發GC的一種手段。G1并發的基礎就是SATB。SATB可以理解成在GC開始之前對堆內存里的對象做一次快照，此時活的對象就認為是活的，從而形成一個對象圖
• 在GC收集的時候，新生代的對象也認為是活的對象，除此之外其他不可達的對象也認為是垃圾對象。
• 如何找到在GC過程分配的對象呢?每個region記錄著兩個top-at-mark-start(TAMS) 指針，分別為prevTAMS 和nextTAMS。在TAMS以上的獨享就是新分配的，因而被視為隱式marked
• 通過這種方式我們就找到了再GC過程中新分配的對象，并把這些對象認為是活的對象。
• 解決了對象在GC過程中分配的問題，呢么GC過程中引用頻繁變化的問題是怎么解決的呢?
• G1給出的解決辦法是通過Write Barrier. Write Barrier 就是堆引用字段進行賦值做了額外處理。通過Write Barrier就可以了解到哪些引用對象發生了什么樣的變化
• mark 的過程就是遍歷heap標記live object的過程，采用的三色標記算法，這三種顏色為white(表示還未訪問到)、gray(訪問到但是它用到的引用還誒有完全掃描)、black (訪問到而且其用到的引用完全掃描完)
• 整個三色標記算法就是從GC Roots出發遍歷heap，針對可達對象先標記white為gray， 然后再標記gray為black; 遍歷完成之后所有可達對象都是black的，所有white 都是可以回收的。
• SATB僅僅對于在marking開始階段進行"snapshot"(marked all reachable at mark start), 但是concurrent 的時候并發修改可能造成對象漏標記

為什 G1 采用 STAB?CMS 使用增量更新?

我的理解：STAB 相對增量更新效率會很高(當然 STAB 可能造成更多的浮動垃圾)，因為不需要重新標記再次深度掃描被刪除引用對象，而 CMS 對增量引用的根對象會做深度掃描， G1 因為很多對象都是位于不同的 region ，CMS 是一塊老年代區域，重新深度掃描對象的話 G1 的代價會比 CMS 高， 所以 G1 選擇 STAB 不深度掃描對象，只是簡單標記， 等到下一輪 GC 再深度掃描。

寫屏障(Write Barrier)

void oop_field_store(oop* field, oop new_value) { 
    *field = new_value; // 賦值操作
}

所謂的寫屏障，其實就是指在賦值操作前后，加入一些處理(可以參考AOP的概念)：

void oop_field_store(oop* field, oop new_value) {  
    pre_write_barrier(field); // 寫屏障-寫前操作
    *field = new_value; 
    post_write_barrier(field, value);  // 寫屏障-寫后操作
}

寫屏障和SATB

當對象E的成員變量的引用發生變化時(objE.fieldG = null;)，我們可以利用寫屏障，將E原來成員變量的引用對象G記錄下來：

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

這種做法的思路是：嘗試保留開始時的對象圖，即原始快照(Snapshot At The Beginning，SATB)，當某個時刻 的GC Roots確定=后，當時的對象圖就已經確定了。比如 當時 D是引用著G的，那后續的標記也應該是按照這個時刻的對象圖走(D引用著G)。如果期間發生變化，則可以記錄起來，保證標記依然按照原本的視圖來。

值得一提的是，掃描所有GC Roots 這個操作(即初始標記)通常是需要STW的，否則有可能永遠都掃不完，因為并發期間可能增加新的GC Roots。

一點小優化：如果不是處于垃圾回收的并發標記階段，或者已經被標記過了，其實是沒必要再記錄了，所以可以加個簡單的判斷:

void pre_write_barrier(oop* field) {
  // 處于GC并發標記階段 且 該對象沒有被標記（訪問）過
  if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) { 
      oop old_value = *field; // 獲取舊值
      remark_set.add(old_value); // 記錄  原來的引用對象
  }
}

寫屏障和增量更新

當對象D的成員變量的引用發生變化時(objD.fieldG = G;)，我們可以利用寫屏障，將D新的成員變量引用對象G記錄下來：

void post_write_barrier(oop* field, oop new_value) {  
  if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
      remark_set.add(new_value); // 記錄新引用的對象
  }
}

這種做法的思路是：不要求保留原始快照，而是針對新增的引用，將其記錄下來等待遍歷，即增量更新(Incremental Update)

讀屏障

oop oop_field_load(oop* field) {
  pre_load_barrier(field); // 讀屏障-讀取前操作
  return *field;
}

讀屏障是直接針對第一步：var G = objE.fieldG;，當讀取成員變量時，一律記錄下來：

void pre_load_barrier(oop* field, oop old_value) {  
  if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
      oop old_value = *field;
      remark_set.add(old_value); // 記錄讀取到的對象
  }
}

現代追蹤式(可達性分析)的垃圾回收器幾乎都借鑒了三色標記的算法思想，盡管實現的方式不盡相同：比如白色/黑色集合一般都不會出現(但是有其他體現顏色的地方)、灰色集合可以通過棧/隊列/緩存日志等方式進行實現、遍歷方式可以是廣度/深度遍歷等等。

對于讀寫屏障，以Java HotSpot VM為例，其并發標記時對漏標的處理方案如下：

• CMS：寫屏障 + 增量更新
• G1：寫屏障 + SATB
• ZGC：讀屏障

漏標-讀寫屏障

漏標會導致被引用的對象被當成垃圾誤刪除，這個是嚴重的 BUG ，有兩種處理方案：增量更新(Incremental Update)和原始快照(Snapshot At The Beginning, STAB)

增量更新 就是當黑色對象插入新的指向白色對象的引用記錄下來，等并發掃描結束之后，再將這些記錄過的引用關系中的黑色對象為根，重新掃描一次。這個可以簡化理解為，黑色對象一旦新插入了指向白色對象的引用之后，它就變回灰色對象了。

原始快照 就當灰色對象要刪除指向白色的對象，將白色對象直接標記為黑色(目的就是讓這種對象在本輪 GC 清理中能夠存活下來，等待下一輪 GC 的時候重新掃描， 這個對象也可能就是浮動垃圾)

以上無論是引用關系記錄的插入還是刪除，虛擬機的記錄操作都是通過 寫屏障 實現的。

記憶集和卡表 (**Remember Set **& Cardtable)

在新生代做 GC Roots 可達性掃描過程中可能會碰到跨代引用的對象 ,這種如果又去對老年代再去掃描效率太低了。為此,在新生代可以引入記錄集 (Remember Set) 的數據結枃 (記錄從非收集區到收集區的指針集合) , 避免把整個老年代加入 GC Roots掃描范圍。事實上并不只是新生代、老年代之間才有跨代引用的問題,所有涉及部分區域收集( Partial GC)行為的垃圾收集器,典型的如G1、ZC和 Shenandoah 收集器,都會面臨相同的問題。

垃圾收集場景中, 收集器只需通過記憶集判斷岀某一塊非收集區域是否存在指向收集區域的指針即可, 無需了解跨代引用指針的全部細節hotspot使用一種叫做 "卡表"( Cardtable )的方式實現記憶集,也是目前最常用的一種方式。關于卡表與記憶集的關系,可以類比為Java語言中 Hashmap與Map的關系卡表是使用一個字節數組實現: CARD TABLE[],每個元素對應著其標識的內存區域一塊特定大小的內存塊,稱為“卡頁”。hotspot使用的卡頁是2^9大小,即512字節

卡表與卡頁.png

一個卡頁中可以包含多個對象，只要有一個對象的字段存在跨代指針，其對應的卡表的元素標識就變成 1 ，表示該元素變臟， 否則為 0 ， GC 時， 只要篩選本收集區的卡表中變臟的元素加入 GCRoots 里。

卡表的維護

卡表變臟上面已經說到了， 但是需要注意的是如何讓卡表變臟， 即發生了引用字段賦值時，如何更新卡表對標識為 Hotspot 使用 寫屏障 維護卡表狀態

參考資料

• 《深入理解 Java 虛擬機第三版》 周志明
• 三色標記法與讀寫屏障 路過的豬