可達(dá)性分析可以分成兩個(gè)階段

• 根節(jié)點(diǎn)枚舉
• 從根節(jié)點(diǎn)開(kāi)始遍歷對(duì)象圖

前文我們?cè)诮榻B垃圾收集算法的時(shí)候，簡(jiǎn)單提到過(guò)：標(biāo)記-整理算法(Mark-Compact)中的移動(dòng)存活對(duì)象操作是一種極為負(fù)重的操作，必須全程暫停用戶應(yīng)用程序才能進(jìn)行，像這樣的停頓被最初的虛擬機(jī)設(shè)計(jì)者形象地描述為 “Stop The World (STW)”。

顯然 STW 并不是一件好事，能夠避免那就需要盡可能避免。

在可達(dá)性分析中，第一階段 ”可達(dá)性分析“ 是必須 STW 的，而第二階段 ”從根節(jié)點(diǎn)開(kāi)始遍歷對(duì)象圖“，如果不進(jìn)行 STW 的話，會(huì)導(dǎo)致一些問(wèn)題，由于第二階段時(shí)間比較長(zhǎng)，長(zhǎng)時(shí)間的 STW 很影響性能，所以大佬們?cè)O(shè)計(jì)了一些解決方案，從而使得這個(gè)第二階段可以不用 STW，大幅減少時(shí)間。

先這樣籠統(tǒng)的介紹下，大伙兒對(duì)可達(dá)性分析的整體脈絡(luò)有個(gè)認(rèn)識(shí)就行，下面會(huì)詳細(xì)解釋，我會(huì)分兩篇文章來(lái)寫，本篇就先來(lái)分析第一階段 ”可達(dá)性分析“！

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

迄今為止，所有收集器在根節(jié)點(diǎn)枚舉這一步驟時(shí)都是必須暫停用戶線程的，枚舉過(guò)程必須在一個(gè)能保障 ”一致性“ 的快照中才得以進(jìn)行。

通俗來(lái)說(shuō)，整個(gè)枚舉期間整個(gè)系統(tǒng)看起來(lái)就像被凍結(jié)在某個(gè)時(shí)間點(diǎn)上，不會(huì)出現(xiàn)在分析過(guò)程中，用戶進(jìn)程還在運(yùn)行，導(dǎo)致根節(jié)點(diǎn)集合的對(duì)象引用關(guān)系還在不斷變化的情況，若這點(diǎn)都不能滿足的話，可達(dá)性分析結(jié)果的準(zhǔn)確性顯然也就無(wú)法保證。

也就是說(shuō)，根節(jié)點(diǎn)枚舉與我們之前提到的標(biāo)記-整理算法(Mark-Compact)中的移動(dòng)存活對(duì)象操作一樣會(huì)面臨相似的 “Stop The World” 的困擾。

另外，眾所周知，可作為 GC Roots 的對(duì)象引用就那么幾個(gè)，主要在全局性的引用(例如常量或類靜態(tài)屬性)與執(zhí)行上下文(例如虛擬機(jī)棧中引用的對(duì)象)中，盡管目標(biāo)很明確，但查找過(guò)程要做到快速高效其實(shí)并不是一件容易的事情。

現(xiàn)在 Java 應(yīng)用越做越龐大，光是方法區(qū)的大小就常有數(shù)百上千兆，里面的類、常量等更是一大堆，要是把這些區(qū)域全都掃描檢查一遍顯然太過(guò)于費(fèi)事。

那有沒(méi)有辦法減少耗時(shí)呢?

一個(gè)很自然的想法，空間換時(shí)間!

把引用類型和它對(duì)應(yīng)的位置信息用哈希表記錄下來(lái)，這樣到 GC 的時(shí)候就可以直接讀取這個(gè)哈希表，而不用一個(gè)區(qū)域一個(gè)區(qū)域地進(jìn)行掃描了。Hotspot 就是這么實(shí)現(xiàn)的，這個(gè)用于存儲(chǔ)引用類型的數(shù)據(jù)結(jié)構(gòu)叫 OopMap。

下圖是 HotSpot 虛擬機(jī)客戶端模式下生成的一段 String::hashCode() 方法的本地代碼，可以看到在 0x026eb7a9 處的 call 指令有 OopMap 記錄，它指明了 EBX 寄存器和棧中偏移量為 16 的內(nèi)存區(qū)域中各有一個(gè) OopMap 的引用，有效范圍為從 call 指令開(kāi)始直到0x026eb730(指令流的起始位置)+ 142(OopMap 記錄的偏移量)= 0x026eb7be，即 hlt 指令為止。

實(shí)話實(shí)說(shuō)，這段不理解也就算了，知道 OopMap 是這么一個(gè)東西就行了。

安全點(diǎn) Safe Point

在 OopMap 的協(xié)助下，HotSpot 可以快速完成根節(jié)點(diǎn)枚舉了，但一個(gè)很現(xiàn)實(shí)的問(wèn)題隨之而來(lái)：由于引用關(guān)系可能會(huì)發(fā)生變化，這就會(huì)導(dǎo)致 OopMap 內(nèi)容變化的指令非常多，如果為每一條指令都生成對(duì)應(yīng)的 OopMap，那將會(huì)需要大量的額外存儲(chǔ)空間，這樣垃圾收集伴隨而來(lái)的空間成本就會(huì)變得無(wú)法忍受的高昂。

所以實(shí)際上 HotSpot 也確實(shí)沒(méi)有為每條指令都生成 OopMap，只是在 “特定的位置” 生成 OopMap，換句話說(shuō)，只有在某些 ”特定的位置“ 上才會(huì)把對(duì)象引用的相關(guān)信息給記錄下來(lái)，這些位置也被稱為安全點(diǎn)(Safepoint)。

有了安全點(diǎn)的設(shè)定，也就決定了用戶程序執(zhí)行時(shí)并不是隨便哪個(gè)時(shí)候都能夠停頓下來(lái)開(kāi)始 GC 的，而是強(qiáng)制要求程序必須執(zhí)行到達(dá)安全點(diǎn)后才能夠進(jìn)行 GC(因?yàn)椴坏竭_(dá)安全點(diǎn)話，沒(méi)有 OopMap，虛擬機(jī)就沒(méi)法快速知道對(duì)象引用的位置呀，沒(méi)法進(jìn)行根節(jié)點(diǎn)枚舉)。

如下圖所示：

因此，安全點(diǎn)的設(shè)定既不能太少以至于讓垃圾收集器等待時(shí)間過(guò)長(zhǎng)，也不能太多以至于頻繁進(jìn)行垃圾收集從而導(dǎo)致運(yùn)行時(shí)的內(nèi)存負(fù)荷大幅增大。所以，安全點(diǎn)的選定基本上是以 “是否具有讓程序長(zhǎng)時(shí)間執(zhí)行的特征” 為標(biāo)準(zhǔn)進(jìn)行選定的，最典型的就是指令序列的復(fù)用：例如方法調(diào)用、循環(huán)跳轉(zhuǎn)、異常跳轉(zhuǎn)等，所以只有具有這些功能的指令才會(huì)產(chǎn)生安全點(diǎn)。

對(duì)于安全點(diǎn)，另外一個(gè)需要考慮的問(wèn)題是，如何在 GC 發(fā)生時(shí)讓所有用戶線程都執(zhí)行到最近的安全點(diǎn)，然后停頓下來(lái)呢?。這里有兩種方案可供選擇：

• 搶先式中斷(Preemptive Suspension)：這種思路很簡(jiǎn)單，就是在 GC 發(fā)生時(shí)，系統(tǒng)先把所有用戶線程全部中斷掉。然后如果發(fā)現(xiàn)有用戶線程中斷的位置不在安全點(diǎn)上，就恢復(fù)這條線程執(zhí)行，直到跑到安全點(diǎn)上再重新中斷。

搶先式中斷的最大問(wèn)題是時(shí)間成本的不可控，進(jìn)而導(dǎo)致性能不穩(wěn)定和吞吐量的波動(dòng)，特別是在高并發(fā)場(chǎng)景下這是非常致命的，所以現(xiàn)在幾乎沒(méi)有虛擬機(jī)實(shí)現(xiàn)采用搶先式中斷來(lái)暫停線程響應(yīng) GC 事件。

• 主動(dòng)式中斷(Voluntary Suspension)：主動(dòng)式中斷不會(huì)直接中斷線程，而是全局設(shè)置一個(gè)標(biāo)志位，用戶線程會(huì)不斷的輪詢這個(gè)標(biāo)志位，當(dāng)發(fā)現(xiàn)標(biāo)志位為真時(shí)，線程會(huì)在最近的一個(gè)安全點(diǎn)主動(dòng)中斷掛起?，F(xiàn)在的虛擬機(jī)基本都是用這種方式。

安全區(qū)域 Safe Region

安全點(diǎn)機(jī)制保證了程序執(zhí)行時(shí)，在不太長(zhǎng)的時(shí)間內(nèi)就會(huì)遇到可進(jìn)入垃圾收集過(guò)程的安全點(diǎn)。

對(duì)于主動(dòng)式中斷來(lái)說(shuō)，用戶線程需要不斷地去輪詢標(biāo)志位，那對(duì)于那些處于 sleep 或者 blocked 狀態(tài)的線程(不在活躍狀態(tài)的線程)來(lái)說(shuō)怎么辦?

這些不在活躍狀態(tài)的線程沒(méi)有獲得 CPU 時(shí)間，沒(méi)法去輪詢標(biāo)志位，自然也就沒(méi)法找到最近的安全點(diǎn)主動(dòng)中斷掛起了。

換句話說(shuō)，對(duì)于這些不活躍的線程，我們沒(méi)法掌控它們醒過(guò)來(lái)的時(shí)間。很可能其他線程都已經(jīng)通過(guò)輪詢標(biāo)志位到達(dá)安全點(diǎn)被中斷了，然后虛擬機(jī)開(kāi)始根節(jié)點(diǎn)枚舉了(根節(jié)點(diǎn)枚舉需要暫停所有用戶線程)，但是這時(shí)候那些本不活躍的用戶線程又醒過(guò)來(lái)了開(kāi)始執(zhí)行，破壞了對(duì)象之間的引用關(guān)系，那顯然是不行的。

對(duì)于這種情況，就必須引入安全區(qū)域(Safe Region)來(lái)解決。

安全區(qū)域的定義是這樣的：確保在某一段代碼片段之中，引用關(guān)系不會(huì)發(fā)生變化，因此，在這個(gè)區(qū)域中的任意地方開(kāi)始 GC 都是安全的。

可以簡(jiǎn)單地把安全區(qū)域看作被拉長(zhǎng)了的安全點(diǎn)。

當(dāng)用戶線程執(zhí)行到安全區(qū)域里面的代碼時(shí)，首先會(huì)標(biāo)識(shí)自己已經(jīng)進(jìn)入了安全區(qū)域。那樣當(dāng)這段時(shí)間里虛擬機(jī)要發(fā)起 GC 時(shí)，就不必去管這些在安全區(qū)域內(nèi)的線程了。當(dāng)安全區(qū)域中的線程被喚醒并離開(kāi)安全區(qū)域時(shí)，它需要檢查下主動(dòng)式中斷策略的標(biāo)志位是否為真(虛擬機(jī)是否處于 STW 狀態(tài))，如果為真則繼續(xù)掛起等待(防止根節(jié)點(diǎn)枚舉過(guò)程中這些被喚醒線程的執(zhí)行破壞了對(duì)象之間的引用關(guān)系)，如果為假則標(biāo)識(shí)還沒(méi)開(kāi)始 STW 或者 STW 剛剛結(jié)束，那么線程就可以被喚醒然后繼續(xù)執(zhí)行。