CSAPP-虚拟内存

一个系统的进程是与其他进程共享CPU和主存资源的。然而，共享主存会形成一些特殊的挑战。随着对CPU需求的增长，进程以某种合理的平滑方式慢下来。但是如果太多进程需要太多的内存，那么它们中的一些就根本无法运行。同时这种方式内存还十分容易被破坏。如果一个进程不小心写入另一个进程使用的内存，它可能以某种完全和程序逻辑无关的令人迷惑的方式失败。

为了更加有效地管理内存并且减少出错，现代操作系统提供了一种对主存储器的抽象概念，叫做虚拟内存（VM）。虚拟内存为每一个进程提供了一个强大的一致的私有地址空间。通过一个清晰的机制，虚拟内存提供了三个重要的能力：

  1. 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效的使用了主存。
  2. 它为每个进程提供了一致的地址空间，从而简化了内存管理。
  3. 它保护了每个进程的地址空间不被其他进程破环。

虚拟内存是计算机系统的一个重要的概念。它成功的一个主要原因是因为它可以沉默的自动的工作，不需要应用程序员的任何干涉。

这里将通过两个角度来看虚拟内存。本章的前一部分描述虚拟内存是如何工作的。后一部分将描述应用程序如何使用和管理虚拟内存。

1. 物理和虚拟寻址

计算机系统的主存被组织成为一个由M个连续的字节大小的单元组成的数组。每个字节都有一个唯一的*物理地址(Physical Address)。这种结构中，CPU访问内存最自然的方式就是使用物理地址。我们把这种方式称为物理寻址(physical addressing)*。

现代处理器使用一种称为是虚拟寻址（virtual addressing），使用虚拟寻址，CPU通过生成一个虚拟地址(Virtual Address, VA)来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。将一个虚拟地址转换成为物理地址的过程叫做地址翻译(address translation)。就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。 CPU芯片上叫做内存管理单元（Memory Management Unit，MMU）的专用硬件，利用存放在主存中的查询来动态翻译虚拟地址，该表的内容由操作系统管理。

2. 地址空间

地址空间(address space)是一个非负整数地址的有序集合。如果地址空间中的整数是连续的，那我们就说它是一个线性地址空间（linear address space）。在一个带虚拟内存的系统中，CPU从一个有N=2^n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间（virtual address space）。

一个地址空间的大小是由表示的最大地址所需要的位数来描述的。例如，一个包含 N=2^n个地址的虚拟地址空间就叫做一个n位地址空间。现代系统通常支持32位或者64位虚拟地址空间。

一个系统还有一个*物理地址空间(physical address space)*， 对应于系统中物理内存的M个字节。

地址空间的概念十分重要，它清楚地区分了数据对象（字节）和它们的属性（地址）。一旦认识到这种区别，那么我们就可以将其推广，允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。这就是虚拟内存的基本思想。主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

3. 虚拟内存作为缓存工具

概念上而言虚拟内存被组织成为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每一个字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘中数组的内容被缓存到主存中。和存储器层次结构中的其他缓存一样，磁盘（较低层）上的数据被分隔成块，这些块作为磁盘和主存（较高层）之间的传输单元。VM系统通过将虚拟内存分割成为虚拟页（Virtual Page， VP）的大小固定块来处理这个问题。每个虚拟页的大小为P=2^p字节。类似地，物理内存被分割成为*物理页(Physical Page, PP)*，大小也为P字节（物理页中被称为 （页帧（page frame））。

任何时刻，虚拟页面的集合都被分为三个不相交的子集：

  • 未分配的 ： VM系统还未被分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何的磁盘空间。
  • 缓存的 ： 当前已缓存在物理内存中的已分配页
  • 未缓存的 ： 未缓存在物理内存中的已分配页

虚拟页（VP）存储在磁盘中，物理页（PP）缓存在DRAM中。

3.1. DRAM缓存的组织结构

这里将使用SRAM缓存来表示位于CPU和主存之间的L1、L2和L3高速缓存，并且术语DRAM缓存来表示虚拟内存系统的缓存，它在主存缓存虚拟页中。

DRAM缓存大约比SRAM缓存慢了10倍，而磁盘要比DRAM慢了大约100000 多倍。因此，DRAM的缓存不命中比起SRAM的缓存不命中的代价要昂贵很多。而且，磁盘的随机读写要比连续读写要慢很多。所以，DRAM缓存的组织结构完全是由巨大的不命中开销驱动的。

这里因为巨大的不命中处罚，虚拟页往往很大，通常是4KB～2MB。由于不命中处罚，DRAM缓存是完全相联的，即任何虚拟页都可以放置在任何物理页中。不命中时的替换策略也很重要，因为替换错误的处罚非常之高。

3.2. 页表

如同缓存一样，虚拟内存系统必须要某种方法判定一个虚拟内存页是否缓存在DRAM中的某个地方。如果是，系统还必须确定这个虚拟页存放在那个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的那个位置，在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换这个牺牲页。

这些功能是由软硬件联合提供的，包括操作系统软件、MMU（内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表（page table）的数据结构，页表将虚拟页映射到物理页。每一次地址翻译硬件将一个虚拟地址转换成为物理地址的时候都会读取页表。操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传递页。

3.3. 页命中

当CPU想要读取缓存在DRAM中的虚拟内存中的一个字时，就会发生页命中。

3.4. 缺页

在虚拟内存的习惯说法中，DRAM缓存不命中称为缺页（page fault）。下面通过一个例子展现在缺页时我们的计算机会发生的变化。

  1. CPU引用VP3页中的一个字，VP3并未缓存在DRAM中。触发缺页异常。
  2. 地址翻译硬件从内存中读取PET3，从有效位推断出VP3未被缓存，并且触发一个缺页异常。
  3. 缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，例如存放在PP3中的VP4。如果VP4已经被修改，那么内核将它复制回磁盘。
  4. 内核修改VP4的页表条目，反应VP4不再缓存在主存中。
  5. 内核从磁盘复制VP3到内存中的PP3，更新PTE3，随后返回。
  6. 重新启动触发缺页异常之前的指令。

虚拟内存是在SRAM引入之前被提出。因此虚拟内存系统使用了和SRAM缓存不同的术语。例如在虚拟内存中，块被称为页。在磁盘和内存之间传送页的活动被叫做交换（swapping）或者页面调度（paging）。页从磁盘换入（或者页面调入）DRAM和从DRAM换出（或者页面调出）磁盘。只有当不命中发生时，才换入页面这种策略被称为按需页面调度（demand paging）。也可以采用其他方式，例如尝试预测不命中，在页面实际被引入之前就换入页面。现代系统大部分都是使用按需调度的方式

3.5. 局部性

通常整个运行过程中程序引用的不同页面的总数可能超过物理内存的总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面（active page）集合上面工作，这个集合叫做工作集（working set）或者常驻集合（resident set）。在初始开销，也就是将工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。

只要程序具有良好的时间局部性，虚拟内存系统就能工作得相当的好。如果工作集的大小超出了物理内存的大小，那么程序将产生一种抖动（thrashing），这时页面将不断地换进换出。

可以利用Linux的getrusage函数检测缺页的数量。

4. 虚拟内存作为内存管理工具

实际上，操作系统为每一个进程提供了一个独立的页表。注意多个虚拟页面可以映射到同一个共享物理页面。

按需页面调度和独立的虚拟地址空间的结合，对系统中内存的使用和管理造成了深远的影响。特别地，VM简化了链接和加载、代码和数据共享，以及应用程序的内存分配。

  • 简化链接 ： 独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。这样的一致性极大地简化了链接器的设计和实现，允许连接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中的代码和数据的最终位置的。
  • 简化加载 ： 虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。要把目标文件中的.text 和.data 节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，并将它们标记成为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置，有趣的是，加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用时，要么时CPU取指令时引用的，要么时一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。
  • 简化共享 ： 独立的地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般来说，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。在这种情况中，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面中。
  • 简化内存分配 ： 虚拟内存为向用户进程提供一个简单的分配额外内存的机制。当一个运行在用户进程中的程序要求额外的堆空间的时候（如调用malloc），操作系统分配一个适当的数字个连续的虚拟内存页面，并将它们映射到物理内存中任意位置的物理页面。由于页表的存在，这里操作系统并不需要分配k个连续的物理内存页面，页面可以随机的分散在物理内存中。

将一组连续的虚拟页映射到任意一个文件中的任意位置的表示方式称作内存映射（memory mapping）。Linux提供了一个称为mmap的系统调用，允许应用程序自己做内存映射。

在一些情况中，还是需要进程来共享代码和数据。例如，每个进程必须调用相同的操作系统内核代码，而每个C程序都会调用C标准库中的代码，如printf。操作系统通过将不同进程中适当的虚拟页映射到相同的物理页面中，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和C标准库的副本。

5. 虚拟内存作为内存保护的工具

现代计算机系统必须要为操作系统提供手段来控制对内存系统的访问，不应该允许一个用户进程修改它的只读代码段。而且也不应该允许它读或者修改任何内核中的代码和数据结构。不应该允许它读或者写其他进程的私有内存，并且不允许它修改任何与其他进程共享的虚拟页面。除非所有的共享者都显式地允许它这么做（通过调用明确的进程间通信系统调用）。

提供独立的地址空间使得区分不同进程的私有内存变得容易。但是地址翻译机制可以以一种自然的方式扩展到提供更好的访问控制。因此每次CPU生成一个地址时，地址翻译硬件都会读一个PTE，所以一般通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问。如读权限/写权限/用户组的许可位。

如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序，Linux shell一般将这种异常报告为”段错误（segmentation fault）”。

6. 地址翻译

这里描述地址翻译的基础知识，帮助了解硬件在支持虚拟内存中的角色。下面先总结一下地址翻译常用的符号。

基本参数

符号 描述
N=2^n 虚拟地址空间中地址的数量
M=2^m 物理地址空间中地址的数量
P=2^p 页的大小（字节）

虚拟地址（VA）的组成部分

符号 描述
VPO 虚拟页面地址偏移量（字节）
VPN 虚拟页号
TLBI TLB索引
TLBT TLB标记

物理地址（PA）的组成部分

符号 描述
PPO 物理页面偏移量（字节）
PPN 物理页号
CO 缓冲块内的字节偏移量
CI 高速缓存索引
CT 高速缓存标记

从形式上面来说，地址翻译是一个N元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）中元素之间的映射。

下面描述MMU如何利用页表来实现这种映射。CPU中的一个控制寄存器，页表基址寄存器（Page Table Base Register， PTBR）指向当前页表。n位的虚拟地址包含两个部分：一个P位的虚拟页面偏移（Virtual Page Offset，VPO）和一个（n-p）位的虚拟页号（Virtual Page Number， VPN），MMU利用VPN来选择适当的PTE。将页条目中的物理页号（Physical Page Number，PPN）和虚拟地址中的VPO串联起来，就得到相应的物理地址。

因为物理和虚拟页面都是P字节的，所以物理页面偏移PPO和VPO是相同的。

这里CPU硬件执行的步骤如下：

  1. 处理器生成一个虚拟地址，并把它传送给MMU；
  2. MMU生成PTE地址，并从高速缓存/主存请求得到它；
  3. 高速缓存/主存向MMU返回PTE；
  4. MMU构造物理地址，并把它传送给高速缓存/主存；
  5. 高速缓存/主存返回所请求的数据字给处理器。

当页面命中时完全是由硬件来处理，与之不同的是，处理缺页要求硬件和操作系统内核协作完成，具体步骤如下：

1～3 同上
4. PTE中的有效位是0，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。
5. 缺页处理程序确定物理内存中的牺牲页，如果这个页已经被修改了，则把它换出到磁盘。
6. 缺页处理程序页面调入新的页面，并更新内存中的PTE。
7. 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU将引起缺页的虚拟地址重新发送给MMU。因为虚拟页面现在缓存在物理内存中韩，所以就会命中。

6.1. 结合高速缓存和虚拟内存

再任何即使用虚拟内存又使用SRAM的高速缓存系统中，都有应该使用虚拟地址还是使用物理地址来访问SRAM高速缓存的问题。大多数的系统是使用物理寻址。使用物理寻址，多个进程同时再高速缓存中有存储块和共享来自虚拟页面的块成为很简单的事情。而且，高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。

6.2. 利用TLB加速地址翻译

如同我们看到的一样，每次CPU产生一个虚拟地址，MMU就必须查阅一个PTE，以便将虚拟地址翻译为物理地址。再最糟糕的情况下，这会要求从内存中多取一次数据，代价是几十到几百个计算机周期。如果PTE碰巧缓存在L1中，那么开销就下降到1个或者2个周期。许多系统试图消除这样的开销，通过再MMU中包含一个关于PTE的小缓存，称为翻译后备缓冲器（translation Lookaside Buffer，TLB）。

TLB是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。当TLB命中的时候（通常情况）CPU读取一个地址：

  1. CPU生成一个虚拟地址
    2~3. MMU从TLB中取出相应的PTE。
  2. MMU将这个虚拟地址翻译成为一个物理地址，并将他发送到高速缓存/主存中。
  3. 高速缓存/主存将请求数据字返回给CPU。

当TLB不命中时候，MMU必须从L1缓存中取出相应的PTE。新取出的PTE存放在TLB中，可能会覆盖一个已经存在的条目。

6.3. 多级页表

到目前为止，我们一直假设系统只用一个单独页表来进行地址翻译。但是如果我们有一个32位的地址空间、4KB页面和一个4字节的PTE，那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个4MB的页表贮留在内存中。

用来压缩页表的常用方法是使用层次结构的页表。一级页表中的每个PTE负责映射虚拟地址空间中的4MB的片。如果片i中的每个页面都未被分配，那么一级PTE i 就为空。如果片i中至少有一个页面是分配了的，那么一级PTE i就指向一个二级页的基址。二级页表中的每个PTE都负责映射一个4KB的虚拟内存页面。使用4字节的PTE，每个一级和二级页表都是4KB字节，这刚好和一个页面的大小是一样的。

7. 案例研究：Intel Core i7/Linux 内存系统

这里以一个实际系统的案例研究来总结我们对虚拟内存的讨论：一个运行Linux的Intel Core i7。虽然底层的Haswell微体系结构允许完全的64位虚拟地址空间和物理地址空间，而现在的（以及可以预见的未来的）Core i7 实现支持48位（256TB）虚拟地址空间和52位（4PB）物理地址空间，还有一个兼容模式，支持32位（4GB）虚拟和物理地址空间。

一个基本的core i7内存系统包括。处理器封装包括4个核、一个大的所有核共享的L3高速缓存，以及一个DDR3内存控制器。每个核包含一个层次结构的TLB、一个层次结构的数据和指令高速缓存，以及一组快速的点到点链路，这种链路基于QucikPath技术，是为了让一个核与其他核和外部I/O桥直接通信。TLB是虚拟寻址的，是四路组相连的。L1、L2和L3高速缓存是物理寻址的，块大小为64字节。L1和L2是8路组相连的，而L3是16路组相联的。页大小在启动的时候被配置为4K或者4MB。Linux使用的是4KB页。

7.1 Core i7 地址翻译

Core i7 采用4级页表层次结构，每个进程有它自己私有的页表层次结构。当一个Linux进程在运行时，虽然Core i7体系结构允许页表换进换出，但是与已分配了的页相关联的页表都是驻留在内存中的。CR3控制器指向第一级页表L1的起始位置。CR3的值是每个进程上下文的一部分。每次上下文切换，CR3的值都会被恢复。

对于Core i7来说，第一级、第二级或第三级页表中条目的格式如下：

地址 字段 描述
0 P 子页表在物理内存中（1），不在（0）
1 R/W 对于所有可访问页，只读或者读写访问权限
2 U/S 对于所有可访问的页，用户或超级用户（内核）模式访问权限
3 WT 子页表的直写或写回缓存策略
4 CD 能/不能缓存子页表
5 A 引用位 （由MMU在读和写时设置，由软件清除）
6 N/A N/A
7 PS 页大小为4KB或者4MB（只对第一层PTE定义）
8 G
9–11 N/A N/A
12–51 Base addr 子页表的物理地址的最高40位
52–62 N/A N/A
63 XD 能/不能从这个PTE可访问的所有页中取指令

对于第四级页表中条目的格式。当P=1的时候，地址字段中包括一个40位的PPN，它指向物理内存中某一页的基地址。这里要求物理页4KB对齐。第四级页表格式如下：

地址 字段 描述
0 P 子页表在物理内存中（1），不在（0）
1 R/W 对于子页，只读或者读写访问权限
2 U/S 对于所有可访问的页，用户或超级用户（内核）模式访问权限
3 WT 子页表的直写或写回缓存策略
4 CD 能/不能缓存子页表
5 A 引用位 （由MMU在读和写时设置，由软件清除）
6 D 修改位 （由MMU在读和写时设置，由软件清除）
7 0
8 G 全局页 （在任务切换时，不从TLB中驱逐出去）
9–11 N/A N/A
12–51 Base addr 子页表的物理地址的最高40位
52–62 N/A N/A
63 XD 能/不能从这个子页中取指令

PTE有三个权限位，控制对页的访问。RW位确定页的内容是可以读写还是只读的。U/S位确定是否能够在用户模式中访问该页面。从而保护操作系统内核中的代码和数据不被用户程序访问。XD（禁止执行）位是在64位系统中引入的，可以用来禁止某些内存页取指令，这是一个重要的性特性，通过限制只能执行只读代码段，使得操作系统内核降低缓冲区溢出攻击的风险。

当MMU翻译每一个虚拟地址时，它还会更新另外两个内核缺页处理程序会用到的位。每次访问一个页的时候，MMU都会设置A位，称为引用位（reference bit）。内核可以用这个引用位来实现它的页替换算法。每次对一个页进行了写之后，MMU都会设置D位，又称为修改位或脏位（dirty bit）。修改位高速内核在复制替换页之前是否必须写回牺牲页。内核可以通过调用一条特殊的内核指令来清除引用位或修改位。

对于地址翻译这一过程，我们可以总结为下面两个步骤：1）MMU将虚拟地址翻译成物理地址；2）将物理地址传送到L1高速缓存。

7.2 Linux 虚拟内存系统

这里我们对Linux的虚拟内存系统做一个描述，使得能够大致了解一个实际的操作系统是如何组织虚拟内存的，以及如何处理缺页。

Linux为每个进程维护一个单独的虚拟地址空间。

内核虚拟内存包括内核中的代码和数据结构。内核虚拟内存的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据结构。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来访问物理内存中的任何特定位置，例如，当它需要访问页表，或者在一些设备上执行内存映射I/O操作，而这些设备被映射到特定的物理内存位置。

内核虚拟内存的其他区域包含了每个进程都不相同的数据。比如说，页表、内核在进程的上下文中执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

7.2.1 Linux 虚拟内存区域

Linux 将虚拟内存组织成一些区域（也叫做段）的集合。一个区域（area）就是已经存在着的（已分配的）虚拟内存的连续片段（chunk），这些页是以某种方式相关联的。例如代码段、数据段、堆、共享库段，以及用户栈都是不同的区域。每个存在的虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。区域允许虚拟地址之间有间隙，内核不用记录那些不存在的虚拟页，而这样的页也不占用内存、磁盘或者内核本身的任何额外资源。

内核为系统中的每个进程维护一个单独的任务结构（源代码中的 task_struct），任务结构中的元素包含或者指向内核运行改进程所需要的所有信息（如PID，指向用户栈的指针，等）

7.2.2 Linux 缺页异常处理

假设MMU在试图翻译某个虚拟地址A的时候，触发了一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序执行下面步骤：

  1. 判断虚拟地址A是否合法，如果不合法，那么缺页处理程序就会触发一段错误，从而终止这个进程；
  2. 判断试图进行的内存访问是否合法，或者说进程是否有读、写或者说执行这个区域内页面的权限。
  3. 当缺页是由对合法地址的合法操作造成的，内核就会选择一个牺牲页面，如果这个页面被修改过，那么将它交换出去，并换入新的页并更新页表。

8. 内存映射

Linux 通过将一个虚拟内存区域与一个磁盘上的对象（object） 关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射（memory mapping）。虚拟内存区域可以映射到两种类型的对象中的一种。

  1. Linux 文件系统中的普通文件 ：一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区（section）被分成页大小的片，每一片包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际进行交换进入物理内存，直到CPU第一次引用到这个页面（即发射一个虚拟地址，落在地址空间这个页面的范围之内）。如果区域比文件区还要大，那么就用0来填充这个区域剩余的部分。
  2. 匿名文件 ：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制0 。 CPU第一次引用这个的一个区域内的虚拟页面的时候，内核就在物理内存中找到一个合适的牺牲页面，如果这个页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为是驻留在内存中。注意磁盘和内存之间并没有实际的数据传送。

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件（swap file）之间换来换去。交换文件也叫做交换空间（swap space）或者交换区域（swap area）。任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

8.1. 再看共享对象

如果虚拟内存系统可以集成到传统的文件系统中，那么就可以提供一种简单而高效的把数据加载到内存的方法。

进程这一抽象能够为每个进程提供自己私有的虚拟地址空间，可以避免受其他进程错误的读写。不过，许多进程有同样的只读代码区域。例如，每个运行Linux Shell程序的bash进程都有相同的代码区域。而且，许多程序需要访问只读运行时的库代码的相同副本。例如 标准C库。如果每个进程都在物理内存中保持这些常用的代码副本，那就是极端的浪费，内存映射给我们提供了一种清晰的机制，来控制多个进程如何共享对象的。

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。如果一个进程将一个共享对象映射到它的虚拟地址空间中的一个区域，那么这个进程对这个区域的任何操作，对于那些把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。而且，这些变化也会反映在磁盘的原始对象中。

另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所作的任何写操作都不会反应到磁盘上的对象中。一个映射到共享对象的虚拟内存的区域叫做共享区域。类似的也有私有区域。

私有对象使用一种叫做写时复制（copy-on-write）的巧妙技术被映射到虚拟内存中。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。

8.2. 再看fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当fork在新进程中返回时，新进程现在的虚拟内存设置和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

8.3. 再看execve函数

如下面的execve函数调用：

1
execve("a.out", NULL, NULL);

execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out程序有效地替代当前程序。加载并运行a.out包含以下几个步骤：

  • 删除已经存在的用户区域。删除当前进程虚拟地址的用户部分中已经存在的区域结构；
  • 映射私有区域。同时为新程序的代码，数据，bss和栈区域创建新的区域结构。所有的这些新的区域都是私有的，写时复制的。代码和数据区域被映射到a.out文件中的.text和.date区。
  • 映射共享区域。
  • 设置程序计数器（PC）。最后设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
               +------------------+    
               |       用户栈      |   -->  私有的，请求二进制零的
               +------------------+
               |                  |
               |                  |     
libc.so        +------------------+    
.data  --->    |     共享库的      |    ---> 共享的，文件提供的
.text  --->    |   内存映射区域     |
               +-------------------+  
               |                   |
               |                   |  
               +-------------------+  
               |     运行时堆       |
               | (通过malloc分配的) |
               +-------------------+
               |未初始化的数据(.bss)|
a.out          +-------------------+
.data  --->    |已初始化数据(.data) |
               +-------------------+
.text  --->    |     代码（.text）  |
               +-------------------+   
               |                   |  
             0 +-------------------+

8.4. 使用mmap函数的用户内存映射

Linux进程可以使用mmap函数来创建新的虚拟内存区域，并将对象映射到这些区域中。

9. 动态内存分配

使用动态内存分配器（dynamic memory allocator）会更方便，也有更好的可抑制性。

分配器将堆视为一组不同大小的块（block）的集合来维护，每个块就是一个连续的虚拟内存片（chunk），要么是已分配的，要么是空闲的。空闲块保持空闲，直到它显示地被应用分配。

分配器有两种基本的风格。两种风格都要求显示的分配块，它们的不同之处在于由那个实体来负责释放已分配的块。

  • 显式分配器（explicit allocator）。如C语言的malloc函数。
  • 隐式分配器（implicit allocator）。如高级语言java的垃圾收集器。

9.1. malloc和free函数

malloc函数返回一个指针，指向大小为至少size字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。实际上，对齐依赖编译代码在32位模式（gcc -m32）还是64位模式中运行。在32位模式中，malloc返回的块地址是8的倍数，在64位模式中，该地址总是16的倍数。

下面展示一个malloc和free的实现是如何管理一个C程序16字的堆的。

  1. 程序请求一个4字的块。malloc的响应是：从空闲块的前部切出一个4字的块，并返回一个指向这个块的第一字的指针。
  2. 程序请求一个5字的块。malloc的响应是：从空闲块的前部切出一个6字的块，malloc会在块里填充一个额外的字，为了保持空闲块是双字边界对齐的。
  3. 程序请求一个6字的块。malloc的响应是：从空闲块的前部切出一个6字的块.
  4. 程序释放第2步中分配的6字节块。注意在调用free函数后
    ，指针P2任然指向被释放的块。application需要保证它被一个新的malloc调用初始化之前不在使用P2.
  5. 程序请求一个2字的块。malloc分配在第四步中释放的区域，并返回一个指向这个块的新的指针。

9.2. 为什么要使用动态内存分配

程序使用动态内存分配的最重要的原因是经常直到程序实际运行时，才知道某些数据结构的大小。

9.3. 分配器的要求和目标

显式分配器必须在一些相当严格的约束条件下工作：

  • 处理任意请求序列；
  • 立即响应请求；
  • 只使用堆；
  • 对齐块（对齐要求）；
  • 不修改已分配的块。

在这些限制条件下，分配器的编写者试图实现的吞吐最大化和内存使用率最大化的这两个性能目标通常是相互冲突的。

9.4. 碎片

造成空间利用率很低的主要原因是一种称为碎片（fragmentation）的现象，当虽然有未使用的内存但不能用来满足分配请求时，就会发生这种现象。有两种形式的碎片：内部碎片（internal fragmentation）和外部碎片（external fragmentation）

内部碎片是指分配块要比有效载荷大。外部碎片是当前空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以处理这个请求。

9.5. 实现问题

这里想象一个简单的分配器的例子，分配器将堆组织成一个大的字节数组，还有一个指针p，出事指向这个数组的第一个字节。为了分配这个size字节，malloc将p的当前值保存在栈里，将P增加size，并将p的旧值返回到调用函数，而不做任何事情。

这里的例子中分配器的吞吐性极好，因为malloc和free函数只执行很少量的指令。但是内存利用效率将极差。

一个实际的分配器需要考虑下面几个问题：

  • 空闲块组织；
  • 放置，如何选择一个适合的空闲块来放置一个新的分配的块；
  • 分割，新分配后如何处理空闲块的其他部分；
  • 合并，如何处理一个刚被释放的块

9.6. 隐式空闲链表

任何实际的分配器系统都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。一般来说块是由一个字的头部，有效载荷，以及可能的一些额外的填充组成的。

9.7. 放置已分配的块

当一个应用请求一个k字节的块的时候，分配器搜索空闲链表，查找一个足够大可以放置所请求块的空闲块。分配器执行这种搜索的方式是由放置策略（placement policy）确定的。一些常见的策略是首次适配(first fit)、下一次适配（next fit）和最佳适配（best fit） 。

9.8. 分割空闲块

当分配空间小于空闲空间的时候，分配器通常会选择将这个空闲块分割成为两个部分。第一部分分配为分配块，剩下的部分变成新的空闲块。

9.9. 获取额外的堆内存

当没有足够大的空闲块的时候，分配器会首先合并相邻的空闲块来创建一个更大的空闲块。然而如果这样任然不够，分配器就会调用sbrk函数，向内核请求额外的堆内存。

9.10. 合并空闲块

可选的合并空闲块的策略有：立即合并（immediate coalescing），也就是每一次一个块被释放，就合并所有相邻的块。或者推迟合并（deferred coalescing），也就是等到稍晚的时候再合并空闲块，如分配请求失败的时候扫描整个堆，合并所有的空闲块。

9.11. 带边界标记的合并

边界标记的思想是在块的结尾处添加一个脚部的数据结构，其内容为头部分复制。这样当需要合并的时候可以通过脚部确定前一个块的状态，而不需要遍历整个链表。这样做的坏处是会带来一定的额外的内存开销。

10. 垃圾收集

当程序忘记释放p的时候。指针指向的分配内存会在程序的生命周期内都保持为已分配的状态，毫无必要地占用着本来可以用来满足后面分配请求的堆空间。

垃圾收集器（garbage collector）是一种动态内存分配器，它自动释放程序不在需要的分配块。垃圾收集器定期识别垃圾块，并相应地调用free函数，将这些块放回到空闲链表中。

垃圾收集器将内存视为一张有向的可达图（reachability graph）。每个堆节点对应于堆中的一个已分配块。有向边p–>q意味着p中的某个位置指向q中的某个位置。当存在任意一条从根节点出发的并到达p的有向路径，我们说节点p是可达的（reachable）。任何时刻，不可达节点对应于垃圾，是不可能被再次使用的。垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点将它们返回给空闲链表，来定期回收它们。

11. 常见C语言中关于内存的错误

对于C语言来说，管理和使用虚拟内存可能是个困难的，容易出错的任务。常见的一些与内存相关的错误讨论如下：

  1. 间接引用坏指针；
  2. 读未初始化的内存；
  3. 允许栈缓冲区溢出；
  4. 假设指针和它们指向的对象大小是相同的；
  5. 造成错位的错误；
  6. 引用指针，而不是它所指向的对象；
  7. 误解指针运算；
  8. 引用不存在的变量；
  9. 引用空闲堆块中的数据；
  10. 引起内存泄露。