GC復(fù)制算法是Marvin L.Minsky在1963年研究出來(lái)的算法。說(shuō)簡(jiǎn)單點(diǎn)，就是只把某個(gè)空間的活動(dòng)對(duì)象復(fù)制到其它空間，把原空間里的所有對(duì)象都回收掉。這是一個(gè)大膽的想法。在此，我們將復(fù)制活動(dòng)對(duì)象的原空間稱為From空間，將粘貼活動(dòng)對(duì)象的新空間稱為To空間。

1、什么是復(fù)制算法

GC復(fù)制算法是利用From空間進(jìn)行分配的。當(dāng)From空間被完全占滿時(shí)，GC會(huì)將活動(dòng)對(duì)象全部復(fù)制到To空間。當(dāng)復(fù)制完成后，該算法會(huì)把From空間和To空間互換。GC也就結(jié)束了。From空間和To空間大小必須一致。這是為了保證能把From空間中所有活動(dòng)對(duì)象都收納到To空間里。

copying(){$free = $to_startfor(r:$roots)*r = copy(*r)swap($from_start, &to_start)
}

2、Copy函數(shù)

copy（）函數(shù)將作為參數(shù)給出的對(duì)象復(fù)制，再遞歸復(fù)制其子對(duì)象。

copy（obj）{if（obj.tag != COPIED）copy_data($free,obj,obj.size)obj.tag = COPIEDobj.forwarding = $free$free += obj.sizefor(child:children(obj.forwarding))*child = copy(*child)return obj.forwarding
}			

3、new_obj函數(shù)

跟標(biāo)記清除算法不同，復(fù)制算法的分配過(guò)程非常簡(jiǎn)單

new_obj(size){if($free + size > $free_start + HEAP_SIZE/2)copying()if($free + size > $free_start + HEAP_SIZE/2)allocation_fail()obj = $freeobj.size = size&free += sizereturn obj;
}

4、執(zhí)行過(guò)程

4.1初始狀態(tài)
為了給GC做準(zhǔn)備，這里事先將$free指針指向To空間的開(kāi)頭

4.2 B被復(fù)制后

4.3 A被復(fù)制后

接下來(lái)就是按照同樣步驟復(fù)制G及其子對(duì)象E
4.4 GC結(jié)束后

5、優(yōu)缺點(diǎn)

5.1優(yōu)點(diǎn)

1. 優(yōu)秀的吞吐量
2. 可實(shí)現(xiàn)高速分配
3. 不會(huì)發(fā)生碎片化
4. 與緩存兼容

5.2缺點(diǎn)

1. 堆使用效率低下
2. 不兼容保守式GC算法
3. 遞歸調(diào)用函數(shù)

6、Cheney的復(fù)制算法

C.J.Cheney于1970年研究出GC算法，相比Fenichel和Yochelson的GC復(fù)制算法，Cheney的算法不是簡(jiǎn)單遞歸的，而是迭代地進(jìn)行復(fù)制。

copying(){scan = $free = $to_startfor(r:$roots)*r = copy(*r)while(scan != $free)for(child : children(scan))*child = copy(*child)scan += scan.sizeswap($from_start, &to_start)
}

6.1 copy函數(shù)

copy（obj）{if(is_pointer_to_heap(obj.forwarding,$to_start) == FALSE)copy_data($free,obj,obj.size)obj.forwarding = $free$free += obj.sizereturn obj.forwarding
}			

6.2 執(zhí)行過(guò)程
6.2.1初始狀態(tài)多引入了一個(gè)scan

6.2.2在cheney算法中，首先復(fù)制所有從根直接引用的對(duì)象

6.2.3 然后在所有b和g

6.3 優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：因?yàn)樵撍惴ㄊ堑?#xff0c;所以他可以抑制調(diào)用函數(shù)額外負(fù)擔(dān)和棧的消耗。特別是拿堆用作隊(duì)列，省去了用于搜索的內(nèi)存空間這一點(diǎn)，實(shí)在是令人贊嘆。
缺點(diǎn)：有引用關(guān)系的對(duì)象并不相鄰，不兼容緩存。當(dāng)然這是因?yàn)樗蔷钟驈V度優(yōu)先遍歷，我們可以通過(guò)修改其搜索算法，利用深度優(yōu)先遍歷來(lái)解決這個(gè)問(wèn)題。

7、多空間復(fù)制算法

GC復(fù)制算法最大的缺點(diǎn)就是只能利用半個(gè)堆，這是因?yàn)樵撍惴▽⒄麄€(gè)堆分成了兩半，每次都要騰出一半來(lái)。
多空間復(fù)制算法就是把堆N等分，對(duì)其中2塊空間執(zhí)行GC復(fù)制算法，剩下的N-2塊空間執(zhí)行GC標(biāo)記清除算法，也就是把這兩種算法組合起來(lái)使用。

優(yōu)點(diǎn)：更有效的利用了堆空間
缺點(diǎn)：因?yàn)橹挥袃蓧K空間進(jìn)行了復(fù)制算法，剩下的仍然是標(biāo)記清除算法，因此就會(huì)有標(biāo)記清除算法的固有問(wèn)題：分配耗費(fèi)時(shí)間，分塊碎片化等。