后端開(kāi)發(fā)技術(shù)

來(lái)自：后端開(kāi)發(fā)技術(shù)

談到Java不得不談GC,談到GC不得不談垃圾回收算法

對(duì)象已死嗎

在進(jìn)行垃圾回收之前,，第一件事就是判斷哪些對(duì)象還存活著，哪些對(duì)象已死需要被回收,。

1.引用計(jì)數(shù)算法

        很多判斷對(duì)象是否存活的算法是這樣解答的：給對(duì)象中添加一個(gè)引用計(jì)數(shù)器,，每當(dāng)有個(gè)地方引用它時(shí)，計(jì)數(shù)器值就加1,；當(dāng)引用失效時(shí),，計(jì)數(shù)器值就減1，任何時(shí)刻計(jì)數(shù)器為0的對(duì)象就是不可能再被使用的,，該對(duì)象將被回收,。

        客觀的說(shuō)，引用計(jì)數(shù)法實(shí)現(xiàn)簡(jiǎn)單,，效率高,。但是沒(méi)有主流JVM選擇引用計(jì)數(shù)法管理內(nèi)存，因?yàn)樗麩o(wú)法解決循環(huán)引用的問(wèn)題,。例如a.objB=b,b.objA=a,

此時(shí)對(duì)象a,、b的計(jì)數(shù)器永遠(yuǎn)至少為1，當(dāng)兩個(gè)對(duì)象都不在使用時(shí),，并不會(huì)置為0,，所以難以被回收。并且,，引用計(jì)數(shù)器要求在每次因引用產(chǎn)生和消除的時(shí)候,，伴隨一個(gè)加法操作和減法操作，對(duì)系統(tǒng)性能會(huì)有一定的影響,。

2.可達(dá)性分析算法

        主流JVM都是稱(chēng)通過(guò)可達(dá)性分析來(lái)判定對(duì)象是否存活的,。這個(gè)算法的基本思路就是通過(guò)一系列的稱(chēng)為"GC Roots"的對(duì)象作為起始點(diǎn)，從這些節(jié)點(diǎn)開(kāi)始向下搜索,，搜索所走過(guò)的路徑稱(chēng)為引用鏈( Reference Chain),，當(dāng)一個(gè)對(duì)象到GC Roots 沒(méi)有任何引用鏈相連，用圖論的話(huà)來(lái)說(shuō),，就是從GC Roots 到這個(gè)對(duì)象不可達(dá)) 時(shí),，則證明此對(duì)象是不可用的,。如圖所示，對(duì)象object 5,、object 6,、object 7 雖然互相有關(guān)聯(lián)，但是它們到GC Roots 是不可達(dá)的,，所以它們將會(huì)被判定為是可回收的對(duì)象,。

垃圾回收算法

1.引用技術(shù)算法

        前面已經(jīng)介紹

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

        最基礎(chǔ)的收集算法是“標(biāo)記- 清除”(Mark-Sweep) 算法，如同它的名字一樣,，算法分為“標(biāo)記”和“清除”兩個(gè)階段：首先標(biāo)記出所有需要回收的對(duì)象,，在標(biāo)記完成后統(tǒng)一回收所有被標(biāo)記的對(duì)象（可達(dá)性分析）。之所以說(shuō)它是最基礎(chǔ)的收集算法,，是因?yàn)楹罄m(xù)的收集算法都是基于這種思路并對(duì)其不足進(jìn)行改進(jìn)而得到的,。

        不足：效率問(wèn)題，標(biāo)記和清除兩個(gè)過(guò)程的效率都不高; 空間問(wèn)題,，標(biāo)記清除之后會(huì)產(chǎn)生大量不連續(xù)的內(nèi)存碎片,，空間碎片太多可能會(huì)導(dǎo)致以后在程序運(yùn)行過(guò)程中需要分配較大對(duì)象時(shí)，無(wú)法找到足夠的連續(xù)內(nèi)存而不得不提前觸發(fā)另一次垃圾收集動(dòng)作,。

3.標(biāo)記-整理算法（標(biāo)記-壓縮）

        算法分為“標(biāo)記”,、“壓縮”和“清除”三個(gè)階段：首先標(biāo)記出所有需要回收的對(duì)象，把所有存活的對(duì)象壓縮到一段,，然后清理掉端邊界以外的內(nèi)存。這樣

將不會(huì)產(chǎn)生磁盤(pán)碎片,。但是,，壓縮階段占用了系統(tǒng)的消耗，并且如果標(biāo)記對(duì)象過(guò)多的話(huà),，損耗可能會(huì)很大,，在標(biāo)記對(duì)象相對(duì)較少的時(shí)候，效率較高,。

4.復(fù)制算法

        為了解決效率問(wèn)題,，一種稱(chēng)為“復(fù)制”(Copying)  的收集算法出現(xiàn)了，它將可用內(nèi)存按容量劃分為大小相等的兩塊,，每次只使用其中的一塊,。當(dāng)這一塊的內(nèi)存用完了，就將還存話(huà)著的對(duì)象復(fù)制到另外一塊上面,，然后再把已使用過(guò)的內(nèi)存空間一次清理掉,。這樣使得每次都是對(duì)整個(gè)半?yún)^(qū)進(jìn)行內(nèi)存回收，內(nèi)存分配時(shí)也就不用考慮內(nèi)存碎片等復(fù)雜情況,，只要移動(dòng)堆頂指針,，按順序分配內(nèi)存即可，實(shí)現(xiàn)簡(jiǎn)單，運(yùn)行高效,。只是這種算法的代價(jià)是將內(nèi)存縮小為了原來(lái)的一半,，未免太高了一點(diǎn)。

        不足：對(duì)象較多時(shí)效率低,，并且有一半的空間浪費(fèi),。

5.分代收集算法

       目前主流JVM垃圾收集都采用“分代收集”(Generational Collection) 算法，這種算法并沒(méi)有什么新的思想,，只是根據(jù)對(duì)象存活周期的不同將內(nèi)存劃分為幾塊,。一般是把Java堆分為新生代和老年代，這樣就可以根據(jù)各個(gè)年代的特點(diǎn)采用最適當(dāng)?shù)氖占惴?。在新生代中,，每次垃圾收集時(shí)都發(fā)現(xiàn)有大批對(duì)象死去，只有少量存活,，那就選用復(fù)制算法,，只需要付出少量存活對(duì)象的復(fù)制成本就可以完成收集。而老年代中因?yàn)閷?duì)象存活率高,、沒(méi)有額外空間對(duì)它進(jìn)行分配擔(dān)保（如果有空間,，通過(guò)分配擔(dān)保機(jī)制進(jìn)入老年代），就必須使用“標(biāo)記一清理”或者“標(biāo)記一整理”算法來(lái)進(jìn)行回收,。

對(duì)于新生代和老年代來(lái)說(shuō),，通常新生代回收的頻率很高，但是每次回收的時(shí)間都很短,，而老年代回收的頻率比較低,，但是被消耗很多的時(shí)間。為了支持高頻率的新生代回收,，虛擬機(jī)可能使用一種叫做卡表的數(shù)據(jù)結(jié)構(gòu),，卡表為一個(gè)比特位集合，每一個(gè)比特位可以用來(lái)表示老年代的某一區(qū)域中的所有對(duì)象是否持有新生代對(duì)象的引用,，

        這樣以來(lái),，新生代GC時(shí)，可以不用花大量時(shí)間掃描所有老年代對(duì)象,，來(lái)確定每一個(gè)對(duì)象的引用關(guān)系,，而可以先掃描卡表，只有當(dāng)卡表的標(biāo)記為1時(shí),，才需要掃描給定區(qū)域的老年代對(duì)象,，而卡表為0的所在區(qū)域的老年代對(duì)象，一定不含有新生代對(duì)象的引用,。

        卡表中每一位表示老年代4KB的空間,，卡表記錄為0的老年代區(qū)域沒(méi)有任何對(duì)象指向新生代,，只有卡表為1的區(qū)域才有對(duì)象包含新生代對(duì)象的引用，因此在新生代GC時(shí),，只需要掃面卡表為1所在的老年代空間,，使用這種方式，可以大大加快新生代的回收速度,。

6.分區(qū)算法

        分代算法將按照對(duì)象的生命周期長(zhǎng)短劃分成兩個(gè)部分,，分區(qū)算法將整個(gè)堆空間劃分成不同小區(qū)間。每個(gè)小區(qū)間都獨(dú)立使用,，獨(dú)立回收,。這種算法的好處是可以控制一次回收多少個(gè)小區(qū)間。

        一般來(lái)說(shuō),，在相同的條件下,，堆空間越大，一次GC時(shí)所需要的時(shí)間就越長(zhǎng),，從而產(chǎn)生的停頓也越長(zhǎng),。為了更好地控制GC產(chǎn)生的停頓時(shí)間，將一塊大的內(nèi)存區(qū)域分割為多個(gè)小塊,，根據(jù)目標(biāo)的停頓時(shí)間,，每次合理的回收若干個(gè)小區(qū)間，而不是整個(gè)堆空間,，從而減少一次GC所產(chǎn)生的停頓,。