内存分配与垃圾回收

1. 操作系统内存模型简述

1.1 堆（heap）

程序运行的时候，操作系统会给它分配一段内存，用来储存程序和运行产生的数据。这段内存有起始地址和结束地址，比如从0x1000到0x8000，起始地址是较小的那个地址，结束地址是较大的那个地址。

程序运行过程中，对于动态的内存占用请求（比如新建对象，或者使用malloc命令），系统就会从可用的空闲内存中划出一部分给用户，具体规则是从起始地址开始划分（实际上，起始地址会有一段静态数据，这里忽略）。举例来说，用户要求得到10个字节内存，那么从起始地址0x1000开始给他分配，一直分配到地址0x100A，如果再要求得到22个字节，那么就分配到0x1020。

这种因为用户主动请求而划分出来的内存区域，叫做 Heap（堆）。它由起始地址开始，从低位（地址）向高位（地址）增长。Heap 的一个重要特点就是不会自动消失，必须手动释放，或者由垃圾回收机制来回收。

1.2 栈（stack）

除了 Heap 以外，其他的内存占用叫做 Stack（栈）。简单说，Stack 是由于函数运行而临时占用的内存区域。

请看下面的例子。

1
2
3
4


int main() {
   int a = 2;
   int b = 3;
}

上面代码中，系统开始执行main函数时，会为它在内存里面建立一个帧（frame），所有main的内部变量（比如a和b）都保存在这个帧里面。main函数执行结束后，该帧就会被回收，释放所有的内部变量，不再占用空间。

如果函数内部调用了其他函数，会发生什么情况？

1
2
3
4
5


int main() {
   int a = 2;
   int b = 3;
   return add_a_and_b(a, b);
}

上面代码中，main函数内部调用了add_a_and_b函数。执行到这一行的时候，系统也会为add_a_and_b新建一个帧，用来储存它的内部变量。也就是说，此时同时存在两个帧：main和add_a_and_b。一般来说，调用栈有多少层，就有多少帧。

等到add_a_and_b运行结束，它的帧就会被回收，系统会回到函数main刚才中断执行的地方，继续往下执行。通过这种机制，就实现了函数的层层调用，并且每一层都能使用自己的本地变量。

Stack 是由内存区域的结束地址开始，从高位（地址）向低位（地址）分配（所以栈顶是在下面一侧）。比如，内存区域的结束地址是0x8000，第一帧假定是16字节，那么下一次分配的地址就会从0x7FF0开始；第二帧假定需要64字节，那么地址就会移动到0x7FB0。

1.3 内存分配器

前面说了，由用户自行维护（包括申请和释放）的内存区域被称为堆。从分配器的角度来看，该区域将内存分为一组大小不同的块（block），每个块是一篇连续的虚拟内存（chunk），这些块要么是已分配的，要么是空闲的。已分配的内存用于程序运行，空闲的内存就是待分配的。

内存分配器有两种风格，这两种风格都要求应用显式地分配内存块，区别在于由哪个实体来负责释放已分配的块。

显示分配器（explicit allocator）：要求开发者显式地释放已分配的块。比如C程序通过调用malloc函数类分配内存，并通过调用free函数来释放内存。
隐式分配器（implicit allocator）：隐式分配器也叫垃圾收集器（garbage collector），自动释放未使用的已分配的内存块（这一过程就称之为垃圾回收）。通过垃圾回收机制，程序员不再需要手动管理内存。

2. 动态内存分配器

本节讨论的内容是显示分配器的设计与实现。

3. 垃圾收集

在一个支持垃圾回收的系统中，应用需显式分配堆内存，但是无需显式地释放它们，由垃圾收集器定期识别垃圾块，并相应地调用free，把这些块放回空闲链表中。垃圾回收的策略和算法有很多，本节的讨论仅局限于Mark&Sweep（标记清除）算法，该算法可以在已存在的 malloc/free 的基础之上，为C/C++程序提供垃圾收集。

3.1 基础知识

垃圾收集器将内存视为一张有向可达图（reachability graph），如下图所示。该图的节点被分成一组根节点（root node）和一组堆节点（heap node）。每个堆节点对应于堆中的一个已分配块。有向边 p→q 意味着块 p 中的某个位置指向块 q 中的某个位置。根节点对应于这样一种不在堆中的位置，它们中包含指向堆中的指针。这些位置可以是寄存器、栈里的变量，或者是虚拟内存中读写数据区域内的全局变量。

当存在一条从任意根节点出发并到达 p 的有向路径时，我们说节点 p 是可达的（reachable）。在任何时刻，不可达节点对应于垃圾，是不能被应用再次使用的。垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点且将它们返回给空闲链表，来定期地回收它们。

3.2 Mark&Sweep 垃圾收集器

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

我们对 Mark&Sweep 的描述将假设使用下列函数，其中 ptr 定义为 typedef void* ptr：

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

标记阶段为每个根节点调用一次 mark 函数，如下所示。如果 p 不指向一个已分配并且未标记的堆块，mark 函数就立即返回。否则，它就标记这个块，并对块中的每个字递归地调用它自己（注：相当于一个深度遍历）。每次对 mark 函数的调用都标记某个根节点的所有未标记并且可达的后继节点。在标记阶段的末尾，任何未标记的已分配块都被认定为是不可达的，是垃圾，可以在清除阶段回收。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// mark 伪代码
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;
}

清除阶段是对 sweep 函数的一次调用，如下所示。sweep 函数在堆中每个块上反复循环，释放它所遇到的所有未标记的已分配块（也就是垃圾）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// sweep 伪代码
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&Sweep 的图形化解释（注意这个示例中的箭头表示内存引用，而不是空闲链表指针）。块边界用粗线条表示。每个方块对应于内存中的一个字。每个块有一个字的头部，要么是已标记的，要么是未标记的。

初始情况下，图中的堆由六个已分配块组成，其中每个块都是未分配的。第 3 块包含一个指向第 1 块的指针。第 4 块包含指向第 3 块和第 6 块的指针。根指向第 4 块。在标记阶段之后，第 1 块、第 3 块、第 4 块和第 6 块被做了标记，因为它们是从根节点可达的。第 2 块和第 5 块是未标记的，因为它们是不可达的。在清除阶段之后，这两个不可达块被回收到空闲链表。

参考：

《深入理解计算机系统》第9章

文章目录