《深入理解Java虛擬機器器》第三章讀書筆記（二）——HotSpot垃圾回收演演算法實現(OopMap，安全點安全區域，卡表，寫屏障，三色標記演演算法)

前面《深入理解Java虛擬機器器》第三章讀書筆記（一）——垃圾回收演演算法我們學習了垃圾回收演演算法理論知識，下面我們關注下HotSpot垃圾回收演演算法的實現，分為以下幾部分

物件是垃圾的判斷依據 GC Roots 是如何高效掃描的
如何解決跨代參照物件的垃圾回收問題
如何降低垃圾回收STW的時長——並行可達性分析

1.GC Roots 是如何高效掃描的

固定作為GC Roots的節點主要分佈在全域性性的參照（常數，靜態屬性）於棧幀本地變數表等，如何快速從方法區中獲取這些節點呢？

HotSpot使用一組稱為OopMap的資料結構來實現快速的掃描哪些地方存在物件參照——一旦類載入動作完成的實還，HotSpot就會在物件內什麼偏移量上是什麼型別的資料計算出來，對於即時編譯，也會在特定的位置記錄下棧裡和暫存器裡哪些位置是參照。

根節點列舉的過程需要暫停使用者執行緒（Stop the world 簡稱STW），這樣可以掃描的過程在一個一致性快照中進行（使用者執行緒都停止了不會該變物件的參照關係）

2.使用者執行緒何時停止進行垃圾回收

2.1安全點

Oop Map 讓HotSpot可以快速進行根節點列舉，但是使用者執行緒可能正在執行改變參照關係的指令，如果為每一條指令都生成對應的Oop Map，那麼將需要大量的空間。因此需要一個「特定的位置」，在這個位置參照關係不會再改變，可以維護Oop Map 並進行GC，這個位置稱為——「安全點」，它決定了使用者程式執行時並非在程式碼指令流的任意位置都能夠停頓下來開始垃圾收集，而是強制要求必須執行到達安全點後才能夠暫停。

安全點的選定不能太多，以至於增大執行時的負荷（太多意味著Oop Map的維護過於頻繁）,也不能太少導致垃圾收集器等待時間太長。安全點位置需要能讓程式長時間執行（大部分指令的執行時間都很短），但是方法呼叫，迴圈跳轉，異常跳轉這種指令序列複用符合這個要求，具備這些功能的指令回產生安全點。
如何在垃圾回收是，讓使用者執行緒跑到最近的安全點，然後停頓下來
- 主動式中斷：當垃圾收集需要中斷執行緒的時候，不直接對執行緒操作，僅僅簡單地設定一個標誌位，各個執行緒執行過程時會不停地主動去輪詢這個標誌，一旦發現中斷標誌為真時就自己在最近的安全點上主動中斷掛起。輪詢標誌的地方和安全點是重合的，另外還要加上所有建立物件和其他需要在Java堆上分配記憶體的地方，這是為了檢查是否即將要發生垃圾收集，避免沒有足夠記憶體分配新物件。
  
  由於輪詢操作在程式碼中會頻繁出現，這要求它必須足夠高效。HotSpot使用記憶體保護陷阱的方式，把輪詢操作精簡至只有一條組合指令的程度。執行緒執行到這個組合指令的會產生一個自陷異常訊號，然後在預先註冊的例外處理器中掛起執行緒實現等待，這樣僅通過一條組合指令便完成安全點輪詢和觸發執行緒中斷了。
- 搶先式中斷
  
  搶先式中斷不需要執行緒的執行程式碼主動去配合，在垃圾收集發生時，系統首先把所有使用者執行緒全部中斷，如果發現有使用者執行緒中斷的地方不在安全點上，就恢復這條執行緒執行，讓它一會再重新中斷，直到跑到安全點上。現在幾乎沒有虛擬機器器實現採用搶先式中斷來暫停執行緒響應GC事件。

2.2安全區域

安全點保證了使用者執行緒在執行的時候，如何停止使用者執行緒，讓jvm進入垃圾回收狀態。但是如果使用者執行緒被阻塞而停止的時候呢？

如果一個執行緒處於 Sleep 或中斷狀態，它就不能響應 JVM 的中斷請求，再執行到安全點（Safe Point) 上。因此 JVM 引入了 安全區域（Safe Region）。Safe Region 是指在一段程式碼片段中，參照關係不會發生變化。在這個區域內的任意地方開始 GC 都是安全的。執行緒在進入 Safe Region 的時候先標記自己已進入了 Safe Region，等到被喚醒時準備離開 Safe Region 時，先檢查能否離開，如果 GC 完成了，那麼執行緒可以離開，否則它必須等待直到收到安全離開的訊號為止。

3.如何解決跨代參照物件的回收

1.記憶集與卡表

如果老年代參照了新生代的物件，回收新生代的時候，難道需要掃描全部老年代找出存在跨代參照的物件麼？

垃圾收集器在新生代中建立了名為記憶集的物件，可以避免將整個老年代加入到GC Roots的掃描範圍。記憶集是用於記錄非收集區域指向收集區域的指標集合的抽象資料結構。

為了減少記憶集的空間成本，收集器只需要記憶集判斷出某一塊非收集區域是否存在向收集區域的指標就可以了，並不記錄所有跨代指標細節，因此記憶集的具體實現——「卡表」只精確到一塊記憶體區域（該區域記憶體在物件的跨代指標）。

2.寫屏障維護卡表

卡表用於記錄跨代指標，但是卡表中的元素何時進行維護，也就說出現跨代指標的時候如何記錄在卡表中，跨代指標消除的時候如何清除卡表的內容？

hotSpot虛擬機器器使用寫屏障進行維護，這個寫屏障可以看作是賦值操作的AOP環形通知。有了寫屏障之後，虛擬機器器會為賦值操作生成相應指令，進行維護卡表。

為了避免並行場景下，多執行緒操作卡表導致偽共用，虛擬機器器會先檢查卡表是否未被標記，未被標記才會進行標記操作。

4.並行可達性分析——三色標記演演算法

可達性分析演演算法理論上必須在一個一致性快照中進行，一致性意味著需要凍結使用者執行緒。在列舉GC Roots這個環節jvm使用OopMap讓STW停頓時間減少，但是獲得GC Roots之後繼續遍歷物件圖的過程必然會隨著堆越大而愈加耗時，導致停頓的時間更長。

那麼如何減少這個停頓時間呢？——讓可達性分析演演算法中的標記步驟可以和使用者執行緒儘量並行，三色標記演演算法應運而生。

三色標記演演算法

三色是：黑色，白色，灰色。

把遍歷物件圖過程中遇到的物件，按照是否存取過這個條件標記成以下三種顏色：

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

上圖描述了三色標記的流程。但是如果標記的時候使用者執行緒在修改參照關係，導致物件圖關係改變，可能導致出現錯誤。

錯標：是垃圾的物件，沒有被標記為垃圾

這種情況本應灰色的垃圾E,以及和它關聯的物件 F，G都不會會被回收（E被視為和GC Roots關聯導致錯誤的任務，G,F也不垃圾）,這種稱為浮動垃圾（不和GC Roots關聯如同漂浮無依無靠的垃圾）浮動垃圾的問題影響不是很大，可能就是暫時的浪費一點記憶體，它肯定抗不過下一輪GC
錯殺

這種情況十分嚴重，但是存在補救方法：
- 增量更新
  
  當黑色物件插入指向白色物件的參照關係時，將這個插入的參照記錄下來，並行掃描結束後再將這些及參照關係的黑色物件為根重新掃描一次。
  
  例如D插入了對G的參照當並行掃描結束後，以D為根再次進行掃描，這時候G就會被標記為黑色，從而不被回收。
- 原始快照
  
  當灰色物件要刪除指向白色物件的參照關係時，就將刪除的參照記錄下來，並行掃描結束後，再將這些記錄過參照關係的灰色物件為根，重新掃描一次。
  
  例如E刪除了對G的參照，但是記錄下了E->G，並行掃描結束後，再掃描E並且結合E->G將G標黑，從而讓G不被回收。