复制算法

定义

把活动对象复制到其他空间，回收原空间所有对象。原空间称为From区，新空间称为To区。

过程概要

copying伪代码

// $from_start 为From区起始地址
// $to_start 为To区起始地址
copying() {
    $free = $to_start
    // 循环复制所有根及其子对象
    for (r : $roots) {
        copy(*r);
    }
    // 交换From和To区
    swap($from_start, $to_start);
}

copy函数

copy(obj) {
    // 检测是否已经复制
    if (obj.tag !=  COPIED) {
        // 复制对象到新空间
        copy_data($free, obj, obj.size);
        obj.tag = COPIED;
        // 把新空间地址放入forwording域
        obj.forwarding = $free;
        $free += obj.size
        // 循环处理子对象，使其复制到新空间
        for (child : children(obj.forwarding)) {
            *child = copy(*child);
        }
    }
    // 返回新空间对象的地址
    return obj.forwarding;
}

1. 通过 copy_data() 函数复制对象

   
   

2. 定义 COPIED 标签和设置 forwarding 指针

   
   

3. copying() 函数执行完毕后

   
   

new_obj函数

new_obj(size) {
    // 判断空间大小是否小于申请空间大小
    if ($free + size > $from_start + HEAP_SIZE/2) {
        // 执行复制
        copying();
        // 再次判断
        if ($free + size > $from_start + HEAP_SIZE/2) {
            // 执行分配失败策略
            allocation_fail();
        }
    }
    // 分配成功
    obj = $free;
    obj.size = size;
    // 修改偏移量
    $free += size;
    return obj;
}

执行过程

1. 初始状态

   
   

2. B被复制后

   
   

3. B的子对象A被复制后

   
   

4. GC结束

   
   

迭代复制算法

copying函数

// scan 是用于搜索复制完成的对象的指针
// $free 是指向分块开头的指针
copying() {
    scan = $free = $to_start;
    // 复制根对象
    for(r : $roots) {
        *r = copy(*r);
    }
    // 循环复制子对象
    while (scan != $free) {
        for (child : children(scan)) {
            *child = copy(*child);
        scan += scan.size;
    }
    swap($from_start, $to_start);
}

copy(obj) {
    // 检测是否已复制完毕
    if (is_pointer_to_heap(obj.forwarding, $to_start) == FALSE) {  
        // 复制对象
        copy_data($free, obj, obj.size);
        obj.forwarding = $free;
        $free += obj.size;
    }
    return obj.forwarding;
}

执行过程

1. 初始状态

   
   

2. 复制根对象B和G之后

   
   

3. 搜索B新对象，并复制子对象

   
   

4. GC结束状态

   
   

多空间复制算法

多空间复制算法是把堆 N 等分，对其中 2 块空间执行 GC 复制算法，对剩下的 (N-2)块空间执行 GC 标记 - 清除算法，也就是把这 2 种算法组合起来使用。

multi_space_copying函数

multi_space_copying() {
    $free = $heap[$to_space_index];
    // 给活动对象打标记
    for (r : $roots) {
        *r = mark_or_copy(*r);
    // 清除阶段
    for (index : 0..(N-1)) {
        if (is_copying_index(index) == FALSE) {
            sweep_block(index);
    $to_space_index = $from_space_index;
    $from_space_index = ($from_space_index + 1) % N;
}

mark_or_copy函数

mark_or_copy(obj) {
    // 若obj在From空间，使用复制算法
    if (is_pointer_to_from_space(obj) == TRUE) {
        return copy(obj);
    } else {
        // 否则，使用标记-清除算法
        if (obj.mark == FALSE) {
            obj.mark = TRUE;
            for(child : children(obj)) {
                *child = mark_or_copy(*child);
            return obj;
        }
    }
}

copy(obj) {
    if (obj.tag != COPIED) {
        copy_data($free, obj, obj.size);
        obj.tag = COPIED;
        obj.forwarding = $free;
        $free += obj.size;
        for(child : children(obj.forwarding)) {
            *child = mark_or_copy(*child);
        }
        return obj.forwarding;
    }
}

执行过程

1. 开始第一次GC前

   
   

2. 第一次GC后

   
   

3. 开始第二次GC前

   
   

4. 第二次GC后