GC標(biāo)記-清除算法
分為兩個階段
- 標(biāo)記階段：把所有活動對象做上標(biāo)記的階段。
- 清除階段：把那些沒有標(biāo)記的對象（非活動對象）回收的階段。
通過這兩個階段就可以令不能利用的內(nèi)存空間重新得到利用。
偽代碼如下：
mark_sweep() {
mark_phase() //標(biāo)記階段
sweep_phase() //清除階段
}
假設(shè)我們執(zhí)行GC前堆的狀態(tài)示意圖如下：
執(zhí)行GC前堆的狀態(tài)
標(biāo)記階段
簡單概況： 標(biāo)記階段就是“遍歷對象并標(biāo)記”的處理過程
偽代碼如下：
mark_phase() {
for(r: $roots) {
mark(*r)
}
}
標(biāo)記階段中，為所有活動對象打上標(biāo)記。其中活動對象是通過遍歷、遞歸根（roots）直接引用的對象。
mark() 函數(shù)功能如下：
mark(obj) {
if(obj.mark == FALSE) { //檢查對象標(biāo)記狀態(tài)
obj.mark = TRUE //將標(biāo)記置為TRUE
for (child : children(obj)) {
mark(*child) //遞歸標(biāo)記引用的對象
}
}
}
標(biāo)記操作會對對象中的mark標(biāo)志位進(jìn)行處理：
設(shè)置標(biāo)志位的處理
標(biāo)記階段結(jié)束后，堆的狀態(tài)如下：
標(biāo)記階段結(jié)束后狀態(tài)
清除階段
清除階段會遍歷整個堆，并回收沒有打上標(biāo)記的對象（垃圾對象）。使其能再次得到利用。
偽代碼：
sweep_phase() {
sweeping = $heap_start //堆起始位置
while(sweeping < $heap_end) { //遍歷堆
if(sweeping.mark == TRUE) {
sweeping.mark = FALSE // 重置標(biāo)記狀態(tài)
} else {
sweeping.next = $free_list //加入到空閑鏈表
$free_list = sweeping
}
sweeping += sweeping.size //移動指針到堆中下一個對象的頭
}
}
相關(guān)說明：
-
sweeping: 用來遍歷堆的指針,每移動一次增加當(dāng)前sweeping.size個大小。 -
size域: 存儲對象大?。ㄗ止?jié)數(shù)）的域，與mark域一樣，事先定義在對象頭中。 -
$free_list: 名為空閑鏈表的單向鏈表，遍歷堆時會將非活動對象加入到空閑鏈表中。后續(xù)分配新對象時，通過遍歷這個空閑鏈表來找到分塊。 -
next域: 只有在生成空閑鏈表及從空閑鏈表中取出分塊時才會使用到，因此不需要額外定義一個next域，實際上是對象最初始的域（field1）。即給field1取的別名為next。與C語言中union 聯(lián)合體概念相同。 （有點難于理解）
清除階段完成后堆狀態(tài)如下：
清除階段結(jié)束后堆狀態(tài)
總結(jié): 清除階段程序會遍歷所有堆，進(jìn)行垃圾回收。因此，花費(fèi)的事件與堆大小成正比。堆越大，清除階段花費(fèi)的時間越長。
分配
分配指將回收的垃圾進(jìn)行再利用。即當(dāng)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大小后剩余大小的分塊，并把剩余的分塊返回空閑鏈表。 - 如果沒有找到合適的分塊，則拋出分配錯誤。
