轉載：http://blog.csdn.net/tjiyu/article/details/53983064
?
下面先來了解Java虛擬機垃圾回收的幾種常見算法：標記-清除算法、復制算法、標記-整理算法、分代收集算法、火車算法，介紹它們的算法思路，有什么優點和缺點，以及主要應用場景。
1、標記-清除算法
???????標記-清除（Mark-Sweep）算法是一種基礎的收集算法。
1、算法思路
???????"標記-清除"算法，分為兩個階段：
（A）、標記
??????首先標記出所有需要回收的對象；
???????標記過程如《Java虛擬機垃圾回收(一) 基礎》"2-4、判斷對象生存還是死亡"中所述--分為兩個標記過程（詳細請參考前文）：
（1）、第一次標記
???????在可達性分析后發現對象到GC Roots沒有任何引用鏈相連時，被第一次標記；
???????并且進行一次篩選：此對象是否必要執行finalize()方法；
???????對有必要執行finalize()方法的對象，被放入F-Queue隊列中；????
（2）、第二次標記
???????GC將對F-Queue隊列中的對象進行第二次小規模標記；
???????在其finalize()方法中重新與引用鏈上任何一個對象建立關聯，第二次標記時會將其移出"即將回收"的集合；
???????對第一次被標記，且第二次還被標記（如果需要，但沒有移出"即將回收"的集合），就可以認為對象已死，可以進行回收。
（B）、清除
??????兩次標記后，還在"即將回收"集合的對象將被統一回收；
???????執行過程如下圖：
2、優點
???????基于最基礎的可達性分析算法，它是最基礎的收集算法；
???????而后續的收集算法都是基于這種思路并對其不足進行改進得到的；
3、缺點
???????主要有兩個缺點：
（A）、效率問題
???????標記和清除兩個過程的效率都不高；
（B）、空間問題
???????標記清除后會產生大量不連續的內存碎片；
???????這會導致分配大內存對象時，無法找到足夠的連續內存；
???????從而需要提前觸發另一次垃圾收集動作；
4、應用場景
??????針對老年代的CMS收集器；
2、復制算法
???????"復制"（Copying）收集算法，為了解決標記-清除算法的效率問題；
1、算法思路
???????（A）、把內存劃分為大小相等的兩塊，每次只使用其中一塊；
???????（B）、當一塊內存用完了，就將還存活的對象復制到另一塊上（而后使用這一塊）；
???????（C）、再把已使用過的那塊內存空間一次清理掉，而后重復步驟2；????
??????執行過程如下圖：
2、優點
???????這使得每次都是只對整個半區進行內存回收；
???????內存分配時也不用考慮內存碎片等問題（可使用"指針碰撞"的方式分配內存）；
??????實現簡單，運行高效；
???????（關于"指針碰撞"請參考《Java對象在HotSpot虛擬機中的創建過程》）
3、缺點
（A）、空間浪費
??????可用內存縮減為原來的一半，太過浪費（解決：可以改良，不按1:1比例劃分）；
（B）、效率隨對象存活率升高而變低
??????當對象存活率較高時，需要進行較多復制操作，效率將會變低（解決：后面的標記-整理算法）；
4、應用場景
??????現在商業JVM都采用這種算法（通過改良缺點1）來回收新生代；
新生代：新建的對象都放到新生代
老年代：多次回收沒有被回收的對象或者大對象
??????如Serial收集器、ParNew收集器、Parallel Scavenge收集器、、G1（從局部看）；
5、HotSpot虛擬機的改良算法
（A）、弱代理論
???????分代垃圾收集基于弱代理論（weak generational hypothesis），具體描述如下：
???????（1）、大多數分配了內存的對象并不會存活太長時間，在處于年輕代時就會死掉；
???????（2）、很少有對象會從老年代變成年輕代；
???????其中IBM研究表明：新生代中98%的對象都是"朝生夕死"；
????????所以并不需要按1:1比例來劃分內存（解決了缺點1）；
（B）、HotSpot虛擬機新生代內存布局及算法
??????????????????????（1）、將新生代內存分為一塊較大的Eden空間和兩塊較小的Survivor空間；
??????????????????????（2）、每次使用Eden和其中一塊Survivor；
??????????????????????（3）、當回收時，將Eden和使用中的Survivor中還存活的對象一次性復制到另外一塊Survivor；
??????????????????????（4）、而后清理掉Eden和使用過的Survivor空間；
??????????????????????（5）、后面就使用Eden和復制到的那一塊Survivor空間，重復步驟3；
?????????默認Eden：Survivor=8:1，即每次可以使用90%的空間，只有一塊Survivor的空間被浪費；
（C）、分配擔保
???????如果另一塊Survivor空間沒有足夠空間存放上一次新生代收集下來的存活對象時，這些對象將直接通過分配擔保機制（Handle Promotion）進入老年代；
???????分配擔保在以后講解垃圾收集器執行規則時再詳解；
???????更多請參考：http://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/generations.html#sthref16
3、標記-整理算法
???????"標記-整理"（Mark-Compact）算法是根據老年代的特點提出的。
1、算法思路
（1）、標記
??????標記過程與"標記-清除"算法一樣；
（2）、整理
???????但后續不是直接對可回收對象進行清理，而是讓所有存活的對象都向一端移動；
???????然后直接清理掉端邊界以外的內存；
執行過程如下圖：
2、優點
（A）、不會像復制算法，效率隨對象存活率升高而變低
???????老年代特點：
???????對象存活率高，沒有額外的空間可以分配擔保；
???????所以老年代一般不能直接選用復制算法算法；
???????而選用標記-整理算法；
（B）、不會像標記-清除算法，產生內存碎片
???????因為清除前，進行了整理，存活對象都集中到空間一側；
3、缺點
???????主要是效率問題：除像標記-清除算法的標記過程外，還多了需要整理的過程，效率更低；
4、應用場景
???????很多垃圾收集器采用這種算法來回收老年代；
??????如Serial Old收集器、G1（從整體看）；
4、分代收集算法
???????"分代收集"（Generational Collection）算法結合不同的收集算法處理不同區域。
1、算法思路
???????基于前面說的弱代理論，其實并沒有什么新的思想；
???????只是根據對象存活周期的不同將內存劃分為幾塊；
???????這樣就可以根據各個年代的特點采用最適當的收集算法；
???????一般把Java堆分為新生代和老年代；
（A）、新生代
???????每次垃圾收集都有大批對象死去，只有少量存活；
???????所以可采用復制算法；
（B）、老年代
???????對象存活率高，沒有額外的空間可以分配擔保；
??????使用"標記-清理"或"標記-整理"算法；
??????結合上面對新生代的內存劃分介紹和上篇文章對Java堆的介紹，可以得出HotSpot虛擬機一般的年代內存劃分，如下圖：
2、優點??????
???????可以根據各個年代的特點采用最適當的收集算法；?
3、缺點??????
???????仍然不能控制每次垃圾收集的時間；4、應用場景
??????目前幾乎所有商業虛擬機的垃圾收集器都采用分代收集算法；
??????如HotSpot虛擬機中全部垃圾收集器：Serial、ParNew、Parallel Scavenge、Serial Old、Parallel Old、CMS、G1（也保留）；
