本文已收錄至Github，推薦閱讀 ?? Java隨想錄
微信公眾號：Java隨想錄
CSDN： 碼農BookSea
目錄你愈是少說你的偉大，我將愈想到你的偉大，——培根
- 三色標記演算法
- 增量更新
- 原始快照
面試官：我們先從JVM基礎開始問，了解三色標記演算法嗎？
我：額......不了解，
面試官：出去的時候記得把門帶上，
現在Java面試真的已經是越來越卷了，很喜歡問底層實作原理，本篇來聊聊三色標記演算法，也是Java面試的常客，
三色標記演算法可以扯出增量更新和原始快照，聊好了會讓面試官覺得你這小伙子有點東西，
三色標記演算法
既然叫三色標記演算法，首先我們要搞明白是哪三色，三色是：黑色，白色，灰色，
把遍歷物件圖程序中遇到的物件，按照是否訪問過這個條件標記成以下三種顏色：
- 白色：表示物件尚未被垃圾收集器訪問過，顯然在可達性分析剛剛開始的階段，所有的物件都是白色的，若在分析結束的階段，仍然是白色的物件，即代表不可達，
- 黑色：表示物件已經被垃圾收集器訪問過，且這個物件的所有參考都已經掃描過，黑色的物件代表已經掃描過，它是安全存活的，如果有其他物件參考指向了黑色物件，無須重新掃描一遍，黑色物件不可能直接（不經過灰色物件）指向某個白色物件，
- 灰色：表示物件已經被垃圾收集器訪問過，但這個物件上至少存在一個參考還沒有被掃描過，
原書中的圖畫的很好，一目了然，
由于一些垃圾回收器存在垃圾回收執行緒和用戶執行緒并發的情況（例如CMS的并發階段），那么三色標記會有2個問題：
- 一種是把原本消亡的物件錯誤標記為存活，這不是好事，但其實是可以容忍的，只不過產生了一點逃過本次收集的浮動垃圾而已，下次收集清理掉就好，
- 另一種是把原本存活的物件錯誤標記為已消亡，這就是非常致命的后果了，程式肯定會因此發生錯誤，
Wilson于1994年在理論上證明了，當且僅當以下兩個條件同時滿足時，會產生“物件消失”的問題，即原本應該是黑色的物件被誤標為白色：
- 賦值器插入了一潭訓多條從黑色物件到白色物件的新參考，
- 賦值器洗掉了全部從灰色物件到該白色物件的直接或間接參考，
因此，我們要解決并發掃描時的物件消失問題，只需破壞這兩個條件的任意一個即可，由此分別產生了兩種解決方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning，SATB），
這2種解決方案各破壞一個條件
增量更新
增量更新要破壞的是第一個條件，當黑色物件插入新的指向白色物件的參考關系時，就將這個新插入的參考記錄下來，等并發掃描結束之后，再將這些記錄過的參考關系中的黑色物件為根，重新掃描一次，這可以簡化理解為，黑色物件一旦新插入了指向白色物件的參考之后，它就變回灰色物件了，
這其實有點像之前講過類似OopMap的思想，本質也是維護了個映射關系，重新掃描的時候掃描這個映射關系就行了，不用全表掃描，
原始快照
原始快照要破壞的是第二個條件，當灰色物件要洗掉指向白色物件的參考關系時，就將這個要洗掉的參考記錄下來，在并發掃描結束之后，再將這些記錄過的參考關系中的灰色物件為根，重新掃描一次，這也可以簡化理解為，無論參考關系洗掉與否，都會按照剛剛開始掃描那一刻的物件圖快照來進行搜索，
以上無論是對參考關系記錄的插入還是洗掉，虛擬機的記錄操作都是通過寫屏障實作的，寫屏障，我們之前講記憶集與卡表的時候介紹過的，可以理解為Spring中的AOP，目前為止卡表狀態的維護，增量更新，原始快照都是基于寫屏障，
另外，CMS使用的是增量更新，G1使用的是原始快照，
本篇文章就到這里，如果再遇見面試官問你類似的問題，你可以好好跟他扯皮咯，
如果本篇博客有任何錯誤和建議，歡迎給我留言指正，文章持續更新，可以關注公眾號第一時間閱讀，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/542657.html
標籤：其他
上一篇：一文弄懂三色標記演算法
下一篇：eclipse上找不到相關插件