程式設計師真的有必要把GC演算法好好過一遍，因為它是進大廠必備的

GC演算法概述

最早的GC演算法可以追溯到20世紀60年代，但到目前為止，GC的基本演算法沒有太多的創新，可以分為複製演算法（Copying GC）、標記清除（MarkSweep GC）和標記壓縮（Mark-Compact GC）。近些年推出的GC演算法也都是在基礎演算法上針對一些場景進行最佳化，所以非常有必要理解基礎的GC演算法。

複製演算法

複製演算法是把堆空間分為兩個部分，分別稱為From Space（From空間）和To Space（To空間）。其中From空間用於應用的記憶體分配，To空間用於執行GC時活躍物件的轉移。GC執行時From空間中的活躍物件都會轉移到To空間中，GC完成後From和To交換，From空間中剩餘尚未使用的空間繼續用於應用的記憶體分配，To空間用於下一次GC活躍物件轉移。下面透過示意圖演示。假設物件標記如圖2-4所示。

圖2-4 複製演算法執行前記憶體空間狀態

複製演算法執行之後，記憶體示意圖如圖2-5所示。

圖2-5 複製演算法執行後記憶體空間狀態

複製演算法的特點可以總結為：

1）複製完成後，To空間中的物件是按照堆空間的記憶體順序分配的，也就是說複製完成後，To空間不存在記憶體碎片的問題。

2）複製完成後，From空間和To空間交換，應用程式新的物件都分配在From空間剩餘的空間中（圖2-5為了演示覆制過程，沒有將From和To交換）。

由於複製演算法涉及物件的移動，因此必須儲存物件移動前後的位置關係（確保物件只轉移一次），在複製演算法中當物件轉移成功後，通常把轉移後的地址儲存在物件頭中，當再次轉移相同物件時可以透過物件頭的資訊獲得轉移後的物件，無須再次轉移，這也意味著複製演算法除了轉移物件以外，還需要在原物件轉移成功後在原物件的物件頭中設定物件轉移後的地址。可以想象，當多執行緒並行執行復制演算法時，需要考慮同步，防止多個執行緒同時轉移一個物件，通常使用無鎖的原子指令來保證物件僅能成功轉移一次。

複製演算法通常只需要遍歷From空間一次就可以完成所有活躍物件的轉移，所以物件的標記和轉移一次性完成。由於轉移中需要遍歷活躍物件的成員變數，因此演算法實現中需要一個額外的資料結構儲存待遍歷的物件，當然這個額外的資料結構可以是佇列或者棧。Cheney提出的複製演算法藉助To空間而

不需要

額外的資料結構，該演算法在後面詳細介紹。

另外，複製演算法還有一個最大的問題：空間利用率不夠高。如圖2-4和圖2-5所示，空間利用率只有50%。為了解決空間利用率的問題，JVM對複製演算法進行了最佳化，設定了3個分割槽，分別是Eden、Survivor 0（簡稱S0）和Survivor 1（簡稱S1）。在新的最佳化實現中，Eden用於新物件的分配，S0和S1儲存複製演算法時標記活躍物件。這個最佳化的依據是，應用程式分配的物件很快就會死亡，在GC回收時活躍物件佔比一般都很小，所以不需要將一半空間用於物件的轉移，只需使用很少的空間用於物件的轉移，S0和S1加起來通常小於整個空間的20%就能儲存轉移後的物件。下面演示一下新的最佳化演算法的執行過程。

新分配的物件都放在Eden區，S0和S1分別是兩個存活區。

複製演算法

第一次執行前S0和S1都為空，在

複製演算法執行

後，Eden和S0裡面的活躍物件都放入S1區，如圖2-6所示。

圖2-6 複製演算法第一次執行

回收後應用程式繼續執行併產生垃圾，在複製演算法第二次執行前Eden和S1都有活著的物件，在複製演算法執行後，Eden和S1裡面活著的物件都被放入S0區，如圖2-7所示。

圖2-7 複製演算法第二次執行

雖然最佳化後的演算法可以提高記憶體的利用率，但是帶來了額外的複雜性。

例如，S0可能無法儲存所有活躍物件的情況（這在標準的半代回收中不會出現，活躍物件不可能超過使用空間的最大值）。通常有兩種方法處理S0溢位的情況：使用額外的預留空間儲存溢位的物件，這部分空間需要預留；動態調整S0和S1的大小，保證S0和S1在GC執行時滿足物件轉移的需要，這意味著Eden、S0/S1的邊界並不固定，在實現時需要額外處理。這兩種方法在JVM中均有體現。另外JVM實現了分代演算法，在某一個代中執行復制演算法時，如果出現S0或S1溢位，則可以跨代使用其他代的記憶體。

標記清除演算法

複製演算法的空間利用率有限，但效率較高，並且GC執行過程包含了壓縮，所以不存在記憶體碎片化問題。另外一種GC演算法是標記清除，對於記憶體的管理可以使用連結串列的方式，當應用需要記憶體時從連結串列中獲得一塊空閒空間並使用，當GC執行時首先遍歷整個空間中所有的活躍物件，然後再次遍歷記憶體空間，將空間中所有非活躍物件釋放並加入空閒連結串列中。以圖2-4的記憶體狀態為例，標記清除演算法執行結束後的示意圖如圖2-8所示。

圖2-8 標記清除演算法執行結束後的記憶體示意圖

標記清除演算法的記憶體使用率相對來說較高，但是還有一些具體情況需要進一步分析。由於標記清除演算法使用連結串列的方式分配記憶體，因此需要考慮分配的效率及記憶體分配時記憶體碎片化的情況。具體來說，空間連結串列中存放尚未使用或者已經釋放的記憶體塊，這些記憶體塊的大小並不相同。從空閒連結串列中請求記憶體塊時，需要遍歷連結串列找到一個記憶體塊。另外，由於連結串列中記憶體塊大小不相同，因此可能沒有和請求大小一樣的記憶體塊，此時需要找到一個比請求記憶體大的記憶體塊才能滿足應用的需要，這就需要額外的控制策略，是找到一個和請求記憶體儘可能接近（best-fit）的記憶體塊，還是找一個最大（worstfit）的記憶體塊，或者是第一個滿足需求（first-fit）的記憶體塊？不同策略導致分配時的碎片化情況有所不同。

除了考慮分配效率和分配時記憶體碎片化的情況，還需要考慮回收的情況。特別是回收時空閒記憶體的合併，是否允許相鄰的空間記憶體塊合併？合併需要花費額外的時間，同時也會影響記憶體的碎片化。

在JVM中併發標記清除採用了該演算法，為提高分配效率使用了多條連結串列及樹形連結串列，分配策略使用best-fit方法，回收時提供了5種策略並輔以預測模型控制空閒記憶體塊的合併。更多細節參考第4章。

標記壓縮演算法

標記清除演算法的記憶體利用率雖然比較高，但是有一個重要的缺點：記憶體碎片化嚴重。記憶體碎片化可能會導致無法滿足應用大記憶體塊的需求。另外一種GC演算法是標記壓縮演算法，其本質是就地壓縮記憶體空間，而不是像複製演算法那樣需要一個額外的空間。演算法可以分為以下4步：

1）遍歷記憶體空間，標記記憶體空間的活躍物件。

2）遍歷記憶體空間，計算所有活躍物件壓縮後的位置，“壓縮後”是指如果遇到死亡物件，則直接將其覆蓋。

3）遍歷記憶體空間，更新所有活躍物件成員變數壓縮後的位置。

4）遍歷記憶體空間，移動所有活躍物件到第二步計算好的位置，此時由於物件內部的成員變數已經完成更新，因此移動物件後所有的引用關係都是正確的。

在一些實現中，第二步和第三步可以藉助額外的資料結構合併成一步。

總體來說，標記壓縮演算法需要遍歷3～4次記憶體空間，雖然記憶體利用率更高，並且GC執行後不存在記憶體碎片的問題，但是因為多次遍歷記憶體空間，故演算法的執行效率不高。

仍然以圖2-4的記憶體狀態為例，標記壓縮演算法執行結束後的示意圖如圖2-9所示。

圖2-9 標記壓縮演算法執行後記憶體示意圖

由於標記壓縮演算法執行效率不高，因此通常作為GC的兜底演算法。標記壓縮在JVM中也有多種實現，分別是序列實現、並行實現。在第3～5章中都會介紹標記壓縮演算法。

分代回收

3種GC演算法各有優缺點，實際中需要根據需求選擇不同的實現。除此以外還可以將記憶體空間劃分成多個區域，每個區域採用一種或者多種演算法協調管理。這個思路來自人們對應用程式執行時的觀察和分析。根據研究發現，大多數應用執行時分配的記憶體很快會被使用，然後就釋放，這意味著為這樣的物件劃分一塊記憶體空間，然後使用複製演算法效率會很高，因為物件的生命週期很短，在GC執行時大多數物件都已經死亡，只需要標記/複製少量的物件就可以完成記憶體回收。現代垃圾回收實現中都會根據物件的生命週期劃分將記憶體劃分成多個代進行管理，最常見的是將記憶體劃分為兩個代：新生代和老生代，其中新生代主要用於應用程式物件的分配，一般採用複製演算法進行管理；老生代儲存新生代執行GC後仍然存活的物件，一般採用標記清除演算法管理。

基於物件生命週期管理，有弱分代理論假設和強分代理論假設兩種：

1）弱分代理論假設：假定物件分配記憶體後很快使用，並且使用後很快就不再使用（記憶體可以釋放）。

2）強分代理論假設：假定物件長期存活後，未來此類物件還將長期存活。

基於弱分代理論將記憶體管理劃分成多個空間進行管理，基於強分代理論可以最佳化GC執行的效率，不回收識別的長期存活物件，從而加快GC的執行效率。

值得一提的是，目前弱分代理論在高階語言中普遍得到證實和認可，但是對於強分代理論只在一些場景中適用。目前弱分代理論和強分代理論在JVM中均有體現。

雖然分代回收的思想非常簡單，但實現中有許多細節需要考慮，例如在記憶體分代以後，分代邊界是否可以調整？以記憶體劃分為兩個代為例，最簡單的實現是邊界固定，如圖2-10所示。