如何實(shí)現(xiàn)GC

垃圾收集器的具體實(shí)現(xiàn)

?  

這部分的內(nèi)容，筆者點(diǎn)到為止，覺得看的不爽的歡迎進(jìn)群一起討論。因?yàn)椴淮_定的東西我不能寫出來誤導(dǎo)別人，要做一個(gè)講筆德的作者。

?  

我站在周老師的肩上高歌 ”HotSpot 是這么實(shí)現(xiàn)的垃圾收集器！“

根節(jié)點(diǎn)枚舉

通過上一篇的內(nèi)容我們知道了一些可以固定作為 GC Roots 的內(nèi)容，他們包括靜態(tài)變量、常量、方法運(yùn)行時(shí)上下文。我們也知道了可達(dá)性分析算法 （這里如果不清楚的請(qǐng)參考筆者前兩篇文章內(nèi)容，>" data-itemshowtype="0" tab="innerlink" data-linktype="2">這里放個(gè)傳送門>>） 。不過運(yùn)行時(shí)這么多引用，全部都掃描一遍這啥虛擬機(jī)也受不了啊，GC 2秒鐘，掃描8小時(shí)啊。

所以就有了第一階段的根結(jié)點(diǎn)枚舉，這一步就是直接掃描與 GC Roots 直接相關(guān)的那部分內(nèi)容。這一步的操作需要 “Stop The World”（Stop The World 就是用來形容在安全點(diǎn)用戶線程暫停的這種狀態(tài)的一個(gè)叫法，關(guān)于安全點(diǎn)接下來就會(huì)提到）。

可達(dá)性分析時(shí)，并不會(huì)全部的挨個(gè)掃描執(zhí)行上下文和全局引用。在 HotSpot 中，有一個(gè)叫做 OopMap 的數(shù)據(jù)結(jié)構(gòu)，專門存放著引用信息，這個(gè)普通對(duì)象指針是在類加載和即時(shí)編譯時(shí)分別將全局引用和執(zhí)行上下文「特定」的相關(guān)位置記錄下來的。（這地方與后面的內(nèi)容有關(guān)，記一下）

?  

OopMap（ Ordinary Object Pointer）  點(diǎn)到為止，這部分內(nèi)容可以根據(jù)代碼的編譯結(jié)果看到，感興趣的可以研究研究。圖片來自《深入理解 Java 虛擬機(jī)》3.4.1 代碼清單 3-3

?  

安全點(diǎn)

通過上面我們知道 GC 要做的事是通過 OopMap 找出來那些被引用的對(duì)象，而這個(gè) OopMap 里面存了兩種數(shù)據(jù)，一部分是全局引用，這好說，類加載的時(shí)候懟上，不會(huì)變了。那執(zhí)行上下文怎么辦？那一個(gè)個(gè)方法的調(diào)用，一個(gè)個(gè)棧幀，棧幀里又那么多變量 （這部分內(nèi)容在前面已經(jīng)學(xué)過了，如果不清楚可以回到前面文章復(fù)習(xí)，>" data-itemshowtype="0" tab="innerlink" data-linktype="2">再次召喚傳送門>>） 。如果把全部的字節(jié)碼指令全部都存下來那不瘋了？所以 hotspot 沒瘋，它只存了一些特定的位置把這個(gè)信息記到 OopMap 中。在程序執(zhí)行過程中會(huì)有多個(gè)這樣的特定位置，這些特定的位置就被稱為 「安全點(diǎn)」。

在安全點(diǎn)才能 GC

有了安全點(diǎn)我們就應(yīng)該知道了，GC 不是任何時(shí)候都能做的。必須要等到程序到達(dá)安全點(diǎn)之后才能做。為啥應(yīng)該不難理解吧，兩個(gè)安全點(diǎn)之間如果你執(zhí)行了 GC ，是不是會(huì)導(dǎo)致一部分執(zhí)行上下文相關(guān)的引用你不知道，因?yàn)?OopMap 里面只存了最近一個(gè)安全點(diǎn)內(nèi)的指令內(nèi)容。

安全點(diǎn)在哪

明白了這個(gè)必須等到安全點(diǎn)才能 GC 之后，又有新的問題了，（ GC 做一次真是太難了）你說這個(gè)安全點(diǎn)，你放多少個(gè)合適，間隔又要多少才合理，放遠(yuǎn)了吧，半天半天不能做一次 GC ，放近了吧倒是隨時(shí)想做就能做，但是你要知道這個(gè)安全點(diǎn)也是一條指令啊，那插入那么多額外的指令到程序中你覺得合適嗎？而且這玩應(yīng)也要存儲(chǔ)啊不是 OopMap 了解一下。于是 hotspot 的開發(fā)者就研究。最后來有了一個(gè)比較銀杏的解決辦法。

因?yàn)橐话阒噶顖?zhí)行的時(shí)間很短，所以這個(gè)解決辦法就是，在一些長時(shí)間執(zhí)行的部分給它懟一個(gè)安全點(diǎn)，防止程序長時(shí)間執(zhí)行我沒辦法 GC ，根據(jù)長時(shí)間執(zhí)行的特征，有些地方就顯而易見的被選出來祭天了，它們是 方法調(diào)用 、循環(huán)回邊處 、異常跳轉(zhuǎn)

怎么到達(dá)安全點(diǎn)

現(xiàn)在我們知道了 GC 需要通過 OopMap 找到 GC Roots 中的相關(guān)引用，又知道了要在安全點(diǎn)的時(shí)候暫停的時(shí)候開始找這些引用，但又有問題了，我知道 GC 要在線程執(zhí)行到安全點(diǎn)的時(shí)候暫停，可怎么才能讓每一個(gè)線程到達(dá)最近的安全點(diǎn)上，并且暫停呢？

兩種辦法，虛擬機(jī)強(qiáng)行等你到安全點(diǎn)，還有一種就全憑自覺。

什么叫虛擬機(jī)強(qiáng)行等你到安全點(diǎn)呢，他還有個(gè)名字叫 「Preemptive Suspension」，就是 先發(fā)制人（搶先式中斷） 。虛擬機(jī)直接中斷用戶線程，然后看你到?jīng)]到安全點(diǎn)，沒到繼續(xù)跑，然后在中斷。再看再跑再看再跑，直到全部線程都到達(dá)安全點(diǎn)，over 任務(wù)完成。

相比虛擬機(jī)懟我到安全點(diǎn)，我還不如自覺點(diǎn)  **Voluntary Suspension  ** 主動(dòng)式中斷 。虛擬機(jī)會(huì)發(fā)出一個(gè)安全點(diǎn)集合信號(hào)，所有線程輪詢這個(gè)集合信號(hào)，一旦信號(hào)為真時(shí)，當(dāng)前線程會(huì)在最近的一個(gè)安全點(diǎn)到達(dá)時(shí)掛起。

人生苦短，我選自覺?，F(xiàn)在大部分虛擬機(jī)都是選的自覺方式來到達(dá)安全點(diǎn)。畢竟先發(fā)制人太不講武德了。

?  

點(diǎn)到為止內(nèi)容，就是線程的這個(gè)輪詢操作的實(shí)現(xiàn)。因?yàn)樾枰l繁執(zhí)行，且高效。HotSpot 只使用了一條匯編指令實(shí)現(xiàn)了這個(gè)操作。

test %eax,0x160100 當(dāng)需要暫停用戶線程時(shí)， 虛擬機(jī)把0x160100的內(nèi)存頁設(shè)置為不可讀， 那線程執(zhí)行到test指令時(shí)就會(huì)產(chǎn)生一個(gè)自陷異常信號(hào)， 然后在預(yù)先注冊(cè)的異常處理器中掛起線程實(shí)現(xiàn)等待。

?  

安全區(qū)域

這部分可以算是安全點(diǎn)的擴(kuò)展，因?yàn)槌绦驁?zhí)行過程中，不能保證線程全部都在運(yùn)行狀態(tài)，或等待或阻塞等等，所以就有了安全區(qū)域的概念，這部分區(qū)域內(nèi)容標(biāo)志著在這個(gè)區(qū)域中，對(duì)象的引用關(guān)系不會(huì)發(fā)生改變。不會(huì)影響 GC 正常進(jìn)行，當(dāng)用戶線程執(zhí)行到安全區(qū)域后會(huì)標(biāo)志自己現(xiàn)在在安全區(qū)域， GC 不要管我，等到用戶線程從安全區(qū)域出來的時(shí)候要和 GC 打招呼，“GC 你完事了嗎？我要出來了” 如果這個(gè)時(shí)候沒有 GC 動(dòng)作，那你就可以出來了，如果這個(gè)時(shí)候在 根結(jié)點(diǎn)枚舉 階段，或在收集過程需要用戶線程暫停的階段，那么用戶線程就需要等待，知道 GC 結(jié)束才能從安全區(qū)域出來。

記憶集（Remembered Set）

上面的 GC 過程，在只有新生代內(nèi)存被使用，老年代沒有使用的時(shí)候還是沒問題的，但是一旦出現(xiàn)之前文章提到過的跨代引用問題，就需要考慮了，跨代引用是指老年代中存在引用新生代對(duì)象的指針。為了解決對(duì)象跨代引用所帶來的問題，垃圾收集器在新生代中建立了名為記憶集（Remembered Set）的數(shù)據(jù)結(jié)構(gòu)，一種用于記錄從非收集區(qū)域指向收集區(qū)域的指針集合的抽象數(shù)據(jù)結(jié)構(gòu)。這個(gè)在后面不光用在了這種只有新生代和老年代的收集器中，后面的區(qū)域收集器也會(huì)用到。

?  

區(qū)域收集器指的是 G1 ，ZGC 還有 Shenandoah收集器這種。

?  

卡表（Card Table）

有了記憶集的概念之后，就考慮怎么保存含有跨代引用的信息，可以將有跨代引用的對(duì)象全部保存下來，但是這樣做太占內(nèi)存，而且維護(hù)起來也不方便。于是有一種較好的記錄方案，就是按區(qū)域劃分內(nèi)存，將有跨代引用的那部分內(nèi)存區(qū)域記錄下來，這種實(shí)現(xiàn)方式稱為 “卡表”。

HotSpot 將整個(gè)堆劃分為一個(gè)個(gè)大小為 512 字節(jié)的卡頁，維護(hù)成一個(gè)卡表，每個(gè)卡表的大小默認(rèn)為 1 個(gè)字節(jié)用來存儲(chǔ)每張卡的一個(gè)標(biāo)識(shí)位0或者1。這個(gè)標(biāo)識(shí)位代表對(duì)應(yīng)的卡「是否可能存有指向新生代對(duì)象的引用」。如果可能存在，那么這張卡就是 「臟卡」。在 GC 的時(shí)候，只需要篩選臟卡對(duì)應(yīng)內(nèi)存區(qū)域中的對(duì)象就好了，不需要掃描全部的對(duì)象。

?  

注意不要搞混記憶集與卡表的概念，一個(gè)是定義的數(shù)據(jù)結(jié)構(gòu)，另一個(gè)是具體的實(shí)現(xiàn)方法。

?  

寫屏障

知道了用卡表來解決跨代或跨內(nèi)存區(qū)域的問題，當(dāng)某個(gè)卡頁可能存在跨代引用時(shí)就會(huì)變臟，那這個(gè)變臟的過程是怎么樣的呢？又是怎么實(shí)現(xiàn)的呢？

正常情況下，卡表變臟的時(shí)機(jī)是當(dāng)前區(qū)域中的對(duì)象中，引用了其他區(qū)域的對(duì)象，此時(shí)更新這張表為臟表。如果解釋執(zhí)行，一條條執(zhí)行下去可以，虛擬機(jī)可以根據(jù)變量賦值的指令來判斷，進(jìn)行相應(yīng)的操作，但是在即時(shí)編譯過程中，這個(gè)就需要一些對(duì)應(yīng)的機(jī)器指令操作了。在HotSpot虛擬機(jī)里是通過寫屏障（Write Barrier）技術(shù)來維護(hù)卡表狀態(tài)的。「與 volatile 的重排序屏障指令不同?。?！」

這個(gè)寫屏障的具體實(shí)現(xiàn)分為兩個(gè)，一個(gè)叫做寫前屏障，一個(gè)叫做寫后屏障。他們的操作類似 AOP ，他們可以在一個(gè)變量賦值操作前后做出一個(gè)通知。在 hotspot 中大多使用了寫后屏障。這樣就可以在變量賦值操作之后，將其對(duì)應(yīng)的卡表更新為臟表。

虛共享

寫屏障帶來了一個(gè)問題，這個(gè)問題是由 CPU 引起的，現(xiàn)在的 CPU 緩存中都是有一個(gè)個(gè)緩沖行保存的數(shù)據(jù)，在多核處理器的情況下，可能存在多個(gè)線程共享一個(gè)緩沖行的情況，比如一個(gè)緩沖行的大小是 32 kb，那么一張存有 64 張卡頁的卡表（64 * 512字節(jié)）就有可能在同一個(gè)緩沖行上面。為了解決多個(gè)線程同時(shí)更新同一個(gè)緩沖行浪費(fèi)的性能開銷。hotspot 在更新卡表狀態(tài)時(shí)，加入了一個(gè)當(dāng)前卡表是否為臟表的判斷，如果是臟表就不再進(jìn)行更新操作。

?  

在JDK 7之后，HotSpot虛擬機(jī)增加了一個(gè)新的參數(shù)-XX：+UseCondCardMark，用來決定是否開啟卡表更新的條件判斷。開啟會(huì)增加一次額外判斷的開銷，但能夠避免偽共享問題，兩者各有性能損耗，是否打開要根據(jù)應(yīng)用實(shí)際運(yùn)行情況來進(jìn)行測(cè)試權(quán)衡。

?  

并發(fā)的可達(dá)性分析

上面已經(jīng)對(duì)整個(gè)垃圾回收過程涉及的細(xì)節(jié)過了一遍，接下來就要看看其中的重頭戲，可達(dá)性分析算法了，也就是上面一直說的掃描掃描的內(nèi)個(gè)。

我們知道可達(dá)性分析算法是需要暫停用戶線程才能夠使用，就是需要 Stop The World ，根結(jié)點(diǎn)枚舉這一步的暫停時(shí)間雖然很短，但是還是要暫停的，同時(shí)這個(gè)暫停的時(shí)候會(huì)隨著系統(tǒng)的對(duì)象的增長而增長，成正比關(guān)系。

三色標(biāo)記

可達(dá)性分析算法的描述目前都是采用三色標(biāo)記來輔助理解的。

?  

希望這塊的內(nèi)容能夠和之前的 finalize 方法聯(lián)系起來，還記得之前文章中我們提到的自己救自己一次的那個(gè)地方嗎，待會(huì)可以倒過去看一看，這可以幫助你加深這塊的理解，當(dāng)然也只有我才會(huì)給你說這么細(xì)的提醒

?  

• 白色：死亡的顏色，即沒有引用的對(duì)象。只會(huì)發(fā)生在 GC 開始標(biāo)記工作之前（還沒開始標(biāo)記，大家都是白色），和 GC 工作之后（標(biāo)記完了，就你是白色）
• 黑色：GC 已經(jīng)開始工作到過這里，而且確認(rèn)這個(gè)節(jié)點(diǎn)存活，其存在有效的引用，即這個(gè)對(duì)象的引用也全都掃描過。被黑色節(jié)點(diǎn)引用的對(duì)象一定可以活下來?？蛇_(dá)性分析算法對(duì)已經(jīng)是黑色的節(jié)點(diǎn)，不會(huì)在進(jìn)行掃描（重要，后面理解三色標(biāo)記的問題會(huì)用到）
• 灰色：GC 已經(jīng)開始工作到過這里，但這個(gè)對(duì)象上至少還有一個(gè)引用沒有掃描。

并發(fā)標(biāo)記的問題

?  

周老師《深入理解 Java 虛擬機(jī)》（第三版）3.4.6插圖

此例子中的圖片引用了Aleksey Shipilev在DEVOXX 2017上的主題演講：《Shenandoah GC Part I：The Garbage Collector That Could》。

?  

 

上圖最后兩個(gè)情況說明了在并發(fā)階段的標(biāo)記問題。因?yàn)椴l(fā)標(biāo)記是指 GC 的工作線程與用戶線程并發(fā)執(zhí)行，所以就會(huì)出現(xiàn)一邊標(biāo)記一邊改變對(duì)象引用的情況。

并發(fā)標(biāo)記會(huì)出現(xiàn)兩類問題，一類是漏標(biāo)，一類是誤標(biāo)。漏標(biāo)是指某個(gè)應(yīng)該為白色的對(duì)象沒有被標(biāo)記成白色，這種問題一般不會(huì)有太大影響。最多浪費(fèi)一部分內(nèi)存在下一次 GC 時(shí)將其再次標(biāo)記回收。而另一類問題就是誤標(biāo)。這兩個(gè)問題在上圖的最后兩個(gè)里面可以體現(xiàn)出來。

誤標(biāo)的危害是很嚴(yán)重的，如果一個(gè)正在引用的對(duì)象，被誤標(biāo)記成了白色。那么 GC 結(jié)束之后這個(gè)對(duì)象被清除，可能直接導(dǎo)致系統(tǒng)崩潰。

這個(gè)問題的出現(xiàn)原因有被證實(shí)過，當(dāng)且僅當(dāng)滿足以下兩點(diǎn)時(shí)才會(huì)出現(xiàn)誤標(biāo)的情況

1. 賦值器插入一條以上由黑色節(jié)點(diǎn)指向白色節(jié)點(diǎn)的引用
2. 賦值器刪除了灰色節(jié)點(diǎn)直接或間接到達(dá)白色節(jié)點(diǎn)的全部引用

通過這兩個(gè)情況，我們也不難理解誤標(biāo)的產(chǎn)生，因?yàn)楹谏?jié)點(diǎn)的規(guī)則是不會(huì)在掃描，而灰色則是會(huì)再進(jìn)行掃描。所以對(duì)應(yīng)的解決辦法也比較清晰，只需要不要讓以上兩個(gè)條件同時(shí)滿足即可。HotSpot 針對(duì)以上兩點(diǎn)分別使用了「增量更新」和「原始快照」兩種解決方案。

增量更新的意思是指，如果一個(gè)引用關(guān)系是從黑色節(jié)點(diǎn)指向白色節(jié)點(diǎn)，那么就需要在并發(fā)標(biāo)記結(jié)束對(duì)這些個(gè)黑色節(jié)點(diǎn)作為根節(jié)點(diǎn)，重新進(jìn)行掃描，即黑色節(jié)點(diǎn)發(fā)生新的引用關(guān)系后，其會(huì)變成灰色節(jié)點(diǎn)。（CMS 收集器中的重新標(biāo)記使用的這種方案）

原始快照指的是，如果一個(gè)灰色節(jié)點(diǎn)刪除了指向白色節(jié)點(diǎn)的引用，那么需要將這個(gè)刪除的引用記錄下來，在并發(fā)標(biāo)記結(jié)束對(duì)這個(gè)記錄的引用關(guān)系中灰色節(jié)點(diǎn)作為根結(jié)點(diǎn)重新掃描。無論這個(gè)對(duì)象是否刪除了，都會(huì)重新再掃描一次。（G1 的最終標(biāo)記使用的這種方案）