垃圾回收算法詳談

目錄

• 分代收集理論
• 标記-清除算法
• 标記-複制算法
• 标記-整理算法

分代收集理論

現在大多數的經典垃圾收集器，都遵循分代垃圾回收，就是将記憶體分為新生代和舊生代進行分代收回。這樣的設計是建立在三種假說上

弱分代假說：絕大數的對象都是朝生夕滅的

強分代假說：熬過越多次的垃圾收集過程的對象就越難消亡

跨代引用假說：跨代引用相對于同代引用來說僅占極少數

根據前兩條的假說，就不難了解分代垃圾設計的原因。如果一個區域的對象都是朝生夕滅的話，那麼把他們集中在一起，每次都關注如何保留少量的存活對象而不是去标記那些要消亡的對象，就能以較小的代價回收大量的垃圾。而如果多次進行垃圾回收卻仍未消亡的對象，那麼也将它們集中在一個區域進行管理，在這個區域用比較低的頻率進行垃圾回收。這樣就能同時兼顧時間消耗和記憶體的利用。

根據這兩條假說，設計者至少會将記憶體劃分為兩個區域，一個是新生代，用于存儲一開始建立的對象，它們絕大數都逃不了一輪垃圾回收，一個是老年代，存儲經過多次垃圾回收後仍存活的對象。但是，分代收集并不是簡單的将區域劃為為兩塊那麼簡單。這是因為對象之間不是孤立的，它們跨代引用。對于跨代引用，假如新生代的對象被老年代的對象引用。那麼每次進行垃圾收集時，還需要周遊老年代的對象來找出新生代裡存活對象，反之亦然。這樣對性能是極大的消耗。是以這就需要第三條假說。依據這樣的假說，我們就不需要為少量的引用去掃描整個老年代，隻需要在新生代設計一個全局的資料結構，标記老年代哪塊記憶體引用新生代的對象，在進行新生代垃圾回收時隻掃描那一塊的記憶體。

标記-清除算法

最早的也是最基礎的垃圾回收算法。說它基礎是因為後續的垃圾回收算法都是以這個為基礎的。該算法分别兩個步驟，為标記和清除步驟。标記階段可以标記存活的對象，那麼清除階段就清除未标記的對象。也能标記未存活的對象，清除階段就清除已标記的對象。

這個算法有兩個缺點。第一個是效率不穩定。如果堆中存在大量的對象，那麼标記和清除的效率就很低。也就是說，它的效率會随着對象的增長而減低。第二個缺點就是它會産生大量的記憶體碎片，記憶體碎片太多會導緻大的對象找不到連續的足夠的記憶體而不得不提前進行新一輪的垃圾回收。

标記-複制算法

标記複制算法是将記憶體分為兩半，每次隻使用一塊。當其中一塊滿了後，觸發垃圾回收。它将記憶體裡的存活的對象複制到新的一塊記憶體上，然後把原有的那一半記憶體整塊清除。由于每次清除的都是整塊對象，是以也沒有記憶體碎片問題，簡單高效，速度也很快。不足的之處是需要浪費一半的記憶體。

現在的虛拟機的新生代大多采用這種算法。由于新生代的每次都能回收98%的垃圾，是以它們并不需要按照1比1的比例劃分新生代的。

新生代按照8:1:1的比例劃分為Eden區，和兩塊Survivor區。每次隻是用一塊Eden和一塊Survivor區。進行垃圾回收時，将存活的對象複制到另一塊Survivor區，然後清除整塊Eden區和被使用的Survivor區。這樣隻有10%的新生代會被浪費。

标記-整理算法

老年代不适用與标記複制，因為老年代的對象大多數存活，那麼需要複制比較多的對象進而導緻效率降低，并且對象多，需要額外浪費比較多的記憶體空間。

針對老年代的對象存亡特性，出現了标記整理算法。标記過程和标記清除算法一樣，後續的過程是先将所有的存活對象往記憶體一一端移動，然後再清除掉邊界外所有的記憶體。

标記整理和标記清除的本地差別就是标記整理是移動式的，标記清除是非移動式的。它們各有利弊。

标記整理的優點當然就是不會産生記憶體碎片。缺點則是在移動對象時，會産生STW（stop the world），就是使用者的程式都會暫停。

從停頓時間上來看，标記整理延遲長，标記清除延遲短。但從吞吐量上，标記整理吞吐量比标記清除大。有些關注吞吐量的垃圾收集器是基于标記整理的。有些關注延遲的垃圾收集器是标記清除的。

當然也有些垃圾收集器兩者皆有。一開始采用标記清除，當碎片太多時換成标記整理