垃圾收集

垃圾收集

未能释放已分配的块是一种编程错误。如下代码

void garbage()
{
	int *p = (int *)malloc(15213);
    return ;
}

程序员忘记释放p，导致p占用本来可以满足后面分配请求的堆空间。 垃圾收集器(garbage collector)是一种动态存储分配器，自动释放不再需要的称为垃圾的块，自动回收堆存储过程叫做垃圾收集，垃圾收集器定期识别垃圾块，并相应的调动free，将这些块放回到空闲链表中。 我们主要讨论标记清除法

基本知识

垃圾收集器将存储器视为一张有向可达图，如下图所示 垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点将它们返回给空闲链表，来定期回收它们。 像ML和Java对应用如何创建和使用指针有很严格的控制，能彀维护可达图的一种精确表示，可以回收所有的垃圾，然而C和C++通常步能维持可达图的精确表示，这样的收集器叫做保守的垃圾收集器，每个可达块都被正确的表示为可达，而一些不可达节点错误的被标记位可达。

Mark&Sweep垃圾收集器

Mark&Sweep垃圾收集器由标记(Mark)阶段和清除阶段组成，标记阶段标记出根节点的所有可达和已分配的后继，后面的清除阶段释放每个未被标记的已分配块。典型地，块头部中空闲的低位中的一位来表示这个块是否被标记了。

typedef void* ptr
ptr isPtr(ptr p) //如果p指向一个已分配的字，就返回一个指向这个块的起始位置的指针p，否则返回NULL
int blockMarked(ptr b) //如果已经标记了块b，就返回true
int blockAllocated() //如果块b是已分配的，就返回true
void markBlock(ptr b) //标记块b
int length(ptr b) //返回块b的以字为单位的长度(包括头部)
void unmarkBlock(prt b) //将块b的状态由已标记改为未标记
ptr nextBlock(ptr b) //返回堆中b的后继

标记阶段调用下图所示的Mark函数

void mark(ptr p) {
	if((b = isPtr(p)) == NULL) 
    	return;
    if (blockMarked(b)) 
    	return;
   	markBlock(b);
    len = length(b);
    for(int i = 0; i < len; i++)
    	mark(b[i]);
    return;
}

在标记阶段的末尾，任何未标记的已分配块都被认定为不可达的，是垃圾 Sweep函数如下所示

void sweep(prt b, ptr end) {
	while (b < end) {
    	if (blockMarked(b))
        	unmarkBlock(b);
        else if (blockAllocated(b))
        	free(b);
        b = nextBlock(b);
    }
    return;
}

下图展示了一个小堆的Mark&Sweep图形化解释 C语言GC有以下两点问题

• C不会用任何类型信息来标记存储器位置，对isPtr没有一种明显的方式来判断参数p是否为指针
• 对isPtr没有明显的方式来判断p是否指向一个已分配块的有效载荷中的某个位置

对第二个问题的解决方法是将已分配块集合维护成一颗平衡二叉树，这颗树保持这样一个属性:左子树的所有块都放在较小的地址处，而右子树的所有块都放在较大的地址处。 idPtr(ptr p) 函数用树来执行对已分配块的二分查找。平衡树方法会保证标记所有从根节点可达的节点，单它是保守的。