垃圾搜集算法的實現(xiàn)涉及太多細(xì)節(jié)劣针，而且各個平臺虛擬機操作內(nèi)存的方法又各不相同，因此本文不會太多的討論算法實現(xiàn)竞思，而是介紹幾種算法的思想以及其發(fā)展過程搞坝。
本文涉及到以下GC算法：
- 標(biāo)記-清除算法（Mark-Sweep）
- 復(fù)制算法（Copying）
- 標(biāo)記整理算法（Mark-Compact）
- 分代搜集算法（Generational Collection）
標(biāo)記-清除算法（Mark-Sweep）
算法思想
最基礎(chǔ)的算法就是標(biāo)記-清除算法，如同其名字一樣干旁，算法分為“標(biāo)記”和“清除”兩個階段：
第一階段驶沼，標(biāo)記：使用可達性分析算法判斷對象是否可達，然后一般在對象的header中對可達性進行“標(biāo)記”争群。
第二階段回怜，清除：垃圾搜集器會對被標(biāo)記為不可達的對象進行“清除”。
算法缺陷
- 效率問題：標(biāo)記和清除兩個過程的效率都不高
-
空間問題：標(biāo)記清楚之后會產(chǎn)生大量的不連續(xù)的內(nèi)存碎片换薄，空間碎片太多玉雾，可能導(dǎo)致以后在程序運行過程中需要分配較大對象時，無法找到足夠的連續(xù)內(nèi)存而不得不提前觸發(fā)另一次垃圾搜集動作轻要。
標(biāo)記-清除算法示意圖
復(fù)制算法（Copying）
算法思想
為了解決效率問題复旬，一種稱為“復(fù)制”的搜集算法出現(xiàn)了，他將可用內(nèi)存按照容量劃分為大小相等的兩塊冲泥，每次只使用其中的一塊驹碍。當(dāng)這一塊用完了，就將還活著的對象復(fù)制到另一塊上面凡恍，然后再把已經(jīng)使用過得內(nèi)存一次性清理掉志秃。這樣使得每次都是對整個半?yún)^(qū)進行內(nèi)存回收，內(nèi)存分配時也就不用考慮內(nèi)存碎片等復(fù)雜情況嚼酝，只要移動堆頂指針浮还，按照順序分配內(nèi)存即可，實現(xiàn)簡單闽巩，運行高效碑定。
算法缺陷
內(nèi)存浪費嚴(yán)重：這種算法的代價是將內(nèi)存縮小為了原來的一半流码，浪費嚴(yán)重。
算法優(yōu)化
現(xiàn)在的商業(yè)虛擬機都采用這種搜集算法來回收新生代延刘，IBM公司研究表明漫试，新生代中對象98%是“朝生夕死”，所以并不需要按照1:1的比例來劃分內(nèi)存空間碘赖，而是將內(nèi)存分為一塊較大的Eden空間和兩塊較小的Survivor空間驾荣，每次使用Eden和其中一塊Survivor。當(dāng)回收時普泡，將Eden和Survivor中還存活的對象一次性復(fù)制到另外一塊Survivor空間上播掷，最后清掉Eden和剛才用過的Survivor空間。
HotSpot虛擬機默認(rèn)Eden和Survivor的大小比例是8:1,也就是每次新生代中可用內(nèi)存空間為整個新生代容量的90%（80%+10%）撼班，只有10%的內(nèi)存會被浪費歧匈。當(dāng)然，98%的對象可回收只是一般場景下的數(shù)據(jù)砰嘁，我們沒有辦法保證每次回收都只有不多于10%的對象存活件炉，當(dāng)Survivor空間不夠用時，需要依賴其他內(nèi)存（這里指老年代）進行分配擔(dān)保（Handle Promotion）矮湘。
內(nèi)存的分配擔(dān)保就好比我們?nèi)ャy行借款斟冕，如果我們信譽很好，在98%的情況下都能按時償還缅阳，于是銀行可能會默認(rèn)我們下一次也能按時按量地償還貸款磕蛇，只需要有一個擔(dān)保人能保證如果我不能還款時，可以從他的賬戶扣錢十办，那銀行就認(rèn)為沒有風(fēng)險了秀撇。內(nèi)存的分配擔(dān)保也一樣，如果另外一塊Survivor空間沒有足夠空間存放上一次新生代收集下來的存活對象時向族，這些對象將直接通過分配擔(dān)保機制進入老年代呵燕。
標(biāo)記-整理算法
算法思想
復(fù)制收集算法在對象存活率較高時就要進行較多的復(fù)制操作，效率將會變低炸枣。更關(guān)鍵的是，如果不想浪費50%的空間弄唧，就需要有額外的空間進行分配擔(dān)保适肠，以應(yīng)對被使用的內(nèi)存中所有對象都100%存活的極端情況，所以在老年代一般不能直接選用這種算法候引。
根據(jù)老年代的特點侯养，有人提出了另外一種“標(biāo)記-整理”（Mark-Compact）算法，標(biāo)記過程仍然與“標(biāo)記-清除”算法一樣澄干，但后續(xù)步驟不是直接對可回收對象進行清理逛揩，而是讓所有存活的對象都向一端移動柠傍，然后直接清理掉端邊界以外的內(nèi)存。
分代搜集算法
當(dāng)前商業(yè)虛擬機的垃圾收集都采用“分代收集”（Generational Collection）算法辩稽，這種算法并沒有什么新的思想惧笛，只是根據(jù)對象存活周期的不同將內(nèi)存劃分為幾塊。一般是把Java堆分為新生代和老年代逞泄，這樣就可以根據(jù)各個年代的特點采用最適當(dāng)?shù)氖占惴ɑ颊Ｔ谛律校看卫占瘯r都發(fā)現(xiàn)有大批對象死去喷众，只有少量存活各谚，那就選用復(fù)制算法，只需要付出少量存活對象的復(fù)制成本就可以完成收集到千。而老年代中因為對象存活率高昌渤、沒有額外空間對它進行分配擔(dān)保，就必須使用“標(biāo)記—清理”或者“標(biāo)記—整理”算法來進行回收憔四。
參考
《深入理解Java虛擬機》
