標(biāo)記/清除算法
它的做法是當(dāng)堆中的有效內(nèi)存空間（available memory）被耗盡的時(shí)候前翎，就會停止整個(gè)程序（也被成為stop the world），然后進(jìn)行兩項(xiàng)工作纱耻，第一項(xiàng)則是標(biāo)記仙蛉，第二項(xiàng)則是清除。
標(biāo)記：標(biāo)記的過程其實(shí)就是观挎，遍歷所有的GC Roots，然后將所有GC Roots可達(dá)的對象標(biāo)記為存活的對象段化。
清除：清除的過程將遍歷堆中所有的對象嘁捷，將沒有標(biāo)記的對象全部清除掉。
其實(shí)這兩個(gè)步驟并不是特別復(fù)雜显熏，也很容易理解雄嚣。LZ用通俗的話解釋一下標(biāo)記/清除算法，就是當(dāng)程序運(yùn)行期間，若可以使用的內(nèi)存被耗盡的時(shí)候缓升，GC線程就會被觸發(fā)并將程序暫停鼓鲁，隨后將依舊存活的對象標(biāo)記一遍，最終再將堆中所有沒被標(biāo)記的對象全部清除掉港谊，接下來便讓程序恢復(fù)運(yùn)行骇吭。
下面LZ給各位制作了一組描述上面過程的圖片，結(jié)合著圖片歧寺，我們來直觀的看下這一過程燥狰，首先是第一張圖。
這張圖代表的是程序運(yùn)行期間所有對象的狀態(tài)斜筐，它們的標(biāo)志位全部是0（也就是未標(biāo)記碾局，以下默認(rèn)0就是未標(biāo)記，1為已標(biāo)記）奴艾，假設(shè)這會兒有效內(nèi)存空間耗盡了，JVM將會停止應(yīng)用程序的運(yùn)行并開啟GC線程内斯，然后開始進(jìn)行標(biāo)記工作蕴潦，按照根搜索算法，標(biāo)記完以后俘闯，對象的狀態(tài)如下圖潭苞。
可以看到，按照根搜索算法真朗，所有從root對象可達(dá)的對象就被標(biāo)記為了存活的對象此疹，此時(shí)已經(jīng)完成了第一階段標(biāo)記。接下來遮婶，就要執(zhí)行第二階段清除了蝗碎，那么清除完以后，剩下的對象以及對象的狀態(tài)如下圖所示旗扑。
可以看到蹦骑，沒有被標(biāo)記的對象將會回收清除掉，而被標(biāo)記的對象將會留下臀防，并且會將標(biāo)記位重新歸0眠菇。接下來就不用說了，喚醒停止的程序線程袱衷，讓程序繼續(xù)運(yùn)行即可捎废。
標(biāo)記/整理算法
標(biāo)記/整理算法與標(biāo)記/清除算法非常相似，它也是分為兩個(gè)階段：標(biāo)記和整理致燥。下面LZ給各位介紹一下這兩個(gè)階段都做了什么登疗。
標(biāo)記：它的第一個(gè)階段與標(biāo)記/清除算法是一模一樣的，均是遍歷GC Roots嫌蚤，然后將存活的對象標(biāo)記谜叹。
整理：移動所有存活的對象匾寝，且按照內(nèi)存地址次序依次排列，然后將末端內(nèi)存地址以后的內(nèi)存全部回收荷腊。因此艳悔，第二階段才稱為整理階段。
它GC前后的圖示與復(fù)制算法的圖非常相似女仰，只不過沒有了活動區(qū)間和空閑區(qū)間的區(qū)別猜年，而過程又與標(biāo)記/清除算法非常相似，我們來看GC前內(nèi)存中對象的狀態(tài)與布局疾忍，如下圖所示乔外。
這張圖其實(shí)與標(biāo)記/清楚算法一模一樣，只是LZ為了方便表示內(nèi)存規(guī)則的連續(xù)排列一罩，加了一個(gè)矩形表示內(nèi)存區(qū)域杨幼。倘若此時(shí)GC線程開始工作，那么緊接著開始的就是標(biāo)記階段了聂渊。此階段與標(biāo)記/清除算法的標(biāo)記階段是一樣一樣的差购，我們看標(biāo)記階段過后對象的狀態(tài)，如下圖汉嗽。
沒什么可解釋的欲逃，接下來，便應(yīng)該是整理階段了饼暑。我們來看當(dāng)整理階段處理完以后稳析，內(nèi)存的布局是如何的，如下圖弓叛。
可以看到彰居，標(biāo)記的存活對象將會被整理，按照內(nèi)存地址依次排列撰筷，而未被標(biāo)記的內(nèi)存會被清理掉裕菠。如此一來，當(dāng)我們需要給新對象分配內(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à)奈虾，可謂是一舉兩得，一箭雙雕，一石兩鳥肉微，一匾鸥。。碉纳。勿负。一女兩男？
不過任何算法都會有其缺點(diǎn)劳曹，標(biāo)記/整理算法唯一的缺點(diǎn)就是效率也不高奴愉，不僅要標(biāo)記所有存活對象，還要整理所有存活對象的引用地址铁孵。從效率上來說锭硼，標(biāo)記/整理算法要低于復(fù)制算法。
復(fù)制算法
我們首先一起來看一下復(fù)制算法的做法蜕劝，復(fù)制算法將內(nèi)存劃分為兩個(gè)區(qū)間檀头，在任意時(shí)間點(diǎn)，所有動態(tài)分配的對象都只能分配在其中一個(gè)區(qū)間（稱為活動區(qū)間）岖沛，而另外一個(gè)區(qū)間（稱為空閑區(qū)間）則是空閑的暑始。
當(dāng)有效內(nèi)存空間耗盡時(shí)，JVM將暫停程序運(yùn)行烫止，開啟復(fù)制算法GC線程。接下來GC線程會將活動區(qū)間內(nèi)的存活對象戳稽，全部復(fù)制到空閑區(qū)間馆蠕，且嚴(yán)格按照內(nèi)存地址依次排列，與此同時(shí)惊奇，GC線程將更新存活對象的內(nèi)存引用地址指向新的內(nèi)存地址互躬。
此時(shí)，空閑區(qū)間已經(jīng)與活動區(qū)間交換颂郎，而垃圾對象現(xiàn)在已經(jīng)全部留在了原來的活動區(qū)間吼渡，也就是現(xiàn)在的空閑區(qū)間。事實(shí)上乓序，在活動區(qū)間轉(zhuǎn)換為空間區(qū)間的同時(shí)寺酪，垃圾對象已經(jīng)被一次性全部回收。
聽起來復(fù)雜嗎替劈？
其實(shí)一點(diǎn)也不復(fù)雜寄雀，有了上一章的基礎(chǔ)，相信各位理解這個(gè)算法不會費(fèi)太多力氣陨献。LZ給各位繪制一幅圖來說明問題盒犹，如下所示。
只不過此時(shí)內(nèi)存被復(fù)制算法分成了兩部分，下面我們看下當(dāng)復(fù)制算法的GC線程處理之后急膀，兩個(gè)區(qū)域會變成什么樣子沮协，如下所示。
可以看到卓嫂，1和4號對象被清除了慷暂，而2、3命黔、5呜呐、6號對象則是規(guī)則的排列在剛才的空閑區(qū)間，也就是現(xiàn)在的活動區(qū)間之內(nèi)悍募。此時(shí)左半部分已經(jīng)變成了空閑區(qū)間蘑辑，不難想象，在下一次GC之后坠宴，左邊將會再次變成活動區(qū)間洋魂。
很明顯，復(fù)制算法彌補(bǔ)了標(biāo)記/清除算法中喜鼓，內(nèi)存布局混亂的缺點(diǎn)副砍。不過與此同時(shí)，它的缺點(diǎn)也是相當(dāng)明顯的庄岖。
1豁翎、它浪費(fèi)了一半的內(nèi)存，這太要命了隅忿。
2心剥、如果對象的存活率很高，我們可以極端一點(diǎn)背桐，假設(shè)是100%存活优烧，那么我們需要將所有對象都復(fù)制一遍，并將所有引用地址重置一遍链峭。復(fù)制這一工作所花費(fèi)的時(shí)間畦娄，在對象存活率達(dá)到一定程度時(shí)，將會變的不可忽視弊仪。
所以從以上描述不難看出熙卡，復(fù)制算法要想使用，最起碼對象的存活率要非常低才行励饵，而且最重要的是再膳，我們必須要克服50%內(nèi)存的浪費(fèi)。
算法總結(jié)
這里L(fēng)Z給各位總結(jié)一下三個(gè)算法的共同點(diǎn)以及它們各自的優(yōu)勢劣勢曲横，讓各位對比一下喂柒，想必會更加清晰不瓶。
它們的共同點(diǎn)主要有以下兩點(diǎn)。
1灾杰、三個(gè)算法都基于根搜索算法去判斷一個(gè)對象是否應(yīng)該被回收蚊丐，而支撐根搜索算法可以正常工作的理論依據(jù)，就是語法中變量作用域的相關(guān)內(nèi)容艳吠。因此麦备，要想防止內(nèi)存泄露，最根本的辦法就是掌握好變量作用域昭娩，而不應(yīng)該使用前面內(nèi)存管理雜談一章中所提到的C/C++式內(nèi)存管理方式凛篙。
2、在GC線程開啟時(shí)栏渺，或者說GC過程開始時(shí)呛梆，它們都要暫停應(yīng)用程序（stop the world）。
它們的區(qū)別LZ按照下面幾點(diǎn)來給各位展示磕诊。（>表示前者要優(yōu)于后者填物，=表示兩者效果一樣）
效率：復(fù)制算法>標(biāo)記/整理算法>標(biāo)記/清除算法（此處的效率只是簡單的對比時(shí)間復(fù)雜度，實(shí)際情況不一定如此）霎终。
內(nèi)存整齊度：復(fù)制算法=標(biāo)記/整理算法>標(biāo)記/清除算法滞磺。
內(nèi)存利用率：標(biāo)記/整理算法=****標(biāo)記/清除算法>復(fù)制算法。
可以看到標(biāo)記/清除算法是比較落后的算法了莱褒，但是后兩種算法卻是在此基礎(chǔ)上建立的击困，俗話說“吃水不忘挖井人”，因此各位也莫要忘記了標(biāo)記/清除這一算法前輩广凸。而且阅茶，在某些時(shí)候，標(biāo)記/清除也會有用武之地炮障。
