前文介紹過(guò)，基于分代收集理論的指導(dǎo)，我們才可以針對(duì)堆中不同的區(qū)域，設(shè)計(jì)出不同的垃圾收集算法，主要有以下三種：

• 標(biāo)記-清除算法
• 標(biāo)記-復(fù)制算法
• 標(biāo)記-整理算法

全文思維導(dǎo)圖如下：

標(biāo)記-清除算法，Mark-Sweep“標(biāo)記-清除”(Mark-Sweep)算法是最基礎(chǔ)的垃圾收集算法，在 1960 年由 Lisp 之父 John McCarthy 所提出，后面所介紹的兩種算法都是基于此改進(jìn)而來(lái)。

不難理解，從名稱上就已經(jīng)能看出，整個(gè)算法分為兩個(gè)大步驟：

標(biāo)記 and 清除。

拓展來(lái)說(shuō)：

• 標(biāo)記，Mark：指的是標(biāo)記出所有需要回收的對(duì)象(也就是判斷對(duì)象是否是垃圾，這個(gè)前文已經(jīng)說(shuō)過(guò)了，有兩種方法：引用計(jì)數(shù)法和可達(dá)性分析，由于引用計(jì)數(shù)法無(wú)法解決循環(huán)引用問(wèn)題，所以目前主流的虛擬機(jī)采用的都是可達(dá)性分析法)
• 清除，Sweep：指的是在標(biāo)記完成后，統(tǒng)一回收掉所有被標(biāo)記的對(duì)象

當(dāng)然了，反過(guò)來(lái)也是可以的，標(biāo)記存活的對(duì)象，統(tǒng)一回收所有未被標(biāo)記的對(duì)象。

我們說(shuō)這個(gè)標(biāo)記-清除算法是最基礎(chǔ)的垃圾收集算法奧，后面兩種算法都是基于此改進(jìn)而來(lái)，那么改進(jìn)改進(jìn)，既然是改進(jìn)，這個(gè)基礎(chǔ)的算法一定是存在一些問(wèn)題，才能夠有改進(jìn)的空間，對(duì)吧。

標(biāo)記-清除算法的主要缺點(diǎn)有兩個(gè)：

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

標(biāo)記-清除算法的執(zhí)行過(guò)程如圖：

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

“標(biāo)記-復(fù)制”(Mark-Copy)算法常被簡(jiǎn)稱為復(fù)制算法。

為了解決標(biāo)記-清除算法面對(duì)大量可回收對(duì)象時(shí)執(zhí)行效率低的問(wèn)題，1969 年 Fenichel 提出了一種稱為 “半?yún)^(qū)復(fù)制”(Semispace Copying)的垃圾收集算法，具體思想大概是這樣：

將可用內(nèi)存按容量劃分為大小相等的兩塊，每次只使用其中的一塊。當(dāng)這一塊的內(nèi)存用完了，就將還存活著的對(duì)象復(fù)制到另外一塊上面，然后再把已使用過(guò)的內(nèi)存空間一次性全部清理掉。

很顯然，這個(gè)方法并不適用于多數(shù)對(duì)象都是存活的情況，因?yàn)檫@將會(huì)產(chǎn)生大量的內(nèi)存間復(fù)制的開(kāi)銷。

但對(duì)于多數(shù)對(duì)象都是可回收的情況，該算法只需要復(fù)制少量的存活對(duì)象，而且每次都是針對(duì)整個(gè)半?yún)^(qū)進(jìn)行內(nèi)存回收，分配內(nèi)存時(shí)也就不用考慮有空間碎片的復(fù)雜情況，只要移動(dòng)堆頂指針，按順序分配即可。

這樣實(shí)現(xiàn)簡(jiǎn)單，運(yùn)行高效，現(xiàn)在大部分的商用 Java 虛擬機(jī)都優(yōu)先采用了這種垃圾收集算法去回收新生代

該算法的執(zhí)行過(guò)程如圖所示：

這樣實(shí)現(xiàn)簡(jiǎn)單，運(yùn)行高效，不過(guò)其缺陷也顯而易見(jiàn)，這種復(fù)制回收算法的代價(jià)是將可用內(nèi)存縮小為了原來(lái)的一半，空間浪費(fèi)未免太多了一點(diǎn)。

IBM 公司曾有一項(xiàng)專門(mén)研究對(duì)新生代 “朝生夕滅” 的特點(diǎn)做了更量化的詮釋：新生代中的對(duì)象有 98% 熬不過(guò)第一輪收集。因此并不需要按照 1∶1的比例來(lái)劃分新生代的內(nèi)存空間。

更簡(jiǎn)單的來(lái)說(shuō)，標(biāo)記-復(fù)制算法設(shè)計(jì)這么一大塊的保留區(qū)域，目的就是為了把存活對(duì)象移動(dòng)到這塊區(qū)域上來(lái)，方便對(duì)之前的區(qū)域進(jìn)行快速清理。

對(duì)于新生代對(duì)象來(lái)說(shuō)，其具備的鮮明特點(diǎn)就是 “朝生夕滅”，能夠在一輪垃圾收集后活下來(lái)的對(duì)象少之又少。所以，我們其實(shí)并不需要這么大一塊的保留區(qū)域。

1989 年 Andrew Appel 基于此提出了一種更優(yōu)化的半?yún)^(qū)復(fù)制分代策略，現(xiàn)在稱為 “Appel 式回收”。HotSpot 虛擬機(jī)的 Serial、ParNew 等新生代收集器均采用了這種策略來(lái)設(shè)計(jì)新生代的內(nèi)存布局。

? Appel 式回收的具體做法是把新生代分為一塊較大的 Eden 空間和兩塊較小的 Survivor 空間，每次分配內(nèi)存只使用 Eden 和其中一塊 Survivor。發(fā)生垃圾收集時(shí)，直接清空 Eden 和已用過(guò)的那塊 Survivor 空間，當(dāng)然，在清空之前需要將存活對(duì)象復(fù)制到另一塊 Survivor 中。

這兩塊 Survivor 空間也分別被稱為 From Survivior 和 To Survivor，很顯然，每經(jīng)過(guò)一次新生代 GC，F(xiàn)rom Survivor 和 To Survivor 的身份就會(huì)互換。

簡(jiǎn)單理解，Eden 和 From Survivor 其實(shí)就是新生代能夠使用的真正內(nèi)存，而 To Survivor 的存在是為了在清空新生代空間時(shí)提供一個(gè)地方用來(lái)存放仍然存活的對(duì)象 (也即保留區(qū)域)。

HotSpot 虛擬機(jī)默認(rèn) Eden 和 Survivor 的大小比例是 8∶1，也即每次新生代中可用內(nèi)存空間為整個(gè)新生代容量的 90%(Eden 的 80% 加上一個(gè) Survivor 的 10%)，只有一個(gè) Survivor 空間，即 10% 的新生代空間是會(huì)被 “浪費(fèi)” 的。

當(dāng)然，任何人都沒(méi)有辦法百分百保證每次回收都只有不多于 10% 的對(duì)象存活，萬(wàn)一 To Survivor 的內(nèi)存空間不足以容納存活的對(duì)象怎么辦?

別急，我們都能想到，祖宗能想不到?

Appel 式回收還有一個(gè)充當(dāng)罕見(jiàn)情況的 “逃生門(mén)” 的安全設(shè)計(jì)：當(dāng) To Survivor 空間不足以容納一次新生代 GC 之后存活的對(duì)象時(shí)，這些對(duì)象便將通過(guò)分配擔(dān)保機(jī)制(Handle Promotion)直接進(jìn)入老年代。

所謂分配擔(dān)保，后續(xù)文章介紹垃圾收集器的時(shí)候會(huì)再詳細(xì)解釋

標(biāo)記-整理算法，Mark-Compact

Mark-Copy 算法在對(duì)象存活率較高時(shí)就要進(jìn)行較多的復(fù)制操作，效率將會(huì)降低。更關(guān)鍵的是，如果不想浪費(fèi) 50% 的空間，使用 Apple 式回收的話，就需要有額外的空間進(jìn)行分配擔(dān)保，以應(yīng)對(duì)被使用的內(nèi)存中所有對(duì)象都 100% 存活的極端情況，所以在老年代一般不能直接選用 Mark-Copy 算法

針對(duì)老年代對(duì)象的存亡特征，1974 年 Edward Lueders 提出了另外一種有針對(duì)性的 “標(biāo)記-整理”(Mark-Compact)算法

其中的標(biāo)記過(guò)程還是一樣的，但后續(xù)步驟不是直接對(duì)可回收對(duì)象進(jìn)行清理，而是讓所有存活的對(duì)象都向內(nèi)存空間一端移動(dòng)，然后直接清理掉邊界以外的內(nèi)存，如圖所示:

Mark-Sweep 算法與 Mark-Compact 算法的本質(zhì)差異在于前者是一種非移動(dòng)式的回收算法，而后者是移動(dòng)式的。是否移動(dòng)回收后的存活對(duì)象是一項(xiàng)優(yōu)缺點(diǎn)并存的風(fēng)險(xiǎn)決策

• 如果移動(dòng)存活對(duì)象，尤其是在老年代這種每次回收都有大量對(duì)象存活區(qū)域，移動(dòng)存活對(duì)象并更新所有引用這些對(duì)象的地方是一種極為負(fù)重的操作，而且這種對(duì)象移動(dòng)操作必須全程暫停用戶應(yīng)用程序才能進(jìn)行，像這樣的停頓被最初的虛擬機(jī)設(shè)計(jì)者形象地描述為 “Stop The World (STW)”。(記住這個(gè)名詞 STW，后續(xù)我們會(huì)經(jīng)常見(jiàn)到他!!!移動(dòng)存活對(duì)象時(shí)需要 STW，可達(dá)性分析中的根節(jié)點(diǎn)枚舉也需要 STW)。

總結(jié)來(lái)說(shuō)：移動(dòng)則內(nèi)存回收時(shí)會(huì)更復(fù)雜

• 如果完全不考慮移動(dòng)和整理存活對(duì)象的話，彌散于堆中的存活對(duì)象導(dǎo)致的空間碎片化問(wèn)題就只能依賴更為復(fù)雜的內(nèi)存分配器和內(nèi)存訪問(wèn)器來(lái)解決，而內(nèi)存的訪問(wèn)是用戶程序最頻繁的操作，甚至都沒(méi)有之一，假如在這個(gè)環(huán)節(jié)上增加了額外的負(fù)擔(dān)，勢(shì)必會(huì)直接影響應(yīng)用程序的吞吐量。

總結(jié)來(lái)說(shuō)：不移動(dòng)則內(nèi)存分配時(shí)會(huì)更復(fù)雜

從垃圾收集的停頓時(shí)間來(lái)看，不移動(dòng)對(duì)象的停頓時(shí)間會(huì)更短，甚至可以不需要停頓，但是從整個(gè)程序的吞吐量來(lái)看，移動(dòng)對(duì)象會(huì)更劃算。

這里的吞吐量，簡(jiǎn)單理解，就是用戶程序和垃圾收集器的效率總和

所以我們其實(shí)可以推斷出:

• 關(guān)注延遲/速度的收集器(比如 HotSpot 虛擬機(jī)中的 CMS 收集器)應(yīng)該使用 Mark-Sweep 算法。
• 關(guān)注吞吐量的收集器(比如 HotSpot 虛擬機(jī)中的 Parallel Old 收集器)應(yīng)該使用 Mark-Compact 算法。

另外，其實(shí)還有一種折中的辦法，Mark-Sweep 算法速度快，可以讓虛擬機(jī)平時(shí)大多數(shù)時(shí)間都采用 Mark-Sweep 算法，暫時(shí)容忍內(nèi)存碎片的存在，直到內(nèi)存空間的碎片化程度已經(jīng)大到影響對(duì)象分配的時(shí)候，再采用 Mark-Compact 算法收集一次，以獲得規(guī)整的內(nèi)存空間(基于 Mark-Sweep 算法的 CMS 收集器面臨空間碎片過(guò)多時(shí)采用的就是這種處理辦法)。

最后放上這道題的背誦版：

面試官：講一講有哪些垃圾收集算法?

小牛肉：主要有三種：

1)標(biāo)記-清除算法：這是最基礎(chǔ)的算法，主要思想就是先標(biāo)記出所有需要回收的對(duì)象，然后統(tǒng)一回收掉所有被標(biāo)記的對(duì)象。

這個(gè)算法主要有兩個(gè)缺點(diǎn)：

• 執(zhí)行效率不穩(wěn)定。如果堆中包含大量對(duì)象，而且其中大部分是需要被回收的，這時(shí)就必須進(jìn)行大量的標(biāo)記和清除的動(dòng)作，也就是說(shuō)執(zhí)行效率和對(duì)象數(shù)量成反比
• 內(nèi)存空間的碎片化問(wèn)題。標(biāo)記、清除之后會(huì)產(chǎn)生大量不連續(xù)的內(nèi)存碎片，空間碎片太多可能會(huì)導(dǎo)致當(dāng)程序運(yùn)行過(guò)程中需要分配較大對(duì)象時(shí)，因無(wú)法找到足夠的連續(xù)內(nèi)存而不得不提前觸發(fā)另一次垃圾收集動(dòng)作

后續(xù)兩個(gè)算法 標(biāo)記-復(fù)制算法 和 標(biāo)記-整理算法 都是在 標(biāo)記-清除算法 的基礎(chǔ)上做的改進(jìn)。

2)標(biāo)記-復(fù)制算法：主要思想就是將可用內(nèi)存按容量劃分為大小相等的兩塊，每次只使用其中的一塊。當(dāng)這一塊的內(nèi)存用完了，就將還存活著的對(duì)象復(fù)制到另外一塊上面，然后再把已使用過(guò)的內(nèi)存空間一次性全部清理掉。

這個(gè)半?yún)^(qū)復(fù)制算法也有兩個(gè)比較明顯的問(wèn)題：

• 不適用于對(duì)象存活率較高的情況(即一般不適用于老生代)
• 可用內(nèi)存空間縮小了一半(針對(duì)這個(gè)問(wèn)題，“Appel 式回收” 進(jìn)行了改進(jìn)，就是根據(jù)新生代 “朝生夕滅” 的特點(diǎn)，能夠在一輪垃圾收集后活下來(lái)的對(duì)象少之又少，所以，我們其實(shí)并不需要這么大一塊的保留區(qū)域。具體做法是把新生代分為一塊較大的 Eden 空間和兩塊較小的 Survivor 空間，每次分配內(nèi)存只使用 Eden 和其中一塊 Survivor。發(fā)生垃圾收集時(shí)，在清空之前需要將存活對(duì)象復(fù)制到另一塊 Survivor 中，然后直接清空 Eden 和已用過(guò)的那塊 Survivor 空間。另外，使用 Apple 式回收的話，還需要有額外的空間進(jìn)行分配擔(dān)保，因?yàn)槲覀儧](méi)有辦法百分百保證分配給 To Survivor 的內(nèi)存空間能夠容納全部的存活對(duì)象，常見(jiàn)的做法就是當(dāng) To Survivor 空間不足以容納一次新生代 GC 之后存活的對(duì)象時(shí)，這些對(duì)象便將通過(guò)分配擔(dān)保機(jī)制直接進(jìn)入老年代)。

3)標(biāo)記-整理算法：主要思想就是讓所有存活的對(duì)象都向內(nèi)存空間一端移動(dòng)，然后直接清理掉邊界以外的內(nèi)存。這種移動(dòng)式的算法相對(duì)于非移動(dòng)式的標(biāo)記-清除算法來(lái)說(shuō)，吞吐量更高，不過(guò)速度相對(duì)較慢，因?yàn)橐苿?dòng)對(duì)象需要 Stop the world。所以，關(guān)注延遲/速度的收集器(比如 HotSpot 虛擬機(jī)中的 CMS 收集器)應(yīng)該使用 Mark-Sweep 算法，而關(guān)注吞吐量的收集器(比如 HotSpot 虛擬機(jī)中的 Parallel Old 收集器)應(yīng)該使用 Mark-Compact 算法。

另外，其實(shí)還有一種折中的辦法，Mark-Sweep 算法速度快，可以讓虛擬機(jī)平時(shí)大多數(shù)時(shí)間都采用 Mark-Sweep 算法，暫時(shí)容忍內(nèi)存碎片的存在，直到內(nèi)存空間的碎片化程度已經(jīng)大到影響對(duì)象分配的時(shí)候，再采用 Mark-Compact 算法收集一次，以獲得規(guī)整的內(nèi)存空間(基于 Mark-Sweep 算法的 CMS 收集器面臨空間碎片過(guò)多時(shí)采用的就是這種處理辦法)。