CSAPP / CSE 351 学习笔记（虚拟内存 Virtual Memory)

为了更加有效地管理内存并且少出错，现代系统提供了一种对主存的抽象概念，叫做虚拟内存（VM）。虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。通过一个清晰的机制，它主要有三个功能：

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

物理和虚拟寻址

计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址（Physical Address，PA）。CPU 使用物理地址访问内存的方式被称为物理寻址（physical addressing）。现代处理器使用的是一种称为虚拟寻址（virtual addressing）的寻址形式。

将一个虚拟地址（Virtual Memory，VA）转换为物理地址的任务叫做地址翻译（address translation）。就像异常处理一样，地址翻译需要 CPU 硬件和操作系统之间的紧密合作。CPU 芯片上叫做内存管理单元（Memory Management Unit，MMU）的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

地址空间

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

解决三个问题：

• How Does Everything Fit? (64-bit addresses, 16 Exabyte -> tiny physical main memory)
• Memory Management
• How To Protect

An important technique that helps solve many problems: Indirection.

Any problem in computer science can be solved by adding another level of indirection.

Other examples: DNS -> IP, phone system, snail mail (e.g., mail forwarding), 911 (routed to local office).

So the solution is Level of Indirection.

虚拟内存作为缓存的工具

• Think of virtual memory as an array of $N = 2^n$ contiguous bytes stored on a disk
• Then physical main memory (DRAM) is used as a cache for the virtual memory array

概念上而言，虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。每个节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存到主存中。VM 系统通过将虚拟内存分割为虚拟页（Virtual Page，VP）的大小固定的块来处理这个问题。每个虚拟页的大小为 $P=2^p$ 字节。类似地，物理内存被分割为物理页（Physical Page，PP）或者页帧（page frame），大小也为 P 字节。

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

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

DRAM 缓存的组织结构

从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约 100000 倍。因d大的不命中处罚和访问第一个字节的开销，虚拟页往往很大，通常是 4KB ~ 2MB。由于大的不命中处罚，DRAM 缓存是全相联的，即任何虚拟页都可以放置在任何的物理页中。此外，不命中时的替换策略也很重要。最后，DRAM 缓存总是使用写回，而不是直写。

页表

判定一个虚拟页是否缓存在 DRAM 中的某个地方是由软硬件联合提供的，包括操作系统软件、MMU 中的地址翻译硬件和一个存放在物理内存中叫做页表（page table）的数据结构，页表将虚拟页映射到物理页。操作系统负责维护页表的内容，以及在磁盘和 DRAM 之间来回传送页。

页表就是一个页表项目（Page Table Entry，PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。每个 PTE 由一个有效位（valid bit）和一个 n 位地址字段组成。有效位表明了该虚拟页是否被缓存在 DRAM 中。

• 如果设置了有效位，那么地址字段就表示 DRAM 中相应的物理页的初始位置，这个物理页中缓存了该虚拟页（VP 1、2、4、7）。
• 如果有效位为 0，那么一个空地址（null）表示这个虚拟页还未被分配（VP 0 和 VP 5）。否则，这个地址就指向虚拟页在磁盘上的起始位置（VP 3、6）。

页命中

地址翻译硬件将虚拟地址作为一个索引来定位某个 PTE。如果设置了有效位，那么地址翻译硬件就知道其缓存在内存中。

缺页

DRAM 缓存不命中称为缺页（page fault）。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页进行替换，如果已经被修改了，内核还会将它复制回磁盘（写回）。

接下来，内核从磁盘复制新的虚拟页到内存中，并更新页表相应的页表项，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重新发送到地址翻译硬件（将会页命中）。

虚拟内存是在 20 世纪 60 年代早期发明的，远在「由于 CPU 和内存之间差距的加大而引发产生的 SRAM 缓存」之前。因此，虚拟内存系统使用了和 SRAM 缓存不同的术语，即使它们的许多概念是相似的。在虚拟内存的习惯说法中，块被称为页。在磁盘和内存之间的传送页的活动叫做交换（swapping）或者页面调度（paging）。页从磁盘换入（或者页面调入）DRAM 和从 DRAM换出（或者页面调出）磁盘。

一直等待，直到最后时刻，也就是当有不命中发生时，才换入页面的这种策略叫做按需页面调度（demand paging）。也可以采用其他的方法，例如尝试着预测不命中，在页面实际被引用之前就换入页面。然而，所有现代系统都使用的是按需页面调度的方式。

分配页面

当操作系统分配一个新的虚拟内存页时（比如程序调用了 malloc），新的虚拟页的分配过程是在磁盘上创建空间并更新对应的页表项 PTE，使它指向磁盘上这个新创建的页面。（如下图以 VP 5、PTE 5 为例）

又是局部性

由于不命中的处罚很大，我们担心页面调度会严重破坏程序性能。实际上，虚拟内存工作得相当好，这主要归功于我们的老朋友局部性（locality）。

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

如果工作机的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动（thrashing），这时页面将不断地换进换出。虽然虚拟内存通常是有效的，但是如果一个程序性能慢得像爬一样，那么聪明的程序员就会考虑是否发生了抖动（但起码内存还是够用的，只要磁盘空间没有被用尽，减少发生故障的可能性）。

• If (working set size < main memory size):
  • Good performance for one process after compulsory misses
• If (SUM(working set sizes) > main memory size):
  • Thrashing: Performance meltdown where pages are swapped (copied) in and out continuously

虚拟内存为内存管理的工具

到目前为止，我们都假设有一个单独的页表，将一个虚拟地址空间映射到物理地址空间。实际上，操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。注意，多个虚拟页面可以映射到同一个共享物理页面上。

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

• 简化链接

  独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。对于 64 位地址空间，代码段总是从虚拟地址0x400000开始。数据段跟在代码段之后，中间有一段符合要求的对齐空白。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置。

• 简化加载

  虚拟内存方便了向内存中加载可执行文件和共享对象文件。要把目标文件中.text和.data加载到一个新创建的进程中，Linux 加载器为代码和数据段分配虚拟页，把它们标记为无效（即未被缓存，这里这就解释了为什么无效有两种状态以及链接时的一些问题），将页表条目指向目标文件中适当的的位置（在磁盘中）。

  有趣的是，加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用时，要么是 CPU 取指令引用时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。

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

• 简化共享

  每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。在这种情况下，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。

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

• 简化内存分配

  虚拟内存向用户提供一个简单的分配额外内存的机制。由于页表的工作方式，操作系统没有必要分配 k 个连续的物理内存页面。页面可以随机地分散在物理内存中。

虚拟内存为内存保护的工具

任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问。不应该允许一个用户进程修改它的只读代码段。地址翻译机制可以以一种自然的方式扩展到提供更好的访问控制。因为每次 CPU 生成一个地址时，地址翻译硬件都会读一个 PTE，所以通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单。

在这个示例中，每个 PTE 中添加了三个许可位，其中SUP位表示进程是否必须运行在内核（超级用户）模式下才能访问该页。如果一条指令违反了这些许可条件，那么 CPU 就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell 一般将这种异常报告为段错误（segmentation fault）。

地址翻译（MMU）

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

$$MAP: VAS\rightarrow PAS \cup \emptyset$$

其中：

$$
MAP(A) = \left{
\begin{aligned}
&A’, 如果虚拟地址 A 处的数据在 PAS 的物理地址 A’ 处\
&\emptyset, 如果虚拟地址 A 处的数据不在物理内存中
\end{aligned}
\right.
$$

CPU 中的一个控制寄存器，即页表基址寄存器（Page Table Base Register，PTBR）指向当前页表。n 位的虚拟地址包含两个部分：一个 p 位的虚拟页面偏移（Virtual Page Offset，VPO）和一个（n - p）位的虚拟页号（Virtual Page Number，VPN）。MMU 利用 VPN 来选择适当的 PTE。例如，VPN 0 选择 PTE 0，VPN 1 选择 PTE 1，以此类推。将页表条目中的物理页号（Physical Page Number，PPN）和虚拟地址中的VPO串联起来，就得到相应的物理地址。注意，因为物理和虚拟页面都是 P 字节的，所以物理页面偏移（Physical Page Offset， PPO）和 VPO 是相同的。

页面的大小决定了页偏移的大小，页偏移的大小决定了虚拟地址和物理地址中需要用多少低位来表示偏移量。如虚拟地址为 14 位，物理地址为 12 位，页面大小是 64 字节（$2^64$），即需要 6 个低位。

当页面命中时，CPU 硬件执行步骤：

1. 处理器生成一个虚拟地址VA，并把它传送给 MMU。
2. MMU 生成PTE地址（PTBR基址 + VPN），并从高速缓存/主存请求得到它。
3. 高速缓存/主存向 MMU 返回PTE（取得页表项）。
4. MMU 构造物理地址（物理页号PA = PPN + VPO/PPO），并把它传送给高速缓存/主存。
5. 高速缓存/主存返回所请求的数据字给处理器。

页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成。

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

结合高速缓存和虚拟内存

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

利用 TLB 加速地址翻译

每次 CPU 产生一个虚拟地址，MMU 就必须查阅一个 PTE，以便将虚拟地址翻译为物理地址。最糟糕的情况下，这会要求从内存多取一次数据，代价是几十到几百个周期，除非 PTE 碰巧缓存在 L1，开销降到 1 个或 2 个周期。然而，许多系统会在 MMU 中包括一个关于 PTE 的小的缓存，称为翻译后备缓冲器（Translation Lookaside Buffer，TLB）。

TLB 是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个 PTE 组成的块。TLB 通常有高度的相联度。用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号（VPN）中提取出来的。

注意：一般，TLB 是虚拟寻址，L1、L2、L3 是物理寻址。

多级页表

问题：假设系统只有一个单独的页表来进行地址翻译。但是如果我想有一个 32 位的地址空间、4KB 的页面和一个 4 字节（32位）的 PTE，那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个 4MB 的页表驻留在内存中。对于地址空间为 64 位的系统来说，问题变得更加复杂。

解决方法（如何压缩表）：使用层次结构的页表。

一级页表中的每个 PTE 负责映射虚拟地址中一个 4MB 的片（chunk），这里每一片都是由 1024 个连续的页面组成的。比如，PTE 0 映射第一片，PTE 1 映射接下来的一片，由此类推。假设地址空间是 4GB，那么 1024 个 PTE 已经足够覆盖整个空间了。

如果片 i 中的每个页面都未被分配n那么一级 PTEi 就为空；否则，一级 PTEi 就指向一个二级页表的基址。

二级页表中的每个 PTE 都负责映射一个 4KB 的虚拟内存页面，就像我们查看只有一级的页表一样。注意，使用 4 字节的 PTE，每个一级和二级页表都是 4KB 字节，这刚好和一个页面大小是一样的。

页表项都是 4B，一级和二级都可以有 1024 个页表项，总共可以表示 1024 x 1024，即 1M 个页面，乘以页面大小 4KB，即等于 4GB 的内存地址空间。

这种方法从两个方面减少了内存要求：

1. 如果一级页表中的一个 PTE 是空的，那么相应的二级页表就根本不会存在。因为一个典型的程序，4GB 的虚拟地址空间的大部分都会是未分配的。
2. 只有一级页表才需要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

多级页表的物理地址构造

假设一个使用 k 级页表层次结构的地址翻译。虚拟地址被划分成为 k 个 VPN 和 1 个 VPO。第 k 级页表中的每个 PTE 包包含某个物理页面的 PPN，或者一个磁盘块的地址。为了构造物理地址，在能够确定 PPN 之前，MMU 必须访问 k 个 PTE。

在这里 TLB 能够起作用，正是通过将不同层次上页表的 PTE 缓存起来。实际上，带多级页表的地址翻译并不比单级页表慢很多。

案例研究：Core i7 地址翻译

Intel Core i7 底层的 Haswell 为体系结构允许完全的 64 位虚拟和物理地址空间，而现在的（以及可预见的未来的）Core i7 实现支持 48 位（256TB）虚拟地址空间和 52 位（4PB）物理地址空间，还有一个兼容模式，支持 32 位（4GB）虚拟和物理地址空间。

Core i7 采用四级页表层次结构。每个进程有它自己私有的页表层次结构。

实际的页表项非常复杂，拥有很多字段。

优化地址翻译：

前面讨论了地址翻译的两个步骤：1）MMU 将虚拟地址翻译成物理地址；2）将物理地址传送到 L1 高速缓存。

然而，实际的硬件实现使用了一个灵活的技巧，允许这些步骤部分重叠，从而加l了对 L1 高速缓存的访问。当 CPU 需要翻译一个虚拟地址时，它就发送 VPN 到 MMU，发送 VPO 到高速 L1 缓存。当向 TLB 请求一个页表条目时，L1 高速缓存正忙着利用 VPO 位查找相应的组。当 MMU 从 TLB 得到 PPN 时，缓存已经准备好试着把这个 PPN 与从 L1 中得出的数据进行匹配、结合。

参考：p576

案例研究：Linux 内存系统

一个虚拟内存系统要求硬件和内核软件之间的紧密协作。版本与版本之间细节都不尽相同。Linux 为每个进程维护了一个单独的虚拟地址空间。

内核虚拟内存包含内核中的代码和数据结构，其某些区域被映射到所有进程共享的物理页面。有趣的是，Linux 也将一组连续的虚拟页面（大小等同于系统中 DRAM 的总量）映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来访问物理内存中任何特定的位置。此外，内核虚拟内存的其他区域包含每j进程都不相同的数据。比如说，页表、内核在进程的上下文执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

Linux 虚拟内存区域

Linux 将虚拟内存组织成一些区域（也叫做段）的集合。一个区域（area）就是已经存在着的（已分配的）虚拟内存的连续片（chunk），这些页是以某种方式相关联的（链表）。例如，代码段、数据段、堆、共享库段，以及用户栈都是不同的区域。每个存在的虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。

区域的概念很重要，因为它允许虚拟地址空间有间隙。内核不用记录那些不存在的虚拟页，而这样的页也不占用内存、磁盘或者内核本身中的任何资源。

该图强调了一个进程中虚拟内存区域的内核数据结构。内核为系统中的每个进程维护一个单独的任务结构（源代码中的task_struct）。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息（PID、指向用户栈的指针、可执行目标文件的名字、PC）。

任务结构中的一个条目指向mm_struct，它描述了虚拟内存的当前状态。其中，pgd（page table directory）指向第一级页表（页全局目录）的基址，而mmap指向一个vm_area_structs（区域结构）的链表，其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将pgd存放在CR3控制寄存器中。

• vm_start：区域的起始处。
• vm_end：区域的结束处。
• vm_prot：区域内所有页的读写许可权限。
• vm_flags：区域内页面是与其他进程共享的，还是这个进程私有的（还描述了其他一些信息）。
• vm_next：指向链表中下一个区域结构。

Linux 缺页异常处理

内核的缺页处理程序：

1. 虚拟地址 A 合法吗？（A 在某个区域结构定义的区域内吗？）

缺页处理程序需要搜索区域结构的链表，把 A 和每个区域结构中的vm_start和vm_end做比较，如果不合法就触发一个段错误，从而终止这个进程（如图中的「1」）。

因为一个进程可以创建任意数量的新虚拟内存区域（使用之后描述的mmap函数），所以顺序搜索花销很大。因此在实际中，Linux 使用某些这里没有显示出来的字段，在链表中构建了一棵树，并在这棵树上进行查找。

2. 试图进行的内存访问合法吗？（进程是有读写这个区域内页面的权限？）

如果试图进行的访问是不合法的，那么缺页处理程序会触发一个保护异常，从而终止这个进程，如图中的「2」。

此时，内核知道了这个缺页是由于对合法的虚拟地址进行合法的操作造成，它将选择一个牺牲页面，如果其被修改过，那么就将它交换出去，换入新的页面并更新页表。当缺页处理程序返回时，CPU 重新启动引起缺页的指令，这条指令将再次发送 A 到 MMU。

内存映射

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

1. Linux 文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区（section）被分成页大小的片，每一片包含一个虚拟页面的初始内容。所有这些虚拟页面没有实际交换进入物理内存，直到 CPU 第一次引用到页面。

2. 匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。CPU 第一次引用这样一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为是驻留在内存中的。注意在磁盘和内存之间并没有实际的数据传送。因为这个原因，映射到匿名文件的区域中的页面有时称为请求二进制零的页（demand-zero page）。

无论在哪种情况下，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门交换文件（swap file）之间换来换去，也叫做交换空间（swap space）或者交换区（swap area）。

共享对象 & 私有对象

内存映射给我们提供了一种清晰的机制，用来控制多个进程如何共享对象。一个进程可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。

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

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

私有对象使用一种叫做写时复制（copy-on-write）的巧妙技术被映射到虚拟内存中。

对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。只要没有进程试图写它自己的私有区域，它们就可以继续共享物理内存中对象的一个单独副本。然而，只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。故障处理程序会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。最后，CPU 重新执行这个写操作。

通过尽量延迟产生私有对象中的副本，写时复制最充分地利用了稀有的物理资源。

fork 函数

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

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

execve 函数

假设运行在当前进程中的程序执行了如下的 execve 调用：

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

加载并运行a.out需要以下几个步骤：

1. 删除已存在的用户区域（结构）。
2. 映射私有区域。为新程序的代码、数据、bss 和栈区域创建新的区域结构，都是私有、写时复制的。bss 区域是请求二进制零的，映射到匿名文件，其大小包含在 a.out 中的。栈和堆区域也是请求二进制零的，初始长度为零。
3. 映射共享区域。共享库中的对象需要动态链接到这个程序，然后再映射到用户虚拟地址空间中的共享区域内。
4. 设置程序计数器。执行的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。

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

动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域，称为堆（heap）。系统之间细节不同，但不失通用性。假设堆是一个请求二进制零的区域，它紧接在未初始化的数据区域后开始，并向上生长（向更高地址）。对于每个进程，内核维护者一个变量brk（读「break」），它指向堆的顶部。

分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟内存片（chunk），要么是已分配的，要么是空闲的。内存释放要么是应用程序显式执行，要么是内存分配器自身隐式执行。

分配器有两种基本风格：

• 显式分配器（explicit allocator）：C 程序通过调用 malloc 函数来分配一个块，并通过调用 free 函数来释放一个块（类似于 C++ 的 new 和 delete 关键字）。
• 隐式分配器（implicit allocator）：也叫做垃圾收集器（garbage collection），诸如 Lisp、ML 以及 Java 之类的高级语言就依赖垃圾收集来释放已分配的块。

分配器的两个性能目标：最大化吞吐率和最大化内存利用率。

碎片

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

• 内部碎片：是在一个已分配块比有效载荷大时发生的，即一个分配器的实现可能对已分配块强加一个最小值限制，而这个要求要比某个请求的有效载荷大。

  

• 外部碎片：当空闲内存合计起来满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生，即需要的大小分散在不同的小的空闲块中。

  

因为外部碎片难以量化且不可能预测，所以分配器通常采用启发式策略来试图维持少量的大空闲块，而不是维持大量的小空闲块。

实现的时候会考虑到：如何组织空闲块、放置问题、分割问题、合并问题。

隐式空闲链表

任何实际的分配器都需要一些数据结构，允许它来区别块的边界，以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身。通过头部中的大小字段隐含地连接着空闲块的结构称为隐式空闲链表（Implicit Free Lists）。

一个块是由 32 位的头部、有效载荷，以及可能的一些额外的填充组成的。头部编码了这个块的大小，以及这个块是已分配还是空心啊的。头部后面是调用 malloc 请求的有效载荷。有效载荷后面是一片不使用的填充块，其大小可以是任意的，为了实现某些分配器策略，以对付外部碎片，或者用来满足对齐要求。

分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。特点：简单，但开销大。

常见的搜索策略（放置策略，placement policy）：

• 首次适配（first fit）：从头开始。
• 下一次适配（next fit）：从上一次查询结束的地方开始（当链表前面布满了许多小的碎片时）。（Donald Knuth）
• 最佳适配（best fit）：检查每个空闲块。

常见的分割策略：

• 选择使用整个块：简单，但容易造成内部碎片。
• 将空闲块分割为两部分，第一部分变成分配块，第二部分变成空闲块。

如果分配器不能为请求块找到合适的空闲块将发生什么呢？一个选择是通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块，或者调用sbrk函数，向内核请求额外的堆内存。

基于边界标记的合并策略：

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种假象，叫做假碎片（fault fragmentation），即无法使用的、小的空闲块。

为了解决假碎片的问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并（coalescing）。但是，何时执行合并？立即合并或者推迟合并（直到某个分配请求失败时）？

合并下一个空闲块很简单而且高效，可以通过检查头部中指向下一个块的头部的指针以判断下一个块是为空闲的。但是我们该如何合并前面的块？记住前面块的位置？

Donald Knuth，即《计算机程序设计艺术》（TAOCP）的作者，提出了一种聪明而通用的技术，叫做边界标记（boundary tag），允许在常数时间内进行对前面块的合并。这种思想，是在每个块的结尾处添加一个脚部（footer，边界标记），其就是头部的一个副本。这样分配器就可以通过检查脚步来判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。

前面的块	后面的块	合并
已分配	已分配	不能合并
已分配	空闲	与后面的块合并，并更新当前块的块大小信息和后面块的脚部
空闲	已分配	与前面的块合并，并更新前面块的块大小信息和当前块的脚部
空闲	空闲	与前后的块合并，更新前面块的头部和后面块的脚部

边界标记的概念是简单优雅的，对许多不同类型的分配器和空闲链表组织都是通用的。但是，当应用程序操作许多个小块时，它会产生一个潜在的缺陷（内存空间开销大）。

有一种非常聪明的边界标记的优化访问，能够使得在已分配块中不再需要脚部。因为只有在前面的块是空闲块时，才会需要用到它的脚部。如果我们把前面块的已分配/空闲位存放在当前块中多出来的低位中，那么已分配块就不再需要脚部了（当分配很多小块时还能充分利用内存空间）。

显式空闲链表

在隐式空闲链表中，因为块分配与堆块的总数呈线性关系，所以对于通用的分配器，隐式空闲链表是不适合的。一种更好的方法是将空闲块组织为某种形式的显示数据结构，即采用显示空闲链表（explicit free lists），如堆可以组织成一个双向空闲链表。

使用双向链表使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，取决于空闲链表中块的排序策略。

一种方法是采用后进先出（LIFO）的顺序维护链表，将新释放的块放置在链表的开始处。在这种情况下，释放一个块可以在常数时间内完成。

另一种方法是按照地址顺序来维护链表，其中链表中每个块都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。但是，在首次适配上这种方法比 LIFO 排序有更高的内存利用率。

一般而言，显式链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。

分离的空闲链表

一种流行的减少分配时间的方法，通常称为分离存储（segregated storage），就是维护多个空闲链表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，也叫做大小类（size class），如可以根据二次幂划分，或者小的块分派到自己的大小类，大的块使用二次幂。

有关动态内存分配的文献描述了几十种分离存储方法，其中两种基本的方法是：

简单分离存储（simple segregated storage）

使用简单分离存储，每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小，如大小类 {17~32}，其块大小为 32。在分配一个给定大小的块时，我们检查相应的空闲链表。

• 如果链表非空，我们简单地分配其中第一块的全部（不会分割）。
• 如果链表为空，分配器就会向操作系统请求一个固定大小的额外内存片（通常是d大小的整数倍），并将这个片分成大小相等的块。

要释放一个块，分配器只要简单地将这个块插入到相应的空闲链表的前部。

优点：

• 分配和释放都是很快的常数时间操作。
• 不需要分割、合并，每个块只有很少的内存开销（没有了头部、脚部）。
• 由于块的大小相同，可以根据已分配块的地址推断出其大小。

显著的缺点：简单分离存储很容易造成内部和外部碎片，因为空闲块是不会分割、合并。

分离适配（segregated fit）

每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。在链表中适配的时候，查找一个合适的块。如果找到了一个，就分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到合适的块，那么就搜索下一个更大的大小类的空闲链表。如果重复，直到找到一个合适的块。如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配一个块，将剩余部分放置在适当的大小类中。要释放一个块，我们执行合并，并将结果放置到相应的空闲链表中。

C 标准库中提供的 GNU malloc 包就是采用的这种方法，因为这种方法既迅速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。

伙伴系统（buddy system）

伙伴系统是分离适配堆一种特例，其中每个大小类都是 2 的幂。基本的思路是假设一个堆的大小为 $2^m$ 个字，我们为每个块大小 $2^k$ 维护一个分离空闲链表，其中 0 <= k <= m。请求块大小向上舍入到最接近的二的幂。最开始时，只有一个大小为 $2^m$ 个字的空闲块。

为了分配一个大小为 $2^k$ 的块，我们找到第一个可用的、大小为 $2^j$ 的块，其中 k <= j <= m。如果 j = k，那么我们就完成了。否则，我们递归地二分割这个块，直到 j = k。当我们进行这样的分割时，每个剩下的半块（也叫做伙伴）被放置在相应的空闲链表中。要释放一个大小为 $2^k$ 的块，我们继续合并空闲的伙伴。当遇到一个已分配的伙伴，我们就停止合并。

关于伙伴系统的一个关键事实是，给定地址和块的大小，很容易计算出它的伙伴的地址，两者之间只有一位不同。

伙伴系统分配器的主要优点是它的快速搜索和快速合并。主要缺点是要求块大小为二次幂可能导致显著的内部碎片。

垃圾收集

垃圾收集器（garbage collector）是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块成为垃圾（garbage）。自动回收堆存储的过程叫做垃圾收集（garbage collection）。

Classical GC Algorithms

• Mark-and-sweep collection (McCarthy, 1960)
  • Does not move blocks (unless you also “compact”)
• Reference counting (Collins, 1960)
  • Does not move blocks
• Copying collection (Minsky, 1963)
  • Moves blocks
• Generational Collectors (Lieberman and Hewitt, 1983)
  • Collection based on lifetimes
    • Most allocations become garbage very soon
    • So focus reclamation work on zones of memory recently allocated

垃圾收集器的基本知识

垃圾收集器将内存视为一张有向可达图（reachability graph），该图的节点被分成一组根节点（root node）和一组堆节点（heap node）。每个堆节点对应于堆中的一个已分配块。有向边 p->q意味着 p 中的某个位置指向块 q 中的某个位置。根节点对应于这样一种不在堆中的位置，它们中包含指向堆中的指针。这些位置可以是寄存器、栈里的变量，或者是虚拟内存中读写数据区域内的全局变量。

当存在一条从任意根节点出发并到达 p 的有向路径时，我们说节点 p 是可达的（reachable）。在任何时刻，不可达节点对应于垃圾，是不能被应用再次使用的。垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点且将它们返回给空闲链表，来定期地回收它们。

• Can build on top of malloc/free package
  • Allocate using malloc until you “run out of space”
• When out of space:
  • Use extra mark bit in the head of each block
  • Mark: Start at roots and set mark bit o˜n each reachable block
  • Sweep: Scan all blocks and free blocks that are not marked

/* Mark using depth-first traversal of the memory graph */
ptr mark(ptr p) {
  if (!is_ptr(p)) return;
  if (markBitSet(p)) return;
  setMarkBit(p);
  for (int i = 0; i < length(p); ++i) {
    mark(p[i]);
  }
  return;
}

/* Sweep using lengths to find next block */
ptr sweep(ptr p, ptr end) {
  while (p < end) {
    if (markBitSet(p))
      clearMarkBit();
    else if (allocateBitSet(p))
      free(p);
    p += length(p);
  }
}

像 ML 和 Java 这样的语言的垃圾收集器，对应用如何创建和使用指针有严格的控制，能够维护可达图的一种精确的表示。然而，如 C 和 C++ 这样的语言的垃圾收集器通常不能维持可达图的精确表示。这样的收集器也叫做保守的垃圾收集器（conservative garbage collector），即每个可达块都被正确地标记为可达了，而一些不可达节点却可能被错误地标记为可达。

收集器可以按需提供它们的服务，或者它们可以作为一个和应用并行的独立线程，不断地更新可达图和回收垃圾。

这里到关键思想是收集器代替应用去调用 free。

Mark & Sweep 垃圾收集器

Mark & Sweap 垃圾收集器由标记（mark）阶段和清除（sweep）阶段组成。标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个未被标记的已分配块。

C 程序中常见的与内存有关的错误

间接引用坏指针

scanf("%d", &val); // correct
scanf("%d", val); // incorrect 将 val的 值当作地址

读未初始化的内存

int *y = (int *)malloc(n * sizeof(int));

允许栈缓冲区溢出

char buf[64];
gets(buf);

引用指针，而不是它所指向的对象

*size--;
/* vs */
(*size--);

引用不存在的变量

int *stackref() {
  int val;
  // foo
  return &val;
}