1. 垃圾回收的簡單回顧
關于垃圾回收演算法，基本就是那么幾種：標記-清除、標記-復制、標記-整理，在此基礎上可以增加分代（新生代/老年代），每代采取不同的回收演算法，以提高整體的分配和回收效率，
無論使用哪種演算法，標記總是必要的一步，這是理算當然的，你不先找到垃圾，怎么進行回收？
垃圾回收器的作業流程大體如下：
- 標記出哪些物件是存活的，哪些是垃圾（可回收）；
- 進行回收（清除/復制/整理），如果有移動過物件（復制/整理），還需要更新參考，
2. 三色標記法
2.1 基本演算法
要找出存活物件，根據可達性分析，從 GC Roots 開始進行遍歷訪問，可達的則為存活物件（最終結果：A/D/E/F/G 可達）：
我們把遍歷物件圖程序中遇到的物件，按“是否訪問過”這個條件標記成以下三種顏色：
- 白色：尚未訪問過，
- 本物件已訪問過，而且本物件參考到的其他物件也全部訪問過了，
- 本物件已訪問過，但是本物件參考到的其他物件尚未全部訪問完，全部訪問后，會轉換為黑色，
假設現在有白、灰、黑三個集合（表示當前物件的顏色），其遍歷訪問程序為：
- 初始時，所有物件都在【白色集合】中；
- 將 GC Roots 直接參考到的物件挪到 【灰色集合】中；
- 從灰色集合中獲取物件：
3.1. 將本物件參考到的其他物件全部挪到 【灰色集合】中；
3.2. 將本物件挪到【黑色集合】里面， - 重復步驟3，直至【灰色集合】為空時結束，
- 結束后，仍在【白色集合】的物件即為 GC Roots 不可達，可以進行回收，
注：如果標記結束后物件仍為白色，意味著已經“找不到”該物件在哪了，不可能會再被重新參考，
當 Stop The World （以下簡稱 STW）時，物件間的參考是不會發生變化的，可以輕松完成標記，
而當需要支持并發標記時，即標記期間應用執行緒還在繼續跑，物件間的參考可能發生變化，多標和漏標的情況就有可能發生，
2.2 多標-浮動垃圾
假設已經遍歷到 E（變為灰色了），此時應用執行了 objD.fieldE = null (D > E 的參考斷開)：
此刻之后，物件 E/F/G 是“應該”被回收的，然而因為 E 已經變為灰色了，其仍會被當作存活物件繼續遍歷下去，最終的結果是：這部分物件仍會被標記為存活，即本輪 GC 不會回收這部分記憶體，
這部分本應該回收 但是沒有回收到的記憶體，被稱之為“浮動垃圾”，浮動垃圾并不會影回應用程式的正確性，只是需要等到下一輪垃圾回收中才被清除，
另外，針對并發標記開始后的新物件，通常的做法是直接全部當成黑色，本輪不會進行清除，這部分物件期間可能會變為垃圾，這也算是浮動垃圾的一部分，
2.3 漏標-讀寫屏障
假設 GC 執行緒已經遍歷到 E（變為灰色了），此時應用執行緒先執行了：
var G = objE.fieldG;
objE.fieldG = null; // 灰色E 斷開參考 白色G
objD.fieldG = G; // 黑色D 參考 白色G
此時切回 GC 執行緒繼續跑，因為 E 已經沒有對 G 的參考了，所以不會將 G 放到灰色集合；盡管因為 D 重新參考了 G，但因為 D 已經是黑色了，不會再重新做遍歷處理，
最終導致的結果是：G 會一直停留在白色集合中，最后被當作垃圾進行清除，這直接影響到了應用程式的正確性，是不可接受的，
不難分析，漏標只有同時滿足以下兩個條件時才會發生：
- 灰色物件斷開了白色物件的參考（直接或間接的參考）；即灰色物件原來成員變數的參考發生了變化，
- 黑色物件重新參考了該白色物件；即黑色物件成員變數增加了新的參考，
從代碼的角度看：
var G = objE.fieldG; // 1.讀
objE.fieldG = null; // 2.寫
objD.fieldG = G; // 3.寫
- 讀取物件 E 的成員變數 fieldG 的參考值，即物件 G；
- 物件 E 往其成員變數 fieldG，寫入 null值，
- 物件 D 往其成員變數 fieldG，寫入物件 G ；
我們只要在上面這三步中的任意一步中做一些“手腳”，將物件 G 記錄起來，然后作為灰色物件再進行遍歷即可，比如放到一個特定的集合，等初始的 GC Roots 遍歷完（并發標記），該集合的物件遍歷即可（重新標記），
重新標記是需要 STW 的，因為應用程式一直在跑的話，該集合可能會一直增加新的物件，導致永遠都跑不完，當然，并發標記期間也可以將該集合中的大部分先跑了，從而縮短重新標記 STW 的時間，這個是優化問題了，
寫屏障用于攔截第二和第三步；而讀屏障則是攔截第一步，
它們的攔截的目的很簡單：就是在讀寫前后，將物件 G 給記錄下來，
3. 寫屏障
給某個物件的成員變數賦值時，其底層代碼大概長這樣：
/**
* @param field 某物件的成員變數，如 D.fieldG
* @param new_value 新值，如 null
*/
void oop_field_store(oop* field, oop new_value) {
*field = new_value; // 賦值操作
}
所謂的寫屏障，其實就是指在賦值操作前后，加入一些處理（可以參考AOP的概念），讀屏障的含義也類似，
void oop_field_store(oop* field, oop new_value) {
pre_write_barrier(field); // 寫屏障-寫前操作
*field = new_value;
post_write_barrier(field, value); // 寫屏障-寫后操作
}
3.1 寫屏障 + SATB
當物件 E 的成員變數的參考發生變化時（objE.fieldG = null;），我們可以利用寫屏障，將 E 原來成員變數的參考物件 G 記錄下來：
void pre_write_barrier(oop* field) {
oop old_value = https://www.cnblogs.com/jmcui/p/*field; // 獲取舊值
remark_set.add(old_value); // 記錄 原來的參考物件
}
當原來成員變數的參考發生變化之前，記錄下原來的參考物件，
這種做法的思路是：嘗試保留開始時的物件圖，即原始快照（Snapshot At The Beginning，SATB），當某個時刻 的 GC Roots 確定后，當時的物件圖就已經確定了，
比如 當時 D 是參考著 G 的，那后續的標記也應該是按照這個時刻的物件圖走（D 參考著 G），如果期間發生變化，則可以記錄起來，保證標記依然按照原本的視圖來，
SATB 破壞了條件一：【灰色物件斷開了白色物件的參考】，從而保證了不會漏標，
3.1 寫屏障 + 增量更新
當物件 D 的成員變數的參考發生變化時（objD.fieldG = G;），我們可以利用寫屏障，將 D 新的成員變數參考物件 G 記錄下來：
void post_write_barrier(oop* field, oop new_value) {
if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
remark_set.add(new_value); // 記錄新參考的物件
}
}
當有新參考插入進來時，記錄下新的參考物件，
這種做法的思路是：不要求保留原始快照，而是針對新增的參考，將其記錄下來等待遍歷，即增量更新（Incremental Update），
增量更新破壞了條件二：【黑色物件重新參考了該白色物件】，從而保證了不會漏標，
4. 讀屏障
oop oop_field_load(oop* field) {
pre_load_barrier(field); // 讀屏障-讀取前操作
return *field;
}
讀屏障是直接針對第一步：var G = objE.fieldG;，當讀取成員變數時，一律記錄下來：
void pre_load_barrier(oop* field, oop old_value) {
if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
oop old_value = https://www.cnblogs.com/jmcui/p/*field;
remark_set.add(old_value); // 記錄讀取到的物件
}
}
這種做法是保守的，但也是安全的，因為條件二中【黑色物件重新參考了該白色物件】，重新參考的前提是：得獲取到該白色物件，此時已經讀屏障就發揮作用了，
5. 三色標記法與現代垃圾回收器
現代追蹤式（可達性分析）的垃圾回收器幾乎都借鑒了三色標記的演算法思想，盡管實作的方式不盡相同：比如白色/黑色集合一般都不會出現（但是有其他體現顏色的地方）、灰色集合可以通過堆疊/佇列/快取日志等方式進行實作、遍歷方式可以是廣度/深度遍歷等等，
對于讀寫屏障，以Java HotSpot VM 為例，其并發標記時對漏標的處理方案如下：
- CMS：寫屏障 + 增量更新
- G1：寫屏障 + SATB
- ZGC：讀屏障
作者：路過的豬
鏈接：https://www.jianshu.com/p/12544c0ad5c1
來源：簡書
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/237868.html
標籤：Java