版權(quán)聲明
作者：zuoxiaolong（左瀟龍）
出處：博客園左瀟龍的技術(shù)博客--http://www.cnblogs.com/zuoxiaolong
您的支持是對(duì)博主最大的鼓勵(lì)，感謝您的認(rèn)真閱讀。
本文版權(quán)歸作者所有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁(yè)面明顯位置給出原文連接，否則保留追究法律責(zé)任的權(quán)利。
原文鏈接：http://www.cnblogs.com/zuoxiaolong/p/jvm5.html
本次LZ和各位分享GC最后兩種算法，復(fù)制算法以及標(biāo)記/整理算法。上一章在講解標(biāo)記/清除算法時(shí)已經(jīng)提到過(guò)，這兩種算法都是在此基礎(chǔ)上演化而來(lái)的，究竟這兩種算法優(yōu)化了之前標(biāo)記/清除算法的哪些問(wèn)題呢？
復(fù)制算法
我們首先一起來(lái)看一下復(fù)制算法的做法，復(fù)制算法將內(nèi)存劃分為兩個(gè)區(qū)間，在任意時(shí)間點(diǎn)，所有動(dòng)態(tài)分配的對(duì)象都只能分配在其中一個(gè)區(qū)間（稱為活動(dòng)區(qū)間），而另外一個(gè)區(qū)間（稱為空閑區(qū)間）則是空閑的。
當(dāng)有效內(nèi)存空間耗盡時(shí)，JVM將暫停程序運(yùn)行，開啟復(fù)制算法GC線程。接下來(lái)GC線程會(huì)將活動(dòng)區(qū)間內(nèi)的存活對(duì)象，全部復(fù)制到空閑區(qū)間，且嚴(yán)格按照內(nèi)存地址依次排列，與此同時(shí)，GC線程將更新存活對(duì)象的內(nèi)存引用地址指向新的內(nèi)存地址。
此時(shí)，空閑區(qū)間已經(jīng)與活動(dòng)區(qū)間交換，而垃圾對(duì)象現(xiàn)在已經(jīng)全部留在了原來(lái)的活動(dòng)區(qū)間，也就是現(xiàn)在的空閑區(qū)間。事實(shí)上，在活動(dòng)區(qū)間轉(zhuǎn)換為空間區(qū)間的同時(shí)，垃圾對(duì)象已經(jīng)被一次性全部回收。
聽(tīng)起來(lái)復(fù)雜嗎？
其實(shí)一點(diǎn)也不復(fù)雜，有了上一章的基礎(chǔ)，相信各位理解這個(gè)算法不會(huì)費(fèi)太多力氣。LZ給各位繪制一幅圖來(lái)說(shuō)明問(wèn)題，如下所示。
其實(shí)這個(gè)圖依然是上一章的例子，只不過(guò)此時(shí)內(nèi)存被復(fù)制算法分成了兩部分，下面我們看下當(dāng)復(fù)制算法的GC線程處理之后，兩個(gè)區(qū)域會(huì)變成什么樣子，如下所示。
可以看到，1和4號(hào)對(duì)象被清除了，而2、3、5、6號(hào)對(duì)象則是規(guī)則的排列在剛才的空閑區(qū)間，也就是現(xiàn)在的活動(dòng)區(qū)間之內(nèi)。此時(shí)左半部分已經(jīng)變成了空閑區(qū)間，不難想象，在下一次GC之后，左邊將會(huì)再次變成活動(dòng)區(qū)間。
很明顯，復(fù)制算法彌補(bǔ)了標(biāo)記/清除算法中，內(nèi)存布局混亂的缺點(diǎn)。不過(guò)與此同時(shí)，它的缺點(diǎn)也是相當(dāng)明顯的。
1、它浪費(fèi)了一半的內(nèi)存，這太要命了。
2、如果對(duì)象的存活率很高，我們可以極端一點(diǎn)，假設(shè)是100%存活，那么我們需要將所有對(duì)象都復(fù)制一遍，并將所有引用地址重置一遍。復(fù)制這一工作所花費(fèi)的時(shí)間，在對(duì)象存活率達(dá)到一定程度時(shí)，將會(huì)變的不可忽視。
所以從以上描述不難看出，復(fù)制算法要想使用，最起碼對(duì)象的存活率要非常低才行，而且最重要的是，我們必須要克服50%內(nèi)存的浪費(fèi)。
標(biāo)記/整理算法
標(biāo)記/整理算法與標(biāo)記/清除算法非常相似，它也是分為兩個(gè)階段：標(biāo)記和整理。下面LZ給各位介紹一下這兩個(gè)階段都做了什么。
標(biāo)記：它的第一個(gè)階段與標(biāo)記/清除算法是一模一樣的，均是遍歷GC Roots，然后將存活的對(duì)象標(biāo)記。
整理：移動(dòng)所有存活的對(duì)象，且按照內(nèi)存地址次序依次排列，然后將末端內(nèi)存地址以后的內(nèi)存全部回收。因此，第二階段才稱為整理階段。
它GC前后的圖示與復(fù)制算法的圖非常相似，只不過(guò)沒(méi)有了活動(dòng)區(qū)間和空閑區(qū)間的區(qū)別，而過(guò)程又與標(biāo)記/清除算法非常相似，我們來(lái)看GC前內(nèi)存中對(duì)象的狀態(tài)與布局，如下圖所示。
這張圖其實(shí)與標(biāo)記/清楚算法一模一樣，只是LZ為了方便表示內(nèi)存規(guī)則的連續(xù)排列，加了一個(gè)矩形表示內(nèi)存區(qū)域。倘若此時(shí)GC線程開始工作，那么緊接著開始的就是標(biāo)記階段了。此階段與標(biāo)記/清除算法的標(biāo)記階段是一樣一樣的，我們看標(biāo)記階段過(guò)后對(duì)象的狀態(tài)，如下圖。
沒(méi)什么可解釋的，接下來(lái)，便應(yīng)該是整理階段了。我們來(lái)看當(dāng)整理階段處理完以后，內(nèi)存的布局是如何的，如下圖。
以看到，標(biāo)記的存活對(duì)象將會(huì)被整理，按照內(nèi)存地址依次排列，而未被標(biāo)記的內(nèi)存會(huì)被清理掉。如此一來(lái)，當(dāng)我們需要給新對(duì)象分配內(nèi)存時(shí)，JVM只需要持有一個(gè)內(nèi)存的起始地址即可，這比維護(hù)一個(gè)空閑列表顯然少了許多開銷。
不難看出，標(biāo)記/整理算法不僅可以彌補(bǔ)標(biāo)記/清除算法當(dāng)中，內(nèi)存區(qū)域分散的缺點(diǎn)，也消除了復(fù)制算法當(dāng)中，內(nèi)存減半的高額代價(jià)，可謂是一舉兩得，一箭雙雕，一石兩鳥，一。。。。一女兩男？
不過(guò)任何算法都會(huì)有其缺點(diǎn)，標(biāo)記/整理算法唯一的缺點(diǎn)就是效率也不高，不僅要標(biāo)記所有存活對(duì)象，還要整理所有存活對(duì)象的引用地址。從效率上來(lái)說(shuō)，標(biāo)記/整理算法要低于復(fù)制算法。
算法總結(jié)
這里L(fēng)Z給各位總結(jié)一下三個(gè)算法的共同點(diǎn)以及它們各自的優(yōu)勢(shì)劣勢(shì)，讓各位對(duì)比一下，想必會(huì)更加清晰。
它們的共同點(diǎn)主要有以下兩點(diǎn)。
1、三個(gè)算法都基于根搜索算法去判斷一個(gè)對(duì)象是否應(yīng)該被回收，而支撐根搜索算法可以正常工作的理論依據(jù)，就是語(yǔ)法中變量作用域的相關(guān)內(nèi)容。因此，要想防止內(nèi)存泄露，最根本的辦法就是掌握好變量作用域，而不應(yīng)該使用前面內(nèi)存管理雜談一章中所提到的C/C++式內(nèi)存管理方式。
2、在GC線程開啟時(shí)，或者說(shuō)GC過(guò)程開始時(shí)，它們都要暫停應(yīng)用程序（stop the world）。
它們的區(qū)別LZ按照下面幾點(diǎn)來(lái)給各位展示。（>表示前者要優(yōu)于后者，=表示兩者效果一樣）
效率：復(fù)制算法>標(biāo)記/整理算法>標(biāo)記/清除算法（此處的效率只是簡(jiǎn)單的對(duì)比時(shí)間復(fù)雜度，實(shí)際情況不一定如此）。
內(nèi)存整齊度：復(fù)制算法=標(biāo)記/整理算法>標(biāo)記/清除算法。
內(nèi)存利用率：標(biāo)記/整理算法=標(biāo)記/清除算法>復(fù)制算法。
可以看到標(biāo)記/清除算法是比較落后的算法了，但是后兩種算法卻是在此基礎(chǔ)上建立的，俗話說(shuō)“吃水不忘挖井人”，因此各位也莫要忘記了標(biāo)記/清除這一算法前輩。而且，在某些時(shí)候，標(biāo)記/清除也會(huì)有用武之地。
結(jié)束語(yǔ)
到此我們已經(jīng)將三個(gè)算法了解清楚了，可以看出，效率上來(lái)說(shuō)，復(fù)制算法是當(dāng)之無(wú)愧的老大，但是卻浪費(fèi)了太多內(nèi)存，而為了盡量兼顧上面所提到的三個(gè)指標(biāo)，標(biāo)記/整理算法相對(duì)來(lái)說(shuō)更平滑一些，但效率上依然不盡如人意，它比復(fù)制算法多了一個(gè)標(biāo)記的階段，又比標(biāo)記/清除多了一個(gè)整理內(nèi)存的過(guò)程。
難道就沒(méi)有一種最優(yōu)算法嗎？
當(dāng)然是沒(méi)有的，這個(gè)世界是公平的，任何東西都有兩面性，試想一下，你怎么可能找到一個(gè)又漂亮又勤快又有錢又通情達(dá)理，性格又合適，家境也合適，身高長(zhǎng)相等等等等都合適的女人？就算你找到了，至少有一點(diǎn)這個(gè)女人也肯定不滿足，那就是多半不會(huì)恰巧又愛(ài)上了與LZ相似的各位苦逼猿友們。你是不是想說(shuō)你比LZ強(qiáng)太多了，那LZ只想對(duì)你說(shuō)，高富帥是不會(huì)爬在電腦前看技術(shù)文章的，0.0。
但是古人就是給力，古人說(shuō)了，找媳婦不一定要找最好的，而是要找最合適的，聽(tīng)完這句話，瞬間感覺(jué)世界美好了許多。
算法也是一樣的，沒(méi)有最好的算法，只有最合適的算法。
既然這三種算法都各有缺陷，高人們自然不會(huì)容許這種情況發(fā)生。因此，高人們提出可以根據(jù)對(duì)象的不同特性，使用不同的算法處理，類似于蘿卜白菜各有所愛(ài)的原理。于是奇跡發(fā)生了，高人們終于找到了GC算法中的神級(jí)算法-----分代搜集算法。
至于這個(gè)神級(jí)算法是如何處理的，LZ就在下一章再和各位猿友探討了，本次就到此為止了，希望各位有所收獲。
