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

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

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

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

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

標(biāo)記 and 清除。

拓展來說：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)來說：移動則內(nèi)存回收時會更復(fù)雜

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

總結(jié)來說：不移動則內(nèi)存分配時會更復(fù)雜

從垃圾收集的停頓時間來看，不移動對象的停頓時間會更短，甚至可以不需要停頓，但是從整個程序的吞吐量來看，移動對象會更劃算。

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

所以我們其實可以推斷出:

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

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

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

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

小牛肉：主要有三種：

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

這個算法主要有兩個缺點：

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

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

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

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

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

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

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