前言
垃圾自動回收機制的出現(xiàn)使編程更加的簡單庶橱，使得我們不需要再去考慮內(nèi)存分配和釋放的問題睁蕾，而是更加的專注在我們產(chǎn)品功能的實現(xiàn)上蛛倦。但是我們還是需要花時間去了解下垃圾收集機制是怎么工作的年柠，以便后面能夠更好的進行我們應(yīng)用的性能調(diào)優(yōu)等扰楼。
目前最基本的垃圾收集算法有四種,標記-清除算法(mark-sweep),標記-壓縮算法(mark-compact),復(fù)制算法(copying)以及引用計數(shù)算法(reference counting).而現(xiàn)代流行的垃圾收集算法一般是由這四種中的其中幾種算法相互組合而成，比如說划鸽，對堆(heap)的一部分采用標記-清除算法输莺，對堆(heap)的另外一部分則采用復(fù)制算法等等戚哎。今天我們主要來看下標記-清除算法的原理。
基本概念
在了解標記-清除算法前嫂用，我們先要了解幾個基本概念型凳。
首先是mutator和collector，這兩個名詞經(jīng)常在垃圾收集算法中出現(xiàn)嘱函，collector指的就是垃圾收集器啰脚，而mutator是指除了垃圾收集器之外的部分，比如說我們應(yīng)用程序本身实夹。mutator的職責(zé)一般是NEW(分配內(nèi)存),READ(從內(nèi)存中讀取內(nèi)容),WRITE(將內(nèi)容寫入內(nèi)存)橄浓，而collector則就是回收不再使用的內(nèi)存來供mutator進行NEW操作的使用。
第二個基本概念是關(guān)于mutator roots(mutator根對象),mutator根對象一般指的是分配在堆內(nèi)存之外亮航，可以直接被mutator直接訪問到的對象荸实，一般是指靜態(tài)/全局變量以及Thread-Local變量(在Java中，存儲在java.lang.ThreadLocal中的變量和分配在棧上的變量 - 方法內(nèi)部的臨時變量等都屬于此類).
第三個基本概念是關(guān)于可達對象的定義缴淋，從mutator根對象開始進行遍歷准给，可以被訪問到的對象都稱為是可達對象。這些對象也是mutator(你的應(yīng)用程序)正在使用的對象重抖。
算法原理
顧名思義露氮，標記-清除算法分為兩個階段，標記(mark)和清除(sweep).
在標記階段钟沛，collector從mutator根對象開始進行遍歷畔规，對從mutator根對象可以訪問到的對象都打上一個標識，一般是在對象的header中恨统，將其記錄為可達對象叁扫。
而在清除階段，collector對堆內(nèi)存(heap memory)從頭到尾進行線性的遍歷畜埋，如果發(fā)現(xiàn)某個對象沒有標記為可達對象-通過讀取對象的header信息莫绣，則就將其回收。
從上圖我們可以看到悠鞍，在Mark階段对室，從根對象1可以訪問到B對象，從B對象又可以訪問到E對象咖祭，所以B,E對象都是可達的掩宜。同理，F(xiàn),G,J,K也都是可達對象心肪。到了Sweep階段锭亏，所有非可達對象都會被collector回收纠吴。同時硬鞍，Collector在進行標記和清除階段時會將整個應(yīng)用程序暫停(mutator)，等待標記清除結(jié)束后才會恢復(fù)應(yīng)用程序的運行，這也是Stop-The-World這個單詞的來歷固该。
接著我們先看下一般垃圾收集動作是怎么被觸發(fā)的锅减，下面是mutator進行NEW操作的偽代碼：
New():
ref <- allocate() //分配新的內(nèi)存到ref指針
if ref == null
collect() //內(nèi)存不足，則觸發(fā)垃圾收集
ref <- allocate()
if ref == null
throw "Out of Memory" //垃圾收集后仍然內(nèi)存不足伐坏，則拋出Out of Memory錯誤
return ref
atomic collect():
markFromRoots()
sweep(HeapStart,HeapEnd)
而下面是對應(yīng)的mark算法:
markFromRoots():
worklist <- empty
for each fld in Roots //遍歷所有mutator根對象
ref <- *fld
if ref != null && isNotMarked(ref) //如果它是可達的而且沒有被標記的怔匣，直接標記該對象并將其加到worklist中
setMarked(ref)
add(worklist,ref)
mark()
mark():
while not isEmpty(worklist)
ref <- remove(worklist) //將worklist的最后一個元素彈出，賦值給ref
for each fld in Pointers(ref) //遍歷ref對象的所有指針域桦沉，如果其指針域(child)是可達的每瞒，直接標記其為可達對象并且將其加入worklist中
//通過這樣的方式來實現(xiàn)深度遍歷，直到將該對象下面所有可以訪問到的對象都標記為可達對象纯露。
child <- *fld
if child != null && isNotMarked(child)
setMarked(child)
add(worklist,child)
在mark階段結(jié)束后剿骨，sweep算法就比較簡單了，它就是從堆內(nèi)存起始位置開始埠褪，線性遍歷所有對象直到堆內(nèi)存末尾，如果該對象是可達對象的（在mark階段被標記過的），那就直接去除標記位（為下一次的mark做準備）顷啼，如果該對象是不可達的藕夫，直接釋放內(nèi)存。
sweep(start,end):
scan <- start
while scan < end
if isMarked(scan)
setUnMarked(scan)
else
free(scan)
scan <- nextObject(scan)
缺點
標記-清除算法的比較大的缺點就是垃圾收集后有可能會造成大量的內(nèi)存碎片渴语，像上面的圖片所示苹威，垃圾收集后內(nèi)存中存在三個內(nèi)存碎片，假設(shè)一個方格代表1個單位的內(nèi)存驾凶，如果有一個對象需要占用3個內(nèi)存單位的話屠升，那么就會導(dǎo)致Mutator一直處于暫停狀態(tài)，而Collector一直在嘗試進行垃圾收集狭郑，直到Out of Memory腹暖。
