下面將結(jié)合業(yè)界目前垃圾回收器的發(fā)展方向，介紹幾種較前沿的垃圾回收器，以便于加深對(duì)垃圾回收算法的理解。

注：如無特別說明，本文中垃圾回收器的內(nèi)容都是基于 HotSpot Java 虛擬機(jī)展開的。

一 、垃圾回收器簡介

工業(yè)界的垃圾回收器，一般都是上篇中幾種垃圾回收算法的組合實(shí)現(xiàn)。下圖中列舉了最常見及最新的幾種垃圾回收器，大多數(shù)的垃圾回收器均采用了分代設(shè)計(jì)(或者適用于分代場(chǎng)景)，且一般有固定的搭配使用模式，每種垃圾回收器的用法和特性在這里就不贅述了，有需要的話可以參考其他資料。圖中的垃圾回收器，還需要補(bǔ)充的一些內(nèi)容有：

• CMS 是適用于老年代的垃圾回收器，雖然在回收過程中可能也會(huì)觸發(fā)新生代垃圾回收。CMS 在 JDK 9中被聲明為廢棄的，在JDK 14中將被移除;
• Parallel Scavenge 和大部分垃圾回收器都不兼容，原因是其實(shí)現(xiàn)未基于 HotSpot VM 框架;
• Parallel Scavenge + Parallel Old 的組合有自適應(yīng)調(diào)節(jié)策略，適用于對(duì)吞吐量敏感的場(chǎng)景;
• C4 和 ZGC 可以視為是同一種垃圾回收算法的不同實(shí)現(xiàn)，ZGC 目前還沒有分代設(shè)計(jì)(規(guī)劃中);
• C4、ZGC、Shenandoah GC 的垃圾回收算法在多處是趨同的，同時(shí)各自也有比較獨(dú)特的設(shè)計(jì)理念。

??

各種垃圾回收器和垃圾回收算法間的關(guān)系如下：

• Serial：標(biāo)記-復(fù)制
• Serial Old：標(biāo)記-壓縮
• ParNew：標(biāo)記-復(fù)制
• Parallel Scavenge：標(biāo)記-復(fù)制
• Parallel Old：標(biāo)記-壓縮
• CMS(Concurrent-Mark-Sweep)：(并發(fā))標(biāo)記-清除
• G1(Garbage-First)：并發(fā)標(biāo)記 + 并行復(fù)制
• ZGC/C4：并發(fā)標(biāo)記 + 并發(fā)復(fù)制
• Shenandoah GC：并發(fā)標(biāo)記 + 并發(fā)復(fù)制

可以看到，如果堆空間進(jìn)行了分代，那么新生代通常采用復(fù)制算法，老生代通常采用壓縮-復(fù)制算法。G1、C4、ZGC、Shenandoah GC 是幾種比較新的垃圾回收器，下面會(huì)結(jié)合算法實(shí)現(xiàn)，分別介紹這四種垃圾回收器的核心原理。

二、 G1 垃圾回收器

G1是從JDK 7 Update 4及后續(xù)版本開始正式提供的，從JDK 9開始G1作為默認(rèn)的垃圾回收器。

G1 的垃圾回收是分代的，整個(gè)堆分成一系列大小相等的分區(qū)(Region)。新生代的垃圾回收(Young GC)使用的是并行復(fù)制的方式，一旦發(fā)生一次新生代回收，整個(gè)新生代都會(huì)被回收(根據(jù)對(duì)暫停時(shí)間的預(yù)測(cè)值，新生代的大小可能會(huì)動(dòng)態(tài)改變)。老年代回收不會(huì)回收全部老年代空間，只會(huì)選擇一部分收益最高的 Region，回收時(shí)一般會(huì)搭便車——把待回收的老年代 Region 和所有的新生代 Region 放在一起進(jìn)行回收，這個(gè)過程一般被稱為 Mixed GC，Young GC 和 Mixed GC 最大的不同就在于是否回收了老年代的 Region。注意：Young GC 和 Mixed GC 都是在進(jìn)行對(duì)象標(biāo)記，具體的回收過程與這兩個(gè)過程是獨(dú)立的，回收時(shí) GC 線程會(huì)根據(jù)標(biāo)記的結(jié)果選擇部分收益高的 Region 進(jìn)行復(fù)制。從某種角度來說，G1 可視為是一種「標(biāo)記-復(fù)制算法」的實(shí)現(xiàn)(注意這里不是壓縮算法，因?yàn)?G1 的復(fù)制過程完全依賴于之前標(biāo)記階段對(duì)對(duì)象生死的判定，而不是自行從 GC Roots 出發(fā)遍歷對(duì)象引用關(guān)系圖)。

G1 老年代的標(biāo)記過程大致可以分為下面四個(gè)階段：

1. 初始標(biāo)記階段(STW)
2. 并發(fā)標(biāo)記階段
3. 再標(biāo)記階段(STW)
4. 清理階段(STW)

上面的四個(gè)階段中，有三個(gè)階段都是 STW 的，每個(gè)階段的內(nèi)容就不具體敘述了。為了降低標(biāo)記階段中 STW 的時(shí)間，G1 使用了記錄集(Remembered Set, RSet)來記錄不同代際之間的引用關(guān)系。在并發(fā)標(biāo)記階段，GC 線程和應(yīng)用線程并發(fā)運(yùn)行，在這個(gè)過程中涉及到引用關(guān)系的改變，G1 使用了 SATB(Snapshot-At-The-Beginning) 記錄并發(fā)標(biāo)記時(shí)引用關(guān)系的改變，保證并發(fā)結(jié)束后引用關(guān)系的正確性。實(shí)現(xiàn) RSet 和 SATB 的關(guān)鍵就是之前提到的寫屏障。

G1 中的寫屏障分為 pre_write_barrier 和 post_write_barrier，如下面的代碼所示，應(yīng)用 field 將要被賦予新值 value，由于 field 指向的舊的引用對(duì)象會(huì)丟失引用關(guān)系，因此在賦值之前會(huì)觸發(fā) pre_write_barrier，更新 SATB 日志記錄，記錄下引用關(guān)系變化時(shí)舊的引用值;在正式賦值之后，會(huì)執(zhí)行 post_write_barrier，更新新引用對(duì)象所在的 RSet。

// 賦值操作，將 value 賦值給 field 所在的引用 
 void assign_new_value(oop* field, oop value) {   
   pre_write_barrier(field);         // 步驟1 
   *field = value;                   // 步驟2 
   post_write_barrier(field, value); // 步驟3 
 }

SATB 和 RSet 的更新都是通過寫屏障來實(shí)現(xiàn)的，但是更新操作并不都是在屏障里做的，否則會(huì)對(duì)應(yīng)用線程造成很大的干擾。G1 中的寫屏障實(shí)現(xiàn)為線程隊(duì)列+全局隊(duì)列的兩級(jí)結(jié)構(gòu)，當(dāng)寫屏障觸發(fā)后，記錄會(huì)首先加入到線程隊(duì)列(線程隊(duì)列是獨(dú)立、定長的)中，線程隊(duì)列區(qū)滿了后，就會(huì)加入到全局隊(duì)列區(qū)里，換一個(gè)新的、干凈的隊(duì)列繼續(xù)執(zhí)行下去，全局隊(duì)列里的記錄超過一定的閾值，相關(guān)線程就會(huì)去做相應(yīng)處理(更新 RSet 或是將記錄壓入標(biāo)記棧中)。

RSet

首先來看一下 RSet，這個(gè)數(shù)據(jù)結(jié)構(gòu)是為了記錄對(duì)象代際之間的引用關(guān)系而提出的，目的是加速垃圾回收的速度。引用關(guān)系的記錄方式通常有兩種方式：「我引用了誰」和「誰引用了我」，前一種記錄簡單，但是在回收時(shí)需要對(duì)記錄集做全部掃描，后一種記錄復(fù)制，占用空間大，但是在回收時(shí)只需要關(guān)注對(duì)象本身，即可通過 RSet 直接定位到引用關(guān)系。G1 的 RSet 使用的是后一種「誰引用了我」的記錄方式，其數(shù)據(jù)結(jié)構(gòu)可理解為一個(gè)哈希表。每次向引用類型字段賦值時(shí)，會(huì)觸發(fā)：「寫屏障 -> 線程隊(duì)列 -> 全局隊(duì)列 -> 并發(fā) RSet 更新」這樣一個(gè)過程。

G1 RSet 記錄的是對(duì)象之間的引用關(guān)系，那到底需要記錄哪些引用關(guān)系呢?

• Region 內(nèi)部的引用：無需記錄，因?yàn)槔厥諘r(shí) Region 內(nèi)對(duì)象肯定要掃描的;
• 新生代 Region 間的引用：無需記錄，因?yàn)樾律?Young GC 和 Mixed GC 中都會(huì)被整體回收：
• 老年代 Region 間的引用：需要記錄，因?yàn)槔夏甏厥諘r(shí)是按 Region 進(jìn)行回收的，因此需要記錄;
• 新生代 Region 到老年代 Region 的引用：無需記錄，Mixed GC 中會(huì)把整個(gè)新生代作為 GC Roots;
• 老年代 Region 到新生代 Region 的引用：需要記錄，Young GC 時(shí)直接將這種引用加入 GC Roots。

具體在回收時(shí)，RSet 的作用是這樣的：進(jìn)行 Young GC 時(shí)，選擇新生代所在的 Region 作為 GC Roots，這些 Region 中的 RSet 記錄了老年代->新生代的的跨代引用(「誰引用了我」)，從而可以避免了掃描整個(gè)老年代。進(jìn)行 Mixed GC 時(shí)，「老年代->老年代」之間的引用，可以通過待回收 Region 中的 RSet 記錄獲得，「新生代->老年代」之間的引用通過掃描全部的新生代獲得(前面提到過 Mixed GC 會(huì)搭 Young GC 的便車)，也不需要掃描全部老年代?？傊?，引入 RSet 后，GC 的堆掃描范圍大大減少了。

??

SATB

SATB 在算法篇介紹過，其實(shí)就是在一次 GC 活動(dòng)前所有對(duì)象引用關(guān)系的一個(gè)快照。之所以需要快照，是因?yàn)椴l(fā)標(biāo)記時(shí)，GC 線程一邊在標(biāo)記垃圾對(duì)象，應(yīng)用線程一邊還在生成垃圾對(duì)象，如果我們記錄下快照，以及并發(fā)標(biāo)記期間引用發(fā)生過變更的對(duì)象(包括新增對(duì)象和引用發(fā)生變更的對(duì)象)，則我們就可以實(shí)現(xiàn)一次完整的標(biāo)記。

SATB 的過程可以簡單理解為：當(dāng)并發(fā)標(biāo)記階段引用的關(guān)系發(fā)生變化時(shí)，舊引用所指向的對(duì)象就會(huì)被標(biāo)記，同時(shí)其子引用對(duì)象也會(huì)被遞歸標(biāo)記，這樣快照的完整性就得到保證了。SATB 的記錄更新是由 pre_write_barrier 寫屏障觸發(fā)的，下面是 G1 論文中介紹的 SATB 原始表述，具體實(shí)現(xiàn)時(shí)，還是由兩級(jí)的隊(duì)列結(jié)構(gòu)緩存，再由并發(fā)標(biāo)記線程批量處理進(jìn)入標(biāo)記隊(duì)列 satb_mark_queue。

void pre_write_barrier(oop* field) {   
   oop old_value = *field;   
   if (old_value != null) {   
     if ($gc_phase == GC_CONCURRENT_MARK) { 
       $current_thread->satb_mark_queue->enqueue(old_value);   
     }   
   }   
 }

因此，G1 在結(jié)束并發(fā)標(biāo)記后還有一個(gè)需要 STW 的再標(biāo)記(remark)階段就可以理解了，因?yàn)槿绻灰胍粋€(gè) STW 的過程，那么新的引用變更會(huì)不斷產(chǎn)生，永遠(yuǎn)就無法達(dá)成完成標(biāo)記的條件。再標(biāo)記階段，因?yàn)橛辛薙ATB 的設(shè)計(jì)，則只需要掃描 satb_mark_queue 隊(duì)列里的引用變更記錄就可以對(duì)此次 GC 活動(dòng)形成完整標(biāo)記了(可以對(duì)比 CMS 的 remark 階段)。

三、ZGC/C4 垃圾回收器

G1 目前的發(fā)展已經(jīng)相當(dāng)成熟了，從眾多的測(cè)評(píng)結(jié)果上看，也達(dá)到了其最初的設(shè)計(jì)目標(biāo)。但是 G1 也有下面這些不足之處：

• 堆利用率不高：原因就是引入的 RSet 占用內(nèi)存空間較大，一般會(huì)達(dá)到1%~20%;
• 暫停時(shí)間較長：通常 G1 的 STW 時(shí)間要達(dá)到幾十到幾百毫秒，還不夠低。

G1 由于使用了并發(fā)標(biāo)記，因此標(biāo)記階段對(duì)暫停時(shí)間的影響較小，暫停時(shí)間主要來自于標(biāo)記階段結(jié)束后的 Region 復(fù)制(一般占用整個(gè) GC STW 的 80%)，這個(gè)階段使用的是復(fù)制算法：GC 把一部分 Region 里的活的對(duì)象復(fù)制到空 Region 里去，然后回收原本的 Region的空間。上述過程是無法并發(fā)進(jìn)行的(并發(fā)復(fù)制一般需要通過「讀屏障」來實(shí)現(xiàn)，G1 并未使用)，因?yàn)樾枰贿呉苿?dòng)對(duì)象，同時(shí)一邊修正指向這些對(duì)象的引用(并發(fā)期間應(yīng)用線程可能會(huì)訪問到這些對(duì)象)，G1 雖然在復(fù)制對(duì)象時(shí)也做到了并行化，但大量對(duì)象的復(fù)制會(huì)涉及到很多內(nèi)存分配、變量復(fù)制的操作，非常耗時(shí)。

ZGC 就是針對(duì)上述 G1 的不足提出的，2017 年 Oracle 將 ZGC 貢獻(xiàn)給 OpenJDK 社區(qū)，2018年 JEP-333 正式引入：ZGC: A Scalable Low-Latency Garbage Collector (Experimental)。ZGC 的設(shè)計(jì)思路借鑒了一款商業(yè)垃圾回收器——Azul Systems公司的的 C4(Continuously Concurrent Compacting Collector) 垃圾回收器，后者是一款分代式的、并發(fā)的、協(xié)作式垃圾回收算法，目前只在 Azul System 公司的 Zing JVM 得到實(shí)現(xiàn)，詳細(xì)介紹請(qǐng)參考論文：http://go.azul.com/continuously-concurrent-compacting-collector。ZGC 和 C4 背后的算法均是 Azul Systems 很多年前提出的 Pauseless GC，區(qū)別在于 C4 是一種分代的實(shí)現(xiàn)，而 ZGC 現(xiàn)在還是不分代的。

ZGC 可以視為是一種「標(biāo)記-復(fù)制」算法的并發(fā)實(shí)現(xiàn)，其中標(biāo)記階段是并發(fā)的，復(fù)制階段又分為轉(zhuǎn)移(Relocate)和重定位(Remap)兩個(gè)子階段，也都是并發(fā)的，通過全程并發(fā)，可以讓暫停時(shí)間保持在10ms以內(nèi)。標(biāo)記和復(fù)制看上去是兩個(gè)串行的階段，其實(shí)也是有重疊的，譬如重定位(remap)階段實(shí)際上被合并到標(biāo)記階段中，即在標(biāo)記的時(shí)候如果發(fā)現(xiàn)對(duì)象引用到老的地址，這時(shí)會(huì)先完成重定位更新對(duì)象的引用關(guān)系，然后再標(biāo)記對(duì)象。

下面具體來看一下 ZGC 是如何高效地設(shè)計(jì)并發(fā)操作的。

??

算法設(shè)計(jì)

SATB

ZGC 在進(jìn)行并發(fā)標(biāo)記和并發(fā)復(fù)制時(shí)也會(huì)面臨引用關(guān)系改變?cè)斐傻摹嘎?biāo)」和「漏轉(zhuǎn)移」，解決的方法是引入 SATB，和 G1 中通過寫屏障實(shí)現(xiàn)的 SATB 不同，ZGC 是通過「讀屏障」+「多視圖映射」來實(shí)現(xiàn) SATB 的。讀屏障在算法篇已經(jīng)介紹過了，它發(fā)生在從堆上加載一個(gè)對(duì)象引用時(shí)，后續(xù)使用該引用不會(huì)觸發(fā)讀屏障。

讀屏障是實(shí)現(xiàn) SATB 的關(guān)鍵，除此之外，ZGC 引入讀屏障后，也實(shí)現(xiàn)了對(duì)象的并發(fā)復(fù)制，彌補(bǔ)了 G1 垃圾回收算法中最大的不足。讀屏障和寫屏障解決的問題是不一樣的，標(biāo)記-清除算法是不需要讀讀屏障的，因?yàn)闆]有內(nèi)存移動(dòng)的過程(壓縮或者復(fù)制)，但是對(duì)于復(fù)制算法，如果不用讀屏障去跟蹤讀的情況，并發(fā)執(zhí)行的應(yīng)用線程可能就會(huì)讀取到錯(cuò)誤的引用。引入讀屏障后，GC 線程可以并發(fā)執(zhí)行，應(yīng)用讀取的引用如果發(fā)生了轉(zhuǎn)移或者修改，可以在讀屏障內(nèi)完成內(nèi)存的轉(zhuǎn)移或者重定位，也就不會(huì)出現(xiàn)長時(shí)間的 STW 了。

可以通過從堆空間中加載對(duì)象的執(zhí)行代碼這里對(duì)讀屏障有更直觀的感受，這里調(diào)用的load_barrier_on_oop_field_preloaded 就是讀屏障。

template <DecoratorSet decorators, typename BarrierSetT> 
 template <typename T> 
 inline oop ZBarrierSet::AccessBarrier<decorators, BarrierSetT>::oop_load_in_heap(T* addr) { 
   verify_decorators_absent<ON_UNKNOWN_OOP_REF>(); 
   const oop o = Raw::oop_load_in_heap(addr); 
   return load_barrier_on_oop_field_preloaded(addr, o); 
 }

讀屏障觸發(fā)后，SATB 的具體執(zhí)行細(xì)節(jié)就不展開了，SATB 雖然實(shí)現(xiàn)的方式不一樣，如 G1 中是通過寫屏障實(shí)現(xiàn)的，但是其核心思想是一致的：標(biāo)記開始后，把引用關(guān)系快照里所有的活對(duì)象都看作是活的，如果出現(xiàn)了引用關(guān)系變更，則把舊的引用所指向的對(duì)象進(jìn)行標(biāo)記或記錄下來。

讀屏障的開銷是很大的，因?yàn)槎训淖x操作頻率是遠(yuǎn)高于寫操作的，ZGC 是如何對(duì)對(duì)象進(jìn)行標(biāo)記，實(shí)現(xiàn)高效的 SATB 算法的呢?答案是上面提到過的「多視圖映射」，下面簡單介紹下。

多視圖映射

和 G1 一樣，ZGC 將內(nèi)存劃分成小的分區(qū)，在ZGC中稱為頁面(page)，但是 ZGC 中的頁面大小并不是固定的，分為小頁面、中頁面和大頁面，其中小頁面大小為 2MB，中頁面大小為 32MB，而大頁面則和操作系統(tǒng)中的大頁面的大小一致。

多視圖映射指的是在 ZGC 的內(nèi)存管理中，同一物理地址的對(duì)象可以映射到多個(gè)虛擬地址上，虛擬地址有 Marked0、Marked1 和 Remapped 三種，在 ZGC 中這三個(gè)虛擬空間在同一時(shí)間點(diǎn)有且僅有一個(gè)空間有效。下表中顯示了這三個(gè)地址空間的范圍，[0~4TB)對(duì)應(yīng)的是Java的堆空間，該虛擬地址對(duì)應(yīng)用程序可見，經(jīng) ZGC 映射后，真正使用的就是 Marked0、Marked1 和 Remapped 這三個(gè)視圖對(duì)應(yīng)的地址空間，這三個(gè)視圖的切換是由垃圾回收的不同階段觸發(fā)的。

+--------------------------------+ 0x0000140000000000 (20TB) 
 |         Remapped View          | 
 +--------------------------------+ 0x0000100000000000 (16TB) 
 |     (Reserved, but unused)     | 
 +--------------------------------+ 0x00000c0000000000 (12TB) 
 |         Marked1 View           | 
 +--------------------------------+ 0x0000080000000000 (8TB) 
 |         Marked0 View           | 
 +--------------------------------+ 0x0000040000000000 (4TB)

既然多個(gè)視圖映射的是同一個(gè)物理對(duì)象，那么就需要對(duì)引用(指針)進(jìn)行若干改造，ZGC 在堆引用(指針)上增加了若干元數(shù)據(jù)信息：前42位保留為對(duì)象的實(shí)際地址(在源代碼中作為偏移量引用)，42位地址理論上提供了4TB的堆限制，其余的位用于標(biāo)記：Finalizable、Remapped、Marked1 和 Marked0 (保留一位以備將來使用)，這種引用也被稱為著色指針(Color Pointers)。

6                  4 4 4   4 4                                             0 
 3                  7 6 5   2 1                                             0 
 +-------------------+-+----+-----------------------------------------------+ 
 |00000000 00000000 0|0|1111|11 11111111 11111111 11111111 11111111 11111111| 
 +-------------------+-+----+-----------------------------------------------+ 
 |                  | |    | 
 |                  | |    * 41-0 Object Offset (42-bits, 4TB address space) 
 |                   | | 
 |                  | * 45-42 Metadata Bits (4-bits)  0001 = Marked0 
 |                  |                                 0010 = Marked1 
 |                  |                                 0100 = Remapped 
 |                  |                                 1000 = Finalizable 
 |                  | 
 |                  * 46-46 Unused (1-bit, always zero) 
 | 
 * 63-47 Fixed (17-bits, always zero)

為什么要使用多視圖映射呢?最直接的好處就是可以加快標(biāo)記和轉(zhuǎn)移的速度。比如在標(biāo)記階段，標(biāo)記某個(gè)對(duì)象時(shí)只需要轉(zhuǎn)換地址視圖即可，而地址視圖的轉(zhuǎn)化非常簡單，只需要設(shè)置地址中第42~45位中相應(yīng)的標(biāo)記位即可。而在以前的垃圾回收器實(shí)現(xiàn)中，需要修改相應(yīng)對(duì)象頭的標(biāo)記位，而這會(huì)有內(nèi)存存取訪問的開銷。在 ZGC 標(biāo)記對(duì)象中無須任何對(duì)象訪問，這就是ZGC在標(biāo)記和轉(zhuǎn)移階段速度更快的原因。

把讀屏障、 SATB 和多視圖映射放在一起，可以總結(jié) ZGC 中的并發(fā)算法的核心要點(diǎn)為：

• SATB 保證了在并發(fā)標(biāo)記和并發(fā)復(fù)制階段引用變更的正確性;
• 在并發(fā)標(biāo)記階段，通過標(biāo)記引用(指針)實(shí)現(xiàn)對(duì)對(duì)象的遍歷;
• 在并發(fā)轉(zhuǎn)移階段，讀屏障會(huì)保證并發(fā)轉(zhuǎn)移時(shí)應(yīng)用線程讀出的指針為對(duì)象的新地址;
• 在并發(fā)重定位階段，讀屏障會(huì)保證應(yīng)用線程可以獲取到轉(zhuǎn)移后的對(duì)象的新地址。

引用 R 大(RednaxelaFX)的話就是：與標(biāo)記對(duì)象的傳統(tǒng)算法相比，ZGC 在指針上做標(biāo)記，在訪問指針時(shí)加入 Load Barrier(讀屏障)，比如當(dāng)對(duì)象正被 GC 移動(dòng)，指針上的顏色就會(huì)不對(duì)，這個(gè)屏障就會(huì)先把指針更新為有效地址再返回，也就是，永遠(yuǎn)只有單個(gè)對(duì)象讀取時(shí)有概率被減速，而不存在為了保持應(yīng)用與 GC 一致而粗暴整體的 Stop The World。

算法實(shí)現(xiàn)

下面通過一個(gè)簡單的例子看了解 ZGC 的并發(fā)執(zhí)行過程。

??

第一次執(zhí)行并發(fā)標(biāo)記前，整個(gè)內(nèi)存空間的地址視圖被設(shè)置為 Remapped，并發(fā)標(biāo)記結(jié)束后，對(duì)象的地址視圖要么是 Marked0，要么是 Remapped。

• 如果地址視圖是 Marked0，說明對(duì)象是在標(biāo)記階段被標(biāo)記或者是新創(chuàng)建的;如上圖所示 A、B 對(duì)象均可以通過 GC Roots 訪問到，屬于活躍的對(duì)象，對(duì)象 D 在并發(fā)期間被創(chuàng)建，也屬于活躍對(duì)象，均被映射到 Marked0 地址視圖;
• 如果地址視圖是 Remapped，說明對(duì)象在標(biāo)記階段既不能通過根集合訪問到(直接或間接訪問)，也沒有應(yīng)用線程訪問它，所以是不活躍的，即對(duì)象所使用的內(nèi)存可以被回收。上圖中的對(duì)象 C 不能從 GC Roots 訪問，屬于不活躍對(duì)象，地址視圖還是 Remapped，表示為垃圾對(duì)象。

在并發(fā)標(biāo)記期間，如果應(yīng)用線程訪問對(duì)象且對(duì)象的地址視圖是 Remapped，說明對(duì)象是前一階段分配的，只要把該對(duì)象的視圖從 Remapped 調(diào)整為 Marked0 就能防止對(duì)象漏標(biāo)。

標(biāo)記階段結(jié)束后，所有活躍對(duì)象的地址會(huì)被存儲(chǔ)在一個(gè)「對(duì)象活躍信息表」的集合中，然后進(jìn)入并發(fā)轉(zhuǎn)移(Relocated)階段。轉(zhuǎn)移階段轉(zhuǎn)移線程會(huì)從「對(duì)象活躍信息表」中把活躍對(duì)象轉(zhuǎn)移到新的內(nèi)存中，并回收對(duì)象轉(zhuǎn)移前的內(nèi)存空間(注意：如果頁面不需要轉(zhuǎn)移，那么頁面里面的對(duì)象也就不需要轉(zhuǎn)移)。并發(fā)轉(zhuǎn)移結(jié)束后，對(duì)象的地址視圖要么是 Remapped，要么是 Marked0。

• 如果地址視圖是 Marked0，說明該對(duì)象在垃圾回收的標(biāo)記階段已經(jīng)被標(biāo)記，但是在轉(zhuǎn)移階段未被轉(zhuǎn)移(如下圖中的 B 和 D);
• 如果地址視圖是 Remapped，說明對(duì)象在并發(fā)轉(zhuǎn)移階段被轉(zhuǎn)移或者被訪問過(如下圖中的 G 和 F，C 因?yàn)椴换钴S可能就直接被回收了)。

??

在并發(fā)轉(zhuǎn)移階段，如果應(yīng)用線程訪問的對(duì)象在對(duì)象活躍信息表中，且對(duì)象的地址視圖為 Marked0，說明對(duì)象是標(biāo)記階段標(biāo)記的活躍對(duì)象，所以需要轉(zhuǎn)移對(duì)象，對(duì)象轉(zhuǎn)移以后，對(duì)象的地址視圖從 Marked0 調(diào)整為 Remapped。

??

并發(fā)轉(zhuǎn)移結(jié)束后，會(huì)再次進(jìn)入下一次的標(biāo)記階段。新的標(biāo)記階段為了區(qū)分「本次標(biāo)記的活躍對(duì)象」和「上次標(biāo)記的活躍對(duì)象」，使用了 Marked1 來標(biāo)識(shí)本次并發(fā)標(biāo)記的結(jié)果，即：用 Marked1 表示本次垃圾回收中識(shí)別的活躍對(duì)象(上圖中的 H 和 F)，用 Marked0 表示前一次垃圾回收的標(biāo)記階段被標(biāo)記過的活躍對(duì)象，且該對(duì)象在轉(zhuǎn)移階段未被轉(zhuǎn)移，但是在本次垃圾回收中被識(shí)別為不活躍對(duì)象(上圖中的 B 和 D)。注意：在并發(fā)轉(zhuǎn)移完活躍對(duì)象之后，引用還指向?qū)ο筠D(zhuǎn)移之前的地址，ZGC 通過「對(duì)象轉(zhuǎn)移地址信息表」存儲(chǔ)頁面對(duì)象轉(zhuǎn)移前和轉(zhuǎn)移后的地址，在新一輪垃圾回收啟動(dòng)后，在標(biāo)記時(shí)會(huì)執(zhí)行重定位的操作。

ZGC 雖然是全程并發(fā)設(shè)計(jì)的，但也還是有若干個(gè) STW 的階段的，包括并發(fā)標(biāo)記中的初始化標(biāo)記和結(jié)束標(biāo)記階段，并發(fā)轉(zhuǎn)移中的初始轉(zhuǎn)移階段等。事實(shí)上，完全沒有 STW 的垃圾回收器是不存在的，即便是 Azul 的 PGC(原汁原味基于 Pauseless GC 算法實(shí)現(xiàn))，也是有非常短暫的 STW 階段，譬如 GC Roots 的掃描。

四、Shenandoah 垃圾回收器

Shenandoah GC 最早是由 Red Hat 公司發(fā)起的，后來被貢獻(xiàn)給了 OpenJDK，2014 年通過 JEP-189：A Low-Pause-Time Garbage Collector (Experimental)正式成為 OpenJDK 的開源項(xiàng)目，Shenandoah GC 出現(xiàn)的時(shí)間比 ZGC 要早很多，因此發(fā)展的成熟度和穩(wěn)定性相較于 ZGC 來說更好一些，實(shí)現(xiàn)了包括括C1屏障、C2屏障、解釋器、對(duì) JNI 臨界區(qū)域的支持等特性。

和 ZGC 一樣，Shenandoah GC 也聚焦在解決 G1 中產(chǎn)生最長暫停時(shí)間的「并行復(fù)制」問題，通過與 ZGC 不一樣的方式，實(shí)現(xiàn)了「并發(fā)復(fù)制」，在 Shenandoah GC 中也未區(qū)別年輕代與老年代。ZGC實(shí)現(xiàn)并發(fā)復(fù)制的關(guān)鍵是：讀屏障 + 基于著色指針(Color Pointers)的多視圖映射，而 Shenandoah GC 實(shí)現(xiàn)并發(fā)復(fù)制的關(guān)鍵是：讀寫屏障 + 轉(zhuǎn)發(fā)指針(brook Pointers)，轉(zhuǎn)發(fā)指針(brook Pointers)的原理將在下面詳細(xì)介紹，其過程可以參考論文：Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware。

Shenandoah GC 的 回收周期和 ZGC 非常類似，大致也可以分為并發(fā)標(biāo)記和并發(fā)復(fù)制兩個(gè)階段，在并發(fā)標(biāo)記階段，也是通過 讀屏障+ SATB 來實(shí)現(xiàn)的，并發(fā)復(fù)制階段也分為并發(fā)轉(zhuǎn)移和并發(fā)重定位兩個(gè)子階段。

算法設(shè)計(jì)

并發(fā)標(biāo)記階段的 SATB 在這里就不詳細(xì)介紹了，這里主要看一下 Shenandoah GC 是如何實(shí)現(xiàn)并發(fā)復(fù)制的。

Shenandoah GC 將堆分成大量同樣大小的分區(qū)(Region) ，分區(qū)大小從 256KB 到 32MB不等。在進(jìn)行垃圾回收時(shí)，也只是會(huì)回收部分堆區(qū)域。上面提到，Shenandoah GC 實(shí)現(xiàn)高效讀屏障的關(guān)鍵是增加了 轉(zhuǎn)發(fā)指針(brook Pointers)這個(gè)結(jié)構(gòu)，這是對(duì)象頭上增加的一個(gè)額外的數(shù)據(jù)，在讀寫屏障觸發(fā)時(shí)時(shí)可以通過 brook Pointer 直接訪問對(duì)象。轉(zhuǎn)發(fā)指針要么指向?qū)ο蟊旧?，要么指向?qū)ο蟾北舅诘目臻g，如下圖所示：

??

Shenandoah GC 使用寫屏障+轉(zhuǎn)發(fā)指針完成了并發(fā)復(fù)制，其過程可以用下面的偽代碼表示：

stub evacuate(obj) { 
     if(in-colleciton-set(obj) && fwd-ptrs-to-self(obj)) { 
         copy = copy(obj); 
         CAS(fwd-ptr-addr(obj), obj, copy); 
     } 
 }

上面并發(fā)轉(zhuǎn)移的詳細(xì)過程如下：首先判斷待轉(zhuǎn)移對(duì)象是否在待回收集合中(這個(gè)集合根據(jù)標(biāo)記階段的結(jié)果生成)，同時(shí)轉(zhuǎn)移指針是否指向了自己，如果沒有在待收回集合，則不用轉(zhuǎn)移，如果對(duì)象的轉(zhuǎn)移指針已經(jīng)指向了其他地址，說明已經(jīng)轉(zhuǎn)移過了，也不用轉(zhuǎn)移;然后進(jìn)行對(duì)象復(fù)制;對(duì)象復(fù)制結(jié)束后，會(huì)通過 CAS 的方式更新轉(zhuǎn)移指針的值，使其指向新的復(fù)制對(duì)象所在的堆空間地址，如果 CAS 失敗，會(huì)多次重試。

Shenandoah GC 使用讀屏障+轉(zhuǎn)發(fā)指針保證轉(zhuǎn)移過程中或轉(zhuǎn)移結(jié)束后，應(yīng)用線程可以讀取到真實(shí)的引用地址，保證了數(shù)據(jù)的一致性，因?yàn)槿绻贿@樣做，可能會(huì)導(dǎo)致一些線程使用舊對(duì)象，而另一些線程使用新對(duì)象。

需要注意的是，在 ZGC 中并發(fā)重定位和并發(fā)標(biāo)記階段是重合的，而在 Shenandoah GC 在某些情況下，可能會(huì)把并發(fā)標(biāo)記、并發(fā)轉(zhuǎn)移和并發(fā)重定位合并到同一個(gè)并發(fā)階段內(nèi)完成，這種回收方式在 Shenandoah GC 中被稱為遍歷回收，細(xì)節(jié)請(qǐng)參考相關(guān)資料。如下圖所示，第1個(gè)回收周期會(huì)進(jìn)行并發(fā)標(biāo)記，第2回收周期會(huì)進(jìn)行并發(fā)標(biāo)記和并發(fā)轉(zhuǎn)移，第3個(gè)以后的回收周期會(huì)同時(shí)執(zhí)行并發(fā)標(biāo)記、并發(fā)轉(zhuǎn)移和并發(fā)重定位。

??

算法實(shí)現(xiàn)

我們來看一下并發(fā)復(fù)制的具體過程。

步驟1：將對(duì)象從 From 復(fù)制到 to 空間，同時(shí)將新對(duì)象的轉(zhuǎn)移指針指向新對(duì)象自己。

??

步驟2：將舊對(duì)象的轉(zhuǎn)移指針通過 CAS 的方式指向新對(duì)象。

??

步驟3：將堆中其他指向舊對(duì)象的引用，更新為新對(duì)象的地址，如果在這個(gè)過程中有應(yīng)用線程訪問到了舊對(duì)象，則會(huì)通過讀屏障的方式將新對(duì)象的地址返回給新的應(yīng)用。

??

步驟4：所有的引用被更新，舊對(duì)象所在的分區(qū)可以被回收。

??

再次回顧一下 Shenandoah GC 里使用的各種屏障：讀對(duì)象時(shí)，會(huì)首先通過讀屏障來解析對(duì)象的真實(shí)地址，當(dāng)需要更新對(duì)象(或?qū)ο蟮淖侄?，則會(huì)觸發(fā)寫屏障，將對(duì)象從 From 空間復(fù)制到 to 空間。讀寫屏障在底層的應(yīng)用，可以用下面的一個(gè)例子去理解。

void updateObject(Foo foo) { 
   // 讀操作 
   Bar b1 = foo.bar; 
   
   // 讀操作 
   Baz baz = b1.baz; 
   // 寫操作          
   b1.x = makeSomeValue(baz);   
 }

Shenandoah GC 中讀寫屏障出現(xiàn)的位置：

void updateObject(Foo foo) { 
   // 讀屏障 
   Bar b1 = readBarrier(foo).bar;              
    
   // 讀屏障 
   Baz baz = readBarrier(b1).baz;              
   X value = makeSomeValue(baz); 
   // 寫屏障 
   writeBarrier(b1).x = readBarrier(value);   
 }

一言以蔽之，Shenandoah GC 的并發(fā)復(fù)制是基于讀屏障+寫屏障共同實(shí)現(xiàn)的( ZGC 只使用了讀屏障)。Shenandoah GC 中所有的數(shù)據(jù)寫操作均會(huì)觸發(fā)寫屏障，包括對(duì)象寫、獲取鎖、hash code 的計(jì)算等，因此在具體實(shí)現(xiàn)時(shí) Shenandoah GC 對(duì)寫屏障也有若干的優(yōu)化(譬如從循環(huán)邏輯中移除寫屏障)。Shenandoah GC 還使用了一種稱之為「比較屏障」的機(jī)制來解決對(duì)象引用間的比較操作，特別是同一個(gè)對(duì)象分別處于 From 和 to 空間時(shí)的比較。此外，Shenandoah GC 里屏障也不需要特殊的硬件支持和操作系統(tǒng)支持。

Shenandoah GC 更適合用在大堆上，如果CPU資源有限，內(nèi)存也不大，比如小于20GB，那么就沒有必要使用Shenandoah GC。Shenandoah GC 在降低了暫停時(shí)間的同時(shí)，也犧牲了一部分的吞吐，如果對(duì)吞吐有較高的要求，則還是建議使用傳統(tǒng)的基于 STW 的 GC 實(shí)現(xiàn)，譬如 Parallel 系列垃圾回收器。

五、總結(jié)與回顧

在這一篇文章中，我們看到了幾種比較前沿的垃圾回收器：G1/C4/ZGC/Shenandoah GC，在它們的諸多實(shí)現(xiàn)細(xì)節(jié)中，我們也可以看到 Java 垃圾回收器的一大技術(shù)趨勢(shì)：在大內(nèi)存的前提下，通過并發(fā)的方式降低 GC 算法在標(biāo)記和轉(zhuǎn)移對(duì)象時(shí)對(duì)應(yīng)用程序的影響。CMS 做到了并發(fā)標(biāo)記，G1降低了并發(fā)標(biāo)記的成本，同時(shí)還通過并行復(fù)制的方式對(duì)部分堆內(nèi)存進(jìn)行了整理，ZGC、C4、Shenandoah GC 進(jìn)一步降低了并發(fā)標(biāo)記時(shí)的 STW 的時(shí)間，同時(shí)通過并發(fā)復(fù)制的方式將對(duì)象轉(zhuǎn)移時(shí)的暫停時(shí)間最小化。并發(fā)算法降低了應(yīng)用暫停的時(shí)間，但與此同時(shí)我們也需要看到：并發(fā)算法可以正常執(zhí)行的前提是「垃圾回收的速度大于對(duì)象的分配速度」，這也就意味著并發(fā)算法需要更大的堆空間，同時(shí)需要預(yù)留部分空間用來「喘息」。

在并發(fā)算法中，讀寫屏障和SATB是非常關(guān)鍵的，它們共同保證了并發(fā)操作時(shí)引用關(guān)系的正確性，相信通過對(duì)上述垃圾回收器的介紹，可以對(duì)這幾個(gè)概念理解得更加透徹。

參考資料

[1]http://dinfuehr.github.io/blog/a-first-look-into-zgc/

[2]https://rkennke.wordpress.com/2013/06/10/shenandoah-a-pauseless-gc-for-openjdk/

[3]https://shipilev.net/talks/devoxx-Nov2017-shenandoah.pd

[4]http://go.azul.com/continuously-concurrent-compacting-collector

[5]https://dl.acm.org/doi/10.1145/800055.802042

[6]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.6386&rep=rep1&type=pdf

[7]https://www.infoq.com/articles/tuning-tips-G1-GC/

[8]https://developers.redhat.com/blog/2019/06/27/shenandoah-gc-in-jdk-13-part-1-load-reference-barriers/

【本文為51CTO專欄作者“阿里巴巴官方技術(shù)”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】 

??戳這里，看該作者更多好文??