← Back

垃圾回收的算法与实现读书笔记-复制算法

在上一篇文章中介绍了引用计数法的实现，这边接着来讲复制算法的实现

文中部分图片引用自《垃圾回收的算法与实现》一书，如有版权问题，请联系删除。

复制算法

GC复制算法是Marvin L. Minsky在1963年研究出来的算法。该算法会将整个堆分成两个区域：from area 和 to area。这两个空间的大小一样。GC复制算法利用from区做分配，当from区满了以后，会将存活的对象全部复制到to区，当复制完成以后会将from区和to区互换，这样整体的GC也就结束了。下图描述了整体的一个概要:

复制算法概要

算法实现

用Java来模拟复制算法有个难点是：因为Java的参数是值传递，所以在复制对象的时候需要更新原来对象的引用，但是这个不引入辅助的情况下是比较难的。所以我们先来通过图解了解下整个GC算法的一个过程。

首先假设现在堆中对象结构如下图所示：

初始状态

根引用A，A同时引用了C和D，B没有引用来源，所以是需要被回收的对象。复制算法的回收是从根开始的，所有能够从根到达的对象都是活的对象，需要被复制。

首先对象A被复制，生成了A'。因为A有引用其他的对象，所以新生成的A'也会引用到这些对象。但是需要注意的是这些对象现在都还在from区域，所以A'持有指向from区域的引用，如下图所示：

复制A

接着会将A对象标记为COPIED，如下图所示：

复制A第二步

接着会把A引用的对象C和D都copy到to区域，同时原对象都标记为COPIED。同时将根的引用切换到A'，变成了如下图所示的情况：

复制A的子对象

最后将from区里面的对象全部清理掉，并将from和to区域交换，就完成了一次GC的过程。

完成GC

代码模拟实现

首先对于Obj对象需要增加一个copied的标记来方式对象被重复的复制。

GC复制算法使用的堆对象比前面提到的标记-清除和引用计数都简单，因为在内存中都是连续分配的，所以也不需要指定分配策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

public class CopyHeap {

    /**
     * from 区域的起始位置。在完成一个copying后，
     * fromStart 和 toStart的值会进行互换
     */
    public int fromStart;

    /**
     * to 区域的起始位置。
     */
    public int toStart;

    /**
     * 表明当前空闲内存的起始位置。
     */
    public int free;

    /**
     * 表明实际可用的大小
     */
    public int size;


    static final int MAXIMUM_CAPACITY = 1 << 30;

    public CopyHeap() {
    }

    /**
     * 因为Copy算法是连续分配的，所以不需要确定分配策略
     * @param size
     */
    public CopyHeap(int size) {
        int realSize = calcPowSize(size);
        this.size = realSize / 2;
        fromStart = 0;
        toStart = this.size;
        free = 0;
    }


    /**
     * 将数据Copy 到 TO 区块。简单的实现为增加空闲内存的起始位置
     * @param size
     */
    public int copyData(int size){

        int start = free;
        free += size;

        return start;
    }

    /**
     * 判断是否有足够的内存来满足对象分配
     * @param size
     * @return
     */
    public boolean hasEnoughMemory(int size){
        return free + size < (this.size + fromStart);
    }


    /**
     * 每次copying完成以后，互换fromStart 和 toStart
     */
    public void swap(){
        int tmp = fromStart;
        fromStart = toStart;
        toStart = tmp;
    }


    private static final int calcPowSize(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}

GC复制算法本身实现也比较简单，主要注意的地方就是要考虑Java的值传递的问题，所以在实现的时候做了一个小的改造，就是只是将原对象的起始地址修改下，以此来表示对象已经被复制了。否则要在Java中实现引用传递还是比较麻烦的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

public class CopyAlgo {

    private CopyHeap heap;

    /**
     * 表示GC 的根
     */
    private LinkedList<CopyObj> roots = new LinkedList<>();


    public CopyAlgo(int size) {
        heap = new CopyHeap(size);
    }

    /**
     * 创建对象
     * @param size
     * @return
     */
    public CopyObj newObj(int size) {
        if (!heap.hasEnoughMemory(size)) {
            copying();

            if (!heap.hasEnoughMemory(size)) {

                System.out.println(String.format("Copy GC Fail Heap total(%d) used(%d)", heap.size, heap.free));
                throw new OutOfMemoryError("------ oh, out of memory! ------");
            }
        }

        CopyObj copyObj = new CopyObj(size, heap.free);
        heap.free += size;

        return copyObj;
    }

    /**
     * 开始进行复制
     */
    private void copying() {

        int oldSize = heap.free - heap.fromStart;
        //将当前空闲内存的起始位置置为to区域的起始位置
        heap.free = heap.toStart;

        //从根节点开始递归的进行复制
        for (CopyObj root : roots) {
            copy(root);
        }

        //交互from 和 to
        heap.swap();

        System.out.println(String.format("Copy GC End. Heap before(%d) now(%d)", oldSize, heap.free - heap.fromStart));
    }

    private void copy(CopyObj copyObj) {

        //复制对象，在目标区域中申请同样大小的内存
        copyData(copyObj);
        //将复制标记为置为true
        copyObj.copied = true;

        //开始复制引用的对象
        for (Obj child : copyObj.children) {
            CopyObj obj = (CopyObj) child;
            copy(obj);

        }
    }

    private void copyData(CopyObj copyObj) {
        //因为Java的参数传递均为值传递，所以为了不影响上层的使用
        //这里均实现为修改对象的起始位置。
        copyObj.start = heap.copyData(copyObj.size);
    }

    /**
     * 把对象置为根节点
     *
     * @param obj 根对象
     */
    public void makeItToRoot(CopyObj obj) {
        roots.add(obj);
    }

    public void removeFromRoot(CopyObj obj){
        roots.remove(obj);
    }
}

最后看一个实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class GcUseCaseByCopyAlgo {

    public static void main(String[] args) {

        CopyAlgo copyAlgo = new CopyAlgo(32);

        CopyObj first = copyAlgo.newObj(4);
        CopyObj second = copyAlgo.newObj(4);

        copyAlgo.makeItToRoot(first);
        copyAlgo.makeItToRoot(second);

        CopyObj firstChildOne = copyAlgo.newObj(5);

        //进行到这里时需要的总内存为 13 + 7， 总内存只有16， 所有会进行一次复制
        //回收掉没有引用来源的 firstChildOne
        CopyObj firstChildTwo = copyAlgo.newObj(7);

        first.children.add(firstChildTwo);

        //到这里需要的内存为 4+4+7+6 = 21, 大于总内存 16，会进行一次copy ,
        //但是仍然是不能满足要求的，所以会抛出OOM的异常
        CopyObj firstChildChildOne = copyAlgo.newObj(6);
        firstChildTwo.children.add(firstChildChildOne);


        CopyObj secondChild = copyAlgo.newObj(6);
        second.children.add(secondChild);

        firstChildOne.children.remove(firstChildChildOne);
        first.children.remove(firstChildTwo);

        CopyObj needCopyingObj = copyAlgo.newObj(4);
    }
}

运行结果如下图所示:

运行结果

算法优缺点

优点:

* 吞吐量较好。GC复制算法只会搜索存活的对象，跟标记-清除算法比需要的时间较短。
* 可实现高速分配。GC算法的分配是在一片连续的内存空间分配的，所以只需要移动空闲的指针即可。
* 不会产生碎片。
* 对缓存友好。每次GC完成以后，有关联的对象都会顺序排列在一起。

缺点:

* 堆的使用效率低下。很明显，只能使用一般的堆
* 递归调用函数。每次复制对象都要递归的调用函数，效率比较低，还有栈溢出的可能性。