一、根節點枚舉

????????固定可作為GC Roots的節點主要在全局性的引用（如常量或類靜態屬性）與執行上下文（如棧幀中的本地變量表）中，盡管目標明確，但查找要做到高效很難。現在java應用越來越龐大，光方法區的大小就常有數百上千兆，里面的類、常量等更是恒河沙數，逐個檢查以這里為起源的引用肯定得消耗不少時間。

????????同時迄今為止，所有收集器在根節點枚舉這一步時都是必須暫停用戶線程的。根節點枚舉必須在一個保障一致性的快照中進行。一致性的意思是整個枚舉期間執行子系統看起來就像被凍結在某一個時間點上，不會出現分析過程中，根節點集合的對象引用關系還在不斷的變化的情況，若這點不能滿足，分析結果準確性也就無法保證。

????????由于目前主流java虛擬機使用的都是準確式垃圾收集（準確式內存管理：虛擬機可以知道內存中某個位置的數據具體是什么類型），所以當用戶線程停頓時，不需要一個不漏的檢查完所有執行上下文和全局的引用位置，虛擬機應當是有辦法直接得到哪些地方存放著對象的引用。在HotSpot的解決方案里，是使用一組稱為OopMap的數據結構來達到這個目的。

????????類加載完成時，HotSpot就會把對象內什么偏移量上是什么類型的數據計算出來，在即時編譯過程中，也會在特定的位置記錄下棧里和寄存器里哪些位置時引用。這樣收集器掃描時就可以直接知道這些信息，并不需要真正一個不漏從方法區等GC Roots考試查找。

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

二、安全點

????????HotSpot沒有為每一條指令都生成OopMap,上面提到的“類加載完成時，HotSpot就會把對象內什么偏移量上是什么類型的數據計算出來，在即時編譯過程中，也會在特定的位置記錄下棧里和寄存器里哪些位置時引用”中提到的特定的位置記錄了這些信息，這些位置被稱為安全點（Safepoint）。因此，用戶程序執行時并非在任意位置都能停下來進行垃圾收集，強制要求必須執行到安全點后才能暫停。所以，安全點的選定既不能太少以至于讓收集器等待時間過長，也不能太頻繁以至于過分增大運行時的內存負荷。

? ? ? ? 安全點位置的選取標準：是否具有讓程序長時間執行的特征。因為每條指令執行的時間都非常短暫，程序不太可能因為指令流長度太長這樣的原因而長時間執行，長時間執行的最明顯特征就是指令序列的復用，例如方法調用、循環跳轉、異常跳轉等都屬于指令序列復用，所以只有具有這些功能的指令才會產生安全點。

如何讓所有線程都跑到最近的安全點停頓下來：

搶先式中斷：

????????搶先式中斷不需要線程的執行代碼主動去配合。

????????在垃圾收集發生時，系統首先把所有用戶線程全部中斷，如果發現有用戶線程中斷的地方不在安全點上，就恢復這條線程執行，讓它一會兒再重新中斷，直到跑到安全點上。

????????現在幾乎沒有虛擬機實現采用搶先式中斷來暫停線程響應GC事件。

主動式中斷：

????????設置一個標志位，線程執行時會不停的主動輪詢這個標志，一旦發現中斷標志位為真自己在最近的安全點上主動中斷掛起。

????????輪詢標志的地方和安全點是重合的，另外還要加上所有創建對象和其他需要在Java堆上分配內存的地方，這是為了檢查是否即將要發生垃圾收集，避免沒有足夠內存分配新對象。

????????由于輪詢操作在代碼中會頻繁出現，這要求它必須足夠高效。HotSpot 使用內存保護陷阱的方式，把輪詢操作精簡至只有一條匯編指令的程度。

????????下面代碼清單中的 test 指令就是 HotSpot 生成的輪詢指令，當需要暫停用戶線程時，虛擬機把0x160100 的內存頁設置為不可讀，那線程執行到 test 指令時就會產生一個自陷異常信號，然后在預先注冊的異常處理器中掛起線程實現等待，這樣僅通過一條匯編指令便完成安全點輪詢和觸發線程中斷了。

三、安全區域

????????程序“不執行”時（沒有分配處理器時間，如sleep和blocked狀態），線程無法響應虛擬機的中斷請求，不能走到安全點主動掛起，虛擬機也不可能等線程重新被激活。所以引入安全區域。

????????安全區域是指能夠確保在某一段代碼片段之中，引用關系不會發生改變。因此，在這個區域中任意地方開始垃圾收集都是安全的。可以看作擴展延伸了的安全點。

????????進入安全區域的代碼，會標識自己已經進入安全區域，虛擬機發起垃圾收集時不用去管這些線程。當線程要離開安全區域時，他要檢查虛擬機是否已經完成了根節點枚舉（或垃圾收集過程中其他需要暫停用戶線程的階段），完成，那線程就當作沒事發生，繼續執行。否則一直等待直到收到可以離開安全區域的信號。

四、記憶集與卡表

????????在分代收集中，為了解決對象跨代引用所帶來的問題，在新生代中建立記憶集的數據結構，用以避免把整個老年代加進GC Roots掃描范圍。事實上所有部分區域收集行為的垃圾收集器都會有跨代引用問題。

????????記憶集是一種記錄從非收集區域指向收集區域的指針集合的抽象數據結構。不考慮效率和成本，最簡單的實現用非收集區域中所有含跨代引用的對象數組來實現這個數據結構。

? ? ? ? 在垃圾收集場景中，收集器只需要通過記憶集判斷出某一塊非收集區域是否存在有指向收集區域的指針就行，不需要了解跨代指針的全部細節。

????????設計者在實現記憶集的時候，便可以選擇更為粗獷的記錄粒度來節省記憶集的存儲和維護成本，下面列舉了一些可供選擇（當然也可以選擇這個范圍以外的）的記錄精度：

字節精度：每個記錄精確到機器字長（就是處理器的尋址位數，如常見的32位或64位，這個精度決定了機器訪問物理內存地址的指針長度），該字包含跨代指針。
對象精度：每個記錄精確到一個對象，該對象里有字段含有跨代指針。
卡精度：每個記錄精確到一塊內存區域，該區域內有對象含有跨代指針。（用一種稱為“卡表”的方式去實現記憶集，是常用記憶集實現方式之一。）

????????記憶集其實是一種“抽象 ” 的數據結構，抽象的意思是只定義了記憶集的行為意圖，并沒有定義其行為的具體實現。卡表就是記憶集的一種具體實現，它定義了記憶集的記錄精度、與堆內存的映射關系等。

卡表最簡單的形式可以只是一個字節數組，下面這行代碼是HotSpot默認的卡表標記邏輯：

CARD_TABLE[this address >> 9] = 0;

????????字節數組CARD_TABLE 的每一個元素都對應著其標識的內存區域中一塊特定大小的內存塊，這個內存塊被稱作“ 卡頁 ” （ Card Page ）。一般來說，卡頁大小都是以 2 的 N 次冪的字節數，通過上面代碼可以看出HotSpot 中使用的卡頁是 2 的 9 次冪，即 512 字節（地址右移 9 位，相當于用地址除以 512 ）。那如果卡表標識內存區域的起始地址是0x0000 的話，數組 CARD_TABLE 的第 0 、 1 、 2 號元素，分別對應了地址范圍為0x0000 ～ 0x01FF 、 0x0200 ～ 0x03FF 、 0x0400 ～ 0x05FF 的卡頁內存塊，如下圖所示。

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

五、寫屏障

????????何時變臟：有其他分代區域中對象引用了本區域對象時，其對應的卡表元素就應該變臟，變臟時間點原則上應該發生在引用類型字段賦值的那一刻。

? ? ? ? 如何變臟，即如何更新維護卡表：

若是解釋執行的字節碼，虛擬機負責每條字節碼指令的執行，有充分的介入空間。
若是編譯執行，經過即時編譯后的代碼已經是純粹的機器指令流了，這就必須找到一個在機器碼層面的手段，把維護卡表的動作放到每一個賦值操作之中。

????????HotSpot通過寫屏障（Writer Barrier）技術維護卡表。寫屏障可以看作在虛擬機層面對“引用類型字段賦值”這個動作的AOP切面，在引用對象賦值時會產生一個環形（Around）通知，供程序執行額外的動作，也就是說賦值前后都在寫屏障的覆蓋范圍內。在賦值前的部分的寫屏障叫做寫前屏障（Pre-Write Barrier），賦值后則叫寫后屏障（Post-Write Barrier）。

G1之前只用到寫后屏障。

寫后屏障更新卡表，如下圖。

????????除了寫屏障開銷外（相較于掃描整個老年代的代價低），卡表在高并發下面臨著“偽共享”問題。中央處理器的緩存系統是以緩存行為單位存儲，多線程修改獨立變量，這些變量恰好共享同一個緩存行，就會彼此影響（寫回，無效化或同步）而導致性能降低。

????????解決偽共享辦法：不采用無條件的寫屏障，先檢查卡表標記，只有卡表元素未被標記過時才將其標記變臟，即卡表更新邏輯變為：

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

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

六、并發的可達性分析

????????在根節點枚舉這個步驟中，GC ROOTS相比起整個java堆中全部的對象已經減少了很多，且在各種優化技巧（如OopMap）的加持下，它帶來的停頓已經非常短暫且相對固定。可從GC Roots繼續往下遍歷對象圖，這一步驟的停頓時間必定與java堆容量成正比關系：堆越大，存儲的對象越多，對象圖結構越復雜，要標記更多對象而產生的停頓時間的更長。

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

首先了解一下為什么在一個能保障一致性的快照下才能進行對象圖的遍歷？我們使用三色標記輔助推導：

白色：對象尚未被垃圾收集器訪問到。在可達性分析剛剛開始階段，所有階段對象都是白色，分析結束階段，仍為白色，即代表不可達。
黑色：對象已經被垃圾收集器訪問過，且這個對象的所有引用都已經掃描過。黑色對象代表已經掃描過，它是安全存活的，如有其他對象引用指向黑色對象，無須重新掃描。黑色對象不可能直接（不經過灰色對象）指向某個白色對象。
灰色：對象已經被垃圾收集器訪問過，但這個對象上至少存在一個引用還沒有被掃描過。

????????可達性分析的掃描過程，可以看作對象圖上一股以灰色為波峰的波紋從黑向白推進的過程。用戶線程凍結不會有任何問題。但用戶線程并發，收集器在標記時，用戶線程在修改引用，會導致兩種結果：一種是把原本消亡的對象錯誤標記為存活，即產生浮動垃圾，下次收集即可，可以容忍。另一種是把原本存活的對象標記為已消亡，這就很致命了，程序肯定會因此發生錯誤，下面演示這樣的致命錯誤是怎樣產生的。

“對象消失”問題：原本應該是黑色的對象被誤標為白色。

“對象消失”問題產生的條件(需要同時滿足)：

賦值器插入了一條或多條從黑色對象到白色對象的新引用
賦值器刪除了全部從灰色對象到該白色對象的直接或間接引用

解決“對象消失”問題：增量更新 和 原始快照。

增量更新：破壞第一個條件，當黑色對象插入新的指向白色對象的引用關系時，就將這個新插入的引用記錄下來，等并發掃描結束后，再將這些記錄過的引用關系中的黑色對象為根，重新掃描一次。簡化理解為：黑色對象一旦新插入了指向白色對象的引用之后，他就變回灰色對象了。
原始快照：破壞第二個條件，當灰色對象要刪除指向白色對象的引用關系時，就將這個要刪除的引用記錄下來，在并發掃描結束之后，再將這些記錄過的引用關系中的灰色對象為根，重新掃描一次。簡化理解為：無論引用關系刪除與否，都會按照剛剛開始掃描那一刻的對象圖快照來進行搜索。