← Back

垃圾回收的算法与实现读书笔记-标记清除算法

作为一个Java 程序员，得益于它的自动垃圾回收机制，极大的降低了因为编程导致的内存问题的发生几率。但是作为一个有追求的程序员，了解垃圾回收的内部实现对工作以及个人发展都是极其有帮助的。

在之前的工作中已经对Java 常用的GC算法有了一些浅显的理解，但是对于算法本身的实现并无深入的了解。后来在网上淘书是发现了这版本《垃圾回收的算法与实现》，试读后发现很不错。于是购买了一本打算深入的学习下。这里就是记录我学习过程中的一些记录以及根据书中伪代码实现完成简单的Java实现。

GC 算法的分类

GC 算法的分类主要有一下的几种：

* 标记-清除算法  1960年 John McCarthy 发布了第一个GC算法 标记-清除算法
* 引用计数算法  1960年 George E. Collins 发布了引用计数算法。
* 复制算法  1963年 Marvin L.Minsky 发布了复制算法
* 标记-压缩算法

后续会按照顺序都会做一个简单的实现。

基本数据结构

首先看下实现过程中使用的数据结构:

* 堆。 堆是存放对象的地方。主要完成两个动作：申请指定大小的内存；释放指定大小的内存

        public class Heap {

            /**
            * 整个堆得大小
            */
            protected int size;

            /**
            * 整个堆已经分配的大小
            */
            protected int allocatedSize;

            /**
            * 堆的分配策略
            */
            protected int fitStrategy;

            public static final int FIRST_FIT_STRATEGY = 1;
            public static final int BEST_FIT_STRATEGY = 2;
            public static final int WORST_FIT_STRATEGY = 3;

            /**
            * 空闲Slot的列表
            */
            protected LinkedList<Slot> emptyList = new LinkedList<Slot>();

            /**
             * 从堆中申请一个指定大小的可用区块
            */
            public Slot applySlot(int size);

            /**
             * 释放指定大小的区块
            */
            public void release(Slot releaseSlot);
        }    

* 对象。表示一个基本的对象，可以知道该对象在内存中的起始位置、大小以及引用的对象

        public class Obj {

            /**
            * 表示对象的大小
            */
            public int size;

            /**
            * 表示对象在中的起始位置
            */
            public int start;

            /**
            * 用来表示对象之间的引用关系
            */
            public LinkedList<Obj> children = new LinkedList<Obj>();
        }

* GC 算法接口。目前只定义了一个创建对象的接口
        public interface GcAlgo {

            /**
            * 创建一个指定大小的对象
            * @param size
            * @return
            */
            Obj newObj(int size);
        }

标记-清除算法

标记-清除算法理解起来还是比较简单的。主要分为两个阶段：

* 标记阶段
    * 首先标记通过根直接可以引用到的对象
    * 然后在标记所有能够访问到的对象
        * 可以通过递归做深度优先访问
        * 可以通过辅助队列做广度优先访问
* 清除阶段
    * 遍历整个堆，回收没有打上标记的对象

算法实现

标记-清除算法需要在对象中增加一个字段来标识对象是否已经被标记。所以我新定义了一个 MarkSweepObj 对象

1
2
3
4
5
6
7

public class MarkSweepObj extends Obj{

    /**
     * 表示对象的标记状态  true : 表示不需要清理，false : 表示需要清理
     */
    public boolean marked;
}

基本的代码实现

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

public void markSweep() {
    //标记阶段
    markPhase();
    //清除阶段
    sweepPhase();
}

private void markPhase() {
    //从根节点开始标记对象
    for (MarkSweepObj obj : roots) {
        mark(obj);
    }
}

private void mark(MarkSweepObj obj) {
    if (!obj.marked) {
        obj.marked = true;
        //如果有引用对象，则递归标记引用对象
        if (!obj.children.isEmpty()) {
            for (Obj child : obj.children) {
                mark((MarkSweepObj) child);
            }
        }
    }
}

private void sweepPhase() {
    // allocatedObjList 记录了所有分配过的对象
    Iterator<MarkSweepObj> iterator = allocatedObjList.iterator();
    while (iterator.hasNext()) {
        MarkSweepObj obj = iterator.next();
        //如果对象没有标记，则说明该对象从根节点不可达，需要清理掉
        if (!obj.marked) {
            //release 之后会将Slot 添加到空闲列表中
            heap.release(new Slot(obj.start, obj.size));
            iterator.remove();
        } else {
            //将对象的标记归位，供下次GC使用
            obj.marked = false;
        }
    }
}

代码看起来可能还有些不那么直观，有图的话就会好很多了。假设下图是GC执行之前的初始状态。

标记清除init.png

图中绿色的分块表示已经分配的对象，白色的表示空闲的内存。可以看到从根节点直接引用了两个对象，其中一个对象又引用了另外的两个对象。还有几个对象无法从根节点开始访问得到。空闲列表中包含了可用来分配的内存区块。

当标记阶段执行完成以后，整个堆得情况如下：

标记清除marked.png

可以看到从根节点开始可以访问到的对象都已经打上了对象存货的标记了。接下来就是执行清除的步骤了。

标记清除sweeped.png

可以看到清除之前从根节点不可达的对象都已经被清理，加入到了空闲列表中。其他存活的对象的标记也都重置了。现在空闲列表中总共有3块可供分配的内存区块，大小分别是3，2，6。

以上就是整个标记-清除算法的基本实现，在之前的基本结构中有个 GcAlgo，这个接口中定义的 newOb 方法又是怎么实现的呢。

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

/**
 * 创建一个新的对象
 *
 * @param size 对象的大小
 * @return 创建好的对象
 * @throws OutOfMemoryError 当内存无法满足分配要求时抛出
 */
public MarkSweepObj newObj(int size) {

    Slot slot = heap.applySlot(size);

    //如果申请到的内存空间为null, 则执行一次GC
    if (slot == null) {

        markSweep();

        slot = heap.applySlot(size);
        //到这里还没有分配成功，说明内存已经不能满足分配的需求
        //直接抛出 OOM 的错误
        if (slot == null) {
            throw new OutOfMemoryError("oh, out of memory!");
        }
    }

    //初始化对象
    MarkSweepObj obj = initObj(slot);
    //将分配好的对象添加到列表中
    allocatedObjList.add(obj);

    return obj;
}

//简单的对象初始化，只是记录了对象的开始位置和大小
private MarkSweepObj initObj(Slot slot) {
    MarkSweepObj obj = new MarkSweepObj();

    obj.start = slot.start;
    obj.size = slot.size;

    return obj;
}

逻辑比较简单清晰。首选就是尝试从堆中获取指定大小的内存；如果没有获取得到，就执行一次GC；完了以后再尝试一次内存分配，如果再不成功说明当前内存已经不能满足分配需求了（并不是空间就一定比需求小了），所以抛出OOM的错误。

以上就是这个标记-清理算法的实现逻辑了。具体的代码请查看：标记-清理算法实现。

执行

接下来我们执行下，执行的示例代码如下：

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

//构建一个容量为20，采用BestFit分配策略的堆
MarkSweepAlgo algo = new MarkSweepAlgo(20, Heap.FIRST_FIT_STRATEGY);


try {
    MarkSweepObj obj1 = algo.newObj(4);
    MarkSweepObj obj2 = algo.newObj(3);
    obj1.children.add(obj2);

    MarkSweepObj obj3 = algo.newObj(3);
    algo.makeItToRoot(obj3);

    MarkSweepObj obj4 = algo.newObj(4);
    algo.makeItToRoot(obj4);
    MarkSweepObj obj5 = algo.newObj(2);
    MarkSweepObj obj6 = algo.newObj(3);
    obj4.children.add(obj5);
    obj4.children.add(obj6);


    MarkSweepObj obj7 = algo.newObj(2);

    MarkSweepObj obj8 = algo.newObj(7);
    obj3.children.add(obj8);
    MarkSweepObj obj9 = algo.newObj(4);

    }catch (Throwable e){
        System.out.println(e.getMessage());
    }

通过以上的代码，模拟创建了如下图所示的对象结构：

标记清除示例初始化.png

接下来执行结果：

标记清除-算法执行结果1.png

可以看到整个过程分配了7个对象，执行了两次GC。最后一次GC执行后堆可用空间是8，这时候我们要分配的obj8 的大小为7，但是却抛出了oom的异常，从最后的日志可以看到，虽然可用空间有8，但是没有单个Slot 能够满足要求。

接下来我们对标记-清理算法做一个总结。

优点

实现简单是标记-清除算法最大的优点。整个模拟的实现也就200多行代码，真正核心的更少。

缺点

相较于优点，标记-清除的缺点就比较多了。

* 碎片化。这个在实际运行的时候已经看到了，在使用过程中会逐渐产生被细化的分块，尽管在总量上内存是够用的，但是实际上却因为碎片化导致对象无法分配。
* 分配速度。每次分配都需要遍历空闲列表
* 与COW(copy-on-write)技术不兼容。现代操作系统会使用COW技术来减少对象的移动，但是标记-清除算法每次都需要修改标记，就会引起不必要的对象移动。

优化方案

碎片化

通过适时对空闲列表进行压缩，能够比较有效的解决碎片化的问题。这个在Java 常用的 CMS GC 算法中也有体现，可以通过参数 UseCMSCompactAtFullCollection 和 CMSFullGCsBeforeCompaction=N 来设置压缩策略。

在我们简单的实现中，将空闲列表按照地址排序后，遍历列表将相邻的Slot 合并为一个大的Slot。以下是增加了合并功能之后的执行结果，可以看到压缩 obj8 分配成功了。

标记清除示例压缩.png

分配速度

现在我们只使用了一个空闲列表，为了加快速度可以使用多个空闲列表。将相同大小的 Slot 放在一个列表中，这样分配的时候就直接去对应列表的第一个元素就可以了。当然空闲列表也不越多越好，对于大小超过一定限制的可以放到一个列表中。

兼容COW

为了能够兼容COW，所以需要将对象的标记存储其他的地方。可以使用位图标记的方式来解决。主要思路是：将堆按照指定大小划分为多个区块，然后每个区块对应到位图中的1位。这样对内存中的对象是存活的对象，就将对应的位图标记置为1，清理的时候就将所有标记为0的对象清理掉就可以了。

以下是简单的代码实现：

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


public class MarkSweepWithBitMapAlgo extends MarkSweepAlgo {
    /**
     * 定义一个字的长度
     */
    public static final int WORD_LENGTH = 32;

    private int[] bitmapTable;
    private int bitmapTableSize;

    public MarkSweepWithBitMapAlgo(int size, int fitStrategy) {
        super(size, fitStrategy);
        this.bitmapTableSize = size / WORD_LENGTH + 1;
        //初始化位图标记
        bitmapTable = new int[bitmapTableSize];
    }

    @Override
    public void markSweep() {
        markPhase();
        sweepPhase();
    }

    private void markPhase() {
        for (MarkSweepObj obj : roots) {
            mark(obj);
        }
    }

    private void mark(MarkSweepObj obj) {

        int index = obj.start / WORD_LENGTH;
        int offset = obj.start % WORD_LENGTH;

        if ((bitmapTable[index] & (1 << offset)) == 0) {
            //将对象对应的标志位置为 1
            bitmapTable[index] |= (1 << offset);
            for (MarkSweepObj child : obj.children) {
                mark(child);
            }
        }
    }

    private void sweepPhase() {
        int index, offset;

        Iterator<MarkSweepObj> iterator = allocatedObjList.iterator();
        while (iterator.hasNext()) {

            MarkSweepObj obj = iterator.next();
            index = obj.start / WORD_LENGTH;
            offset = obj.start % WORD_LENGTH;

            //标记完成之后标志位为0，说明该对象是需要回收的对象
            if ((bitmapTable[index] & (1 << offset)) == 0) {
                heap.release(new Slot(obj.start, obj.size));
                iterator.remove();
            }
        }

        //重置标志位
        for (int i = 0; i < bitmapTableSize; i++) {
            bitmapTable[i] = 0;
        }
    }


}