Skip to content
English

12.2 - 栈和堆

Key Takeaway

一个程序的内存可以被分为几个不同的区域，称为内存段：

  • 代码段(code段) (也称为 text 段)，编译后的程序就位于该段。代码段通常是只读的；
  • bss段 (也称为未初始化数据段)，这里存放0初始化的全局变量和静态变量；
  • 数据段(也称为初始化数据段)，这里存放初始化的全局变量和静态变量；
  • 堆：动态变量的内存是从堆中分配的；
  • 栈：形参、局部变量和其他函数相关的信息都存放在这里。

本节课，我们将主要关注堆和栈，它们是这几个内存段中最”有意思“的。

堆内存段

堆段(也称为“自由存储区”)跟踪用于动态内存分配的内存。我们已经在 11.11 - 使用 new 和 delete 进行动态内存分配 中介绍了堆，所以这里只是复习一下：

在 C++ 中，当你使用 new 分配内存时，该内存就会位于堆段。

1
2
int* ptr { new int }; // ptr is assigned 4 bytes in the heap
int* array { new int[10] }; // array is assigned 40 bytes in the heap

该内存的地址通过操作符new返回，然后可以存储在指针中。你不必担心定位空闲内存并将其分配给用户的底层机制。然而，你需要知道的是，连续内存请求可能不会分配连续的内存地址！

1
2
3
int* ptr1 { new int };
int* ptr2 { new int };
// ptr1 and ptr2 may not have sequential addresses

当动态分配的变量被删除时，内存被“返回”到堆中，然后可以在接收到未来的分配请求时重新分配。请记住，删除指针并不删除变量，它只是将相关地址的内存返回给操作系统。

堆有优点和缺点：

  • 在堆上分配内存相对很慢；
  • 已分配的内存一直保持分配状态，直到它被特别地释放(注意内存泄漏)或应用程序结束(这时操作系统应该清理它)；
  • 动态分配的内存必须通过指针访问。解引用指针比直接访问变量比较慢；
  • 因为堆是一个很大的内存池，所以可以在这里分配大型数组、结构或类。

调用栈

调用栈所扮演的角色更加有意思。调用栈会追踪所有活动函数（已经被调用但尚未结束）从开始到当前时间点的信息，并且负责为函数形参和局部变量分配内存。

调用栈使用数据结构——栈实现。所以在讨论调用栈的工作原理之前，我们必须要指定栈是一种什么样的数据结构。

数据结构——栈

数据结构是一种组织数据以便有效地使用数据的编程机制，你已经了解了几种类型的数据结构，例如数组和结构体。这两种数据结构都提供了有效地存储数据和访问数据的机制。还有许多在编程中经常使用的附加数据结构，其中相当一部分是在标准库中实现的，栈就是其中之一。

想想自助餐厅里的一叠盘子。因为每个盘子都很重，而且它们是堆叠的，所以你实际上只能做三件事中的一件:

  1. 看到最顶层盘子的表面；
  2. 拿走最上面一个盘子（漏出下面一个盘子）；
  3. 将一个新的盘子放在最上面（遮蔽下面一个盘子）。

在计算机编程中，栈是一种容纳多个变量的容器数据结构(很像数组)。然而，数组允许你按任何顺序访问和修改元素(称为随机访问)，而栈则有更多的限制。可以在堆栈上执行的操作对应于上面提到的三件事：

  1. 查看栈顶元素(通常通过top()函数或peek())；
  2. 获取并移除栈顶元素(通过pop()完成)；
  3. 将一个新元素放置在栈顶(通过push()完成)。

栈是一个后入先出(LIFO)的数据结构。最后被压入栈的元素会第一个被弹出。如果你将一个新的盘子放在盘子堆顶上的话，那你第一个拿走的盘子也只能是它。当新的元素被压入栈时，栈就会增长。当元素被移除时，则栈会收缩。

例如，下面是一个简短的序列，展示了栈上的push和pop是如何工作的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

对于调用栈是如何工作的，盘子类比是一个非常好的类比，但我们可以做一个更好的类比。考虑一堆邮箱，它们都堆叠在一起。每个邮箱只能装一件物品，而且所有邮箱都是空的。此外，每个邮箱都固定在它下面的邮箱上，因此邮箱的数量不能更改。如果不能更改邮箱的数量，如何获得类似于堆栈的行为?

首先，我们使用一个标记(比如便利贴)来跟踪最下面的空邮箱的位置。在开始时，这将是最低的邮箱(在堆栈的底部)。当我们将一个项目推入邮箱堆栈时，我们将它放入有标记的邮箱中(即第一个空邮箱)，并将标记向上移动一个邮箱。当我们从堆栈中弹出一个项目时，我们将标记向下移动一个邮箱(因此它指向顶部的非空邮箱)，并从该邮箱中删除该项目。任何低于标记的东西都被认为是“在栈上”。标记处或标记上方的任何东西都不在栈上。

调用栈内存段

调用栈内存段保存用于调用栈的内存。当应用程序启动时，main()函数被操作系统压到调用栈上。然后程序开始执行。

函数调用时将函数压入调用栈。当当前函数结束时，该函数从调用栈中弹出。因此，通过查看压入调用栈上的函数，我们可以看到为到达当前执行点而调用的所有函数。

邮箱的比喻很好地描述了调用栈的工作原理。栈本身是一段固定长度的内存。邮箱可以被看做是内存地址，而压入或弹出的内容称为栈帧。栈帧追踪和某个函数调用相关的全部数据。比喻中的“标记”是一个被称为堆栈指针(SP)的寄存器(CPU中的一小块内存)。堆栈指针用于追踪当前的栈顶位置。

我们还可以进一步优化：当从调用栈中弹出内容的时候，我们并不需要实际清理或清零被弹出的栈帧——只需要将栈顶指针向下移动即可。相应的内容已经不被认为是栈的一部分了（栈指针会在该地址或该地址的下方），所以它也不会被寻址。如果稍后我们将新的栈帧压入了该内存地址，则其内容正好就被覆盖掉了。

调用栈实例

让我们更详细地研究调用栈是如何工作的。下面是调用函数时的步骤：

  1. 程序中发生函数调用；
  2. 栈帧被构建并压入调用栈。栈帧包括：
    • 函数调用后指令的地址（返回地址）。CPU通过它知道函数退出时应该返回到的地址；
    • 所有函数的实参；
    • 所有局部变量的内存；
    • 保存被函数修改且需要在函数返回时恢复的寄存器
  3. CPU 跳转到函数起点；
  4. 函数中的指令开始被执行。

当函数结束时，会执行下面的步骤：

  1. 寄存器从调用栈恢复；
  2. 栈帧弹出调用栈。此时会释放局部变量和实参的内存；
  3. 处理返回值；
  4. CPU继续从返回地址执行。

根据计算机的体系结构的不同，可以有许多不同的方法处理返回值。有些体系结构将返回值作为堆栈框架的一部分，其他则使用CPU寄存器。

通常，了解调用堆栈如何工作的所有细节并不重要。但是，了解函数在调用时被有效地推入堆栈，在返回时弹出，可以帮助您了解递归所需的基础知识，以及在调试时有用的其他一些概念。

提示：在某些体系结构上，调用堆栈从内存地址0增长。在其他情况下，它会向内存地址0增长。因此，新推的堆栈帧可能比以前的栈帧有更高或更低的内存地址。

一个简单的调用栈例子

考虑下面这个简单的应用程序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int foo(int x)
{
    // b
    return x;
} // foo is popped off the call stack here

int main()
{
    // a
    foo(5); // foo is pushed on the call stack here
    // c

    return 0;
}

在对应调用栈标记点处看起来是这样的：

a:

1
main()

b:

1
2
foo() (including parameter x)
main()

c:

1
main()

堆栈溢出

栈的大小是有限的，因此它只能保存有限的信息。对于Windows上的Visual Studio 来说，栈的默认大小为 1MB。而对于Linux上的 g++/Clang，栈的默认大小为8MB。如果程序视图在栈上保存过多的信息，就会导致堆栈溢出。当栈上的所有内存都被分配出去时，就会发生堆栈溢出——这种情况下，再次分配的内存就会溢出到其他内存段。

堆栈溢出的主要原因是在栈上分配了过多的变量，或者执行了过多的函数调用（函数A调用函数B调用函数C调用函数D等等）。对于现代操作系统来说，堆栈溢出会导致操作系统报告非法访问并终止程序。

下面这个程序就有可能导致堆栈溢出。你可以在你的系统上试试看程序会不会崩溃：

1
2
3
4
5
6
7
8
9
#include <iostream>

int main()
{
    int stack[10000000];
    std::cout << "hi" << stack[0]; // we'll use stack[0] here so the compiler won't optimize the array away

    return 0;
}

这个程序试图在堆栈上分配一个巨大的(可能是40MB)数组。因为堆栈不够大，无法处理这个数组，数组分配溢出到程序不允许使用的内存部分。

在 Windows (Visual Studio) 上，程序运行结果为：

1
HelloWorld.exe (process 15916) exited with code -1073741571.

-1073741571 等于十六进制的 c0000005 ，它在 Windows 中表示非法访问。注意“hi”并没有被打印出来，因为还没到这一步程序就崩溃了。

下面是另一个程序，它会因为不同的原因导致堆栈溢出：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>

void foo()
{
    foo();
    std::cout << "hi";
}

int main()
{
    foo();

    return 0;
}

在上面的程序中，每次调用函数foo()时，栈帧都会被推入堆栈。因为foo()无限地调用自身，最终栈将耗尽内存并导致溢出。

栈的优缺点：

  • 在栈上分配内存相对较快；
  • 在栈上分配的内存只要在作用域就会一直在栈上，在弹出栈时会被释放；
  • 所有在栈上分配的内存都是在编译时就已知的，因此这些内存可以通过变量直接访问；
  • 因为栈相对来说很小，所以在栈上分配大量的内存是不明智的。这其中就包括创建很大的局部变量数组或大型结构体。

作者注

此评论有一些附加的(简化的)信息，关于堆栈上的变量是如何布局的，以及在运行时如何接收实际的内存地址。