從方法論上講，程序語言的回收算法主要分為
一、引用計數算法（Reference Counting）：給對象添加一個引用計數器，每當一個地方引用它時，數據器加1；當引用失效時，計數器減1；計數器為0的即可被回收。
二、根搜索算法（GC Root Tracing）：通過一系列的名為“GC Root”的對象作為起始點，從這些節點開始向下搜索，搜索所有走過的路徑稱為引用鏈（Reference Chain）,當一個對象到GC Root沒有任何引用鏈相連時（用圖論來說就是GC Root到這個對象不可達時），證明該對象是可以被回收的。
JAVA采用了根搜索算法，基本原理根據上面解釋應該都能理解，基于根搜索方法，又有具體實現算法
一、標記-清除算法（Mark-Sweep）
最基礎的垃圾收集器算法，分為“標記”和“清除”兩個階段，先標記處所需要回收的對象，標記完成后，統一回收掉所有被標記的對象。
缺點：1）效率問題，標記和清除的效率不高。
2）清除后會產生大量的不連續的內存碎片，可能會導致該程序需要為較大對象分配內存時無法找到足夠連續的內存，不得不提前觸發垃圾收集動作。
二、復制算法（Copying）
將內存容量分成大小相等的兩塊，每次只使用其中一塊，當一塊用完時，將還存活的對象復制到另一塊去，然后把之前使用滿的那塊空間一次性清理掉，如此反復。
優點：內存分配的時候不用考慮內存碎片問題，只移動堆頂指針，按順序分配即可，簡單高效。
缺點：內存空間浪費大，每次只能使用當前的 能夠使用 內存空間的一半；當對象存活率較高時，需要有大量的復制操作，效率低。
三、標記-整理算法（Mark-Compact）
標記整理是在標記-清算上改進得來的，前面說到標記-清算內存碎片的問題，在標記-整理中有解決。同樣有標記階段，標記出所有需要回收的對象，但是不會直接清理，而是將存活的對象向一端移動，在移動過程中清理掉可回收對象。
優點：解決了之前內存碎片的問題，特別是在存活率高的時候，效率遠高于復制算法。
四、分代收集算法（Generational Collection）
根據內存對象的存活周期不同，將內存劃分成幾塊，java虛擬機中一般將內存劃分成新生代和老年代，當新建對象時一般在新生代中分配內存，在新生代垃圾收集器回收幾次后仍然存活的對象，將被移動到老年代，或者當大的對象在新生代中無法分配到足夠連續的內存空間時也會直接分配到老年代。
上面四種算法JVM在回收內存時都有采用，大多都是復合運用多種算法一起實現垃圾回收，具體細節每個算法都可以寫很多內容，為了不偏題，我們這里只寫CMS、G1，其他的有興趣可以自己查詢資料。CMS算法主要是應用在分代收集算法的老年代里，是從JDK8開始采用， 當然默認沒有啟用，如果在開發或生產環境想采用CMS，可以修改JVM配置-XX:+UseConcMarkSweepGC : 手動指定老年代使用CMS收集器。
下面進入正題
CMS定義：英文全稱Concurrent Mark Sweep，可以翻譯為 并發標記清除，是一種以獲取最短回收時間為目標的收集器。這是因為CMS收集器工作時，GC工作線程與用戶線程可以并發執行，以此來達到降低收集停頓時間的目的。
CMS收集器僅作用于老年代的收集，是基于標記-清除算法的，它的運作過程分為4個步驟：
- 初始標記（CMS initial mark）
- 并發標記（CMS concurrent mark）
- 重新標記（CMS remark）
- 并發清除（CMS concurrent sweep）
其中，初始標記、重新標記這兩個步驟仍然需要Stop-the-world。初始標記僅僅只是標記一下GC Roots能直接關聯到的對象，速度很快，并發標記階段就是進行GC Roots Tracing的過程，而重新標記階段則是為了修正并發標記期間因用戶程序繼續運作而導致標記產生變動的那一部分對象的標記記錄，這個階段的停頓時間一般會比初始階段稍長一些，但遠比并發標記的時間短。
CMS以流水線方式拆分了收集周期，將耗時長的操作單元保持與應用線程并發執行。只將那些必需STW才能執行的操作單元單獨拎出來，控制這些單元在恰當的時機運行，并能保證僅需短暫的時間就可以完成。這樣，在整個收集周期內，只有 兩次短暫的暫停（初始標記和重新標記）， 達到了近似并發的目的。
CMS收集器優點：并發收集、低停頓。
CMS收集器缺點：
- CMS收集器對CPU資源非常敏感。
- CMS收集器無法處理浮動垃圾（Floating Garbage），所以如果采用CMS算法，JVM還是在浮動垃圾很多時，自動運行fullgc一次來清除浮動垃圾。
- CMS收集器是基于標記-清除算法，該算法的缺點都有。
什么情況下CMS比較適合：
（1）響應時間優先，能接受犧牲一定的吞吐量，如果需要高響應時間和高吞吐量，推薦使用G1。后續文章再繼續介紹G1。G1也是JDK9默認的垃圾收集器；
（2）硬件配置較高，即CPU和內存資源充足。CMS由于需要與用戶線程并發執行，所以可能會競爭CPU資源。同時CMS并發標記階段，用戶線程同時執行時會新建對象，故內存占用會比較高；
（3）堆大小在3G到8G之間，同時存活時間較長的對象比較多
下面再簡單講講G1算法，
G1重新定義了堆空間，打破了原有的分代模型，將堆劃分為一個個區域。這么做的目的是在進行收集時不必在全堆范圍內進行，這是它最顯著的特點。區域劃分的好處就是帶來了停頓時間可預測的收集模型：用戶可以指定收集操作在多長時間內完成。即G1提供了接近實時的收集特性。
G1收集器將整個Java堆劃分為多個大小相等的獨立區域（Region），雖然還保留有新生代和老年代的概念，但新生代和老年代不再是物理隔離的了，它們都是一部分Region（不需要連續）的集合。Region的大小是一致的，數值是在1M到32M字節之間的一個2的冪值數，JVM會盡量劃分2048個左右、同等大小的Region。其實這個數字既可以手動調整，G1也會根據堆大小自動進行調整。
G1收集的運作過程大致如下：
- 初始標記（Initial Marking）：僅僅只是標記一下GC Roots能直接關聯到的對象，并且修改TAMS（Next Top at Mark Start）的值，讓下一階段用戶程序并發運行時，能在正確可用的Region中創建新對象，這階段需要停頓線程，但耗時很短。
- 并發標記（Concurrent Marking）：是從GC Roots開始堆中對象進行可達性分析，找出存活的對象，這階段耗時較長，但可與用戶程序并發執行。
- 最終標記（Final Marking）：是為了修正并發標記期間因用戶程序繼續運作而導致標記產生變動的那一部分標記記錄，虛擬機將這段時間對象變化記錄在線程Remembered Set Logs里面，最終標記階段需要把Remembered Set Logs的數據合并到Remembered Set中，這階段需要停頓線程，但是可并行執行。
- 篩選回收（Live Data Counting and Evacuation）：首先對各個Region的回收價值和成本進行排序，根據用戶所期望的GC停頓時間來制定回收計劃。這個階段也可以做到與用戶程序一起并發執行，但是因為只回收一部分Region，時間是用戶可控制的，而且停頓用戶線程將大幅提高收集效率。
- 下圖就是G1堆空間分布
G1特點：
- 并行與并發：G1能充分利用多CPU、多核環境下的硬件優勢，使用多個CPU來縮短Stop-the-world停頓的時間，部分其他收集器原來需要停頓Java線程執行的GC操作，G1收集器仍然可以通過并發的方式讓Java程序繼續運行。
- 分代收集
- 空間整合：與CMS的標記-清除算法不同，G1從整體來看是基于標記-整理算法實現的收集器，從局部（兩個Region之間）上來看是基于“復制”算法實現的。但無論如何，這兩種算法都意味著G1運作期間不會產生內存空間碎片，收集后能提供規整的可用內存。這種特性有利于程序長時間運行，分配大對象時不會因為無法找到連續內存空間而提前觸發下一次GC。
- 可預測的停頓：這是G1相對于CMS的一個優勢，降低停頓時間是G1和CMS共同的關注點。
總結
隨著JVM的發展，ORACLE官方推出的JDK11又有了新算法ZGC，它對內存碎片的整理更加優化，回收暫停時間也更加縮短，具體細節本人還沒有深入研究，后面有機會可以寫文章專門介紹它。
最后，我把目前主流JDK使用到的JVM垃圾收集器采用的算法做下簡單總結，方便大家對比參考，
- 新生代垃圾收集器
- Serial-復制算法：Serial收集器是新生代單線程收集器，優點是簡單高效，算是最基本、發展歷史最悠久的收集器。它在進行垃圾收集時，必須暫停其他所有的工作線程，直到它收集完成。
- ParNew收集器-復制算法：ParNew收集器是新生代并行收集器，其實就是Serial收集器的多線程版本。
- Parallel Scavenge（并行回收）-復制算法：
- Parallel Scavenge收集器是新生代并行收集器，追求高吞吐量，高效利用 CPU。該收集器的目標是達到一個可控制的吞吐量（Throughput）。所謂吞吐量就是CPU用于運行用戶代碼的時間與CPU總消耗時間的比值，即 吞吐量=運行用戶代碼時間/（運行用戶代碼時間+垃圾收集時間）。停頓時間越短就越適合需要與用戶交互的程序，良好的響應速度能提升用戶體驗，而高吞吐量則可用高效率地利用CPU時間，盡快完成程序的運算任務，主要適合在后臺運算而不需要太多交互的任務。
2. 老年代垃圾收集器
- Serial Old-標記整理算法：Serial Old是Serial收集器的老年代版本，它同樣是一個單線程(串行)收集器，使用標記整理算法。這個收集器的主要意義也是在于給Client模式下的虛擬機使用
- Parallel Old-標記整理算法：Parallel Old 是Parallel Scavenge收集器的老年代版本，使用多線程和“標記-整理”算法。
- CMS：標記清除算法
- G1：標記整理算法
