编程之禅
0%

垃圾回收的基本原理

发表于 更新于 分类于 阅读次数： Disqus：

对于像 maclloc 这样的显式分配器，应用通过调用 malloc 和 free 来分配和释放堆块，应用要负责释放所有不再需要的已分配块。

不能及时释放内存堆块可能造成严重的内存错误，例如：内存泄漏，如下列代码所示：

1
2
3
4
void garbage(){
		int *p = (int*)malloc(1024);
  	return;
}

在 garbage 返回之前应该释放 p，不幸的是，程序员忘了释放这个块，它在程序的生命周期内都保持已分配状态。

垃圾收集器(garbage collector)是一种动态内存分配器，它自动释放不再需要的已分配块。这些块被称为垃圾(garbage)。

垃圾收集可以追溯到 John McCarthy 在 20世纪 60 年代早期在 MIT 开发的 Lisp 系统，它是诸如 Java，Perl 等现代语言系统的一个重要部分。接下来讨论 McCarthy 独创的 Mark&Sweep(标记 & 清除)算法。这个算法可以建立在已存在的 malloc 包的基础之上，为 C 和 C++ 程序提供垃圾收集。

垃圾收集器基本知识

垃圾收集器将内存视为一张有向可达图(reachability graph)，如下图所示：

IMG_AA00E2AD75D9-1

该图被分为一组根节点(root node)和一组堆节点(heap node)。每个堆节点对应于堆中的一个已分配块。有向边 p -> q意味着块 p 中的某个位置指向块 q 中的某个位置。根节点对应于这样一种不在堆中的位置，它们包含指向堆中的指针。

当存在任意根节点出发到达 p 的有向路径时，称节点 p 是可达的(reachable)。在任何时刻，不可达节点称为垃圾。垃圾收集器的作用就是维护可达图的某种表示，并通过释放不可达节点且将它们返回给空闲链表，来定期回收它们。

像 Java 这种语言，对应用如何创建和使用指针有很严格的控制，能够维护可达图的一种精确表示，因此能回收所有垃圾。

对于 C 和 C++ 这样的语言的收集器通常不能维持可达图的精确表示，这样的收集器叫做保守的收集器，即每个可达块都被正确地标记为可达了，而一些不可达节点确可能被错误的标记为可达。

收集器可以按需提供它们的服务，也可以和应用并行的独立线程，不断地更新可达图和回收垃圾。例如下图：考虑如何将一个 C 程序的保守的收集器加入到已存在的 malloc 包中。

IMG_8064FB70CB76-1

无论何时需要堆空间，应用都会调用 malloc ，当空闲块不够用时，就启动垃圾收集器，回收不使用的堆块。如果回收空闲块之后还是不够用，就向操作系统要求额外的内存。执行成功返回指向请求块的指针，失败返回空指针。

Mark & Sweep 垃圾收集器

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

Mark & Sweep 使用以下函数：ptr 定义为 typedef void* ptr

1
2
3
4
5
6
7
ptr isPtr(ptr p)；          // 如果 p 指向已分配块中的某个字，返回指向这个块的起始位置的指针 b，否则返回 NULLL
int blockMarked(ptr b);     // 如果块 b 是已标记的，就返回 true
int blockAllocated(ptr b)   // 如果块 b 是已分配的，就返回 true
void markBlock（ptr b）      // 标记块 b
int length(b)               // 返回块 b 的以字(4 字节)为单位的长度，不包括头部
void unmarkBlock(ptr b)     // 将 b 的状态由已标记的改为未标记的
ptr nextBlock(ptr b)        // 返回堆中块 b 的后继
1
2
3
4
5
6
7
8
9
10
11
void mark(ptr p){
  	if((b=isPtr(p))== NULL){
      	return;
    }
  	if(blockMarked(b))
      	return;
  	len = length(b);
  	for(int i=0; i<len; ++i){
      	mark(b[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
void sweep(ptr b, ptr end){
		while(b<end){
				if(blockMarked(b)){
          	unmarkBlock(b);
        }else if(blockAllocated(b)){
          	free(b);
        }
      	b = nextBlock(b);
		}
  	return;
}

标记阶段为每个根节点调用 mark 函数，如果 p 不指向一个已分配并且未被标记的堆块，mark 函数就立即返回，否则就标记这个块，并对块中每个字递归调用自己。每次调用 mark 函数都标记某个根节点的所有未标记并且可达的后继节点。在清除节点，任何未被标记的节点都被认为是不可达的，应当被清除。

IMG_20E282EC8C41-1

C 程序的保守 Mark & Sweep

Mark & Sweep 对 C程序的垃圾收集是一种合适的方法，它可以就地工作，而不需要移动任何块，然而C 语言中 isPtr 函数的实现具有一定的挑战：

  • C 不会用任何类型信息来标记内存位置，因此对于 isPtr 没有一种明显的方式来判断它的输入参数 p 是不是一个指针。
  • 即使我们知道 p 是一个指针，对 isPtr 也没有明显的方式来判断 p 是否指向一个已分配块的有效载荷中的某个位置。

对于第二个问题，解决方案就是将已分配块集合维护成一棵平衡二叉树，这棵树保持以下属性：左子树的所有块都放在较小的地址处，而右子树的所有块都放在较大的地址处。这就要求每个已分配块的头部里有两个附加字段(left 和 right)，每个字段指向某个已分配块的头部。isPtr (ptr p) 用树来执行对已分配块的二分查找，它依赖于块头部中的大小字段来判断 p 是否落在这个块的范围之内。如下图所示：

IMG_A93B7D3E642F-1

这种方式从某种意义讲是保守的，因为它可能不正确地标记实际上不可达的块，因此它可能不正确地标记实际上不可达的块，因此它可能不会释放某些垃圾。比如： C语言不会用类型信息来标记内存位置。因此，像 int 或者 float 这样的标量可以伪装成指针，例如，某个可达的已分配块在它的有效载荷中包含一个 int，其值碰巧对应于某个已分配块 b 的有效载荷中的一个地址。对收集器而言，没有办法判断这个数据实际上是 int 而不是指针。因此，分配器必须保守地将块 b 标记为可达，尽管事实上它可能不可达。