Mark-and-Sweep algorithm
by Jing. (mqJing@gmail.com)
Android Dalvik VM 記憶體管理中, 很重要的一個項目是 garbage collection (GC). 其中 GC 的算法就是使用 Mark-and-Sweep algorithm. 這份文件包含了 Mark-and-Sweep algorithm 最簡單的解說. 另外你也可以在 reference 中, 參考 android 的實作方式.
Note: 從 HC 開始後, 充分使用 multi-core 的效能. 也就是說當正在進行掃除垃圾的時候, 不會暫停 目前正在執行的 process.
特色:
- unreferenced object 不會立即被清除, 除非等到所有可用的記憶體被耗盡
- 當沒有記憶體可用時, 正在執行的 process 會被暫停(suspended) 讓 mark-and-sweep 算法去 收集垃圾
- 當所有的 unreferenced object 全部回收後, 恢復(resume) 正常的程式執行
Tracing garbage collector
這類 collector 會 trace 整個程式中, 直接或間接可存取的物件集合
名詞解釋
root: 程式可以被 local 或 static variable 直接存取的物件
什麼是間接存取的物件呢: 該物件被其他物件的 field 所 reference
live: 一個可以被存取的物件, 稱為 live
garbage: 無法間接或直接存取的物件
Mark-and-Sweep Garbage algorithm 簡介
Step 1: 找出所有可以存取的物件 [mark phase]
Step 2: 掃描整個 heap 並且回收那些 unmark 的物件 [sweep phase]
簡單的說:
for each root variable r mark (r);sweep (); |
如何做 mark?
- 基本上, 在每個物件的欄位都有一個 field 稱為 marked, default value = false
- 然後, 從一個物件 p 開始, 對他所有可以存取的物件, 進行遞迴地 mark 的工作
就是這樣:
void mark (Object p){ if (!p.marked){ // 針對沒有被 mark 的物件p.marked = true; for each Object q referenced by p // 搜索全部可存取物件 mark (q); // 遞迴搜索 } } |
如何掃出垃圾?
- 對整個 heap 掃出沒有被 marked 的物件, 並且釋放記憶體
- 同時, reset marked=false 以便下次垃圾收集.
簡單的說, 可以這樣表示
| void sweep (){ for each Object p in the heap if (p.marked) p.marked = false else heap.release (p); } |
全部串起來
Step 1: 對於一個 root, 尚未執行GC的物件 reference 狀態
Step 2: 經過 mark 程序的結果
Step 3: 最後清掃過的結果
Enjoy!
by Jing.
References
- Mark-and-Sweep, http://www.brpreiss.com/books/opus5/html/page424.html
- Android Dalvik Source, dvmHeapMarkRootSet()::dalvik/vm/alloc/MarkSweep.c
- Android Dalvik Source, struct GcSpec::dalvik/vm/alloc/Heap.h