GC標記-清除算法
分為兩個階段
- 標記階段：把所有活動對象做上標記的階段域帐。
- 清除階段：把那些沒有標記的對象（非活動對象）回收的階段。
通過這兩個階段就可以令不能利用的內(nèi)存空間重新得到利用。
偽代碼如下：
mark_sweep() {
mark_phase() //標記階段
sweep_phase() //清除階段
}
假設我們執(zhí)行GC前堆的狀態(tài)示意圖如下：
執(zhí)行GC前堆的狀態(tài)
標記階段
簡單概況： 標記階段就是“遍歷對象并標記”的處理過程
偽代碼如下：
mark_phase() {
for(r: $roots) {
mark(*r)
}
}
標記階段中踩衩，為所有活動對象打上標記恍涂。其中活動對象是通過遍歷、遞歸根（roots）直接引用的對象。
mark() 函數(shù)功能如下：
mark(obj) {
if(obj.mark == FALSE) { //檢查對象標記狀態(tài)
obj.mark = TRUE //將標記置為TRUE
for (child : children(obj)) {
mark(*child) //遞歸標記引用的對象
}
}
}
標記操作會對對象中的mark標志位進行處理：
設置標志位的處理
標記階段結束后弃鸦，堆的狀態(tài)如下：
標記階段結束后狀態(tài)
清除階段
清除階段會遍歷整個堆听盖，并回收沒有打上標記的對象（垃圾對象）胀溺。使其能再次得到利用。
偽代碼：
sweep_phase() {
sweeping = $heap_start //堆起始位置
while(sweeping < $heap_end) { //遍歷堆
if(sweeping.mark == TRUE) {
sweeping.mark = FALSE // 重置標記狀態(tài)
} else {
sweeping.next = $free_list //加入到空閑鏈表
$free_list = sweeping
}
sweeping += sweeping.size //移動指針到堆中下一個對象的頭
}
}
相關說明：
-
sweeping: 用來遍歷堆的指針,每移動一次增加當前sweeping.size個大小皆看。 -
size域: 存儲對象大胁治搿（字節(jié)數(shù)）的域，與mark域一樣腰吟，事先定義在對象頭中无埃。 -
$free_list: 名為空閑鏈表的單向鏈表，遍歷堆時會將非活動對象加入到空閑鏈表中毛雇。后續(xù)分配新對象時嫉称，通過遍歷這個空閑鏈表來找到分塊。 -
next域: 只有在生成空閑鏈表及從空閑鏈表中取出分塊時才會使用到灵疮，因此不需要額外定義一個next域织阅，實際上是對象最初始的域（field1）。即給field1取的別名為next震捣。與C語言中union 聯(lián)合體概念相同蒲稳。 （有點難于理解）
清除階段完成后堆狀態(tài)如下：
清除階段結束后堆狀態(tài)
總結: 清除階段程序會遍歷所有堆氮趋，進行垃圾回收。因此江耀，花費的事件與堆大小成正比剩胁。堆越大，清除階段花費的時間越長祥国。
分配
分配指將回收的垃圾進行再利用昵观。即當mutator申請分塊時，將合適大小的分塊分配給muator舌稀。實際操作是通過搜索空閑鏈表并尋找大小合適的分塊啊犬。
偽代碼：
new_obj(size) {
chunk = pick_chunk(size, &free_list) {
if(chunk != NULL) {
return chunk //返回分塊
}
else {
allocation_fail() //分塊失敗
}
}
}
其中pick_chunk()函數(shù)用于遍歷$free_list空閑鏈表，尋找大于等于size的分塊壁查。
- 如果找到和
size大小相同的分塊觉至，則會直接返回該分塊； - 如果找到比
size大的分塊睡腿，則將其分割成size大小的分塊和去掉size大小后剩余大小的分塊语御，并把剩余的分塊返回空閑鏈表。 - 如果沒有找到合適的分塊席怪，則拋出分配錯誤应闯。
