垃圾回收算法的标记清除算法

标记清除算法

标记清除算法是一种基础的垃圾回收算法，主要分为两个阶段：

1. 标记阶段

从根集合（全局变量、活动栈等）出发，递归遍历所有可达对象，将其标记为活动对象。未被标记的对象即为垃圾。该过程可表示为： $$ \text{Mark}(root) = { x \mid \exists \text{路径 } root \to x } $$

2. 清除阶段

遍历整个堆内存，回收所有未被标记的对象占用的空间：

def sweep(memory): for obj in memory: if not obj.is_marked: free(obj) else: obj.is_marked = False # 重置标记位

算法特点

• 优点：实现简单，无需额外内存空间
• 缺点：
  • 产生内存碎片
  • 暂停时间较长（需遍历整个堆）
  • 清除阶段需扫描所有对象

改进方案

现代垃圾回收器常采用分代收集或标记整理算法来优化碎片问题。