可達性分析可以分成兩個階段

• 根節點枚舉
• 從根節點開始遍歷對象圖

前文我們在介紹垃圾收集算法的時候，簡單提到過：標記-整理算法(Mark-Compact)中的移動存活對象操作是一種極為負重的操作，必須全程暫停用戶應用程序才能進行，像這樣的停頓被最初的虛擬機設計者形象地描述為 “Stop The World (STW)”。

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

在可達性分析中，第一階段 ”可達性分析“ 是必須 STW 的，而第二階段 ”從根節點開始遍歷對象圖“，如果不進行 STW 的話，會導致一些問題，由于第二階段時間比較長，長時間的 STW 很影響性能，所以大佬們設計了一些解決方案，從而使得這個第二階段可以不用 STW，大幅減少時間。

先這樣籠統的介紹下，大伙兒對可達性分析的整體脈絡有個認識就行，下面會詳細解釋，我會分兩篇文章來寫，本篇就先來分析第一階段 ”可達性分析“！

根節點枚舉

迄今為止，所有收集器在根節點枚舉這一步驟時都是必須暫停用戶線程的，枚舉過程必須在一個能保障 ”一致性“ 的快照中才得以進行。

通俗來說，整個枚舉期間整個系統看起來就像被凍結在某個時間點上，不會出現在分析過程中，用戶進程還在運行，導致根節點集合的對象引用關系還在不斷變化的情況，若這點都不能滿足的話，可達性分析結果的準確性顯然也就無法保證。

也就是說，根節點枚舉與我們之前提到的標記-整理算法(Mark-Compact)中的移動存活對象操作一樣會面臨相似的 “Stop The World” 的困擾。

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

現在 Java 應用越做越龐大，光是方法區的大小就常有數百上千兆，里面的類、常量等更是一大堆，要是把這些區域全都掃描檢查一遍顯然太過于費事。

那有沒有辦法減少耗時呢?

一個很自然的想法，空間換時間!

把引用類型和它對應的位置信息用哈希表記錄下來，這樣到 GC 的時候就可以直接讀取這個哈希表，而不用一個區域一個區域地進行掃描了。Hotspot 就是這么實現的，這個用于存儲引用類型的數據結構叫 OopMap。

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

實話實說，這段不理解也就算了，知道 OopMap 是這么一個東西就行了。

安全點 Safe Point

在 OopMap 的協助下，HotSpot 可以快速完成根節點枚舉了，但一個很現實的問題隨之而來：由于引用關系可能會發生變化，這就會導致 OopMap 內容變化的指令非常多，如果為每一條指令都生成對應的 OopMap，那將會需要大量的額外存儲空間，這樣垃圾收集伴隨而來的空間成本就會變得無法忍受的高昂。

所以實際上 HotSpot 也確實沒有為每條指令都生成 OopMap，只是在 “特定的位置” 生成 OopMap，換句話說，只有在某些 ”特定的位置“ 上才會把對象引用的相關信息給記錄下來，這些位置也被稱為安全點(Safepoint)。

有了安全點的設定，也就決定了用戶程序執行時并不是隨便哪個時候都能夠停頓下來開始 GC 的，而是強制要求程序必須執行到達安全點后才能夠進行 GC(因為不到達安全點話，沒有 OopMap，虛擬機就沒法快速知道對象引用的位置呀，沒法進行根節點枚舉)。

如下圖所示：

因此，安全點的設定既不能太少以至于讓垃圾收集器等待時間過長，也不能太多以至于頻繁進行垃圾收集從而導致運行時的內存負荷大幅增大。所以，安全點的選定基本上是以 “是否具有讓程序長時間執行的特征” 為標準進行選定的，最典型的就是指令序列的復用：例如方法調用、循環跳轉、異常跳轉等，所以只有具有這些功能的指令才會產生安全點。

對于安全點，另外一個需要考慮的問題是，如何在 GC 發生時讓所有用戶線程都執行到最近的安全點，然后停頓下來呢?。這里有兩種方案可供選擇：

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

搶先式中斷的最大問題是時間成本的不可控，進而導致性能不穩定和吞吐量的波動，特別是在高并發場景下這是非常致命的，所以現在幾乎沒有虛擬機實現采用搶先式中斷來暫停線程響應 GC 事件。

• 主動式中斷(Voluntary Suspension)：主動式中斷不會直接中斷線程，而是全局設置一個標志位，用戶線程會不斷的輪詢這個標志位，當發現標志位為真時，線程會在最近的一個安全點主動中斷掛起。現在的虛擬機基本都是用這種方式。

安全區域 Safe Region

安全點機制保證了程序執行時，在不太長的時間內就會遇到可進入垃圾收集過程的安全點。

對于主動式中斷來說，用戶線程需要不斷地去輪詢標志位，那對于那些處于 sleep 或者 blocked 狀態的線程(不在活躍狀態的線程)來說怎么辦?

這些不在活躍狀態的線程沒有獲得 CPU 時間，沒法去輪詢標志位，自然也就沒法找到最近的安全點主動中斷掛起了。

換句話說，對于這些不活躍的線程，我們沒法掌控它們醒過來的時間。很可能其他線程都已經通過輪詢標志位到達安全點被中斷了，然后虛擬機開始根節點枚舉了(根節點枚舉需要暫停所有用戶線程)，但是這時候那些本不活躍的用戶線程又醒過來了開始執行，破壞了對象之間的引用關系，那顯然是不行的。

對于這種情況，就必須引入安全區域(Safe Region)來解決。

安全區域的定義是這樣的：確保在某一段代碼片段之中，引用關系不會發生變化，因此，在這個區域中的任意地方開始 GC 都是安全的。

可以簡單地把安全區域看作被拉長了的安全點。

當用戶線程執行到安全區域里面的代碼時，首先會標識自己已經進入了安全區域。那樣當這段時間里虛擬機要發起 GC 時，就不必去管這些在安全區域內的線程了。當安全區域中的線程被喚醒并離開安全區域時，它需要檢查下主動式中斷策略的標志位是否為真(虛擬機是否處于 STW 狀態)，如果為真則繼續掛起等待(防止根節點枚舉過程中這些被喚醒線程的執行破壞了對象之間的引用關系)，如果為假則標識還沒開始 STW 或者 STW 剛剛結束，那么線程就可以被喚醒然后繼續執行。