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-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所示。
回收後應用程式繼續運行並產生垃圾，在複製算法第二次執行前Eden和S1都有活著的對象，在複製算法執行後，Eden和S1裡面活著的對象都被放入S0區，如圖2-7所示。
雖然優化後的算法可以提高內存的利用率，但是帶來了額外的複雜性。
例如，S0可能無法存儲所有活躍對象的情況（這在標準的半代回收中不會出現，活躍對象不可能超過使用空間的最大值）。通常有兩種方法處理S0溢出的情況：使用額外的預留空間保存溢出的對象，這部分空間需要預留；動態調整S0和S1的大小，保證S0和S1在GC執行時滿足對象轉移的需要，這意味著Eden、S0/S1的邊界並不固定，在實現時需要額外處理。這兩種方法在JVM中均有體現。另外JVM實現了分代算法，在某一個代中執行複製算法時，如果出現S0或S1溢出，則可以跨代使用其他代的內存。
標記清除算法
複製算法的空間利用率有限，但效率較高，並且GC執行過程包含了壓縮，所以不存在內存碎片化問題。另外一種GC算法是標記清除，對於內存的管理可以使用鍊表的方式，當應用需要內存時從鍊表中獲得一塊空閒空間並使用，當GC執行時首先遍歷整個空間中所有的活躍對象，然後再次遍歷內存空間，將空間中所有非活躍對象釋放並加入空閒鍊表中。以圖2-4的內存狀態為例，標記清除算法執行結束後的示意圖如圖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所示。
由於標記壓縮算法執行效率不高，因此通常作為GC的兜底算法。標記壓縮在JVM中也有多種實現，分別是串行實現、並行實現。在第3～5章中都會介紹標記壓縮算法。
分代回收
3種GC算法各有優缺點，實際中需要根據需求選擇不同的實現。除此以外還可以將內存空間劃分成多個區域，每個區域採用一種或者多種算法協調管理。這個思路來自人們對應用程式運行時的觀察和分析。根據研究發現，大多數應用運行時分配的內存很快會被使用，然後就釋放，這意味著為這樣的對象劃分一塊內存空間，然後使用複製算法效率會很高，因為對象的生命周期很短，在GC執行時大多數對象都已經死亡，只需要標記/複製少量的對象就可以完成內存回收。現代垃圾回收實現中都會根據對象的生命周期劃分將內存劃分成多個代進行管理，最常見的是將內存劃分為兩個代：新生代和老生代，其中新生代主要用於應用程式對象的分配，一般採用複製算法進行管理；老生代存儲新生代執行GC後仍然存活的對象，一般採用標記清除算法管理。
基於對象生命周期管理，有弱分代理論假設和強分代理論假設兩種：
1）弱分代理論假設：假定對象分配內存後很快使用，並且使用後很快就不再使用（內存可以釋放）。
2）強分代理論假設：假定對象長期存活後，未來此類對象還將長期存活。
基於弱分代理論將內存管理劃分成多個空間進行管理，基於強分代理論可以優化GC執行的效率，不回收識別的長期存活對象，從而加快GC的執行效率。
值得一提的是，目前弱分代理論在高級語言中普遍得到證實和認可，但是對於強分代理論只在一些場景中適用。目前弱分代理論和強分代理論在JVM中均有體現。
雖然分代回收的思想非常簡單，但實現中有許多細節需要考慮，例如在內存分代以後，分代邊界是否可以調整？以內存劃分為兩個代為例，最簡單的實現是邊界固定，如圖2-10所示。
邊界固定的分代回收算法實現簡單，可以通過固定邊界快速判斷對象處於哪個空間，管理代際引用也比較簡單。但是邊界固定的分代方法需要JVM使用者提前設定好每個代的大小，這對於JVM使用者來說並不容易，實際使用中可能需要使用者不斷調整邊界，以便內存代的劃分和內存使用方式一致。
一種很自然的優化是將邊界設計為浮動的，浮動可以解決使用者需要分代劃分的問題，由JVM根據程序使用內存的情況自動調整內存代的劃分。邊界浮動的示意圖如圖2-11所示。
邊界浮動後可以縮小新生代也可以擴大新生代，一般來說縮小新生代會導致GC的停頓時間減少、吞吐量減少，如圖2-12所示。而擴大新生代會導致GC的停頓時間增加、吞吐量增加，如圖2-13所示。
浮動邊界對JVM使用者很友好，但是回收算法的實現難度增加了很多。在JVM中所有的垃圾回收器實現中只有一款實現了邊界浮動，但該功能因為存在一些bug，已在JDK 15中被移除，關於如何實現邊界浮動將在後面詳細介紹。
除了代際邊界劃分的問題，在分代中還需要考慮分代的大小、代際引用管理等問題。這些問題將在後續具體垃圾回收器的實現中介紹。
本文給大家講解的內容是Java虛擬機和垃圾回收基礎知識：GC算法概述
- 下篇文章給大家講解的內容是JVM中垃圾回收相關的基本知識：GC的根
- 感謝大家的支持！