标记-整理算法

定义

该算法分为标记和整理两个阶段，标记阶段会遍历并标记活动对象，整理阶段通过数次搜索堆来重新装填活动对象，它们聚集到了堆的一端。

lisp2算法

forwarding指针表示活动对象的目标地址

过程概要

1. 初始状态

   
   

2. 标记结束后

   
   

3. 整理结束后

   
   

整理阶段伪代码

compaction_phase() {
    // 设定forwarding指针
    set_forwarding_ptr();
    // 更新指正
    adjust_ptr();
    // 移动对象
    move_obj();
}

// 第一次遍历堆
// $head_start 堆起始地址
// $head_end 堆结束地址
set_forwarding_ptr() {
    // 定义搜索堆的指针和指向目标地址的指针
    scan = new_address = $head_start;
    // 遍历堆，进行设置
    while (scan < $head_end) {
        // 若是活动对象，则设置forwarding指针
        if (scan.mark == TRUE) {
            scan.forwarding = new_address;
            new_address += scan.size;
        }
        scan += scan.size;
    }
}

// 第二次遍历堆
adjust_ptr() {
    // 更新根对象forwarding指针
    for (r : $roots) {
        *r = (*r).forwarding;
    }
    scan = $head_start;
    while (scan < $head_end) {
        // 更新子对象forwarding指针
        if(scan.mark == TRUE) {
            for(child : children(scan)) {
                *child = (*child).forwarding;
            }
        }
        scan += scan.size;
    }
}

// 第三次遍历堆
move_obj() {
    scan = $free = $heap_start;
    while(scan < $heap_end) {
        if(scan.mark == TRUE) {
            // 将找到的对象移动到 forwarding 指针的引用目标处
            new_address = scan.forwarding;
            copy_data(new_address, scan, scan.size);
            new_address.forwarding = NULL;
            new_address.mark = FALSE;
            $free += new_address.size;
        }
        scan += scan.size;
}