垃圾回收算法的标记整理算法

好的，我们来详细说明垃圾回收中的标记整理算法。

标记整理算法

标记整理算法是一种常见的内存回收算法，主要用于解决内存碎片问题。它分为两个主要阶段：标记阶段和整理阶段。

1. 标记阶段

• 从根节点（如全局变量、活动栈帧）出发，递归遍历所有可达对象。
• 将所有可达对象标记为存活状态。
• 未被标记的对象即为垃圾对象。

2. 整理阶段

• 将所有存活对象向内存空间的起始端连续移动。
• 更新所有引用这些对象的指针，使其指向新的地址。
• 剩余空间被整理为连续空闲块。

移动存活对象后，内存布局变为： $$ \text{存活对象} \quad | \quad \text{连续空闲空间} $$

伪代码示例

def mark_compact(gc): # 标记阶段 mark_roots(gc.roots) # 计算新地址并移动对象 new_address = gc.heap_start for obj in gc.heap: if obj.marked: obj.new_address = new_address new_address += obj.size # 更新引用 for ref in gc.references: ref.target = ref.target.new_address # 移动对象并清除标记 for obj in gc.heap: if obj.marked: move(obj, obj.new_address) obj.marked = False

优点

1. 消除内存碎片：存活对象连续排列，避免内存空洞。
2. 空间局部性：对象紧密排列，提高缓存命中率。
3. 大内存分配：连续空闲空间可满足大对象需求。

缺点

1. 暂停时间长：移动对象时需暂停程序（Stop-The-World）。
2. 指针更新开销：需遍历所有引用更新地址。

该算法常用于对内存碎片敏感的场景（如嵌入式系统），典型代表为压缩垃圾回收（Compacting GC）。