GC algorithm design seems like more of an art than a science – constantly trading off various parameters based on the priority of expected usage models
垃圾回收算法有很悠久的歷史。早在 20 世紀(jì) 60 年代，Lisp 就開始采用垃圾回收器來自動(dòng)管理內(nèi)存。但是出于現(xiàn)實(shí)復(fù)雜的度、效率的考慮以及程序員的執(zhí)念，使得自動(dòng)管理內(nèi)存在當(dāng)時(shí)并沒有流行起來。直到 90 年代出現(xiàn) java 大法。現(xiàn)在的大部分高級語言，如 Python、Object-C、Swift、C# 等都有相應(yīng)的垃圾回收機(jī)制，只是在回收垃圾的實(shí)現(xiàn)上有差異。
垃圾回收算法最簡單的是標(biāo)記-清除算法（Mark-Sweep），很多的算法都是基于它的。本文還將介紹
- 標(biāo)記-整理算法（Compacting Collecting）
- 交換復(fù)制算法（Semi-Space）
- 增量算法（Incremental Collecting）
- 分代算法（Generational Collecting）
介紹算法之前，我們先了解一下 GC-root
java 中對象之間的引用可以用一張有向圖來標(biāo)識(shí)。指向的是被引用的對象。
藍(lán)色圓圈表示 object， 藍(lán)色矩形表示 GC-Root
從 GC-Root 出發(fā)，可以被直接或間接引用的對象，被稱作是可達(dá)的
而無法通過 GC-Root 被引用到的對象就是不可達(dá)的
可以被當(dāng)作 GC-Root 的對象有：
- 虛擬機(jī)棧（棧幀中的本地變量表）中引用的對象。
- 方法區(qū)中類靜態(tài)屬性引用的對象。
- 方法區(qū)中常量引用的對象。
- 本地方法棧中JNI（即一般說的Native方法）引用的對象。
標(biāo)記-清除
標(biāo)記-清除算法有兩個(gè)過程：一個(gè)是標(biāo)記，一個(gè)是清除。
標(biāo)記過程就是從 GC-Root 出發(fā)，遍歷堆，標(biāo)記出不可達(dá)對象。清除過程將被標(biāo)記為不可達(dá)的對象清除。算法需要對堆做遍歷，是非常耗時(shí)的。而且清除過程完成后，可能出現(xiàn)很多的碎片。當(dāng)為大對象分配空間是，這些碎片將無法提供充足的空間，導(dǎo)致提前觸發(fā)垃圾回收
mark_sweep_collect() =
mark(root)
sweep()
mark(o) =
If mark-bit(o)=0
mark-bit(o)=1
For p in references(o)
mark(p)
EndFor
EndIf
sweep() =
o = 0
While o < N
If mark-bit(o)=1
mark-bit(o)=0
Else
free(o)
EndIf
o = o + size(o)
EndWhile
標(biāo)記-整理
標(biāo)記-整理算法可以解決標(biāo)記-清除碎片化的問題。標(biāo)記過程和標(biāo)記-清理算法是一樣的。但是在清除階段，標(biāo)記-整理算法會(huì)在清除垃圾的同時(shí)，把剩下的對象整理到一起。整理出一塊連續(xù)的空間來給新分配的對象使用
交換復(fù)制
交換復(fù)制算法把內(nèi)存空間分為大小相等的兩個(gè)部分。一個(gè)稱為 from-space，一個(gè)稱為 to-space，這兩個(gè)名稱不是固定對應(yīng)一個(gè)空間的。起始狀態(tài)，只有 from-space 存有對象，to-space 為空。新對象將分配在 to-space。算法執(zhí)行：將存活的對象，從 from-space 移動(dòng)到 to-space 。此時(shí)，from-space 對應(yīng)的空間改名為 to-space ，to-space 改名為 from-space。這樣一直都有一塊連續(xù)的空間 to-space 用于分配新對象，解決了碎片問題。但是，吐過存活的對象過多，復(fù)制效率變低。因?yàn)閷⒖臻g一分為二，所以空間使用率也降低。
initialize() =
tospace = 0
fromspace = N/2
allocPtr = tospace
allocate(n) =
If allocPtr + n > tospace + N/2
collect()
EndIf
If allocPtr + n > tospace + N/2
fail “insufficient memory”
EndIf
o = allocPtr
allocPtr = allocPtr + n
return o
collect() =
swap( fromspace, tospace )
allocPtr = tospace
root = copy(root)
copy(o) =
If o has no forwarding address
o’ = allocPtr
allocPtr = allocPtr + size(o)
copy the contents of o to o’
forwarding-address(o) = o’
ForEach reference r from o’
r = copy(r)
EndForEach
EndIf
return forwarding-address(o)
增量算法
增量算法的提出主要是為了減少一次執(zhí)行垃圾回收的時(shí)間，提高程序的響應(yīng)度。前一篇文章提到過，java 執(zhí)行垃圾回收會(huì)停止所用應(yīng)用線程，只留下 gc 執(zhí)行垃圾回收。如果碰巧這時(shí)你在寫一篇博客，那么你的輸入和修改將在這段時(shí)間內(nèi)被停止響應(yīng)。這段時(shí)間越長，用戶體驗(yàn)就越差。增量算法，每次為新對象分配空間時(shí)都會(huì)執(zhí)行一次小規(guī)模的垃圾回收。把垃圾回收分?jǐn)偟矫看畏峙淇臻g，減少了用戶等待時(shí)間。
分代收集
淺析 java 垃圾回收（一）中介紹了 HotSpot 的垃圾回收機(jī)制就是分代收集。根據(jù)對象存活周期的不同將內(nèi)存劃分為幾塊。一般是把Java堆分為新生代和老年代，這樣就可以根據(jù)各個(gè)年代的特點(diǎn)采用最適當(dāng)?shù)氖占惴āＴ谛律?，每次垃圾收集時(shí)都發(fā)現(xiàn)有大批對象死去，只有少量存活，那就選用復(fù)制算法，只需要付出少量存活對象的復(fù)制成本就可以完成收集。而老年代中因?yàn)閷ο蟠婊盥矢摺]有額外空間對它進(jìn)行分配擔(dān)保，就必須使用“標(biāo)記—清理”或者“標(biāo)記—整理”算法來進(jìn)行回收。
來對比一下上面幾種算法
綠色代表讀操作，黃色代表寫操作，黑色代表空閑
再來說一說，引用計(jì)數(shù)
引用計(jì)數(shù)簡單來說就是，每個(gè)對象都有一個(gè)記錄被引用次數(shù)的計(jì)數(shù)器。當(dāng)對象被引用時(shí)，它引用計(jì)數(shù)器就加 1。當(dāng)引用計(jì)數(shù)器為 0 時(shí)，對象就會(huì)被回收
引用計(jì)數(shù)算法雖然簡單，但是存在循環(huán)引用問題
看以下代碼
public class ReferenceCountingGC{
public Object instance=null；
private static final int_1MB=1024*1024；
/**
*這個(gè)成員屬性的唯一意義就是占點(diǎn)內(nèi)存，以便能在GC日志中看清楚是否被回收過
*/
private byte[]bigSize=new byte[2*_1MB]；
public static void testGC（）{
ReferenceCountingGC objA=new ReferenceCountingGC（）; //counter_A = 1
ReferenceCountingGC objB=new ReferenceCountingGC（）; //counter_B = 1
objA.instance=objB; //counter_A = 2
objB.instance=objA; //counter_B = 2
objA=null; //counter_A = 1
objB=null; //counter_B = 1
System.gc（）;
}
}
觀察上面代碼，會(huì)發(fā)現(xiàn) objA 和 objB 句柄被設(shè)置為 null 時(shí)，對象 A 和 B 之間仍有互相引用，且計(jì)數(shù)值都為 1。盡管現(xiàn)在已經(jīng)無法訪問到對象 A 和 B ，但是因?yàn)橛?jì)數(shù)值不為 0 ，所以它們不會(huì)被回收。
HotSpot 中不使用引用計(jì)數(shù)器算法，所以不會(huì)出現(xiàn)這個(gè)問題。上述代碼，只要離開了方法 testGC( ) ，對象 A 和 B 就無法通過 GC-Root 的引用鏈被訪問，所以他們會(huì)被回收。
參考
[1] Garbage Collection Algorithms
