内存管理基础

程序可执行文件的结构

一个程序的可执行文件在内存中的结果，从大的角度可以分为两个部分：只读部分和可读写部分。只读部分包括程序代码（.text）和程序中的常量（.rodata）。可读写部分（也就是变量）大致可以分成下面几个部分：

  • .data： 初始化了的全局变量和静态变量
  • .bss： 即 Block Started by Symbol， 未初始化的全局变量和静态变量（这个我感觉上课真的没讲过啊我去。。。）
  • heap： 堆，使用 malloc, realloc, 和 free 函数控制的变量，堆在所有的线程，共享库，和动态加载的模块中被共享使用
  • stack： 栈，函数调用时使用栈来保存函数现场，自动变量（即生命周期限制在某个 scope 的变量）也存放在栈中。

下面就各个分区具体解释一下：

data 和 bss 区

这两个区经常放在一起说，因为他们都是用来存储全局变量和静态变量的，区别在于 data 区存放的是初始化过的， bss 区存放的是没有初始化过的，例如：

  1. int val = 3;
  2. char string[] = "Hello World";

这两个变量的值会一开始被存储在 .text 中（因为值是写在代码里面的），在程序启动时会拷贝到 .data 去区中。

而不初始化的话，像下面这样：

  1. static int i;

这个变量就会被放在 bss 区中。

答疑一 静态变量和全局变量

这两个概念都是很常见的概念，又经常在一起使用，很容易造成混淆。

全局变量：在一个代码文件（具体说应该一个 translation unit/compilation unit)）当中，一个变量要么定义在函数中，要么定义在在函数外面。当定义在函数外面时，这个变量就有了全局作用域，成为了全局变量。全局变量不光意味着这个变量可以在整个文件中使用，也意味着这个变量可以在其他文件中使用（这种叫做 external linkage）。当有如下两个文件时；

a.c

  1. #include <stdio.h>
  3. int a;
  5. int compute(void);
  7. int main()
  8. {
  9.     a = 1;
  10.     printf("%d %d\n", a, compute());
  11.     return 0;
  12. }

b.c

  1. int a;
  3. int compute(void)
  4. {
  5.     a = 0;
  6.     return a;
  7. }

在 Link 过程中会产生重复定义错误，因为有两个全局的 a 变量，Linker 不知道应该使用哪一个。为了避免这种情况，就需要引入 static。

静态变量： 指使用 static 关键字修饰的变量，static 关键字对变量的作用域进行了限制，具体的限制如下：

  • 在函数外定义：全局变量，但是只在当前文件中可见（叫做 internal linkage）
  • 在函数内定义：全局变量，但是只在此函数内可见（同时，在多次函数调用中，变量的值不会丢失）
  • （C++）在类中定义：全局变量，但是只在此类中可见

对于全局变量来说，为了避免上面提到的重复定义错误，我们可以在一个文件中使用 static，另一个不使用。这样使用 static 的就会使用自己的 a 变量，而没有用 static 的会使用全局的 a 变量。当然，最好两个都使用 static，避免更多可能的命名冲突。

注意：’静态’这个中文翻译实在是有些莫名其妙，给人的感觉像是不可改变的，而实际上 static 跟不可改变没有关系，不可改变的变量使用 const 关键字修饰，注意不要混淆。

Bonus 部分 —— extern： extern 是 C 语言中另一个关键字，用来指示变量或函数的定义在别的文件中，使用 extern 可以在多个源文件中共享某个变量，例如这里的例子。 extern 跟 static 在含义上是“水火不容”的，一个表示不能在别的地方用，一个表示要去别的地方找。如果同时使用的话，有两种情况，一种是先使用 static，后使用 extern ，即：

  1. static int m;
  2. extern int m;

这种情况，后面的 m 实际上就是前面的 m 。如果反过来：

  1. extern int m;
  2. static int m;

这种情况的行为是未定义的，编译器也会给出警告。

答疑二 程序在内存和硬盘上不同的存在形式

这里我们提到的几个区，是指程序在内存中的存在形式。和程序在硬盘上存储的格式不是完全对应的。程序在硬盘上存储的格式更加复杂，而且是和操作系统有关的，具体可以参考这里。一个比较明显的例子可以帮你区分这个差别：之前我们提到过未定义的全局变量存储在 .bss 区，这个区域不会占用可执行文件的空间（一般只存储这个区域的长度），但是却会占用内存空间。这些变量没有定义，因此可执行文件中不需要存储（也不知道）它们的值，在程序启动过程中，它们的值会被初始化成 0 ，存储在内存中。

栈

栈是用于存放本地变量，内部临时变量以及有关上下文的内存区域。程序在调用函数时，操作系统会自动通过压栈和弹栈完成保存函数现场等操作，不需要程序员手动干预。

栈是一块连续的内存区域，栈顶的地址和栈的最大容量是系统预先规定好的。能从栈获得的空间较小。如果申请的空间超过栈的剩余空间时，例如递归深度过深，将提示stackoverflow。

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。

堆

堆是用于存放除了栈里的东西之外所有其他东西的内存区域，当使用malloc和free时就是在操作堆中的内存。对于堆来说，释放工作由程序员控制，容易产生memory leak。

堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，永远都不可能有一个内存块从栈中间弹出。

堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。

计算机底层并没有对堆的支持，堆则是C/C++函数库提供的，同时由于上面提到的碎片问题，都会导致堆的效率比栈要低。

内存分配

  • 虚拟地址：用户编程时将代码（或数据）分成若干个段，每条代码或每个数据的地址由段名称 + 段内相对地址构成，这样的程序地址称为虚拟地址
  • 逻辑地址：虚拟地址中，段内相对地址部分称为逻辑地址

  • 物理地址：实际物理内存中所看到的存储地址称为物理地址

  • 逻辑地址空间：在实际应用中，将虚拟地址和逻辑地址经常不加区分，通称为逻辑地址。逻辑地址的集合称为逻辑地址空间

  • 线性地址空间：CPU地址总线可以访问的所有地址集合称为线性地址空间

  • 物理地址空间：实际存在的可访问的物理内存地址集合称为物理地址空间

  • MMU(Memery Management Unit内存管理单元)：实现将用户程序的虚拟地址（逻辑地址） → 物理地址映射的CPU中的硬件电路

  • 基地址：在进行地址映射时，经常以段或页为单位并以其最小地址（即起始地址）为基值来进行计算
  • 偏移量：在以段或页为单位进行地址映射时，相对于基地址的地址值

虚拟地址先经过分段机制映射到线性地址，然后线性地址通过分页机制映射到物理地址。

虚拟内存

  • 请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入

页面置换算法

  • FIFO算法

    先入先出，即淘汰最早调入的页面。

  • OPT(MIN)算法

    选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。

    可惜，MIN需要知道将来发生的事，只能在理论中存在，实际不可应用。

  • LRU(Least-Recently-Used)算法

    用过去的历史预测将来，选最近最长时间没有使用的页淘汰(也称最近最少使用)。

    LRU准确实现：计数器法，页码栈法。

    由于代价较高，通常不使用准确实现，而是采用近似实现，例如Clock算法。

内存抖动现象：页面的频繁更换，导致整个系统效率急剧下降，这个现象称为内存抖动（或颠簸）。抖动一般是内存分配算法不好，内存太小引或者程序的算法不佳引起的。

Belady现象：对有的页面置换算法，页错误率可能会随着分配帧数增加而增加。

FIFO会产生Belady异常。

栈式算法无Belady异常，LRU，LFU（最不经常使用），OPT都属于栈式算法。

参考资料