并行的新生代回收
CMS新生代回收相比串行新生代回收最大的優化是将串行算法更新為并行算法。
并行回收在CMS中被稱為ParNew。從串行到并行需要考慮的問題是：如何讓多個線程并行地執行任務？如果多個并行線程任務負載不均衡該如何處理？如何判斷多個線程并行執行結束？
本篇僅讨論CMS如何将串行任務并行執行的問題，關于多線程任務負載均衡和任務結束的問題在後續讨論。
前面已經詳細介紹過串行的複制算法，本文主要介紹兩者的異同點。
類似于串行回收，ParNew也是在新生代記憶體不足時觸發。回收算法的流程圖也和串行回收的算法流程圖類似，但ParNew采用了并行的實作，主要表現如下：
1）根處理并行化。
2）周遊對象使用深度周遊，并行處理。
3）引用支援并行。
4）弱根支援并行。
另外，需要注意對轉移失敗的處理，串行回收中如果發生轉移失敗，則會繼續掃描和轉移該對象的成員變量。ParNew轉移失敗，會把失敗對象放入待周遊對象中，繼續執行轉移，但是并不會真的繼續轉移該對象（因為已經設定轉移失敗），也會繼續掃描和轉移該轉移失敗對象的成員變量。ParNew在轉移失敗發生之後，會把全局的标志位設定為true，自此以後轉移的對象隻能移到To空間，不會再晉升到老生代空間。ParNew的并行算法流程圖如圖4-5所示。
圖4-5 新生代并行回收流程圖
在對根進行并行處理時，可以根據根集合的特性選擇不同的并行處理方式。簡單地說，可以從指向新生代的位置來源進行劃分。
1）從非堆空間指向新生代：典型的根集合有線程棧、中繼資料等，稱為一般根集合。
2）從堆空間指向新生代：卡表儲存了老生代到新生代的引用。
這樣設計的原因主要是，一般根集合通常都比較小，且各個根集合的元素之間都很明确；而卡表覆寫的是整個老生代，老生代通常比較大，卡表的并行處理通常是劃分為多個小空間進行處理，但是劃分的小空間的起始位址通常不是一個完整對象的起始位址，是以需要額外處理，以確定每個小空間的處理都從第一個完整的對象開始。
一般根集合的并行處理
和串行标記相比，ParNew根集合并行化如何實作呢？
假設在垃圾回收時有N個根集合，有M個線程執行垃圾回收。當M大于等于N時，每個線程都可以單獨處理一個根集合；當N大于M時，M個線程先從N個根集合中選擇M個進行處理，當一個線程處理完一個根集合之後，再從剩餘的NM個根集合中選擇一個進行處理，直到N個根集合都處理完成。
從實作角度來看也比較簡單。可以定義一個數組，長度為根集合的個數（此處為N），數組中的每個元素标記一個根集合是否被處理。每個線程都從數組中依次擷取元素的狀态，并嘗試設定元素狀态為已處理，如果能夠擷取并成功設定元素狀态，則處理這個元素對應的根集合；如果擷取到的元素狀态為已經處理，則處理下一個根。注意，在這個過程中，擷取和設定動作可能被M個線程同時執行，是以需要使用CAS原子性操作來保證有且僅有一個線程能成功設定狀态。
在根集合的進行中，線程棧這個根集合處理稍有不同。線程棧并不像其他的根集合那樣作為一個整體，被一個GC工作線程進行掃描和标記，而是把每一個線程的線程棧都作為一個根集合。這是因為在運作時線程數量可能比較多，且棧到堆的引用比較多，如果僅使用一個線程來處理，可能導緻該GC工作線程處理根集合所需的時間長，這将導緻後續處理時發生線程間任務的竊取機率很高。是以為了平衡線程間的待處理對象，可将每一個線程都作為一個根集合。在實作時，Java線程的資料内部有一個變量用于記錄線程棧是否被M個線程之一的GC線程處理，修改變量也需要使用CAS指令。
老生代到新生代引用的并行處理
上面提到對于代際引用的并行處理方法是把老生代記憶體分成更小的塊，然後讓多個線程并行地處理。這樣做遇到的第一個問題就是每個記憶體塊的大小該怎麼設定？記憶體塊設定得太大，掃描效率可能高，但可能出現并行線程處理不均衡的現象；記憶體塊設定得過小，可能導緻并行線程處理邊界時出現沖突，降低性能。JVM提供一個參數ParGCCardsPerStrideChunk（預設值為256，意思是每個線程一次處理256個卡塊），讓使用者自己設定記憶體塊的大小。記憶體塊（稱為chunk）大小可以通過公式計算得到，如果使用者沒有顯式地設定參數，則使用預設參數。計算方式如下：
chunk = ParGCCardsPerStrideChunk×Card size = 256×512B = 128KB
将整個堆空間劃分成chunk以後，就可以建立M個線程與chunk之間的映射了，例如0号線程處理0，M，2M，…，1号線程處理1，M+1，2M+1，…，以此類推。
但是實際中還經常遇到這樣的情況，有些chunk中包含的代際引用非常多，而有些chunk包含的代際引用比較少。為了讓M個線程執行的任務盡可能地均衡，JVM增加了一層映射，稱為條代（strip）。JVM中提供了一個額外的參數ParGCStridesPerThread（控制每個線程執行的strip數目），讓所有的記憶體塊均分到ParGCStridesPerThread×M個strip中。
預設情況下ParGCStridesPerThread是線程個數的2倍，即整體strip為2M，讓chunk先映射到2M個strip中，然後再讓M個線程執行2M個strip。chunk、strip和線程的映射關系如圖4-6所示。
為什麼采用兩級映射，而不是直接把記憶體劃分到2M個線程上呢？原因是防止過大的記憶體塊中出現不均衡現象。例如在程式運作初期，整個老生代隻有前面部分記憶體存在指向新生代的引用，按照這樣的方式劃分，可能隻有一個或者兩個線程非常忙碌地工作，其他線程都處于空閑狀态。而按照現在的設計，則可以避免這種情況。
圖4-6 老生代并行粒度劃分示意圖
記憶體按照chunk劃分以後會帶來另外一個問題，那就是一個對象可能跨越記憶體塊。理論上來說，不同的記憶體塊由不同的線程處理，對于跨越記憶體塊的對象該如何處理？
在介紹如何處理跨記憶體塊對象之前，先了解一下JVM中涉及的兩類代際引用，一種是精确的引用，另一種是不精确的引用。這兩種引用分别對應以下兩種場景：
當老生代對象被修改時，JVM明确地知道哪一個成員變量被修改，是以在掃描時可以隻掃描這個成員變量指向的新生代，這就是所謂的精确的引用。在JVM的GC階段通常使用精确的引用來記錄引用關系。
JVM内部還定義了非精确引用，主要是在通過寫屏障往記憶體寫對象時，統一将對象頭對應的卡表設定為Dirty（這樣設計主要是為了減少寫屏障的執行，可以通過優化參數進一步要求在寫之前判斷是否已經設定過卡表）。在掃描時需要掃描整個對象的成員變量，并處理那些真正指向新生代的成員變量。這種掃描稱為不精确的引用。
這兩種不同的引用可以同時存在，但這會增加跨記憶體塊處理的複雜性。
為了能準确地處理跨記憶體塊的情況，ParNew設計了一個算法來計算待處理記憶體塊的邊界。
1）區間的頭部。
如果記憶體塊的頭部剛好是對象的起始位址，則區間的頭部為記憶體塊的頭部。
如果記憶體塊的頭部不是對象的起始位址，說明對象跨了至少兩個區間，并且該記憶體塊不包含對象的起始位址。簡單的處理就是找到第一個需要處理的卡塊對應的位址作為區間的頭部（隻要存在引用，無論是精确的引用還是不精确的引用都可以找到）。
2）區間的尾部則根據引用類型的不同采用不同的計算方式。
如果最後一個對象是非精确引用，并且不是數組對象，此時整個對象都需要處理，且可能需要跨記憶體塊（需要找到對象的尾部），是以區間的尾部一般計算到對象的尾部，或者直到對象存在精确引用時停止。
如果對象是精确引用，或者是資料對象，或者不是對象類型（即基本類型），則區間的尾部直接設定為記憶體塊的結束位址。
在周遊記憶體塊時，會根據區間的情況及是精确引用還是不精确引用來處理（此處處理指的是根據引用，判斷對象是活躍對象，需要轉移對象還是晉升對象）。精确引用隻處理對應的卡塊，不精确引用将處理整個對象的所有成員變量。
并行周遊記憶體塊時采用逆序周遊，從後向前逐一掃描對象。原因就是有精确引用和不精确引用。為了更快速地處理精确引用，如果是正序處理，從前向後，對于不精确引用處理比較簡單，對象所有的成員變量都需要掃描。
到精确引用部分需要分成兩種情況處理，若對象不包含不精确引用，則僅處理卡塊；若對象是不精确引用，此時不精确引用處理需要處理整個後半部分（或者到達下一個精确引用的卡塊）。而從後向前處理，邏輯更為簡單。
卡表的競争操作介紹
在對卡表的周遊過程中，Minor GC的執行過程還會存在多個線程同時更新卡表的動作。觸發寫同一卡塊的主要原因是新生代中對象位置發生變化，但是老生代中的對象仍然存在對新生代的引用，此時需要更新卡表，保持代際引用的正确性。而多個線程按照記憶體塊劃分通路卡表，也會修改卡表（一般處理是先将卡表中的卡塊設定為Clean），表示卡塊已經周遊完成（MinorGC執行過程中新生代對象會晉升，意味着目前的卡塊變成無效值，是以将卡塊設定為Clean。如果不将卡塊設定為Clean，則會導緻大量的浮動垃圾）。
是以在Minor GC執行過程中實際上存在兩種修改卡表的操作，分别記為掃描和更新：掃描指的是把老生代作為根掃描活躍對象；更新指的是Minor GC過程中對象位置變化後仍然需要記錄卡表的操作。一般來說，多個線程同時通路同一卡塊時需要鎖來保證操作的正确性，但是ParNew通過算法的設計來盡量避免鎖的使用。下面通過一個例子來示範這個設計，假設堆空間如圖4-7所示。
圖4-7 多個線程通路同一卡塊示意圖
其中Thread1（線程1，簡稱T1）和Thread2（線程2，簡稱T2）分别根據記憶體塊的區間執行掃描動作，假設T1在掃描過程中晉升了對象A，同時該對象仍然有指向新生代的引用對象B，并且晉升的對象A正好處于T2的掃描區間内，在掃描區間中有一個對象C指向了新生代的對象D。
線程T1和線程T2分别根據卡表的值執行掃描操作，在執行過程中需要修改卡塊的值以避免重複操作。假設T1先執行，執行掃描時一般需要将卡塊的值設定為Clean，從卡塊中找到對象A，并且T1繼續執行将對象晉升到對象A'處。由于A'有一個成員變量指向新生代中對象B（假設對象B已經轉移完成），說明在下一次執行Minor GC時仍然需要把對象A'作為根，是以此處需要将對應的卡塊設定為Dirty。另外，T2掃描對象C，并将卡塊設定為Clean。
由于T1和T2同時寫一個卡塊（一個線程寫卡塊為Clean，一個線程寫卡塊為Dirty），進而産生了競争。對于這樣的競争僅僅通過鎖是無法保證正确性的。
假設T1先執行，将卡塊設定為Dirty，表示該卡塊對應的對象是下一次的Minor GC的根。接着T2執行，将卡塊設定為Clean，表示該卡塊對應的對象将會處理，T2在處理過程中先根據對象C轉移對象D，假設對象D轉移至老生代中，對于這種情況則不需要設定卡塊；然後再處理對象A'，因為對象A'是晉升對象，其成員變量的周遊已經完成，不應該再次被處理，是以卡塊保持Clean。但是卡塊應該仍然為Dirty才能保證下一次Minor GC可以正确處理。
另外，在老生代的回收中，也會通過卡表記錄對象的引用變化，并且在老生代的回收中也會處理和設定卡表。如果不正确地設定卡表将導緻MinorGC的根丢失。
是以，此時就涉及在正确地處理卡表的同時保證效率的問題。下面來看看ParNew是如何實作的。首先定義以下幾個狀态。
1）prev_youngergen：上一次執行Minor GC後明确包含了老生代對象指向新生代對象的引用，是本次垃圾回收的根。
2）Dirty：上一次垃圾回收後，對象的成員被修改，該修改可能是識别為老生代到新生代的引用，或者老生代到老生代的引用，并且該引用尚未被老生代回收或新生代回收處理。
3）PreClean：老生代回收中通過處理卡表标記了修改的對象，但是修改對象仍然可能包含老生代到新生代的引用，是以引入一個不同于Dirty的狀态（在後面介紹）。
4）cur_youngergen：本次執行Minor GC後明确存在老生代對象指向新生代對象的引用，是下一次垃圾回收的根。
5）cur_youngergen_and_prev_nonclean_card：臨時狀态，表示目前卡塊需要被掃描，又有下一次Minor GC的根，但是執行了更新尚未執行掃描，後面需要執行一次掃描。
卡表掃描和更新的流程分為兩步，不同的操作根據不同的狀态設定對應的卡塊值。
線程掃描卡表時，先根據目前卡塊的狀态決定是否需要處理，如果卡表中的卡塊為Clean，表示不需要處理，直接跳過卡塊；如果卡表中的卡塊不為Clean，表示需要處理，在處理之前先更新卡塊。
1）當發現卡塊的狀态為prev_youngergen、Dirty和PreClean時，先把卡塊設定為Clean。
2）當發現卡塊的狀态為cur_youngergen_and_prev_nonclean_card時，說明本線程正在與别的線程競争修改卡塊，同時别的線程已經更新過卡塊，且标注該卡塊包含了下一次Minor GC的根，但是該卡塊尚未完成掃描，是以執行掃描，并将卡塊狀态設定為cur_youngergen。
3）當卡塊狀态為cur_youngergen時，則無須進一步處理。
對應的狀态機如圖4-8所示。
圖4-8 線程掃描卡表狀态機
當線程執行對象轉移或者晉升時，如果發現卡塊不包含下一次Minor GC的根，則不會進入卡塊的處理過程中；如果卡塊包含了下一次Minor GC的根，則進入卡表更新過程中。
1）當卡塊狀态為Clean時，則更新為cur_youngergen，表示卡塊作為下一次垃圾回收的根。
2）當卡塊狀态為Dirty時，說明卡塊包含了下一次Minor GC的根，并且該卡塊尚未被處理，需要掃描，是以設定狀态為
cur_youngergen_and_prev_nonclean_card。
3）當卡塊狀态為PreClean時，說明卡塊包含了下一次Minor GC的根，并且該卡塊待掃描，也設定卡塊狀态為
cur_youngergen_and_prev_nonclean_card。
4）當卡塊狀态為prev_youngergen時，說明卡塊包含了下一次Minor GC的根，并且該卡塊待掃描，是以卡塊狀态也設定為cur_youngergen_and_prev_nonclean_card。
5）當卡塊狀态為cur_youngergen時，說明卡塊掃描完成，直接作為下一次的根，直接保留狀态cur_youngergen。
6）當卡塊狀态為cur_youngergen_and_prev_nonclean_card時，說明卡塊對應的記憶體待掃描，在掃描完成時會在另外的線程的卡表掃描結束直接更新狀态，是以這裡保持不變。
對應的狀态機如圖4-9所示。
圖4-9 線程更新卡表狀态機
在ParNew中對卡表掃描的流程圖如圖4-10所示。
圖4-10 ParNew卡表掃描流程圖
ParNew中更新卡表中對應卡塊的流程圖如圖4-11所示。
圖4-11 ParNew更新卡表流程圖
并行複制算法對于卡表的處理帶來了新的調整。上述過程以JDK 8代碼為例進行說明，堆空間隻包含了兩個代。
并行複制算法卡表設計
在JDK 7中還有持久代這個概念，相當于整個堆空間被劃分為3個代。那麼上述卡表的設計是否需要修改？更有甚者，如果堆空間被劃分成更多代，在并行複制算法中卡表該如何設計？
一種簡單的處理是針對多個代設計多個卡表，每個卡表維護一個代際之間的引用關系。這樣的方式雖然簡單，但是需要大量的卡表，存儲成本高且實作邏輯也比較複雜。除此之外，還有一個問題，在分代垃圾回收中，針對多代記憶體回收，需要差別不同代記憶體對于增量對象的管理（包括對象的晉升和對象的修改），這就涉及并行卡表的掃描和更新問題。
針對這樣的問題，一些學者探索出一種優化的方法，即使用一個卡表管理多個代際之間的引用，同時支援卡表并行掃描和更新。
專利中詳細介紹了算法，這裡簡單地進行介紹。假設整個堆空間被劃分為3個代，如圖4-12所示。
圖4-12 3個代的記憶體劃分
當記憶體被劃分成多個代時，需要多少個值記錄卡表操作狀态？以圖4-12為例，整個堆被分成3個代，分别為新生代、中生代和老生代。中生代和老生代需要對應的卡表用于記錄它們到新生代的引用，當然老生代的卡表也應該記錄老生代到中生代的引用。假設發生以下場景：
1）發生新生代回收，設第一次卡表的操作狀态為A，當垃圾回收完成後，如果老生代和中生代中存在對新生代的引用，則在卡表中記錄操作狀态為A，表示在下一次回收新生代時，操作狀态為A的卡塊都應該作為根。
2）接着發生一次中生代回收，如果垃圾回收完成後，老生代存在對中生代的引用，則需要在卡表中記錄操作狀态。但是這個操作狀态和操作狀态A并不相同，是以需要一個新的操作狀态，假設為B。對于同一卡塊，操作狀态A和B可以共存嗎？如果有沖突，該如何解決？統一設定為B。
3）接着又發生一次新生代回收，由于老生代中存在狀态A和B，A和B都表示老生代可能存在對新生代的引用。當新的垃圾回收發生時，為了差別現在的操作和以前的操作，需要一個新的狀态，記為C。在垃圾回收完成後，如果老生代和中生代中存在對新生代的引用，則在卡表中記錄操作狀态為C。
如果後續再發生新生代或者中生代垃圾回收，則可以重用狀态A，用于差別目前的操作和以前的操作。當然從算法角度來說，還可以消除狀态C的使用，那麼為了差別不同的狀态，可以在中生代的卡表使用狀态B來區分操作狀态，在老生代中使用狀态A來區分操作狀态。當然算法實作相對比較複雜。是以簡單的結論就是：直接使用分代的個數作為卡表操作狀态的個數。JVM的實作和專利的描述基本思路相同，在CMS并發回收器中使用3種操作狀态（注意，這3種操作展現為3種不同的cur_youngergen_card即可）。
本文給大家講解的内容是JVM垃圾回收器詳解：并發标記清除回收，并行的新生代回收
- 下篇文章給大家講解的内容是JVM垃圾回收器詳解：并發标記清除回收，并發回收的難點
- 感謝大家的支援！