JVM05-垃圾收集算法

前言

上一篇我們介紹了JVM04-JVM中內(nèi)存溢出以及其處理方法。這一篇文章我們來(lái)熟悉下JVM中各種垃圾回收算法。這些垃圾收集算法是后面各種垃圾收集器的算法基礎(chǔ)。閑話少敘，讓我們直入主題。
標(biāo)記-清除算法

標(biāo)記-清除算法分為"標(biāo)記"和"清除"兩個(gè)階段，首先標(biāo)記所有需要回收的對(duì)象，在標(biāo)記完成后，統(tǒng)一回收掉所有被標(biāo)記的對(duì)象，也可以反過來(lái)，標(biāo)記存活的對(duì)象，統(tǒng)一回收未標(biāo)記的對(duì)象，標(biāo)記的過程就是對(duì)象是否屬于垃圾的判定過程，一般是通過可達(dá)性分析算法，也就是說(shuō)某個(gè)對(duì)象到GC Root間是否有引用鏈相連，如果沒有則判斷該對(duì)象不再被使用，也就是說(shuō)是可以被回收的。如下圖所示，標(biāo)黃的內(nèi)存塊，在標(biāo)記之后，就被清除了，留下來(lái)不少的內(nèi)存碎片。
在這里插入圖片描述

標(biāo)記-清除算法的優(yōu)點(diǎn)

實(shí)現(xiàn)簡(jiǎn)單
標(biāo)記-清除算法實(shí)現(xiàn)簡(jiǎn)單， 與其他算法的組合也相應(yīng)地簡(jiǎn)單。
與保守式GC算法兼容中，對(duì)象是不能被移動(dòng)的，因此保守式GC算法跟把對(duì)象從現(xiàn)在的場(chǎng)所復(fù)制算法與標(biāo)記-壓縮算法不兼容。標(biāo)記-清除算法因?yàn)椴粫?huì)移動(dòng)對(duì)象，所以非常適合搭配保守式GC算法。事實(shí)上，在很多采用保守式GC算法的處理程序中也用到了標(biāo)記-清除算法。

標(biāo)記-清除算法的缺點(diǎn)

分配速度
執(zhí)行效率不穩(wěn)定，如果Java堆中包含大量對(duì)象，而且這些對(duì)象大部分是需要回收的，這是必須進(jìn)行大量標(biāo)記和清除動(dòng)作，導(dǎo)致標(biāo)記和清除兩個(gè)過程的執(zhí)行效率都隨著對(duì)象數(shù)量增長(zhǎng)而降低。
碎片化
內(nèi)存空間的碎片問題、標(biāo)記、清除之后會(huì)產(chǎn)生大量不連續(xù)的內(nèi)存碎片，空間碎片太多會(huì)導(dǎo)致當(dāng)以后在程序運(yùn)行過程中需要分配較大對(duì)象時(shí)無(wú)法找到足夠連續(xù)內(nèi)存而不得不提前觸發(fā)另一次垃圾收集動(dòng)作。

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

標(biāo)記-復(fù)制算法將可用的內(nèi)存容量劃分為大小相等的兩塊，每次只使用其中的一塊，當(dāng)這一塊的內(nèi)存用完了，就將還存活著的對(duì)象復(fù)制到另外一塊上面，然后再把已使用的內(nèi)存空間一次清理掉。如果內(nèi)存中多數(shù)對(duì)象都是存活的，這種算法將會(huì)產(chǎn)生大量的內(nèi)存間復(fù)制的開銷，但對(duì)于多數(shù)對(duì)象都是可回收的情況下，算法需要復(fù)制的就是占少數(shù)的存活對(duì)象。而且每次都是針對(duì)整個(gè)半?yún)^(qū)進(jìn)行內(nèi)存回收，分配內(nèi)存時(shí)就不用考慮有內(nèi)存碎片的復(fù)雜情況了。如下圖所示：回收之后將存活的對(duì)象全部移動(dòng)到原來(lái)的保留區(qū)域。
在這里插入圖片描述

標(biāo)記-復(fù)制算法的優(yōu)點(diǎn)

優(yōu)秀的吞吐量
標(biāo)記-清除算法消耗的吞吐量是搜索活動(dòng)對(duì)象（標(biāo)記階段）所花費(fèi)的時(shí)間和搜索整體堆（清除階段）所花費(fèi)的時(shí)間之和。
另一方面，因?yàn)闃?biāo)記-復(fù)制算法只搜索并復(fù)制活動(dòng)對(duì)象，所以跟一般的標(biāo)記-清除算法相比，它能在較短時(shí)間內(nèi)完成GC，也就是說(shuō)，其吞吐量?jī)?yōu)秀。
尤其是堆越大，差距越明顯。
可實(shí)現(xiàn)高速分配
標(biāo)記-復(fù)制算法不使用空閑鏈表，這是因?yàn)榉謮K是一塊連續(xù)的內(nèi)存空間，比起標(biāo)記-清除算法等使用空閑鏈表的分配，標(biāo)記-復(fù)制算法明顯快得多。
不會(huì)發(fā)生碎片化
存活對(duì)象被幾種安排到保留區(qū)域，像這樣把對(duì)象重新集中，放在堆的一端的行為就叫作壓縮，在標(biāo)記-復(fù)制算法中，每次運(yùn)行GC時(shí)都會(huì)執(zhí)行壓縮。因此復(fù)制算法不會(huì)發(fā)生碎片化。

標(biāo)記-復(fù)制算法的缺點(diǎn)

堆使用效率低下
標(biāo)記-復(fù)制算法把堆二等分，通常只能利用其中的一半來(lái)安排對(duì)象，也就是說(shuō)，只有一半的堆能被使用，相比其他能使用整個(gè)堆的GC算法而言，這是標(biāo)記-復(fù)制算法的一個(gè)重大缺陷。
不兼容保守式GC算法
標(biāo)記-復(fù)制算法因?yàn)楸仨氁苿?dòng)對(duì)象重寫指針，所以跟保守式GC算法不相容。

Appel式回收

在1989年，Andrew Appel針對(duì)具備"朝生夕滅"特點(diǎn)的對(duì)象，提出了一種更優(yōu)化的半?yún)^(qū)復(fù)制分代策略，稱之為"Appel式回收"。Appel式回收的具體做法就是把新生代分為一塊較大的Eden和Survivor中仍然存活的對(duì)象一次性復(fù)制到另一塊Survivor空間上，然后直接清理掉Eden和已用過的那塊Survivor空間，HotSpot虛擬機(jī) 默認(rèn)Eden和Survivor的大小比例是8:1，也即每次新生代可用空間為整個(gè)新生代容量的90%（Eden的80%加上一個(gè)Survivor的10%），只有一個(gè)Survivor空間，即10%的新生代會(huì)被"浪費(fèi)"掉。
標(biāo)記-整理算法

標(biāo)記-復(fù)制算法在對(duì)象存活率較高時(shí)就要進(jìn)行較多的復(fù)制操作，效率將會(huì)降低。更關(guān)鍵的是，如果不想浪費(fèi)50%的空間，就需要有額外的空間進(jìn)行分配擔(dān)保，以應(yīng)對(duì)被使用的內(nèi)存中所有對(duì)象都100%存活的極端情況。所以老年代一般不能直接選用這種算法。所以，針對(duì)老年代的垃圾收集，有標(biāo)記-整理算法，首先還是標(biāo)記所有需要回收的對(duì)象，然后讓所有存活的對(duì)象都向內(nèi)存一端移動(dòng)，然后，直接清理掉邊界以外的內(nèi)存。
如果移動(dòng)存活對(duì)象，尤其是在老年代這種每次回收都有大量對(duì)象存活區(qū)域，移動(dòng)存活對(duì)象并更新所有引用這些對(duì)象的地方將會(huì)是一種極為負(fù)重的操作。而且這種對(duì)象移動(dòng)操作必須全程暫停用戶應(yīng)用程序才能進(jìn)行。移動(dòng)對(duì)象則內(nèi)存回收時(shí)會(huì)更復(fù)雜，不移動(dòng)則內(nèi)存分配時(shí)會(huì)更復(fù)雜，從垃圾收集的停頓時(shí)間來(lái)看，不移動(dòng)對(duì)象停頓時(shí)間會(huì)更短，甚至不需要停頓，但是從整個(gè)程序的吞吐量來(lái)看，移動(dòng)對(duì)象會(huì)更劃算。關(guān)注吞吐量的Parallel Scavenge收集器是基于標(biāo)記-整理算法的，而關(guān)注延遲的CMS收集器則是基于標(biāo)記-清除算法的。標(biāo)記-整理算法清理過程如下圖所示：
在這里插入圖片描述

標(biāo)記-整理算法的優(yōu)點(diǎn)

標(biāo)記-整理算法會(huì)執(zhí)行壓縮，和其他算法相比而言，堆利用效率高。而且標(biāo)記-整理算法不會(huì)出現(xiàn)標(biāo)記-復(fù)制算法那樣只能利用半個(gè)堆的情況。另外，由于有了壓縮過程，不會(huì)產(chǎn)生碎片化。

標(biāo)記-整理算法的缺點(diǎn)

壓縮花費(fèi)計(jì)算成本
標(biāo)記-清除算法中，清除階段也要搜索整個(gè)堆，不過搜索1次就夠了，但標(biāo)記-壓縮算法要搜索3次，這樣就要花費(fèi)約3倍的時(shí)間，這是一個(gè)相當(dāng)巨大的缺陷，特別是堆越大，所消耗的成本也就越大。

保守式GC算法

前面提到了保守式，簡(jiǎn)單的來(lái)說(shuō)，保守式GC（Conservative GC）指的是"不能識(shí)別指針和非指針的GC"。
總結(jié)

本文簡(jiǎn)單的介紹了JVM中幾個(gè)基本的垃圾回收算法，主要是標(biāo)記-清除算法，標(biāo)記-復(fù)制算法和標(biāo)記-整理算法。每個(gè)算法都有各自的優(yōu)缺點(diǎn)。一般而言新生代采用標(biāo)記-清除算法和標(biāo)記-復(fù)制算法居多，老年代會(huì)采用標(biāo)記-整理算法。




作者：碼農(nóng)飛哥
微信公眾號(hào)：碼農(nóng)飛哥