作者 | 崔皓
開篇
我們知道JVM的垃圾回收機制實際上是對JVM記憶體的操作，回收的目的是為了避免記憶體溢位和記憶體洩漏的問題。而JVM記憶體由方法區、堆、虛擬機器棧、本地方法棧以及程式計數器5塊區域組成，虛擬機器棧、本地方法棧、程式計數器是隨著Java執行緒建立而建立，當Java 執行緒完成之後這三個部分的記憶體就會被釋放掉。
而方法區和堆屬於共有執行緒，是隨著JVM啟動而建立的，而且這兩個區域與另外三個區域也有所不同，一個介面中有多少個實現類（方法區）以及每次程式執行需要建立多少物件（堆）是動態的，也就是說在程式執行時才能知道。
為了讓這部分動態的記憶體分配能夠進行合理的回收，就需要垃圾回收演算法和垃圾回收器來幫忙了。下面讓我們進入今天的主題。
如何判斷物件“存活”？
JVM 垃圾回收機制是對堆中沒有使用的物件進行回收，那麼判斷物件是否“存活”就至關重要。在判斷物件是否“存活”的方法中，我們會介紹引用計數演算法和可達性分析法。
引用計數演算法
Java
堆
中針對每個物件都設定一個
引用計數器
。當一個物件被建立並初始化賦值後，該變數計數設定為1。每當有一個地方引用它時，計數器值就
加1
。當引用
失效
時，即一個物件的某個引用超過了生命週期（出作用域後）或者被設定為一個新值時，計數器值就
減1
。任何引用計數為0的物件可以被當作垃圾回收。當一個物件被
垃圾回收
時，它引用的任何物件計數減1。
這種方法的優點很明顯，引用計數回收器執行簡單，判定效率高，對程式不被長時間打斷的實時環境比較有利。不過缺點也很明顯，對於物件迴圈引用的場景難以判斷，同時引用計數器增加了程式執行的開銷。Java語言並沒有選擇這種演算法進行垃圾回收。
可達性分析法
可達性分析法也叫根搜尋演算法，透過稱為 GC Roots 的物件作為起點，從上往下進行搜尋。搜尋所走過的路徑稱為引用鏈 （Reference Chain）， 當發現某個物件與 GC Roots之間沒有任何引用鏈相連時， 即認為該物件不可達，該物件也就成了垃圾回收的目標。
如圖1 所示，從GC Roots 開始沒有引用鏈和Obejct5、Object6 和Object7 相連，因此這三個物件對於GC Roots 而言就是不可達的，會被垃圾回收，即便他們互相都有引用。
圖1 可達性分析法
在Java中，可作為GC Roots的物件包括如下四種：
虛擬機器棧（棧幀中的本地變量表）中引用的物件
本地方法棧 中 JNI （Native方法）引用的變數
方法區 中類靜態屬性引用的變數
方法區 中常量引用的變數
前面談到的可達實際上是在判斷物件是否被引用，如果沒有被引用，垃圾回收器會將其進行回收。不過我們希望存在這樣一些物件，當記憶體空間足夠的情況下儘量將其保留在記憶體中，當記憶體不夠的情況下，再回收這些物件。下面看看如何對如下物件進行處理：
強引用（Strong Reference）：例如，Object obj = new Object（）這類引用，只要強引用存在，垃圾回收器永遠不會回收掉被引用的物件。
軟引用（Soft Reference）：在系統將要出現記憶體溢位之前，會將軟引用物件列進回收範圍之中進行二次回收。如果這次回收還沒有足夠的記憶體，才會丟擲記憶體溢位異常。
弱引用（Weak Reference）：被弱引用關聯的物件只能生存到下一次垃圾回收發生之前，無論當前記憶體是否足夠，用軟引用相關聯的物件都會被回收掉。
虛引用（Phantom Reference）：虛引用也稱為幽靈引用或幻影引用，是最弱的一種引用關係，為一個物件設定虛引用的唯一目的是：能在這個物件在垃圾回收器回收的時候收到一個系統通知。
垃圾回收演算法
上面講解了如何發現“存活”物件，JVM中會使用可達性分析法，說白了就是看GC Roots在引用鏈上是否有對應的物件被引用到了。接下來就在這個背景下看看有哪些垃圾回收的演算法，這裡我們列舉出常見的幾種：
標記清除演算法
該演算法分為標記和清除兩個階段，首先透過可達性分析法找到要回收的物件，也就是沒有被引用的物件，對其進行標記，然後再對該物件進行清除也就是回收了。
如圖2 所示，該演算法會對記憶體空間進行掃描，發現GC Roots 對Object1 和Object2 進行引用，但是對Object2 沒有引用。首先標記Object2 沒有被引用。
圖2
如圖3 所示，演算法再次對記憶體進行掃描，清除Object2 物件佔用的空間，將其設定為空閒空間。
圖3 標記清除演算法
該演算法的優點就是簡單粗暴，沒有引用的物件會被清除掉，但是缺點是效率問題。標記和清除操作會掃描整個空間兩次（第一次：標記存活物件；第二次：清除沒有標記的物件）才能完成清理工作。同時清理過程容易產生記憶體碎片，這些空閒的空間無法容納大物件，如果此時有一個比較大的物件進入記憶體，由於該記憶體中沒有連續的容納大物件的空間，就會提前觸發垃圾回收。
複製演算法
為了解決標記清除法帶來的問題，複製演算法將記憶體劃分為大小相等的兩塊，每次使用其中的一塊，當這塊的記憶體使用完畢以後，再將物件複製到另外一塊上面，然後對已經使用過的記憶體空間進行清理。這樣每次對記憶體的一半區域進行回收，不用考慮記憶體碎片的問題。
如圖4 所示，上面的區域是垃圾回收之前的記憶體空間，我們用黑色的虛線將記憶體分為兩個部分。左邊的部分是正在使用的空間，右邊是預留空間。左邊區域中紅色的部分是不可回收的記憶體，也就是說這裡面有被GC Roots 引用的物件，另外灰色的部分是可回收的區域，也就是沒有被GC Roots 引用的物件，白色區域是未分配的。
如果透過複製演算法進行垃圾回收，順著綠色的箭頭向下，在回收後的記憶體區域可以看到，將左側紅色的記憶體物件移動到了右側預留的區域，並且按照順序排放。然後對左側執行的記憶體區域進行清理，成為預留區域等待第二次垃圾回收的執行。
圖4 複製演算法
複製演算法的優點是簡單高效，不會出現記憶體碎片。缺點也明顯，記憶體利用率低，只有一半的記憶體被利用。特別是存活物件較多時效率明顯降低，因為需要移動每個不可回收資料的記憶體實際位置。
標記整理演算法
該演算法和標記清除演算法相似，但是後續步驟並不是直接對可回收物件進行清理，而是讓所有存活物件都移動到記憶體的前端，然後再清除掉其他可回收的物件所佔用的記憶體空間。
如圖5 所示，回收前的記憶體中紅色為不可回收的記憶體空間，灰色是可回收空間，白色是未分配空間。執行標記整理演算法的垃圾回收之後，將不可回收的記憶體空間整理到記憶體的前端，同時清除掉可回收的記憶體空間，此時不可回收空間之後存放的都是白色的未分配空間，供由新物件存放。
圖5 標記整理演算法
標記整理演算法優點是解決了標記清理演算法存在的記憶體碎片問題。缺點也是非常明顯，需要進行區域性物件移動，一定程度上降低了效率。
分代收集演算法
分代收集演算法，顧名思義是根據物件的存活週期將記憶體劃分為幾塊，然後定義回收規則。如圖6所示，從左到右分別是年輕代（Young Generation）、老年代（Old Generation） 和 永久代（Permanent Generation），另外年輕代又分為了Eden Space（伊甸空間） 、Survivor Space（倖存者空間）。分代收集的演算法在當前商業虛擬機器演算法中被廣泛採用。
圖6 分代收集法
上面對分代收集法做了字面的解釋，現將該演算法的執行過程描述如下：
1）新產生的物件優先分配在Eden區（除非配置了-XX：PretenureSizeThreshold，大於該值的物件會直接進入老年代）。有這樣一種情況，當物件剛剛在新生代建立就被回收了，物件從這個區域消失的過程我們稱之為 minor GC。
2）當Eden區滿了或放不下了，這時候其中存活的物件會複製到from區。如果此時存活下來的物件在from 區都放不下，就會放到老年代，之後Eden 區的記憶體會全部回收掉。
3）之後產生的物件繼續分配在Eden區，當Eden區又滿了或放不下了，這時候將會把Eden區和from區存活下來的物件複製到to區，此時如果存活下來的物件to區也放不下，會將其移動到年老代，同時會回收掉Eden區和from區的記憶體。
4）如果按照如上操作將物件在幾個區域中移動，會出現物件被多次複製的情況，物件被複制一次，物件的年齡就會+1。預設情況下，當物件被複制了15次（透過：-XX：MaxTenuringThreshold來配置），該物件就會進入老年代了。
5）當老年代滿了的情況下，就會發生一次Full GC。
備註：Minor GC指發生在新生代的垃圾收集動作，因為Java物件大多都具備朝生夕滅的特性，所以Minor GC非常頻繁，一般回收速度也比較快。Full GC指發生在老年代的GC，出現了Full GC，經常會伴隨至少一次的Full GC，Full GC的速度一般會比Minor GC慢10倍以上。
垃圾回收器
如果垃圾回收演算法是記憶體回收的方法論的話，那麼垃圾回收器就是記憶體回收的具體實現了。下面會針對JDK1。7 Update 14 之後的HotSpot虛擬機器給大家做介紹。
如圖7所示，這裡將記憶體分為新生代和老年代，將7種不同垃圾回收器分佈於其間，垃圾回收器之間存在連線，說明它們可以搭配使用。
虛擬機器所處的區域，則表示它是屬於新生代收集器還是老年代收集器。Hotspot實現瞭如此多的收集器，正是因為目前並無完美的收集器出現，只是選擇對具體應用最適合的收集器。
圖7垃圾回收器的分類
下面就來介紹這幾個垃圾回收器：
Serial回收器
Serial（序列）回收器採用複製演算法的新生代收集器，它是一個單執行緒回收器，針對一個CPU或一條收集執行緒去完成垃圾收集工作，它在進行垃圾收集時，必須暫停其他所有的工作執行緒，直至Serial收集器收集結束為止，這個做法也稱為 “Stop The World”。
如圖8 所示，左邊多個應用程式執行緒在執行， 當Serial 回收器的GC執行緒（虛線部分）執行的時候，應用程式執行緒（左邊多個實線）都會暫停，只有在回收器執行緒執行完畢以後，應用程式執行緒（右邊多個實線）才會繼續執行。
圖 8 序列垃圾回收器
該回收器的問題就是在進行垃圾回收時其他工作執行緒必須停頓，不過它在HotSpot虛擬機器執行的Client模式下可以為新生代回收器服務。它的簡單而高效對於限定單個CPU的環境來說，Serial回收器沒有執行緒互動的開銷。在使用者的桌面應用場景中，分配給虛擬機器管理的記憶體不大，停頓時間可以控制在幾十毫秒以內，還是可以接收。它對於執行在Client模式下的虛擬機器來說是一個很好的選擇。
ParNew 回收器
ParNew回收器是Serial回收器的多執行緒版本，它也是一個新生代回收器。除了使用多執行緒進行垃圾收集外，其餘行為包括Serial收集器可用的所有控制引數、收集演算法（複製演算法）、Stop The World、物件分配規則、回收策略等。
如圖9 所示，與Serial 不同的是ParNew 使用多個執行緒（中間多條虛線）的方式進行垃圾回收。
圖9 ParNew 並行回收器
ParNew 回收器在多CPU環境下垃圾回收的效率會有明顯提高。它預設開啟的收集執行緒數與CPU的數量相同，在CPU非常多的情況下可使用-XX：ParallerGCThreads引數設定。反過來，如果針對單個CPU的環境 ParNew 和Serial 回收器的效果就難分伯仲了。
Serial Old回收器
Serial Old 是 Serial回收器的老年代版本，是單執行緒收集器，使用標記整理（Mark-Compact）演算法。它可以給Client模式下的虛擬機器使用。如果在Server模式下，它還有兩大用途：在JDK1。5 以及之前版本（Parallel Old誕生以前）中與Parallel Scavenge收集器搭配使用。作為CMS收集器的後備預案，在併發收集發生Concurrent Mode Failure時使用。
Parallel Old回收器
Parallel Old回收器是Parallel Scavenge的老年代版本，使用多執行緒的標記整理演算法。在JDK 1。6中才開始提供，如果新生代選擇了Parallel Scavenge收集器，老年代除了Serial Old以外別無選擇。Parallel Old回收器的工作流程與Parallel Scavenge相同。
Parallel Scavenge 回收器
Parallel Scavenge回收器是並行的多執行緒新生代回收器，它使用複製演算法。Parallel Scavenge回收器的目標是達到一個可控制的吞吐量（Throughput）。
這裡稍微說明一下， 吞吐量就是CPU執行使用者程式碼時間與CPU總消耗時間的比值，表現成工時是：吞吐量 = 使用者程式碼執行時間 /（使用者程式碼執行時間 + 垃圾回收時間）。使用者程式碼執行時間95 分鐘，垃圾回收時間為5分鐘，那吞吐量就是95/（95+5）=95%。
高吞吐量說明垃圾回收器高效率地利用CPU時間，儘快完成程式的運算任務。從而讓垃圾回收造成的停頓時間變短，適合與使用者互動的程式提升使用者體驗。
Parallel Scavenge會提供精確控制吞吐量的引數，此外還透過對引數-XX：+UseAdaptiveSizePolicy 設定來自動調節新生代的大小（-Xmn）、Eden和Survivor區的比例（-XX：SurvivorRatio）、晉升老年代物件年齡（-XX：PretenureSizeThreshold）等資訊。
此外Parallel Scavenge 回收器還有一個特點就是，會根據當前系統的執行情況收集效能監控資訊，動態調整這些引數以提供最合適的停頓時間或者最大的吞吐量，我們稱之為GC自適應的調節策略（GC Ergonomics）。
CMS收集器
CMS（Concurrent Mark Sweep）收集器是以獲取最短回收停頓時間為目標的回收器，它適用於重視響應速度的應用場景，它是基於標記清除演算法而實現的。
如圖10 所示，從左往右CMS工作流程分為以下4個步驟：
初始標記（CMS initial mark）：標記GC Roots直接關聯到的物件，需要執行“Stop The World”，也就是讓工作執行緒暫停。
併發標記（CMS concurrent mark）：從GC Roots 查詢所有可達的物件，這個過程耗時比較長，此時使用者執行緒依舊在執行。
重新標記（CMS remark）：修正併發標記期間，使用者程式繼續運作而導致標記的物件，並且調整標記記錄，此階段也需要“Stop The World”，因為不暫停工作執行緒的話還可能有標記不準確的情況發生。
併發清除（CMS concurrent sweep）：對於標記不可用的物件進行併發清除操作，這個過程耗時會比較長，此時工作執行緒依舊可以執行。
所以，從總體上來說，CMS收集器的記憶體回收過程是與使用者執行緒一起併發執行的。透過下圖可以比較清楚地看到CMS收集器的運作步驟中併發和需要停頓的時間：
圖10 CMS 垃圾回收器
CMS的優點明顯，併發收集、低停頓。不過他對CPU資源非常敏感，在併發階段雖然不會導致使用者執行緒暫停，但會因為佔用了一部分執行緒（或者說CPU資源）而導致應用程式變慢，總吞吐量會降低。
CMS預設啟動的回收執行緒數是（CPU數量+3）/4，也就是當CPU在4個以上時，併發回收時垃圾收集執行緒不少於25%的CPU資源，並且隨著CPU數量的增加而下降。但是當CPU不足4個時（比如2個），CMS對使用者程式的影響就可能變得很大，如果本來CPU負載就比較大，還要分出一半的運算能力去執行收集器執行緒，就可能導致使用者程式的執行速度忽然降低了50%。
無法處理浮動垃圾（Floating Garbage） 可能出現“Concurrent Mode Failure”失敗而導致另一次Full GC的產生。在垃圾回收階段，使用者執行緒還在執行，還需要預留有足夠的記憶體空間給使用者執行緒使用，因此CMS需要預留一部分空間提供併發收集時的程式運作使用。標記清除演算法本身也會導致產生大量的空間碎片。
G1回收器
G1（Garbage-First）回收器是面向服務端應用的垃圾回收器，它具備如下特點：
充分利用多CPU縮短“Stop The World”停頓時間，可以透過併發的方式讓Java程式繼續執行。
不需要其他回收器配合就能獨立管理整個GC堆，採用不同方式去處理新建立的物件和已存活一段時間、對於經歷過多次GC的舊物件來說會有更好的回收效果。
G1基本上是基於標記整理演算法實現的，在區域性（兩個Region之間）是基於複製演算法實現的。這意味著G1執行期間不會產生記憶體空間碎片，收集後能提供規整的可用記憶體。此特性有利於程式長時間執行，分配大物件時不會因為無法找到連續記憶體空間而提前觸發下一次GC。
可預測的停頓時間模型，能讓使用者明確指定在一個長度為M毫秒的時間片段內，消耗在GC上的時間不得超過N毫秒。
與其他垃圾回收器不同的是，G1回收的範圍橫跨整個堆記憶體。
如圖11所示，G1將堆劃分為多個大小相等的區域（Region），雖然還保留新生代和老年代的概念，但新生代和老年代不再是物理隔離的了，而是Region的集合。
圖11 G1 將堆進行分Region
前面提到G1回收器可以預測的停頓時間，是因為它避免在整個Java堆中進行全區域的垃圾回收。G1會跟蹤各個Region的垃圾堆積的價值大小（回收的空間大小以及回收所需時間的經驗值），在後臺維護一個優先列表，每次根據允許的回收時間，優先回收價值最大的Region。
雖然G1把Java堆分為多個Region，在某個Region中的物件可以與位於其他Region中的任意物件發生引用關係。在做可達性分析時仍然需要掃描整個堆，顯然這樣做效率是不高的。為了避免全堆掃描， G1為每個Region維護了一個記憶集（Remembered Set）。當發現程式在對引用（Reference）型別的資料進行寫操作時，會產生一個Write Barrier暫時中斷寫操作。然後檢查引用（Reference）物件是否處於不同的Region之中，如果是便透過CardTable把相關引用資訊記錄到被引用物件所屬的Region的記憶集（Remembered Set）之中。當進行記憶體回收時，在GC根節點的列舉範圍中加入Remembered Set即可保證不對全堆掃描也不會有遺漏。說白了就是透過Remembered Set 記錄跨Region引用的物件，其目的是避免全堆掃描。
如圖12所示，Region2 中的兩個物件分配被Region1 和Region3 中的物件引用，因此在Region2中的記憶集（Remembered set）就會記錄這兩個引用的資訊，在垃圾回收的時候只需要收集記憶集的資訊就知道物件在每個Region 的引用關係了，並不需要掃描所有堆的Region。
圖12 跨Region的物件引用
說了G1 的特點和機制，下面透過圖13 來看看它的執行過程：
初始標記（Initial Marking）：標記GC Roots 能直接引用的物件，讓下一階段使用者程式併發執行時，能在正確的Region中建立物件，此階段需要停頓執行緒，但耗時很短。
併發標記（Concurrent Marking） ：從GC Root 開始對堆中物件進行可達性分析，找到存活物件，此階段耗時較長，但可與使用者程式併發執行。
最終標記（Final Marking）：為了修正在併發標記期間因使用者程式繼續運作而導致標記產生變動的那一部分標記記錄，虛擬機器將這段時間物件變化記錄線上程的Remembered Set Logs裡面，最終標記階段需要把Remembered Set Logs的資料合併到Remembered Set中，這階段需要停頓執行緒，但是可並行執行。
篩選回收（Live Data Counting and Evacuation） ：首先對各個Region中的回收價值和成本進行排序，根據使用者所期望的GC 停頓時間來制定回收計劃。此階段其實也可以做到與使用者程式一起併發執行，但是因為只回收一部分Region，時間是使用者可控制的，而且停頓使用者執行緒將大幅度提高收集效率。
總結
今天給大家介紹了垃圾回收的演算法和JVM的垃圾回收器，演算法作為思路和方法論的指導，而垃圾回收器是方法論的最佳實踐，這裡透過一張表格將兩者進行一個總結：
作者介紹
崔皓，51CTO社群編輯，資深架構師，擁有18年的軟體開發和架構經驗，10年分散式架構經驗。曾任惠普技術專家。樂於分享，撰寫了很多熱門技術文章，閱讀量超過60萬。《分散式架構原理與實踐》作者。
點分享
點收藏
點點贊
