GC 复制算法

思路

之前提到的标记清扫和引用计数法都不会更改对象的位置，并且利用了全部的内存。在此我们就打破这个限制。

首先我们把内存分成两半，一半叫 from , 一半叫 to 。每次程序运行时只占用 from，当需要垃圾回收的时候，就先找到所有的活动对象，然后复制到 to 中，并且从 to 的低地址陆续摆放。然后交换 from 和 to 的名字。

这个算法的关键是不仅要把对象搬运过来，还要把对象之间的引用给修正了。这里也是假定了对象至少有一个域，我们把这个域称为 forward .

在对象还是在 from 中的活动对象的时候，这个 forward 就可以认为不存在，因为这是对象的成员的一部分。而当对象复制到 to 之后的时候，原来的对象就没用了，我们就取它的第一个字节为 forward，用来记录对象复制到 to 之后的新地址。

值得一提的是：由于 from 和 to 本身都是连续的地址（但是 from 和 to 的地址未必是连续的，这里只需要记录下 from 和 to 的开始和结尾四个变量即可，实际上用了 $heapSize/2 ）所以可以瞬间判断一个地址是属于 from 还是 to，进而判断它有没有被复制完成。

但是我们暂时不用这种方法，仍然是采用多设置一个 obj.tag，如果为 1，也就是 COPYED, 就表示已经复制了，否则就没有复制。

经过上述分析不难发现，这个算法是不会在内存中产生碎片的。因为内存的空闲位置一定在 from 的高地址位置连续。所以也不需要空闲链表，只需要看看 from 空间末尾还有没有位置即可。

实现

全局变量

$fromStart : from 的起始地址 $toStart : to 的起始地址 $heapSize : 整个堆的大小 $toFree : 目前 to 的空闲的位置的首地址 $free : 目前 from 空间的空闲位置的首地址

newObj(size){
    // from 空间不足
    // 这里是假设堆只有 from 和 to 两个空间
    if($free + size > $heapSize/2)
        copying();
        if($free + size > $heapSize/2)
            allocationFail();
        }
    }
    obj = $free;
    obj.size = size; 
    $free +=size;
    return obj;
}

// 将所有对象都复制到 to 中
copying(){
    for(r : $roots){
        copy(r);
    }
    swap($from,$to);
    $toFree = $to;
}

// 复制单个对象并且
copy(obj){
    // obj 是旧对象
    if(obj.tag != COPYED){
        obj.tag = COPYED;
        obj.forward = $toFree;
        $toFree += obj.size;
        // 这里实际上是个引用，就是引用自己复制后的对象，修正新对象的儿子指针的指向。
        for(child : children(*obj.forward)){
            // 如果儿子没被复制就复制，如果被复制了就会返回新地址
            child = copying(child);
        }
        return obj.forward;
    }
    return obj;
}

优点

GC 复制算法优点很多。

没有碎片。因为每次复制之后，活动对象都紧紧挨着，所以没有碎片。
分配对象速度快。只需要判断 from 的末尾是否能放开这个对象即可，不需要。
只对活动对象进行分配，所以算法的复杂度就是标记的复杂度（正比于活动对象的个数）和复制的复杂度（也是正比于活动对象的个数）
对缓存友好。在复制之后，所有有引用关系的对象都会尽可能挨着（因为是 dfs 序排放）

缺点

最大的缺点就是只有一半的内存使用效率。
不兼容保守式 gc。也就是说我们必须重写指针，这是之前的算法所没有的。
采用了 dfs，有爆栈的风险。事实上这是一个比较好解决的方案，我们接下来就会解决它。

优化

Cheney GC 复制算法

这个算法思路非常巧妙。之前提到担心 dfs 会爆栈，所以我们就可以采用 bfs，但是 bfs 不也是有空间消耗吗？此算法就拿 to 空间本身加上一些指针就把 to 当做了队列来使用。

首先要复制根直接指向的对象（不递归）。

然后设置队首指针 scan ，指向 to 空间的首地址。 $toFree 表示 to 空间的第一个空闲的首地址。

然后进入循环，扫描队首对象的子对象，如果没有在队列中，就放到 toFree 的位置，然后 toFree 向后移动。当处理完队首对象，scan 就向后移动。

注意这个算法顺便还取消了 tag，所有的对象都按照 forward 指针的值来判断是否已经复制了。这个原理我们在本章前文已经讲述了。

// copy 所有对象
copying(){
    scan = $toFree = $toStart;
    for(r : $roots){
        r = copyObj(r);
    }

    // scan == $toFree 表示队列为空
    while(scan < $toFree){
        for(child : children(*scan)){
            child = copyObj(child)
        }
    }

    swap($fromStart，$toStart)
}

copyObj(obj){
    // 实际上这里的 obj 必然是一个在 from 空间的对象，所以必须要看其 forward
    // 已经复制完了
    if($toFree < obj.forward && obj.forward < $toFree+$heapSize/2){
        return obj.forward;
    }
    obj.forward = $free;
    $free+=obj.size;
    return obj.forward
}

优点

相比于原始的 GC 复制算法，Cheney 方法能够更好的利用内存，避免了爆栈的风险。

缺点

同样，由于 bfs 的访问顺序问题，相邻的对象就不一定是其儿子对象了。相当于树的层序遍历顺序，这样其实对缓存不友好。接下来的方法就是尝试去解决这个问题。

近似深度优先搜索

这个算法是针对 Cheney 的优化。主要是考虑了内存分页问题。我们假设所有对象都一样大，每个页能放的对象个数也一样。

但是这个算法如果仅仅根据书中的描述是很有局限性的。书中举得例子是有些巧合的。

大体思路是这样：由于每个页的大小是有限的，所以我们争取把父子关系的对象放到一个页里。当一个节点的儿子对象被分到了新的一页的时候，就停止当前的操作，再把这个儿子的儿子对象给分配到这一页（注意这个过程不是递归的）。

$majorScan : 当前正在处理的第一页（也就是存在儿子对象没有复制完的对象的第一页） $free : 整个堆空间中剩余空间的开端 $localScan[] 是一个数组，大小和页面数相同，第 i 个元素表示第 i 页的第一个没有处理完子对象的儿子的下标

然后复制 majorScan 的时候，如果探测到子对象被安排在了新页，就跳到那一页的开始放这个子对象的子对象。放完了之后再眺回 majorScan 那一页继续复制。最终缓存友好了。

多空间复制算法

GC 复制算法一次使用半个堆太浪费了，但是要保证 from 不能大于 to 的大小，所以就有人提出了把堆分成多个空间。其中一个空间是 from，另一个空间是 to，在这两个空间里使用 gc 复制算法，其他的采用标记清除算法。然后每次的 from 和 to 都不一样。

思路也比较简单。假设空间的标号是 [0, n-1] (n>2) , 那么我们令 0 为 to, 1 为 from，然后其他空间标记清扫，这两个空间 gc 复制。在复制之后， to = from, from = (from+1)%n .

这样就综合了两种方法的优点和缺点，实际上是降低了标记清扫法每次停止的时间。然后也减少了标记清扫法产生的内存碎片问题。

「垃圾回收的算法和实现」第四章-GC 复制算法

GC 复制算法

思路

实现

优点

缺点

优化

Cheney GC 复制算法

优点

缺点

近似深度优先搜索

多空间复制算法

CATALOG

FEATURED TAGS

FRIENDS