JVM學習（三）HotSpot虛擬機的演算法細節實作

HotSpot虛擬機的演算法細節實作

根節點列舉

以可達性分析演算法中從GC Roots集合找參考鏈這個操作來作為介紹虛擬機高效實作的例子，迄今為止，所有收集器在根節點列舉這一步驟時都是必須暫停用戶執行緒的，現在可達性分析演算法耗時最長的查找參考鏈的程序已經可以做到與用戶執行緒一起并發，但根節點列舉始侄訓是必須在一個能保障一致性的快照中才得以進行——這里“一致性“的意思是整個列舉期間執行子系統看起來就像被凍結在某個時間點上，不會出現分析程序中，根節點的集合的物件參考關系還在不斷變化的情況，若這點不能滿足的話，分析結果準確性也就不能保證，

由于目前主流Java虛擬機使用的都是準確式垃圾收集，所以當用戶執行緒停頓下來以后，其實并不需要全部檢查完所有執行背景關系和全域的參考位置，虛擬機應當是有辦法直接得到哪些地方存放著物件參考的，在HotSpot的解決方案里，是使用一組稱為OopMap的資料結構來達到這個目的，一旦完成類加載，得到類似的哈希碼來找到其位置，

普通物件指標（Ordinary Object Pointer， OOP）

安全點

在快速準確完成GC Roots列舉后，其實HotSpot也的確沒有為每條指令都生成OopMap，為解決參考關系變化的問題，在"特定的位置"記錄了資訊，這些位置被稱為安全點（Safepoint），有了安全點的設定，也就決定了用戶執行緒在執行時并非在代碼指令流的任意位置都能夠夠停頓下來開始垃圾收集，而是強制要求必須執行到達安全點后才能夠暫停，因此 ，安全點的選擇既不能太少以至于讓收集器等待時間過長，也不能太過頻繁以至于過分增大運行時的記憶體負荷，安全點位置的選取基本上是以“是否具有讓程式長時間執行的特征”為標準進行選定的，“長時間執行”的最明顯特征就是指令序列的復用，例如方法呼叫、回圈跳轉、例外跳轉等都屬于指令序列的復用，所以只有具有這些功能的指令才會產生安全點，

對于安全點，另一個需要考慮的問題就是如何在垃圾收集發生時讓所有執行緒都跑到最近的安全點，然后停頓下來，有兩種方案可供選擇：

• 搶先式中斷（Preemptive Suspension）

搶先式中斷不需要執行緒的執行代碼主動去配合，在垃圾收集發生時，系統首先把所有用戶執行緒全部中斷，如果發現有用戶執行緒中斷的地方不在安全點上，就恢復這條執行緒執行，讓其運行一會再重新中斷，直到跑到安全點上，但現在幾乎沒有虛擬機實作采用搶先式中斷來暫停執行緒回應GC事件，

• 主動式中斷（Voluntary Suspension）

主動式中斷的思想是當垃圾收集需要中斷執行緒的時候，不直接對執行緒操作，而是設定一個標志位，各個執行緒執行程序時會不停地主動去輪詢這個標志，一旦發現中斷標志為真時就自己在最近的安全點上主動中斷掛起，輪詢標志的地方和安全點是重合的，另外還要加上所有創建物件和其他需要在Java堆上分配記憶體的地方，這是為了檢查是否即將要發生垃圾收集，避免沒有足夠記憶體分配新物件，

安全區域

安全點機制保證了程式執行時，在不太長的時間內就會遇到可進入垃圾收集程序的安全點，但是，當程式不執行即沒有分配處理器時間時，典型場景即用戶執行緒處于sleep狀態或者blocked狀態，這時執行緒不能走到安全點，虛擬機也不可能持續等待執行緒重新被激活分配處理器時間，對于這種情況，就必須引入安全區域（Safe Region）來解決，

安全區域是指能夠保證在某一段代碼片段之中，參考關系不會發生變化，因此，在這個區域中任意地方開始垃圾收集都是安全的，

當用戶執行緒執行到處安全區域里面的代碼時，首先會標識自己已經進入了安全區域，這段時間若發生垃圾收集就不會管這些已宣告自己在安全區域內的執行緒了，當執行緒要離開安全區域時，它要檢查虛擬機是否已經完成了根節點列舉（或者垃圾收集程序中其它需要暫停用戶執行緒的階段），如果完成了，那執行緒就當作沒事發生過，繼續執行；否則它就必須一直等待，直到收到可以離開安全區域的信號為止，

記憶集與卡表

為解決物件跨代參考所帶來的問題，垃圾收集器在新生代中建立了名為記憶集（Remembered Set）的資料結構，用以避免把整個老年代加入GC Roots的掃描范圍，

記憶集是一種用于記錄從非收集區域指向收集區域的指標集合的抽象資料結構，

在實作記憶集的時候，可以選用更為粗獷的記憶粒度來節省記憶集的存盤和維護成本，下面列舉了一些可供選擇的記憶精度：

• 字長精度：每個記錄精確到一個機器字長，該字包含跨代指標，
• 物件精度：每個記錄精確到一個物件，該物件里有欄位含有跨代指標，
• 卡精度：每個記錄精確到一塊記憶體區域，該區域內有物件含有跨代指標，

卡精度指的是用一種稱為“卡表”（Card Table）的方式去實作記憶集，這也是目前最常用的一種記憶集的實作形式，它定義了記憶集的記錄精度，與堆記憶體的映射關系等，

卡表最簡單的形式可以只是一個位元組陣列，而HotSpot虛擬機確實也是這樣做的，下面這段代碼是HotSpot默認的卡表標記邏輯，

CARD_TABLE [this address >> 9] = 0;

位元組陣列CARD_TABLE的每一個元素都對應著其標識的記憶體區域中一塊特定大小的記憶體塊，這個記憶體塊被稱作“卡頁”（Card Page），一般來說，卡頁大小都是以2的N次冪的位元組數，通過上面代碼可以看出HotSpot中使用的卡頁是2的9次冪，

一個卡頁的記憶體中通常包含不止一個物件，只要卡頁內有一個（或更多）物件的欄位存在著跨代指標，那就將對應卡表的陣列元素值標為1，稱為這個元素變臟，沒有則標識為0，在垃圾收集發生時，只要篩選出卡表中變臟的元素，就能輕易得出哪些卡頁記憶體塊中包含跨代指標，把它們加入GC Roots中一并掃描，

寫屏障

在HotSpot虛擬機里是通過寫屏障（Write Barrier）技術維護卡表狀態的，寫屏障可以看做在虛擬機層面對“參考型別子段賦值”這個動作的AOP切面，在參考賦值物件時會產生一個環形通知，供程式執行額外的動作，也就是說賦值的前后都在寫屏障的覆寫范疇內，在賦值前的部分寫屏障叫做寫前屏障（Pre-Write Barrier），在賦值后的則叫做寫后屏障（Post-Write Barrier），

AOP為Aspect Oriented Programming的縮寫，意為面向切面編程，通過預編譯方式和運行期動態代理實作程式功能的統一的一種技術，

應用寫屏障后，虛擬機就會為所有賦值操作生成相應的指令，一旦收集器在寫屏障中增加了更新卡表操作，無論更新的是不是老年代對新生代物件的參考，每次只要對參考進行更新，就會產生額外的開銷，不過這個開銷與Minor GC時掃描整個老年代的代價相比還是低很多的，

除了寫屏障的開銷外，卡表在高并發場景下還面臨著“偽共享”（False Sharing）問題，偽共享是處理并發底層細節時一種經常需要考慮的問題，現代中央處理器的快取系統中是以快取行（Cache Line）為單位存盤的，當多執行緒修改相互獨立的變數時，如果這些變數恰好共享同一個快取行，就會彼此影響（寫回、無效化或者同步）而導致性能降低，這就是偽共享問題，

為了避免偽共享問題，一種簡單的解決方案是不采用無條件的寫屏障，而是先檢查卡表標記，只有當該卡表元素未被標記過時才將其標記為臟，即將卡表更新的邏輯變為以下代碼所示：

if (CARD_TABLE [this address >> 9] != 0)
    CARD_TABLE [this address >> 9] = 0;

在JDK7之后，HotSpot虛擬機增加了一個新的引數：-XX:+UseCondCardMark，用來決定是否開啟卡表更新的條件判斷，開啟會增加一次額外判斷的開銷，但能避免偽共享問題，兩者各有性能損耗，是否打開要根據應用實際運行情況來進行測驗權益，

并發的可達性分析

當前主流語言的垃圾收集器都是以可達性分析演算法來判定物件是否存活的，可達性分析演算法理論上要求全程序都基于一個能保障一致性的快照中才能夠進行分析，這意味著必須全程凍結用戶執行緒的運行，在根節點列舉這個步驟中，由于GC Roots相比整個Java堆中的全部物件畢竟來說還是極少數，且在各種優化技巧的加持下，它帶來的停頓已經是非常短暫且相對固定的了，

若想解決或者降低用戶執行緒的停頓，就要先搞清楚為什么必須在一個能保障一致性的快照上才能進行物件圖的遍歷？為了能解釋清楚這個問題，我們引入了三色標記（Tri-color-Marking）作為工具來輔助推導，把遍歷物件圖程序中遇到的物件，按照“是否訪問過”這個條件標記成以下三種顏色：

• 白色：表示物件尚未被垃圾收集器訪問過，顯然在可達性分析剛剛開始的階段，所有的物件都是白色的，若在可達性分析結束的階段，仍然是白色的物件，即代表不可達，
• 黑色：表示物件已被垃圾收集器訪問過，且這個物件的所有參考都已被掃描過，黑色的物件代表已經掃描過，它是安全存活的，如果有其它物件參考指向了黑色物件，無需重新掃描一遍，黑色物件不可能直接（不經過灰色物件）指向某個白色物件，
• 灰色：表示物件已經被垃圾收集器訪問過，但這個物件上至少存在一個參考還沒有被掃描過，

若用戶執行緒與收集器是并發作業的，收集器在物件圖上標記顏色，同時用戶執行緒在修改參考關系——即修改物件圖的結構，這樣可能出現兩種后果，一種是把原本消亡的物件錯誤標記為存活，這種情況可容忍且可在下次收集清理掉就好；另一種是把原本存活的物件錯誤標記為已消亡，程式肯定會因此而發生錯誤，下圖演示了這樣的致命錯誤是如何產生的

wilson于1994年在理論上證明了，當且僅當以下兩個條件同時滿足時，會產生“物件消失”的問題，即原本應該是黑色的物件被誤標為白色：

• 賦值器插入了一潭訓多條從黑色物件到白色物件的新參考
• 賦值器洗掉了全部從灰色物件到該白色物件的直接或間接參考

因此，我們要解決并發掃描時的物件消失問題，只需破壞這兩個條件中任意一個即可，由此分別產生了兩種解決方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning, SATB），

增量更新要破壞的是第一個條件，當黑色物件插入到指向新的指向白色物件的參考關系時，就將這個新插入的參考記錄下來，等并發掃描結束之后，再將這些記錄過的參考關系中的黑色物件為根，重新掃描一次，可簡單理解為黑色物件一旦新插入了指向白色物件的參考之后，它就變回灰色物件了，

原始快照要破幻的是第二個條件，當灰色物件要洗掉指向白色物件的參考關系時，就將這個要洗掉的參考記錄下來，在并發掃描結束之后，再將這些記錄過的參考關系中的灰色物件為根，重新掃描一次，可簡化理解為無論參考關系是否洗掉與否，都會按照剛開始掃描那一刻的物件圖快照來進行搜索，

以上無論是對參考關系的記錄還是洗掉，虛擬機的記錄操作都是通過寫屏障實作的，

以上介紹的HotSpot虛擬機如何發起垃圾回收、如何加速記憶體回收，以及如何保證回收正確性問題，但是虛擬機如何具體地進行垃圾回收動作仍然未涉及，因為記憶體回收如何進行是由虛擬機采用哪一款垃圾收集器所決定的，而通常虛擬機中往往有多種垃圾收集器，

參考《深入理解Java虛擬機》周志明著