好的，我们来详细说明垃圾回收中的标记整理算法。
标记整理算法
标记整理算法是一种常见的内存回收算法，主要用于解决内存碎片问题。它分为两个主要阶段：标记阶段和整理阶段。
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优点
- 消除内存碎片：存活对象连续排列，避免内存空洞。
- 空间局部性：对象紧密排列，提高缓存命中率。
- 大内存分配：连续空闲空间可满足大对象需求。
缺点
- 暂停时间长：移动对象时需暂停程序（Stop-The-World）。
- 指针更新开销：需遍历所有引用更新地址。
该算法常用于对内存碎片敏感的场景（如嵌入式系统），典型代表为压缩垃圾回收（Compacting GC）。
