垃圾回收 - 复制算法

GC复制算法是Marvin L.Minsky在1963年研究出来的算法。说简单点，就是只把某个空间的活动对象复制到其它空间，把原空间里的所有对象都回收掉。这是一个大胆的想法。在此，我们将复制活动对象的原空间称为From空间，将粘贴活动对象的新空间称为To空间。

1、什么是复制算法

GC复制算法是利用From空间进行分配的。当From空间被完全占满时，GC会将活动对象全部复制到To空间。当复制完成后，该算法会把From空间和To空间互换。GC也就结束了。From空间和To空间大小必须一致。这是为了保证能把From空间中所有活动对象都收纳到To空间里。

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

2、Copy函数

copy（）函数将作为参数给出的对象复制，再递归复制其子对象。

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函数

跟标记清除算法不同，复制算法的分配过程非常简单

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、执行过程

4.1初始状态
为了给GC做准备，这里事先将$free指针指向To空间的开头

4.2 B被复制后

4.3 A被复制后

接下来就是按照同样步骤复制G及其子对象E
4.4 GC结束后

5、优缺点

5.1优点

1. 优秀的吞吐量
2. 可实现高速分配
3. 不会发生碎片化
4. 与缓存兼容

5.2缺点

1. 堆使用效率低下
2. 不兼容保守式GC算法
3. 递归调用函数

6、Cheney的复制算法

C.J.Cheney于1970年研究出GC算法，相比Fenichel和Yochelson的GC复制算法，Cheney的算法不是简单递归的，而是迭代地进行复制。

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函数

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 执行过程
6.2.1初始状态多引入了一个scan

6.2.2在cheney算法中，首先复制所有从根直接引用的对象

6.2.3 然后在所有b和g

6.3 优缺点
优点：因为该算法是迭代的，所以他可以抑制调用函数额外负担和栈的消耗。特别是拿堆用作队列，省去了用于搜索的内存空间这一点，实在是令人赞叹。
缺点：有引用关系的对象并不相邻，不兼容缓存。当然这是因为他是局域广度优先遍历，我们可以通过修改其搜索算法，利用深度优先遍历来解决这个问题。

7、多空间复制算法

GC复制算法最大的缺点就是只能利用半个堆，这是因为该算法将整个堆分成了两半，每次都要腾出一半来。
多空间复制算法就是把堆N等分，对其中2块空间执行GC复制算法，剩下的N-2块空间执行GC标记清除算法，也就是把这两种算法组合起来使用。

优点：更有效的利用了堆空间
缺点：因为只有两块空间进行了复制算法，剩下的仍然是标记清除算法，因此就会有标记清除算法的固有问题：分配耗费时间，分块碎片化等。