一、什么是垃圾回收？

垃圾回收（英語：Garbage Collection，縮寫為 GC），在計算機(jī)科學(xué)中是一種自動的存儲器管理機(jī)制。當(dāng)一個電腦上的動態(tài)存儲器不再需要時，就應(yīng)該予以釋放，以讓出存儲器，這種存儲器資源管理，稱為垃圾回收。垃圾回收器可以讓程序員減輕許多負(fù)擔(dān)，也減少程序員犯錯的機(jī)會。垃圾回收最早起源于 LISP 語言。當(dāng)前許多語言如 Smalltalk、Java、C#和 D 語言都支持垃圾回收器。--摘自 wiki

二、常用的垃圾回收算法

2.1 標(biāo)記清除法( Mark-Sweep )

介紹

標(biāo)記清除算法是現(xiàn)代垃圾回收算法的思想基礎(chǔ)。標(biāo)記清除算法將垃圾回收分為兩個階段：標(biāo)記階段和清除階段。首先標(biāo)記出所有需要回收的對象，在標(biāo)記完成后，統(tǒng)一回收掉所有被標(biāo)記的對象，也可以反過來，標(biāo)記存活的對象，統(tǒng)一回收所有未被標(biāo)記的對象

標(biāo)記清除法圖示

image

缺點

• 執(zhí)行效率不穩(wěn)定。執(zhí)行效率都隨對象數(shù)量增長而降低
• 內(nèi)存空間的碎片化問題。標(biāo)記、清除之后會產(chǎn)生大量不連續(xù)的內(nèi)存碎片，空間碎片太多可能會導(dǎo)致當(dāng)以后在程序運行過程中需要分配較大對象時無法找到足夠的連續(xù)內(nèi)存而不得不提前觸發(fā)另一次垃圾收集動作。

2.2 標(biāo)記復(fù)制算法(Copying)

核心思想

• 將原有的內(nèi)存空間分為兩塊，每次只使用其中一塊
• 在垃圾回收時，將正在使用的內(nèi)存中的存活對象復(fù)制到未使用的內(nèi)存塊中
• 之后，清除正在使用的內(nèi)存塊中的所有對象，交換兩個內(nèi)存的角色，完成垃圾回收

算法圖示

image

• 可以看到每次只對一半?yún)^(qū)域進(jìn)行收集，這樣就不用考慮內(nèi)存碎片等復(fù)雜情況了，只要移動堆頂指針，按順序分配內(nèi)存即可，實現(xiàn)簡單，運行高效。但是這種算法的代價是將內(nèi)存縮小為原來的一半，內(nèi)存成本高
• 復(fù)制算法一般用于收集新生代，因為新生代大部分的對象的存活時間很短，因此新生代中存活的對象遠(yuǎn)遠(yuǎn)少于垃圾對象
• 現(xiàn)在的商用 Java 虛擬機(jī)大多都優(yōu)先采用了這種收集算法去回收新生代。HotSpot 虛擬機(jī)的 Serial、ParNew 等新生代收集器均采用了這種策略來設(shè)計新生代的內(nèi)存布局。

新生代的內(nèi)存布局

• 把新生代分為一塊較大的 Eden 空間和兩塊較小的 Survivor 空間，每次分配內(nèi)存只使用 Eden 和其中一塊 Survivor。
• HotSpot 虛擬機(jī)默認(rèn) Eden 區(qū)與 Survivor 區(qū)的大小比例是 8:1，也即是說 Eden 區(qū)占新生代的 80%，兩個 Survivor 分別占 10%。

image

新生代復(fù)制算法執(zhí)行規(guī)則

• 每次使用復(fù)制算法進(jìn)行垃圾回收時，會將 Eden 區(qū)和其中一塊 Survivor 區(qū)的所有存活對象復(fù)制到另一塊空閑 Survivor 區(qū)中，在復(fù)制操作中，大對象和老年對象將直接復(fù)制到老年代
• 然后將原來的 Eden 區(qū)和 Survivor 區(qū)的對象一次性清理掉
• 如果在執(zhí)行復(fù)制算法時一塊空閑 Survivor 區(qū)域不能夠容納原來的 Eden 區(qū)和 Survivor 區(qū)的對象，就需要依賴?yán)夏甏?，將多余的對象直接?fù)制到老年代

2.3 標(biāo)記整理算法(Mark-Compact)

介紹

在對象存活率較低的新生代使用復(fù)制算法效率高。那么在對象存活率高的老年代，使用復(fù)制算法效率將會變得很低。根據(jù)老年代的特點，有人提出了“標(biāo)記 - 整理”算法。算法流程如下：

• 首先需要從根節(jié)點開始，對所有可達(dá)對象做一次標(biāo)記
• 將所有的存活對象壓縮到內(nèi)存的一端
• 清理邊界外所有的空間

這種方法既避免了碎片的產(chǎn)生 ，又不需要兩塊相同的內(nèi)存空間，因此，其性價比較高。

算法工作圖示

image

三、HotSpot 算法實現(xiàn)

3.1 根節(jié)點枚舉

存在問題：

• 耗時：固定可作為 GC Roots 的節(jié)點主要在全局性的引用（例如常量或類靜態(tài)屬性）與執(zhí)行上下文（例如棧幀中的本地變量表）中，但隨著 Java 應(yīng)用越做越龐大，方法區(qū)龐大，引用眾多，若要逐個檢查以這里為起源的引用肯定消耗不少時間。

• 保障一致性：現(xiàn)在可達(dá)性分析算法耗時最長的查找引用鏈的過程已經(jīng)可以做到與用戶線程一起并發(fā)，但根節(jié)點枚舉始終還是必須在一個能保障一致性的快照中才得以進(jìn)行——這里“一致性”的意思是整個枚舉期間執(zhí)行子系統(tǒng)看起來就像被凍結(jié)在某個時間點上，不會出現(xiàn)分析過程中，根節(jié)點集合的對象引用關(guān)系還在不斷變化的情況。因此 GC 進(jìn)行時必須停頓所有的 Java 執(zhí)行線程 （STW，Stop The World）

解決方案：

在 HotSpot 的解決方案里，是使用一組稱為 OopMap 的數(shù)據(jù)結(jié)構(gòu)來解決

• 一旦類加載動作完成的時候，HotSpot 就會把對象內(nèi)什么偏移量上是什么類型的數(shù)據(jù)計算出來
• 在 JIT 編譯過程中，也會在特定位置記錄下棧和寄存器中哪些位置是引用
• 這樣收集器在掃描時就可以直接得知這些信息了，并不需要真正一個不漏地從方法區(qū)等 GC Roots 開始查找。

3.2 安全點(Safe Point)

問題：

• 在 OopMap 的協(xié)助下，HotSpot 可以快速準(zhǔn)確地完成 GC Roots 枚舉，但一個很現(xiàn)實的問題隨之而來，OopMap 內(nèi)容變化的指令過多導(dǎo)致需要大量額外空間的問題

解決:

• HotSpot 沒有為每條指令都生成 OopMap，只是在“特定的位置”記錄了這些信息，這些位置稱為安全點（Safe Point），即程序執(zhí)行時只有在到達(dá) Safe Point 時才能更新自己的 OopMap。

對于安全點，另外一個需要考慮的問題是，如何在垃圾收集發(fā)生時讓所有線程（這里其實不包括執(zhí)行 JNI 調(diào)用的線程）都跑到最近的安全點，然后停頓下來。有以下兩種方式：

• 搶先式中斷（Preemptive Suspension）:

• • 搶先式中斷不需要線程的執(zhí)行代碼主動去配合
  • 在垃圾收集發(fā)生時，系統(tǒng)首先把所有用戶線程全部中斷
  • 如果發(fā)現(xiàn)有用戶線程中斷的地方不在安全點上，就恢復(fù)這條線程執(zhí)行,讓它一會再重新中斷，直到跑到安全點上
  • 現(xiàn)在幾乎沒有虛擬機(jī)實現(xiàn)采用搶先式中斷來暫停線程響應(yīng) GC 事件。

• 主動式中斷（Voluntary Suspension）:

• • 當(dāng)垃圾收集需要中斷線程的時候，不直接對線程操作
  • 僅僅簡單地設(shè)置一個標(biāo)志位，各個線程執(zhí)行過程時會不停地主動去輪詢這個標(biāo)志
  • 一旦發(fā)現(xiàn)中斷標(biāo)志為真時就自己在最近的安全點上主動中斷掛起。
  • 輪詢標(biāo)志的地方和安全點是重合的，另外還要加上所有創(chuàng)建對象和其他需要在 Java 堆上分配內(nèi)存的地方，這是為了檢查是否即將要發(fā)生垃圾收集，避免沒有足夠內(nèi)存分配新對象。

3.3 安全區(qū)域(Safe Region)

安全點機(jī)制保證了程序執(zhí)行時，在不太長的時間內(nèi)就會遇到可進(jìn)入垃圾收集過程的安全點。

問題：

但是當(dāng)線程沒有分配 CPU 時間（如線程處于 Sleep 狀態(tài)或者 Blocked 狀態(tài)），這時候線程無法響應(yīng) JVM 的中斷請求以繼續(xù)到安全的地方去中斷掛起，JVM 也顯然不太可能等待線程重新被分配 CPU 時間。對于這種情況，就需要安全區(qū)域（Safe Region）來解決。

安全區(qū)域(Safe Region):

是指能夠確保在某一段代碼片段之中，引用關(guān)系不會發(fā)生變化，因此，在這個區(qū)域中任意地方開始垃圾收集都是安全的。我們也可以把安全區(qū)域看作被擴(kuò)展拉伸了的安全點。

• 當(dāng)用戶線程執(zhí)行到安全區(qū)域里面的代碼時，首先會標(biāo)識自己已經(jīng)進(jìn)入了安全區(qū)域，那樣當(dāng)這段時間里虛擬機(jī)要發(fā)起垃圾收集時就不必去管這些已聲明自己在安全區(qū)域內(nèi)的線程了。
• 當(dāng)線程要離開安全區(qū)域時，它要檢查虛擬機(jī)是否已經(jīng)完成了根節(jié)點枚舉（或者垃圾收集過程中其他需要暫停用戶線程的階段），如果完成了，那線程就當(dāng)作沒事發(fā)生過，繼續(xù)執(zhí)行；
• 否則它就必須一直等待，直到收到可以離開安全區(qū)域的信號為止。

3.4 記憶集與卡表(Remembered Set)

問題：

為解決對象跨代引用所帶來的問題，垃圾收集器在新生代中建立了名為記憶集（Remembered Set）的數(shù)據(jù)結(jié)構(gòu)，用以避免把整個老年代加進(jìn) GC Roots 掃描范圍。來縮減 GC Roots 掃描范圍的問題。

記憶集：

是一種用于記錄從非收集區(qū)域指向收集區(qū)域的指針集合的抽象數(shù)據(jù)結(jié)構(gòu)。

記錄精度

• 字長精度：每個記錄精確到一個機(jī)器字長（就是處理器的尋址位數(shù)，如常見的 32 位或 64 位，這個精度決定了機(jī)器訪問物理內(nèi)存地址的指針長度），該字包含跨代指針。
• 對象精度：每個記錄精確到一個對象，該對象里有字段含有跨代指針。
• 卡精度：每個記錄精確到一塊內(nèi)存區(qū)域，該區(qū)域內(nèi)有對象含有跨代指針。

卡表”（Card Table）

記錄精度中，第三種“卡精度”所指的是用一種稱為“卡表”（Card Table）的方式去實現(xiàn)記憶集。卡表最簡單的形式可以只是一個字節(jié)數(shù)組。以下這行代碼是 HotSpot 默認(rèn)的卡表標(biāo)記邏輯

CARD_TABLE[this.address >> 9] = 0;

字節(jié)數(shù)組 CARD_TABLE 的每一個元素都對應(yīng)著其標(biāo)識的內(nèi)存區(qū)域中一塊特定大小的內(nèi)存塊，這個內(nèi)存塊被稱作“卡頁”（Card Page）。一般來說，卡頁大小都是以 2 的 N 次冪的字節(jié)數(shù)。

卡表與卡頁對應(yīng)示意圖：

image

一個卡頁的內(nèi)存中通常包含不止一個對象，只要卡頁內(nèi)有一個（或更多）對象的字段存在著跨代指針，那就將對應(yīng)卡表的數(shù)組元素的值標(biāo)識為 1，稱為這個元素變臟（Dirty），沒有則標(biāo)識為 0。在垃圾收集發(fā)生時，只要篩選出卡表中變臟的元素，就能輕易得出哪些卡頁內(nèi)存塊中包含跨代指針，把它們加入 GC Roots 中一并掃描。

3.5 寫屏障（Write Barrier）

解決了如何使用記憶集來縮減 GC Roots 掃描范圍的問題，但還沒有解決卡表元素如何維護(hù)的問題，例如它們何時變臟、誰來把它們變臟等。

卡表元素何時變臟？：

• 有其他分代區(qū)域中對象引用了本區(qū)域?qū)ο髸r，其對應(yīng)的卡表元素就應(yīng)該變臟
• 變臟時間點原則上應(yīng)該發(fā)生在引用類型字段賦值的那一刻

卡表元素如何變臟： 即如何在對象賦值的那一刻去更新維護(hù)卡表呢？

• 假如是解釋執(zhí)行的字節(jié)碼，那相對好處理，虛擬機(jī)負(fù)責(zé)每條字節(jié)碼指令的執(zhí)行，有充分的介入空間；

• 但在編譯執(zhí)行的場景中呢？經(jīng)過即時編譯后的代碼已經(jīng)是純粹的機(jī)器指令流了，這就必須找到一個在機(jī)器碼層

  面的手段，把維護(hù)卡表的動作放到每一個賦值操作之中。

寫屏障（Write Barrier）

在 HotSpot 虛擬機(jī)里是通過寫屏障（Write Barrier）技術(shù)維護(hù)卡表狀態(tài)的。注意這里的寫屏障與解決并發(fā)亂序執(zhí)行問題中的“內(nèi)存屏障”區(qū)分開來。寫屏障可以看作在虛擬機(jī)層面對“引用類型字段賦值”這個動作的 AOP 切面，在引用對象賦值時會產(chǎn)生一個環(huán)形（Around）通知，供程序執(zhí)行額外的動作，也就是說賦值的前后都在寫屏障的覆蓋范疇內(nèi)。

• 在賦值前的部分的寫屏障叫作寫前屏障（Pre-WriteBarrier）
• 在賦值后的則叫作寫后屏障（Post-Write Barrier）

問題：

• 應(yīng)用寫屏障后，虛擬機(jī)就會為所有賦值操作生成相應(yīng)的指令，一旦收集器在寫屏障中增加了更新卡表操作，所以每次只要對引用進(jìn)行更新，就會產(chǎn)生額外的開銷。
• 卡表在高并發(fā)場景下還面臨著“偽共享”（False Sharing）問題

解決“偽共享”（False Sharing）問題：

• 為了避免偽共享問題，一種簡單的解決方案是不采用無條件的寫屏障，而是先檢查卡表標(biāo)記，只有當(dāng)該卡表元素未被標(biāo)記過時才將其標(biāo)記為變臟
• 在 JDK 7 之后，HotSpot 虛擬機(jī)增加了一個新的參數(shù) -XX：+UseCondCardMark，用來決定是否開啟卡表更新的條件判斷。

3.6 并發(fā)的可達(dá)性分析

三色標(biāo)記（Tri-color Marking）:

• 白色：表示對象尚未被垃圾收集器訪問過。顯然在可達(dá)性分析剛剛開始的階段，所有的對象都是白色的，若在分析結(jié)束的階段，仍然是白色的對象，即代表不可達(dá)。
• 黑色：表示對象已經(jīng)被垃圾收集器訪問過，且這個對象的所有引用都已經(jīng)掃描過。黑色的對象代表已經(jīng)掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對象不可能直接（不經(jīng)過灰色對象）指向某個白色對象。
• 灰色：表示對象已經(jīng)被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過。

關(guān)于可達(dá)性分析的掃描過程:

初始狀態(tài)： 只有 GC Roots 是黑色，注意圖中的箭頭，引用是有向的，對象只有被黑色對象引用才能活，否則，如果沒有黑色對象引用它，它再怎么引用其他對象都是會消亡的。看以下圖示：

image

掃描過程中，以灰色為波峰的波紋從黑向白推進(jìn)，灰色對象是黑、白對象的分界線

image

掃描順利完成，此時黑色對象是可存活對象，白色對象是已消亡可回收對象。

image

但用戶線程在標(biāo)記進(jìn)行時并發(fā)修改了引用關(guān)系，掃描就不會如此順利完成了。
如：在波紋推進(jìn)過程中，正在掃描的灰色對象的一個引用被切斷了，同時原來的引用對象又與掃描過的黑色對象建立了引用關(guān)系

image

又譬如,這種切斷后重新被黑色對象引用的對象可能是原有引用鏈中的一部分。
由于黑色對象不會重新掃描,這將導(dǎo)致掃描結(jié)束后出現(xiàn)兩個被黑色對象引用的對象仍是白色,這個對象就會消失,這就很危險了

image

并發(fā)掃描時的對象消失問題：

• 賦值器插入了一條或多條從黑色對象到白色對象的新引用；
• 賦值器刪除了全部從灰色對象到該白色對象的直接或間接引用。

解決：只需破壞這兩個條件的任意一個即可

• 增量更新（Incremental Update）：增量更新要破壞的是第一個條件，當(dāng)黑色對象插入新的指向白色對象的引用關(guān)系時，就將這個新插入的引用記錄下來，等并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關(guān)系中的黑色對象為根，重新掃描一次。這可以簡化理解為，黑色對象一旦新插入了指向白色對象的引用之后，它就變回灰色對象了。
• 原始快照（Snapshot At The Beginning，SATB）：原始快照要破壞的是第二個條件，當(dāng)灰色對象要刪除指向白色對象的引用關(guān)系時，就將這個要刪除的引用記錄下來，在并發(fā)掃描結(jié)束之后，再將這些記錄過的引用關(guān)系中的灰色對象為根，重新掃描一次。這也可以簡化理解為，無論引用關(guān)系刪除與否，都會按照剛剛開始掃描那一刻的對象圖快照來進(jìn)行搜索。

以上無論是對引用關(guān)系記錄的插入還是刪除，虛擬機(jī)的記錄操作都是通過寫屏障實現(xiàn)的。在 HotSpot 虛擬機(jī)中，增量更新和原始快照這兩種解決方案都有實際應(yīng)用，譬如，CMS 是基于增量更新來做并發(fā)標(biāo)記的，G1、Shenandoah 則是用原始快照來實現(xiàn)。

參考

• 《深入理解 Java 虛擬機(jī)：JVM 高級特性與最佳實踐第三版》