• 内存管理基础
    • 程序可执行文件的结构
      • 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>
    2. int a;
    3. int compute(void);
    4. int main()
    5. {
    6. a = 1;
    7. printf("%d %d\n", a, compute());
    8. return 0;
    9. }

    b.c

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

    在 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。

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

    堆是用于存放除了栈里的东西之外所有其他东西的内存区域,当使用mallocfree时就是在操作堆中的内存。对于堆来说,释放工作由程序员控制,容易产生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