垃圾收集演算法與垃圾收集器
到目前為止，GC和記憶體分配這塊技術已經發展的相當成熟了，無需我們在花費大量的精力繼續研究改進，那我們為什麼要還要了解這塊的知識呢？因為當需要排查各種記憶體溢出，記憶體泄露問題時，當垃發量的瓶頸時，我們就需要需要對GC和記憶體分配這方面有一定的了解和認識，才能會更好的解決問題！！
一， 確定對象死亡
在堆裡面存放著Java世界中幾乎所有的對象實例，垃圾收集器在對堆進行回收前，第一件事情就是要確定這些對象之中哪些還「存活」著，哪些已經「死去」（即不可能再被任何途徑使用的對象）。那如何確定呢？就是採用一些演算法來確定的，接下來就給大家介紹這些演算法。
1.1 引用計數演算法（Reference Counting）
引用計數演算法可以簡單概括為：給對象中添加一個引用計數器，每當有一個地方引用它時，計數器值就加1；當有引用失效時，計數器值就減1；任何時刻計數器為0的對象就是不可能再被使用的，即該對象就可以被垃圾收集器回收掉。
雖然此演算法實現簡單，在確定失效對象時的效率也很高，但它有一個弊端就是很難解決對象間相互循環引用的問題，以至於當今主流虛擬機都沒有使用它來管理記憶體。
那什麼是對象相互循環引用的問題？下面給大家用程式碼舉例下。
public class ReferenceCountingGC { public Object instance=null; /** * 定義數組僅僅是為了佔用記憶體，使在GC日誌中能明顯看出對象是否被回收的效果 */ private byte[] bigSize=new byte[1024*1024]; public static void testGC(){ ReferenceCountingGC objA=new ReferenceCountingGC(); ReferenceCountingGC objB=new ReferenceCountingGC(); objA.instance=objB; objB.instance=objA; objA=null; objB=null; System.gc();//垃圾回收 } public static void main(String[] args) { testGC(); } }
從程式碼可以看出，對象objA的instance變數引用著對象objB，對象objB的instance變數引用著對象objA，並且底下已經將這兩個對象都置為null了，但是如果採用引用計數演算法來管理記憶體空間，雖然這兩個對象已經沒什麼用來了，但是因為還被其他對象引用著，計數一直大於0，所以無法被回收掉。
1.2 可達性分析演算法（Reachability Analysis）
當前主流使用演算法（Java.C都在用），基本思路就是通過一系列稱為「GC Roots」的根對象作為起始節點集，從這些節點開始，根據引用關係向下搜索，搜索過程所走過的路徑稱為「引用鏈」（Reference Chain），如果某個對象到GC Roots間沒有何引用鏈相連，或者用圖論的話來說就是從GC Roots到這個對象不可達時，則證明此對象是不可能再被使用的，就可以被回收掉了。如下圖中的對象object5，object6和object7，他們之間雖然還存在著引用關係，但是它們從GC Roots是不可達的，因此它們三個就可被判定為可回收對象。
注意在可達性分析演算法中不可達的對象，也並非是「非死不可」的，這時候它們只是處於「緩刑」階段，要真正判斷宣告一對象已死亡，至少要經歷兩次標記的過程：如果對象在進行可達性分析後發現沒有與GC Roots相連接的引用鏈，那它就將會被第一次標記並且進行一次篩選，篩選的條件是此對象是否有必要執行finalize()方法，當對象沒有覆蓋finalize()方法，或者該方法已經被虛擬機調用過了，虛擬機會認為是沒有必要執行，那麼該對象就可被回收了；如果該對象被判斷有必要執行finalize()方法，那麼就會將該對象放置到一個叫做F-Queue的隊列中，並在稍後由一個虛擬機自動建立的，低優先順序的Finalizer執行緒去執行它。
這裡所謂的這個「執行」是指虛擬機會觸發這個方法，但並不承諾會等待它運行結束，是為了防止該對象在finalize()方法中執行緩慢影響F-Queue隊列中其他對象的執行。也可以說finalize()方法是對象逃脫死亡的最後一次機會，當GC對F-Queue中的對象進行第二次小規模的標記，如果對象在finalize()方法中成功拯救自己（只要重新與引用鏈上的任何一個對象建立關聯即可），那麼在第二次標記時它將被移除「即將回收」集合；如果該對象這時候還沒有逃脫，那基本上就可被回收了。
Java中可以固定作為GC Roots的對象：
- 虛擬機棧中引用的對象；
- 方法區中類靜態屬性引用對象；
- 方法區常量引用對象，譬如字元串常量池裡的引用；
- 本地方法棧中JNI（Native方法）引用的對象；
- Java虛擬機內部引用；
- 被同步鎖持有的對象；
- 反映Java虛擬機內部情況的JMXBean、JVMTI中註冊的回調、本地程式碼快取等。
從圖中可以注意到，對象實例1，對象實例4，對象實例6都是可作為GC Roots的對象，而對象實例5因為從GC Roots可達，所以也不可被回收。而對象實例2，對象實例3因為從GC Roots不可達，所以就可被回收掉。
1.3引用的定義
JDK1.2之後，引用分為強引用（Strongly Re-ference）、軟引用（Soft Reference）、弱引用（Weak Reference）和虛引用（Phantom Reference）4種，這4種引用強度依次逐漸減弱。那為什會有這麼多分類？因為在這之前，引用的定義太過於狹隘，一個對象在這種定義下只有被引用或者沒有被引用兩種狀態，對於一些「食之無味，棄之可惜」的對象就顯得無能為力。所以在出現了強，軟，弱，虛這幾種引用之後，我們就可以對對象引用的各種狀態進行描述，如：記憶體不足，是否可被回收等等。
強引用（Strongly Re-ference）：在程式程式碼之中普遍存在的引用賦值，即類似「Object obj=new Object()」這種引用關係。無論任何情況下，只要強引用關係還存在，垃圾收集器就永遠不會回收掉被引用的對象。
軟引用（Soft Reference）：是用來描述一些還有用，但非必須的對象。只被軟引用關聯著的對象，在系統將要發生記憶體溢出異常前，會把這些對象列進回收範圍之中進行第二次回收，如果這次回收還沒有足夠的記憶體，才會拋出記憶體溢出異常。在JDK 1.2版之後提供了SoftReference類來實現軟引用。
弱引用（Weak Reference）：也是用來描述那些非必須對象，但是它的強度比軟引用更弱一些，被弱引用關聯的對象只能生存到下一次垃圾收集發生為止。當垃圾收集器開始工作，無論當前記憶體是否足夠，都會回收掉只被弱引用關聯的對象。在JDK 1.2版之後提供了WeakReference類來實現弱引用。
虛引用（Phantom英[ˈfæntəm] Reference）：也稱為「幽靈引用」或者「幻影引用」，它是最弱的一種引用關係。一個對象是否有虛引用的存在，完全不會對其生存時間構成影響，也無法通過虛引用來取得一個對象實例。為一個對象設置虛引用關聯的唯一目的只是為了能在這個對象被收集器回收時收到一個系統通知。在JDK 1.2版之後提供了PhantomReference類來實現虛引用。
二， 垃圾回收演算法
2.1 標記-清除演算法（Mark-Sweep）
分為標記和清除兩個階段：首先標記需要回收的對象，在標記完成後統一回收，是最基礎的垃圾收集演算法，其他垃圾收集演算法都
是基於它進行改進而實現的。
它有兩個不足點：一是效率低，二是清除後會產生大量不連續的記憶體碎片，可能會出現無法繼續存放一個較大的對象而不得已提前觸發另一次垃圾回收的情況。
2.2 複製演算法（Mark-Copy）
一般將可用記憶體按容量劃分為大小相等的兩塊，每次只使用其中的一塊，當這一塊的記憶體用完了，就將還存活的對象複製到另外一塊並整齊排列，此後新產生的對象都存放在這塊記憶體空間中。然後在將那塊已使用過的記憶體一次清理掉，作為預留區域下次使用。這樣使得每次都是對半個記憶體區進行記憶體回收，記憶體分配時也就不用考慮記憶體碎片等複雜情況。但是這種演算法也有弊端，就是每次只能使用記憶體空間的一半大小，降低了系統資源利用率，且當存活對象較多時，複製的工作量會太大而影響效率。
2.3 標記-整理演算法（Mark-Compact）
標記-整理演算法和標記-清除演算法的過程有點相似之處，兩者的標記過程是相同的，但對於標記整理演算法來說，後續的步驟不是直接對可回收的對象進行清除回收，而是將它們統一移動到一端，然後直接清除掉端邊界以外的記憶體。使用這種演算法避免了記憶體空間利用率低的問題。
2.4 分代收集演算法
當前商業虛擬機的垃圾收集都採用「分代收集」演算法，這種演算法是根據對象存活周期的不同將記憶體劃分為幾塊。一般是把Java堆分為新生代（年輕代）和老年代，因為新生代中的對象98%是」朝生夕死「的，所以又將新生代的記憶體劃分為一塊較大的Eden空間和兩塊較小的Survivor空間，Eden空間用來存放每次新生的對象，Survivor空間來存放沒有被垃圾收集器回收掉的對象，在每次進行回收時，先將Eden區和Survivor中還存活的對象一次性複製到Survivor的另一塊空間中，並將對象的年齡值加一，當有對象的年齡值大於15時，就可將它移動到老年代，接著清除掉Eden區和Survivor中剛被用的空間區中的對象。HotSpot虛擬機默認Eden區和Survivor區中兩塊空間的大小比例為8：1：1。
要注意在回收過程中，當Survivor空間不夠存放本次存活的對象時，就需要依賴其他記憶體（老年代）進行擔保。也就是說如果Survivor區中的另一塊空間不夠存放本次存活的對象，這些對象將直接通過分配擔保機制進入老年代。當老年代也滿了的時候，就會進行一次Full GC，就是將Eden區，Survivor區和老年代中的記憶體都進行一次垃圾收集。（新生代中使用的是Minor GC）
採用這種分代處理的好處是可以根據各個年代的特點採用最適合的收集演算法。在新生代中，每次手機發現有大批對象死亡，只有少量存活，那就採用複製演算法，只需要付出少量存活對象的複製成本就可以完成收集，而老年代中因為對象存活率高沒有額外空間對它進行擔保，就必須使用「標記-清理『或」標記-整理「演算法來進行。
下面就模擬一下垃圾收集的過程：
先將Eden區和Survivor區的from區中本次仍存活的對象複製到to區中，並將對象的計數值加一，當對象的值為15時就將其複製到老年代中，
然後將Eden區中和from區中的對象清除掉，結果如下圖。
當Eden區中無法繼續存儲時，就再次進行垃圾回收，步驟和上面類似。
2.5 分代收集理論
1.一般把Java堆分為新生代（Young Generation）和老年代（Old Generation），在新生代中又分為Eden區和Survivor區，通常
比例為8：1：1，每次只保留10%的空間作預留區域，然後將90%的空間可以用作新生對象。
2.每一次垃圾回收之後，存活的對象年齡加1，當經歷15次還存活的對象，我們就讓它直接進入老年代。
3.另外一種進入老年代的方式是記憶體擔保機制，也就是當新生代的空間不夠的時候，讓對象直接進入到老年代。
4.新生代的垃圾回收叫Minor GC，老年代的叫Full GC。
三， 垃圾收集器（JDK7-JDK11）
如果說收集演算法是記憶體回收的方法論，那麼垃圾是收集器就是記憶體回收的具體實現。因為Java虛擬機規範中對垃圾收集器應如何實現沒有任何規定，因此不同廠商提供的垃圾收集器都會有很大的差別，所以用戶使用時都需要通過設置參數來決定自己要使用垃圾收集器。
下圖中展示了7種作用不同分代的垃圾收集器，存在連線的代表可以搭配使用，另外，目前沒有一個真正最好的收集器出現，我們選擇的只是對具體應用最合適的收集器。。
3.1 Serial收集器
Serial收集器是最基本，發展最悠久的收集器。它是單執行緒的，也就是說它只會使用一個CPU或一條收集執行緒去完成垃圾收集的工作，並且在它進行垃圾收集時，必須暫停其他所有工作的執行緒，直到它收集結束（Stop the world）。
可以看出該垃圾收集器工作效率是很低的，雖然在這之後又研發出了Parallel收集器和CMS收集器，減少了工作執行緒因記憶體回收而造成的停頓時間。但Serial收集器仍是不可替代的，並且到目前為止，它依然是虛擬機運行在Client模式下的默認新生代收集器。因為相對其他收集器，它簡單高效，關鍵對於限定單個CPU的環境來說，Serial收集器由於沒有執行緒交互的開銷（比如ParNew是多執行緒GC，所以工作時需要不停切換），專門做垃圾收集自然可以獲得最高的單執行緒收集效率。
3.2 ParNew收集器
ParNew是Serial收集器的多執行緒版本，除了使用多執行緒進行垃圾收集之外，其餘行為包括Serial收集器可用的所有控制參數，收集演算法，STW,對象分配規則，回收策略等都與Serial收集器完全一樣。
雖然它相對Serial收集器來說，只是增加了垃圾多執行緒收集的方法，並無其他創新，但由於目前除了Serial收集器外，只有它能跟CMS收集器配合使用，所以它目前也是許多運行在Server模式下的虛擬機中首選的新生代收集器。
3.3 Parallel Scavenge收集器
Parallel Scavenge收集器也是一款新生代收集器，它同樣是基於複製演算法實現的，能夠並行收集的多執行緒收集器，與其他收集器的目標不同，其他收集器是儘可能的縮短垃圾收集時用戶執行緒的停頓時間，而Parallel Scavenge收集器的目標則是達到一個可控制的吞吐量（Throughput）。所謂吞吐量就是CUP處理器用於運行用戶程式碼的時間與處理器總消耗時間的比值，即吞吐量=運行用戶程式碼時間/（運行用戶程式碼時間+垃圾收集時間），如虛擬機總運行了100分鐘，其中垃圾收集器花費了1分鐘，那吞吐量就是99%。
停頓時間越短就越適合需要與用戶交互的程式，良好的響應速度能提升用戶體驗，而高吞吐量則可以高效率的利用CPU時間，儘快完成程式的運算任務，主要適合在後台運算而不需要太多交互的任務。
該收集器提供了兩個參數用於精準控制吞吐量，分別為最大垃圾收集停頓時間：-XX：MaxGCPauseMillis；吞吐量：-XX：GCTimeRatio；自適應策略：-XX：+UseAdaptiveSizePolicy可以自動給Eden區和survivor區分配記憶體空間的大小。注意最大垃圾收集停頓時間並非越短越好，因為收集停頓時間短了，收集的頻率就會增加，這樣就會降低吞吐量。
3.4 Serial Old收集器
Serial收集器的老年代版本，它同樣是單執行緒的，使用的標記-整理演算法。
這個收集器的主要目的是在與給Client模式下使用的，在server模式下只有兩種用途：一是配合Parallel Scavenge收集器使用（在剛開始沒有Parallel Old時），二是作為CMS的備選方案。
3.5 Parallel Old收集器
Parallel Old是Parallel Scavenge收集器的老年代版本，支援多執行緒記憶體回收，是基於標記整理演算法。 一般與Parallel Scavenge（新生代的垃圾收集器）結合使用。在這出現之前Parallel Scavenge一直處於尷尬期，因為在這之前Parallel Scavenge因為兼容問題只能與Serial Old配合使用，而又因為Serial Old效率低，使得Serial Old+Parallel Scavenge結合的效率，還不如 ParNew+CMS組合的效率高，這就顯得Parallel Scavenge 有點無用武之地的感覺，直到Parallel Old出現。。。 。
之後在注重吞吐量和CPU利用率的情況下，都會使用Parallel Old+Parallel Scavenge的結合。
4.6 CMS收集器
CMS（Concurrent Mark Sweep）收集器是HotSpot虛擬機中第一款真正意義上的並發收集器，一種以獲取最短回收停頓時間為目標的收集器。
CMS收集器是基於標記-清除演算法實現的，整個過程分為四個步驟，包括：
1）初始標記（CMS initial mark）：需要STW（stop the world），僅僅是標記一下GC Roots能直接關聯到的對象，速度是非常快的。
2）並發標記（CMS concurrent mark），就是進行GC Roots Tracing的過程。
3）重新標記（CMS remark）：需要STW，是為了修正並發標記期間因用戶程式繼續運作而導致標記產生變動的那一部分對象的標記記錄，這個階段的停頓時間一般會比初始標記階段稍長一些，但遠比並發標記的時間短。
4）並發清除（CMS concurrent sweep）
由於整個過程中耗時最長的並發標記和並發清除過程收集器執行緒都可以與用戶執行緒一起工作，自己單獨運行的時間個非常短，所以，從總體上來說，CMS收集器的記憶體回收過程是與用戶執行緒一起並發執行的。
CMS的三大缺點：
1.CMS收集器的並發標記階段需要佔用CPU，所以就會減少用戶執行緒的CPU的佔用，就會降低用戶執行緒的執行效率。
2.無法處理浮動垃圾，而浮動垃圾就是在並發清理過程中產生的垃圾，因為此次並發處理的只是前面被標記了的垃圾，而清理過程中仍然是會產生垃圾的，所以在並發清理階段還需要有一個預留區域來存放這些浮動垃圾，但會當出現預留區域不夠存放這些浮動垃圾的情況，就需要使用Serial Old收集器。
3.因為基於標記清除演算法，所以會產生大量垃圾碎片。
4.7 Garbage First收集器（G1）
Garbage First（簡稱G1）已經是JDK9及以上版本的默認垃圾收集器，是目前最新的穩定的垃圾收集器（JDK11之前），主要面向服務端應用。
G1回收器使用分代和分區演算法。分代演算法就是依然區分年輕代和老年代，依然有eden區和survivor區。分區演算法就是在此演算法中是將Java堆劃分為許多大小相等的獨立區（Region）,數值是在 1M 到 32M 位元組之間的一個 2 的冪值數，JVM 會盡量劃分 2048 個左右、同等大小的 region。當然這個數字既可以手動調整，G1 也會根據堆大小自動進行調整。這些Region獨立區一部分 是作為 Eden，一部分作為 Survivor，除了意料之中的 Old region，G1 會將超過 region 50% 大小的對象（在應用中，通常是 byte 或 char 數組）歸類為 Humongous 對象，並放置在相應的 region 中。邏輯上，Humongous region 算是老年代的一部分。也就是說在此演算法中不要求整個eden區，年輕代或者老年代都連續。
與前面介紹的各種收集器不同的是，在G1演算法中不是在整個Java堆中進行全區域的垃圾收集，而是先檢測各個Region裡面的垃圾堆積的大小，然後在後台維護一個優先列表，每次根據允許的收集時間，優先回收價值最大的Region區（回收後獲得的記憶體多，回收時所需的時間少的價值大）。這種使用Region劃分記憶體空間以及優先順序的區域回收方式，保證了G1收集器在有限的時間內可以獲取儘可能高的收集效率。
從 GC 演算法的角度，G1 選擇的是複合演算法，可以簡化理解為：
1）在新生代，G1 採用的仍然是並行的複製演算法，所以同樣會發生 Stop-The-World 的暫停。
2）在老年代，大部分情況下都是並發標記，而整理（Compact）則是和新生代 GC 時捎帶進行，並且不是整體性的整理，而是增量進行的。習慣上人們喜歡把新生代 GC（Young GC）叫作 Minor GC，老年代 GC 叫作 Major GC，區別於整體性的 Full GC，但是現代 GC 中，這種概念已經不再準確，對於 G1 來說：Minor GC 仍然存在，雖然具體過程會有區別，會涉及 Remembered Set 等相關處理。老年代回收，則是依靠 Mixed GC。並發標記結束後，JVM 就有足夠的資訊進行垃圾收集，Mixed GC 不僅同時會清理 Eden、Survivor 區域，而且還會清理部分 Old 區域。有一個重點就是 Remembered Set，用於記錄和維護 region 之間對象的引用關係。G1中提供了兩種模式垃圾回收模式，Minor GC（YoungGC）和Mixed GC，兩種都是Stop The World(STW)的。
如果不計算維護Remembered Set的操作，G1收集器的運作大致可以分為以下幾個步驟：
1）初始標記
2）並發標記
3）最終標記
4）篩選回收
說在後：此篇部落格摘自周志明老師《深入理解Java虛擬機》，想深入理解的同學可查看此書。
