深入理解JVM（③）各種垃圾收集演算法
前言
從如何判定對象消亡的角度出發，垃圾收集演算法可以劃分為「引用計數式垃圾收集」（Reference Counting GC）和「追蹤式垃圾收集」（Tracing GC）兩大類，這兩類也常被稱作「直接垃圾收集」和「間接垃圾收集」。由於束流Java虛擬機中使用 的都是「追蹤式垃圾收集」，所以後續介紹的垃圾收集演算法都是屬於追蹤式的垃圾收集。
分代式收集理論
當前商業虛擬機的垃圾收集器，大多數都遵循了「分代收集」的理論進行設計。
主要簡歷在兩個分代假說之上：
1、弱分代假說：絕大多數對象都是「朝生夕滅」的。
2、強分代假說：熬過越多此垃圾收集過程的對象就越難以消亡。
這兩個分代假說奠定了多款常用的垃圾收集器的一致設計原則：收集器應該將Java堆劃分出不同的區域，然後將回收對象依據其年齡（對象熬過垃圾收集過程的次數）分配到不同的區域之中存儲。
把分代收集理論具體放到現在商用的Java虛擬機里，設計者一般至少會把Java堆劃分為新生代（Young Generation） 和 老年代（Old Generation兩個區域。在新生代中，每次垃圾收集時都有大批對象死去，而每次回收後存活的少量對象，將會逐步晉陞到老年代中存放。
標記-清除演算法
標記-清除演算法，分為「標記」和「清除」兩個階段：首先標記所有需要回收的對象，標記完成後，統一回收掉所有被標記的對象，也可以反過來，標記存活的對象，統一回收所有未被標記的對象。
這個演算法有兩個主要的缺點：
第一個是執行效率不穩定，如果Java堆中有大部分是需要回收的對象，這個會進行大量標記和清除動作，導致標記和清除兩個過程的執行效率隨著對象數量增長而降低。
第二個是記憶體碎片化問題，標記、清除之後會產生大量不連續的記憶體碎片，空間碎片太多會導致當需要大對象時找不到足夠的連續記憶體，而提前觸發另一次垃圾收集動作。
因為這兩個缺點的原因，才會產生後續一些針對於修復這兩個缺點的演算法。
標記清除演算法示意圖：
標記複製演算法
標記複製演算法也被簡稱Wie複製演算法，為了解決標記清除演算法面對大量可回收對象時執行效率低的問題，而產生的一種稱為「半區複製」的垃圾收集演算法。
原理是：將可用記憶體按容量劃分為大小相等的兩塊，每次只使用其中的一塊當這一塊記憶體用完了，就將還存活著的對象複製到另外一塊上面，然後再把已使用過的記憶體空間一次清理掉。
這種演算法不用考慮空間碎片化，只需要移動堆指針，按順序分配即可，實現簡單，運行高效，但缺點也是顯而易見的，就是將可用記憶體縮小了原來的一半。
標記複製演算法示意圖：
由於新生代里的對象「朝生夕滅」，針對這個特點，又產生了一種更優化的半區複製分代策略，稱為「Appel式回收」。具體做法是把新生代分為一塊較大的Eden空間和兩塊較小的Survivor空間，每次分配記憶體只是用Eden和其中一塊Survivor。當發生垃圾收集時，將Eden和Survivor中任然存活的對象一次性複製到另外一塊Survivor空間上，然後直接清理掉Eden和Survivor空間。
HotSpot虛擬機默認Eden和Survivor的大小比例是8：1，也就是說每次可利用的空間為新生代的90%，只有10%的空間會暫時「浪費」。
如果另外一塊兒Survivor沒有足夠的空間存放存活的對象了，這些對象將通過分配擔保機制直接進入到老年代。
標記整理演算法
標記複製演算法在對象存活率較高時就要進行較多的複製操作，效率將會降低。更關鍵的是，如果不浪費50%的空間，就需要有額外的空間進行分配擔保，以應對被使用的記憶體中所有對象都100%存活的極端情況，所以在老年代一般不能直接選用這種演算法。
針對老年代對象的存亡特徵，產生了另外一種有針對性的「標記整理」演算法。標記的過程和「標記-清除」演算法一樣，也是判斷對象是否屬於垃圾的過程。但後續步驟是讓所有存活的對象都向記憶體空間一端移動，然後直接清理掉邊界以外的記憶體。
標記整理演算法示意圖：
在這種演算法中，在移動存活對象，尤其是在老年代這種每次回收都有大量對象存活區域，移動存活對象並更新所有引用這些對象的地方將會是一種極為負重的操作，而且這種移動操作必須在暫停用戶應用程式才能進行（也就是「Stop The World」）。但是不移動又會造成記憶體空間碎片化。所以各有利弊，從垃圾收集的停頓時間來看，不移動對象停頓時間更短，但從整個程式的吞吐量來看，移動對象會更划算。所以要依情況而定。
還有一種「和稀泥」的解決方案，就是平時採用標記清除演算法，直到記憶體空間碎片化程度已經大到影響對象分配時，再採用標記整理演算法收集一次，以獲得規整的記憶體空間。
