底層原理：垃圾回收算法是如何設計的？
阿里妹導讀：理解Java虛擬機垃圾回收機制的底層原理，是成爲一個高級Java開發者的基本功。本文從底層的垃圾回收算法開始，着重去闡釋不同垃圾回收器在算法設計和實現時的一些技術細節，去探索「why」這一部分，通過對比不同的垃圾回收算法和其實現，進一步感知目前垃圾回收的發展脈絡。
文末福利：輕量應用服務器優惠，新用戶專享。
如果大家關注 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 的成員變量(引用類型的)被分配/寫入時，會觸發寫屏障。
voidexample(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 虛擬機中寫屏障的一段代碼，這段代碼記錄下了所有的引用關係的變化情況。
voidpost_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
輕量應用服務器
新用戶專享
阿里雲開發者成長計劃面向全年齡段開發者，依託免費資源、免費體驗、免費學習、免費實踐 4 大場景，全面助力開發者輕鬆掌握雲上技能。新用戶專享輕量應用服務器，內置WordPress等8種主流環境，5M峯值帶寬，40GBSSD雲盤，1000G流量包，輕鬆滿足學習、搭建應用等場景！
