前言
半?yún)^(qū)復(fù)制算法的目的也是為了更好的緩解內(nèi)存碎片問題庸娱。對比于標(biāo)記-壓縮算法, 它不需要遍歷堆內(nèi)存那么多次，節(jié)約了時間谐算，但是它也帶來了一個主要的缺點(diǎn)臣樱，那就是相比于標(biāo)記-清除和標(biāo)記-壓縮垃圾回收器，它的可用堆內(nèi)存減少了一半。同時對于大對象飘蚯，復(fù)制比標(biāo)記的代價更大暴凑。所以半?yún)^(qū)復(fù)制算法更一般適合回收小的凯傲，存活期短的對象。
三色抽象法
在我們深入半?yún)^(qū)復(fù)制算法原理前，我們需要了解下什么是三色抽象法缘厢。對于一個對象伊者，垃圾收集器可以將其標(biāo)記為灰色，黑色和白色中的一種多律，每種顏色代表不同的含義相味，
- 灰色 - 表示垃圾收集器已經(jīng)訪問過該對象，但是還沒有訪問過它的所有孩子節(jié)點(diǎn)。
- 黑色 - 表示該對象以及它的所有孩子節(jié)點(diǎn)都已經(jīng)被垃圾收集器訪問過了。
- 白色 - 表示該對象從來沒有被垃圾收集器訪問過，這就是非可達(dá)對象带族。
三色抽象法也可以用在標(biāo)記-清除算法和標(biāo)記-壓縮算法跋理。當(dāng)垃圾收集結(jié)束后，可達(dá)對象都被標(biāo)記為黑色，非可達(dá)對象都被標(biāo)記為白色，不會有灰色對象存在浦夷。在半?yún)^(qū)復(fù)制算法里懈息，我們也采用了三色抽象法來標(biāo)記對象姑宽。
算法原理
之所以叫半?yún)^(qū)復(fù)制，是因為它將堆內(nèi)存對半分為兩個半?yún)^(qū)，只用其中一個半?yún)^(qū)來進(jìn)行對象內(nèi)存的分配，如果在這個半?yún)^(qū)內(nèi)存不夠給新的對象分配了，那么就開始進(jìn)行垃圾收集舆声，將這個半?yún)^(qū)中的所有可達(dá)對象都拷貝到另外一個半?yún)^(qū)中去，然后繼續(xù)在另外那個半?yún)^(qū)進(jìn)行新對象的內(nèi)存分配。半?yún)^(qū)復(fù)制算法中比較常見是Cheney算法。
下面是復(fù)制算法的偽代碼：
atomic collect():
flip()
scan <- free
for each fld in Roots
process(fld)
while not isEmpty(worklist)
ref <- remove(worklist)
scan(ref)
flip():
fromspace, tospace <- tospace, fromspace
top <- tospace+extent //界定堆內(nèi)存的邊界
free <- tospace
scan(ref):
for each fld in Pointers(ref)
process(fld)
process(fld):
fromRef <- *fld
if fromRef != null
*fld <- forward(fromRef) //將可達(dá)對象復(fù)制后的地址寫到原對象的位置上奥邮，當(dāng)作遷移地址
forward(fromRef):
toRef <- forwardingAddress(fromRef) //讀取該位置上對象的遷移地址
if toRef == null //如果該位置上的對象沒有遷移地址蘸朋，那就說明它還沒有被復(fù)制，需要復(fù)制到tospace中去
toRef <- copy(fromRef)
return toRef
copy(fromRef):
toRef <- free
free <- free + size(fromRef)
move(fromRef, toRef) //從fromRef位置復(fù)制對象到toRef位置上
forwardingAddress(fromRef) <- toRef //將地址toRef寫到fromRef位置上的對象中去
add(worklist, toRef)
return toRef
remove(worklist):
ref <- scan
scan <- scan + size(scan)
return ref
實際上半?yún)^(qū)復(fù)制算法的實現(xiàn)跟標(biāo)記-壓縮算法的實現(xiàn)差不多， 都是采用的深度遍歷算法贞奋，理解該算法的關(guān)鍵點(diǎn)是，怎么計算可達(dá)對象的遷移地址(forwardingAddress) - 看copy(fromRef)方法的實現(xiàn)癌蚁， 以及怎么更新對象間的引用關(guān)系。
半?yún)^(qū)復(fù)制算法的過程如下：
我們假設(shè)A,B對象是根對象复唤。
- 首先先交換左右半?yún)^(qū)(ToSpace, FromSpace), 同時設(shè)置free指針和top指針。
- 遍歷處理根對象A,B穆桂。先將A對象復(fù)制到free指針指向的位置，同時將A對象復(fù)制后的地址(遷移地址)寫到原先A對象所在的位置萤衰，圖中虛線的箭頭表示∩崛牛可以看到A對象已經(jīng)被collector訪問過了，但是還沒有訪問其孩子節(jié)點(diǎn)阱表，所以將其標(biāo)為了灰色爱致。緊接著scan，free指針繼續(xù)向前移動忘朝。
- 由于是深度遍歷算法局嘁，緊接collector會先遍歷處理A對象所引用的對象C晌畅，當(dāng)發(fā)現(xiàn)對象C沒有遷移地址時剩岳，說明它還沒有被復(fù)制，由于它又是可達(dá)對象，所以接著collector會將它復(fù)制到當(dāng)前free指針指向的位置潮峦，即對象A后面嘱腥。對象C復(fù)制完后，會用其復(fù)制后的地址來更新A原先對C的引用拘悦，同時也寫到原先C對象所在的地址上齿兔。
- 接著collector會處理對象C的孩子節(jié)點(diǎn)（深度遍歷算法），由于對象C沒有引用任何對象础米，于是對象C的處理結(jié)束分苇，將其標(biāo)記為黑色。然后collector接著處理A對象的另外一個孩子節(jié)點(diǎn)E對象屁桑，處理方式跟處理對象C一致医寿。
- 對象E也沒有孩子節(jié)點(diǎn)，collector也將其標(biāo)識為黑色掏颊。
- 到目前為此糟红，A對象也全部處理結(jié)束了，于是collector將其標(biāo)識為黑色乌叶，然后接著去處理對象B盆偿。當(dāng)復(fù)制B對象結(jié)束后，發(fā)現(xiàn)B對象所引用的對象C有遷移地址准浴，于是就更新其對對象C的引用事扭，使其指向FromSpace半?yún)^(qū)中對象C的遷移地址 - 即C對象復(fù)制后所在ToSpace的地址。這個情況下就不需要再次復(fù)制對象C了乐横。
- 當(dāng)所有的可達(dá)對象都從FromSpace半?yún)^(qū)復(fù)制到ToSpace半?yún)^(qū)后求橄，垃圾收集結(jié)束今野。新對象的內(nèi)存分配從free指針指向的位置開始進(jìn)行分配。
其實罐农，從垃圾收集過程中對象的移動順序來看条霜，collector將相鄰的對象都復(fù)制在相近的位置上，它屬于前面我們在標(biāo)記-壓縮算法里所說的“線性順序”涵亏。
