• 内存管理基础
    • 程序可执行文件的结构
      • data 和 bss 区
    • 栈
    • 堆
  • 内存分配
  • 虚拟内存
    • 页面置换算法
      • 参考资料

    内存管理基础

    程序可执行文件的结构

    一个程序的可执行文件在内存中的结果，从大的角度可以分为两个部分：只读部分和可读写部分。只读部分包括程序代码（.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都属于栈式算法。

    参考资料

    • https://en.wikipedia.org/wiki/Data_segment
    • https://stackoverflow.com/questions/12798486/bss-segment-in-c/12799389#12799389
    • https://stackoverflow.com/questions/7837190/c-c-global-vs-static-global
    • https://stackoverflow.com/questions/572547/what-does-static-mean-in-a-c-program/572550#572550