就如他的字面意思一樣，由標(biāo)記階段和清除階段構(gòu)成。標(biāo)記階段是把所有的活動(dòng)對象都做上標(biāo)記的階段。清除階段是把那些沒有標(biāo)記的對象，也就是非活動(dòng)對象回收的階段。通過這兩個(gè)階段，就可以令不能利用的內(nèi)存空間重新得到利用。
1、 標(biāo)記階段
mark_phase(){
for（r:$roots）
mark(*r)
}
在標(biāo)記階段中，collector會為堆里所有活動(dòng)對象打上標(biāo)記。為此，我們首先要標(biāo)記通過根直接引用的對象。然后遞歸地標(biāo)記通過指針數(shù)組能訪問到的對象。這樣就能把所有活動(dòng)對象都標(biāo)記上。
mark(obj){
if(obj.mark == false)
obj.mark = true
for(child :children(obj))
mark(*child)
}
如果標(biāo)記未完成，則程序會在對象頭部進(jìn)行置位操作。這個(gè)位要分配在對象的頭之中，并且能用obj.mark訪問。
在標(biāo)記階段，程序會標(biāo)記所有活動(dòng)對象。毫無疑問，標(biāo)記所花費(fèi)的時(shí)間是與“活動(dòng)對象的總數(shù)成正比”。
標(biāo)記階段結(jié)束時(shí)的堆如下圖所示：
2、 清除階段
在清除階段中，collector會遍歷整個(gè)堆，回收沒有打上標(biāo)記的對象（即垃圾），使其可以再次得到利用。
sweep_phase(){
sweeping = $heap_start
while（sweeping < $heap_end）
if(sweeping.mark == true) sweeping,mark = false
else
sweeping.next = $free_list
&free_list = sweeping
sweeping += sweeping.size
}
在此出現(xiàn)了叫做size的域，這是存儲對象大小（字節(jié)數(shù)）的域，跟mark域一樣，我們事先在各對象的頭中定義他們。
在清除階段，我們使用變量sweeping遍歷堆，具體來說就是從堆首地址$heap_start開始，按順序一個(gè)個(gè)遍歷對象的標(biāo)志位。
設(shè)置了標(biāo)志位，就說明這個(gè)對象是活動(dòng)對象。活動(dòng)對象必然是不能回收的。因?yàn)槲覀內(nèi)∠麡?biāo)志位，準(zhǔn)備下一次的GC。
我們必須把非活動(dòng)對象回收再利用。回收對象就是把對象分塊，鏈接到被稱為“空閑鏈表”的單向鏈表。在之后進(jìn)行分配時(shí)只要遍歷這個(gè)空閑鏈表，就可以找到分塊了。
在清除階段，程序會遍歷所有堆，進(jìn)行垃圾回收。也就是說，所花費(fèi)時(shí)間與堆大小成正比。堆越大，清楚階段所花費(fèi)的時(shí)間就會越長。
3、分配
接下來為大家講解分配的相關(guān)內(nèi)容。這里的分配是指將回收的垃圾進(jìn)行再利用。那么，分配是怎樣進(jìn)行的呢？也就是說，當(dāng)mutator 申請分塊時(shí)，怎樣才能把大小合適的分塊分配給mutator 呢？
如前文所述，我們在清除階段已經(jīng)把垃圾對象連接到空閑鏈表了。搜素空閑鏈表并尋找大小合適的分塊，這項(xiàng)操作就叫作分配。執(zhí)行分配的函數(shù) new_obj（）如下所示。
new_obj(size){
chunk = pickup_chunk(size,$free_list)
if(chunk != NULL) return chunk
else allocation_fail()
}
這里的pickup_chunk()函數(shù)用于遍歷$free_list,尋找大于等于size的分塊。如果他找到和size大小相同的分塊，則會直接返回改分塊；如果找到比size大的分塊，則會將其分割成size大小的分塊和去掉size后剩余大小的分塊，并把剩余的分塊返回給空閑鏈表。
| 分配策略 | 描述 |
|---|---|
| First-fit | 發(fā)現(xiàn)大于等于size的分塊立即返回結(jié)果 |
| Worst-fit | 找出大于等于size的最大分塊返回結(jié)果 |
| Best-fit | 找出大于等于size的最小分塊返回結(jié)果 |
4、合并
根據(jù)分配策略的不同可能會產(chǎn)生大量的小分塊。但如果他們是連續(xù)的，我們就能把所有的小分塊連在一起形成一個(gè)大分塊。這種操作就叫做合并。
sweep_phase(){
sweeping = $heap_start
while(sweeping < $heap_end)
if(sweeping.mark == true) sweeping.mark = false
else
if(sweeping == $free_list + $free_list.size)
$free_list.size += sweeping.size
else
sweeping.next = $free_list
$free_list = sweeping
sweeping += sweeping.size
}
5、優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
- 實(shí)現(xiàn)簡單
- 與保守式GC算法兼容：不會移動(dòng)對象
缺點(diǎn)
- 碎片化：使用過程中會逐漸產(chǎn)生被細(xì)化的分塊，不久后就會導(dǎo)致無數(shù)的小分塊散布在堆的各處。眾所周知，Windows的文件系統(tǒng)也會產(chǎn)生這種現(xiàn)象。
- 分配速度底下：因?yàn)榉謮K不是連續(xù)的，每次分配都必須遍歷空閑鏈表，找到足夠大的分塊。最糟糕的情況就是每次進(jìn)行分配都得把空閑鏈表遍歷到最后。下面將要介紹的多個(gè)空閑鏈表和BiBOP法都是為了能在標(biāo)記清除算法中高速進(jìn)行分配而想出的方法。
- 與寫時(shí)復(fù)制技術(shù)不兼容：即使沒有重寫對象，GC也會設(shè)置所有活動(dòng)對象的標(biāo)志位，這樣就會頻繁發(fā)生本不應(yīng)該發(fā)生的復(fù)制，壓迫到內(nèi)存空間。
寫時(shí)復(fù)制技術(shù)（copy-on-write）
在Linux等眾多UNIX操作系統(tǒng)的虛擬存儲中用的的高速化方法。比如：在Linux中復(fù)制進(jìn)程，也就是使用fork函數(shù)時(shí)，大部分內(nèi)存空間都不會被復(fù)制。只是復(fù)制進(jìn)程，就復(fù)制了所有內(nèi)存空間不太實(shí)際。因此寫時(shí)復(fù)制技術(shù)只是裝作復(fù)制了內(nèi)存空間，實(shí)際上是將內(nèi)存空間共享了。
在各個(gè)進(jìn)程中訪問數(shù)據(jù)時(shí)，能夠訪問共享內(nèi)存就沒什么問題了。
然而，當(dāng)我們對共享內(nèi)存空間進(jìn)行寫入時(shí)，不能重寫共享內(nèi)存。因?yàn)閺钠渌绦蛟L問時(shí)，會發(fā)生數(shù)據(jù)不一致的情況。在重寫時(shí)，要復(fù)制自己私有空間的數(shù)據(jù)，對這個(gè)私有空間進(jìn)行重寫。復(fù)制后只訪問這個(gè)私有空間，不訪問貢獻(xiàn)內(nèi)存。像這樣，因?yàn)檫@門技術(shù)是在寫入時(shí)進(jìn)行復(fù)制的，所以才稱為寫時(shí)復(fù)制技術(shù)。
6、多個(gè)空閑鏈表
之前的標(biāo)記清除算法，我們只用到了一個(gè)空閑鏈表，在這個(gè)空閑鏈表中，對大的分塊和小的分塊進(jìn)行了同樣的處理，但這樣一來，每次分配的時(shí)候都要遍歷一次空閑鏈表來尋找合適大小的空閑鏈表。
因此，我們就利用分塊大小不同的空閑鏈表，來分配不同的分塊。
7、BiBOP法
Big Bag Of Page:將大小相近的對象整理成固定大小的塊進(jìn)行管理的做法。
我們把堆分割成固定大小的塊，讓每個(gè)塊只能配置同樣大小的對象。
BiBOP法原本是為了消除碎片化，提高堆效率而采用的方法，但像上面這樣，在多個(gè)塊中分散殘留著同樣大小的對象，反而會降低堆的使用效率。
8、位圖標(biāo)記
在單純的標(biāo)記清除法中，用于標(biāo)記的位是被分配到各個(gè)對象的頭中的，也就是說，算法是把對象和頭一并處理的。所以這和寫時(shí)復(fù)制技術(shù)不兼容。
對此我們有個(gè)方法，那就是只收集各個(gè)對象的標(biāo)志位并表格化，不和對象一起管理，在標(biāo)記的時(shí)候不在對象的頭里置位，而是在這個(gè)表格中的特定場所置位。像這樣集合了用于標(biāo)記的位的表哥稱為“位圖表格”，利用這個(gè)表格進(jìn)行標(biāo)記的行為稱為“位圖標(biāo)記”
這樣做的優(yōu)點(diǎn)就是與寫時(shí)復(fù)制技術(shù)相兼容，不會產(chǎn)生無謂的復(fù)制。并且清除起來也更加高效。文章來源：http://www.zghlxwxcb.cn/news/detail-689990.html
9、延遲清除法
之前我們提到過，清除操作所花費(fèi)的時(shí)間與堆大小成正比。也就是說堆越大，清除所花費(fèi)的時(shí)間就越長。結(jié)果就會妨礙到mutator的處理。
延遲清除法，就是在標(biāo)記操作結(jié)束后，不一并進(jìn)行清除操作，而是延遲，來防止mutator長時(shí)間的暫停。
因?yàn)檠舆t清除法，不是一下遍歷整個(gè)堆，他只在分配時(shí)執(zhí)行必要的便利，所以可以壓縮因清除操作導(dǎo)致的mutator的暫停時(shí)間。文章來源地址http://www.zghlxwxcb.cn/news/detail-689990.html
到了這里，關(guān)于垃圾回收 -標(biāo)記清除算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
