乐趣区

关于jvm:深入理解-JVM-垃圾回收算法-复制算法

通常来说,在整个程序的运行过程中,垃圾回收只会占用很小一部分工夫,赋值器的执行会占用更多的工夫,因而,内存调配速度的快慢将间接决定整个程序的性能。很显著,后面提到的标记 - 清理算法并不是一个很好的范例,尽管它的算法简略且实现容易,但存在很重大的内存碎片化问题,会重大影响内存的调配速度。

标记 - 整顿算法能够铲除碎片问题,而且调配速度也很快,但在垃圾回收过程中会进行屡次堆遍历,进而显著减少了回收工夫。

本文将介绍第三种根本的垃圾回收算法:半区复制算法。回收器在整个过程中通过复制的形式来进行堆整顿,从而晋升内存调配速度,且回收过程中只需对存活对象便当一次,其最大的毛病是堆的可用空间升高了一半。

复制算法是一种典型的以空间换工夫的算法。

实现原理

在复制算法中,回收器将堆空间划分为两个大小相等的半区 (semispace),别离是 起源空间 (fromspace) 指标空间(tospace)。在进行垃圾回收时,回收器将存活对象从起源空间复制到指标空间,复制完结后,所有存活对象严密排布在指标空间一端,最初将起源空间和指标空间调换。半区复制算法的概要如下图所示。

接下来看下代码如何实现?次要流程很简略,有一个 free 指针指向 TOSPACE 的终点,从根节点开始遍历,将根节点及其援用的子节点全副复制到 TOSPACE,每复制一个对象,就把 free 指针向后挪动相应大小的地位,最初替换 FROMSPACE 和 TOSPACE,大抵可用如下代码形容:

collect() {
// 变量后面加 * 示意指针
// free 指向 TOSPACE 半区的起始地位
*free = *to_start;
for(root in Roots) {copy(*free, root);
}
// 替换 FROMSPACE 和 TOSPACE
swap(*from_start,*to_start);
}
复制代码

外围函数 copy 的实现如下所示:

copy(*free,obj) {
// 查看 obj 是否曾经复制实现
// 这里的 tag 仅是一个逻辑上的域
if(obj.tag != COPIED) {
// 将 obj 真正的复制到 free 指向的空间
copy_data(*free,obj);
// 给 obj.tag 贴上 COPIED 这个标签
// 即便有多个指向 obj 的指针,obj 也不会被复制屡次
obj.tag = COPIED;
// 复制实现后把对象的新地址寄存在老对象的 forwarding 域中
obj.forwarding = *free;
// 依照 obj 的长度将 free 指针向前挪动
*free += obj.size;

// 递归调用 copy 函数复制其关联的子对象
for(child ingetRefNode(obj.forwarding)){*child = copy(*free,child);
}
}
returnobj.forwarding;
}
复制代码

在这段代码中须要留神两个问题,其一是 tag=COPIED 只是一个逻辑上的概念,用来辨别对象是否曾经实现复制,以确保即便这个对象被屡次援用,也仅会复制一次;另外一个问题则是 forwarding 域,forwarding 指针 在后面曾经屡次提到过,次要是用来保留对象挪动后的新地址,比方在标记整顿算法中,对象挪动后须要遍历更新对象的援用关系,就须要应用 forwarding 指针 来查找其挪动后的地址,而在复制算法中,其作用相似,如果遇到已复制实现的对象,间接通过 forwarding 域把对象的新地址返回即可。整个复制算法的根本致流程如下图所示。

接下来用一个具体的示例看看复制算法的大抵流程。堆中对象的关系如下图所示,其中 free 指针指向 TOSPACE 的终点地位。

首先,从根节点登程,找到它间接援用的对象 B 和 E,其中对象 B 首先被复制到 TOSPACE。B 被复制后的堆的关系如下图所示。

这里将 B 被复制后生成的对象成为 B ’,而原来的对象 B 中 tag 域曾经打上复制实现的标签,而 forwarding 指针 也寄存着 B ’ 的地址。

对象 B 复制实现后,它援用的对象 A 还在 FROMSPACE 里,接下来就会把对象 A 复制到 TOSPACE 中。

接下来复制从根援用的对象 E,以及其援用对象 B,不过因为 B 曾经复制实现,所以只须要把从 E 指向 B 的指针换成指向 B ’ 的指针即可。

最初只有把 FROMSPACE 和 TOSPACE 调换,GC 就完结了。GC 完结时堆的状态如下图所示。

在这儿,程序的搜寻程序是按 B、A、E 的顺序搜索对象的,即以深度优先算法来搜寻的。

算法评估

复制算法次要有如下劣势:

  • 吞吐量高:整个 GC 算法只搜寻并复制存活对象,尤其是堆越大,差距越显著,毕竟它耗费的工夫只是与流动对象数量成正比。
  • 可实现高速调配:因为 GC 实现后闲暇空间是一个间断的内存块,在内存调配时,只有申请空间小于闲暇内存块,只须要挪动 free 指针即可。相较于标记 - 清理算法应用闲暇链表的调配形式,复制算法显著快得多,毕竟要在闲暇链表中找到适合大小的内存怎么都得遍历这个链表。
  • 无碎片:没啥好说的。
  • 与缓存兼容:能够回顾一下后面说的局部性原理,因为所有存活对象都严密的排布在内存里,十分有利于 CPU 的高速缓存。

相较于后面的两种 GC 算法,其劣势次要有亮点:

  • 堆空间利用率低:复制算法把堆一分为二,只有一半能被应用,内存利用率极低,这也是复制算法的最大缺点。
  • 递归调用函数:复制某个对象时要递归复制它援用的对象,相较于迭代算法,递归的效率更低,而且有栈空间溢出的危险。

Cheney 复制算法

Cheney 算法是用来解决如何遍历援用关系图并将存活对象挪动到 TOSPACE 的算法,它应用迭代算法来代替递归。

还是以一个简略的例子来看看 Cheney 算法的执行过程,首先还是初始状态,在后面的例子上做了一点改变,同时有两个指针指向 TOSPACE 的终点地位。

首先复制所有从根节点间接援用的对象,在这儿就是复制 B 和 E。

这时,与根节点间接援用的对象都曾经复制结束,scan 依然指向 TOSPACE 的终点,free 从终点向前挪动了 B 和 E 个长度。

接下来,scan 和 free 持续向前挪动,scan 的每次挪动都意味着对已实现复制对象的搜寻,而 free 的向前挪动则意味着新的对象复制实现。

还是以例子来说,在 B 和 E 实现复制当前,接着开始复制与 B 关联的所有对象,这里是 A 和 C。

在复制 A 和 C 时,free 向前挪动,等 A 和 C 复制实现当前,scan 向前挪动 B 个长度到 E。接着,持续扫描 E 援用的对象 B,发现 B 曾经实现复制,则 scan 向前挪动 E 个长度,free 放弃不动。因为对象 A 没有援用任何对象,还是 scan 向前挪动 A 个长度,free 放弃不动。

接下来,持续复制 C 的关联对象 D,实现 D 的复制当前,发现 scan 和 free 相遇了,则完结复制。

最初依然是 FROMSPACE 和 TOSPACE 调换,GC 完结。

代码实现只须要在之前的代码上稍做批改,即可:

collect() {
// free 指向 TOSPACE 半区的起始地位
*scan = *free = *to_start;
// 复制根节点间接援用的对象
for(root in Roots) {copy(*free, root);
}
// scan 开始向前挪动
// 首先获取 scan 地位处对象所援用的对象
// 所有援用对象复制实现后,向前挪动 scan
while(*scan != *free) {for(child ingetRefObject(scan)){copy(*free, child);
}
*scan += scan.size;
}
swap(*from_start,*to_start);
}
复制代码

copy 函数也不再蕴含递归调用,仅仅是实现复制性能:

copy(*free,obj) {if(!is_pointer_to_heap(obj.forwarding,*to_start)) {
// 将 obj 真正的复制到 free 指向的空间
copy_data(*free,obj);
// 复制实现后把对象的新地址寄存在老对象的 forwarding 域中
obj.forwarding = *free;
// 依照 obj 的长度将 free 指针向前挪动
*free += obj.size;
}
returnobj.forwarding;
}
复制代码

对于 is_pointer_to_heap(obj.forwarding,*to_start),如果 obj.forwarding 是指向 TOSPACE 的指针,则返回 TRUE,否则返回 FALSE。这里没有应用 tag 来辨别对象是否曾经实现复制,而是直接判断 obj.forwarding 指针,如果 obj.forwarding 不是指针或者没有指向 TOSPACE,那么就认为它没有实现复制,否则就阐明曾经实现复制。

通过代码能够看出,Cheney 算法采纳的是广度优先算法。相熟算法的同学可能晓得,广度优先搜索算法是须要一个先进先出的队列来辅助的,但这儿并没有队列。实际上 scan 和 free 之间的堆变成了一个队列,scan 右边是曾经搜寻完的对象,左边是待搜寻对象。free 向前挪动,队列就会追加对象,scan 向前挪动,都会有对象被取出并进行搜寻,这样一来,就满足了先入先出队列的条件。

上面是一个广度优先遍历算法的典型实现,大家能够用作比照,加深了解。

voidBFS(List<Node> roots){
// 曾经被拜访过的元素
List<Node> visited =newArrayList<Node>();
// 用队列寄存顺次要遍历的元素
Queue<GraphNode> queue =newLinkedList<GraphNode>();

for(node in roots) {visited.add(node);
process(node);
queue.offer(node);
}

while(!queue.isEmpty()) {Node currentNode = queue.poll();
if(!visited.contains(currNode)) {visited.add(currentNode);
process(node);
for(child ingetChildren(node)){queue.offer(node);
}
}
}
}
复制代码

比照之前的算法,Cheney 算法的长处是应用迭代算法代替递归,防止了栈的耗费和可能的栈溢出危险,特地是拿堆空间用作队列来实现广度优先遍历,十分奇妙。而毛病则是,互相援用的对象并不是相邻的,就没方法充分利用缓存。留神,这里不是说,Cheney 算法无奈兼容缓存,只是相较于前一种算法来说,没有那么好而已。

最初

复制算法还有挺多变种的,这里没方法一一列举,更多内容能够浏览参考资料中的两本书籍。(也能够关注公众号【Java 斗帝】收费获取 pdf 版)

垃圾回收算法手册:主动内存治理的艺术

垃圾回收的算法与实现

复制算法的最大缺点就是堆空间利用率低,因而大多数场景下,都是与其余算法搭配应用;并且咱们也不是真的会把堆空间一分为二,而是依据理论状况,正当的划分。就比方,能够把堆空间分成 10 份,拿出 2 份空间别离作为 From 空间和 To 空间,用来执行复制算法,而剩下的 8 分则搭配应用标记 - 清理算法。

是不是又想到了 JVM 的新生代和老年代的区域划分,嗯,起因就是咱们所讲的内容。

看完三件事❤️

如果你感觉这篇内容对你还蛮有帮忙,我想邀请你帮我三个小忙:

  1. 点赞,转发,有你们的『点赞和评论』,才是我发明的能源。
  2. 关注公众号『Java 斗帝』,不定期分享原创常识。
  3. 同时能够期待后续文章 ing????
退出移动版