現(xiàn)有的垃圾回收算法

分類

根據(jù)如何判定對(duì)象是垃圾，垃圾回收算法分為兩類：1、 「引用計(jì)數(shù)式垃圾收集」 （判定垃圾是通過引用計(jì)數(shù)器）別名：直接垃圾收集 2、 「追蹤式垃圾收集」 （判定垃圾是通過GC Roots）別名：間接垃圾收集

主流虛擬機(jī)采用的是第二種追蹤式垃圾收集，所以本文講解第二種垃圾收集的算法

垃圾收集器的設(shè)計(jì)原則

根據(jù)兩個(gè)分代假說：

1.絕大部分對(duì)象是熬不過第一次垃圾回收的 2.熬過多次垃圾回收的對(duì)象是難以被標(biāo)記為垃圾的。

垃圾收集器將堆中的內(nèi)存劃分為了不同的區(qū)域，根據(jù)對(duì)象分代年齡（熬過多少次垃圾回收）來分配到不同的區(qū)域中：

比如對(duì)象分代年齡小的，第一種對(duì)象就應(yīng)該 「標(biāo)記存活對(duì)象」 即可，而不需要標(biāo)記那些垃圾對(duì)象，因?yàn)檫@部分對(duì)象大部分都是很快用完就不用的垃圾對(duì)象。

而第二種對(duì)象分代年齡大的，則應(yīng)該標(biāo)記的是垃圾對(duì)象，因?yàn)楦鶕?jù)第二個(gè)假說這部分對(duì)象中垃圾對(duì)象的占比很少，所以垃圾回收的頻率也可以降低。

「將堆劃分為不同的區(qū)域后，垃圾回收器可以只回收其中一部分區(qū)域，針對(duì)每一部分區(qū)域也可以采用不同的算法來進(jìn)行回收垃圾。」

一般來說堆中至少會(huì)被劃分為“新生代”和“老年代”兩個(gè)區(qū)域。新生代存儲(chǔ)第一種假說類型的對(duì)象，老年代存放第二種假說類型的對(duì)象。

「注意」 ：這種設(shè)計(jì)看起來是完美的，但是如果 「老年代中的對(duì)象引用了新生代中的對(duì)象」 這個(gè)時(shí)候年輕代發(fā)生垃圾回收時(shí)，除了需要遍歷GC Roots外，還需要 「遍歷整個(gè)老年代」 才會(huì)確保年輕代中的對(duì)象真正沒有對(duì)象引用。顯然這種遍歷整個(gè)老年代效率肯定會(huì)很低，所以采用了一種解決方案：讀者有興趣可以看看： 在這篇博客的末尾

標(biāo)記-清除算法

最早出現(xiàn)的垃圾回收算法，之后出現(xiàn)的算法都是根據(jù)其缺點(diǎn)來進(jìn)行演進(jìn)的。

兩個(gè)階段：1. 「標(biāo)記」 2.「清除」「標(biāo)記需要回收的對(duì)象完成后進(jìn)行統(tǒng)一回收所有被標(biāo)記的對(duì)象， 也可以標(biāo)記存活的對(duì)象統(tǒng)一回收沒有被標(biāo)記的對(duì)象。」

「一，標(biāo)記」 ：如何判定對(duì)象是否是垃圾的過程在上一篇 博客 中已經(jīng)講解過，接著 「標(biāo)記」 這些垃圾對(duì)象。

「二，清除」 ：進(jìn)行統(tǒng)一回收掉標(biāo)記的對(duì)象。

缺點(diǎn)

1.當(dāng)堆中的對(duì)象大部分是垃圾時(shí)， 「標(biāo)記和清除的效率會(huì)變低」 ，而且會(huì)隨著內(nèi)存中垃圾對(duì)象的增長，導(dǎo)致效率越來越低。

2. 「內(nèi)存碎片化」 ：因?yàn)閮?nèi)存分配不是連續(xù)的，所以當(dāng)清除后，內(nèi)存中會(huì)存在大量內(nèi)存碎片。當(dāng)遇到大對(duì)象分配內(nèi)存找不到足夠的連續(xù)的內(nèi)存來存放時(shí)會(huì)提前觸發(fā)GC。

標(biāo)記-復(fù)制算法

采用的是“半?yún)^(qū)復(fù)制”的算法來實(shí)現(xiàn)的，即每次只使用其中的一部分內(nèi)存，當(dāng)這部分內(nèi)存用完后將存活著的對(duì)象復(fù)制到另外一塊內(nèi)存上，接著清空剛才使用的那部分內(nèi)存，當(dāng)另一部分內(nèi)存滿了的時(shí)候再用上一次清空后的那塊內(nèi)存往復(fù)。

解決了標(biāo)記-清除的內(nèi)存碎片化問題，因?yàn)楫?dāng)發(fā)生GC時(shí)會(huì)進(jìn)行全部清空，只將存活對(duì)象復(fù)制到另外一塊內(nèi)存中。

在這里插入圖片描述

“Apple回收策略”

Andrew Appel針對(duì)剛剛分代假說中的第一條，提出了“Appel式回收策略”。

一般情況下百分之九十八的對(duì)象在經(jīng)歷第一次gc時(shí)就會(huì)被清除。因此做出優(yōu)化將年輕代分為了 「一塊eden空間和兩塊Survival空間」 。enen和Survival內(nèi)存占比為 「8：1」 ，即每次使用百分之九十的內(nèi)存， 「只有百分之十的內(nèi)存會(huì)被浪費(fèi)」 ，因?yàn)閷?duì)象大部分都會(huì)死去所以沒有必要分配一半的空間來存放存活對(duì)象。

但是如果使用百分之十的內(nèi)存來存放存活對(duì)象，當(dāng)存活對(duì)象在Survival空間存放不下時(shí)，這個(gè)時(shí)候就需要用老年代擔(dān)保，因此當(dāng)存不下時(shí)會(huì)存放到老年代中。

缺點(diǎn)

1.當(dāng)內(nèi)存中的對(duì)象存活率較高時(shí)，復(fù)制大量存活對(duì)象會(huì)使得效率變低。2.如果不想造成嚴(yán)重的內(nèi)存浪費(fèi)，就需要有額外的空間進(jìn)行分配。

標(biāo)記-整理算法

上面所說的標(biāo)記-復(fù)制算法針對(duì)與新生代中進(jìn)行的回收算法，并不適用與老年代，原因：老年代中存活率較高，存放不下時(shí)需要額外的內(nèi)存空間擔(dān)保。

因此出現(xiàn)了標(biāo)記-整理算法， 和標(biāo)記-復(fù)制算法相同的是： 「標(biāo)記的都是存活對(duì)象」 ；和標(biāo)記-復(fù)制算法不同的是： 「復(fù)制算法將存活對(duì)象復(fù)制到另外一塊內(nèi)存上然后清除之前使用的內(nèi)存，而整理算法是移動(dòng)存活的對(duì)象到一端，然后清除邊界以外的內(nèi)存」 。

缺點(diǎn)

「移動(dòng)存活對(duì)象」 ：對(duì)于老年代中GC之后大部分都為存活對(duì)象，將這些對(duì)象都進(jìn)行移動(dòng)并且更新引用這些對(duì)象的地方是一個(gè)比較耗時(shí)的操作。而且更新引用需要暫停用戶線程來保證用戶線程訪問對(duì)象不會(huì)出錯(cuò)，簡稱STW,"Stop the Word"。

其實(shí)不止整理算法里面移動(dòng)對(duì)象更新引用需要STW，清除算法和復(fù)制算法中的標(biāo)記清除都需要STW，只不過時(shí)間短

在這里插入圖片描述

總結(jié)

采用標(biāo)記-整理算法意味著GC的時(shí)候要移動(dòng)對(duì)象更新對(duì)象的引用，也就是說 「內(nèi)存回收的時(shí)候會(huì)更復(fù)雜」 。

采用標(biāo)記-清除算法意味著 「內(nèi)存碎片化」 。

采用標(biāo)記-復(fù)制算法意味著 「內(nèi)存可用度不高」 。

“吞吐量”：賦值器（使用垃圾回收器的線程也就是用戶線程）與垃圾回收器的效率總和。

因?yàn)?「內(nèi)存分配和訪問（內(nèi)存碎片化導(dǎo)致過多的分配和訪問）比垃圾回收器回收的頻率（回收時(shí)需要STW，而且比較耗時(shí)）要高」 ，因此整理這種方式其實(shí)吞吐量要比清除要好。

對(duì)于關(guān)注吞吐量的收集器Parallel Scabenge基于標(biāo)記-整理算法， 對(duì)于關(guān)注STW的收集器CMS來說采用的是標(biāo)記-清除算法。其實(shí)CMS是一種將兩種算法混合起來的收集器，大部分時(shí)間采用清除算法，只有當(dāng)分配內(nèi)存不足（碎片化特別嚴(yán)重）時(shí)用整理算法進(jìn)行一次收集。