视频地址：

http://player.bilibili.com/player.html?aid=31289365&bvid=BV1iW411d7hd&cid=161460550&page=20

课件地址：

本章对应于书中的9.10~9.11。

在上一章中介绍了显示分配器要求应用程序显示地调用free函数来释放已分配块，比如以下代码中在garbage函数中调用了malloc函数来分配块，但是函数返回时并没进行释放，使得p指向的分配块始终保持已分配的状态，则分配器就无权对该分配块进行操作，由于p保存在函数garbage的栈帧中，当garbage返回时也丢失了p，所以这个已分配块就变成了垃圾，无法被使用，直到程序终止。

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

而在隐式分配器中，分配器会释放程序不再使用的已分配块，自动对其调用free函数进行释放。则应用程序只需要显示分配自己需要的块，而回收过程由分配器自动完成。

本章主要介绍Mark&Sweep算法，它建立在malloc包的基础上，使得C和C++就有垃圾收集的能力。

1 垃圾收集器

1.1 基础知识

垃圾收集器将内存视为一个有向可达图（Reachability Graph），其中具有两种节点：

• **根节点（Root Node）：**对应于不在堆中但包含指向堆中的指针，可以是寄存器、栈中变量或全局变量等等。
• **堆节点（Heap Node）：**对应于堆中的一个已分配的块。

有向边 $p \rightarrow q$ 表示p中的某个位置指向q中的某个位置，说明p需要q的存在。我们可以从根节点触发找到所有可达的节点，则剩下的不可达的节点就是垃圾，因为不存在使用这些不可达节点的入口，应用程序无法再次访问这些不可达的已分配块。垃圾收集器就是在维护这样一个有向可达图，并释放不可达节点。