写点什么

深入理解 JVM 垃圾回收算法 - 复制算法

发布于: 2020 年 10 月 19 日

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


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

实现原理

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


接下来看下代码如何实现?主要流程很简单,有一个 free 指针指向 TOSPACE 的起点,从根节点开始遍历,将根节点及其引用的子节点全部复制到 TOSPACE,每复制一个对象,就把 free 指针向后移动相应大小的位置,最后交换 FROMSPACE 和 TOSPACE,大致可用如下代码描述:


核心函数 copy 的实现如下所示:


在这段代码中需要注意两个问题,其一是 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 的起点位置。


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


还是以例子来说,在 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 相遇了,则结束复制。



collect() {// free指向TOSPACE半区的起始位置*scan = *free = *to_start;// 复制根节点直接引用的对象for(root in Roots) {copy(*free, root);}// scan开始向前移动// 首先获取scan位置处对象所引用的对象// 所有引用对象复制完成后,向前移动scanwhile(*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🚀


用户头像

还未添加个人签名 2020.09.07 加入

还未添加个人简介

评论

发布
暂无评论
深入理解 JVM 垃圾回收算法 - 复制算法