专栏首页海纳周报新生代的垃圾回收:Copy GC之基本原理

新生代的垃圾回收: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),作者:海纳

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 修饰者模式

    java.io 这个包里有一个类,比较特别,这就是BufferedReader。我们从JDK的源码里,找到它的实现: public class Buffered...

    海纳
  • 【第四期】GC专题

    我在某个技术群里发现很多人对GC的问题是最多的。确实,由于Java的GC经常会刷存在感(例如占用大量的CPU时间,full gc时直接失去响应),GC的问题就成...

    海纳
  • Java的分代式GC

    要说理解JVM的垃圾回收,什么引用计数,Copy GC,mark & compaction好像都不是必须要掌握的东西。真要说对普通的Java程序员比较重要的东西...

    海纳
  • 面试重点:Java虚拟机常见问题详解

    一、Java引用的四种状态: 强引用: 用的最广。我们平时写代码时,new一个Object存放在堆内存,然后用一个引用指向它,这就是强引用。 如果一个对象具有强...

    Java高级架构
  • 浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来设计,如何实现

    今天小婷儿给大家分享的是浅拷贝与深拷贝的实现方式、区别;deepcopy如果你来设计,如何实现。

    小麦苗DBA宝典
  • Android 中高级面试原理:热修复与插件化基础—Java与Android虚拟机

    下图是Java代码编译的详细流程(即,javac的执行过程),了解即可,一般只要知道java文件是通过javac命令编译成class文件,再通过java命令运行...

    Android技术干货分享
  • Java底层:GC相关

    光有垃圾标记算法还不行,JVM还需要有垃圾回收算法来将这些标记为垃圾的对象给释放回收掉。主要的回收算法有以下几种:

    端碗吹水
  • 内存泄露从入门到精通三部曲之基础知识篇

    1 首先以一个内存泄露实例来开始本节基础概念的内容: 实例1:(单例导致内存对象无法释放而泄露) ? ? 可以看出ImageUtil这个工具类是一个单例,并引...

    腾讯Bugly
  • 闲谈Android中的内存泄漏

    在长久以来的 Android 开发过程中,内存泄漏一直是一个比较头疼的问题。内存泄漏会导致应用卡顿,用户体验不佳,甚至会造成应用崩溃的严重后果。所以如何科学地进...

    俞其荣
  • 剖析 Python 面试知识点(二)- 内存管理和垃圾回收机制

    Python 中一切皆对象,对象又可以分为可变对象和不可变对象。二者可以通过原地修改,如果修改后地址不变,则是可变对象,否则为不可变对象,地址信息可以通过id(...

    天澄技术杂谈

扫码关注云+社区

领取腾讯云代金券