曾經(jīng)，我以為這些東西自己平時看看書就夠了，屬于那種花了半天精力總算搞明白了，然后過兩天就自然忘記的東西。

結果，這都啥啊，啥是卡表，什么又是三色標記法，這些鬼問題都有人面試問，卷就完了。

引用計數(shù)&可達性分析

要進行垃圾回收GC，那么我們首先就要決定到底怎么判斷對象是否存活？一般來說有兩種方式。

引用計數(shù)，給對象添加一個計數(shù)器，每當有地方引用它計數(shù)器就+1，反之引用失效時就-1，那么計數(shù)器值為0的對象就是可以回收的對象，但是有一個問題就是循環(huán)引用的話無法解決。

對于現(xiàn)在的虛擬機來說，主要用的算法是可達性分析算法。

首先定義GC ROOTS根對象集合，通過GC ROOTS向下搜索，搜索的過程走過的路徑稱作引用鏈，如果某個對象到GC ROOTS沒有任何引用鏈，那么就是對象不可達，是可以被回收的對象。

不可達對象需要進行兩次標記，第一次發(fā)現(xiàn)沒有引用鏈相連，會被第一次標記，如果需要執(zhí)行finalize()方法，之后這個對象會被放進隊列中等待執(zhí)行finalize()，如果在finalize()中成功和引用鏈上的其他對象關聯(lián)，就會被移出可回收對象集合。（但是不建議使用finalize()方法）

image

分代收集

有了如何判斷對象存活的基礎，接下來的問題就是怎么進行垃圾收集GC，現(xiàn)在商用的虛擬機基本上都是分代收集的實現(xiàn)，它的實現(xiàn)建立于兩個假說：

1. 絕大多數(shù)對象都是朝生夕死的
2. 熬過越多次垃圾回收的對象越難死亡

基于這兩個假說，就產(chǎn)生了現(xiàn)在我們常見的年輕代和老年代。

因為分代了，所以GC也就分代了。

年輕代用于存放那些死的快的對象，年輕代GC我們稱之為MinorGC，每次年輕代內存不夠我們就觸發(fā)MinorGC，以后還有存活的對象我們就根據(jù)經(jīng)歷過MinorGC次數(shù)和動態(tài)年齡判斷來決定是否晉升老年代。

老年代則存放老不死的對象，這里GC稱之為OldGC，現(xiàn)在也有很多人把他叫做FullGC，實際上這并不準確，F(xiàn)ullGC應該泛指年輕代和老年代的的GC。

按照我們上文所說的使用可達性分析算法來判斷對象的存活，那么假如我們進行MinorGC，會不會有對象被老年代引用著？進行OldGC會不會又有對象被年輕代引用著？
如果是的話，那我們進行MinorGC的時候不光要管GC Roots，還有再去遍歷老年代，這個性能問題就很大了。

因此，又來了一個假說。。。

跨代引用相對于同代引用來說僅占極少數(shù)。

由此就產(chǎn)生了一個新的解決方案，我們不用去掃描整個老年代了，只要在年輕代建立一個數(shù)據(jù)結構，叫做記憶集Remembered Set，他把老年代劃分為N個區(qū)域，標志出哪個區(qū)域會存在跨代引用。

以后在進行MinorGC的時候，只要把這些包含了跨代引用的內存區(qū)域加入GC Roots一起掃描就行了。

image

卡表

說完這些，才到了第一個話題：卡表。

卡表實際上就是記憶集的一種實現(xiàn)方式，如果說記憶集是接口的話，那么卡表就是他的實現(xiàn)類。

對于HotSpot虛擬機來說，卡表的實現(xiàn)方式就是一個字節(jié)數(shù)組。

CARD_TABLE [this address >> 9] = 0;

這段代碼代表著卡表標記的的邏輯。實際上卡表就是映射了一塊塊的內存地址，這些內存地址塊稱為卡頁，從代碼可以看出每個卡頁的大小就是2^9=512字節(jié)。

如果轉換為16進制，數(shù)組的0，1號元素就映射為0x0000～0x01FF(0-511)、0x0200～0x03FF(512-1023)內存地址的卡頁。

image

只要一個卡頁內的對象存在一個或者多個跨代對象指針，就將該位置的卡表數(shù)組元素修改為1，表示這個位置為臟，沒有則為0。

在GC的時候，就直接把值為1對應的卡頁對象指針加入GC Roots一起掃描即可。

有了卡表，我們就不需要去在發(fā)生MinorGC的時候掃描整個老年代了，性能得到了極大的提升。

卡表的問題

寫屏障

卡表的數(shù)組元素要修改成1，也就是臟的狀態(tài)，對于HotSpot來說是通過寫屏障來實現(xiàn)的，實際上就是在其他分代引用了當前分代的對象時候，在對引用進行賦值的時候進行更新，更新的方式類似AOP的切面思想。

void oop_field_store(oop* field, oop new_value) { 
// 引用字段賦值操作
*field = new_value;
// 寫后屏障，在這里完成卡表狀態(tài)更新 
post_write_barrier(field, new_value);
}

寫屏障帶來的問題就是額外的性能開銷，不過這個問題不大，還能接受。

偽共享

緩存行通常來說都是64字節(jié)，一個卡表元素1個字節(jié)，占用的卡頁內存大小就是64*512=32KB的大小。

如果多線程剛好更新剛好處于這32KB范圍內的對象，那么就會對性能產(chǎn)生影響。

image

怎么解決偽共享問題？

JDK7之后新增了一個參數(shù)-XX:+UseCondCardMark，他代表是否開啟卡表更新的判斷，沒有被標記過才標記為臟。

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

三色標記法

卡表解決了跨代收集和根節(jié)點枚舉的性能問題。而有了這些措施實際上枚舉根節(jié)點這個過程造成的STW停頓已經(jīng)屬于可控范圍。

另外還存在一個問題就是接下來從GC Roots開始遍歷，怎么才能高效的標記這些對象，這就是三色標記法的作用了。因為如果堆內的對象越多，那么顯然標記產(chǎn)生的停頓時間就越長。

以現(xiàn)在我們熟知的CMS或者G1來舉例，GC的前兩個步驟如下：

1. 初始標記：標記GC ROOT能關聯(lián)到的對象，這一步需要STW，但是停頓的時間很短。
2. 并發(fā)標記：從GCRoots的直接關聯(lián)對象開始遍歷整個對象圖的過程，這個時間會比較長，但是現(xiàn)在是可以和用戶線程并發(fā)執(zhí)行的，這個效率的問題就是三色標記關注的問題。

在三色標記法中，把從GC Roots開始遍歷的對象標記為以下三種顏色：

1. 白色，在剛開始遍歷的時候，所有的對象都是白色的
2. 灰色，被垃圾回收器掃描過，但是至少還有一個引用沒有被掃描
3. 黑色，被垃圾回收器掃描過，并且這個對象的引用也全部都被掃描過，是安全存活的對象

整個標記的過程如下，首先剛開始從GC Roots開始遍歷的時候肯定所有的對象都是白色的。

image

接著A\G對象被掃描到變成灰色，然后A\G對象的引用也都被掃描，A\G對象變成黑色。

B\C對象開始被掃描變成灰色，他們的引用也被掃描完成后自己也就都變成了黑色。

而后D對象也一樣會經(jīng)歷從灰色到黑色的過程(偷點懶，省略一張無關緊要的過程圖吧)

最后剩下的E\F節(jié)點就是可以被回收的對象了。

image

三色標記的問題

雖然三色標記法很高效，但是也會引申出其他的問題。

首先我們上文說過并發(fā)標記的過程是不會STW的，就是你媽在打掃衛(wèi)生，而你在旁邊一直丟垃圾，這也沒關系，大不了最后就是還有一些垃圾沒掃干凈而已。

對于三色標記來說就是把應該要清理的對象標記成存活，這樣本次GC就無法清理這個對象，這個被稱作為浮動垃圾，解決方案就是等下次GC的時候再清理，這次掃不干凈就等你媽下次打掃衛(wèi)生的時候再清理就行了。

與此相反，如果把存活對象標記成需要清理，那么就有點麻煩了，這樣你的程序就該出問題了。

所以經(jīng)過研究表明，只有同時滿足兩個條件才會發(fā)生這種對象消失的問題：

1. 插入了一條或者多條黑色到白色對象的引用
2. 刪除了全部從灰色到白色對象的引用

那么，針對這個問題也有兩種解決方案：增量更新和原始快照，如果對應到垃圾回收器的話，CMS使用的是增量更新，而像G1則是使用原始快照。

思路就是既然要同時滿足，那么我只需要破壞其中一個條件那么不就可以了嗎？

所以，先看上面我們的例子中的一個場景，假設A掃描完，剛好C成為灰色，此時C->D的引用刪除，同時A->D新增了引用（同時滿足兩個條件了吧），這樣本來按照順序接下來D應該會變成黑色(黑色對象不應該被清理)，但是由于C->D沒有引用了，A已經(jīng)成為了黑色對象，他不會再被重新掃描了，所以即便新增了A->D的引用，D也只能成為白色對象，最終被無情地清理。
[圖片上傳失敗...(image-ede014-1625575081690)]

增量更新解決方案就是，他會把這些新插入的引用記錄下來，掃描結束之后，再以黑色對象為根重新掃描一次。這樣看起來不就是增量更新嗎？新插入的記錄再掃一次！

原始快照則是去破壞第二個條件，他把這個要刪除的引用記錄下來，掃描結束之后，以灰色對象為根重新掃描一次。所以就像是快照一樣，不管你刪沒刪，其實最終還是會按照之前的關系重新來一次。