在面試過程中，垃圾回收算法經(jīng)常會被問到，本文就來分享下常見的垃圾回收算法及其優(yōu)缺點，以幫助你在面試過程中更好的應(yīng)對這些面試問題。

一、GC 入門：GC 基礎(chǔ)概念

垃圾回收（Garbage Collection，GC） 是一種自動內(nèi)存管理機制。當(dāng)程序申請的堆內(nèi)存不再被使用時，GC 會主動將這些內(nèi)存回收，以供后續(xù)分配或返還給操作系統(tǒng)。

1. 內(nèi)存管理三大參與者

在程序進行 GC 時，有以下 3 個參與者參與到了 GC 的過程中：

• Mutator（用戶程序）
• Allocator（內(nèi)存分配器）
• Collector（垃圾回收器）

上圖是內(nèi)存管理的三個參與者，Mutator 用戶程序、Allocator 內(nèi)存分配器和 Collector 垃圾回收。用戶程序 Mutator 會通過內(nèi)存分配器 Allocator 去申請內(nèi)存 Memory，而垃圾回收器 Collector 則會回收無用的堆內(nèi)存。

2. GC 核心優(yōu)勢與劣勢

使用 GC 會給開發(fā)者帶來很多好處，以下是 GC 的核心優(yōu)勢：

• 開發(fā)者無需手動管理內(nèi)存，降低心智負擔(dān)；
• 自動釋放殘留內(nèi)存，減少內(nèi)存泄漏風(fēng)險；
• 可通過調(diào)控 API（如觸發(fā)時機、暫停策略）進行優(yōu)化。

使用 GC 通常也會帶來以下劣勢：

• 暫停（Stop-The-World，STW）可能影響實時性
• 性能開銷與程序吞吐率相關(guān)

3. 不同語言內(nèi)存管理策略對比

不同編程語言采用的內(nèi)存管理策略是不一樣的，下表是常見內(nèi)存管理策略比較：

二、能否回收：基礎(chǔ)垃圾識別算法

對堆垃圾回收前的第一步就是要判斷哪些對象已經(jīng)死亡（即不能再被任何途徑使用的對象）。判斷一個對象是否存活有引用計數(shù)、可達性分析這兩種算法，兩種算法各有優(yōu)缺點。、

Java 和 Go 都使用可達性分析算法，一些動態(tài)腳本語言（如：ActionScript）一般使用引用計數(shù)算法。

1. 引用計數(shù)（Reference Counting）

引用計數(shù)會為每個對象維護一個計數(shù)器，當(dāng)該對象被其他對象引用時加1，引用失效時減 1，當(dāng)引用次數(shù)為 0 后即可回收對象。

引用計數(shù)通過在對象上增加自己被引用的次數(shù)，被其他對象引用時加 1，引用自己的對象被回收時減1，引用數(shù)為 0 的對象即為可以被回收的對象，這種算法在內(nèi)存比較緊張和實時性比較高的系統(tǒng)中使用比較廣泛，如 PHP，Python 等。

優(yōu)點：

• 原理和實現(xiàn)都比較簡單；
• 回收及時性高，引用計數(shù)為0則立即回收，不需要想其他GC機制需要等待特定的時間回收；
• 不需要暫停應(yīng)用即可完成回收。

缺點：

• 無法解決循環(huán)引用的問題，例如：a.b=b; b.a=a；
• 時間和空間成本高：每個對象需要額外的空間來存儲引用計數(shù)，在棧上修改引用計數(shù)的時間成本高（因為需要額外的原子操作來保證線程安全）；
• 無法保證耗時：引用計數(shù)是一種攤銷算法，會將內(nèi)存的回收分?jǐn)偟秸麄€程序的運行過程，當(dāng)銷毀一個很大的樹形結(jié)構(gòu)時無法保證響應(yīng)時間。

2. 可達性分析（Reachability Analysis）

可達性分析的核心思想是判斷一個對象是否可達，如果這個對象一旦不可達就可以立刻被 GC 回收了，那么我們怎么判斷一個對象是否可達呢？第一步，從根節(jié)點開始找出所有的全局變量和當(dāng)前函數(shù)棧里的變量，標(biāo)記為可達。第二步，從已經(jīng)標(biāo)記的數(shù)據(jù)開始，進一步標(biāo)記它們可訪問的變量，以此類推，專業(yè)術(shù)語叫傳遞閉包。當(dāng)追蹤結(jié)束時，沒有被打上標(biāo)記的對象就被判定是不可觸達。

該算法屬于追蹤式算法，目的是回收不可達對象，可達對象主要包括兩類：

• GC Roots 對象： 包括全局對象，棧上對象；
• 與 GC Roots 對象通過引用鏈相連的對象。

對于不可達對象，我們認(rèn)為該對象為垃圾對象，應(yīng)該被回收。

同上述的引用計數(shù)法相比，追蹤式算法具有如下優(yōu)點：

• 解決了循環(huán)引用的問題；
• 占用的空間少了。

和引用計數(shù)法相比，也有以下缺點：

• 無法立刻識別出垃圾對象，需要依賴 GC 線程；
• 算法在標(biāo)記時必須暫停整個程序，即 STW(stop the world)，否則其他線程有可能會修改對象的狀態(tài)從而回收不該被回收的對象。

三、如何回收：基于可達性分析的 GC 算法

現(xiàn)代主流的 GC 算法都基于可達性分析，并在此基礎(chǔ)上實現(xiàn)了不同的回收策略。

1. 標(biāo)記-復(fù)制算法（Copying Collector）

它把內(nèi)存空間劃分為兩個相等的區(qū)域，每次只使用其中一個區(qū)域。在垃圾收集時，遍歷當(dāng)前使用的區(qū)域，把存活對象復(fù)制到另一個區(qū)域中，最后將當(dāng)前使用的區(qū)域的可回收對象進行回收。

實現(xiàn)主要分為標(biāo)記和復(fù)制兩個步驟：

• 標(biāo)記： 記錄需要回收的垃圾對象；
• 復(fù)制： 將內(nèi)存分為大小相同的兩塊，當(dāng)某一塊的內(nèi)存使用完了之后就將使用中的對象挨個復(fù)制到另一塊內(nèi)存中，最后將當(dāng)前內(nèi)存恢復(fù)為未使用狀態(tài)。

優(yōu)點：

• 不用進行大量垃圾對象的掃描：標(biāo)記-復(fù)制算法需要從 GC-root 對象出發(fā)，將可達的對象復(fù)制到另外一塊內(nèi)存后直接清理當(dāng)前這塊的內(nèi)存即可；
• 解決了內(nèi)存碎片問題，防止分配大空間對象時提前 GC  的問題。

缺點：

• 復(fù)制成本問題：在可達對象占用內(nèi)存高的時候，復(fù)制成本會很高；
• 內(nèi)存利用率低：相當(dāng)于可利用的內(nèi)存僅有一半。

2. 標(biāo)記-清除算法（Mark-and-Sweep）

標(biāo)記-清除算法是最常見的垃圾收集算法，標(biāo)記清除收集器是跟蹤式垃圾收集器，其執(zhí)行過程可以分成標(biāo)記（Mark）和清除（Sweep）兩個階段：

• 標(biāo)記階段：暫停應(yīng)用程序的執(zhí)行，從根對象觸發(fā)查找并標(biāo)記堆中所有存活的對象；
• 清除階段：遍歷堆中的全部對象，回收未被標(biāo)記的垃圾對象并將回收的內(nèi)存加入空閑鏈表，恢復(fù)應(yīng)用程序的執(zhí)行。

優(yōu)點：

• 實現(xiàn)簡單；
• 算法吞吐量高，即運行用戶代碼時間 /（運行用戶代碼時間+運行垃圾收集時間）；
• 空間利用率高，和標(biāo)記-復(fù)制相比，不需要額外的空間復(fù)制對象，和引用計數(shù)法相比，也不需要額外的空間設(shè)置計數(shù)器

缺點：

• 執(zhí)行期間需要把整個程序完全暫停，不能異步的進行垃圾回收；
• 容易產(chǎn)生大量不連續(xù)的內(nèi)存隨便，碎片太多可能會導(dǎo)致后續(xù)沒有足夠的連續(xù)內(nèi)存分配給較大的對象，從而提前觸發(fā)新的一次垃圾收集動作。

3. 標(biāo)記-整理算法（Mark-and-Compact）

標(biāo)記-整理算法（也叫標(biāo)記-壓縮算法）標(biāo)記出所有可達對象，然后將可達對象移動到空間的另外一段，最后清理掉邊界以外的內(nèi)存。

優(yōu)點：

• 避免了內(nèi)存碎片化的問題；
• 適合老年代算法，老年代對象存活率高的情況下，標(biāo)記整理算法由于不需要復(fù)制對象，效率更高。

缺點：整理的過程復(fù)雜，需要多長遍歷內(nèi)存，導(dǎo)致 STW 時間比標(biāo)記清除算法高。

四、性能優(yōu)化：GC 優(yōu)化策略

在解決了“能否回收”和“如何回收”的基礎(chǔ)問題后，垃圾回收技術(shù)演進的下一個核心目標(biāo)便是“如何更高效、更低延遲地回收”。

為了應(yīng)對“Stop-The-World”暫停過長這一核心痛點，現(xiàn)代垃圾回收器主要從兩個維度進行優(yōu)化：一是通過分代收集（Generational GC），根據(jù)對象的生命周期特點“區(qū)別對待”，從而減少單次回收的工作量。二是通過增量與并發(fā) GC（Incremental & Concurrent GC），改變回收的執(zhí)行方式，將巨大的暫停拆解或與用戶程序并行，從而最大化地降低對程序的影響。

1. 分代收集算法（Generational GC）

分代收集算法按照對象生命周期的長短劃分到不同分區(qū)：

• 對于生命周期短的新生代區(qū)域（Young），每次回收僅需要考慮如何保留少量存活對象，因此可以采用標(biāo)記-復(fù)制法完成 GC；
• 對于生命周期長的老年代區(qū)域（Old），可以通過減少 GC 的頻率來提供效率，同時由于對象存活率高沒有額外的空間用于復(fù)制，因此一般可以使用標(biāo)記清除法或標(biāo)記整理法。

這樣劃分，堆就分成了 Young 和 Old 兩個分區(qū)，因此 GC 也分為新生代 GC 和老年代 GC。

對象的分配策略：

• 對象優(yōu)先在新生代上 Eden 區(qū)域分配；
• 大對象直接進入老年代；
• 新生代中周期較長的對象在 s0 或 s1 區(qū)每經(jīng)過一次新生代 GC，就增加一歲，增加到一定閾值的時候，就進入老年代區(qū)域。

2. 增量與并發(fā) GC

前面提到的傳統(tǒng) GC 算法都會 STW，這存在兩個嚴(yán)重的弊端：

• 對實時性程序來說，很致命；
• 對多核計算機來說，會造成計算資源的浪費。

為了避免一次性完成所有 GC 工作導(dǎo)致的長時間 STW，可以將 GC 過程拆分為多個小步驟，與用戶程序交替執(zhí)行。

• 增量 GC（Incremental GC）：將 GC 工作分成多個階段，穿插在用戶程序中執(zhí)行，分?jǐn)偭藭和r間；
• 并發(fā) GC（Concurrent GC）：讓 GC 線程與用戶程序線程在一段時間內(nèi)同時運行，極大地減少了 STW。

這兩種策略都依賴于三色標(biāo)記法和屏障技術(shù)來保證在并發(fā)環(huán)境下的正確性。

3. 增量 GC（Incremental GC）

分?jǐn)?GC 時間，避免程序長時間暫停；

內(nèi)存屏障技術(shù)，需要額外時間開銷，并且由于內(nèi)存屏障技術(shù)的保守性，一些垃圾對象不會被回收，會增加一輪 GC 的總時長。

4. 并發(fā) GC（Concurrent GC）

• 運行 GC 和用戶程序并行；
• 一定程度上利用多核計算機的優(yōu)勢減少了對用戶程序的干擾，不該寫屏障的額外開銷和保守性問題仍然存在，這是不可避免的。

五、并發(fā)保證：三色標(biāo)記與屏障技術(shù)

引入并發(fā) GC 的目的是為了消除或顯著縮短“Stop-The-World”的暫停時間，但這帶來了一個棘手的挑戰(zhàn)：當(dāng) GC 線程正在遍歷對象圖時，用戶線程可能同時在修改對象間的引用關(guān)系。這種并發(fā)修改可能導(dǎo)致 GC“看錯”對象的可達性，從而錯誤地回收仍在使用的對象。

為了保證在并發(fā)環(huán)境下數(shù)據(jù)的一致性和 GC 的正確性，現(xiàn)代垃圾回收器引入了 三色標(biāo)記法（Tri-color Marking）作為核心算法框架，并配合屏障技術(shù)（Barrier）來追蹤并發(fā)間的引用變化，確保萬無一失。

1. 三色標(biāo)記（Tri-color Marking）

前面的標(biāo)記-X 類算法都有一個問題，那就是 STW（即 GC 時暫停整個應(yīng)用程序），三色標(biāo)記法是對標(biāo)記階段進行改進的算法。目的是在不暫停程序的情況下即可完成對象的可達性分析，GC 線程將所有對象分為三類：

• 白色對象：未搜索的對象（潛在的垃圾），在回收周期開始時所有對象都是白色，在回收周期結(jié)束時，所有對象都是垃圾回收對象；
• 灰色對象：正在搜索的對象（活躍的對象），但是對象身上還有一個或多個引用沒有掃描；
• 黑色對象：已搜索完成的對象（活躍的對象），所有的引用已被掃描完

三色標(biāo)記算法屬于增量式 GC 算法，回收器首先將所有對象著色成白色，然后從 GC Roots 出發(fā)，逐步把所有可達的對象變成灰色再到黑色，最終所有的白色對象都是不可達對象。

GC Roots 區(qū)域主要是程序運行到當(dāng)前時刻的棧和全局?jǐn)?shù)據(jù)區(qū)域。

具體實現(xiàn)：

• 初始時所有對象都是白色的；
• 從 GC Roots 對象出發(fā)，掃描所有可達對象并標(biāo)記為灰色，放入待處理隊列；
• 從隊列取出一個灰色對象并標(biāo)記為黑色，將其引用對象標(biāo)記為灰色，放入隊列；
• 重復(fù)上一步驟，直到灰色對象隊列為空；
• 此時剩下的所有白色對象都是垃圾對象。

結(jié)合如下動圖理解：

可以看出：A、F 為 GC Roots 根直接引用的對象，E、G、H 對象為垃圾，需要回收。

優(yōu)點：不需要 STW。

缺點：

• 如果產(chǎn)生垃圾速度大于回收速度時，可能會導(dǎo)致程序中垃圾對象越來越多而無法及時收集；
• 線程切換和上下文轉(zhuǎn)換的消耗會使得垃圾回收的總體成本上升，從而降低系統(tǒng)吞吐量。

三色標(biāo)記法存在并發(fā)性問題：

• 可能會出現(xiàn)野指針（指向沒有合法地址的指針），從而造成嚴(yán)重的程序錯誤；
• 漏標(biāo)，錯誤的回收非垃圾對象。

2. 屏障技術(shù)

屏障技術(shù)是在用戶程序讀取、創(chuàng)建以及更新對象指針時執(zhí)行的一段代碼，簡單來說，內(nèi)存屏障是一種能夠保證內(nèi)存操作順序的技術(shù)。根據(jù)操作類型的不同，屏障技術(shù)分為讀屏障和寫屏障兩種。

由于讀屏障需要在讀操作時加入代碼片段，對用戶程序的影響較大。因此，Go 語言采用寫屏障來保證三色不變式，寫屏障技術(shù)包括 Dijkstra 在 1978 年提出插入寫屏障和 Yuasa 在 1990 年提出刪除寫屏障兩種。

Go 語言中使用到的屏障技術(shù)包含以下 3 種：

3. 插入寫屏障

插入寫屏障的原理是：當(dāng)有黑色對象 A 指向新對象 D 時，如果被指向?qū)ο?D 為白色，則將 D 對象設(shè)置為灰色，它實現(xiàn)了強三色不變式。

如上圖的標(biāo)記過程：

• 垃圾收集器將根集合上的 A 對象標(biāo)記為黑色，并將 A 對象指向的 B 對象標(biāo)記成灰色；
• 用戶程序修改 A 對象的指針，將原本指向 B 對象的指針指向 C 對象，這時，觸發(fā)插入寫屏障將 C 對象標(biāo)記為灰色；
• 垃圾收集器依次遍歷其它灰色對象，標(biāo)記為黑色。

插入寫屏障將被添加引用的白色對象都標(biāo)記為了灰色，這種方法實現(xiàn)簡單，但也有明顯的缺點：

• 缺點一：未存活的對象可能需要兩次回收，假設(shè)上述第 2 步到第 3 步之間，A 對象的指針又從指向 C 改為指向 B，那 C 對象就是垃圾，應(yīng)該回收。但是此時灰色的對象 C 會被垃圾收集器認(rèn)為是存活的，這些被錯誤標(biāo)記的對象只有在下一個循環(huán)才會被回收；
• 缺點二：寫屏障只會對堆上的內(nèi)存對象啟動寫屏障（插入和刪除寫屏障共有的）。而棧上的對象需要保證內(nèi)存安全時，必須在標(biāo)記階段重新對棧上的對象進行 STW 掃描。重新掃描時需要暫停程序，影響整體性能。

4. 刪除寫屏障

刪除寫屏障的原理是：對象 A 被引用時，如果引用它的對象被刪除了，那么白色的 A 對象將被標(biāo)記為灰色，它實現(xiàn)了弱三色不變式。

如上圖的標(biāo)記過程：

• 垃圾收集器將根集合上的 A 對象標(biāo)記為黑色，并將 A 對象指向的 B 對象標(biāo)記成灰色；
• 用戶程序?qū)?A 指向 B 對象的指針，修改為指向 C 對象。這時，觸發(fā)刪除寫屏障，但因為 B 對象不為白色，所以不做改變；
• 用戶程序?qū)?B 指向 C 對象的指針刪除，觸發(fā)刪除寫屏障，此時，白色的 C 對象被標(biāo)記為灰色；
• 垃圾收集器依次遍歷程序中的灰色對象，將它們標(biāo)記為黑色。

刪除寫屏障將被刪除引用的白色對象都標(biāo)記為了灰色，但是它也有缺點和局限性：

• 缺點一：回收精度低，當(dāng)對象 B 已經(jīng)被刪除時，它仍然可以活過這一輪在下一個循環(huán)才被回收；
• 缺點二：同插入寫屏障，重新 STW 掃描棧對象。

5. 混合寫屏障（Go 1.8+）

傳統(tǒng)的寫屏障在處理棧內(nèi)存時仍需短暫的 STW 進行重新掃描。Go 語言的混合寫屏障結(jié)合了插入和刪除寫屏障的優(yōu)點，并進行了優(yōu)化：

(1) GC 開始時，將棧上所有可達對象標(biāo)記為黑色，無需 STW 重掃描。

(2) GC 期間，棧上創(chuàng)建的新對象均為黑色。

(3) 對堆上的指針操作，同時啟用插入和刪除寫屏障的邏輯：

• 將被刪除引用的對象標(biāo)記為灰色；
• 將被添加引用的對象標(biāo)記為灰色。

這種方式幾乎消除了 STW 的重掃描階段，使得 Go 的 GC 暫停時間達到亞毫秒級別。

六、總結(jié)

本文回顧了各類垃圾回收算法的原理與演進后，GC 技術(shù)可以分為兩大模塊：

• 判定可回收對象：引用計數(shù) vs. 可達性分析
• 執(zhí)行回收策略：標(biāo)記-復(fù)制、標(biāo)記-清除、標(biāo)記-整理 + 并發(fā)／增量調(diào)度

分代收集、三色標(biāo)記與屏障技術(shù)是現(xiàn)代高性能 GC 的核心。面試中應(yīng)熟練掌握各方案的原理、優(yōu)缺點與適用場景，并能結(jié)合具體語言（如 Java、Go）的實現(xiàn)細節(jié)進行答題。