下面是看CSAPP时的读书笔记..Chapter10.10

垃圾回收

在C malloc这样的显式分配器中,我们可以使用malloc和free来分配,释放堆块.
在程序返回时,忘记释放已分配的块是一种很让人郁闷的事情.比如说,

void do()
{
	int *p = (int *) Malloc(10); // Malloc为malloc的包裹函数
	... // do something
	return;
}

函数do()分配了一块临时存储,当它不再需要p时,函数do()并未将其释放,这就导致了内存的泄露和浪费.按照UNPv2的说法,该临时存储是process-persistent的,它在程序的生命周期中都保持为已分配状态,毫无必要的占用着堆空间.

问题总是需要解决的.垃圾收集器(garbage-collector)就是其中的一个解决方案.它是一种动态存储分配器,功能是自动释放程序不再需要的已分配块(即内存垃圾),自动回收堆存储的这个过程就叫做垃圾收集(garbage collection).

垃圾收集的历史是相当久远的,它早于C的出现,目前仍是一个重要的研究领域.垃圾收集的算法很多,下面讨论的是Mark&Sweep算法,它比较简单,可以建立在已成熟的malloc包的基础之上,为C和C++提供垃圾收集.

基本原理

首先,不加解释的给出一张linux进程的存储器映像图,

GC(即垃圾收集器)将存储器看做是一张有向可达图(directed-reachability-graph).在该图中,节点可以分为两组,一组是根节点(root node),一组是堆节点(heap node).其中,每个根节点对应于一个不在堆中的位置,每个堆节点对应于堆中的一个已分配块,有向边 p->q 说明块p中的每个位置指向块q中的某个位置..注意,这里所说的位置,既可以是寄存器,又可以是栈里的变量,甚至是虚拟存储器中读写数据局域内的全局变量(见前图).当存在一条从任意根节点到达p的有向路径时,p称为可达的(reachable),否则,p称为不可达的(unreachable),不可达节点所对应的位置,即为内存垃圾.概括起来,GC的角色就是维护这张有向可达图,并通过释放不可达的节点来回收内存垃圾.

在具体的实现中,我们可以将GC作为一个和应用并行的独立线程,在后台进行垃圾的收集.下面是一个将GC加入malloc的例子,

当应用程序调用malloc时,如果malloc找不到一个合适的空闲块,那么它就调用GC,GC识别垃圾,调用free函数将垃圾回收.

Mark&Sweep

由名字就可以知道,Mark&Sweep收集器可以分为两个阶段,标记(mark)和清除(sweep),其中,标记阶段标记处根节点的所有可达的和已分配的后继,而清除阶段释放每个未被标记的已分配块(即垃圾).

小例子:

每个块对应着存储器中的几个字,其中,块头部包含一个字,要么是已标记的,要么是未标记的.

(1)标记前:

在标记前,堆由6个已分配但未标记的块组成,根节点指向第4块,第4块包含指向第3块和第6块的指针,第3块包含指向第1块的指针.

(2)标记后:

在标记后,第1,3,4,6块被标记(可达),第2,5块仍然是未标记(不可达).

(3)清除后

在清除后,第2,5块被回收.

算法

mark函数如下:

typedef char * ptr;

void mark(ptr p)
{
	if((b = isPtr(p)) == NULL) 
//如果p指向一个已分配块中的某个字,则返回指向这个块的起始位置的指针b,否则返回NULL.
		return;
	if(blockMarked(b)) //块b是否已标记
		return; 
	markBlock(b); //标记块b
	len = length(b); //块b的字长,包括头部
	for(i=0; i<len; i++)
		mark(b[i]);
	return;
}

标记阶段为每个根节点调用一次mark函数,如果p不指向一个已分配但未标记的堆块,mark函数就立即返回,否则,它标记这个块,并对块中的每个字递归的调用自己.每次对mark函数的调用都标记某个根节点的所有未标记且可达的后继节点.在标记阶段结束后,未标记但已分配的块就是不可达的,为内存垃圾.

sweep函数如下:

typedef char * ptr;

void sweep(ptr b, ptr end)
{
	while(b<end)
	{
		if(blockMarked(b)) //块b是否已标记
			unmarkBlock(b); //将块b由已标记改为未标记
		else if(blockAllocated(b)) //块b是否已分配
			free(b);
		b = nextBlock(b); //返回堆中块b的后继
	}
	return;
}

sweep函数在堆中的每个块上循环,释放它所遇到的所有未标记的已分配块.

C程序的保守的Mark&Sweep

对C语言来说,Mark&Sweep收集器一定是保守的,即每个可达块都被正确的标记为可达,而一些不可达节点可能会被错误的标记为可达的.导致这一问题的原因,是C语言不会用类型信息来标记存储器位置.因此,像int这样的标量可以伪装成指针.一个很典型的例子是,假如某个可达的已分配块在它的有效载域中包含一个int(注意,mark函数会对块中的每个字递归的调用自己),其值碰巧对应于某个其他已分配块t的有效载域的一个地址.对收集器而言,它是无法断定这个数值到底是int还是一个指针的.因此,它只能保守地将t标记为可达的,尽管事实上t可能是不可达的.

ps: 截图真是悲剧啊..
ps2: 博客域名随时可能改为godorz.info,感谢无敌的@zzzcn