Java JVM 3:垃圾收集算法 - 复制算法(伪代码实现与深入分析)

时间:2021-01-14 15:50:57

复制算法主要用于新生代中,例如作用于新生代的垃圾处理器:Serial,ParNew,Parallel Scavenge 垃圾收集器,主要因为新生代的对象的存活时间比较短,所以采用这个算法折衷起来是比较好的。

复制算法原理

主要把 内存等分成A,B两块,每次只使用其中的一块,那么,每次垃圾回收的时候,就把使用中的半块(例如A)的存活的对象移动到另外的半块中,然后,直接清除另外的半块(B块)。

这样马上就会有一个问题 ==》岂不是太浪费内存了?

对,等分会非常浪费,所以说现在 JVM 的新生代不是等分的,而是 8:1:1 的比例,每次使用 Eden 区域和其中 1 块 Survivor 区域,垃圾回收的时候,那么就把存活的对象全部移动到另外 1 块 Survivor 区域。

(Ps:如果另外一块 Survivor 区域不够怎么办。这里老年代会进行一个分配担保。(简单来说就是不够了对象直接进入老年代))

那么,另外可以看出,一个优点就是实现简单,而且没有内存碎片的问题(之后提到的标记清除法(老年代主要的垃圾算法)就会有这个问题)

算法的伪代码实现

《深入理解 Java 虚拟机》这部分的内容没有涉及到代码,参考 《垃圾回收的算法与实现》一书,再深入理解一下这个算法:

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

首先可以得到所有的 GC roots 对象,也就是所有的根对象,然后对每一个根对象进行复制(此时的复制包括了该根对象的所有子对象)。

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
}

copy_data($free,obj,obj,size) 表示把对象复制到另外的一个区域。

这里如果深入思考的话可能会有个疑惑,就是 比如 A -> B (A引用B),假设 A,B移动到另外的区域后是 A’ 和 B’,怎么保证是 A’ -> B’(A’ 引用 B’) ,而不会混乱呢(比如 A’ -> B )。

解决办法就是利用对象的一个属性 forwarding。这个属性就记录了 A移动到另外一个区域,变成 A’ 后的位置是什么,可以看到代码 obj.forwarding = $free。

这里再顺一遍上面的代码,假设只有 A -> B(A 引用 B,A是 GC roots)。那么:

调用 copying() 开始复制。
A 对象先复制。假设 A 复制到另外 1 块区域的地址是 A’,此时会记录下 A.forwarding = A’,此时要注意一点:A’ 引用的对象还是 B,因为 B’ 还没有呢。
然后复制 A 的子对象 B,同理。最后 B 对象返回 return obj.forwarding 也就是 B 的新地址 B’。
此时又回到 A 流程的 *child = copy(*child) ,那么 A’ -> B’ 就这样关联上了。
所以说,具体的整个复制流程就是这样子的。

优缺点分析

耗费的时间主要在哪里

复制的时候需要遍历 GC roots,找到所有的活动对象。
清除的时候需要遍历整个堆
这个其实还是比较高效的。

不会发生碎片化

不会发生碎片化意味着什么,意味着分配内存的时候不需要遍历空闲链表。对于某一块内存,系统怎么知道这个内存有多大,能不能分配给一个对象,其实是在空闲链表里有维护。那么,分配对象的时候就会遍历这个空闲链表,比如说,某某某某区域有一个内存,够大,可以分配,好,那么就用这个内存了。

缺点 - 浪费了一定的内存

缺点 - 递归调用

递归调用会有栈溢出风险。