CSAPP 09 - 虚拟内存

发表于 更新于 分类于 评论数： 阅读次数：

  现代系统提供了一种对主存的抽象概念，叫做虚拟内存。

  虚拟内存是硬件异常，硬件地址翻译，主存，磁盘文件和内核软件的完美交互。它为每个进程提供了一个大的，一致的和私有的地址空间。虚拟内存有三个重要能力：

  • 将主存看作存储在磁盘上地址空间的高速缓存，只保存活动区域
  • 为每个进程提供了一致的地址空间，简化内存管理
  • 保护每个进程的地址空间不被其他进程破坏

内存寻址

  计算机系统主存被组织为一个由 M 个连续字节大小单元组成的数组。每个字节都有一个唯一的物理地址 PA，第一个字节的地址为 0，下一个为 1，以此类推。CPU 访问内存最自然的方式就是使用物理地址，也叫物理寻址。

  然而，现代处理器使用的是虚拟寻址的寻址方式：

  CPU 通过生成一个虚拟地址 VA 来访问主存，这个虚拟地址在被传送到主存前先被转换为适当的物理地址，转换过程叫做地址翻译。地址翻译需要 CPU 硬件和操作系统相互配合，CPU 芯片上有一个内存管理单元 硬件 MMU，利用存放在主存中的查询表来动态翻译虚拟地址，查询表的内容由操作系统管理。

地址空间

  地址空间是一个非负整数地址的有序集合：{0, 1, 2, …}。如果地址空间中的整数是连续的，就可以将其称作线性地址空间，一般来说，地址空间都是线性的。

  在一个带有虚拟内存的系统中，CPU 从一个 N = 2n 个地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间：{0, 1, 2, …, N - 1}。地址空间的大小由最大地址所需要的位数来描述，一个包含 N = 2n 个地址的虚拟地址空间叫做一个 n 位地址空间。

  一个系统还有物理地址空间，对应系统中物理内存的 M 个字节：{0, 1, 2, …, M - 1}。M 不要求是 2 的幂，但是为了简化讨论，还是假设 M = 2m。

  有了地址空间的概念，可以将其推广：允许每个数据对像有多个独立的地址，其中每个地址都选自一个不同的地址空间。主存中每个字节都有一个选自虚拟地址空间的虚拟地址，和选自物理地址空间的物理地址。

缓存工具

  虚拟内存被组织为一个存放在磁盘上的 N 个连续字节的数组。每个字节都有一个虚拟地址，作为到数组的索引。磁盘上的内容被缓存到主存中：VM 系统将虚拟内存划分割为虚拟页大小的固定块，虚拟页是磁盘到较高层次储存器之间的数据传输单位。每个虚拟页的大小为 P = 2p 字节，类似的，物理内存也被划分为物理页 (页帧)，大小也为 P。

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

  • 未分配的：VM 系统还未分配的页。未分配的页不关联任何数据，因而不占用磁盘空间。
  • 缓存的的：当前已缓存在物理页中的已分配页。
  • 未缓存的：未缓存在物理内存中的已分配页。

DRAM 缓存

  CPU 和主存之间的 L1 L2 和 L3 级缓存称为 SRAM 缓存，主存中用来缓存虚拟页面的缓存称为 DRAM 缓存。

  与 SRAM 缓存相比，DRAM 缓存发生缓存缺失的成本很高：从磁盘读取加载数据很慢。因此虚拟页面往往比较大，通常为 4 KB 到 2 MB。并且 DRAM 缓存是全相联的，即任何虚拟页都可以放在任何物理页中。

  不命中时的替换策略也很重要，因为替换错了虚拟页的处罚也很高。因为对磁盘的访问时间很长，DRAM 缓存总是使用写回，而不是直写。

页表

  VM 系统通过页表来判定一个虚拟页是否缓存在 DRAM 中的某个地方，如果是，系统还必须确定这个虚拟页存放在哪个页帧中。如果不命中，系统还必须判断这个虚拟页存放在磁盘的哪个位置，然后再物理内存中选择一个牺牲页，将虚拟页从磁盘复制到 DRAM 中，并替换掉牺牲页。

  页表是一个存放在物理内存中的数据结构，页表将虚拟页映射到物理页。每次地址翻译时，MMU 都会读取页表。操作系统负责维护页表的内容，以及在磁盘和 DRAM 之间来回传送页。

  页表就是一个由页表条目 PTE 组成的数组：

  虚拟地址空间中每个页在页表中的一个固定偏移位置都对应一个 PTE。PTE 是由一个有效位和一个 n 位地址字段组成的。有效位表明了该虚拟页是否被缓存在 DRAM 中：如果设置了有效位，那么地址字段就代表了物理页的起始位置。如果没有设置，要么用一个空地址表示页还未分配，要么用一个地址表示虚拟页在磁盘上的起始位置。

页命中

  假设 CPU 要读取包含在 VP2 中虚拟内存中的一个字。VP2 被缓存在 DRAM 中，MMU 将虚拟地址作为一个索引来定位 PTE2，并从内存中读取它。因为设置了有效位，所以 MMU 知道它被缓存在内存中了。所以它使用 PTE 中的物理地址，构造出这个字的物理地址：

缺页

  假设 CPU 引用了 VP3 中的一个字，VP3 并未缓存在 DRAM 中。MMU 从内存中读取 PTE3，从有效位得知 VP3 并未被缓存，因此触发了一个缺页异常。缺页异常调用缺页异常处理程序，该程序会选择一个牺牲页 (如果没有空页帧) 进行替换。如果该牺牲页已经被修改，那么系统会将其写回磁盘后再替换。

  接下来，内核会从磁盘复制 VP3 到某个页帧，并更新 PTE，随后返回。当异常处理程序返回时，他会重启导致缺页的指令，此后和页命中情况一致：

分配页面

  操作系统分配一个新的虚拟页面 (如 malloc 调用) 时，页表的变化：

  VP5 的分配过程是在磁盘上创建空间并更新 PTE5，使它指向磁盘上这个新创建的页面。

内存管理

  实际上，操作系统为每个进程都提供了一个独立的页表，也就是一个独立的虚拟地址空间：

  进程 i 的页表将 VP1 映射到 PP2，将 VP2 映射到 PP7。进程 j 的页表将 VP1 映射到 PP7，将 VP2 映射到 PP10。注意：多个虚拟页面可以映射到同一个共享物理页面。

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

  • 简化链接：独立的虚拟地址空间允许每个进程使用相同的内存结构，因此链接器无需考虑可执行文件的代码和数据在物理内存中的实际位置。这种统一性极大地简化了链接器的设计和实现。
  • 简化加载：若要将目标文件的 .text 和 .data 段加载到一个新进程的地址空间中，加载器只需为它们分配虚拟页面，然后将其标记为未缓存，最后再将页表条目指向目标文件中对应的位置。实际上，加载器从未将任何数据从磁盘复制到主存中，代码和数据只有在被第一次引用时才会按需分页。
  • 简化共享：操作系统可以将不同进程中的不同虚拟页面映射到相同的物理页面，从而实现进程之间代码和数据的共享。
  • 内存分配：当应用程序申请额外的内存时，操作系统会为其分配一定数量的连续虚拟页面，然后将它们映射到任意位置的物理页面。这些物理页面无需连续，并且可以在物理内存中随机分布。

内存保护

  任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问。提供独立的地址空间使得区分不同进程的私有内存变得很容易。因为每次 CPU 访问内存时，地址翻译硬件都会读取 PTE，所以通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问：

  SUP 表示是否只有在内核态运行的进程才能访问该页面，READ 和 WRITE 则分别表示页面是否可读写。例如，进程 i 在用户态中运行，那么它可以读取 VP 0，读取和写入 VP 1，但无法访问 VP 2。

  如果某条指令违反了上述权限，CPU 就会触发通用保护故障，并将控制权转移到内核中的异常处理程序。该处理程序会向问题进程发送一个 SIGSEGV 信号，shell 通常将此异常报告为段故障并终止程序。

地址翻译

  形式上来说，地址翻译是一个 N 元素的虚拟地址空间中的元素和一个 M 元素的物理地址空间中元素的映射。MMU 利用页表来实现这种映射，CPU 中的一个控制寄存器页表基址寄存器指向当前页表。n 位的虚拟地址包含两个部分：一个 p 位的虚拟页面偏移 VPO 和一个 n - p 位的虚拟页号 VPN。

  MMU 利用 VPN 来选择适当的 PTE。将 PTE 中的物理页号和虚拟地址中的 VPO 串联起来，就得到了相应的物理地址。因为物理页帧和虚拟页面都是 P 字节，所以物理页面偏移 PPO 和 VPO 是相同的。

  发生页命中时，硬件执行的步骤：

  1. 处理器生成一个虚拟地址，将其传给 MMU
  2. MMU 生成 PTE 地址，并从高速缓存或主存中请求
  3. 高速缓存或主存向 MMU 返回 PTE
  4. MMU 构造物理地址，并将地址传给高速缓存或主存
  5. 高速缓存或主存返回所请求的数据字给 CPU

  页命中完全是由硬件处理的，但是处理缺页时，硬件会和操作系统协作完成：

  1. 前三步和页命中情况一致
  2. PTE 中有效位是 0，所以 MMU 触发一次异常，控制被传递给内核中的缺页异常处理程序
  3. 缺页处理程序选择一个牺牲页 (如果没有空页帧)，如果这个页帧被修改了，则先将其换出磁盘
  4. 缺页处理程序调入新的页面，并更新内存中的 PTE
  5. 缺页处理程序返回到原来进程，重新执行指令

结合高速缓存

  在同时使用虚拟内存和 SRAM 高速缓存的系统中，大多数系统选择使用物理寻址而不是虚拟寻址来访问 SRAM。使用物理寻址可以简化多个进程共享相同存储块的问题，并且高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。注意，地址翻译发生在高速缓存查找之前：

快表加速翻译

  之前的例子中，每次 CPU 产生一个虚拟地址，MMU 都必须查阅一个 PTE。然而页表存放在主存中，访问主存的速度远不及高速缓存，如果 PTE 被缓存在 L1 中，那么 PTE 命中查询的开销就下降到 1 或 2 个时钟周期。为了进一步提高性能，许多系统在 MMU 中包含了一个关于 L1 PTE 的小的缓存，叫做快表 TLB。

  快表是一个小的，虚拟寻址的缓存，其中每一个行都保存着由单个 PTE 组成的块，TLB 通常有高度的相联度。TLB 表目中，用于组选择和行匹配的字段都是从 VPN 中提取出来的。

  当 TLB 命中时，所有的翻译步骤都在 MMU 中进行，因此非常快：

  1. CPU 产生一个虚拟地址
  2. MMU 直接从 TLB 中取出相应的 PTE
  3. MMU 根据虚拟地址和 PTE 信息构造物理地址，发送给高速缓存或主存
  4. 高速缓存或主存将请求的数据字返回给 CPU

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

多级页表

  之前的例子都假设系统中只用一个页表来进行地址翻译。但是如果系统有 32 位的地址空间，4KB 的页面的大小，4 字节大小的 PTE 时，那么即使应用只引用虚拟地址空间中很小的一部分，也总是需要一个 4MB 的页表驻留在内存中。对于 64 位的系统来说，问题更加复杂。

  压缩页表的常用方式是使用层次结构页表：

  一级页表中有 1024 条 PTE，每条 PTE 都映射到一个包含 1024 个连续虚拟页面的地址空间块。每个地址空间块的大小为 1024 * 4 KB = 4 MB，因此 1024 条 PTE 就可以覆盖 32 位地址空间。

  如果地址空间块中的所有页面均未分配，则一级页表中对应的 PTE 为空。如果地址空间块中至少有一个页面已分配，那么一级页表中对应的 PTE 就指向二级页表中该块的起始位置。二级页表中的每条 PTE 都映射到一个 4 KB 的物理内存页，与之前查看的单级页表相同。

  若一级页表中的 PTE 为空，那么二级页表内对应的条目就无需存在。多数应用程序的虚拟地址空间中大部分页面是未分配的，因此这将显著地降低页表的内存占用。另外，只需在主存中维护一级页表和被调用最为频繁的二级页表，其它的二级页表可以由操作系统按需创建和分页。

  描述 k 级页表层次的地址翻译时，虚拟地址被划分为 k 个 VPN 和一个 VPO。每个 VPN i 都是一个到 i 级页表的索引。第 j 级页表的每个 PTE 都指向第 j + 1 级页表的基址。第 k 级页表中每个 PTE 都包含某个物理地址页面的 PPN 或者磁盘地址。

  为了构造物理地址，在确定 PPN 之前，MMU 必须访问 k 个 PTE。并且和一级页表一样，VPO 和 PPO 是相同的。由于 TLB 的作用，多级页表的地址翻译其实不比单极页表慢很多。

TODO 综合

  待更新。

Linux/Core i7 实例

  在一个运行 Linux 的 Intel Core i7 的实际的系统上，虽然底层的 Haswell 微架构能够支持完整的 64 位虚拟和物理地址空间，但目前 Core i7 仅提供了 48 位 (256 TB) 的虚拟地址空间和 52 位 (4 PB) 的物理地址空间，以及一个支持 32 位 (4 GB) 虚拟和物理地址空间的兼容模式。

内存系统

  在这个系统中，CPU 有四个核心，且每个核心都有自己的 L1 L2 级高速缓存，所有的核心共享一个 L3 高速缓存。并且三级缓存都使用物理寻址。页大小可以在启动时被配置为 4KB 或者 4MB，Linux 使用 4KB 的页。

地址翻译

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

  虚拟地址中 36 位的 VPN 被划分为 4 个 9 位的片，每个片作用到一个页表的偏移量：

Linux 虚拟内存系统

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

  内核虚拟内存包含内核中的代码和数据结构，内核虚拟内存的某些区域被映射为所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据结构。Linux 也将一组连续的虚拟页面 (大小等于 DRAM) 映射到一组连续的物理页面，这么做方便了内核访问物理内存中的任何位置。

内存区域

  Linux 将虚拟内存组织为一些区域的集合。一个区域就是已分配的虚拟内存连续片，这些页以某种方式相关联。例如，代码段，数据段，栈，堆等都是不同的区域。每个存在的虚拟页都属于某个区域，不存在某个不属于某个区域的虚拟页，并且其不能被进程引用。区域的概念允许虚拟地址空间有间隙，而不存在的虚拟页也不被内核记录，也不占用空间。

  内核为每个进程都维护一个单独任务结构 task_struct。任务结构中包含或指向内核运行该进程所需要的所有信息，如 PID，指向用户栈的指针，程序计数器等。

  任务结构的一个条目指向 mm_struct，后者描述了虚拟内存的当前状态。结构中 pgd 指向一级页表的基址，mmap 指向一个 vm_area_structs 区域结构的链表。其中每个 vm_area_structs 都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将 pgd 放进 CR3 寄存器中。

  一个区域结构包含下列字段：

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

缺页异常

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

  1. 检测虚拟地址是否合法 (A 是否在某个内存区域中)：缺页处理程序将搜索区域结构链表，把 A 和每个区域的 vm_start 和 vm_end 比较。如果 A 不属于任何区域，那么缺页处理程序就会触发段错误，终止程序。

  2. 检测内存访问是否合法 (进程是否有读写或执行权限)：缺页处理程序会检测进程是否违反权限来访问内存，如试图在一个只读的页上写数据。这种情况会触发保护异常，导致程序终止。

  3. 如果内存访问通过了内核检测，那么内核将选择一个牺牲页 (如果没有空页帧)，如果牺牲页被修改过，那么就将其换出磁盘，最后换入新的页面并更新页表。随后，缺页处理程序会将控制返回，重启内存访问指令。

内存映射

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

  1. Linux 文件系统中的普通文件

  一个区域可以映射到一个普通磁盘文件的连续部分，如可执行目标文件。文件被分成页大小的片，每一片包含一个虚拟页面的初始内容。**因为按需进行页面调度，所以这些虚拟页面没有实际交换进物理内存。**直到 CPU 第一次引用该页面，即发射一个虚拟地址，落在这个页面范围之内。如果区域比文件区大，就用零来填充余下的部分。

  1. 匿名文件

  一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制的零。CPU 第一次引用这个区域的一个页面时，内核就在物理内存中找到一个合适的页面，然后用二进制的零覆盖页帧并更新页表。映射到匿名文件的页面页叫做请求二进制零的页。

  无论哪种情况，一旦一个虚拟页面已经被初始化，它就在一个内核维护的专门的交换文件之间换来换去。交换文件也被叫做交换空间或者交换区域。

共享对象

  内存映射提供了一种将程序和数据加载到内存中的简单而又高效的方法。一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。如果一个进程将共享对象映射到它的某个虚拟内存区域中，那么该进程对这个区域的任何写操作，都对其他共享这个对象的进程可见。而且，这些变化也会反映在磁盘上的原始对象上。

  但是，对于一个映射到私有对象的区域所做的改变，对于其他进程来说是不可见的，并且变化也不会反映到磁盘上的对象上。一个映射到共享对象的虚拟内存区域叫做共享区域，类似的也有私有区域。

  私有对象使用写时复制技术被映射到虚拟内存中。私有对象和共享对象一样，在物理内存中都只保留一份副本。如果两个进程映射了一个私有对象，那么他们共享同一个物理副本。并且相应区域的 PTE 都被标记为只读，但是区域结构被标记为私有的写时复制。只要进程没有试图写他的私有区域，他们就可以继续共享副本。然而，只要有一个进程试图写某个私有对象区域的页面，那么这个写操作就会触发一个保护故障。

  故障处理程序检测到这是由于进程试图写一个私有写时复制区域的页面，它会在物理内存中创建一个这个页面的新副本，更新这个新页面的可写权限，当故障处理程序返回时，CPU 重启这个写操作，现在就可以在新页面上正常写数据了。

fork 函数

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

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

execve 函数

  execve 函数在当前进程加载并运行可执行目标文件需要以下步骤：

  1. 删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构。
  2. 映射私有区域：为新程序的代码，数据，bss 和栈区创建新的区域结构，所有这些新区域都是私有的，写时复制的。代码和数据被映射为文件中的 .text 和 .data 区。bss 区域是请求二进制零的，映射到匿名文件，其大小在程序文件中定义。栈区和堆区也是请求二进制零的，初始长度为零。
  3. 映射共享区域：如果加载的程序与共享对象链接，那么这些对象都是动态链接到这个程序的，再映射到用户虚拟地址空间中的共享区域内。
  4. 设置程序计数器：最后一件事就是将控制移交给新程序。

  下一次调度这个进程时，它将从这个入口点开始运行。Linux 将按需换入代码和数据页面。

mmap 函数

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

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

  mmap 函数要求内核创建一个新的虚拟内存区域，最好是从地址 start 开始。并将文件描述符为 fd 指定的对象的一个连续片映射到这个区域。连续的对象片的大小为 length 字节，从距文件开始处的偏移 offset 处开始。start 只是一个暗示，通常被定义为 NULL。

  参数 prot 描述了新映射的虚拟内存区域的访问权限位 (vm_prot)：

  • PROT_EXEC：这个区域的页面由可以被 CPU 执行的指令组成。
  • PROT_READ：这个区域的页面可读。
  • PROT_WRITE：这个区域的页面可写。
  • PROT_NONE：这个区域的页面不能被访问。

  参数 flags 由描述映射对象类型的位组成：MAP_ANON 表示映射的是一个匿名对象，其相应的虚拟页面是请求二进制零的。MAP_PRIVATE 表示映射的是一个私有的，写时复制的对象。MAP_SHARED 表示是一个共享对象。并且，这些位可以相互组合。

  在指定参数时，如果 flags 的组合包含 MAP_ANON，那么内核将忽略传递的 fd，而创建一个匿名文件映射。如果映射的是普通文件，那么 length 必须是页面大小的整数倍，小于一个页面大小时，内核会自动上调区域大小。注意，创建共享文件映射时，如果文件大小小于虚拟页面大小，余下的虚拟页面会被初始化为 0，在将内存区域同步到底层文件时，内核只会同步文件大小的内容，不会将大于文件的虚拟内存内容同步到文件中。

  munmap 函数删除虚拟内存的区域：

int munmap(void *start, size_t length);

  munmap 函数删除从虚拟地址 start 开始的，由接下来 length 字节组成的区域。接下来对已删除的区域的引用会导致段错误。

动态内存分配

  除了使用低级的函数 mmap 和 munmap 来创建和删除虚拟内存的区域外。更方便简单的方式，是使用 C 标准库中的动态内存分配器。

  动态内存分配器维护着一个进程的虚拟内存区域，称为堆。假设堆是一个请求二进制零的区域，它紧接在 bss 段后面开始，并并且向上生长。对于每个进程，操作系统都维护一个变量 brk，它指向堆顶。

  分配器将堆视为一组不同大小的块的集合，每个块就是一个连续的虚拟内存片，要么是已分配的，要么是空闲的，空闲块可以用来分配。一个已分配的块保持已分配状态，直到它被释放，释放要么是有程序显示执行，要么是内存分配器隐式执行。

  分配器有两种风格，两种风格都要求应用显示的分配块，但是区别在由哪个实体来负责释放已分配的块：

  • 显示分配器：要求应用显示的释放任何已分配的亏啊。C 程序通过 malloc 函数来显示分配一个块，并通过调用 free 函数来显示释放一个块。
  • 隐式分配器：隐式分配器被要求检测一个已分配块何时不被使用，然后释放这个块。隐式分配器也叫垃圾收集器，而自动释放已分配块的过程叫做垃圾收集。

malloc 和 free

  C 标准库提供 malloc 函数来从堆中分配块：

void *malloc(size_t size);

  malloc 函数返回一个指针，指向大小至少为 size 字节的内存块，**这个块会为可能包含在这个块内的任何数据对象类型做对齐。**在 32 位系统中，malloc 返回的地址总是 8 的倍数，在 64 位系统中，该地址总是 16 的倍数。

  如果 malloc 遇到问题，那么就返回 NULL，并设置 errno。malloc 不会初始化它返回的内存。

  动态内存分配器，可以通过使用 mmap 和 munmap 函数，显示的分配和释放堆内存。还可以使用 sbrk 函数：

void *brk(intptr_t incr);

  sbrk 函数通过将内核 brk 指针增加 incr 来扩展和收缩堆。如果成功，它就返回 brk 的旧址，否则返回 -1。如果 incr 为零，那么就返回 brk 当前值。负的 incr 是合法的。

  程序可以使用 free 函数来释放已分配的堆块：

void free(void *ptr);

  free 函数必须指向一个从 malloc calloc realloc 获得的已分配的块的起始位置，否则，行为是未定义的。

分配器要求和目标

  显示分配器必须满足以下要求：

  • 处理任意顺序的请求：分配器不能对 malloc 和 free 的请求顺序作出假设。例如，分配器不能假设所有的 malloc 都紧跟一个与之匹配的 free。
  • 立即响应请求：分配器不可以对请求重新排序或缓冲以提高性能。
  • 仅使用堆：分配器使用的数据结构必须存储在堆中。
  • 对齐块：分配器必须对齐块以使其能够容纳任何类型的数据对象。
  • 不修改已分配的块：分配器无法修改、移动或压缩已分配的块。

  描述分配性性能的两个指标：

  • 吞吐率：每个单位时间内能完成的请求数。
  • 内存利用率：堆内存的使用率。

  如果一个应用请求 p 字节的块，那么得到的已分配块的有效载荷是 p 字节。在完成请求序列 R0 R1 … Rk 后，聚集有效载荷表示为 Pk，为当前已分配块的有效载荷之和。Hk 表示当前堆大小，峰值利用率 Uk = maxPi / Hk (i <= k)。分配器设计的目标就是使 Un-1 最大化。

碎片问题

  碎片是造成堆利用率低的一个主要原因，当虽然有未使用的内存但是不能用来满足分配请求时发生这种现象。碎片有两种形式：内部碎片和外部碎片。

  • 内部碎片

  内部碎片发生在一个已分配的块比有效载荷大时。很多原因都会造成这个问题，例如分配器为了满足地址对齐要求，额外增加块的大小。

  • 外部碎片

  外部碎片发生在空闲内存充足但却没有空闲的能够满足分配请求时。例如堆中有 4 个空闲的字且分布在两个不相邻的块上，此时若进程申请一个 4 字的块就会出现外部碎片。

  内部碎片很容易量化，因为它只是已分配块与有效载荷之间大小差异的总和，其数量仅取决于先前的请求模式和分配器的实现方式。外部碎片则难以量化，因为它还要受到未来请求模式的影响。为了减少外部碎片的产生，分配器力求维护少量较大的空闲块而非大量较小的空闲块。

实现问题

  假设一个简单的分配器，它将堆看作一个大型的字节数组，指针 p 指向该数组的第一个字节。当进程请求 size 大小的块时，malloc 先把 p 的当前值保存在栈中，然后将其加上 size，最后返回 p 的旧值。当进程想要释放块时，free 则只是简单地返回给调用者而不做任何事情。

  由于 malloc 和 free 仅由少量指令组成，这种分配器的吞吐量很大。然而 malloc 不会重用任何块，因此堆内存的利用率非常低。能够在吞吐量和内存利用率之间取得良好平衡的分配器必须考虑以下问题：

  • 空闲块组织：如何记录空闲块
  • 放置：如何选择一个合适的空闲块来防止一个新分配的块
  • 分割：完成放置后，如何处理这个空闲块中剩余的部分
  • 合并：如何处理一个刚刚被释放的块

隐式空闲链表

  实际上，分配器需要一些数据结构来区分边界，以及区分已分配块和空闲块。

  在这种情况中，一个块是由一个字 (这里是 4 字节)，有效载荷，以及可能的额外填充块组成的。头部编码了这个块的大小 (包括头部和填充)，以及这个块是已分配还是空闲的。因为对齐要求，这个块的大小总是 8 的倍数，所以低三位总是 0，那么可以将低三位拿来指明块是已分配的还是空闲的。

  头部后面就是有效载荷，有效载荷后面是可能的填充，其大小任意。一个堆可能的组织情况：

  这种结构称为隐式空闲链表，是因为空闲块是通过头部中大小字段隐含的连接的。分配器可以通过遍历堆中所有块，从而间接的遍历所有的空闲块。最后需要一个终止标记 (0 / 1) 即大小为 0 的已分配块。

  隐式空闲链表的优点是简单，缺点是开销问题。很重要的一点是，因为系统和分配器的对齐要求，头部总是占有一个字的大小，所以即使请求一个字节，分配器也会分配 2 个字的块。

放置已分配的块

  当程序请求一个 k 字节的块时，分配器需要在空闲链表中选取一个足够大的块以响应。分配器搜索空闲块的方式由放置策略所决定，常见的策略有三种：

  • 首次适配：从头开始遍历空闲链表并选择第一个满足条件的块。
  • 下一次适配：从上一次搜索停止的地方开始遍历空闲链表并选择第一个满足条件的块。
  • 最佳适配：遍历所有块并选择满足条件且最小的块。

  首次适配的优点是较大的块通常存留在链表末尾，但一些较小的块也会散落在链表开头，这将增加搜索较大块的时间。如果链表开头存在大量较小的块，下一次适配就比第一次适配快很多。然而研究表明，下一次适配的内存利用率比第一次适配低。最佳适配的内存利用率通常比其他两种策略高，但对隐式空闲链表来说，其搜索时间显然要比它们慢很多。

分割空闲块

  如果分配器找到了合适的块并将整个块分配给程序，就有可能产生内部碎片。为了避免这一问题，分配器可以将选取的块分成一个已分配的块和一个新的空闲块：

  程序请求一个 3 字的块，于是分配器将上面 8 字的空闲块拆分为两个 4 字的块并将其中之一分配给它。

扩展堆内存

  如果分配器无法找到合适的块，它可以尝试将相邻的空闲块合并以获取更大的块。但如果仍然无法满足请求，分配器便会调用 sbrk 函数向内核请求额外的堆内存并将其转换为一个新的空闲块，然后插入到空闲链表中。

合并空闲块

  当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的块相邻。这些相邻的空闲块引起一种假碎片现象，即有许多可用的空闲块被分割为小的，无法使用的空闲块。如果释放上面的已分配块，虽然中间已经空出来 8 字，但是却因为假碎片无法相应一个 4 字请求。

  为了解决假碎片问题，分配器必须合并相邻的空闲块。合并必须考虑何时执行合并，有两种策略：

  • 立即合并：在一个块被释放时，就立即合并所有的相邻空闲块。
  • 推迟合并：到某个稍晚的时间再合并，如直到某个分配请求失败。

  立即合并很简单，但它也有可能造成抖动问题，即某个块在短时间内被多次合并和分割。

边界标记合并

  这里假设要释放的块是当前块，合并当前块的下一个空闲块很简单，只需要根据头部就能得到下一个空闲块的位置，因此只需要将下一个空闲块的大小加给当前块的头部。

  要合并当前块的前一个空闲块时，一种最暴力的方法是搜索整个链表，直到当前块的前一个空闲块。另一种通用技术是边界标记技术，其思想是：在每个块的结尾处添加一个脚部，脚部就是头部的副本。有了脚部，分配器可以很容易获取上一个块的状况和信息。

  为每个块添加一个脚部会增加内存开销，尤其是遇到反复操作多个小块时。一种优化策略是：只在空闲块上添加脚部，已分配块上不需要添加脚部。当前块的头部中，有三个低位，其中一个低位表示是否分配，可以再用一个低位来指明上一个块是否被分配。

TODO 综合

  待更新。

显式空闲链表

  隐式空闲链表很简单，但是不适用于通用分配器，因为其分配块的时间与堆块总数成线性关系。一种更好的方法是将空闲块组织为某种形式的显示数据结构。因为根据定义，程序不需要一个空闲块主体。例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个先驱 pred 和一个后继 succ 指针。

  使用双向空闲链表，使得首次适配的分配时间较少到与空闲块的数量成线性关系。不过释放一个块的时间，可以是线性的也可以是常数的：

  • 使用 LIFO 的顺序维护链表，将新释放的块插入到链表的开始处。这种情况下，释放一个块和合并空闲块都可以在常数时间内完成。
  • 按照地址顺序来维护链表，其中链表中每个块的地址都小于它的后继地址。此时，释放一个块需要一个线性时间。但是作为补偿，按照地址顺序排序的首次适配有更高的内存利用率，接近最佳适配的利用率。

  显式空闲链表的缺点在于指针的引入增加了空闲块的大小，这将增大内部碎片发生的可能性。

TODO 分离空闲链表

  待更新。

TODO 垃圾收集

  待更新。

TODO C 与内存

  待更新。