JVM – 并發的可達性分析

        前言，之前看過周志明老師的深入了解JVM虛拟機第二版，但是有很多的細節并沒有在那本書中進行詳細的講解，這次拿到本書的第三版，真是開心死了，因為這本書，相對于上版糾正了很多錯誤，更重要的是，講解了一些在上版中隻是粗略帶過的知識，現在可以說是對JVM的世界又有了更深的一層了解。

        目前主流程式設計語言的垃圾收集器基本上都是依靠可達性分析算法來判定對象 是否存活的，可達性分析算法理論上要求全過程都基于一個能保障一緻性的快照中才能夠進行分析， 這意味着必須全程當機使用者線程的運作。在根節點枚舉這個步驟中，由于GC Roots相比 起整個Java堆中全部的對象畢竟還算是極少數，且在各種優化技巧（如OopMap）的加持下，它帶來 的停頓已經是非常短暫且相對固定（不随堆容量而增長）的了。可從GC Roots再繼續往下周遊對象 圖，這一步驟的停頓時間就必定會與Java堆容量直接成正比例關系了：堆越大，存儲的對象越多，對 象圖結構越複雜，要标記更多對象而産生的停頓時間自然就更長，這聽起來是理所當然的事情。

        要知道包含“标記”階段是所有追蹤式垃圾收集算法的共同特征，如果這個階段會随着堆變大而等 比例增加停頓時間，其影響就會波及幾乎所有的垃圾收集器，同理可知，如果能夠削減這部分停頓時 間的話，那收益也将會是系統性的。

        想解決或者降低使用者線程的停頓，就要先搞清楚 為什麼必須在一個能保障一緻性的快照上才能進 行對象圖的周遊？ 為了能解釋清楚這個問題，我們引入三色标記（Tri-color Marking）[1]作為工具來輔 助推導，把周遊對象圖過程中遇到的對象，按照“是否通路過”這個條件标記成以下三種顔色：

• 白色

          表示對象尚未被垃圾收集器通路過。顯然在可達性分析剛剛開始的階段，所有的對象都是 白色的，若在分析結束的階段，仍然是白色的對象，即代表不可達。

• 黑色

          表示對象已經被垃圾收集器通路過，且這個對象的所有引用都已經掃描過。黑色的對象代 表已經掃描過，它是安全存活的，如果有其他對象引用指向了黑色對象，無須重新掃描一遍。黑色對 象不可能直接（不經過灰色對象）指向某個白色對象。

• 灰色

          表示對象已經被垃圾收集器通路過，但這個對象上至少存在一個引用還沒有被掃描過。

        關于可達性分析的掃描過程，讀者不妨發揮一下想象力，把它看作對象圖上一股以灰色為波峰的 波紋從黑向白推進的過程，如果使用者線程此時是當機的，隻有收集器線程在工作，那不會有任何問 題。但如果使用者線程與收集器是并發工作呢？收集器在對象圖上标記顔色，同時使用者線程在修改引用 關系——即修改對象圖的結構，這樣可能出現兩種後果。一種是把原本消亡的對象錯誤标記為存活， 這不是好事，但其實是可以容忍的，隻不過産生了一點逃過本次收集的浮動垃圾而已，下次收集清理 掉就好。另一種是把原本存活的對象錯誤标記為已消亡，這就是非常緻命的後果了，程式肯定會是以 發生錯誤，下面表3-1示範了這樣的緻命錯誤具體是如何産生的。

并發出現“對象消失”問題的示意

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

• 指派器插入了一條或多條從黑色對象到白色對象的新引用；
• 指派器删除了全部從灰色對象到該白色對象的直接或間接引用。

        是以，我們要解決并發掃描時的對象消失問題，隻需破壞這兩個條件的任意一個即可。由此分别 産生了兩種解決方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning， SATB）。

        增量更新要破壞的是第一個條件，當黑色對象插入新的指向白色對象的引用關系時，就将這個新 插入的引用記錄下來，等并發掃描結束之後，再将這些記錄過的引用關系中的黑色對象為根，重新掃 描一次。這可以簡化了解為，黑色對象一旦新插入了指向白色對象的引用之後，它就變回灰色對象 了。

        原始快照要破壞的是第二個條件，當灰色對象要删除指向白色對象的引用關系時，就将這個要删 除的引用記錄下來，在并發掃描結束之後，再将這些記錄過的引用關系中的灰色對象為根，重新掃描 一次。這也可以簡化了解為，無論引用關系删除與否，都會按照剛剛開始掃描那一刻的對象圖快照來 進行搜尋。

        以上無論是對引用關系記錄的插入還是删除，虛拟機的記錄操作都是通過寫屏障實作的。在 HotSpot虛拟機中，增量更新和原始快照這兩種解決方案都有實際應用，譬如，CMS是基于增量更新 來做并發标記的，G1、Shenandoah則是用原始快照來實作。

        到這裡，筆者簡要介紹了HotSpot虛拟機如何發起記憶體回收、如何加速記憶體回收，以及如何保證回 收正确性等問題，但是虛拟機如何具體地進行記憶體回收動作仍然未涉及。因為記憶體回收如何進行是由 虛拟機所采用哪一款垃圾收集器所決定的，而通常虛拟機中往往有多種垃圾收集器，下面筆者将逐一 介紹HotSpot虛拟機中出現過的垃圾收集器。