Java 與 C++ 之間有一堵由內(nèi)存動(dòng)態(tài)分配和垃圾收集技術(shù)所圍成的高墻 ---《深入理解Java虛擬機(jī)》

我們知道手動(dòng)管理內(nèi)存意味著自由、精細(xì)化地掌控，但是卻極度依賴于開發(fā)人員的水平和細(xì)心程度。

如果使用完了忘記釋放內(nèi)存空間就會(huì)發(fā)生內(nèi)存泄露，再如釋放錯(cuò)了內(nèi)存空間或者使用了懸垂指針則會(huì)發(fā)生無法預(yù)知的問題。

這時(shí)候 Java 帶著 GC 來了（GC，Garbage Collection 垃圾收集，早于 Java 提出），將內(nèi)存的管理交給 GC 來做，減輕了程序員編程的負(fù)擔(dān)，提升了開發(fā)效率。

所以并不是用 Java 就不需要內(nèi)存管理了，只是因?yàn)?GC 在替我們負(fù)重前行。

但是 GC 并不是那么萬能的，不同場景適用不同的 GC 算法，需要設(shè)置不同的參數(shù)，所以我們不能就這樣撒手不管了，只有深入地理解它才能用好它。

關(guān)于 GC 內(nèi)容相信很多人都有所了解。我最早得知有關(guān) GC 的知識(shí)是來自《深入理解Java虛擬機(jī)》，但是有關(guān) GC 的內(nèi)容單看這本書是不夠的。

當(dāng)時(shí)我以為我懂很多了，后來經(jīng)過了一番教育之后才知道啥叫無知者無畏。

而且過了一段時(shí)間很多有關(guān) GC 的內(nèi)容都說不上來了，其實(shí)也有很多同學(xué)反映有些知識(shí)學(xué)了就忘，有些內(nèi)容當(dāng)時(shí)是理解的，過一段時(shí)間啥都不記得了。

大部分情況是因?yàn)檫@塊內(nèi)容在腦海中沒有形成體系，沒有搞懂前因后果，沒有把一些知識(shí)串起來。

近期我整理了下 GC 相關(guān)的知識(shí)點(diǎn)，想由點(diǎn)及面展開有關(guān) GC 的內(nèi)容，順帶理一理自己的思路，所以輸出了這篇文章，希望對(duì)你有所幫助。

有關(guān) GC 的內(nèi)容其實(shí)有很多，但是對(duì)于我們這種一般開發(fā)而言是不需要太深入的，所以我就挑選了一些我認(rèn)為重要的整理出來，本來還有一些源碼的我也刪了，感覺沒必要，重要的是在概念上理清。

本來還打算分析有關(guān) JVM 的各垃圾回收器，但是文章太長了，所以分兩篇寫，下篇再發(fā)。

本篇整理的 GC 內(nèi)容不限于 JVM 但大體上還是偏 JVM，如果講具體的實(shí)現(xiàn)默認(rèn)指的是 ?HotSpot。

正文

首先我們知道根據(jù) 「Java虛擬機(jī)規(guī)范」，Java 虛擬機(jī)運(yùn)行時(shí)數(shù)據(jù)區(qū)分為程序計(jì)數(shù)器、虛擬機(jī)棧、本地方法棧、堆、方法區(qū)。

而程序計(jì)數(shù)器、虛擬機(jī)棧、本地方法棧這 3 個(gè)區(qū)域是線程私有的，會(huì)隨線程消亡而自動(dòng)回收，所以不需要管理。

因此垃圾收集只需要關(guān)注堆和方法區(qū)。

而方法區(qū)的回收，往往性價(jià)比較低，因?yàn)榕袛嗫梢曰厥盏臈l件比較苛刻。

比如類的卸載需要此類的所有實(shí)例都已經(jīng)被回收，包括子類。然后需要加載的類加載器也被回收，對(duì)應(yīng)的類對(duì)象沒有被引用這才允許被回收。

就類加載器這一條來說，除非像特意設(shè)計(jì)過的 OSGI 等可以替換類加載器的場景，不然基本上回收不了。

而垃圾收集回報(bào)率高的是堆中內(nèi)存的回收，因此我們重點(diǎn)關(guān)注堆的垃圾收集。

如何判斷對(duì)象已成垃圾？

既然是垃圾收集，我們得先判斷哪些對(duì)象是垃圾，然后再看看何時(shí)清理，如何清理。

常見的垃圾回收策略分為兩種：一種是直接回收，即引用計(jì)數(shù)；另一種是間接回收，即追蹤式回收（可達(dá)性分析）。

大家也都知道引用計(jì)數(shù)有個(gè)致命的缺陷-循環(huán)引用，所以 Java 用了可達(dá)性分析。

那為什么有明顯缺陷的計(jì)數(shù)引用還是有很多語言采用了呢？

比如 CPython ，由此看來引用計(jì)數(shù)還是有點(diǎn)用的，所以咱們就先來盤一下引用計(jì)數(shù)。

引用計(jì)數(shù)

引用計(jì)數(shù)其實(shí)就是為每一個(gè)內(nèi)存單元設(shè)置一個(gè)計(jì)數(shù)器，當(dāng)被引用的時(shí)候計(jì)數(shù)器加一，當(dāng)計(jì)數(shù)器減少為 0 的時(shí)候就意味著這個(gè)單元再也無法被引用了，所以可以立即釋放內(nèi)存。

如上圖所示，云朵代表引用，此時(shí)對(duì)象 A 有 1 個(gè)引用，因此計(jì)數(shù)器的值為 1。

對(duì)象 B 有兩個(gè)外部引用，所以計(jì)數(shù)器的值為 2，而對(duì)象 C ?沒有被引用，所以說明這個(gè)對(duì)象是垃圾，因此可以立即釋放內(nèi)存。

由此可以知曉引用計(jì)數(shù)需要占據(jù)額外的存儲(chǔ)空間，如果本身的內(nèi)存單元較小則計(jì)數(shù)器占用的空間就會(huì)變得明顯。

其次引用計(jì)數(shù)的內(nèi)存釋放等于把這個(gè)開銷平攤到應(yīng)用的日常運(yùn)行中，因?yàn)樵谟?jì)數(shù)為 0 的那一刻，就是釋放的內(nèi)存的時(shí)刻，這其實(shí)對(duì)于內(nèi)存敏感的場景很適用。

如果是可達(dá)性分析的回收，那些成為垃圾的對(duì)象不會(huì)立馬清除，需要等待下一次 GC 才會(huì)被清除。

引用計(jì)數(shù)相對(duì)而言概念比較簡單，不過缺陷就是上面提到的循環(huán)引用。

那像 CPython 是如何解決循環(huán)引用的問題呢？

首先我們知道像整型、字符串內(nèi)部是不會(huì)引用其他對(duì)象的，所以不存在循環(huán)引用的問題，因此使用引用計(jì)數(shù)并沒有問題。

那像 List、dictionaries、instances 這類容器對(duì)象就有可能產(chǎn)生循環(huán)依賴的問題，因此 Python 在引用計(jì)數(shù)的基礎(chǔ)之上又引入了標(biāo)記-清除來做備份處理。

但是具體的做法又和傳統(tǒng)的標(biāo)記-清除不一樣，它采取的是找不可達(dá)的對(duì)象，而不是可達(dá)的對(duì)象。

Python 使用雙向鏈表來鏈接容器對(duì)象，當(dāng)一個(gè)容器對(duì)象被創(chuàng)建時(shí)，它被插入到這個(gè)鏈表中，當(dāng)它被刪除時(shí)則移除。

然后在容器對(duì)象上還會(huì)添加一個(gè)字段 gc_refs，現(xiàn)在咱們?cè)賮砜纯词侨绾翁幚硌h(huán)引用的：

1. 對(duì)每個(gè)容器對(duì)象，將 gc_refs 設(shè)置為該對(duì)象的引用計(jì)數(shù)。
2. 對(duì)每個(gè)容器對(duì)象，查找它所引用的容器對(duì)象，并減少找到的被引用的容器對(duì)象的 gc_refs 字段。
3. 將此時(shí) gc_refs 大于 0 的容器對(duì)象移動(dòng)到不同的集合中，因?yàn)?gc_refs 大于 0 說明有對(duì)象外部引用它，因此不能釋放這些對(duì)象。
4. 然后找出 gc_refs 大于 0 的容器對(duì)象所引用的對(duì)象，它們也不能被清除。
5. 最后剩下的對(duì)象說明僅由該鏈表中的對(duì)象引用，沒有外部引用，所以是垃圾可以清除。

具體如下圖示例，A 和 B 對(duì)象循環(huán)引用， C 對(duì)象引用了 D 對(duì)象。

為了讓圖片更加清晰，我把步驟分開截圖了，上圖是 1-2 步驟，下圖是 3-4 步驟。

最終循環(huán)引用的 A 和 B 都能被清理，但是天下沒有免費(fèi)的午餐，最大的開銷之一是每個(gè)容器對(duì)象需要額外字段。

還有維護(hù)容器鏈表的開銷。根據(jù) pybench，這個(gè)開銷占了大約 4% 的減速。

至此我們知曉了引用計(jì)數(shù)的優(yōu)點(diǎn)就是實(shí)現(xiàn)簡單，并且內(nèi)存清理及時(shí)，缺點(diǎn)就是無法處理循環(huán)引用，不過可以結(jié)合標(biāo)記-清除等方案來兜底，保證垃圾回收的完整性。

所以 Python 沒有解決引用計(jì)數(shù)的循環(huán)引用問題，只是結(jié)合了非傳統(tǒng)的標(biāo)記-清除方案來兜底，算是曲線救國。

其實(shí)極端情況下引用計(jì)數(shù)也不會(huì)那么及時(shí)，你想假如現(xiàn)在有一個(gè)對(duì)象引用了另一個(gè)對(duì)象，而另一個(gè)對(duì)象又引用了另一個(gè)，依次引用下去。

那么當(dāng)?shù)谝粋€(gè)對(duì)象要被回收的時(shí)候，就會(huì)引發(fā)連鎖回收反應(yīng)，對(duì)象很多的話這個(gè)延時(shí)就凸顯出來了。

可達(dá)性分析

可達(dá)性分析其實(shí)就是利用標(biāo)記-清除(mark-sweep)，就是標(biāo)記可達(dá)對(duì)象，清除不可達(dá)對(duì)象。至于用什么方式清，清了之后要不要整理這都是后話。

標(biāo)記-清除具體的做法是定期或者內(nèi)存不足時(shí)進(jìn)行垃圾回收，從根引用(GC Roots)開始遍歷掃描，將所有掃描到的對(duì)象標(biāo)記為可達(dá)，然后將所有不可達(dá)的對(duì)象回收了。

所謂的根引用包括全局變量、棧上引用、寄存器上的等。

看到這里大家不知道是否有點(diǎn)感覺，我們會(huì)在內(nèi)存不足的時(shí)候進(jìn)行 GC，而內(nèi)存不足時(shí)也是對(duì)象最多時(shí)，對(duì)象最多因此需要掃描標(biāo)記的時(shí)間也長。

所以標(biāo)記-清除等于把垃圾積累起來，然后再一次性清除，這樣就會(huì)在垃圾回收時(shí)消耗大量資源，影響應(yīng)用的正常運(yùn)行。

所以才會(huì)有分代式垃圾回收和僅先標(biāo)記根節(jié)點(diǎn)直達(dá)的對(duì)象再并發(fā) tracing 的手段。

但這也只能減輕無法根除。

我認(rèn)為這是標(biāo)記-清除和引用計(jì)數(shù)的思想上最大的差別，一個(gè)攢著處理，一個(gè)把這種消耗平攤在應(yīng)用的日常運(yùn)行中。

而不論標(biāo)記-清楚還是引用計(jì)數(shù)，其實(shí)都只關(guān)心引用類型，像一些整型啥的就不需要管。

所以 JVM 還需要判斷棧上的數(shù)據(jù)是什么類型，這里又可以分為保守式 GC、半保守式 GC、和準(zhǔn)確式 GC。

保守式 GC

保守式 GC 指的是 JVM 不會(huì)記錄數(shù)據(jù)的類型，也就是無法區(qū)分內(nèi)存上的某個(gè)位置的數(shù)據(jù)到底是引用類型還是非引用類型。

因此只能靠一些條件來猜測(cè)是否有指針指向。比如在棧上掃描的時(shí)候根據(jù)所在地址是否在 GC 堆的上下界之內(nèi)，是否字節(jié)對(duì)齊等手段來判斷這個(gè)是不是指向 GC 堆中的指針。

之所以稱之為保守式 GC 是因?yàn)椴环喜聹y(cè)條件的肯定不是指向 GC 堆中的指針，因此那塊內(nèi)存沒有被引用，而符合的卻不一定是指針，所以是保守的猜測(cè)。

我再畫一張圖來解釋一下，看了圖之后應(yīng)該就很清晰了。

前面我們知道可以根據(jù)指針指向地址來判斷，比如是否字節(jié)對(duì)齊，是否在堆的范圍之內(nèi)，但是就有可能出現(xiàn)恰好有數(shù)值的值就是地址的值。

這就混亂了，所以就不能確定這是指針，只能保守認(rèn)為就是指針。

因此肯定不會(huì)有誤殺對(duì)象的情況。只會(huì)有對(duì)象已經(jīng)死了，但是有疑似指針的存在指向它，誤以為它還活著而放過了它的情況發(fā)生。

所以保守式 GC 會(huì)有放過一些“垃圾”，對(duì)內(nèi)存不太友好。

并且因?yàn)橐伤浦羔樀那闆r，導(dǎo)致我們無法確認(rèn)它是否是真的指針，所以也就無法移動(dòng)對(duì)象，因?yàn)橐苿?dòng)對(duì)象就需要改指針。

有一個(gè)方法就是加個(gè)中間層，也就是句柄層，引用會(huì)先指到句柄，然后再從句柄表找到實(shí)際對(duì)象。

所以直接引用不需要改變，如果要移動(dòng)對(duì)象只需要修改句柄表即可。不過這樣訪問就多了一層，效率就變低了。

半保守式GC

半保守式GC，在對(duì)象上會(huì)記錄類型信息而其他地方還是沒有記錄，因此從根掃描的話還是一樣，得靠猜測(cè)。

但是得到堆內(nèi)對(duì)象了之后，就能準(zhǔn)確知曉對(duì)象所包含的信息了，因此之后 tracing 都是準(zhǔn)確的，所以稱為半保守式 GC。

現(xiàn)在可以得知半保守式 GC 只有根直接掃描的對(duì)象無法移動(dòng)，從直接對(duì)象再追溯出去的對(duì)象可以移動(dòng)，所以半保守式 GC 可以使用移動(dòng)部分對(duì)象的算法，也可以使用標(biāo)記-清除這種不移動(dòng)對(duì)象的算法。

而保守式 GC 只能使用標(biāo)記-清除算法。

準(zhǔn)確式 GC

相信大家看下來已經(jīng)知道準(zhǔn)確意味 JVM 需要清晰的知曉對(duì)象的類型，包括在棧上的引用也能得知類型等。

能想到的可以在指針上打標(biāo)記，來表明類型，或者在外部記錄類型信息形成一張映射表。

HotSpot 用的就是映射表，這個(gè)表叫 OopMap。

在 HotSpot 中，對(duì)象的類型信息里會(huì)記錄自己的 OopMap，記錄了在該類型的對(duì)象內(nèi)什么偏移量上是什么類型的數(shù)據(jù)，而在解釋器中執(zhí)行的方法可以通過解釋器里的功能自動(dòng)生成出 OopMap 出來給 GC 用。

被 JIT 編譯過的方法，也會(huì)在特定的位置生成 OopMap，記錄了執(zhí)行到該方法的某條指令時(shí)棧上和寄存器里哪些位置是引用。

這些特定的位置主要在：

1. 循環(huán)的末尾（ 非 counted 循環(huán)）
2. 方法臨返回前 / 調(diào)用方法的call指令后
3. 可能拋異常的位置

這些位置就叫作安全點(diǎn)(safepoint)。

那為什么要選擇這些位置插入呢？因?yàn)槿绻麑?duì)每條指令都記錄一個(gè) OopMap 的話空間開銷就過大了，因此就選擇這些個(gè)關(guān)鍵位置來記錄即可。

所以在 HotSpot 中 GC 不是在任何位置都能進(jìn)入的，只能在安全點(diǎn)進(jìn)入。

至此我們知曉了可以在類加載時(shí)計(jì)算得到對(duì)象類型中的 OopMap，解釋器生成的 OopMap 和 JIT 生成的 OopMap ，所以 GC 的時(shí)候已經(jīng)有充足的條件來準(zhǔn)確判斷對(duì)象類型。

因此稱為準(zhǔn)確式 GC。

其實(shí)還有個(gè) JNI 調(diào)用，它們既不在解釋器執(zhí)行，也不會(huì)經(jīng)過 JIT 編譯生成，所以會(huì)缺少 OopMap。

在 HotSpot 是通過句柄包裝來解決準(zhǔn)確性問題的，像 JNI 的入?yún)⒑头祷刂狄枚纪ㄟ^句柄包裝起來，也就是通過句柄再訪問真正的對(duì)象。

這樣在 GC 的時(shí)候就不用掃描 JNI 的棧幀，直接掃描句柄表就知道 JNI 引用了 GC 堆中哪些對(duì)象了。

安全點(diǎn)

我們已經(jīng)提到了安全點(diǎn)，安全點(diǎn)當(dāng)然不是只給記錄 OopMap 用的，因?yàn)?GC 需要一個(gè)一致性快照，所以應(yīng)用線程需要暫停，而暫停點(diǎn)的選擇就是安全點(diǎn)。

我們來捋一遍思路。首先給個(gè) GC 名詞，在垃圾收集場景下將應(yīng)用程序稱為 mutator 。

一個(gè)能被 mutator 訪問的對(duì)象就是活著的，也就是說 mutator 的上下文包含了可以訪問存活對(duì)象的數(shù)據(jù)。

這個(gè)上下文其實(shí)指的就是棧、寄存器等上面的數(shù)據(jù)，對(duì)于 GC 而言它只關(guān)心棧上、寄存器等哪個(gè)位置是引用，因?yàn)樗恍枰P(guān)注引用。

但是上下文在 mutator 運(yùn)行過程中是一直在變化的，所以 GC 需要獲取一個(gè)一致性上下文快照來枚舉所有的根對(duì)象。

而快照的獲取需要停止 mutator 所有線程，不然就得不到一致的數(shù)據(jù)，導(dǎo)致一些活著對(duì)象丟失，這里說的一致性其實(shí)就像事務(wù)的一致性。

而 mutator 所有線程中這些有機(jī)會(huì)成為暫停位置的點(diǎn)就叫 safepoint 即安全點(diǎn)。

openjdk 官網(wǎng)對(duì)安全點(diǎn)的定義是：

A point during program execution at which all GC roots are known and all heap object contents are consistent. From a global point of view, all threads must block at a safepoint before the GC can run.

不過 safepoint 不僅僅只有 GC 有用，比如 deoptimization、Class redefinition 都有，只是 GC safepoint 比較知名。

我們?cè)賮硐胍幌驴梢栽谀男┪恢梅胖眠@個(gè)安全點(diǎn)。

對(duì)于解釋器來說其實(shí)每個(gè)字節(jié)碼邊界都可以成為一個(gè)安全點(diǎn)，對(duì)于 JIT 編譯的代碼也能在很多位置插入安全點(diǎn)，但是實(shí)現(xiàn)上只會(huì)在一些特定的位置插入安全點(diǎn)。

因?yàn)榘踩c(diǎn)是需要 check 的，而 check 需要開銷，如果安全點(diǎn)過多那么開銷就大了，等于每執(zhí)行幾步就需要檢查一下是否需要進(jìn)入安全點(diǎn)。

其次也就是我們上面提到的會(huì)記錄 OopMap ，所以有額外的空間開銷。

那 mutator 是如何得知此時(shí)需要在安全點(diǎn)暫停呢？

其實(shí)上面已經(jīng)提到了是 check，再具體一些還分解釋執(zhí)行和編譯執(zhí)行時(shí)不同的 check。

在解釋執(zhí)行的時(shí)候的 check 就是在安全點(diǎn) polling 一個(gè)標(biāo)志位，如果此時(shí)要進(jìn)入 GC 就會(huì)設(shè)置這個(gè)標(biāo)志位。

而編譯執(zhí)行是 polling page 不可讀，在需要進(jìn)入 safepoint 時(shí)就把這個(gè)內(nèi)存頁設(shè)為不可訪問，然后編譯代碼訪問就會(huì)發(fā)生異常，然后捕獲這個(gè)異常掛起即暫停。

這里可能會(huì)有同學(xué)問，那此時(shí)阻塞住的線程咋辦？它到不了安全點(diǎn)啊，總不能等著它吧？

這里就要引入安全區(qū)域的概念，在這種引用關(guān)系不會(huì)發(fā)生變化的代碼段中的區(qū)域稱為安全區(qū)域。

在這個(gè)區(qū)域內(nèi)的任意地方開始 GC 都是安全的，這些執(zhí)行到安全區(qū)域的線程也會(huì)標(biāo)識(shí)自己進(jìn)入了安全區(qū)域，

所以會(huì) GC 就不用等著了，并且這些線程如果要出安全區(qū)域的時(shí)候也會(huì)查看此時(shí)是否在 GC ，如果在就阻塞等著，如果 GC 結(jié)束了那就繼續(xù)執(zhí)行。

可能有些同學(xué)對(duì)counted 循環(huán)有點(diǎn)疑問，像for (int i...) 這種就是 counted 循環(huán)，這里不會(huì)埋安全點(diǎn)。

所以說假設(shè)你有一個(gè) counted loop 然后里面做了一些很慢的操作，所以很有可能其他線程都進(jìn)入安全點(diǎn)阻塞就等這個(gè) loop 的線程完畢，這就卡頓了。

分代收集

前面我們提到標(biāo)記-清除方式的 GC 其實(shí)就是攢著垃圾收，這樣集中式回收會(huì)給應(yīng)用的正常運(yùn)行帶來影響，所以就采取了分代收集的思想。

因?yàn)?span style="font-weight: 600;color: rgb(60, 112, 198);">研究發(fā)現(xiàn)有些對(duì)象基本上不會(huì)消亡，存在的時(shí)間很長，而有些對(duì)象出來沒多久就會(huì)被咔嚓了。這其實(shí)就是弱分代假說和強(qiáng)分代假說。

所以將堆分為新生代和老年代，這樣對(duì)不同的區(qū)域可以根據(jù)不同的回收策略來處理，提升回收效率。

比如新生代的對(duì)象有朝生夕死的特性，因此垃圾收集的回報(bào)率很高，需要追溯標(biāo)記的存活對(duì)象也很少，因此收集的也快，可以將垃圾收集安排地頻繁一些。

新生代每次垃圾收集存活的對(duì)象很少的話，如果用標(biāo)記-清除算法每次需要清除的對(duì)象很多，因此可以采用標(biāo)記-復(fù)制算法，每次將存活的對(duì)象復(fù)制到一個(gè)區(qū)域，剩下了直接全部清除即可。

但是樸素的標(biāo)記-復(fù)制算法是將堆對(duì)半分，但是這樣內(nèi)存利用率太低了，只有 50%。

所以 HotSpot 虛擬機(jī)分了一個(gè) Eden 區(qū)和兩個(gè)Survivor，默認(rèn)大小比例是8∶1：1，這樣利用率有 90%。

每次回收就將存活的對(duì)象拷貝至一個(gè) Survivor 區(qū)，然后清空其他區(qū)域即可，如果 Survivor 區(qū)放不下就放到 老年代去，這就是分配擔(dān)保機(jī)制。

而老年代的對(duì)象基本上都不是垃圾，所以追溯標(biāo)記的時(shí)間比較長，收集的回報(bào)率也比較低，所以收集頻率安排的低一些。

這個(gè)區(qū)域由于每次清除的對(duì)象很少，因此可以用標(biāo)記-清除算法，但是單單清除不移動(dòng)對(duì)象的話會(huì)有很多內(nèi)存碎片的產(chǎn)生，所以還有一種叫標(biāo)記-整理的算法，等于每次清除了之后需要將內(nèi)存規(guī)整規(guī)整，需要移動(dòng)對(duì)象，比較耗時(shí)。

所以可以利用標(biāo)記-清除和標(biāo)記-整理兩者結(jié)合起來收集老年代，比如平日都用標(biāo)記-清除，當(dāng)察覺內(nèi)存碎片實(shí)在太多了就用標(biāo)記-整理來配合使用。

可能還有很多同學(xué)對(duì)的標(biāo)記-清除，標(biāo)記-整理，標(biāo)記-復(fù)制算法不太清晰，沒事，咱們來盤一下。

標(biāo)記-清除

分為兩個(gè)階段：

標(biāo)記階段：tracing 階段，從根（棧、寄存器、全局變量等）開始遍歷對(duì)象圖，標(biāo)記所遇到的每個(gè)對(duì)象。

清除階段：掃描堆中的對(duì)象，將為標(biāo)記的對(duì)象作為垃圾回收。

基本上就是下圖所示這個(gè)過程：

清除不會(huì)移動(dòng)和整理內(nèi)存空間，一般都是通過空閑鏈表(雙向鏈表)來標(biāo)記哪一塊內(nèi)存空閑可用，因此會(huì)導(dǎo)致一個(gè)情況：空間碎片。

這會(huì)使得明明總的內(nèi)存是夠的，但是申請(qǐng)內(nèi)存就是不足。

而且在申請(qǐng)內(nèi)存的時(shí)候也有點(diǎn)麻煩，需要遍歷鏈表查找合適的內(nèi)存塊，會(huì)比較耗時(shí)。

所以會(huì)有多個(gè)空閑鏈表的實(shí)現(xiàn)，也就是根據(jù)內(nèi)存分塊大小組成不同的鏈表，比如分為大分塊鏈表和小分塊鏈表，這樣根據(jù)申請(qǐng)的內(nèi)存分塊大小遍歷不同的鏈表，加快申請(qǐng)的效率。

當(dāng)然還可以分更多個(gè)鏈表。

還有標(biāo)記，標(biāo)記的話一般我們會(huì)覺得應(yīng)該是標(biāo)記在對(duì)象身上，比如標(biāo)記位放在對(duì)象頭中，但是這對(duì)寫時(shí)復(fù)制不兼容。

等于每一次 GC 都需要修改對(duì)象，假設(shè)是 fork 出來的，其實(shí)是共享一塊內(nèi)存，那修改必然導(dǎo)致復(fù)制。

所以有一種位圖標(biāo)記法，其實(shí)就是將堆的內(nèi)存某個(gè)塊用一個(gè)位來標(biāo)記。就像我們的內(nèi)存是一頁一頁的，堆中的內(nèi)存可以分成一塊一塊，而對(duì)象就是在一塊，或者多塊內(nèi)存上。

根據(jù)對(duì)象所在的地址和堆的起始地址就可以算出對(duì)象是在第幾塊上，然后用一個(gè)位圖中的第幾位在置為 1 ，表明這塊地址上的對(duì)象被標(biāo)記了。

而且用位圖表格法不僅可以利用寫時(shí)復(fù)制，清除也更加高效，如果標(biāo)記在對(duì)象頭上，那么需要遍歷整個(gè)堆來掃描對(duì)象，現(xiàn)在有了位圖，可以快速遍歷清除對(duì)象。

但是不論是標(biāo)記對(duì)象頭還是利用位圖，標(biāo)記-清除的碎片問題還是處理不了。

因此就引出了標(biāo)記-復(fù)制和標(biāo)記-整理。

標(biāo)記-復(fù)制

首先這個(gè)算法會(huì)把堆分為兩塊，一塊是 From、一塊是 To。

對(duì)象只會(huì)在 From 上生成，發(fā)生 GC 之后會(huì)找到所有存活對(duì)象，然后將其復(fù)制到 To 區(qū)，之后整體回收 From 區(qū)。

再將 To 區(qū)和 From 區(qū)身份對(duì)調(diào)，即 To 變成 From ， From 變成 To，我再用圖來解釋一波。

可以看到內(nèi)存的分配是緊湊的，不會(huì)有內(nèi)存碎片的產(chǎn)生。

不需要空閑鏈表的存在，直接移動(dòng)指針分配內(nèi)存，效率很高。

對(duì) CPU緩存親和性高，因?yàn)閺母_始遍歷一個(gè)節(jié)點(diǎn)，是深度優(yōu)先遍歷，把關(guān)聯(lián)的對(duì)象都找到，然后內(nèi)存分配在相近的地方。

這樣根據(jù)局部性原理，一個(gè)對(duì)象被加載了那它所引用的對(duì)象也同時(shí)被加載，因此訪問緩存直接命中。、

當(dāng)然它也是有缺點(diǎn)的，因?yàn)閷?duì)象的分配只能在 From 區(qū)，而 From 區(qū)只有堆一半大小，因此內(nèi)存的利用率是 50%。

其次如果存活的對(duì)象很多，那么復(fù)制的壓力還是很大的，會(huì)比較慢。

然后由于需要移動(dòng)對(duì)象，因此不適用于上文提到的保守式 GC。

當(dāng)然我上面描述的是深度優(yōu)先就是遞歸調(diào)用，有棧溢出風(fēng)險(xiǎn)，還有一種 Cheney 的 GC 復(fù)制算法，是采用迭代的廣度優(yōu)先遍歷，具體不做分析了，有興趣自行搜索。

標(biāo)記-整理

標(biāo)記-整理其實(shí)和標(biāo)記-復(fù)制差不多，區(qū)別在于復(fù)制算法是分為兩個(gè)區(qū)來回復(fù)制，而整理不分區(qū)，直接整理。

算法思路還是很清晰的，將存活的對(duì)象往邊界整理，也沒有內(nèi)存碎片，也不需要復(fù)制算法那樣騰出一半的空間，所以內(nèi)存利用率也高。

缺點(diǎn)就是需要對(duì)堆進(jìn)行多次搜索，畢竟是在一個(gè)空間內(nèi)又標(biāo)記，又移動(dòng)的，所以整體而言花費(fèi)的時(shí)間較多，而且如果堆很大的情況，那么消耗的時(shí)間將更加突出。

至此相信你對(duì)標(biāo)記-清除、標(biāo)記-復(fù)制和標(biāo)記-整理都清晰了，讓我們?cè)倩氐絼偛盘岬降姆执占?/p>

跨代引用

我們已經(jīng)根據(jù)對(duì)象存活的特性進(jìn)行了分代，提高了垃圾收集的效率，但是像在回收新生代的時(shí)候，有可能有老年代的對(duì)象引用了新生代對(duì)象，所以老年代也需要作為根，但是如果掃描整個(gè)老年代的話效率就又降低了。

所以就搞了個(gè)叫記憶集（Remembered Set）的東西，來記錄跨代之間的引用而避免掃描整體非收集區(qū)域。

因此記憶集就是一種用于記錄從非收集區(qū)域指向收集區(qū)域的指針集合的抽象數(shù)據(jù)結(jié)構(gòu)。根據(jù)記錄的精度分為

• 字長精度，每條記錄精確到機(jī)器字長。
• 對(duì)象精度，每條記錄精確到對(duì)象。
• 卡精度，每條記錄精確到一塊內(nèi)存區(qū)域。

最常見的是用卡精度來實(shí)現(xiàn)記憶集，稱之為卡表。

我來解釋下什么叫卡。

拿對(duì)象精度來距離，假設(shè)新生代對(duì)象 A 被老年代對(duì)象 D 引用了，那么就需要記錄老年代 D 所在的地址引用了新生代對(duì)象。

那卡的意思就是將內(nèi)存空間分成很多卡片。假設(shè)新生代對(duì)象 A 被老年代 D 引用了，那么就需要記錄老年代 D 所在的那一塊內(nèi)存片有引用新生代對(duì)象。

也就是說堆被卡切割了，假設(shè)卡的大小是 2，堆是 20，那么堆一共可以劃分成 10 個(gè)卡。

因?yàn)榭ǖ姆秶?，如果此時(shí) D 旁邊在同一個(gè)卡內(nèi)的對(duì)象也有引用新生代對(duì)象的話，那么就只需要一條記錄。

一般會(huì)用字節(jié)數(shù)組來實(shí)現(xiàn)卡表，卡的范圍也是設(shè)為 2 的 N 次冪大小。來看一下圖就很清晰了。

假設(shè)地址從 0x0000 開始，那么字節(jié)數(shù)組的 0號(hào)元素代表 0x0000～0x01FF，1 號(hào)代表0x0200～0x03FF，依次類推即可。

然后到時(shí)候回收新生代的時(shí)候，只需要掃描卡表，把標(biāo)識(shí)為 1 的臟表所在內(nèi)存塊加入到 GC Roots 中掃描，這樣就不需要掃描整個(gè)老年代了。

用了卡表的話占用內(nèi)存比較少，但是相對(duì)字長、對(duì)象來說精度不準(zhǔn)，需要掃描一片。所以也是一種取舍，到底要多大的卡。

還有一種多卡表，簡單的說就是有多張卡表，這里我畫兩張卡表示意一下。

上面的卡表表示的地址范圍更大，這樣可以先掃描范圍大的表，發(fā)現(xiàn)中間一塊臟了，然后再通過下標(biāo)計(jì)算直接得到更具體的地址范圍。

這種多卡表在堆內(nèi)存比較大，且跨代引用較少的時(shí)候，掃描效率較高。

而卡表一般都是通過寫屏障來維護(hù)的，寫屏障其實(shí)就相當(dāng)于一個(gè) AOP，在對(duì)象引用字段賦值的時(shí)候加入更新卡表的代碼。

這其實(shí)很好理解，說白了就是當(dāng)引用字段賦值的時(shí)候判斷下當(dāng)前對(duì)象是老年代對(duì)象，所引用對(duì)象是新生代對(duì)象，于是就在老年代對(duì)象所對(duì)應(yīng)的卡表位置置為 1，表示臟，待會(huì)需要加入根掃描。

不過這種將老年代作為根來掃描會(huì)有浮動(dòng)垃圾的情況，因?yàn)槔夏甏膶?duì)象可能已經(jīng)成為垃圾，所以拿垃圾來作為根掃描出來的新生代對(duì)象也很有可能是垃圾。

不過這是分代收集必須做出的犧牲。

增量式 GC

所謂的增量式 GC 其實(shí)就是在應(yīng)用線程執(zhí)行中，穿插著一點(diǎn)一點(diǎn)的完成 GC，來看個(gè)圖就很清晰了

這樣看起來 GC 的時(shí)間跨度變大了，但是 mutator 暫停的時(shí)間變短了。

對(duì)于增量式 GC ，Dijkstra 等人抽象除了三色標(biāo)記算法，來表示 GC 中對(duì)象三種不同狀況。

三色標(biāo)記算法

白色：表示還未搜索到的對(duì)象?；疑罕硎菊谒阉鬟€未搜索完的對(duì)象。黑色：表示搜索完成的對(duì)象。

下面這圖從維基百科搞得，雖說顏色沒對(duì)上，但是意思是對(duì)的（black 畫成了藍(lán)色，grey畫成了黃色）。

我再用文字概述一下三色的轉(zhuǎn)換。

GC 開始前所有對(duì)象都是白色，GC 一開始所有根能夠直達(dá)的對(duì)象被壓到棧中，待搜索，此時(shí)顏色是灰色。

然后灰色對(duì)象依次從棧中取出搜索子對(duì)象，子對(duì)象也會(huì)被涂為灰色，入棧。當(dāng)其所有的子對(duì)象都涂為灰色之后該對(duì)象被涂為黑色。

當(dāng) GC 結(jié)束之后灰色對(duì)象將全部沒了，剩下黑色的為存活對(duì)象，白色的為垃圾。

一般增量式標(biāo)記-清除會(huì)分為三個(gè)階段：

1. 根查找，需要暫停應(yīng)用線程，找到根直接引用的對(duì)象。
2. 標(biāo)記階段，和應(yīng)用線程并發(fā)執(zhí)行。
3. 清除階段。

這里解釋下 GC 中兩個(gè)名詞的含義。

并發(fā)：應(yīng)用線程和 GC 線程一起執(zhí)行。并行：多個(gè) GC 線程一起執(zhí)行。

看起來好像三色標(biāo)記沒啥問題？來看看下圖。

第一個(gè)階段搜索到 A 的子對(duì)象 B了，因此 A 被染成了黑色，B 為灰色。此時(shí)需要搜索 B。

但是在 B 開始搜索時(shí)，A 的引用被 mutator 換給了 C，然后此時(shí) B 到 C 的引用也被刪了。

接著開始搜索 B ，此時(shí) B 沒有引用因此搜索結(jié)束，這時(shí)候 C 就被當(dāng)垃圾了，因此 A 已經(jīng)黑色了，所以不會(huì)再搜索到 C 了。

這就是出現(xiàn)漏標(biāo)的情況，把還在使用的對(duì)象當(dāng)成垃圾清除了，非常嚴(yán)重，這是 GC 不允許的，寧愿放過，不能殺錯(cuò)。

還有一種情況多標(biāo)，比如 A 變成黑色之后，根引用被 mutator 刪除了，那其實(shí) A 就屬于垃圾，但是已經(jīng)被標(biāo)記為黑色了，那就得等下次 GC 清除了。

這其實(shí)就是標(biāo)記過程中沒有暫停 mutator 而導(dǎo)致的，但這也是為了讓 GC 減少對(duì)應(yīng)用程序運(yùn)行的影響。

多標(biāo)其實(shí)還能接受，漏標(biāo)的話就必須處理了，我們可以總結(jié)一下為什么會(huì)發(fā)生漏標(biāo)：

1. mutator 插入黑色對(duì)象 A 到白色對(duì)象 C 的一個(gè)引用
2. mutator 刪除了灰色對(duì)象 B 到白色對(duì)象 C 的一個(gè)引用

只要打破這兩個(gè)條件任意一個(gè)就不會(huì)發(fā)生漏標(biāo)的情況。

這時(shí)候可以通過以下手段來打破兩個(gè)條件：

利用寫屏障在黑色引用白色對(duì)象時(shí)候，將白色對(duì)象置為灰色，這叫增量更新。

利用寫屏障在灰色對(duì)象刪除對(duì)白色對(duì)象的引用時(shí)，將白色對(duì)象置為灰，其實(shí)就是保存舊的引用關(guān)系。這叫STAB（snapshot-at-the-beginning）。

總結(jié)

至此有關(guān)垃圾回收的關(guān)鍵點(diǎn)和思路都差不多了，具體有關(guān) JVM 的垃圾回收器等我下篇再作分析。

現(xiàn)在我們?cè)賮?span style="font-weight: 600;color: rgb(60, 112, 198);">總結(jié)一下。

關(guān)于垃圾回收首先得找出垃圾，而找出垃圾分為兩個(gè)流派，一個(gè)是引用計(jì)數(shù)，一個(gè)是可達(dá)性分析。

引用計(jì)數(shù)垃圾回收的及時(shí)，對(duì)內(nèi)存較友好，但是循環(huán)引用無法處理。

可達(dá)性分析基本上是現(xiàn)代垃圾回收的核心選擇，但是由于需要統(tǒng)一回收比較耗時(shí)，容易影響應(yīng)用的正常運(yùn)行。

所以可達(dá)性分析的研究方向就是往如何減少對(duì)應(yīng)用程序運(yùn)行的影響即減少 STW(stop the world) 的時(shí)間。

因此根據(jù)對(duì)象分代假說研究出了分代收集，根據(jù)對(duì)象的特性劃分了新生代和老年代，采取不同的收集算法，提升回收的效率。

想方設(shè)法的拆解 GC 的步驟使得可以與應(yīng)用線程并發(fā)，并且采取并行收集，加快收集速度。

還有往評(píng)估的方向的延遲回收或者說回收部分垃圾來減少 STW 的時(shí)間。

總的而言垃圾回收還是很復(fù)雜的，因?yàn)橛泻芏嗉?xì)節(jié)，我這篇就是淺顯的紙上談兵，不要被我的標(biāo)題騙了哈哈哈哈。

最后

這篇文章寫了挺久的，主要是內(nèi)容很多如何編排有點(diǎn)難，我也選擇性的剪了很多了，但還是近 1W 字。

期間也查閱了很多資料，不過個(gè)人能力有限，如果有紕漏的地方請(qǐng)抓緊聯(lián)系我。

巨人的肩膀

http://arctrix.com/nas/python/gc/

https://openjdk.java.net/groups/hotspot/docs/HotSpotGlossary.html

《The Garbage Collection Handbook 》

https://www.iteye.com/blog/user/rednaxelafx R大的博客

https://www.jianshu.com/u/90ab66c248e6 占小狼的博客

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：

長按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠摯感謝