相信不少猿友看到標(biāo)題就認(rèn)為L(zhǎng)Z是標(biāo)題黨了，不過(guò)既然您已經(jīng)被LZ忽悠進(jìn)來(lái)了，那就好好的享受一頓算法大餐吧。不過(guò)LZ丑話說(shuō)前面哦，這篇文章應(yīng)該能讓各位徹底理解標(biāo)記/清除算法，不過(guò)倘若各位猿友不能在五分鐘內(nèi)看完，那就不是LZ的錯(cuò)啦。

       好了，前面只是小小開(kāi)個(gè)玩笑，讓各位猿友放松下心情。下面即將與各位分享的，是GC算法中最基礎(chǔ)的算法------標(biāo)記/清除算法。如果搞清楚這個(gè)算法，那么后面兩個(gè)就完全是小菜一碟了。

       首先，我們回想一下上一章提到的根搜索算法，它可以解決我們應(yīng)該回收哪些對(duì)象的問(wèn)題，但是它顯然還不能承擔(dān)垃圾搜集的重任，因?yàn)槲覀冊(cè)诔绦颍ǔ绦蛞簿褪侵肝覀冞\(yùn)行在JVM上的java程序）運(yùn)行期間如果想進(jìn)行垃圾回收，就必須讓GC線程與程序當(dāng)中的線程互相配合，才能在不影響程序運(yùn)行的前提下，順利的將垃圾進(jìn)行回收。

       為了達(dá)到這個(gè)目的，標(biāo)記/清除算法就應(yīng)運(yùn)而生了。它的做法是當(dāng)堆中的有效內(nèi)存空間（available memory）被耗盡的時(shí)候，就會(huì)停止整個(gè)程序（也被成為stop the world），然后進(jìn)行兩項(xiàng)工作，第一項(xiàng)則是標(biāo)記，第二項(xiàng)則是清除。

       下面LZ具體解釋一下標(biāo)記和清除分別都會(huì)做些什么。

       標(biāo)記：標(biāo)記的過(guò)程其實(shí)就是，遍歷所有的GC Roots，然后將所有GC Roots可達(dá)的對(duì)象標(biāo)記為存活的對(duì)象。

       清除：清除的過(guò)程將遍歷堆中所有的對(duì)象，將沒(méi)有標(biāo)記的對(duì)象全部清除掉。

       其實(shí)這兩個(gè)步驟并不是特別復(fù)雜，也很容易理解。LZ用通俗的話解釋一下標(biāo)記/清除算法，就是當(dāng)程序運(yùn)行期間，若可以使用的內(nèi)存被耗盡的時(shí)候，GC線程就會(huì)被觸發(fā)并將程序暫停，隨后將依舊存活的對(duì)象標(biāo)記一遍，最終再將堆中所有沒(méi)被標(biāo)記的對(duì)象全部清除掉，接下來(lái)便讓程序恢復(fù)運(yùn)行。

       下面LZ給各位制作了一組描述上面過(guò)程的圖片，結(jié)合著圖片，我們來(lái)直觀的看下這一過(guò)程，首先是第一張圖。

          這張圖代表的是程序運(yùn)行期間所有對(duì)象的狀態(tài)，它們的標(biāo)志位全部是0（也就是未標(biāo)記，以下默認(rèn)0就是未標(biāo)記，1為已標(biāo)記），假設(shè)這會(huì)兒有效內(nèi)存空間耗盡了，JVM將會(huì)停止應(yīng)用程序的運(yùn)行并開(kāi)啟GC線程，然后開(kāi)始進(jìn)行標(biāo)記工作，按照根搜索算法，標(biāo)記完以后，對(duì)象的狀態(tài)如下圖。

         可以看到，按照根搜索算法，所有從root對(duì)象可達(dá)的對(duì)象就被標(biāo)記為了存活的對(duì)象，此時(shí)已經(jīng)完成了第一階段標(biāo)記。接下來(lái)，就要執(zhí)行第二階段清除了，那么清除完以后，剩下的對(duì)象以及對(duì)象的狀態(tài)如下圖所示。

         可以看到，沒(méi)有被標(biāo)記的對(duì)象將會(huì)回收清除掉，而被標(biāo)記的對(duì)象將會(huì)留下，并且會(huì)將標(biāo)記位重新歸0。接下來(lái)就不用說(shuō)了，喚醒停止的程序線程，讓程序繼續(xù)運(yùn)行即可。

         其實(shí)這一過(guò)程并不復(fù)雜，甚至可以說(shuō)非常簡(jiǎn)單，各位說(shuō)對(duì)嗎。不過(guò)其中有一點(diǎn)值得LZ一提，就是為什么非要停止程序的運(yùn)行呢？

         這個(gè)其實(shí)也不難理解，LZ舉個(gè)最簡(jiǎn)單的例子，假設(shè)我們的程序與GC線程是一起運(yùn)行的，各位試想這樣一種場(chǎng)景。

         假設(shè)我們剛標(biāo)記完圖中最右邊的那個(gè)對(duì)象，暫且記為A，結(jié)果此時(shí)在程序當(dāng)中又new了一個(gè)新對(duì)象B，且A對(duì)象可以到達(dá)B對(duì)象。但是由于此時(shí)A對(duì)象已經(jīng)標(biāo)記結(jié)束，B對(duì)象此時(shí)的標(biāo)記位依然是0，因?yàn)樗e(cuò)過(guò)了標(biāo)記階段。因此當(dāng)接下來(lái)輪到清除階段的時(shí)候，新對(duì)象B將會(huì)被苦逼的清除掉。如此一來(lái)，不難想象結(jié)果，GC線程將會(huì)導(dǎo)致程序無(wú)法正常工作。

         上面的結(jié)果當(dāng)然令人無(wú)法接受，我們剛new了一個(gè)對(duì)象，結(jié)果經(jīng)過(guò)一次GC，忽然變成null了，這還怎么玩？

         到此為止，標(biāo)記/清除算法LZ已經(jīng)介紹完了，下面我們來(lái)看下它的缺點(diǎn)，其實(shí)了解完它的算法原理，它的缺點(diǎn)就很好理解了。

         1、首先，它的缺點(diǎn)就是效率比較低（遞歸與全堆對(duì)象遍歷），而且在進(jìn)行GC的時(shí)候，需要停止應(yīng)用程序，這會(huì)導(dǎo)致用戶體驗(yàn)非常差勁，尤其對(duì)于交互式的應(yīng)用程序來(lái)說(shuō)簡(jiǎn)直是無(wú)法接受。試想一下，如果你玩一個(gè)網(wǎng)站，這個(gè)網(wǎng)站一個(gè)小時(shí)就掛五分鐘，你還玩嗎？

         2、第二點(diǎn)主要的缺點(diǎn)，則是這種方式清理出來(lái)的空閑內(nèi)存是不連續(xù)的，這點(diǎn)不難理解，我們的死亡對(duì)象都是隨即的出現(xiàn)在內(nèi)存的各個(gè)角落的，現(xiàn)在把它們清除之后，內(nèi)存的布局自然會(huì)亂七八糟。而為了應(yīng)付這一點(diǎn)，JVM就不得不維持一個(gè)內(nèi)存的空閑列表，這又是一種開(kāi)銷(xiāo)。而且在分配數(shù)組對(duì)象的時(shí)候，尋找連續(xù)的內(nèi)存空間會(huì)不太好找。

         看完它的缺點(diǎn)估計(jì)有的猿友要忍不住吐糟了，“這么說(shuō)這個(gè)算法根本沒(méi)法用嘛，那LZ還介紹這么個(gè)玩意干什么。”

         猿友們莫要著急，一個(gè)算法有缺點(diǎn)，高人們自然會(huì)想盡辦法去完善它的。而接下來(lái)我們要介紹的兩種算法，皆是在標(biāo)記/清除算法的基礎(chǔ)上優(yōu)化而產(chǎn)生的。具體的內(nèi)容，下一次LZ再和各位分享。

         本次的分享就到此結(jié)束了，希望各位看完都能有所收獲，0.0。