并發标記清除之初始标記
初始标記是對老生代中活躍對象進行标記的第一步，僅僅收集從老生代外部指向老生代的活躍對象，這些對象構成了初始标記的輸出，并作為下一步并發标記的輸入。下面通過一個簡單的例子來介紹初始标記的思路。假設堆記憶體在執行初始标記前如圖4-24所示。
圖4-24 堆記憶體初始狀态
初始标記是尋找老生代外部指向老生代的活躍對象。對垃圾回收算法來說，有以下兩種實作方法：
1）從根集合出發周遊根集合，找到是否存在指向老生代的對象引用，如果存在引用則直接作為根輸出。在周遊過程中需要周遊新生代所有對象才能知道是否有指向老生代的對象引用。
2）直接将新生代作為根，和其他的根集合一樣判斷是否存在指向老生代的對象引用，如果存在引用則直接作為輸出。
第一種方法能準确地識别老生代中的活躍對象，但是需要周遊整個新生代，會導緻初始标記耗時較長；第二種方式會存在一定的誤差，可能将新生代中已經死亡的對象作為根，導緻老生代中存在浮動垃圾，但是該方法僅需較短的時間就可以完成初始标記。不同的垃圾回收實作中可能采用不同的實作細節，比如OpenJ9中的gencon采用第一種方法，而JVM的CMS采用第二種方法。
是以在初始标記時會把根集合和新生代作為老生代活躍對象的根，如果發現引用的對象在老生代中，則把對應的老生代對象标記出來。為了不影響Mutator的運作，不能直接在對象上進行标記，否則需要鎖（因為在整個老生代回收周期中對象可能會被修改，Mutator也會通路對象，為了保證正确性，并發通路時需要鎖進行同步）。但使用鎖将導緻性能下降，是以引入了一個标記位圖（Bitmap）用于記錄活躍對象。在初始标記完成時，通過标記位圖記錄根集合（含新生代）指向老生代的直接引用。根據堆的初始狀态，标記位圖中有3個位被設定，其中有兩個來自根集合，一個來自新生代，如圖4-25所示。
圖4-25 标記位圖示意圖
标記位圖的粒度和卡表粒度有所不同，老生代中每個字都有一個位與之對應。
新生代的處理思路也是将新生代劃分為多個記憶體塊，由多個線程并行處理。
但是劃分的方式與參數設定有關，預設情況下是新生代劃分為多個記憶體塊。其中Eden的劃分與參數CMSEdenChunksRecordAlways相關（預設值為true），如果參數為false，整個Eden被一個線程處理。關于劃分Eden的更多資訊在預清理階段再詳細介紹。Survivor的劃分與PLAB相關，PLAB是MinorGC并行執行時為防止多線程間同步而引入的，每個線程都有一個緩沖區（稱為PLAB），當對象從Eden轉移到Survivor時都從PLAB中配置設定。可以利用這樣的特性，在初始标記處理Survivor分區時，每個線程以PLAB大小為粒度進行并行處理（隻需要在初始化時按照PLAB大小對Survivor進行劃分即可，然後在執行Minor GC時記錄每個劃分的對象）。
并發标記清除之并發标記
并發标記的輸入是初始标記的輸出，即标記位圖。在并發标記階段，根據标記位圖中的初始活躍對象在老生代中進行周遊，找到老生代中所有活躍的對象。并發标記執行時Mutator正常運作，并發标記本身也是多個線程同時執行标記動作。
為了保證标記的正确性，在并發标記的同時，如果Mutator運作中修改了老生代中對象的引用關系，則會通過卡表的方式進行記錄，在并發标記結束後再對卡表記錄的對象做額外的标記，進而保證标記的正确性。更多具體資訊參考上一節介紹。本節主要關注如何高效地進行并發标記。
針對标記位圖高效執行并發标記的思路非常簡單，那就是将老生代記憶體劃分成大小一定的塊，每個線程處理一個記憶體塊。線程執行标記時，根據記憶體塊對應的标記位圖中存在的标記位找到待标記對象，周遊待标記對象的成員變量，直到完成整個老生代記憶體塊的處理，此時老生代中所有活躍對象都被标記。記憶體塊的大小通過參數CMSConcMarkMultiple控制，預設值為32，表示記憶體塊的大小為32×4KB=128KB。
下面通過一個例子來介紹一下并發标記。假設初始标記後标記位圖中有兩個标記位被設定，分别對應對象A和B。在并發标記中，首先對老生代進行劃分，假設老生代被劃分為n個記憶體塊，其中第一個記憶體無标記位圖。同時假設有3個線程T0、T1和T2，分别對記憶體塊進行處理。T0在執行時在标記位圖中找不到标記對象，是以T0會跳過記憶體塊0，然後尋找下一個可用的記憶體塊。T1和T2分别處理記憶體塊1和記憶體塊2，如圖4-26所示。
圖4-26 并發标記示意圖
在圖4-26中可以看到，對象A引用到記憶體塊0和記憶體塊2中的對象，同時對象B也引用到記憶體塊2的對象。對象A和對象B分别由T1和T2進行周遊标記，可能存在T1和T2需要同時标記對象C的情況，是以兩個線程需要競争通路對象C，在辨別時通過對标記位圖的競争來确定誰來處理對象C，是以對象的标記可能由T1執行，也可能由T2執行。另外，對象A還有一個指向塊0的對象D，也需要被标記，也是由T1處理。
線程在進行标記時通過線程的局部标記棧來儲存待進一步标記的對象。在并發标記中，如果遇到線程局部标記棧溢出的問題，并發标記的處理思路和其他标記的處理思路并不相同。并發标記如果遇到标記棧溢出的情況，會記錄溢出對象的位址，目前并發标記執行結束後如果發現标記棧溢出，會再次進入并發标記并從溢出對象開始向後重新周遊标記整個空間的對象。當有多個線程同時發生标記棧溢出時，将位址最低的對象作為重新開始标記的起點。在并發标記中發生标記棧溢出會導緻成本提高，可能需要做大量無用的重複周遊工作。
那麼為什麼并發标記中标記棧溢出處理和其他标記中的處理方式均不相同？最主要的原因還是并發操作帶來的複雜性。例如下面介紹的再标記階段也是多線程執行，也可能存在标記棧溢出的情況，但是再标記階段可以通過額外的技術來處理标記棧溢出的情況。這裡先不展開介紹，在本章擴充閱讀中會對标記棧溢出展開介紹。
并發标記的整體算法如上所述，但是在處理每個記憶體塊時還是進行了一個小小的優化。具體來說就是，當處理本記憶體塊中的标記對象時，會從起始位址到結束位址逐一判斷是否需要掃描，如果掃描完成那麼增加起始位址的位置用finger表示。一個簡單的例子如圖4-27所示。
圖4-27 一個記憶體塊中并發标記處理優化示意圖
當标記對象A時，finger指向對象A的起始位址，A有兩個對象引用，分别是對象C和對象D，在标記時僅會處理對象D（包含标記對象D并周遊标記對象D的成員變量），但是對于對象C，僅僅标記而不周遊标記其成員變量。
首先，這樣的設計在正确性方面是沒有問題的，當對象A處理完成後，對象C位于尚未周遊的記憶體空間中，即對象C在後續的進行中還會被周遊到。那麼為什麼要這樣設計？為什麼不直接按照深度周遊标記對象C？其主要目的是減少标記棧的溢出。在标記棧溢出時，并發标記會從最低位址對象重新開始繼續标記，成本相對比較高。本質上該優化是将原本可以深度周遊的對象轉換為寬度周遊。
本文給大家講解的内容是JVM垃圾回收器詳解：并發标記清除回收，并發的老生代回收-并發标記清除之初始标記、并發标記
- 下篇文章給大家講解的内容是JVM垃圾回收器詳解：并發标記清除回收，并發的老生代回收-并發标記清除之預清理、可終止預清理
- 感謝大家的支援！