计算机系统虚拟内存分享

前言

该分享文档，是基于《深入理解理解计算机系统》第三版关于内存方面的总结。下述所有模型图，在原书中均有示例。
由于这里主要分享虚拟内存，关于物理内存部分，简单描述

分享的主要问题

1. 计算机物理内存层次结构
2. 什么是虚拟内存
3. 虚拟内存的实现
4. 程序内虚拟内存分配和释放

物理内存

常见的存储技术

在计算机体系中，CPU执行指令，而存储器为CPU存放指令和数据。
实际上，计算机的存储器系统是一个具有不同容量、成本和访问时间的存储设备层次结构。
层次越高的存储越快，价格越高。例如若程序需要的数据存储在CPU寄存器中，在指令的执行周期内，0个周期内就可以访问到他们；如果存储在高速缓存中，需要4~75个周期；如果在主存上，需要上百个周期；而如果存储在磁盘上，需要大约几千万个周期。

随机访问存储器

随访访问存储器（Random-Access Memory,RAM）分为两类：静态和动态的。

1. 静态RAM：不需要刷新电路就能保存数据，所以具有静止存取数据作用，多以多用在Cache。SRAM用来作为高速缓存存储器，可以用在CPU芯片上。
2. 动态RAM：DRAM只需要一个电容和一个晶体管，廉价，但是由于对于干扰敏感，需要不断刷新。DRAM用来作为主存以及图形系统的帧缓冲区。

SRAM比DRAM更快，但是也贵的多。因此类似 MAC，SRAM不会超过几兆字节，但是DRAM却有几千兆字节。

DRAM芯片封装在内存模块（Memeory Module）中，它可以插到主板卡槽上，通过将多个内存模块连接到内存控制器，就聚合成了主存。为了降低芯片上地址引脚数量，DRAM被组织成二维矩阵，而不是线性数组。因此在发送数据时候，必须拆分两步，先选中行，然后将行数据存入一个锁存器，然后等列地址传数，然后再选中所需数据。

数据流通过总线（bus）的共享电子电路在处理器和DRAM主存之间来来回回，每次CPU和主存之间的数据传输都是通过一系列步骤（总线事物）来完成的。主存到CPU为读事物，CPU到主存为写事物。

非易失性存储器

DRAM和SRAM在断电后会丢失信息，非易失性存储器（nonvolatile memory）为即使关电后，仍然保存着它们的信息。这些存储器虽然现在既可读，也可写，但是由于历史原因，仍然被称为ROM（Read-Only Memory,ROM）
常见的ROM，包含：

1. PROM（Programmable ROM），可编程式ROM，只能被编程一次
2. 可擦写式ROM（Erasable Programmable ROM，EPROM），可以多次使用，常见的为光存储和电子可擦除（EEPROM）
3. 闪存（Flash），基于EEPROM

磁盘存储

磁盘广为应用是保存大量数据的存储设备，数量用百G记，但是磁盘上读信息时间为毫秒级，比DRAM读满了10万倍，比SRAM读慢了100万倍。

常见旋转磁盘（disk）和固态硬盘（Solid State Disk，SSD）。其中固态硬盘是基于闪存的存储技术，SSD读比写要快。

SSD速度位于DRAM和旋转磁盘之间。

如下图，存储器层次结构的中心思想是，对于每个K层，位于K层的更快更小的存储设备作为用于位于K+1层的更大更慢的设备中的数据对象的缓冲区域。

局部性

一个编写良好的计算机程序常常具有良好的局部性（locality）。也就是，它们倾向于引用临近于其他最近引用过得数据项的数据项，或者最近引用过的数据项本身。这种倾向性被称为局部性原理。

在一个拥有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再次被多次引用。在一个拥有空间局部性的程序中，程序大概率会在不远的将来引用附近的一个内存位置。

局部性原理：指CPU访问存储器时候，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续空间中。通常包含三种不同类型的局部性原理：

1. 时间局部性：如果一个数据被访问，那么这个数据可能还会被再次访问，例如循环中的变量。
2. 空间局部性：在未来（最近的）将会用到的信息与正在使用的信息在空间上是邻近的（步长）。
3. 工作集理论：进程访问时被频繁访问的页面集合，在同一时间内不会马上替换出去。

现代计算机系统的各个层次，从硬件到操作系统，在到应用程序，他们的设计都利用了局部性原理。在硬件层，局部性原理允许计算机设计者通过引入高速缓存存储来保存最近被引用的指令和数据项。

在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间被引用块的高速缓存。

虚拟内存简介

在介绍虚拟内存之前，我们先来看一张工作中常被问到的图

在这张图中，有我们日常开发中，经常提到的堆栈，然而在上述的物理内存中，并不存在这样的概念。所谓的堆栈，其实是在虚拟内存中抽象的一个概念。

虚拟内存是强大的，它给予应用程序强大的能力，可以创建和释放内存片（chunk），进程之间也可以通过内存片映射共享内存。

同时虚拟内存也是核心的，它遍布计算机系统所有层面，在硬件异常、汇编器、链接器、加载器、共享对象、文件和进程的设计中扮演着重要角色。

在计算机系统中，每次程序引用一个变量、间接引用一个指针、或者调用malloc或free方法时候，都是在和虚拟内存发生交互。

下面我们就正式介绍虚拟内存。

虚拟内存是什么

首先要强调下虚拟的概念，它是抽象的，不是实际存在的。

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

虚拟内存（VM）是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件完美交互，是现代计算机为了更加有效管理内存并减少出错，提供的一种对主存的抽象概念。

虚拟内存的关键能力

虚拟内存的关键能力：

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

物理寻址

计算机系统的主存被组织成一个有M个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址（PA）。第一个字节的物理地址为0，接下来的字节地址为1，再下来为2，依次类推。给定这种简单的结构，CPU访问内存的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址（physical addressing）。

早期的PC使用的是物理地址，而且诸如数字信号处理器、嵌入式微控制器以及Cray超级计算机这样的系统仍然还是继续使用这种寻址方式。

虚拟寻址

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

虚拟内存映射

地址空间

地址空间是一个非负整数的有序集合{0，1，2，.......}。如果地址空间中的整数是连续的，那么我们说它是一个线性的连续地址空间。

在一个带有虚拟内存的系统中，CPU从一个由N个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间（virtual address space）。一个地址空间的大小是由表示最大地址所需要的位数来描叙的。现代系统通常支持32位或者64位虚拟地址空间。

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

虚拟内存映射即为虚拟地址空间到物理地址空间的映射。

MMU 的作用：

MMU 进行虚拟地址转换成为物理地址的过程是 MMU 工作的核心，另外它还包含访问权限控制的作用

后续的一些概念

下面是和虚拟内存相关的一些概念，先简单表述下，后续都会讲到

1. 虚拟地址(virtual memory)：相对物理地址来说的概念，不真实存在的。
2. 物理地址(physical address)：真实存在的，和物理内存关联的。
3. 地址翻译：将虚拟地址映射成物理地址的过程。
4. 页(page)：
   
   通常将虚拟地址空间以512Byte ~ 8K，作为一个单位，称为页，并从0开始依次对每一个页编号。这个大小通常被称为页面。
   
   将物理地址按照同样的大小，作为一个单位，称为框或者块，也从0开始依次对每一个框编号。
5. 页表(page table)：
   
   管理虚拟内存页和物理内存页映射和缓存状态的数据结构。
   
   操作系统通过维护一张表，这张表上记录了每一对页和框的映射关系
6. 页表条目(page table entry PTE)：是构成页表的基本元素，是索引号为虚拟页号、值为物理页号的数组。
7. 虚拟页(VP)：虚拟地址空间划分为多个固定大小的虚拟页。
8. 物理页(PP)：物理地址空间划分为多个固定大小的物理页。
9. 页表基地址寄存器（PTBR）：CPU有一个专门的页表基地址寄存器，指向当前页表的基地址（物理框的起始基地址）。
10. 翻译后备缓冲区（TLB）：一个用来缓存页表条目PTE的硬件设备。
11. MMU(Memory Management Unit)：CPU中含有的硬件，将虚拟地址转换为物理地址。

地址转换的步骤描述

这里我们以页面大小为4k为例

一个4G虚拟地址空间，将会产生1024*1024个页，页表的每一项存储一个页和一个框的映射，所以，至少需要1M个页表条目。如果一个页表条目大小为1Byte，则至少需要1M的空间，所以页表被放在物理内存中，由操作系统维护。

当CPU要访问一个虚拟地址空间对应的物理内存地址时，先将具体的(虚拟地址A)/(页面大小4K)，结果的商作为页表号，结果的余作为业内地址偏移。

例如：

CPU访问的虚拟地址：A

页面：L

页表号：(A/L)

页内偏移：(A%L)

CPU中有一个页表寄存器，里面存放着当前进程页表的起始地址和页表长度。将上述计算的页表号和页表长度进行对比，确认在页表范围内，然后将页表号和页表项长度相乘，得到目标页相对于页表基地址的偏移量，最后加上页表基地址偏移量就可以访问到相对应的框了，CPU拿到框的起始地址之后，再把页内偏移地址加上，访问到最终的目标地址。

虚拟内存的页面调度

请求页面调度即当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由 OS 将其所需页面调入内存。

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

虚拟存储器是由硬件和操作系统自动实现存储信息调度和管理的。它的工作过程包括6个步骤：

1. 中央处理器访问主存的逻辑地址分解成组号a和组内地址b，并对组号a进行地址变换，即将逻辑组号a作为索引，查地址变换表，以确定该组信息是否存放在主存内。
2. 如该组号已在主存内，则转而执行步骤4；如果该组号不在主存内（缺页），则检查主存中是否有空闲区，如果没有，便将某个暂时不用的组调出送往辅存，以便将这组信息调入主存。
3. 辅存读出所要的组，并送到主存空闲区，然后将那个空闲的物理组号a和逻辑组号a登录在地址变换表中。
4. 从地址变换表读出与逻辑组号a对应的物理组号a。
5. 从物理组号a和组内字节地址b得到物理地址。
6. 根据物理地址从主存中存取必要的信息。

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

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

页表

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

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

页表就是一个页表条目（Page Table Entry）的数组。虚拟地址空间中的每个页在页表中都有一个固定的偏移量处都有一个PTE。为了我们的目的，我们假设每个PTE是由一个有效位（valid bit）和一个n位地址字段组成的。有效位表明了该虚拟页面当前是否被缓存在DRAM中。如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么这个空地址表示这个虚拟页还未被分配。否则，这个地址就会指向该虚拟页在磁盘上的起始位置。

在页表条目中，通过有效位与磁盘地址可以产生不同的情况：

1. 有效位为1时候，标识虚拟页已经缓存
2. 有效位为0时候，数值为 null 时候，表示未分配的页
3. 有效位为0，数值不为 null 时候，表示已经分配了虚拟页，但是还未缓存到具体的物理页中（缺页）

注意，这里的缓存是代表内存中存有的数据。

页命中

当CPU 想要读取一个页表内虚拟内存的一个字时候，地址翻译硬件会将虚拟地址作为一个索引来定位页面（例如PTE2），地址翻译硬件会将模拟地址作为一个索引来定位PTE2，并从内存中读取它。

当有效位为1时候，代表页命中，那么地址翻译硬件就知道VP2是缓存在内存中的了。所以它就可以直接使用PTE2表中的物理内存地址（该地址指向PP 1中缓存页的起始位置），构造出这个字的物理地址。

缺页

拟页没有被缓存在物理内存中（缓存未命中）被称为缺页。

当CPU遇见缺页时会触发一个缺页异常，缺页异常将控制权转向操作系统内核，然后调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，如果牺牲页已被修改过，内核会先将它复制回硬盘（采用写回机制而不是直写也是为了尽量减少对硬盘的访问次数），然后再把该虚拟页覆盖到牺牲页的位置，并且更新PTE。

当缺页异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重新发送给MMU。由于现在已经成功处理了缺页异常，所以最终结果是页命中，并得到物理地址。

页面调度

这种在硬盘和内存之间传送页的行为称为页面调度（paging）：页从硬盘换入内存和从内存换出到硬盘。当缺页异常发生时，才将页面换入到内存的策略称为按需页面调度（demand paging），所有现代操作系统基本都使用的是按需页面调度的策略。

虚拟内存调度分为三个方式：分段式、段式和段页式 3种。

1. 页式调度是将逻辑和物理地址空间都分为固定大小的页，主存按页顺序编号，而每个独立编址的程序空间都有自己的页号顺序，通过调度辅存中的程序各页，可以离散装入主存中不同的页面位置，并可以根据表一一映射。
2. 段式调度是按程序的逻辑结构划分地址空间，段的长度是随意的，并且允许伸长，它的优点是消除了内存零头，易于实现存储保护，便于程序动态装配；缺点是调入操作复杂。
3. 将这两种方法结合起来便构成段页式调度。在段页式调度中把物理空间分成页，程序按模块分段，每个段再分成与物理空间页同样小的页面。段页式调度综合了段式和页式的优点。其缺点是增加了硬件成本，软件也较复杂。大型通用计算机系统多数采用段页式调度。

虚拟内存的局部性

虚拟内存跟CPU高速缓存（或其他使用缓存的技术）一样依赖于局部性原则。虽然处理缺页消耗的性能很多（毕竟还是要从硬盘中读取），而且程序在运行过程中引用的不同虚拟页的总数可能会超出物理内存的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面（active page）集合上工作，这个集合被称为工作集（working set）。根据空间局部性原则（一个被访问过的内存地址以及其周边的内存地址都会有很大几率被再次访问）与时间局部性原则（一个被访问过的内存地址在之后会有很大几率被再次访问），只要将工作集缓存在物理内存中，接下来的地址翻译请求很大几率都在其中，从而减少了额外的硬盘流量。

如果一个程序没有良好的局部性，将会使工作集的大小不断膨胀，直至超过物理内存的大小，这时程序会产生一种叫做抖动（thrashing）的状态，页面会不断地换入换出，如此多次的读写硬盘开销，性能自然会十分“恐怖”。所以，想要编写出性能高效的程序，首先要保证程序的时间局部性与空间局部性。

虚拟内存的内存管理与保护

VM作为内存管理工具

上述仅仅是一个单独页表，将一个虚拟地址空间映射到物理地址空间。在实际上，操作系统为每个进程提供了一个独立的虚拟地址空间，大大简化了内存管理。另外，多个虚拟页面可以映射到同一个物理页面上。
操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包含单独的内核和C标准库的副本（例如 printf 函数）。

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

1. 简化链接。独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。
2. 简化加载。虚拟内存使得容易向内存中加载可执行文件和共享对象文件。将一组连续的虚拟页面映射到任意一个文件中的任意位置的表示法称作内存映射（memory mapping）。Linux 提供了一个 mmap 的系统调用，允许应用程序自己做内存映射。
3. 简化共享。独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般情况下，每个进程都有自己私有的代码、数据、堆栈。这些内容不与其他进程共享。在这种情况下，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。
4. 简化内存分配。虚拟内存向用户进程提供一个简单的分配额外内存的机制。当一个用户程序要求额外的堆空间时候，操作系统分配 k 个适当的连续的虚拟内存页面，并且将他们映射到物理内存的中的 k 个任意页面，操作系统没有必要分配 k 个连续的物理内存页面。

VM作为内存保护工具

现代计算机系统为操作系统提供手段来控制对内存系统的访问。

在上图中，每个 PTE 添加了三个控制位， SUP 位表示进程是否必须运行在超级用也就是内核模式下才能访问该页，WRITE 位控制页面的写访问， EXRC 位控制页面的执行。如果有指令违反了这些控制条件，那么 CPU 会触发一个一般保护故障，将控制传递给内核中的异常处理程序。

地址翻译

上述已经简单描述虚拟内存映射，在计算机系统中，硬件还需要支持地址翻译，即 MMU 的相关工作原理。

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

计算机通过MMU硬件利用页表来完成上述映射：

CPU中有一个控制寄存器，页表基址寄存器（Page Table Base Register，PTBR）指向当前页表。n位虚拟地址包含两个部分：一个P位的虚拟页号偏移（Virtual Page Offset，VPO）和一个（n-p）位的虚拟页号（Virtual Page Number，VPN)

MMU用后者选择适当的PTE，再将物理页号和虚拟地址中的VPO串联起来得到物理地址。

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

物理地址是由物理页号和虚拟页面偏移串联起来得到的。

1）页面命中时，执行的步骤（完全由硬件来处理）：

2）缺页时，执行的步骤（硬件和操作系统内核协作完成）：

结合高速缓存和虚拟内存

大多数系统使用物理寻址来访问SRAM高速缓存。

高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。

利用TLB加速地址翻译

如上图，PTE不命中 L1 高速缓存，需要在内存中读取（创建并更新）。每次CPU产生一个虚拟地址，MMU就必须查阅一个PTE，以便将虚拟地址翻译为物理地址。在最糟糕情况下，这会要求内存读取一次数据，代价是几十到几百个周期。

为了消除这样的开销，许多系统在MMU包含了一个关于PTE的小缓存，称为翻译后备缓冲器（Translation Lookaside Buffer，TLB）。

TLB是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。TLB通常有高度的相关联度。如下图所示，用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟号中提炼出来的。如果TLB有 T = 2^t 个组，那么 TLB 索引（TLBI）是有 VPN 的 t 个最低位组成的，而 TLB 标记（TLBT）是由 VPN 中剩余的位组成的。

简单举例：

当cpu要访问一个虚拟地址/线性地址时，CPU会首先根据虚拟地址的高20位（20是x86特定的，不同架构有不同的值）在TLB中查找。如果是表中没有相应的表项，称为TLB miss，需要通过访问慢速RAM中的页表计算出相应的物理地址。同时，物理地址被存放在一个TLB表项中，以后对同一线性地址的访问，直接从TLB表项中获取物理地址即可，称为TLB hit。

下述为TLB命中（通常情况）时候的步骤。由于所有地址翻译步骤都在芯片MMU上，因此非常的快

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

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

TLB介于CPU与高速缓存/内存之间，用于程序从逻辑地址访问内存地址的页表缓存

多级页表

虚拟地址空间以页面为单位划分。在物理内存中对应的单位称为页帧。页面和页帧的大小总是一样的。

假设页面的大小为4KB，下面是一个页表给出虚拟地址与物理内存地址之间的映射关系

这样的页表，有两个很主要的问题

1）页表有可能非常大

2）地址映射必须非常快

这里重点讨论第一个问题，第二个问题可以通过硬件去解决。

第一个问题的产生是由于现代计算机使用的虚拟地址至少是32位的。比如，当页面大小为4KB时，4字节的PTE，32位的地址空间将有100万个页面，4MB（4GB/4KB*4B），64位的地址空间则更多。虚拟地址空间中的100万个页面需要有100万个表项的页表。并且请记住，每个进程都需要有自己的页表（因为每个进程有自己的虚拟地址空间）。

显然不可能每个进程都将自己的页表保存在内存中。

为此，用来压缩页表的常用方法是使用层次结构的页表（多级页表），如下图。

一级页表中的每个PTE负责映射虚拟内存地址空间中的一个4MB的片（chunk），这里每一片都由1024个连续的页面组成。

如果片i中的每个页面都未分配，那么这一级的PTEi就为空

二级页表中的每个PTE负责映射一个4KB的虚拟内存页面。

这种层次结构有效的减缓了内存要求：

1. 如果一个一级页表的一个PTE是空的，那么相应的二级页表也不会存在。这代表一种巨大的潜在节约（对于一个普通的程序来说，虚拟地址空间的大部分都会是未分配的）。
2. 只有一级页表才总是需要缓存在内存中的，这样虚拟内存系统就可以在需要时创建、页面调入或调出二级页表（只有经常使用的二级页表才会被缓存在内存中），这就减少了内存的压力。

Linux虚拟内存系统

程序运行时的虚拟内存，准确的表达是"虚拟内存技术"。

上述的虚拟内存系统，更多的是从硬件角度解析虚拟内存。一个虚拟内存系统要求硬件和内核之间的紧密协作。下面我们开始介绍 Linux 针对虚拟内存的一些实现（内核函数实现思路）。

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

注：用户只能访问整个地址空间的下半部分，不能访问内核部分。同时用户进程也不能操作另一个进程的地址空间（除非共享内存）。

注2：IA-32 系统上地址范围4GB，内核大概1GB。

内核虚存内包含内核中的代码和数据结构。内核虚拟内存的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全部数据结构。

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

内核虚拟区域

Linux将虚拟内存组织成一些区域（也叫做段）的集合。一个区域就是已经存在着的（已分配的）虚拟内存的连续片，这些页是以某种方式相关联的。

代码段、数据段、堆、共享库段和用户区都是不同是区域。只要是存在的虚拟页就保存在某个区域中。
区域的存在允许虚拟地址空间有间隙。内核不记录不存在的虚拟页，由此节省空间。
内核为系统中的每个进程维护一个单独的任务结构（源代码中的task_struct）。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息（例如，PID、指向用户栈的指针、可执行目标文件的名字以及程序计数器）。
下图强调了记录一个进程中虚拟内存区域的内核数据结构。

task_struct的mm指针指向了mm_struct，该结构描述了虚拟内存的当前状态。mm_struct的pgd指针指向该进程的第一级页表（页全局目录）的基址。mmap指针指向了vm_area_struct（区域结构）链表。每个每个vm_area_struct都描绘了虚拟地址空间的一个区域。当内核运行这个进程时，它就将pgdf存放在CR3控制寄存器中。区域结构包含以下几个部分

1. vm_start：指向这个区域的起始处
2. vm_end：指向这个区域的结束处
3. vm_port：描述这个区域内包含的所有页的读写许可权限
4. vm_flags：描述这个区域内的页面是与其他进程共享的，还是这个进程私有的
5. vm_next：指向链表中下一个区域结构

Linux缺页异常处理

当MMU翻译一个虚拟地址时发生发生缺页异常，该异常使控制转移到内核的缺页处理程序，程序执行如下步骤：

1. 缺页处理程序搜索区域结构的链表，将虚拟地址与每个区域结构的vm_start和vm_end进行比较，由此判断虚拟地址是否合法，即是否在某个区域结构定义的区域内。若不合法，则缺页处理程序触发段错误，终止进程。
2. 判断进程是否有读、写、执行这个区域内页面的权限，即内存访问是否合法。若不合法，则触发一个保护异常，终止进程。
3. 若是通过了上述两步，则说明该缺页是对一个合法地址的合法操作导致的，由此则可以处理缺页。选择一个牺牲页，如果牺牲页被修改过，那么把它交换出去。换入新的页面并更新页表。缺页处理程序返回时，CPU重新启动引起缺页的指令。（同去缺页处理）

交换空间

从硬盘中划分出的所谓的"虚拟内存"，准确来说应该叫做虚拟内存的"后备存储空间"

注意，从硬盘划分出来的虚拟内存和程序运行时的虚拟内存并不是一个概念。

从操作系统角度来看，虚拟内存即交换文件；

Linux系统实现虚拟内存有两种方法：交换分区（swap分区）和交换文件

1. 实际内存
   
   实际内存是指一个系统中实际存在的物理内存，称为RAM。实际内存是存储临时数据最快最有效的方式，因此必须尽可能地分配给应用程序，现在的RAM的形式有多种：SIMM、DIMM、Rambus、DDR等，很多RAM都可以使用纠错机制（ECC）。
2. 交换空间swap
   
   交换空间是专门用于临时存储内存的一块磁盘空间（文件），通常在页面调度和交换进程数据时使用，通常推荐交换空间的大小应该是物理内存的二到四倍。在 Mac OS 系统上，可以查看 /private/var/vm/swapfile*。
3. 交换分区
   
   采用交换分区的办法其实就是新建一个分区，然后将该分区挂载作为交换空间，方法步骤与传统的新建分区一样。只不过格式化分区和挂载分区分别采用mkswap和swapon命令。在创建分区之前，我们常常要用过fdisk -l和df -Th命令来查看硬盘信息和挂载信息，来确定分区的大小。

内存映射

虚拟内存区域是和磁盘中的文件对应。

Linux通过将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射(memory mapping)。

虚拟内存区域可以映射到以下两类对象：

1. Linux系统中的普通文件：文件区被分成页大小的片，每一片包含一个虚拟页面的初始内容。因为按需进行页面调度，因此这些虚拟页没有实际交换进入物理内存，直到CPU第一次引用页面。
2. 匿名文件：由内核创建，内容全是二进制零。CPU第一次引用这样一个区域的虚拟内存时，内核就在物理内存中找一个合适的牺牲页面，被修改过就换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为留在内存中。在磁盘和内存间没有实际的数据传输，因此映射到匿名文件中的页叫做请求二进制零的页(demand-zero page)。

无论上述哪种情况，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件(swap file)之间换来换去。交换文件也叫交换空间、交换区域。注意该空间限制当前运行的进程能够分配的虚拟页面的总数。

开发过程中的内存映射

开发中只有虚拟空间的概念，进程看到的所有地址组成的空间，就是虚拟空间。虚拟空间是某个进程对分配给它的所有物理地址（已经分配的和将会分配的）的重新映射。

mmap的作用，在应用这一层，是让你把文件的某一段，当作内存一样来访问。内核和驱动如何实现的，性能高不高这些问题，这层语义上没有承诺。我们可以基于功能决定怎么用它就好了。

mmap的工作原理，当你发起这个调用的时候，它只是在你的虚拟空间中分配了一段空间，连真实的物理地址都不会分配的，当你访问这段空间，CPU陷入OS内核执行异常处理，然后异常处理会在这个时间分配物理内存，并用文件的内容填充这片内存，然后才返回你进程的上下文，这时你的程序才会感知到这片内存里有数据

驱动每次读入多少页面，页面的分配算法等等，包括swap等等，就是上述的一些实现机制。

页面调度和交换

在简单描述下其他一些概念：

Linux内存管理：Linux系统通过2种方法进行内存管理，“调页算法”，“交换技术”。

调页算法是将内存中最近不常使用的页面换到磁盘上，把常使用的页面（活动页面）保留在内存中供进程使用。

交换技术是系统将整个进程，而不是部分页面，全部换到磁盘上。正常情况下，系统会发生一些交换过程。

当内存严重不足时，系统会频繁使用调页和交换，这增加了磁盘I/O的负载。进一步降低了系统对作业的执行速度，即系统I/O资源问题又会影响到内存资源的分配。

1. 页面调度
   
   页面调度是指从磁盘向内存传输数据，以及相反的过程，这个过程之所以被称为页面调度，是因为Unix内存被平均划分成大小相等的页面；通常页面大小为 4KB和8KB（在Solaris中可以用pagesize命令查看）。当可执行程序开始运行时，它的映象会一页一页地从磁盘中换入，与此类似，当某些内 存在一段时间内空闲，就可以把它们换出到交换空间中，这样就可以把空闲的RAM交给其他需要它的程序使用。
2. 交换
   
   页面调度通常容易和交换的概念混淆，页面调度是指把一个进程所占内存的空闲部分传输到磁盘上，而交换是指当系统中实际的内存已不够满足新的分配需求时，把整个进程传输到磁盘上，交换活动通常意味着内存不足。

共享对象

操作系统为每个进程提供私有的虚拟地址空间，免受其他进程读写的干扰。但对于每个进程都要访问的相同的只读代码区域，如果每个进程在物理内存中保存一份副本，那就是极大的浪费。因此还是希望进程能够共享某些对象。

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。一个映射到共享对象的虚拟内存区域叫做共享区域。类似的，也有私有区域。

若进程将一个共享对象映射到虚拟内存的一个区域，则该进程对这个区域的任何写操作，对那些也把该共享对象映射到虚拟内存的其他进程而言是可见的。同时，对象的变化会反映到磁盘上的原始对象上。

反之，进程对映射到私有对象的区域所做的改变对其他进程不可见，且进程对该区域所做的任何写操作也不会反应在磁盘上的对象上。

私有对象使用写时复制（copy on write）的方式被映射到虚拟内存中。在物理内存中保存私有对象的一个副本。进程共享私有对象的同一个物理副本，只要没有进程试图写私有区域，则进程可继续共享物理内存中对象的一个单独副本。注意私有区域的页表条目都被标记为只读，区域结构被标记为私有写时复制。

如果一个进程试图写私有区域的某个页面，则会触发一个保护故障，故障处理程序会在物理内存中创建这个页面的一共新副本，更新页表条目指向新副本，之后恢复页面的可写权限。故障处理程序返回后CPU重新执行写操作。

总结如下

内存映射：将进程中的一个虚拟内存区域与一个磁盘上的对象关联，使得二者存在映射关系，当然，也可以多个进程映射到一个对象上面。如上图所示，其中私有对象与共享对象的区别在于权限管理。

映射关系可以分为两种：

1. 文件映射
   磁盘文件映射进程的虚拟地址空间，使用文件内容初始化物理内存。
2. 匿名映射
   初始化全为0的内存空间。

而对于映射关系是否共享又分为：

1. 私有映射(MAP_PRIVATE)
   多进程间数据共享，修改不反应到磁盘实际文件，是一个copy-on-write（写时复制）的映射方式。
2. 共享映射(MAP_SHARED)
   多进程间数据共享，修改反应到磁盘实际文件中。

虚拟内存系统通过将虚拟内存分割为称作虚拟页(Virtual Page，VP)大小固定的块，一般情况下，每个虚拟页的大小默认是4096字节。同样的，物理内存也被分割为物理页(Physical Page，PP)，也为4096字节。

内存映射和标准IO对比

而作为对比，当通过 标准IO 读取一个文件时，步骤为：

1. 将 完整 的文件从磁盘拷贝到物理内存（内核空间）。
2. 将完整文件数据从 内核空间 拷贝到 用户空间 以供进程访问。

内存映射的使用

Fork函数

Fork系统调用用于创建一个新进程，称为子进程，它与进程（称为系统调用fork的进程）同时运行，此进程称为父进程。创建新的子进程后，两个进程将执行fork（）系统调用之后的下一条指令。子进程使用相同的pc（程序计数器），相同的CPU寄存器，在父进程中使用的相同打开文件。

1. fork函数会在父进程中创建子进程，子进程的堆，栈，数据段，PC指针都是从父进程中复制过来的，和父进程是独立的，但是内容是一致的。代码段子进程和父进程是共享的。
2. fork（）的返回值可能为-1,0，和一个正数。-1表示fork（）调用失败，0表示返回子进程执行结果，正数表示返回父进程结果（正数即为子进程ID）。
3. 在fork的时候，缓存被复制到了子进程空间。

Linux下可以使用fork函数创建新的进程，显然创建的新进程带有自己独立的虚拟地址空间。在当前进程调用fork函数时，内核为新进程创建各种数据结构，并为其分配唯一的进程ID。为给新进程创建虚拟内存，创建当前进程的mm_struct、区域结构和页表的副本。两个进程中的每个页面都标记为只读，两个进程中每个区域结构都标记为私有写时复制。

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

execve函数

execve（执行文件）在进程中启动新的程序，在子进程中调用exec函数启动新的程序。exec函数一共有六个，其中execve为内核级系统调用，其他（execl，execle，execlp，execv，execvp）都是调用execve的库函数。

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

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

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

1. 删除已存在的用户区域。删除当前进程虚拟地址用户部分中的已存在的区域结构。
2. 映射私有区域。为新程序的文本、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时拷贝的。文本和数据区域被映射为a.out文件中的文本和数据区。bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。栈和堆区域也是请求二进制零的。
3. 映射共享区域。如果a.out程序与共享对象(或目标)链接，比如标准C库libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
4. 设置程序计数器(PC)。execve做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向文本区域的入口点。
   下一次调度这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。

内存映射实现

内存映射的实现过程主要是通过 Linux 系统下的系统调用函数 mmap，取消映射则是通过 munmap 函数。

mmap 函数的作用相当于：创建虚拟内存区域+与共享对象建立映射关系。mmap在用户空间映射调用系统中作用很大。

mmap将一个文件或者其它对象映射进内存。文件被映射到多个页上，如果文件的大小不是所有页的大小之和，最后一个页不被使用的空间将会清零。

该函数主要用途有三个：

1. 将一个普通文件映射到内存中，通常在需要对文件进行频繁读写时使用，这样用内存读写取代I/O读写，以获得较高的性能；
2. 将特殊文件进行匿名内存映射，可以为关联进程提供共享内存空间；
3. 为无关联的进程提供共享内存空间，一般也是将一个普通文件映射到内存中。

mmap 函数声明

头文件

<sys/mman.h>

函数原型

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

在 mmap函数各个参数含义：

1. start: 期望的进程虚拟内存起始位置，填 NULL 时由内核来决定起始位置
2. length: 需要映射的对象字节大小
3. fd: 文件句柄
4. offset: 距离文件开始处的偏移量
5. prot: 映射对象的访问权限，用于可指定是否可读写、执行。
6. flags: 映射对象的类型，例如指定是映射普通文件还是请求二进制零、映射共享对象还是私有的写时复制对象等。

前4项地含义可通过下图更直观地了解：

后面2项的含义为，通过映射关系和是否组合。

总结起来有4种组合:

1. 私有文件映射
   多个进程使用同样的物理内存页进行初始化，但是各个进程对内存文件的修改不会共享，也不会反应到物理文件中
2. 私有匿名映射
   mmap会创建一个新的映射，各个进程不共享，这种使用主要用于分配内存(malloc分配大内存会调用mmap)。
   例如开辟新进程时，会为每个进程分配虚拟的地址空间，这些虚拟地址映射的物理内存空间各个进程间读的时候共享，写的时候会copy-on-write。
3. 共享文件映射
   多个进程通过虚拟内存技术共享同样的物理内存空间，对内存文件 的修改会反应到实际物理文件中，他也是进程间通信(IPC)的一种机制。
4. 共享匿名映射
   这种机制在进行fork的时候不会采用写时复制，父子进程完全共享同样的物理内存页，这也就实现了父子进程通信(IPC).

这里值得注意的是，mmap只是在虚拟内存分配了地址空间，只有在第一次访问虚拟内存的时候才分配物理内存。
在mmap之后，并没有在将文件内容加载到物理页上，只上在虚拟内存中分配了地址空间。当进程在访问这段地址时，通过查找页表，发现虚拟内存对应的页没有在物理内存中缓存，则产生"缺页"，由内核的缺页异常处理程序处理，将文件对应内容，以页为单位(4096)加载到物理内存，注意是只加载缺页，但也会受操作系统一些调度策略影响，加载的比所需的多。

mmap在write和read时会发生什么

write

1. 进程(用户态)将需要写入的数据直接copy到对应的mmap地址(内存copy)
2. 若mmap地址未对应物理内存，则产生缺页异常，由内核处理
3. 若已对应，则直接copy到对应的物理内存
4. 由操作系统调用，将脏页回写到磁盘（通常是异步的）

因为物理内存是有限的，mmap在写入数据超过物理内存时，操作系统会进行页置换，根据淘汰算法，将需要淘汰的页置换成所需的新页，所以mmap对应的内存是可以被淘汰的（若内存页是"脏"的，则操作系统会先将数据回写磁盘再淘汰）。这样，就算mmap的数据远大于物理内存，操作系统也能很好地处理，不会产生功能上的问题。

read

从图中可以看出，mmap要比普通的read系统调用少了一次copy的过程。因为read调用，进程是无法直接访问kernel space的，所以在read系统调用返回前，内核需要将数据从内核复制到进程指定的buffer。但mmap之后，进程可以直接访问mmap的数据(page cache)

而在 iOS 开发中，当我们需要的数据类型是 NSData 时，可以更简便地通过调用以下方法

@interface NSData (NSDataCreation)

+ (nullable instancetype)dataWithContentsOfFile:(NSString *)path options:(NSDataReadingOptions)readOptionsMask error:(NSError **)errorPtr;

系统动态内存分配

动态内存分配器维护一个进程的虚拟内存区域，称为堆。

对于每个进程，内核维护着一个变量brk，指向堆的顶部。

分配器将堆视为一组不同大小的块的集合来维护，每个块是一个连续的虚拟内存片，要么是已分配的，要么是空闲的。

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

1. 显式分配器要求应用显式地释放任何已分配的块，比如C中的malloc和free，C++中的new和delete。
2. 隐式分配器要求分配器检测一个已分配块何时不再被程序所使用，那么就释放这个块，隐式分配器也叫做垃圾收集器。

函数声明

malloc函数

C标准库提供了一个称为malloc程序包的显示分配器，程序通过调用malloc函数来从堆中分配块。

void *malloc(size_t size);

malloc函数返回一个指针，指向大小至少size字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。

如果malloc遇到问题（例如程序要求的内存块比可用的虚拟内存还要大），那么它就返回NULL，并设置errno。malloc不初始化它返回的内存。

动态分配器，例如 malloc，可以通过 使用 mmap 和 munmap函数，显示的分配和释放堆，或者还可以使用 sbrk函数：

sbrk函数

void *sbrk(intptr_t incr);

sbrk函数通过将内核的brk指针增加incr来扩展和收缩堆。

如果成功，它就返回brk的旧值，否则它就返回-1，并将errno设置为ENOMEM

如果incr为零，那么sbrk就返回brk的当前值

free函数

void free(void *ptr);

程序是通过free函数来释放已经分配的堆块。

ptr参数必须指向一个从malloc、calloc或者realloc获得的已分配块的起始位置。如果不是，那么free的行为就是未定义的。更糟糕的是，既然它什么都不返回，free就不会告诉应用出现了错误。

分配器需实现的规则和目标

规则：

• 处理任意请求序列（不能假设所有的分配请求都有相匹配的释放请求，例如请求顺序是 1，2，3，4，5 而释放顺序为 3，2，4，5）
• 立即响应请求（不允许分配器为了提高性能重新排列或者缓冲请求）
• 只使用堆（为了使分配器是可扩展的，任何非标量数据结构都必须保存在堆里）
• 对齐块，分配器必须对齐块，使得他们可以保存任何类型的数据对象
• 不修改已分配的块（分配器只能操作或者改变空闲块，一旦块被分配就不允许修改或者移动了）

目标：

• 最大化吞吐率
• 最大化内存利用率

碎片

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

具体的来讲，碎片就是用来描述一个系统中所有不可用的空闲内存；这些资源之所以仍然未被使用，是因为负责分配内存的分配器使这些内存无法使用。碎片只会在虚拟内存中产生。

碎片有两种形式：

1. 内部碎片：已分配块比有效载荷大的时候发生的。
   
   例如 malloc 一个 char （1 byte）的空间，则必须分配 4KB (Linux 通常页面大小)，或者因为对齐，请求1个字，分配了6个字。
2. 外部碎片：空闲内存合计起来足够满足一个分配请求，但没有一个单独的空闲块足够大可以来处理这个请求。
   
   例如 频繁的申请和释放内存，会导致许多不连续的可用小内存存在在分配页中。但申请一块较大内存（申请内存是连续的），即使小内存总和大于要申请的内存，也不可用。

外部碎片比内部碎片的量化要困难的多，外部碎片还不可能测量。因为它不仅取决于以前请求的模式和分配器的实现方式，还取决于将来请求的模式。

实现中会遇到的问题

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

这个简单的分配器是一种极端情况，因为每个malloc和free只执行很少的指令，吞吐率会极好。然而，因为分配器从不重复使用任何块，内存利用率将极差。一个实际的分配器要在吞吐率和利用率之间把握好平衡要考虑以下问题：

空闲块组织：如何记录空闲块？

• 放置：如何选择一个合适的空闲块来放置一个新分配的块？
• 分割：在将一个新分配的块放置到某个空闲块之后，如何处理这个空闲块中的剩余部分？
• 合并：如何处理一个刚刚被释放的块？

隐式空闲链表

任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身。如下图所示

在这种情况中，一个块是由一个字的头部、有效载荷、以及可能的一些额外的填充组成的。头部编码了这个块的大小以及这个块是分配的还是空闲的。如果有一个双字的对齐约束条件，块大小就总是8的倍数，块大小的最低3位总是0。假设有一个已分配的块（a=1），大小为24（0x18）字节，头部将是

0x00000018|0x1=0x00000019

类似地，一个空闲块（a=0），大小为40（0x28）字节，头部将是

0x00000028|0x=0x00000028

在头部后面就应该是调用 malloc 时请求的有效核载，有效核载后面是一片不使用的填充块，大小是任意的(分配器策略或用于满足对其要求)。
这样我们就可以利用上述的头部来将堆组织为一个连续已分配和空闲块的序列

上述结构被称为隐式空闲链表，因为空闲块是通过头部的大小字段隐含的连接的。分配器可以通过遍历堆中所有的块，从而遍历整个空闲块集合。

隐式空闲链表，是因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

隐式空闲链表的优点是简单。显著的缺点是任何操作的开销，要求空闲链表的搜索与堆中已分配块和空闲块的总数呈线性关系。

系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。没有已分配块或者空闲块可以比这个最小值还小。

放置已分配的块

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

• 首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。
• 下一次适配和首次适配很相似，是从上一次查询结束的地方开始。
• 最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。

首次适配的优点是它往往将大的空闲块保留在链表的后面。

缺点是它往在靠近链表起始处留下小空闲块的"碎片飞这就增加了对较大块的搜索时间。

下一次适配比首次适配运行起来明显要快一些，尤其是当链表的前面布满了许多小的碎片时。

下一次适配的存储器利用率要比首次适配低得多。

最佳适配比首次适配和下一次适配的存储器利用率都要高一些。

然而，在简单空闲链表组织结构中,使用最佳适配的缺点是它要求对堆进行彻底的搜索。

分割空闲块

一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。

一个选择是用整个空闲块。简单而快捷，但是主要的缺点就是它会造成内部碎片。如果放置策略趋向于产生好的匹配，那么额外的内部碎片也是可以接受的。

如果匹配不太好，那么分配器通常会选择将这个空闲块分割为两部分。第一部分变成分配块，而剩下的变成一个新的空闲块。

获取额外的堆存储器

如果分配器不能为请求块找到合适的空闲块，一个选择是通过合并那些在存储器中物理上相邻的空闲块来创建一些更大的空闲块。如果这样还是不能生成一个足够大的块，或者如果空闲块已经最大程度地合并了，那么分配器就会通过调用 sbrk 函数，向内核请求额外的堆存储器。

合并空闲块

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种现象，叫做假碎片(fault fragmentation)，就是有许多可用的空闲块被切割 成小的、无法使用的空闲块。

为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并 ( coalescing)。

分配器可以选择立即合并 (immediate coalescing)，也就是在每次一个块被释放时，就合并所有的相邻块。或者它也可 以选择推迟合并 (deferred coalescing)，也就是等到某个稍晚的时候再合并空闲块。

立即合并很简单明了，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会反复地合并，然后马上分割。

如何合并空闲块

试想如下场景：假设我们要释放的chunk为P，它紧邻的前一个chunk为FD，紧邻的后一个chunk为BK，且BK与FD都为free chunk。将P于BK合并在一起是很容易的，因为可以通过P的size字段轻松定位到BK的开始位置，进而获取BK的size等等，但是将P于FD合并却很难，我们必须从头遍历整个堆，找到FD，然后加以合并，这就意味着每次进行chunk释放操作消耗的时间与堆的大小成线性关系。为了解决这个问题，Knuth提出了一种聪明而通用的技术——边界标记。

Knuth在每个块的最后添加了一个脚部(Footer)，它就是该块头部(header)的一个副本，我们称之为边界标记：

显然每个块的脚部都在其相邻的下一个块的头部的前4个字节处。通过这个脚部，堆内存管理器就可以很容易地得到前一个块的起始位置和分配状态，进而加以合并了。

但是，边界标记同时带来了一个问题：它要求每个块都包含一个头部和脚部，如果应用程序频繁地进行小内存的申请和释放操作的话(比如1，2个字节)，就会造成很大的性能损耗。

同时，考虑到只有在对释放块进行合并的时候才需要脚部，也就是说对于分配块而言它并不需要脚部，因此我们可以对这个脚部加以优化——将前一个块的已分配/空闲标记位存储在当前块的size字段的第1，或2比特位上，这样如果我们通过当前块的size字段知道了前一个块为释放块，那么就可得出结论：当前块地址之前的4个字节为前一个释放块的脚部，我们可以通过该脚部获取前一个块的起始位置；如果当前块的size字段的标记位表明前一个块是于分配块的话，那么就可得出另一个结论：前一个块没有脚部，即当前块地址之前的4个字节为前一个于分配块的payload或padding的最后部分。新的块格式图如下：

边界标记的概念是简单优雅的，它对许多不同类型的分配器和空闲链表组织都是通用的，也存在一个潜在的缺陷。它要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块时，会产生显著的存储器开销。

显式空闲链表

显式空闲链表，是在隐式空闲链表上做的优化

在隐式空闲链表中，由于块的分配与堆块的总数呈线性关系，所以对于通用分配器来说，隐式空闲链表是不合适的。

如果我们将空闲块组织为某种显示的数据结构，由于程序不需要一个空闲块的主题，所以我们将数据结构的指针存放在空闲块的主体里面，我们将堆组织为一个双向空闲链表，在每个空闲块中都包含一个 pred 前驱和 succ 后继指针。

使用双向链表后，使得首次适配的分配时间从块总数的线性时间减少到空闲块数量的线性时间。不过释放一个块的时间可以是线性的，也可以是常数的。

释放时间取决于放置策略

• 后进先出
  用 LIFO 的顺序维护链表，将新释放的块放置在链表的开始处，释放和合并可以在常数时间内完成。如果使用了边界标记，合并也可以在常数时间内。
• 按地址放置
  按照地址顺序来维护链表，其中立案表内每个块的地址都小于它的后继的地址。此时，释放一个块需要线性时间的搜索来定位合适的前驱。

按照地址顺序排序的首次适配比LIFO排序的首次适配具有更高的内存利用率，接近最佳适配的利用率（因为空白地址相近）。

分离的空闲链表

在显示空闲链表中，一个使用单向空闲块链表的分配器需要与空闲块数量呈线性关系的时间来分配块。

为了解决这个问题，一种流行的减少分配时间的方法，通常称为分离存储（segregated storage），就是维护多个空闲链表，其中每个链表有大致相等的大小。

例如，我们可以根据2的幂来划分大小
~
{1}，{2}，{3}，{3，4}，{5 ~ 8}，...，{1024}，{1024 ~ 2048}，{2049 ~ 4096}，{4096 ~ ∞}

分配器维护着一个空闲链表数组 ，每个大小类一个空闲链表，按照大小的升序排列。当分配器需要一个大小为 n 的块时，他就搜索相应的空闲链表，如不能找到则搜索下一个链表，以此类推。

简单的分离存储：

每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。

为了分配给一个给定大小的块，我们检查相应的空闲链表，如果链表为空，我们简单地分配其中第一块的全部。此时空闲块是不会分割以满足分配请求的。如果链表为空，分配器就向操作系统申请一个固定大小的额外存储器片，将这个片分成大小相等的块，并将这些块链接起来形成新的空闲链表。释放时，只需要简单的将这个块插入到相应的空闲链表前部。

这样的话，分配和释放都可以在常数时间内完成。由于我们不进行分割，那么也就没有合并，所以我们就不需要一个已分配/空闲标记，已分配块也就不需要头部，因为没有合并，同样也不需要脚部。

缺点 ：容易造成外部碎片和内部碎片，因为空闲块是不会分割的，所以可能会造成内部碎片。更糟糕的是，因为不会合并块，所以某些引用模式会造成极多的碎片。

分离适配方法：

为了改进上述的缺点，我们可以先找到合适的块，分割（可选的）并使用，同时将剩余的块插入到适当的空闲链表中。如果找不到，则继续搜索下一个更大的类的空闲链表。

分离适配方法是一种常见的选择，C标准库提供的GNU malloc 包就是采用的这种方法。因为这种方法即快速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。

伙伴系统——分离适配的特例

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

这样，给定地址和块的大小，很容易计算出它的伙伴的地址，也就是说：一个块的地址和它的伙伴的地址只有一位不同。

伙伴系统分配器的主要优点是快速搜索和快速合并，主要缺点是要求快为2的幂可能导致显著的内存碎片。因此，伙伴系统分配器不适合通用目的的工作负载（适用某些特定应用）。

垃圾回收

垃圾收集器将内存视为一张可达图(reachability graph)。该图的节点被分成一组根节点(root node)和一组堆节点(heap node)。每个堆节点对应于堆中的一个已分配块。有向边(p->q)表示块p中的某个指针指向块q中的某个位置。根节点对应于这样一种不在堆中的位置，它们包含指向堆中的指针。

垃圾收集器的角色就是维护可达图的某种表示，并通过释放不可达节点且将他们返回给空闲链表，来定期回收它们。

Java这类语言可以维护精确地可达图的表示，因此垃圾回收可以回收所有垃圾；而C++和C这样的语言的收集器通常不能维护精确的可达图表示，叫做保守的垃圾收集器。

Mark & Sweep 垃圾收集器

Mark & Sweep 垃圾收集器由标记(mark)阶段和清除(sweep)阶段组成，标记阶段标记处根节点的所有可达的和已分配的后继。后继是指根节点可达的节点指向的下一个已分配内存块。而后面的清除阶段释放每个未被标记的已分配块。块头部中空闲的低位中的一位通常用来表示这个块是否被标记了。

每次对mark函数的调用都标记某个根节点的所有未标记并且可达的后继节点。在标记阶段的末尾，任何未标记的已分配块都被认定为是不可达的，是垃圾，可以在清除阶段回收。

清除阶段基于sweep函数的调用实现，sweep函数在堆中每个块上反复循环，释放它所遇到的所有未标记的已分配块，也就是垃圾。

void mark(ptr p)
{
    if ((b = isPtr(p)) == NULL)
    {
        return ;
    }
    if (blockMarked(b))
    {
        return ;
    }
    markBlock(b);
    len = length(b);
    for(i = 0; i < len; i++)
        mark(b[i]);          // 标记后继节点
    return ;
}
void sweep(ptr b, ptr end)
{
    while(b < end)
    {
        if (blockMarked(b))
            unmarkBlock(b);
        else if (blockAllocated(b))
            free(b);
        b = nextBlock(b);
    }
    return ;
}

C程序的保守Mark & Sweep

这里主要说明一下为什么C中的mark和sweep是保守的，也就是不能精确的维护一个可达图的表示。

C语言的isPtr函数的实现是一个挑战，原因如下：

C不会用任何类型信息来标记内存位置。因此，对isPtr没有一种明显的方式来判断它的输入p是不是一个指针。
即使我们知道p是一个指针，对isPtr也没有明显的方式来判断ps是否指向一个已分配块的有效载荷中的某个位置。
对最后一个问题的解决办法是，将已分配块集合维护成一颗平衡二叉树，这棵树保持着这样一个属性：左子树都是较小地址的块，右子树都是较大地址的块。isPtr函数用树来执行对已分配块的二分查找。在每一步中，它依赖于块头部中的大小字段来判断p是否落在这个块的范围之内。

C语言中的Mark & sweep收集器必须是保守的，其根本原因是C语言不会用类型信息来标记内存位置。因此，像int或float这样的标量可以伪装成指针。对收集器而言，由于缺少类型信息，因此不能推断出这个数据实际上是int而不是指针。因此，分配器必须保守地将块b标记为可达，尽管事实上它可能是不可达的。

C语言常见内存错误

未初始化的本地指针

int sum(int a[], int n)
{
    int *p;
    int sum = 0;
    for (int i = 0; i < n; i++)
    sum += *p++;
}

假设您声明了一个本地指针但是忘记初始化它。由于变量的内存在堆栈上，并且堆栈可能充满了之前的活动记录所丢弃的数据，所以指针可以有任何值：

未初始化的局部变量

int i;
double d;
scanf("%d %g", i, d); // wrong!!!
// here is the correct call:
scanf("%d %g", &i, &d);
scanf()不指定所有参数的类型，而形参在预编译的时候需要告诉系统要预留出多少的内存空间，所以这里的参数不可以是未初始化的局部变量。

内存溢出问题

#define array_size 100
int *a = (int *) malloc(sizeof(int *) * array_size);
for (int i = 0; i <= array_size; i++)
    a[i] = NULL;

这是一个显然的错误，但却是我们经常会不小心犯，应该把for循环中的小于等于改成小于。

超出所分配的内存

#define array_size 100
int *a = (int *) malloc(array_size);
a[99] = 0; // this overwrites memory beyond the block

分配太少的内存会导致之后的赋值覆盖掉之前的内存。
应该改为int a=(int)malloc(array_size*sizeof(int))

忘记给\0分配空间

有时，程序员忘记字符串是由\0结束的。考虑下面的函数，该函数将字符串传输到堆：

char *heapify_string(char *s){
    int len = strlen(s);

    char *new_s = (char *) malloc(len);
    strcpy(new_s, s);
    return new_s;
}

在这个例子中，程序没有为字符串分配足够的空间。malloc中的参数应该为len+1，为终止的零字节留下空间。如果malloc分配的是8字节的倍数，当len是8字节的倍数的时候heapify_string这个函数将会失败（除非内存大小不是舍入到更大的内存大小）

另外，当两个字符串连接时，结果字符串也有可能占用太多空间：

char q[] = “do not overflow”;
char r[] = ” memory”;
char s[16];
strcpy(s, q);
strcat(s, r);

需要22+1个字符，但只分配了16，所以写操作会超出所分配的内存（要知道strcat函数并不会为结果分配额外的内存）

在运行时堆栈上构建指针并将指针返回给调用方

int *ptr_to_zero(){
    int i = 0;
    return &i;
}

尽管这个函数返回一个指向0值整数的指针，但是这个整数是在一个活动记录中。而这个函数返回时这个活动记录就会被立刻删除，那么指针引用的内存的值可以变成任意值，这还要取决于其他函数的调用情况。

运算顺序和优先级导致的问题

// decrement a if a is greater than zero:
void dec_positive(int *a){
    *a--; // decrement the integer
    if (*a < 0) *a = 0; // make sure a is positive
}

函数里的第一行代码本来想减少a的值，但是事实上减少的是指向a的指针，错误原因是–的优先级虽然和一样高，但是执行顺序是从右向左执行的。当不确定运算优先级时需要使用括号，之前的代码改为(a)–即可。

意外地释放相同的指针两次

void my_write(x){
    ... use x ...
    free(x);
}
int *x = (int *) malloc(sizeof(int*) * N);
...
my_read(x);
...
my_write(x);
free(x); //oops, x is freed in my_write()!

引用已被释放的内存块

一旦一个块被释放，如果块占用的内存被另一个块重用，它的数据随时可能被堆分配程序和应用程序改变。因此，使用一个被释放指针会导致不好的事情发生。您可能在块被修改的地方读取到垃圾，如果写入块，则可能破坏程序已经分配好的堆或数据。下面是一个引用已释放指针的程序的示例：

void my_write(x){
    ... use x ...
    free(x);
}
int *x = (int *) malloc(sizeof(int*) * N);
...
my_read(x);
...
my_write(x);
...
my_read(x); // oops, x was freed by my write!
...
my_write(x);

避免这种错误的一种方法是在释放指针时替换带有null的指针。然而，如果指针有多个副本，这并不能解决问题。事实上这是一个常见的错误发生方式：程序员完成了一个引用并释放了块，忘记了还有其他引用可能被使用。

内存泄漏

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

void my_function(char *msg){
    // allocate space for a string
    char *full_msg = (char *) malloc(strlen(msg) + 100);
    strcpy(full_msg, "The following error was encountered: ");
    strcat(full_msg, msg);
    if (!display(full_msg)) return;
    ...
    free(full_msg);   
}

在这个例子中，被分配的内存在函数最后一行被释放，但如果在display那里发生了错误，这个函数就会提前返回而没有释放内存。异常、错误、各种形式的抛出和捕获通常都会与内存泄漏有关。

忘记释放数据结构的各个部分导致内存泄漏

typedef struct  {
    char *name;
    int age;
    char *address;
    int phone;
} Person;
void my_function(){
    Person *p = (Person *) malloc(sizeof(Person));
    p->name = (char *) malloc(M);
    ...
    p->address = (char *) malloc(N);
    ...
    free(p); // what about name and address?
}

在这个例子中，一个person结构体被分配和释放。但是作为这个结构体的一部分，name和address被分配了却没有被释放。