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

• 標記-清除算法
• 標記-復制算法
• 標記-整理算法

全文思維導圖如下：

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

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

標記 and 清除。

拓展來說：

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

當然了，反過來也是可以的，標記存活的對象，統一回收所有未被標記的對象。

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

標記-清除算法的主要缺點有兩個：

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

標記-清除算法的執行過程如圖：

標記-復制算法，Mark-Copy

“標記-復制”(Mark-Copy)算法常被簡稱為復制算法。

為了解決標記-清除算法面對大量可回收對象時執行效率低的問題，1969 年 Fenichel 提出了一種稱為 “半區復制”(Semispace Copying)的垃圾收集算法，具體思想大概是這樣：

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

很顯然，這個方法并不適用于多數對象都是存活的情況，因為這將會產生大量的內存間復制的開銷。

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

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

該算法的執行過程如圖所示：

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

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

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

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

1989 年 Andrew Appel 基于此提出了一種更優化的半區復制分代策略，現在稱為 “Appel 式回收”。HotSpot 虛擬機的 Serial、ParNew 等新生代收集器均采用了這種策略來設計新生代的內存布局。

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

這兩塊 Survivor 空間也分別被稱為 From Survivior 和 To Survivor，很顯然，每經過一次新生代 GC，From Survivor 和 To Survivor 的身份就會互換。

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

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

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

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

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

所謂分配擔保，后續文章介紹垃圾收集器的時候會再詳細解釋

標記-整理算法，Mark-Compact

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

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

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

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

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

總結來說：移動則內存回收時會更復雜

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

總結來說：不移動則內存分配時會更復雜

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

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

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

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

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

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

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

小牛肉：主要有三種：

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

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

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

后續兩個算法 標記-復制算法 和 標記-整理算法 都是在 標記-清除算法 的基礎上做的改進。

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

這個半區復制算法也有兩個比較明顯的問題：

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

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

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