一、垃圾收集演算法

由於垃圾收集演算法的實現涉及大量的程式細節，而且各個平臺的虛擬機操作記憶體的方法又各不相同，因此本節不打算過多地討論演算法的實現，只是介紹幾種演算法的思想及其發展過程。

垃圾收集演算法概要

1、 標記-清除演算法

標記-清除演算法最基礎的收集演算法是“標記-清除”（Mark-Sweep）演算法，演算法分為“標記”和“清除”兩個階段：首先標記出所有需要回收的對象，在標記完成後統一回收所有被標記的對象，它的標記過程其實在前一節講述對象標記判定時已經介紹過了。之所以說它是最基礎的收集演算法，是因為後續的收集演算法都是基於這種思路並對其不足進行改進而得到的。它的主要不足有兩個：一個是效率問題，標記和清除兩個過程的效率都不高；另一個是空間問題，標記清除之後會產生大量不連續的記憶體碎片，空間碎片太多可能會導致以後在程式運行過程中需要分配較大對象時，無法找到足夠的連續記憶體而不得不提前觸發另一次垃圾收集動作。標記—清除演算法的執行過程如圖3-2所示。

圖3-2“標記-清除”演算法示意圖

2、複製演算法

為瞭解決效率問題，一種稱為“複製”（Copying）的收集演算法出現了，它將可用記憶體按容量劃分為大小相等的兩塊，每次只使用其中的一塊。當這一塊的記憶體用完了，就將還存活著的對象複製到另外一塊上面，然後再把已使用過的記憶體空間一次清理掉。這樣使得每次都是對整個半區進行記憶體回收，記憶體分配時也就不用考慮記憶體碎片等複雜情況，只要移動堆頂指針，按順序分配記憶體即可，實現簡單，運行高效。只是這種演算法的代價是將記憶體縮小為了原來的一半，未免太高了一點。複製演算法的執行過程如圖3-3所示。

現在的商業虛擬機都採用這種收集演算法來回收新生代，IBM公司的專門研究表明，新生代中的對象98%是“朝生夕死”的，所以並不需要按照1∶1的比例來劃分記憶體空間，而是將記憶體分為一塊較大的Eden空間和兩塊較小的Survivor空間，每次使用Eden和其中一塊Survivor[插圖]。當回收時，將Eden和Survivor中還存活著的對象一次性地複製到另外一塊Survivor空間上，最後清理掉Eden和剛纔用過的Survivor空間。HotSpot虛擬機預設Eden和Survivor的大小比例是8∶1，也就是每次新生代中可用記憶體空間為整個新生代容量的90%（80%+10%），只有10%的記憶體會被“浪費”。

圖3-3 複製演算法示意圖

3、標記-整理演算法

“標記-整理”（Mark-Compact）演算法，標記過程仍然與“標記-清除”演算法一樣，但後續步驟不是直接對可回收對象進行清理，而是讓所有存活的對象都向一端移動，然後直接清理掉端邊界以外的記憶體，“標記-整理”演算法的示意圖如圖3-4所示。

圖3-4“標記-整理”演算法示意圖

4、分代收集演算法

當前商業虛擬機的垃圾收集都採用“分代收集”（Generational Collection）演算法，根據對象存活周期的不同將記憶體劃分為幾塊。一般是把Java堆分為新生代和老年代，這樣就可以根據各個年代的特點採用最適當的收集演算法。在新生代中，每次垃圾收集時都發現有大批對象死去，只有少量存活，那就選用複製演算法，只需要付出少量存活對象的複製成本就可以完成收集。而老年代中因為對象存活率高、沒有額外空間對它進行分配擔保，就必須使用“標記—清理”或者“標記—整理”演算法來進行回收。

二、HotSpot的演算法實現

HotSpot的演算法實現概要

1、枚舉根節點

由於目前的主流Java虛擬機使用的都是準確式GC（這個概念在第1章介紹Exact VM對Classic VM的改進時講過），所以當執行系統停頓下來後，並不需要一個不漏地檢查完所有執行上下文和全局的引用位置，虛擬機應當是有辦法直接得知哪些地方存放著對象引用。

在HotSpot的實現中，是使用一組稱為OopMap的數據結構來達到這個目的的，在類載入完成的時候，HotSpot就把對象內什麼偏移量上是什麼類型的數據計算出來，在JIT編譯過程中，也會在特定的位置記錄下棧和寄存器中哪些位置是引用。這樣，GC在掃描時就可以直接得知這些信息了。

2、 安全點

HotSpot沒有為每條指令都生成OopMap，只是在“特定的位置”記錄了這些信息，這些位置稱為安全點（Safepoint），即程式執行時並非在所有地方都能停頓下來開始GC，只有在到達安全點時才能暫停。

2.1 GC時中斷方式

如何在GC發生時讓所有線程（這裡不包括執行JNI調用的線程）都“跑”到最近的安全點上再停頓下來。這裡有兩種方案可供選擇：搶先式中斷（Preemptive Suspension）和主動式中斷（Voluntary Suspension）

2.1.1 搶先式中斷（Preemptive Suspension）

搶先式中斷不需要線程的執行代碼主動去配合，在GC發生時，首先把所有線程全部中斷，如果發現有線程中斷的地方不在安全點上，就恢複線程，讓它“跑”到安全點上。現在幾乎沒有虛擬機實現採用搶先式中斷來暫停線程從而響應GC事件。

2.1.2 主動式中斷（Voluntary Suspension）

主動式中斷的思想是當GC需要中斷線程的時候，不直接對線程操作，僅僅簡單地設置一個標誌，各個線程執行時主動去輪詢這個標誌，發現中斷標誌為真時就自己中斷掛起。輪詢標誌的地方和安全點是重合的，另外再加上創建對象需要分配記憶體的地方。

3、安全區域

使用Safepoint似乎已經完美地解決瞭如何進入GC的問題，但實際情況卻並不一定。Safepoint機制保證了程式執行時，在不太長的時間內就會遇到可進入GC的Safepoint。但是，程式“不執行”的時候呢？所謂的程式不執行就是沒有分配CPU時間，典型的例子就是線程處於Sleep狀態或者Blocked狀態，這時候線程無法響應JVM的中斷請求，“走”到安全的地方去中斷掛起，JVM也顯然不太可能等待線程重新被分配CPU時間。對於這種情況，就需要安全區域（Safe Region）來解決。

安全區域是指在一段代碼片段之中，引用關係不會發生變化。在這個區域中的任意地方開始GC都是安全的。我們也可以把Safe Region看做是被擴展了的Safepoint。

線上程執行到Safe Region中的代碼時，首先標識自己已經進入了Safe Region，那樣，當在這段時間里JVM要發起GC時，就不用管標識自己為Safe Region狀態的線程了。線上程要離開Safe Region時，它要檢查系統是否已經完成了根節點枚舉（或者是整個GC過程），如果完成了，那線程就繼續執行，否則它就必須等待直到收到可以安全離開Safe Region的信號為止。