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