《垃圾回收的演算法與實作》第2章GC標記-清除演算法
垃圾回收系列連載：
- 第 1 章 學習GC之前
- 第 2 章 GC標記-清除演算法
- 第 3 章 參考計數法
- 第 4 章 GC復制演算法
- 第 5 章 GC標記-壓縮演算法
- 第 6 章 保守式GC
- 第 7 章 分代垃圾回收
- 第 8 章 增量式垃圾回收
- 第 9 章 RC Immix 演算法
- 第 10 章 Python 的垃圾回收
- 第 11 章 DalvikVM 的垃圾回收
- 第 12 章 Rubinius 的垃圾回收
電子書下載鏈接
第 2 章 GC標記-清除演算法
一圖總結文章內容
graph LR mark("mark(從根深搜廣搜活動物件)")-->Sweep("Sweep(掃描堆)")-->單鏈表再分配("單鏈表再分配(最先匹配、最優匹配、最糟糕匹配)")-->優缺點 Sweep("Sweep(掃描堆)")-->多鏈表再分配("多鏈表再分配(根據大小分鏈表)")-->優缺點 位圖示記("位圖示記") 延遲清除("延遲清除法")什么是GC標記-清除法
標記清除法是一種找到垃圾的方法，就是分成兩個步驟，標記和清除，標記是從根部除法做搜索，經過的則標記，清除是從堆遍歷 找到沒有使用則清除，
標記階段
標記使用什么搜索方式呢？廣度搜索、深度搜索，這個程序是要中斷物件操作的，不中斷的話，新生成的物件 就可能不可達，
清除階段
在清除階段，我們使用變數 sweeping 遍歷堆，具體來說就是從堆首地址 $heap_start 開始，按順序一個個遍歷物件的標志位，
分配階段
這里的分配是指將回收的垃圾進行再利用，遍歷 $free_list，尋找合適的 size 的分塊就是分配階段，
First -fit、Best -fit、Worst -fit 的不同：
碎片合并
前文中已經提過，根據分配策略的不同可能會產生大量的小分塊，但如果它們是連續的， 我們就能把所有的小分塊連在一起形成一個大分塊，這種“連接連續分塊”的操作就叫作合 并(coalescing)，合并是在清除階段進行的，
優點
- 實作簡單
- 與保守式 GC 演算法兼容
缺點
- 碎片化
- 分配速度
- 與寫時復制技術不兼容 行程 fork 節省記憶體的方法
多個鏈表的空閑表
利用分塊大小不同的空閑鏈表，即創建只連接大分塊的空 閑鏈表和只連接小分塊的空閑鏈表，
BiBOP
將大小相近的物件整理成固定大小的塊進行管理的做法
延遲清除
個人對這里有新理解： 所有的物件，一旦物件不在根部有參考，那么這個物件就不可能再被參考，標記后，沒有被標記的物件一定是非活動物件了，但是新產生的物件再后續的發展中 可能成為非活動物件也可能成為非活動物件，那么這些新物件都標記不能被清除，因此沒有標記的物件是可以延遲清除的，不會再次被標記，但是要注意新物件都要標記，
請期待 “第 3 章 參考計數法”
個人簡介：高級開發工程師，興趣和領域（Unity、Unreal、cocos creator、安卓終端開發、ios終端開發、音視頻開發、圖形學），歡迎加W：wlxklyh 探討問題，（歡迎star：https://github.com/wlxklyh/SoftRenderer）
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/194820.html
標籤：Android