本次LZ和各位分享GC最后兩種算法，復制算法以及標記/整理算法。上一章在講解標記/清除算法時已經提到過，這兩種算法都是在此基礎上演化而來的，究竟這兩種算法優化了之前標記/清除算法的哪些問題呢？

復制算法

         我們首先一起來看一下復制算法的做法，復制算法將內存劃分為兩個區間，在任意時間點，所有動態分配的對象都只能分配在其中一個區間（稱為活動區間），而另外一個區間（稱為空閑區間）則是空閑的。

         當有效內存空間耗盡時，JVM將暫停程序運行，開啟復制算法GC線程。接下來GC線程會將活動區間內的存活對象，全部復制到空閑區間，且嚴格按照內存地址依次排列，與此同時，GC線程將更新存活對象的內存引用地址指向新的內存地址。

         此時，空閑區間已經與活動區間交換，而垃圾對象現在已經全部留在了原來的活動區間，也就是現在的空閑區間。事實上，在活動區間轉換為空間區間的同時，垃圾對象已經被一次性全部回收。

         聽起來復雜嗎？

         其實一點也不復雜，有了上一章的基礎，相信各位理解這個算法不會費太多力氣。LZ給各位繪制一幅圖來說明問題，如下所示。

         其實這個圖依然是上一章的例子，只不過此時內存被復制算法分成了兩部分，下面我們看下當復制算法的GC線程處理之后，兩個區域會變成什么樣子，如下所示。

       可以看到，1和4號對象被清除了，而2、3、5、6號對象則是規則的排列在剛才的空閑區間，也就是現在的活動區間之內。此時左半部分已經變成了空閑區間，不難想象，在下一次GC之后，左邊將會再次變成活動區間。

       很明顯，復制算法彌補了標記/清除算法中，內存布局混亂的缺點。不過與此同時，它的缺點也是相當明顯的。

       1、它浪費了一半的內存，這太要命了。

       2、如果對象的存活率很高，我們可以極端一點，假設是100%存活，那么我們需要將所有對象都復制一遍，并將所有引用地址重置一遍。復制這一工作所花費的時間，在對象存活率達到一定程度時，將會變的不可忽視。

       所以從以上描述不難看出，復制算法要想使用，最起碼對象的存活率要非常低才行，而且最重要的是，我們必須要克服50%內存的浪費。

標記/整理算法

       標記/整理算法與標記/清除算法非常相似，它也是分為兩個階段：標記和整理。下面LZ給各位介紹一下這兩個階段都做了什么。

       標記：它的第一個階段與標記/清除算法是一模一樣的，均是遍歷GC Roots，然后將存活的對象標記。

       整理：移動所有存活的對象，且按照內存地址次序依次排列，然后將末端內存地址以后的內存全部回收。因此，第二階段才稱為整理階段。

       它GC前后的圖示與復制算法的圖非常相似，只不過沒有了活動區間和空閑區間的區別，而過程又與標記/清除算法非常相似，我們來看GC前內存中對象的狀態與布局，如下圖所示。

       這張圖其實與標記/清楚算法一模一樣，只是LZ為了方便表示內存規則的連續排列，加了一個矩形表示內存區域。倘若此時GC線程開始工作，那么緊接著開始的就是標記階段了。此階段與標記/清除算法的標記階段是一樣一樣的，我們看標記階段過后對象的狀態，如下圖。

       沒什么可解釋的，接下來，便應該是整理階段了。我們來看當整理階段處理完以后，內存的布局是如何的，如下圖。

       可以看到，標記的存活對象將會被整理，按照內存地址依次排列，而未被標記的內存會被清理掉。如此一來，當我們需要給新對象分配內存時，JVM只需要持有一個內存的起始地址即可，這比維護一個空閑列表顯然少了許多開銷。

       不難看出，標記/整理算法不僅可以彌補標記/清除算法當中，內存區域分散的缺點，也消除了復制算法當中，內存減半的高額代價，可謂是一舉兩得，一箭雙雕，一石兩鳥，一。。。。一女兩男？

       不過任何算法都會有其缺點，標記/整理算法唯一的缺點就是效率也不高，不僅要標記所有存活對象，還要整理所有存活對象的引用地址。從效率上來說，標記/整理算法要低于復制算法。

算法總結

       這里LZ給各位總結一下三個算法的共同點以及它們各自的優勢劣勢，讓各位對比一下，想必會更加清晰。

       它們的共同點主要有以下兩點。

       1、三個算法都基于根搜索算法去判斷一個對象是否應該被回收，而支撐根搜索算法可以正常工作的理論依據，就是語法中變量作用域的相關內容。因此，要想防止內存泄露，最根本的辦法就是掌握好變量作用域，而不應該使用前面內存管理雜談一章中所提到的C/C++式內存管理方式。

       2、在GC線程開啟時，或者說GC過程開始時，它們都要暫停應用程序（stop the world）。

       它們的區別LZ按照下面幾點來給各位展示。（>表示前者要優于后者，=表示兩者效果一樣）

       效率：復制算法>標記/整理算法>標記/清除算法（此處的效率只是簡單的對比時間復雜度，實際情況不一定如此）。

       內存整齊度：復制算法=標記/整理算法>標記/清除算法。

       內存利用率：標記/整理算法=標記/清除算法>復制算法。

       可以看到標記/清除算法是比較落后的算法了，但是后兩種算法卻是在此基礎上建立的，俗話說“吃水不忘挖井人”，因此各位也莫要忘記了標記/清除這一算法前輩。而且，在某些時候，標記/清除也會有用武之地。

結束語

       到此我們已經將三個算法了解清楚了，可以看出，效率上來說，復制算法是當之無愧的老大，但是卻浪費了太多內存，而為了盡量兼顧上面所提到的三個指標，標記/整理算法相對來說更平滑一些，但效率上依然不盡如人意，它比復制算法多了一個標記的階段，又比標記/清除多了一個整理內存的過程。

       難道就沒有一種最優算法嗎？

       當然是沒有的，這個世界是公平的，任何東西都有兩面性，試想一下，你怎么可能找到一個又漂亮又勤快又有錢又通情達理，性格又合適，家境也合適，身高長相等等等等都合適的女人？就算你找到了，至少有一點這個女人也肯定不滿足，那就是多半不會恰巧又愛上了與LZ相似的各位苦逼猿友們。你是不是想說你比LZ強太多了，那LZ只想對你說，高富帥是不會爬在電腦前看技術文章的，0.0。

       但是古人就是給力，古人說了，找媳婦不一定要找最好的，而是要找最合適的，聽完這句話，瞬間感覺世界美好了許多。

       算法也是一樣的，沒有最好的算法，只有最合適的算法。 

       既然這三種算法都各有缺陷，高人們自然不會容許這種情況發生。因此，高人們提出可以根據對象的不同特性，使用不同的算法處理，類似于蘿卜白菜各有所愛的原理。于是奇跡發生了，高人們終于找到了GC算法中的神級算法-----分代搜集算法。

       至于這個神級算法是如何處理的，LZ就在下一章再和各位猿友探討了，本次就到此為止了，希望各位有所收獲