著色標(biāo)記
我們都知道cms gc 和g1 gc 的算法都是通過對(duì)gc root 進(jìn)行遍歷，并進(jìn)行三顏色標(biāo)記拯勉，具體標(biāo)記算法如下：
- 黑色(black):節(jié)點(diǎn)被遍歷完成，而且子節(jié)點(diǎn)都遍歷完成瓶蝴。
- 灰色(gray): 當(dāng)前正在遍歷的節(jié)點(diǎn)映皆，而且子節(jié)點(diǎn)還沒有遍歷。
- 白色(white):還沒有遍歷到的節(jié)點(diǎn)凉敲，即灰色節(jié)點(diǎn)的子節(jié)點(diǎn)衣盾。
并行g(shù)c 面對(duì)的共同問題
我們都知道cmg gc 和g1 gc 都是和程序有并行執(zhí)行的階段。既然有并行爷抓，那就有可能在并行運(yùn)行期間之前的標(biāo)記過的對(duì)象的引用關(guān)系可能被改變势决，比如一個(gè)白色對(duì)象從被灰色的引用變?yōu)楸缓谏膶?duì)象引用。如果不做處理蓝撇，那這個(gè)白色的對(duì)象會(huì)被漏掉果复，會(huì)被錯(cuò)誤的回收。會(huì)導(dǎo)致程序錯(cuò)誤唉地。
這也是cms gc 和g1 gc 都有remark階段的原因据悔。都需要重新對(duì)被修改的card 進(jìn)行掃描。
那cms gc 和g1 gc 是怎么解決這個(gè)問題的呢耘沼。而且有什么區(qū)別呢极颓。這就需要了解cms gc 和g1 gc 所用的算法的不一樣而導(dǎo)致不一樣的解決方案了。
cms gc 是Incremental Update算法群嗤，g1 gc 是采用的 stab 算法菠隆，下面我們先講下Incremental Update。
要知道怎么解決問題狂秘，我們先描述下問題的場(chǎng)景骇径，并行g(shù)c 在什么情況下會(huì)出現(xiàn)漏掉活的對(duì)象，根據(jù)三色掃描算法者春，如果有下面兩種情況發(fā)生破衔，則會(huì)出現(xiàn)漏掃描的場(chǎng)景：
- 把一個(gè)白對(duì)象的引用存到黑對(duì)象的字段里,如果這個(gè)情況發(fā)生，因?yàn)闃?biāo)記為黑色的對(duì)象認(rèn)為是掃描完成的钱烟，不會(huì)再對(duì)他進(jìn)行掃描晰筛。只能通過灰色的對(duì)象
- 某個(gè)白對(duì)象失去了所有能從灰對(duì)象到達(dá)它的引用路徑(直接或間接)
文字描述可能太抽象，通過下面的圖更形象
如上圖所示拴袭，的對(duì)象D 同時(shí)滿足上面兩個(gè)條件读第，引用存到了黑對(duì)象A上面，同時(shí)切斷了灰對(duì)象B對(duì)它的引用拥刻，那D對(duì)象將被漏掃描了怜瞒。
那CMS GC和G1 GC 是怎么解決這個(gè)問題的呢？
解決這個(gè)問題可以從兩個(gè)角度入手般哼，從上面的圖可以看出吴汪，指向D的這個(gè)引用從源B到目的地址A,所以就有兩種算法分別是從源和目標(biāo)的角度來解決，分別產(chǎn)生了下面兩種算法：
SATB 即 Snapshot-at-beginning
satb 算法認(rèn)為開始標(biāo)記的都認(rèn)為是活的對(duì)象蒸眠，如上圖所示,引用B到D 的引用改為B到C時(shí)浇坐，通過write barrier寫屏障技術(shù)，會(huì)把B到D 的引用推到gc 遍歷執(zhí)行的堆棧上黔宛，保證還可以遍歷到D對(duì)象近刘，相對(duì)于d來說，引用從B-->A,SATB 是從源入手解決的臀晃，即上面說的第2種情況觉渴，
這也能理解為啥叫satb 了，即認(rèn)為開始時(shí)所有能遍歷到的對(duì)象都是需要標(biāo)記的徽惋，即都認(rèn)為是活的案淋。如果我吧b = null,那么d 久是垃圾了， satb算法也還是會(huì)把D最終標(biāo)記為黑色险绘，導(dǎo)致D 在本輪gc 不能回收踢京，成了浮動(dòng)垃圾誉碴。
Incremental Update write barrier
Incremental Update 算法判斷如果一個(gè)白色的對(duì)象由一個(gè)黑色的對(duì)象引用，即目的瓣距，如上圖黔帕，D的引用由B-->A,A是目的地址，所以cms 的Incremental Update算法是從目標(biāo)入手解決的蹈丸，這是和SATB的第一個(gè)區(qū)別成黄，發(fā)現(xiàn)這種情況時(shí)，也是通過write barrier寫屏障技術(shù)逻杖，把黑色的對(duì)象重新標(biāo)記為灰色奋岁，讓collector 重新來掃描，活著通過mod-union table 來標(biāo)記荸百，cms 就是這樣實(shí)現(xiàn)的闻伶，這是第二個(gè)區(qū)別，做法不一樣够话，也是上面講的防止第一種情況發(fā)生虾攻。
Incremental Update 和 SATB 的區(qū)別。
通過上面的分析更鲁，我們知道SATB write barrier 是認(rèn)為開始標(biāo)記那一刻認(rèn)為都是活的霎箍，所以有可能有些已經(jīng)是垃圾的對(duì)象就會(huì)也被掃描，導(dǎo)致 satb 相對(duì) Incremental Update 會(huì)更多的開銷澡为，g1 gc 掃描的都是選定的固定個(gè)數(shù)的region漂坏，所以這個(gè)開銷應(yīng)該可控，但是而且浮動(dòng)垃圾也更多媒至。
還有個(gè)問題是顶别，為什么G1 GC 選擇用satb 算法，也還沒有想明白拒啰。
以上是通過仔細(xì)閱讀論文和R大的網(wǎng)上的解答得到的總結(jié)和自己的理解驯绎。
