程序是在内存中运行的，一名合格的程序员必须了解内存，一名不了解内存的程序员，注定不能让自己的编程水平有一个质的飞越，只能雾里看花，知其然不知其所以然。

1、一个程序在计算机中到底是如何运行的？

程序是保存在硬盘中的，要载入内存才能运行，CPU也被设计为只能从内存中读取数据和指令。

对于CPU来说，内存仅仅是一个存放指令和数据的地方，并不能在内存中完成计算功能，例如要计算 a = b + c，必须将 a、b、c 都读取到CPU内部才能进行加法运算。为了了解具体的运算过程，我们不妨先来看一下CPU的结构。

CPU是一个复杂的计算机部件，它内部又包含很多小零件，如下图所示：

运算单元是CPU的大脑，负责加减乘除、比较、位移等运算工作，每种运算都有对应的电路支持，速度很快。

寄存器（Register）是CPU内部非常小、非常快速的存储部件，它的容量很有限，对于32位的CPU，每个寄存器一般能存储32位（4个字节）的数据，对于64位的CPU，每个寄存器一般能存储64位（8个字节）的数据。为了完成各种复杂的功能，现代CPU都内置了几十个甚至上百个的寄存器，嵌入式系统功能单一，寄存器数量较少。

我们经常听说多少位的CPU，指的就是寄存器的的位数。现在个人电脑使用的CPU已经进入了64位时代，例如 Intel 的 Core i3、i5、i7 等。

寄存器在程序的执行过程中至关重要，不可或缺，它们可以用来完成数学运算、控制循环次数、控制程序的执行流程、标记CPU运行状态等。

例如：EIP（Extern Instruction Pointer ）寄存器的值是下一条指令的地址，CPU执行完当前指令后，会根据 EIP 的值找到下一条指令，改变 EIP 的值，就会改变程序的执行流程；CR3 寄存器保存着当前进程页目录的物理地址，切换进程就会改变 CR3 的值，这将在《MMU部件以及对内存权限的控制》中讲解；EBP、ESP 寄存器用来指向栈的底部和顶部，函数调用会改变 EBP 和 ESP 的值，这将在《栈的概念以及栈溢出》中讲解。

那么， 在CPU内部为什么又要设置缓存呢？

虽然内存的读取速度已经很快了，但是和CPU比起来，还是有很大差距的，不是一个数量级的，如果每次都从内存中读取数据，会严重拖慢CPU的运行速度，CPU经常处于等待状态，无事可做。在CPU内部设置一个缓存，可以将使用频繁的数据暂时读取到缓存，需要同一地址上的数据时，就不用大老远地再去访问内存，直接从缓存中读取即可。

大家在购买CPU时，也会经常关心缓存容量，例如 Intel Core i7 3770K 的三级缓存为 8MB，二级缓存为 256KB，一级缓存为 32KB。容量越大，CPU越强悍。

缓存的容量是有限的，CPU只能从缓存中读取到部分数据，对于使用不是很频繁的数据，会绕过缓存，直接到内存中读取。所以不是每次都能从缓存中得到数据，这就是缓存的命中率，能够从缓存中读取就命中，否则就没命中。关于缓存的命中率又是一门学问，哪些数据保留在缓存，哪些数据不保留，都有复杂的算法。

CPU指令
要想让CPU工作，必须借助特定的指令，例如 add 用于加法运算，sub 用于除法运算，cmp 用于比较两个数的大小，这称为CPU的指令集（Instruction Set）。我们的C语言代码最终也会编译成一条一条的CPU指令。不同型号的CPU支持的指令集会有所差异，但绝大部分是相同的。

本节我们讲解了CPU的简单构造以及CPU指令，重点是让大家认识寄存器这个小而快速的存储部件，它在程序运行过程中起着至关重要的作用，CPU就是用它来记录程序的运行状态，然后根据它的值再决定下一步的操作。

2、虚拟内存到底是什么？

在C语言中，指针变量的值就是一个内存地址，&运算符的作用也是取变量的内存地址，请看下面的代码：

代码中的 a、b 是全局变量，它们的内存地址在链接时就已经决定了，以后再也不能改变，该程序无论在何时运行，结果都是一样的。

那么问题来了，如果物理内存中的这两个地址被其他程序占用了怎么办，我们的程序岂不是无法运行了？

幸运的是，这些内存地址都是假的，不是真实的物理内存地址，而是虚拟地址。虚拟地址通过CPU的转换才能对应到物理地址，而且每次程序运行时，操作系统都会重新安排虚拟地址和物理地址的对应关系，哪一段物理内存空闲就使用哪一段。如下图所示：

虚拟地址

虚拟地址的整个想法是这样的：把程序给出的地址看做是一种虚拟地址（Virtual Address），然后通过某些映射的方法，将这个虚拟地址转换成实际的物理地址。这样，只要我们能够妥善地控制这个虚拟地址到物理地址的映射过程，就可以保证程序每次运行时都可以使用相同的地址。

例如，上面代码中变量 a 的地址是 0X404038，第一次运行时它对应的物理内存地址可能是 0X12ED90AA，第二次运行时可能又对应 0XED90，而我们的程序不需要关心这些，这些繁杂的内存管理工作交给操作系统处理即可。

让我们回到程序的运行本质上来。用户程序在运行时不希望介入到这些复杂的内存管理过程中，作为普通的程序，它需要的是一个简单的执行环境，有自己的内存，有自己的CPU，好像整个程序占有整个计算机而不用关心其他的程序。

除了在编程时可以使用固定的内存地址，给程序员带来方便外，使用虚拟地址还能够使不同程序的地址空间相互隔离，提高内存使用效率。

使不同程序的地址空间相互隔离

如果所有程序都直接使用物理内存，那么程序所使用的地址空间不是相互隔离的。恶意程序可以很容易改写其他程序的内存数据，以达到破坏的目的；有些非恶意、但是有 Bug 的程序也可能会不小心修改其他程序的数据，导致其他程序崩溃。

这对于需要安全稳定的计算机环境的用户来说是不能容忍的，用户希望他在使用计算机的时候，其中一个任务失败了，至少不会影响其他任务。

使用了虚拟地址后，程序A和程序B虽然都可以访问同一个地址，但它们对应的物理地址是不同的，无论如何操作，都不会修改对方的内存。

提高内存使用效率

使用虚拟地址后，操作系统会更多地介入到内存管理工作中，这使得控制内存权限成为可能。例如，我们希望保存数据的内存没有执行权限，保存代码的内存没有修改权限，操作系统占用的内存普通程序没有读取权限等。

另外，当物理内存不足时，操作系统能够更加灵活地控制换入换出的粒度，磁盘 I/O 是非常耗时的工作，这能够从很大程度上提高程序性能。

以上两点我们将在《内存分页机制》和《内存分页机制的实现》中进行详细讲解。

中间层思想

在计算机中，为了让操作更加直观、易于理解、增强用户体验，开发者经常会使用一件法宝——增加中间层，即使用一种间接的方式来屏蔽复杂的底层细节，只给用户提供简单的接口。虚拟地址是使用中间层的一个典型例子。

实际上，计算机的整个发展过程就是不断引入新的中间层：

• 计算机的早期，程序都是直接运行在硬件之上，自己负责硬件的管理工作；程序员也使用二进制进行编程，需要处理各种边界条件和安全问题。
• 后来人们不能忍受了，于是开发出了操作系统，让它来管理各种硬件，同时发明了汇编语言，减轻程序员的负担。
• 随着软件规模的不断增大，使用汇编语言编程开始变得捉襟见肘，不仅学习成本高，开发效率也很低，于是C语言诞生了。C语言编译器先将C代码翻译为汇编代码，再由汇编器将汇编代码翻译成机器指令。
• 随着计算机的发展，硬件越来越强大，软件越来越复杂，人们又不满足于使用C语言了，于是 C++、Java、C#、PHP 等现代化的编程语言诞生了。

3、虚拟地址空间以及编译模式

所谓虚拟地址空间，就是程序可以使用的虚拟地址的有效范围。虚拟地址和物理地址的映射关系由操作系统决定，相应地，虚拟地址空间的大小也由操作系统决定，但还会受到编译模式的影响。

这节我们先讲解CPU，再讲解编译模式，让大家了解编译器是如何配合CPU来提高程序运行速度的。

CPU的数据处理能力

CPU是计算机的核心，决定了计算机的数据处理能力和寻址能力，也即决定了计算机的性能。CPU一次（一个时钟内）能处理的数据的大小由寄存器的位数和数据总线的宽度（也即有多少根数据总线）决定，我们通常所说的多少位的CPU，除了可以理解为寄存器的位数，也可以理解数据总线的宽度，通常情况下它们是相等的。

数据总线位于主板之上，不在CPU中，也不由CPU决定，严格来讲，这里应该说CPU能够支持的数据总线的最大根数，也即能够支持的最大数据处理能力，为了表达方便，本文才使用“CPU的数据总线”这一说法。

数据总线和主频都是CPU的重要指标：数据总线决定了CPU单次的数据处理能力，主频决定了CPU单位时间内的数据处理次数，它们的乘积就是CPU单位时间内的数据处理量。

我们常常听说，CPU主频在计算机的发展过程中飞速提升，从最初的几十 KHz，到后来的几百 MHz，再到现在的 4GHz，终于因为硅晶体的物理特性很难再提升，只能向多核方向发展。在这个过程中，CPU的数据总线宽度也在成倍增长，从早期的8位、16位，到后来的32位，现在我们计算机大部分都在使用64位CPU。

需要注意的是，数据总线和地址总线不是一回事，数据总线用于在CPU和内存之间传输数据，地址总线用于在内存上定位数据，它们之间没有必然的联系，宽度并不一定相等。实际情况是，地址总线的宽度往往随着数据总线的宽度而增长，以访问更大的内存。

16位CPU
早期的CPU是16位的，一次能处理 16Bit（2个字节）的数据。这个时候计算机产业还处在早期，个人电脑也没有进入千家万户，也没有提出虚拟地址的概念，程序还是直接运行在物理内存上，操作系统对内存的管理非常简陋，程序员轻易就能编写一个恶意程序去修改其他程序的内存。

学过汇编的同学应该知道，典型的16位处理器是 Intel 8086，它的数据总线有16根，地址总线有20根，寻址能力为 2^20 = 1MB。

32位CPU
随着计算机产业的进步，出现了32位的CPU，一次能处理 32Bit（4个字节）的数据。这个时候就提出了虚拟地址的概念，并被应用到CPU和操作系统中，由它们共同完成虚拟地址和物理地址的映射，这使得程序编写更加容易，运行更加安全。

典型的32位处理器是 Intel 的 80386 和 Intel Pentium 4（奔腾4）：80386 的数据总线和地址总线宽度都是32位，寻址能力达4GB；Pentium 4的地址总线宽度是36位，理论寻址能力达64GB。

64位CPU
现代计算机都使用64位的CPU，它们一次能处理64Bit（8个字节）的数据。典型的64位处理器是 Intel 的 Core i3、i5、i7 等，它们的地址总线宽度为 40~50 位左右。64位CPU的出现使个人电脑再次发生了质的飞跃。

实际支持的物理内存
CPU支持的物理内存只是理论上的数据，实际应用中还会受到操作系统的限制，例如，Win7 64位家庭版最大仅支持8GB或16GB的物理内存，Win7 64位专业版或企业版能够支持到192GB的物理内存。

Windows Server 2003 数据中心版专为大型企业或国家机构而设计，可以处理海量数据，分为32位版和64位版，32位版最高支持512GB的物理内存，这显然超出了32位CPU的寻址能力，可以通过两次寻址来实现。

编译模式

为了兼容不同的平台，现代编译器大都提供两种编译模式：32位模式和64位模式。

32位编译模式

在32位模式下，一个指针或地址占用4个字节的内存，共有32位，理论上能够访问的虚拟内存空间大小为 2^32 = 0X100000000 Bytes，即4GB，有效虚拟地址范围是 0 ~ 0XFFFFFFFF。

也就是说，对于32位的编译模式，不管实际物理内存有多大，程序能够访问的有效虚拟地址空间的范围就是0 ~ 0XFFFFFFFF，也即虚拟地址空间的大小是 4GB。换句话说，程序能够使用的最大内存为 4GB，跟物理内存没有关系。

如果程序需要的内存大于物理内存，或者内存中剩余的空间不足以容纳当前程序，那么操作系统会将内存中暂时用不到的一部分数据写入到磁盘，等需要的时候再读取回来。而我们的程序只管使用 4GB 的内存，不用关心硬件资源够不够。

如果物理内存大于 4GB，例如目前很多PC机都配备了8GB的内存，那么程序也无能为力，它只能够使用其中的 4GB。

64位编译模式

在64位编译模式下，一个指针或地址占用8个字节的内存，共有64位，理论上能够访问的虚拟内存空间大小为 2^64。这是一个很大的值，几乎是无限的，就目前的技术来讲，不但物理内存不可能达到这么大，CPU的寻址能力也没有这么大，实现64位长的虚拟地址只会增加系统的复杂度和地址转换的成本，带不来任何好处，所以 Windows 和 Linux 都对虚拟地址进行了限制，仅使用虚拟地址的低48位（6个字节），总的虚拟地址空间大小为 2^48 = 256TB。

需要注意的是：

• 32位的操作系统只能运行32位的程序（也即以32位模式编译的程序），64位操作系统可以同时运行32位的程序（为了向前兼容，保留已有的大量的32位应用程序）和64位的程序（也即以64位模式编译的程序）。
• 64位的CPU运行64位的程序才能发挥它的最大性能，运行32位的程序会白白浪费一部分资源。
• 目前计算机可以说已经进入了64位的时代，之所以还要提供32位编译模式，是为了兼容一些老的硬件平台和操作系统，或者某些场合下32位的环境已经足够，使用64位环境会增大成本，例如嵌入式系统、单片机、工控等。

这里所说的32位环境是指：32位的CPU + 32位的操作系统 + 32位的程序。

另外需要说明的是，32位环境拥有非常经典的设计，易于理解，适合教学，现有的很多资料都是以32位环境为基础进行讲解的。本教程也是如此，除非特别指明，否则都是针对32位环境。相比于32位环境，64位环境的设计思路并没有发生质的变化，理解了32环境很容易向64位环境迁移。

4、内存对齐，提高寻址效率

计算机内存是以字节（Byte）为单位划分的，理论上CPU可以访问任意编号的字节，但实际情况并非如此。

CPU 通过地址总线来访问内存，一次能处理几个字节的数据，就命令地址总线读取几个字节的数据。32 位的 CPU 一次可以处理4个字节的数据，那么每次就从内存读取4个字节的数据；少了浪费主频，多了没有用。64位的处理器也是这个道理，每次读取8个字节。

以32位的CPU为例，实际寻址的步长为4个字节，也就是只对编号为 4 的倍数的内存寻址，例如 0、4、8、12、1000 等，而不会对编号为 1、3、11、1001 的内存寻址。如下图所示：

这样做可以以最快的速度寻址：不遗漏一个字节，也不重复对一个字节寻址。

对于程序来说，一个变量最好位于一个寻址步长的范围内，这样一次就可以读取到变量的值；如果跨步长存储，就需要读取两次，然后再拼接数据，效率显然降低了。

例如一个 int 类型的数据，如果地址为 8，那么很好办，对编号为 8 的内存寻址一次就可以。如果编号为 10，就比较麻烦，CPU需要先对编号为 8 的内存寻址，读取4个字节，得到该数据的前半部分，然后再对编号为 12 的内存寻址，读取4个字节，得到该数据的后半部分，再将这两部分拼接起来，才能取得数据的值。

将一个数据尽量放在一个步长之内，避免跨步长存储，这称为内存对齐。在32位编译模式下，默认以4字节对齐；在64位编译模式下，默认以8字节对齐。

为了提高存取效率，编译器会自动进行内存对齐.

5、内存分页机制，完成虚拟地址的映射

关于虚拟地址和物理地址的映射有很多思路，我们可以假设以程序为单位，把一段与程序运行所需要的同等大小的虚拟空间映射到某段物理空间。

例如程序A需要 10MB 内存，虚拟地址的范围是从 0X00000000 到 0X00A00000，假设它被映射到一段同等大小的物理内存，地址范围从 0X00100000 到 0X00B00000，即虚拟空间中的每一个字节对应于物理空间中的每一个字节。

程序运行时，它们的对应关系如下图所示：

当程序A需要访问 0X00001000 时，系统会将这个虚拟地址转换成实际的物理地址 0X00101000，访问 0X002E0000 时，转换成 0X003E0000，以此类推。

这种以整个程序为单位的方法很好地解决了不同程序地址不隔离的问题，同时也能够在程序中使用固定的地址。

地址隔离

如上图所示，程序A和程序B分别被映射到了两块不同的物理内存，它们之间没有任何重叠，如果程序A访问的虚拟地址超出了 0X00A00000 这个范围，系统就会判断这是一个非法的访问，拒绝这个请求，并将这个错误报告给用户，通常的做法就是强制关闭程序。

程序可以使用固定的内存地址

虚拟内存无论被映射到物理内存的哪一个区域，对于程序员来说都是透明的，我们不需要关心物理地址的变化，只需要按照从地址 0X00000000 到 0X00A00000 来编写程序、放置变量即可，程序不再需要重定位。

内存使用效率问题

以程序为单位对虚拟内存进行映射时，如果物理内存不足，被换入换出到磁盘的是整个程序，这样势必会导致大量的磁盘读写操作，严重影响运行速度，所以这种方法还是显得粗糙，粒度比较大。

内存分页机制

我们知道，当一个程序运行时，在某个时间段内，它只是频繁地用到了一小部分数据，也就是说，程序的很多数据其实在一个时间段内都不会被用到。

以整个程序为单位进行映射，不仅会将暂时用不到的数据从磁盘中读取到内存，也会将过多的数据一次性写入磁盘，这会严重降低程序的运行效率。

现代计算机都使用分页（Paging）的方式对虚拟地址空间和物理地址空间进行分割和映射，以减小换入换出的粒度，提高程序运行效率。

分页（Paging）的思想是指把地址空间人为地分成大小相等（并且固定）的若干份，这样的一份称为一页，就像一本书由很多页面组成，每个页面的大小相等。如此，就能够以页为单位对内存进行换入换出：

• 当程序运行时，只需要将必要的数据从磁盘读取到内存，暂时用不到的数据先留在磁盘中，什么时候用到什么时候读取。
• 当物理内存不足时，只需要将原来程序的部分数据写入磁盘，腾出足够的空间即可，不用把整个程序都写入磁盘。

关于页的大小

页的大小是固定的，由硬件决定，或硬件支持多种大小的页，由操作系统选择决定页的大小。比如 Intel Pentium 系列处理器支持 4KB 或 4MB 的页大小，那么操作系统可以选择每页大小为 4KB，也可以选择每页大小为 4MB，但是在同一时刻只能选择一种大小，所以对整个系统来说，也就是固定大小的。

目前几乎所有PC上的操作系统都是用 4KB 大小的页。假设我们使用的PC机是32位的，那么虚拟地址空间总共有 4GB，按照 4KB 每页分的话，总共有 2^32 / 2^12 = 2^20 = 1M = 1048576 个页；物理内存也是同样的分法。

根据页进行映射

下面我们通过一个简单的例子来说明虚拟地址是如何根据页来映射到物理地址的，请先看下图：

当我们把程序的虚拟空间按页分隔后，把常用的数据和代码页加载到内存中，把不常用的暂时留在磁盘中，当需要用到的时候再从磁盘中读取。上图中，我们假设有两个程序 Program 1 和 Program 2，它们的部分虚拟页面被映射到物理页面，比如 Program 1 的 VP0、VP1 和 VP7 分别被映射到 PP0、PP2 和 PP3；而有部分却留在磁盘中，比如 VP2、VP3 分别位于磁盘的 DP0、DP1中；另外还有一些页面如 VP4、VP5、VP6 可能尚未被用到或者访问到，它们暂时处于未使用状态。

这里，我们把虚拟空间的页叫做虚拟页（VP，Virtual Page），把物理内存中的页叫做物理页（PP，Physical Page），把磁盘中的页叫做磁盘页（DP，Disk Page）。

图中的线表示映射关系，可以看到，Program 1 和 Program 2 中的有些虚拟页被映射到同一个物理页，这样可以实现内存共享。

Program 1 的 VP2、VP3 不在内存中，但是当进程需要用到这两个页的时候，硬件会捕获到这个消息，就是所谓的页错误（Page Fault），然后操作系统接管进程，负责将 VP2 和 PV3 从磁盘中读取出来并且装入内存，然后将内存中的这两个页与 VP2、VP3 之间建立映射关系。

6、内存分页机制的实现（虚拟地址和物理地址的映射）

现代操作系统都使用分页机制来管理内存，这使得每个程序都拥有自己的地址空间。每当程序使用虚拟地址进行读写时，都必须转换为实际的物理地址，才能真正在内存条上定位数据。如下图所示：

内存地址的转换是通过一种叫做页表（Page Table）的机制来完成的，这是本节要讲解的重点，即：

• 页表是什么？为什么要采用页表机制，而不采用其他机制？
• 虚拟地址如何通过页表转换为物理地址？

直接使用数组转换

最容易想到的映射方案是使用数组：每个数组元素保存一个物理地址，而把虚拟地址作为数组下标，这样就能够很容易地完成映射，并且效率不低。如下图所示：

但是这样的数组有 2^32 个元素，每个元素大小为4个字节，总共占用16GB的内存，显现是不现实的！

使用一级页表

既然内存是分页的，只要我们能够定位到数据所在的页，以及它在页内的偏移（也就是距离页开头的字节数），就能够转换为物理地址。

例如，一个 int 类型的值保存在第 12 页，页内偏移为 240，那么对应的物理地址就是 2^12 * 12 + 240 = 49392。

2^12 为一个页的大小，也就是4K。

虚拟地址空间大小为 4GB，总共包含 2^32 / 2^12 = 2^20 = 1K * 1K = 1M = 1048576 个页面，我们可以定义一个这样的数组：它包含 2^20 = 1M 个元素，每个元素的值为页面编号（也就是位于第几个页面），长度为4字节，整个数组共占用4MB的内存空间。这样的数组就称为页表（Page Table），它记录了地址空间中所有页的编号。

虚拟地址长度为32位，我们不妨进行一下切割，将高20位作为页表数组的下标，低12位作为页内偏移。如下图所示：

为什么要这样切割呢？因为页表数组共有 2^20 = 1M 个元素，使用虚拟地址的高20位作为下标，正好能够访问数组中的所有元素；并且，一个页面的大小为 2^12 = 4KB，使用虚拟地址的低12位恰好能够表示所有偏移。

注意，表示页面编号只需要 20 位，而页表数组的每个元素的长度却为 4 字节，即 32 位，多出 32 - 20 = 12 位。这 12 位也有很大的用处，可以用来表示当前页的相关属性，例如是否有读写权限、是否已经分配物理内存、是否被换出到硬盘等。

例如一个虚拟地址 0XA010BA01，它的高20位是 0XA010B，所以需要访问页表数组的第 0XA010B 个元素，才能找到数据所在的物理页面。假设页表数组第 0XA010B 个元素的值为 0X0F70AAA0，它的高20位为 0X0F70A，那么就可以确定数据位于第 0X0F70A 个物理页面。再来看虚拟地址，它的低12位是 0XA01，所以页内偏移也是 0XA01。有了页面索引和页内偏移，就可以算出物理地址了。经过计算，最终的物理地址为 0X0F70A * 2^12 + 0XA01 = 0X0F70A000 + 0XA01 = 0X0F70AA01。

这种思路所形成的映射关系如下图所示：

可以发现，有的页被映射到物理内存，有的被映射到硬盘，不同的映射方式可以由页表数组元素的低12位来控制。

使用这种方案，不管程序占用多大的内存，都要为页表数组分配4M的内存空间（页表数组也必须放在物理内存中），因为虚拟地址空间中的高1G或2G是被系统占用的，必须保证较大的数组下标有效。

现在硬件很便宜了，内存容量大了，很多电脑都配备4G或8G的内存，页表数组占用4M内存或许不觉得多，但在32位系统刚刚发布的时候，内存还是很紧缺的资源，很多电脑才配备100M甚至几十兆的内存，4M内存就显得有点大了，所以还得对上面的方案进行改进，压缩页表数组所占用的内存。

使用两级页表

略

使用多级页表

略

7、MMU部件以及对内存权限的控制

通过页表完成虚拟地址和物理地址的映射时，要经过多次转换，还要进行计算，如果由操作系统来完成这项工作，那将会成倍降低程序的性能，得不偿失，所以这种方式是不现实的。

MMU

在CPU内部，有一个部件叫做MMU（Memory Management Unit，内存管理单元），由它来负责将虚拟地址映射为物理地址，如下图所示：

在页映射模式下，CPU 发出的是虚拟地址，也就是我们在程序中看到的地址，这个地址会先交给 MMU，经过 MMU 转换以后才能变成了物理地址。

即便是这样，MMU也要访问好几次内存，性能依然堪忧，所以在MMU内部又增加了一个缓存，专门用来存储页目录和页表。MMU内部的缓存有限，当页表过大时，也只能将部分常用页表加载到缓存，但这已经足够了，因为经过算法的巧妙设计，可以将缓存的命中率提高到 90%，剩下的10%的情况无法命中，再去物理内存中加载页表。

有了硬件的直接支持，使用虚拟地址和使用物理地址相比，损失的性能已经很小，在可接受的范围内。

MMU 只是通过页表来完成虚拟地址到物理地址的映射，但不会构建页表，构建页表是操作系统的任务。在程序加载到内存以及程序运行过程中，操作系统会不断更新程序对应的页表，并将页目录的物理地址保存到 CR3 寄存器。MMU 向缓存中加载页表时，会根据 CR3 寄存器找到页目录，再找到页表，最终通过软件和硬件的结合来完成内存映射。

CR3 是CPU内部的一个寄存器，专门用来保存页目录的物理地址。

每个程序在运行时都有自己的一套页表，切换程序时，只要改变 CR3 寄存器的值就能够切换到对应的页表。

对内存权限的控制

MMU 除了能够完成虚拟地址到物理地址的映射，还能够对内存权限进行控制。上节《内存分页机制的实现（虚拟地址和物理地址的映射）》讲到，在页表数组中，每个元素占用4个字节，也即32位，我们使用高20位来表示物理页编号，还剩下低12位，这12位就用来对内存进行控制，例如，是映射到物理内存还是映射到磁盘，程序有没有访问权限，当前页面有没有执行权限等。

操作系统在构建页表时将内存权限定义好，当MMU对虚拟地址进行映射时，首先检查低12位，看当前程序是否有权限使用，如果有，就完成映射，如果没有，就产生一个异常，并交给操作系统处理。操作系统在处理这种内存错误时一般比较粗暴，会直接终止程序的执行。

8、Linux下C语言程序的内存布局（内存模型）

在《虚拟地址空间以及编译模式》一节中讲到，虚拟地址空间在32位环境下的大小为 4GB，在64位环境下的大小为 256TB，那么，一个C语言程序的内存在整个地址空间中是如何分布的呢？数据在哪里？代码在哪里？为什么要这样分布？这些就是本节要讲解的内容。

程序内存在地址空间中的分布情况称为内存模型（Memory Model）。 内存模型由操作系统构建，在Linux和Windows下有所差异，并且会受到编译模式的影响，本节我们讲解Linux下32位环境和64位环境的内存模型。

内核空间和用户空间

对于32位环境，理论上程序可以拥有 4GB 的虚拟地址空间，我们在C语言中使用到的变量、函数、字符串等都会对应内存中的一块区域。

但是，在这 4GB 的地址空间中，要拿出一部分给操作系统内核使用，应用程序无法直接访问这一段内存，这一部分内存地址被称为内核空间（Kernel Space）。

Windows 在默认情况下会将高地址的 2GB 空间分配给内核（也可以配置为1GB），而 Linux 默认情况下会将高地址的 1GB 空间分配给内核。也就是说，应用程序只能使用剩下的 2GB 或 3GB 的地址空间，称为用户空间（User Space）。

Linux下32位环境的用户空间内存分布情况

我们暂时不关心内核空间的内存分布情况，下图是Linux下32位环境的一种经典内存模型：

对各个内存分区的说明：

内存分区	说明
程序代码区(code)	存放函数体的二进制代码。一个C语言程序由多个函数构成，C语言程序的执行就是函数之间的相互调用。
常量区(constant)	存放一般的常量、字符串常量等。这块内存只有读取权限，没有写入权限，因此它们的值在程序运行期间不能改变。
全局数据区(global data)	存放全局变量、静态变量等。这块内存有读写权限，因此它们的值在程序运行期间可以任意改变。
堆区(heap)	一般由程序员分配和释放，若程序员不释放，程序运行结束时由操作系统回收。malloc()、calloc()、free() 等函数操作的就是这块内存，这也是本章要讲解的重点。注意：这里所说的堆区与数据结构中的堆不是一个概念，堆区的分配方式倒是类似于链表。
动态链接库	用于在程序运行期间加载和卸载动态链接库。
栈区(stack)	存放函数的参数值、局部变量的值等，其操作方式类似于数据结构中的栈。

在这些内存分区中（暂时不讨论动态链接库），程序代码区用来保存指令，常量区、全局数据区、堆、栈都用来保存数据。对内存的研究，重点是对数据分区的研究。

程序代码区、常量区、全局数据区在程序加载到内存后就分配好了，并且在程序运行期间一直存在，不能销毁也不能增加（大小已被固定），只能等到程序运行结束后由操作系统收回，所以全局变量、字符串常量等在程序的任何地方都能访问，因为它们的内存一直都在。

常量区和全局数据区有时也被合称为静态数据区，意思是这段内存专门用来保存数据，在程序运行期间一直存在。

函数被调用时，会将参数、局部变量、返回地址等与函数相关的信息压入栈中，函数执行结束后，这些信息都将被销毁。所以局部变量、参数只在当前函数中有效，不能传递到函数外部，因为它们的内存不在了。

常量区、全局数据区、栈上的内存由系统自动分配和释放，不能由程序员控制。

程序员唯一能控制的内存区域就是堆（Heap）：它是一块巨大的内存空间，常常占据整个虚拟空间的绝大部分，在这片空间中，程序可以申请一块内存，并自由地使用（放入任何数据）。堆内存在程序主动释放之前会一直存在，不随函数的结束而失效。在函数内部产生的数据只要放到堆中，就可以在函数外部使用。

为了加深对内存布局的理解，请大家看下面一段代码：

#include <stdio.h>char *str1 = "www.c.xyz";  		//字符串在常量区，str1在全局数据区
int n;  						//全局数据区
char* func(){char *str = "内存布局"; 		//字符串在常量区，str在栈区return str;
}
int main(){int a;  					//栈区char *str2 = "01234";  		//字符串在常量区，str2在栈区char  arr[20] = "56789";  	//字符串和arr都在栈区char *pstr = func();  		//栈区int b;  					//栈区return 0;
}

Linux下64位环境的用户空间内存分布情况

在64位环境下，虚拟地址空间大小为 256TB，Linux 将高 128TB 的空间分配给内核使用，而将低 128TB 的空间分配给用户程序使用。如下图所示：

《虚拟地址空间以及编译模式》一节中讲到，在64位环境下，虚拟地址虽然占用64位，但只有最低48位有效。这里需要补充的一点是，任何虚拟地址的48位至63位必须与47位一致。

上图中，用户空间地址的47位是0，所以高16位也是0，换算成十六进制形式，最高的四个数都是0；内核空间地址的47位是1，所以高16位也是1，换算成十六进制形式，最高的四个数都是1。这样中间的一部分地址正好空出来，也就是图中的“未定义区域”，这部分内存无论如何也访问不到。

9、Windows下C语言程序的内存布局

在32位环境下，Windows 默认会将高地址的 2GB 空间分配给内核（也可以配置为1GB），而将剩下的 2GB 空间分配给用户程序。

不像 Linux，Windows 是闭源的，有版权保护，资料较少，不好深入研究每一个细节，至今仍有一些内部原理不被大家知晓。关于 Windows 地址空间的内存分布，官网上只给出了简单的说明：

• 对于32位程序，内核占用较高的 2GB，剩下的 2GB 分配给用户程序；
• 对于64位程序，内核占用最高的 248TB，用户程序占用最低的 8TB。

下图是一个典型的 Windows 32位程序的内存分布：

可以看到，Windows 的地址空间被分配给了各种 exe、dll 文件、堆、栈。其中 exe 文件一般位于 0x00400000 起始的地址；一部分 DLL 位于 0x10000000 起始的地址，如运行库 dll；还有一部分 DLL 位于接近 0x80000000 的位置，如系统 dll，Ntdll.dll、Kernel32.dll。

栈的位置则在 0x00030000 和 exe 文件后面都有分布，可能有读者奇怪为什么 Windows 需要这么多栈呢？我们知道，每个线程的栈都是独立的，所以一个进程中有多少个线程，就有多少个对应的栈，对于 Windows 来说，每个线程默认的栈大小是 1MB。

在分配完上面这些地址以后，Windows 的地址空间已经是支离破碎了。当程序向系统申请堆空间时，只好从这些剩下的还有没被占用的地址上分配。

10、用户模式和内核模式

首先我们要解释一个概念——进程（Process）。简单来说，一个可执行程序就是一个进程，前面我们使用C语言编译生成的程序，运行后就是一个进程。进程最显著的特点就是拥有独立的地址空间。

严格来说，程序是存储在磁盘上的一个文件，是指令和数据的集合，是一个静态的概念；进程是程序加载到内存运行后一些列的活动，是一个动态的概念。

前面我们在讲解地址空间时，一直说“程序的地址空间”，这其实是不严谨的，应该说“进程的地址空间”。一个进程对应一个地址空间，而一个程序可能会创建多个进程。

内核空间存放的是操作系统内核代码和数据，是被所有程序共享的，在程序中修改内核空间中的数据不仅会影响操作系统本身的稳定性，还会影响其他程序，这是非常危险的行为，所以操作系统禁止用户程序直接访问内核空间。

要想访问内核空间，必须借助操作系统提供的 API 函数，执行内核提供的代码，让内核自己来访问，这样才能保证内核空间的数据不会被随意修改，才能保证操作系统本身和其他程序的稳定性。

用户程序调用系统 API 函数称为系统调用（System Call）；发生系统调用时会暂停用户程序，转而执行内核代码（内核也是程序），访问内核空间，这称为内核模式（Kernel Mode）。

用户空间保存的是应用程序的代码和数据，是程序私有的，其他程序一般无法访问。当执行应用程序自己的代码时，称为用户模式（User Mode）。

计算机会经常在内核模式和用户模式之间切换：

• 当运行在用户模式的应用程序需要输入输出、申请内存等比较底层的操作时，就必须调用操作系统提供的 API 函数，从而进入内核模式；
• 操作完成后，继续执行应用程序的代码，就又回到了用户模式。

总结：用户模式就是执行应用程度代码，访问用户空间；内核模式就是执行内核代码，访问内核空间（当然也有权限访问用户空间）。

为什么要区分两种模式

我们知道，内核最主要的任务是管理硬件，包括显示器、键盘、鼠标、内存、硬盘等，并且内核也提供了接口（也就是函数），供上层程序使用。当程序要进行输入输出、分配内存、响应鼠标等与硬件有关的操作时，必须要使用内核提供的接口。但是用户程序是非常不安全的，内核对用户程序也是充分不信任的，当程序调用内核接口时，内核要做各种校验，以防止出错。

从 Intel 80386 开始，出于安全性和稳定性的考虑，CPU 可以运行在 ring0 ~ ring3 四个不同的权限级别，也对数据提供相应的四个保护级别。不过 Linux 和 Windows 只利用了其中的两个运行级别：

• 一个是内核模式，对应 ring0 级，操作系统的核心部分和设备驱动都运行在该模式下。
• 另一个是用户模式，对应 ring3 级，操作系统的用户接口部分（例如 Windows API）以及所有的用户程序都运行在该级别。

为什么内核和用户程序要共用地址空间

既然内核也是一个应用程序，为何不让它拥有独立的4GB地址空间，而是要和用户程序共享、占用有限的内存呢？

让内核拥有完全独立的地址空间，就是让内核处于一个独立的进程中，这样每次进行系统调用都需要切换进程。切换进程的消耗是巨大的，不仅需要寄存器进栈出栈，还会使CPU中的数据缓存失效、MMU中的页表缓存失效，这将导致内存的访问在一段时间内相当低效。

而让内核和用户程序共享地址空间，发生系统调用时进行的是模式切换，模式切换仅仅需要寄存器进栈出栈，不会导致缓存失效；现代CPU也都提供了快速进出内核模式的指令，与进程切换比起来，效率大大提高了。

---

11、栈的概念以及栈溢出

在《C语言程序的内存布局（内存模型）》中我们讲到，程序的虚拟地址空间分为多个区域，栈（Stack）是其中地址较高的一个区域。

栈（Stack）可以存放函数参数、局部变量、局部数组等作用范围在函数内部的数据，它的用途就是完成函数的调用。

栈内存由系统自动分配和释放：发生函数调用时就为函数运行时用到的数据分配内存，函数调用结束后就将之前分配的内存全部销毁。所以局部变量、参数只在当前函数中有效，不能传递到函数外部。

栈的概念

在计算机中，栈可以理解为一个特殊的容器，用户可以将数据依次放入栈中，然后再将数据按照相反的顺序从栈中取出。也就是说，先放入的数据最后才能取出，而最后放入的数据必须先取出。这称为先进后出（First In Last Out）原则。

放入数据常称为入栈或压栈（Push），取出数据常称为出栈或弹出（Pop）。如下图所示：

可以发现，栈底始终不动，出栈入栈只是在移动栈顶，当栈中没有数据时，栈顶和栈底重合。

从本质上来讲，栈是一段连续的内存，需要同时记录栈底和栈顶，才能对当前的栈进行定位。在现代计算机中，通常使用ebp寄存器指向栈底，而使用esp寄存器指向栈顶。随着数据的进栈出栈，esp 的值会不断变化，进栈时 esp 的值减小，出栈时 esp 的值增大。

ebp 和 esp 都是CPU中的寄存器：ebp 是 Extend Base Pointer 的缩写，通常用来指向栈底；esp 是 Extend Stack Pointer 的缩写，通常用来指向栈顶。

栈的大小以及栈溢出

对每个程序来说，栈能使用的内存是有限的，一般是 1M~8M，这在编译时就已经决定了，程序运行期间不能再改变。如果程序使用的栈内存超出最大值，就会发生栈溢出（Stack Overflow）错误。

一个程序可以包含多个线程，每个线程都有自己的栈，严格来说，栈的最大值是针对线程来说的，而不是针对程序。

栈内存的大小和编译器有关，编译器会为栈内存指定一个最大值，在 VC/VS 下，默认是 1M，在 C-Free 下，默认是 2M，在 Linux GCC 下，默认是 8M。

当然，我们也可以通过参数来修改栈内存的大小。

提示：栈也经常被称为堆栈，而堆依然称为堆，所以堆栈这个概念并不包含堆，大家要注意区分。

12、一个函数在栈上到底是怎样的

函数的调用和栈是分不开的，没有栈就没有函数调用，本节就来讲解函数在栈上是如何被调用的。

栈帧/活动记录

当发生函数调用时，会将函数运行需要的信息全部压入栈中，这常常被称为栈帧（Stack Frame）或活动记录（Activate Record）。

从逻辑上讲，栈帧就是一个函数执行的环境：函数参数、函数的局部变量、函数执行完后返回到哪里等等。

活动记录一般包括以下几个方面的内容：

1. 函数的返回地址，也就是函数执行完成后从哪里开始继续执行后面的代码。例如：

int a, b, c;
func(1, 2);
c = a + b;

站在C语言的角度看，func() 函数执行完成后，会继续执行c=a+b;语句，那么返回地址就是该语句在内存中的位置。

注意：C语言代码最终会被编译为机器指令，确切地说，返回地址应该是下一条指令的地址，这里之所以说是下一条C语言语句的地址，仅仅是为了更加直观地说明问题。

2. 参数和局部变量。有些编译器，或者编译器在开启优化选项的情况下，会通过寄存器来传递参数，而不是将参数压入栈中，我们暂时不考虑这种情况。

3. 编译器自动生成的临时数据。例如，当函数返回值的长度较大（比如占用40个字节）时，会先将返回值压入栈中，然后再交给函数调用者。

当返回值的长度较小（char、int、long 等）时，不会被压入栈中，而是先将返回值放入寄存器，再传递给函数调用者。

4. 一些需要保存的寄存器，例如 ebp、ebx、esi、edi 等。之所以要保存寄存器的值，是为了在函数退出时能够恢复到函数调用之前的场景，继续执行上层函数。

下图是一个函数调用的实例：

在寄存器名字前面添加“old”，表示函数调用之前该寄存器的值。

当发生函数调用时：

• 实参、返回地址、ebp 寄存器首先入栈；
• 然后再分配一块内存供局部变量、返回值等使用，这块内存一般比较大，足以容纳所有数据，并且会有冗余；
• 最后将其他寄存器的值压入栈中。

13、详细分析一个函数进栈出栈的例子

前面我们只是讲解了一个函数的活动记录是什么样子的，相信大家对函数的详细调用过程的认识还不是太清晰，这节我们就以 VS2010 Debug 模式为例来深入分析一下。

请看下面的代码：

void func(int a, int b){int p =12, q = 345;
}
int main(){func(90, 26);return 0;
}

函数使用默认的调用惯例，即参数从右到左入栈，由调用方负责将参数出栈。函数的进栈出栈过程如下图所示：

函数进栈

步骤①到⑥是函数进栈过程：

1. main() 是主函数，也需要进栈，如步骤①所示。

2. 在步骤②中，执行语句func(90, 26);，先将实参 90、26 压入栈中，再将返回地址压入栈中，这些工作都由 main() 函数（调用方）完成。这个时候 ebp 的值并没有变，仅仅是改变 esp 的指向。

3. 到了步骤③，就开始执行 func() 的函数体了。首先将原来 ebp 寄存器的值压入栈中（也即图中的 old ebp），并将 esp 的值赋给 ebp，这样 ebp 就从 main() 函数的栈底指向了 func() 函数的栈底，完成了函数栈的切换。由于此时 esp 和ebp 的值相等，所以它们也就指向了同一个位置。

4. 为局部变量、返回值等预留足够的内存，如步骤④所示。由于栈内存在函数调用之前就已经分配好了，所以这里并不是真的分配内存，而是将 esp 的值减去一个整数，例如 esp - 0XC0，就是预留 0XC0 字节的内存。

5. 将 ebp、esi、edi 寄存器的值依次压入栈中。

6. 将局部变量的值放入预留好的内存中。注意，第一个变量和 old ebp 之间有4个字节的空白，变量之间也有若干字节的空白。

为什么要留出这么多的空白，岂不是浪费内存吗？这是因为我们使用Debug模式生成程序，留出多余的内存，方便加入调试信息；以Release模式生成程序时，内存将会变得更加紧凑，空白也被消除。

至此，func() 函数的活动记录就构造完成了。可以发现，在函数的实际调用过程中，形参是不存在的，不会占用内存空间，内存中只有实参，而且是在执行函数体代码之前、由调用方压入栈中的。

未初始化的局部变量的值为什么是垃圾值

为局部变量分配内存时，仅仅是将 esp 的值减去一个整数，预留出足够的空白内存，不同的编译器在不同的模式下会对这片空白内存进行不同的处理，可能会初始化为一个固定的值，也可能不进行初始化。

虽然编译器对空白内存进行了初始化，但这个值对我们来说一般没有意义，所以我们可以认为它是垃圾值、是随机的。

函数出栈

步骤⑦到⑨是函数 func() 出栈过程：

7. 函数 func() 执行完成后开始出栈，首先将 edi、esi、ebx 寄存器的值出栈。

8. 将局部变量、返回值等数据出栈时，直接将 ebp 的值赋给 esp，这样 ebp 和 esp 就指向了同一个位置。

9. 接下来将 old ebp 出栈，并赋值给现在的 ebp，此时 ebp 就指向了 func() 调用之前的位置，即 main() 活动记录的 old ebp 位置，如步骤⑨所示。

这一步很关键，保证了还原到函数调用之前的情况，这也是每次调用函数时都必须将 old ebp 压入栈中的原因。

最后根据返回地址找到下一条指令的位置，并将返回地址和实参都出栈，此时 esp 就指向了 main() 活动记录的栈顶， 这意味着 func() 完全出栈了，栈被还原到了 func() 被调用之前的情况。

遗留的错误认知

经过上面的分析可以发现，函数出栈只是在增加 esp 寄存器的值，使它指向上一个数据，并没有销毁之前的数据。前面我们讲局部变量在函数运行结束后立即被销毁其实是错误的，这只是为了让大家更容易理解，对局部变量的作用范围有一个清晰的认识。

栈上的数据只有在后续函数继续入栈时才能被覆盖掉，这就意味着，只要时机合适，在函数外部依然能够取得局部变量的值。请看下面的代码：

#include <stdio.h>
int *p;
void func(int m, int n){int a = 18, b = 100;p = &a;
}
int main(){int n;func(10, 20);n = *p;printf("n = %d\n", n);return 0;
}

运行结果：n = 18

在 func() 中，将局部变量 a 的地址赋给 p，在 main() 函数中调用 func()，函数刚刚调用结束，还没有其他函数入栈，局部变量 a 所在的内存没有被覆盖掉，所以通过语句n = *p;能够取得它的值。

14、栈溢出攻击的原理

局部数组也是在栈上分配内存，当输入"12345678901234567890" 时，会发生数组溢出，占用“4字节空白内存”、“old ebp”和“返回地址”所在的内存，并将原有的数据覆盖掉，这样当 main() 函数执行完成后，会取得一个错误的返回地址，该地址上的指令是不确定的，或者根本就没有指令，所以程序在返回时出错。

C语言不会对数组溢出做检测，这是一个典型的由于数组溢出导致覆盖了函数返回地址的例子，我们将这样的错误称为“栈溢出错误”。

注意：这里所说的“栈溢出”是指栈上的某个数据过大，覆盖了其他的数据，和《栈的概念以及栈溢出》一节中提到的栈溢出不是一回事。

局部数组在栈上分配内存，并且不对数组溢出做检测，这是导致栈溢出的根源。除了上面讲到的 gets() 函数，strcpy()、scanf() 等能够向数组写入数据的函数都有导致栈溢出的风险。

15、C语言动态内存分配

在进程的地址空间中，代码区、常量区、全局数据区的内存在程序启动时就已经分配好了，它们大小固定，不能由程序员分配和释放，只能等到程序运行结束由操作系统回收。这称为静态内存分配。

栈区和堆区的内存在程序运行期间可以根据实际需求来分配和释放，不用在程序刚启动时就备足所有内存。这称为动态内存分配。

使用静态内存的优点是速度快，省去了向操作系统申请内存的时间，缺点就是不灵活，缺乏表现力，例如不能控制数据的作用范围，不能使用较大的内存。而使用动态内存可以让程序对内存的管理更加灵活和高效，需要内存就立即分配，而且需要多少就分配多少，从几个字节到几个GB不等；不需要时就立即回收，再分配给其他程序使用。

栈和堆的区别

栈区和堆区的管理模式有所不同：栈区内存由系统分配和释放，不受程序员控制；堆区内存完全由程序员掌控，想分配多少就分配多少，想什么时候释放就什么时候释放，非常灵活。

程序启动时会为栈区分配一块大小适当的内存，对于一般的函数调用这已经足够了，函数进栈出栈只是 ebp、esp 寄存器指向的变换，或者是向已有的内存中写入数据，不涉及内存的分配和释放。当函数中有较大的局部数组时，比如 1024*10 个元素，编译器就会在函数代码中插入针对栈的动态内存分配函数，这样函数被调用时才分配内存，不调用就不分配。

我们经常听说“栈内存的分配效率要高于堆”就是这个道理，因为大部分情况下并没有真的分配栈内存，仅仅是对已有内存的操作。

动态内存分配函数

堆（Heap）是唯一由程序员控制的内存区域，我们常说的动态内存分配也是在这个区域。在堆上分配和释放内存需要用到C语言标准库中的几个函数：malloc()、calloc()、realloc() 和 free()。

16、malloc()背后的实现原理（内存池）

相对于栈而言，堆这片内存面临着一个稍微复杂的行为模式：在任意时刻，程序可能发出请求，要么申请一段内存，要么释放一段已经申请过的内存，而且申请的大小从几个字节到几个GB都有可能，我们不能假设程序一次申请多少堆空间，因此，堆的管理显得较为复杂。

那么，使用 malloc() 在堆上分配内存到底是如何实现的呢？

一种做法是把 malloc() 的内存管理交给系统内核去做，既然内核管理着进程的地址空间，那么如果它提供一个系统调用，可以让 malloc() 使用这个系统调用去申请内存，不就可以了吗？当然这是一种理论上的做法，但实际上这样做的性能比较差，因为每次程序申请或者释放堆空间都要进行系统调用。我们知道系统调用的性能开销是比较大的，当程序对堆的操作比较频繁时，这样做的结果会严重影响程序的性能。

比较好的做法就是 malloc() 向操作系统申请一块适当大小的堆空间，然后由 malloc() 自己管理这块空间。

malloc() 相当于向操作系统“批发”了一块较大的内存空间，然后“零售”给程序用。当全部“售完”或程序有大量的内存需求时，再根据实际需求向操作系统“进货”。当然 malloc() 在向程序零售堆空间时，必须管理它批发来的堆空间，不能把同一块地址出售两次，导致地址的冲突。于是 malloc() 需要一个算法来管理堆空间，这个算法就是堆的分配算法。

malloc()和free()的分配算法

在程序运行过程中，堆内存从低地址向高地址连续分配，随着内存的释放，会出现不连续的空闲区域，如下图所示：

带阴影的方框是已被分配的内存，白色方框是空闲内存或已被释放的内存。程序需要内存时，malloc() 首先遍历空闲区域，看是否有大小合适的内存块，如果有，就分配，如果没有，就向操作系统申请（发生系统调用）。为了保证分配给程序的内存的连续性，malloc() 只会在一个空闲区域中分配，而不能将多个空闲区域联合起来。

内存块（包括已分配和空闲的）的结构类似于链表，它们之间通过指针连接在一起。在实际应用中，一个内存块的结构如下图所示：

next 是指针，指向下一个内存块，used 用来表示当前内存块是否已被使用。这样，整个堆区就会形成如下图所示的链表：

现在假设需要为程序分配100个字节的内存，当搜索到图中第一个空闲区域（大小为200个字节）时，发现满足条件，那么就在这里分配。这时候 malloc() 会把第一个空闲区域拆分成两部分，一部分交给程序使用，剩下的部分任然空闲，如下图所示：

仍然以图3为例，当程序释放掉第三个内存块时，就会形成新的空闲区域，free() 会将第二、三、四个连续的空闲区域合并为一个，如下图所示：

可以看到，malloc() 和 free() 所做的工作主要是对已有内存块的分拆和合并，并没有频繁地向操作系统申请内存，这大大提高了内存分配的效率。

另外，由于单向链表只能向一个方向搜索，在合并或拆分内存块时不方便，所以大部分 malloc() 实现都会在内存块中增加一个 pre 指针指向上一个内存块，构成双向链表，如下图所示：

链表是一种经典的堆内存管理方式，经常被用在教学中，很多C语言教程都会提到“栈内存的分配类似于数据结构中的栈，而堆内存的分配却类似于数据结构中的链表”就是源于此。

链表式内存管理虽然思路简单，容易理解，但存在很多问题，例如：

• 一旦链表中的 pre 或 next 指针被破坏，整个堆就无法工作，而这些数据恰恰很容易被越界读写所接触到。
• 小的空闲区域往往不容易再次分配，形成很多内存碎片。
• 经常分配和释放内存会造成链表过长，增加遍历的时间。

针对链表的缺点，后来人们提出了位图和对象池的管理方式，而现在的 malloc() 往往采用多种方式复合而成，不同大小的内存块往往采用不同的措施，以保证内存分配的安全和效率。

内存池

不管具体的分配算法是怎样的，为了减少系统调用，减少物理内存碎片，malloc() 的整体思想是先向操作系统申请一块大小适当的内存，然后自己管理，这就是内存池（Memory Pool）。

内存池的研究重点不是向操作系统申请内存，而是对已申请到的内存的管理，这涉及到非常复杂的算法，是一个永远也研究不完的课题，除了C标准库自带的 malloc()，还有一些第三方的实现，比如 Goolge 的 tcmalloc 和 jemalloc。

我们知道，C/C++是编译型语言，没有内存回收机制，程序员需要自己释放不需要的内存，这在给程序带来了很大灵活性的同时，也带来了不少风险，例如C/C++程序经常会发生内存泄露，程序刚开始运行时占用内存很少，随着时间的推移，内存使用不断增加，导致整个计算机运行缓慢。

内存泄露的问题往往难于调试和发现，或者只有在特定条件下才会复现，这给代码修改带来了不少障碍。为了提高程序的稳定性和健壮性，后来的 Java、Python、C#、JavaScript、PHP 等使用了虚拟机机制的非编译型语言都加入了垃圾内存自动回收机制，这样程序员就不需要管理内存了，系统会自动识别不再使用的内存并把它们释放掉，避免内存泄露。可以说，这些高级语言在底层都实现了自己的内存池，也即有自己的内存管理机制。

池化技术

在计算机中，有很多使用“池”这种技术的地方，除了内存池，还有连接池、线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。

所谓“池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要申请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效率。

17、C语言内存泄露（内存丢失）

使用 malloc()、calloc()、realloc() 动态分配的内存，如果没有指针指向它，就无法进行任何操作，这段内存会一直被程序占用，直到程序运行结束由操作系统回收。

请看下面的代码：

#include <stdio.h>
#include <stdlib.h>
int main(){char *p = (char*)malloc(100 * sizeof(char));p = (char*)malloc(50 * sizeof(char));free(p);p = NULL;return 0;
}

该程序中，第一次分配 100 字节的内存，并将 p 指向它；第二次分配 50 字节的内存，依然使用 p 指向它。

这就导致了一个问题，第一次分配的 100 字节的内存没有指针指向它了，而且我们也不知道这块内存的地址，所以就再也无法找回了，也没法释放了，这块内存就成了垃圾内存，虽然毫无用处，但依然占用资源，唯一的办法就是等程序运行结束后由操作系统回收。

这就是内存泄露（Memory Leak），可以理解为程序和内存失去了联系，再也无法对它进行任何操作。

内存泄漏形象的比喻是“操作系统可提供给所有程序使用的内存空间正在被某个程序榨干”，最终结果是程序运行时间越长，占用内存空间越来越多，最终用尽全部内存空间，整个系统崩溃。

用C语言写一个内存泄露的例子

操作系统允许程序自己分配内存，并自由使用，使用完了还可以再释放掉，将内存归还给计算机。

所谓分配内存，就是程序向计算机申请一块内存空间，然后自己使用；所谓释放内存，就是程序告诉计算机不再使用之前的内存空间了，需要归还给计算机，让其它程序使用。

如果一个程序不停地分配内存，而不释放内存，那么拥有的内存就会越来越多，计算机内存就会被消耗殆尽，其它程序能够使用的内存越来越少，整台计算机就会都变得缓慢，甚至卡死。

下面我们就用 while 循环来写一个内存泄漏的例子：

#include <stdlib.h>
#include <stdio.h>
int main(){while(1){  //死循环malloc(1024);  //分配1024个字节的内存}return 0;
}

while 循环的条件是 1，始终成立，循环会一直进行下去，永无休止，所以是一个“死循环”。

每次循环，程序都会向计算机申请 1024 个字节（1KB）的内存，并且不会释放；循环到第 1024 次时，程序就占用了 10241024 个字节（1MB）的内存；循环到 10241024 次时，程序就占用了 102410241024 个字节（1GB）的内存。

不要害怕，亲自跑一下试试，打开 Windows 下的任务管理器，可以看到内存的使用率会飙升，稍等片刻后程序会被终止。Windows 的内存管理机制发现我们的程序占用内存太多，会让它崩溃，防止系统卡死（其它的操作系统也有相应的措施）。