Mark-Sweep垃圾收集器

目录

概念

基本知识

Mark-Sweep垃圾收集器

1.标记阶段伪代码：

2.清除阶段伪代码

概念

  垃圾收集器是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块被称为垃圾。自动回收堆存储的过程叫做垃圾收集。

基本知识

  垃圾收集器将内存视为一张有向可达图，该图中有一个根节点，所有的变量都会被根节点引用。形式如下图所示：

  本文仅讨论John McCarthy独创的Mark-Sweep（标记清除）算法。

Mark-Sweep垃圾收集器

  Mark-Sweep垃圾收集器由标记阶段和清除阶段组成。

标记阶段：通过广度扫描，标记与根节点相关（所有可达的和已分配的后继）的结点

清除阶段：将没有被标记的块释放

1.标记阶段伪代码：

void mark(ptr p)
{if((b=isPtr(p))==NULL)//判断块是否已分配return;if(blockMarked(b))//判断块是否已被标记return;markBlock(b);//标记块len=length(b);for(i=0;i<len;i++)mark(b[i]);return;
}

2.清除阶段伪代码

void sweep(ptr b,ptr end)
{while(b<end){if(blockMarked(b))//判断块是否已被标记unmarkBlock(b);//取消标记else if(blockAllocated(b))//判断块是否已分配free(b);//释放垃圾b=nextBlock(b);//返回堆中块的后继}return;
}