GC算法：基礎
在介紹GC算法在實際場景中的實作之前，我們先定義一些必要的術語，以及GC算法的基本準則。具體的細節會因收集器的不同而稍有差別，但是基本上來說，所有的收集器會關注以下兩個方面：
- 找出所有仍然存活的對象
- 清除掉其他所有非存活對象（被認為是dead，并且不會再被使用的對象）
在所有的收集器内部，第一步實作的均是：周遊出所有存活的對象。由标記（Marking）程序完成。
标記所有可達對象
在JVM中，任何主流GC算法均會以找出所有存活對象為開始。這個概念的解釋可以參考下圖：
首先，GC定義某些特定的對象為Garbage Collection Roots，一些典型的GC roots如：
- 目前執行的方法中的本地變量以及輸入參數
- 目前活躍的線程
- 已載入的類中的靜态區域
- JNI（Java Native Interface）引用
下一步，GC周遊記憶體裡的整個對象圖（whole object graph），從GC roots開始，周遊它們引用的所有對象。任何被GC通路到的對象會被标注為存活。
在上圖中，藍色的圓圈表示存活的對象。當Marking階段完成時，所有存活的對象會被标注。所有其他對象（上圖中的灰色圓圈）便是無法由GC roots通路到的對象，也就是說，你的應用無法再使用這些不可達的對象。這種對象被認為是垃圾，GC在清除它們時會經曆以下階段：
- 應用中的線程需要被停止，以便讓Marking階段正常運作。因為應用若是持續運作，則JVM裡的對象可能随時在變化，這樣就不足以擷取到精确的資訊。這個場景被稱為一個安全點（safe point），它造成的結果便是一個Stop The World pause。Safe point可被不同的原因觸發，但是到現目前為止，GC是引入safe point最常見的原因
- 這個暫停持續的時間并不取決于堆記憶體裡對象的總數量，也不取決于堆記憶體的大小。它是由存活的對象個數決定的。是以，增加堆記憶體的大小并不會直接影響marking階段的持續時間
Removing Unused Objects
不同的GC算法中，清楚unused objects的方式稍有不同。但是所有這類GC算法基本上可以分為以下三組：
- Sweeping
- Compacting
- Copying
Mark and Sweep 算法對于垃圾使用了最簡單的方式：忽略掉這些對象。具體的說，就是在marking階段完成後，所有沒被通路到的對象所占據的空間，均被視為可用的空間。并可以被用于為新的對象配置設定。
這種方式使用到一種名為free-list的結構來記錄每個空閑的區域（region）以及它的大小。free-list的管理方法會增加對象配置設定（object allocation）的開銷。并且，它會有一個缺點：可能會存在大量的空閑region，但是如果單個region的空間不足以滿足一個allocation，則這個allocation也會失敗，并傳回OutOfMemoryError的報錯。
Compact
Mark-Sweep-Compact算法解決了Mark and Sweep的缺點。它将所有被标注為存活的對象移動到記憶體區域的起始。這種方法的缺點是增加了每次GC暫停的時間，因為我們需要将所有的對象移動到一個新的地方，并且更新它們的引用。它的優點也顯而易見：在這個compacting操作完成後，對于新對象的配置設定會非常容易。使用這種方式，空餘空間的位址随時可擷取，并且也不會有碎片的問題。
Copy
Mark and Copy算法與Mark and Compact非常接近，因為它們都會重新allocate所有存活的對象。比較重要的不同點是：Mark and Copy 重配置設定的目标空間在一個不同的記憶體區域。它的優點是可以與Marking階段并行執行。缺點是它需要一個足夠大的額外記憶體區域，以支援所有的存活對象。
References：
https://plumbr.io/handbook/garbage-collection-algorithms