简介

标记-压缩法是将标记-清除法和复制法结合起来的产物，由标记阶段和压缩阶段组成

  • 标记阶段：此阶段与标记-清除法提到的标记阶段完全一样
  • 压缩阶段：此阶段通过数次搜索堆来重新装填活动对象

Lisp2算法

对象结构

Lisp2算法在对象头中定义了一个forwarding指针，其用法和复制法中的用法一致(《垃圾回收的算法与实现》3.复制法)

执行过程

假设以下图的堆空间开始GC：

首先是标记阶段，标记完成后堆空间如下图所示：

压缩阶段结束后的堆空间：

在Lisp2算法中，压缩阶段并不会改变对象的排列顺序，只是将它们变得更紧凑了

压缩阶段由以下3个步骤组成：

  1. 设定forwarding指针
  2. 更新指针
  3. 移动对象

设定forwarding指针

在此步骤中，会搜索整个堆，为活动对象设定forwarding指针，将其指向

预计要移动到的地址

此步骤结束后的堆空间如下：

更新指针

此步骤首先会更新根节点的指向，使所有root指向root.forwarding，然后会搜索整个堆，使所有指向活动对象的指针都改为指向此指针的forwarding

此步骤结束后的堆空间如下：

移动对象

此步骤会将所有活动对象移动到forwarding指向的地址处（注意：此时已经是第3次搜索整个堆了）

此步骤结束后的堆空间如下：

优点

可有效利用堆

标记-压缩法和其他GC算法相比，对堆空间的利用率更高，在防止出现标记-清除法可能导致的内存碎片的情况下，不会出现复制法那样只能利用一半堆空间的情况

缺点

压缩花费成本高

Lisp2算法的压缩中，必须对整个堆进行3次搜索，因此吞吐量要劣于其他算法