如果大家關注 JDK，會發現在頻繁釋出的 JDK 版本中，和垃圾回收相關的 JEP (JDK Enhancement Proposals，Java 增強提案）越來越多了，垃圾回收（Garbage Collection，GC）正處于方興未艾的階段。譬如，在 JEP-248 中 G1 替代了并行垃圾回收器成為 JVM 中預設的垃圾回收器，JEP-333 加入了實驗性質的 ZGC；最新的 JEP-189 引入了名為 Shenandoah GC 的垃圾回收器。
對于這麼一個有趣的話題，我決定寫篇文章來介紹，與很多介紹垃圾回收器的文章不同，本文不會涉及「某某垃圾回收器特性」和「如何使用某某垃圾回收器」等「what&how」的内容，而是從底層的垃圾回收算法開始，着重去闡釋不同垃圾回收器在算法設計和實作時的一些技術細節，去探索「why」這一部分，通過對比不同的垃圾回收算法和其實作，進一步感覺目前垃圾回收的發展脈絡。
本文主要分為上下兩個部分：
第一部分為「算法篇」，主要介紹一些重要的 GC 算法，去領略 GC 獨特的思維方式和各算法的特性，這些是和具體的程式設計語言無關的；
第二部分為「實作篇」，主要介紹 JVM 上的一些垃圾回收器實作，包括 G1、ZGC、Shenandoah GC 等，通過了解這些商業垃圾回收器的設計理念，加深對垃圾回收算法的了解。
下面是第一部分，「算法篇」的内容。
一 垃圾回收概述
垃圾回收（Garbage Collection，GC）引起大家的關注，是從1995 年 Java 釋出後開始的。事實上，GC 作為計算機科學領域非常熱的研究話題之一，最早可以追溯到 1959 年的夏天，起初是用用來簡化 Lisp 記憶體管理的。在接下來60餘年的時間裡， 通過 Cheney、Baker 等大師的不斷努力，GC 的世界裡出現了标記清除、複制、分代、增量回收等一系列 GC 算法，基于這些算法，又出現了種類繁複的垃圾回收器。
GC 的定義
首先我們來看一下什麼是 GC。
GC 把程式不用的記憶體空間視為「垃圾」，（幾乎所有的）GC 要做的就隻有兩件事：
- 找到記憶體空間裡的垃圾，使其和活對象分開來。
- 回收垃圾對象的記憶體，使得程式可以重複使用這些記憶體。
GC 給我們帶來的好處不言而喻，選擇 GC 而不是手動釋放資源的原因很簡單：程式比人更可靠。即便是 C/C++ 這種沒有 GC 的語言，也有類似 Boehm GC 這樣的第三方庫來實作記憶體的自動管理了。可以毫不誇張地說，GC 已經是現代程式設計語言的标配。
GC 的流派
GC 從其底層實作方式（即 GC 算法）來看，大體可以分為兩大類：基于可達性分析的 GC和基于引用計數法的 GC。當然，這樣的分類也不是絕對的，很多現代 GC 的設計就融合了引用計數和可達性分析兩種。
可達性分析法
基本思路就是通過根集合（gc root）作為起始點，從這些節點出發，根據引用關系開始搜尋，所經過的路徑稱為引用鍊，當一個對象沒有被任何引用鍊通路到時，則證明此對象是不活躍的，可以被回收。使用此類算法的有JVM、.NET、Golang等。
引用計數法
引用計數法沒有用到根集概念。其基本原理是：在堆記憶體中配置設定對象時，會為對象配置設定一段額外的空間，這個空間用于維護一個計數器，如果有一個新的引用指向這個對象，則計數器的值加1；如果指向該對象的引用被置空或指向其它對象，則計數器的值減1。每次有一個新的引用指向這個對象時，計數器加1；反之，如果指向該對象的引用被置空或指向其它對象，則計數器減1；當計數器的值為0時，則自動删除這個對象。使用此類算法的有 Python、Objective-C、Per l等。
基于可達性分析法的 GC 垃圾回收的效率較高，實作起來比較簡單（引用計算法是是算法簡單，實作較難），但是其缺點在于 GC 期間，整個應用需要被挂起（STW，Stop-the-world，下同），後面很多此類算法的提出，都是在解決這個問題（縮小 STW 時間）。
基于引用計數法的 GC，天然帶有增量特性（incremental），GC 可與應用交替運作，不需要暫停應用；同時，在引用計數法中，每個對象始終都知道自己的被引用數，當計數器為0時，對象可以馬上回收，而在可達性分析類 GC 中，即使對象變成了垃圾，程式也無法立刻感覺，直到 GC 執行前，始終都會有一部分記憶體空間被垃圾占用。
上述兩類 GC 各有千秋，真正的工業級實作一般是這兩類算法的組合，但是總體來說，基于可達性分析的 GC 還是占據了主流，究其原因，首先，引用計數算法無法解決「循環引用無法回收」的問題，即兩個對象互相引用，是以各對象的計數器的值都是 1，即使這些對象都成了垃圾（無外部引用），GC 也無法将它們回收。當然上面這一點還不是引用計數法最大的弊端，引用計數算法最大的問題在于：計數器值的增減處理非常繁重，譬如對根對象的引用，此外，多個線程之間共享對象時需要對計數器進行原子遞增/遞減，這本身又帶來了一系列新的複雜性和問題，計數器對應用程式的整體運作速度的影響，這裡的細節可以參考文章：Boost's shared_ptr up to 10× slower than OCaml's garbage collection[1]。
本文後面介紹的垃圾回收算法，主要就是可達性分析類算法及其變種。
二 垃圾回收核心概念
在深入研究垃圾回收算法的實作細節之前，有必要知道 GC 算法中的一些基本概念，這對了解 GC 算法的基本原理和演進過程是有幫助的。除了算法基礎名詞外，我們需要深入了解GC 世界裡極其重要的兩個核心概念：讀/寫屏障和三色标記法。
基礎名詞
根節點（GC Roots）
在 GC 的世界裡，根是執行可達性分析的「起點」部分，在 Java 語言中，可以作為 GC Roots 的對象包括：
- 虛拟機棧中（棧幀中的本地變量表）引用的對象
- 方法區中的類靜态屬性引用的對象
- 方法區中常量引用的對象
- 本地方法棧中 JNI（Native 方法） 引用的對象
是否作為根的判定依據：程式是否可以直接引用該對象（譬如調用棧中的變量指針）。同時還需要注意的是：不同的垃圾回收器，選擇 GC Roots 的範圍是不一樣的。
并行回收&&串行回收
根據垃圾回收的運作方式不同，GC 可以分為三類：
- 串行執行：垃圾回收器執行的時候應用程式挂起，串行執行指的是垃圾回收器有且僅有一個背景線程執行垃圾對象的識别和回收；
- 并行執行：垃圾回收器執行的時候應用程式挂起，但是在暫停期間會有多個線程進行識别和回收，可以減少垃圾回收時間；
- 并發執行：垃圾回收器執行期間，應用程式不用挂起正常運作（當然在某些必要的情況下垃圾回收器還是需要挂起的）。
上面并發和并行容易混淆，因為在 Java 中，我們提到的并發天然會聯想到是「同一類多個線程」執行「同一類任務」，在 GC 中，并發描述的是「GC 線程」和「應用線程」一起工作。
當我們說到某種垃圾回收器支援并發時，并不意味着在垃圾回收的過程中都是并發的，譬如，G1 和 CMS 垃圾回收器支援并發标記，但是在對象轉移、引用處理、符号表和字元串表處理、類解除安裝時，是不支援并發的。總之，并發的表述具有「階段性」。
三色标記法
可達性分析類 GC 都屬于「搜尋型算法」（标記階段經常用到深度優先搜尋），這一類算法的過程可以用 Edsger W. Dijkstra 等人提出的三色标記算法（Tri-color marking）來進行抽象（算法詳情可以參考論文：On-the-fly Garbage Collection：An Exercise in Cooperation）[2]。顧名思義，三色标記算法背後的首要原則就是把堆中的對象根據它們的顔色分到不同集合裡面，這三種顔色和所包含的意思分别如下所示：
- 白色：還未被垃圾回收器标記的對象
- 灰色：自身已經被标記，但其擁有的成員變量還未被标記
- 黑色：自身已經被标記，且對象本身所有的成員變量也已經被标記
在 GC 開始階段，剛開始所有的對象都是白色的，在通過可達性分析時，首先會從根節點開始周遊，将 GC Roots 直接引用到的對象 A、B、C 直接加入灰色集合，然後從灰色集合中取出 A，将 A 的所有引用加入灰色集合，同時把 A 本身加入黑色集合。最後灰色集合為空，意味着可達性分析結束，仍在白色集合的對象即為 GC Roots 不可達，可以進行回收了。下面是第一輪标記結束後，各個對象的顔色分布。
基于可達性分析的 GC 算法，标記過程幾乎都借鑒了三色标記的算法思想，盡管實作的方式不盡相同，比如标記的方式有棧、隊列、多色指針等。
讀屏障&&寫屏障
在标記對象是否存活的過程中，對象間的引用關系是不能改變的，這對于串行 GC 來說是可行的，因為此時應用程式處于 STW 狀态。對于并發 GC 來說，在分析對象引用關系期間，對象間引用關系的建立和銷毀是肯定存在的，如果沒有其他補償手段，并發标記期間就可能出現對象多标和漏标的情況。還是以上面三色标記法中的例子說明：
（1）多标
假設 C 被标為灰色後，在進行下面的标記之前，A 和 C 之間的引用關系解除了（應用程式），按照三色标記法，C 和 E 都應該是垃圾，而事實上，C 不會在本輪 GC 活動中被回收，這部分本應該回收但是沒有回收到的記憶體，被稱之為「浮動垃圾」。
（2）漏标
如下圖所示，對象 C 在被标記為灰色後，對象 C 斷開了和對象 E 之間的引用，同時對象 A 建立了和對象 E 之間的引用。在進行後面的标記時，因為 C 沒有對 E 的引用，是以不會将 E 放到灰色集合，雖然 A 重新引用了 E，但因為 A 已經是黑色了，不會再傳回重新進行深度周遊了。最終導緻的結果是：對象 E 會一直停留在白色集合中，最後被當作垃圾回收，事實上 E 卻是活動對象，這種情況也是不可接受的。
多标不會影響程式的正确性，隻會推遲垃圾回收的時機，漏标會影響程式的正确性，需要引入讀寫屏障來解決漏标的問題。GC 裡的讀屏障（Read barrier）和寫屏障（Write barrier）指的是程式在從堆中讀取引用或更新堆中引用時，GC 需要執行一些額外操作，其本質是一些同步的指令操作，在進行讀/寫引用時，會額外執行這些指令。讀/寫屏障實作的是「對讀/寫引用這個操作的環切」，即該操作前後都在屏障的範疇内，可以将讀/寫屏障類比于 Spirng 架構裡的攔截器。下面所示的代碼，當從 foo 的成員變量第一次從堆上被加載時，就會觸發讀屏障（後續使用該引用不會觸發 ），而當 bar 的成員變量(引用類型的)被配置設定/寫入時，會觸發寫屏障。
void example(Foo foo) {
Bar bar = foo.bar; // 這裡觸發讀屏障
bar.otherObj = makeOtherValue(); // 這裡觸發寫屏障
}
讀寫屏障是如何解決并發标記時的漏标的？總結一下發生漏标的充分必要條件是：
- 應用線程插入了一個從黑色對象（A）到白色對象（E）的新引用。
- 應用線程删除了從灰色對象（C）到白色對象（E）的直接或者間接引用。
要避免對象的漏标，隻需要打破上述兩個條件中的任何一個即可，兩種不同的方法核心都是采用了讀寫屏障：
（a）方法一：
- 開啟寫屏障，當新增引用關系後，觸發寫屏障，發出引用的黑色或者白色對象會被标記成灰色（例子中 A 将被标記為灰色并進入灰色集合），或者将被引用對象标記為灰色。
- 開啟讀屏障，當檢測到應用即将要通路白色對象時，觸發讀屏障，GC 會立刻通路該對象并将之标為灰色。這種方法被稱為「增量更新（Increment Update）」。
（b）方法二：
- 開啟寫屏障。當删除引用關系前，将所有即将被删除的引用關系的舊引用記錄下來（C -> E），最後以這些舊引用為根重新掃描一遍，這種方法實際上是「SATB（Snapshot At The Begining） 算法」的一種具體實作。
注：SATB 算法是由 Taiichi Yuasa 為增量式标記清除垃圾收集器開發的一個算法，其核心思想是：GC 開始之前，會複制一份引用關系快照，如果某個指針的位址被改變了，那麼之前的位址會被加入待标記棧中，便于後面再次檢查，這樣就可以保證在 GC 時，所有的對象都會被周遊到，即使指向它們的指針發生了改變。鑒于篇幅原因，這裡不再講述，感興趣的讀者可自行檢視 Yuasa 的論文（Real-time garbage collection on general-purpose machines[3]）。
通過讀寫屏障可以解決并發标記時的漏标問題，具體在工程實踐中，不同的垃圾回收器又有不同實作，譬如針對 HotSpot 虛拟機，CMS 使用了「寫屏障 + 增量更新」的方法，G1 和 Shenandoah是通過「寫屏障 + SATB」來完成的，而 ZGC 則采取了「讀屏障」的方式。
下面是 HotSpot 虛拟機中寫屏障的一段代碼，這段代碼記錄下了所有的引用關系的變化情況。
void post_write_barrier(oop* field, oop val) {
jbyte* card_ptr = card_for(field);
*card_ptr = dirty_card;
}
需要注意的是，讀/寫屏障隻是一種理念，觸發讀寫屏障後具體執行什麼，取決于垃圾回收器的實作。由于從堆讀取引用是非常頻繁的操作，是以這兩種屏障需要非常高效，在常見情況下就是一些彙編代碼，讀屏障的開銷通常比寫屏障大一個數量級（這也是為何大多數 GC 沒有使用或者很少使用讀屏障的原因，因為引用的讀操作要遠多于寫操作），讀屏障更多的時候是用在解決并發轉移時的引用更新問題上。
一些公司可能會在硬體層面對讀寫屏障做專門的設計，便于達到最高效的垃圾回收效率。譬如，Azul 公司為 Pauseless GC 算法專門定制了一整套系統（包括CPU、晶片組、主機闆和作業系統），用來運作具備垃圾收集功能的虛拟機，定制的 CPU 内置了「讀屏障指令」，來實作并行的、具有碎片壓縮功能的高并發(無 STW 暫停)垃圾收集算法。
注意：JVM 裡還有另外一組記憶體屏障的概念：讀屏障（Load Barrier）和寫屏障（Store Barrier），這兩組指令和上面我們談及的屏障不同，Load Barrier 和 Store Barrier主要用來保證主緩存資料的一緻性以及屏障兩側的指令不被重排序。
三 垃圾回收算法
這一部分将從最簡單的垃圾回收算法開始，介紹垃圾回收算法的演進情況，主要介紹的算法有：
- 标記-清除算法
- 标記-壓縮算法
- 标記-複制算法
- 分代算法
- 增量算法
- 并發算法
前三種是最基礎的算法，後面三種是對前面三種算法在某些方面的改進。了解到上述這些算法後，我們可以看到，現在的很多垃圾回收器，無非是是把文中提到的幾種算法進行組合或取舍。如 CMS 垃圾回收器，就是「标記-清除 + 并發算法」的組合，其全稱 Concurrent Mark-Sweep 也表明了這一點，而 G1 是「标記-複制算法 + 增量算法 + 并發算法」的組合。
基礎垃圾回收算法
基礎的垃圾回收算法有标記-清除算法、标記-壓縮算法和标記-複制算法這三種，後面兩種可以視為是對标記-清除算法中「清除」階段的優化。
标記-清除算法（Mark-Sweep）
在之前介紹三色标記法時，其實已經能看到标記-清除算法的影子了，正是因為如此，它是最簡單也是最重要的一種算法。
标記-清除算法由标記階段和清除階段構成。标記階段是把所有活動對象都做上标記的階段，有對象頭标記和位圖示記（bitmap marking）這兩種方式，後者可以與寫時複制技術（copy-on-write）相相容。清除階段是把那些沒有标記的對象，也就是非活動對象回收的階段，回收時會把對象作為分塊，連接配接到被稱為「空閑連結清單（free-lis）」的連結清單中去。
清除操作并不總是在标記階段結束後就全部完成的，一種「延遲清除（Lazy Sweep）」的算法可以縮減因清除操作導緻的應用 STW 時間。延遲清除算法不是一下周遊整個堆（清除所花費的時間與堆大小成正比），它隻在配置設定對象時執行必要的堆周遊，同時其算法複雜度隻與活動對象集的大小成正比。
下圖是标記-清除算法執行前後，堆空間的變化情況：
從上圖可以看到，标記-清除算法執行完成後，會讓堆出現碎片化，這會帶來兩個問題：
- 大量的記憶體碎片會導緻大對象配置設定時可能失敗，進而提前觸發了另一次垃圾回收動作；
- 具有引用關系的對象可能會被配置設定在堆中較遠的位置，這會增加程式通路所需的時間，即「通路的局部性（Locality）」較差。
上述兩個問題，将分别由下面介紹的标記-壓縮算法和标記-複制算法來解決。
标記-壓縮算法（Mark-Compact）
标記-壓縮算法是在标記-清除算法的基礎上，用「壓縮」取代了「清除」這個回收過程，如下圖所示，GC 将已标記并處于活動狀态的對象移動到了記憶體區域的起始端，然後清理掉了端邊界之外的記憶體空間。
壓縮階段需要重新安排可達對象的空間位置（reloacate）以及對移動後的對象引用重定向（remap），這兩個過程都需要搜尋數次堆來實作，是以會增加了 GC 暫停的時間。标記-壓縮算法的好處是顯而易見的：在進行這種壓縮操作之後，新對象的配置設定會變得非常友善——通過指針碰撞即可實作。與此同時，因為 GC 總是知道可用空間的位置，是以也不會帶來碎片的問題。
标記-壓縮算法算法還有很多變種，如 Robert A. Saunders 研究出來的名為 Two-Finger 的壓縮算法（論文：The LISP system for the Q-32 computer. In The Programming Language LISP: Its Operation and Applications[4]），可以把堆搜尋的次數縮短到2次， Stephen M. Blackburn 等研究出來的 ImmixGC 算法（論文：Cyclic reference counting with lazy mark-scan[5]）結合了标記-清除和标記-壓縮兩種算法，可以有效地解決碎片化問題。
标記-複制算法（Mark-Copy）
标記-複制算法與标記-壓縮算法非常相似，因為它們會對活動對象重新配置設定（reloacate）空間位置。兩個算法差別是：在标記-複制算法中，reloacate 目标是一個不同的記憶體區域。
标記清除算法的優點很多，譬如：
- 不會發生碎片化
- 優秀的吞吐率
- 可實作高速配置設定
- 良好的 locality
對比算法執行前後堆空間的變化，可以看到，不難發現标記-複制算法最大缺點在于所需空間翻倍了，即堆空間的使用率很低。
标記-複制在複制階段，需要遞歸複制對象和它的子對象，遞歸調用帶來的開銷是不容忽視的。C. J. Cheney 于 1970 年研究出了疊代版本的複制算法，可以抑制調用函數的額外負擔和棧的消耗，感興趣的同學可以參考論文：A Nonrecursive List Compacting Algorithm[6]。
垃圾回收算法的改進
下面介紹的三種垃圾回收算法，會針對基礎算法中諸如堆碎片化、暫停時間過長、空間使用率不高等不足進行改進。
分代算法（Generational GC）
分代算法對基礎算法的改進主要展現在該算法減小了 GC 的作用範圍。如前所述，标記過程和對象的 reloacate 過程都需要完全停止應用程式進行堆搜尋，堆空間越大，進行垃圾回收所需的時間就越長，如果 GC 的堆空間變小，應用暫停時間也會相應地降低。
分代算法基于這樣一個假說（Generational Hypothesis）：絕大多數對象都是朝生夕滅的，該假說已經在各種不同類型的程式設計範式或者程式設計語言中得到證明了。分代算法把對象分類成幾代，針對不同的代使用不同的 GC 算法：剛生成的對象稱為新生代對象，對新對象執行的 GC 稱為新生代 GC（minor GC），到達一定年齡的對象則稱為老年代對象，面向老年代對象的 GC 稱為老年代 GC（major GC），新生代對象轉為為老年代對象的情況稱為晉升（promotion）。注：代數并不是劃分的越多越好，雖然按照分代假說，如果分代數越多，最後抵達老年代的對象就越少，在老年代對象上消耗的垃圾回收的時間就越少，但分代數增多會帶來其他的開銷，綜合來看，代數劃分為 2 代或者 3 代是最好的。
在經過新生代 GC 而晉升的對象把老年代空間填滿之前，老年代 GC 都不會被執行。是以，老年代 GC 的執行頻率要比新生代 GC 低。通過使用分代垃圾回收，可以改善 GC 所花費的時間（吞吐量）。
分代算法由于其普适性，已經被大多數的垃圾回收器采用（ZGC 目前不支援，但也在規劃中了），其細節就不贅述了，這裡我們主要關注引入分代算法後，GC 過程會出現哪些問題。
（1）問題1：不同分代在堆空間之中如何劃分？
Ungar 提出的分代算法（論文：Generation Scavenging[7]）是目前使用最多的分代劃分方案，該算法即為目前 CMS 垃圾回收器的原型：堆空間由 eden、survivor0/survivor1、old 共四個區域組成。Ungar 的論文裡新生代 GC 采用的是标記-複制算法，主要是利用該算法高吞吐的特性；老年代 GC 使用的是标記-清除算法，因為老年代空間比整體堆要小，如果使用标記-複制算法，能利用的堆空間會變得更小。
分代算法的堆空間組織方式，不隻 Ungar 這一種方案。譬如，在一些基于 Ungar 的 Generation GC 的實作中，會把老年代的最後一個代通過标記-複制算法處理（Lisp Machine），還有的算法會把最後一個代通過标記-壓縮算法回收，降低複制算法出現的頻繁換頁的問題。
（2）問題2：如何标記代際之間的引用關系？
分代算法引入，需要考慮跨代/區之間對象引用的變化情況。新生代對象不隻會被根對象和新生代裡的對象引用，也可能被老年代對象引用，GC 算法需要做到「在不回收老年代對象的同時，安全地回收新生代裡面的對象」，新生代回收時，不适合也不可能去掃描整個老年代（變相搜尋堆中的所有對象），否則就失去了對堆空間進行分代的意義了。
解決上述引用問題的關鍵是引入寫屏障：如果一個老年代的引用指向了一個新生代的對象，就會觸發寫屏障。寫屏障執行過程的僞代碼如下所示，其中參數 obj 的成員變量為 field，該變量将要被更新為 new_obj 所指向的對象，記錄集 remembered_sets 被用于記錄從老年代對象到新生代對象的引用，新生代 GC 時将會把記錄集視為 GC Roots 的一部分。
write_barrier(obj, field, new_obj){
if(obj.old == TRUE && new_obj.young == TRUE && obj.remembered == FALSE){
remembered_sets[rs_index] = obj
rs_index++
obj.remembered = TRUE
}
*field = new_obj
}
在寫入屏障裡，首先會判斷：
- 發出引用的對象是不是老年代對象；
- 目标引用标對象是不是新生代對象；
- 發出引用的對象是否還沒有加入記錄集。
如果滿足以上三點，則本次建立的引用關系中，老年代的對象會被加入到記錄集。上述過程可能會帶來「浮動垃圾」，原因是所有由老年代->新生代的引用都會被加入記錄集，但老年代内對象的存活性，隻有在下一次老年代GC 時才知道。
分代算法的優點在于減小了 GC 的作用範圍後帶來的高吞吐，但與此同時我們需要注意的是，其假說「絕大多數對象都是朝生夕滅的」并不适用于所有程式，在某些應用中，對象會活得很久，如果在這樣的場景下使用分代算法，老年代的 GC 就會很頻繁，反而降低了 GC 的吞吐。此外，由于在記錄代際引用關系時引入了寫屏障，這也會帶來一定的性能開銷。
增量算法（Incremental GC）
增量算法對基礎算法的改進主要展現在該算法通過并發的方式，降低了 STW 的時間。下圖是增量算法和基礎的标記-清除算法在執行時間線上的對比，可以看到，增量算法的核心思想是：通過 GC 和應用程式交替執行的方式，來控制應用程式的最大暫停時間。
增量算法的「增量」部分，主要有「增量更新（Incremental Update）」和「增量拷貝（Incremental Copying）」兩種，前者主要是做「标記」增量，後者是在做「複制」增量。
增量更新（Incremental Update）我們已經比較熟悉了，在介紹讀/寫屏障的時候，我們提到過由于存在并發，會出現對象漏标的情況。同樣的，在增量算法中，由于 GC 線程和應用線程是交替執行的，也會出現黑色節點指向白色節點的情況，增量算法中的漏标，同樣是通過寫屏障來解決的，主要有以下兩種（基于快照的 SATB 也可以解決增量更新時出現的漏标，在此不再贅述）。
（1）寫入屏障1（Dijkstra 寫入屏障）
write_barrier(obj, field, new_obj){
if(new_obj == FALSE){
new_obj.mark == TRUE
push(new_obj, mark_stack)
}
*field = new_obj
}
在上面的代碼中，如果新引用的對象 new_obj 沒有被标記過，會将它标記後放到 mark_stack 這個标記棧中，對比三色标記法，就是将這個新對象從白色對象塗成了灰色（下圖中的 E）。
（2）寫入屏障2（Steele 寫入屏障）
write_barrier(obj, field, new_obj){
if(obj.mark == TRUE && new_obj == FALSE){
obj.mark = FALSE
push(obj, mark_stack)
}
*field = new_obj
}
在上面的代碼中，如果新引用的對象 new_obj 沒有被标記過，且将要引用它的對象 obj 已經被标記過了，那麼會把發出引用的對象去除标記，将其放入标記棧中，對比三色标記法，就是将發出引用的對象從黑色塗成了灰色（下圖中的 A）。
Steele 的寫入屏障相較于 Dijkstra 的寫入屏障來說，多了一個判斷條件，缺點是帶來的額外的負擔，優點是嚴格的條件減少了被标記的對象的個數，防止了因疏忽而造成垃圾殘留的後果，譬如 A 和 E 引用關系被标記後，如果 E 在本輪标記過程中又稱為了垃圾，Dijkstra 的寫入屏障還需要對 E 及其子節點進行标記，而 Steele 的寫入屏障就避免了這一點。
增量拷貝（Incremental Copying）大部分邏輯與标記-複制算法相似，還是會通過周遊引用關系圖，把所有引用的對象拷貝到另一半堆記憶體，不過這個過程是并發執行的。當應用程式通路到老的堆空間對象時，會觸發讀屏障，對象會從老的空間被拷貝至新的堆空間。
增量算法中大量使用了讀寫屏障（主要是寫屏障），給應用程式帶來了負擔，結果就是 GC 的吞吐相較于其他的算法來說不高。
并發算法（Concurrent GC）
廣義上的并發算法指的是在 GC 過程中存在并發階段的算法，如 G1 中存在并發标記階段，可将其整個算法視為并發算法。
狹義上的并發垃圾回收算法是以基礎的标記-複制算法為基礎，在各個階段增加了并發操作實作的。與複制算法的3個階段相對應，分為并發标記（mark）、并發轉移（relocate）和并發重定位（remap）:
（1）并發标記
從 GC Roots 出發，使用周遊算法對對象的成員變量進行标記。同樣的，并發标記也需要解決标記過程中引用關系變化導緻的漏标記問題，這一點通過寫屏障實作；
（2）并發轉移
根據并發标記後的結果生成轉移集合，把活躍對象轉移（複制）到新的記憶體上，原來的記憶體空間可以回收，轉移過程中會涉及到應用線程通路待轉移對象的情況，一般的解決思路是加上讀屏障，在完成轉移任務後，再通路對象；
（3）并發重定位
對象轉移後其記憶體位址發生了變化，所有指向對象老位址的指針都要修正到新的位址上，這一步一般通過讀屏障來實作。
并發算法是 ZGC、Shenandoah、C4 等垃圾回收器的算法基礎，在具體的實作中，不同的垃圾回收器又有自己的選擇和取舍。
至此，GC 算法的理論知識就告一段落了，有一些知識點是沒有提到的，如部分标記-清除算法（Partial Mark & Sweep）的原理、保守式 GC（Conservative GC）對資料和指針的識别、基于引用計數法的若幹 GC 算法等，感興趣的同學可以參考文中列出的論文。
相關連結
[1]
http://flyingfrogblog.blogspot.com/2011/01/boosts-sharedptr-up-to-10-slower-than.html[2]
https://lamport.azurewebsites.net/pubs/garbage.pdf[3]
https://www.sciencedirect.com/science/article/pii/016412129090084Y[4]
https://www.semanticscholar.org/paper/The-lisp-system-for-the-q-32-computer-Saunders/ad2b04c404dc40e142332a030a146b487b6e3cf2[5]
https://www.sciencedirect.com/science/article/pii/002001909290088D[6]
https://dl.acm.org/doi/10.1145/362790.362798[7]
https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p157-ungar.pdf