新生代的垃圾回收:Copy GC之基本原理

据我所能查到的资料,基于复制的GC算法最早是Marvin Minsky提出来的。

这个算法的思路很简单,总的来说,就是把空间分成两部分,一个叫分配空间(Allocation Space),一个是幸存者空间(Survivor Space)。创建新的对象的时候都是在分配空间里创建。在GC的时候,把分配空间里的活动对象复制到Survivor Space,把原来的分配空间全部清空。然后把这两个空间交换,就是说Allocation Space变成下一轮的Survivor Space,现在的Survivor Space变成Allocation Space。

在有些文献中,或者实现中,allocation space也会被称为from space,survivor space也被称为to space。JVM代码中,这两套命名方式都会出现,所以搞清楚这点比较有好处。我们的文章中,为了方便后面解析JVM代码,还是使用from space和to space来指代分配空间和幸存者空间。

copy gc的想法很简单,但真要使用代码实现出来,还是有很多细节要处理的。我从最基本最原始的算法开始介绍,希望能从浅入深地把这个事情说清楚。

朴素的Copy算法

最早的,最简单的copy算法,是把程序运行的堆分成大小相同的两半,一半称为from空间,一半称为to空间。利用from空间进行分配,当空间不足以分配新的对象的时候,就会触发GC。GC会把存活的对象全部复制到to空间。当复制完成以后,会把 from 和 to 互换。

用图来表示就是这样的:

此时,from空间已经满了,A对象存活,A又引用了C和D,所以C和D也是活跃的。已经没有任何地方引用B对象了,那么B就是垃圾了。这时候,如果想再创建一个新的对象就不行了,这时就会执行GC算法,将A,C,D都拷贝到新的空间中去。

然后把原来的空间全部清空。这样,就完成了一次垃圾回收。

有几个问题要解决,第一个问题,如何判断A和B是否存活。因为C和D是被A引用的,那么,A如果是存活的,C和D就是存活的,这个相对简单一些。我们先看一下Java程序中怎么样的:

public static void foo() {
    A a = new A();
    bar();
    E e = new E();
}

public static void bar() {
    B b = new B();
}

在上面的例子中,在创建对象E的时候,已经从bar的调用中返回了。这个时候,对象a还存活于foo的调用栈里,而b已经没有任何地方会去引用它了——原来唯一的引用,bar的栈空间,已经消失了。所以b就变成了垃圾。而这个时候由于from空间不足,无法正确地创建E,所以,就会执行GC,这时候 b 做为垃圾就被回收了。

可见,如果存在一个从栈上出发到对象的引用,那么这个对象就是存活的。所以我们把栈上的这种引用称为roots。roots包含很多内容,除了栈上的引用,JNIHandle,Universe等等都会有向堆上的引用,但在我的文章里,只以栈上的引用做为roots来讲解。

Copy的实现

复制GC算法,最核心的就是如何实现复制。我用伪代码来表示:

void copy_gc() {
    for (obj in roots) {
        *obj = copy(obj);
    }
}

obj * copy(obj) {
    if (!obj.visited) {
        new_obj = to_space.allocate(obj.size);
        copy_data(new_obj, obj, size);
        obj.visited = true;
        obj.forwarding = new_obj;

        for (child in obj) {
            *child = copy(child);
        }
    }

    return obj.forwarding;
}

算法的开始是从roots的遍历开始,然后对每一个roots中的对象都执行copy方法。

如果这个对象没有被访问过,那么就在to space中分配一个与该对象大小相同的一块内存,然后把这个对象的所有数据都拷贝过去(copy data),然后把它的visited标记为true,它的forwarding记为新的地址。

接着遍历这个对象的所有引用,执行copy。这个过程是一个典型的深度优先搜索。

然后,还有最重要的一步,把forwarding做为返回值,返回给用者,让它更新引用。为什么要有forwarding这个属性呢?看起来很麻烦的样子,我直接在分配完了就把引用我的指针改掉不就行了吗?

考虑这样一种情况,A和B都引用了C:

然后我们执行copy算法,A先拷到to space,然后C又拷过去,这时候,空间里的引用是这种状态:

A和C都拷到新的对象里了,原来的引用关系还是正确的,美滋滋。但是B就惨了,它并不知道自己引用的C已经被拷贝了。当我们访问完B以后,对于它所引用的C,只看到C已经被搬走了,但并不知道搬到哪里去了。这就是forwarding的含义,我们可以在C上留下一个地址,告诉后来的人,这个地址已经失效了,你要找的对象已经搬到某某地了,然后你只要把引用更新到新的地址就好了。

举个例子,你有一个通讯录,上面记了你朋友家的地址在东北旺西路南口18号,当你按这个地址去找他的时候,看见他家门口贴了一张纸条,说我已经搬到北京西站南广场东81号了。好,那你就可以把这个新的地址更新到通讯录里了,下次,你按照新的地址还能找到你的朋友。

如上图所示,当B再去访问C的时候,就看到C已经被拷贝过了,而C通过forwarding指针引用了新的地址,那么B就可以根据这个新的地址把自己对C的引用变成对C'的引用。

Copy GC的特点

在普通的应用程序中,有大量的对象生命周期并不长,很多都是创建了以后没多久,就会变成垃圾(例如,一个函数通出以后,它所使用的局部变量都全都是垃圾了)。所以,在执行Copy GC时,存活的对象会比较少。我们执行Copy GC只要把还存活的对象拷贝到幸存者空间就可以了。当存活对象少的时候,GC算法的效率就会比较高。这时,算法就有很高的吞吐量。

至于Copy GC的更多内容,我们下期再讲。

原文发布于微信公众号 - HinusWeekly(gh_4b8b4eda4e40)

原文发表时间:2018-01-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏对角另一面

lodash源码分析之数组的差集

外部世界那些破旧与贫困的样子,可以使我内心世界得到平衡。 ——卡尔维诺《烟云》 本文为读 lodash 源码的第十七篇,后续文章会更新到这个仓库中,欢迎 s...

43414
来自专栏Spark生态圈

[spark] Shuffle Write解析 (Sort Based Shuffle)

从 Spark 2.0 开始移除了Hash Based Shuffle,想要了解可参考Shuffle 过程,本文将讲解 Sort Based Shuffle。

1522
来自专栏轮子工厂

务实基础篇--Java内存模型及GC原理

堆是Java代码可及的内存,留给开发人员使用的;非堆是JVM留给自己用的,包含方法区、JVM内部处理或优化所需的内存(如 JIT Compiler,Just-i...

1712
来自专栏祝威廉

ElasticSearch Aggregations GroupBy 实现源码分析

也就是按newtype 字段进行group by,然后对num求平均值。在我们实际的业务系统中,这种统计需求也是最多的。

4473
来自专栏生信小驿站

数据处理第3部分:选择行的基本和高级的方法

原文地址:https://suzan.rbind.io/2018/02/dplyr-tutorial-3/ 作者:Suzan Baert 这是系列dplyr...

981
来自专栏FreeBuf

浅析ReDoS的原理与实践

*本文原创作者:MyKings,本文属FreeBuf原创奖励计划,未经许可禁止转载 ReDoS(Regular expression Denial of Ser...

7915
来自专栏DOTNET

.Net多线程编程—Parallel LINQ、线程池

Parallel LINQ 1 System.Linq.ParallelEnumerable 重要方法概览: 1)public static ParallelQ...

3017
来自专栏Android知识点总结

Java总结IO篇之File类和Properties类

打开颜色选择器 :读流I-->字符串分割-->字符串存入Map-->使用Map对象还原用户配置 修改配置时 :写流O-->创建Map对象-->字符...

1842
来自专栏喔家ArchiSelf

从构造函数看线程安全

线程是编程中常用而且强大的手段,在使用过程中,我们经常面对的就是线程安全问题了。对于Java中常见的数据结构而言,一般的,ArrayList是非线程安全的,Ve...

1122
来自专栏社区的朋友们

iOS 中的 Promise 设计模式

无论是代理模式,还是闭包,在处理单一任务的时候,都出色的完成了任务。可是当两种模式要相互配合,一起完成一系列任务,并且每个任务之间还要共享信息,相互衔接,雇主就...

2.3K1

扫码关注云+社区

领取腾讯云代金券