垃圾回收 - 复制算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了垃圾回收 - 复制算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

1、什么是复制算法

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

copying(){
	$free = $to_start
	for(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 = COPIED
		obj.forwarding = $free
		$free += obj.size
		for(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 = $free
	obj.size = size
	&free += size
	return obj;
}

4、执行过程

4.1初始状态
为了给GC做准备，这里事先将$free指针指向To空间的开头
垃圾回收 - 复制算法,垃圾回收与内存泄漏,算法,java,jvm

4.2 B被复制后
垃圾回收 - 复制算法,垃圾回收与内存泄漏,算法,java,jvm

4.3 A被复制后
垃圾回收 - 复制算法,垃圾回收与内存泄漏,算法,java,jvm

接下来就是按照同样步骤复制G及其子对象E
4.4 GC结束后
垃圾回收 - 复制算法,垃圾回收与内存泄漏,算法,java,jvm

5、优缺点

5.1优点

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

5.2缺点

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

6、Cheney的复制算法

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

copying(){
	scan = $free = $to_start
	for(r:$roots)
		*r = copy(*r)
		
	while(scan != $free)
		for(child : children(scan))
			*child = copy(*child)
		scan += scan.size
	
	swap($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.size
	return obj.forwarding
}

6.2 执行过程
6.2.1初始状态多引入了一个scan
垃圾回收 - 复制算法,垃圾回收与内存泄漏,算法,java,jvm
6.2.2在cheney算法中，首先复制所有从根直接引用的对象

6.2.3 然后在所有b和g

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