虚拟内存¶

现代系统提供了一种对主存的抽象 , 称为虚拟内存 (VM).

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

地址空间¶

地址空间 (address space) 是一个非负整数地址的有序集合 . \(\{0,1,2,\ldots\}\)
如果地址空间中的整数是连续的, 我们称为线性地址空间.( 假设我们讨论的都是线性地址空间 )

计算机系统的主存被组织成一个由 M 个字节大小的单元组成的数组，每个字节都有一个唯一的物理地址 (Physical Address), 并且物理地址是连续的。由此就构成了一个物理地址空间 (Physical Address Space), 对应于系统中物理内存的 M 个字节 . CPU 可以通过物理地址来访问内存，这种方式称为物理寻址 (Physical Addressing), 再将获得的数据字保存到寄存器中 .

对于主存存储器资源也可以通过虚拟内存提供另一种不同的视图 . 现代 CPU 从一个有 \(N=2^n\) 个地址的地址空间中生成虚拟地址 (Virtual Address), 该地址空间称为虚拟地址空间 (Virtual Address Space), 虚拟地址空间的大小由表示最大虚拟地址所需的位数 n 来确定 , 现代系统支持 32 位或 64 位的虚拟地址空间 . CPU 会使用虚拟地址来访问主存，称为虚拟寻址 (Virtual Addressing), 需要首先通过地址翻译 (Address Translation) 将虚拟地址转换为对应的物理地址 , 再通过物理地址来访问内存 . 而地址翻译类似于异常处理 ( 软硬结合 )，需要 CPU 上的内存管理单元 (Memory Management Unit, MMU), 以及内存中由操作系统管理的查询表来动态翻译虚拟内存 . 所以通过 MMU 来控制对内存的读写 , 达到对内存进行虚拟化的目的 .

虚拟内存¶

概念上 , 虚拟内存被组织为一个由存放在磁盘上的 N 个连续字节大小的单元组成的数组 , 每个字节有一个唯一的虚拟地址 , 而该数组的内容被缓存到主存中 .

VM 系统将虚拟内存分割为虚拟页 (Virtual Page, VP), 每个虚拟页的大小为 \(P=2^p\) 字节 . 类似地物理内存被分割为物理页 (Physical Page, PP), 大小也为 P 字节 , 物理页也被称为页帧 (page frame).

虚拟页面分为三个不相交的子集 :
(这里的物理内存即主存, 相当于 DRAM 缓存)

• 未分配的: VM 系统还未分配 ( 或者创建 ) 的页 , 不占用任何磁盘空间
• 缓存的: 当前已缓存在物理内存中的已分配页
• 未缓存的: 未缓存在物理内存中的已分配页

DRAM 缓存的不命中代价更昂贵 , 而且从磁盘的一个扇区读第一个字节的时间开销也非常大 , 因此虚拟页往往很大 , 通常是 4KB~2MB. DRAM 缓存是全相联的 , 任何虚拟页可以放在任何物理页中 . 因为对磁盘访问时间长 , DRAM 缓存总是采用写回 , 而不是直写 .

页表¶

为了判断虚拟页是否缓存在 DRAM 中的某个地方 , 软硬件联合 ( 包括操作系统软件 , MMU 中的地址翻译硬件和一个存放在物理内存中的页表) 提供了这个功能 . 页表将虚拟页映射到物理页 , 每次地址翻译硬件将一个虚拟地址转为物理地址时 , 都会读取页表 . 操作系统负责维护页表的内容 , 以及在磁盘和 DRAM 之间来回传送页 .

页表就是一个页表条目 (Page Table Entry, PTE) 的数组 . 虚拟地址空间中每个页在页表中一个固定偏移量处都有一个 PTE. 我们假设 PTE 是一个有效位和一个 n 位地址字段组成 .

• 有效位表明该虚拟页是否被缓存在 DRAM 中 . 如果设置了有效位 , n 位地址字段就表示 DRAM 中相应物理页的起始地址 .
• 没有设置有效位 , 如果未分配则以一个空地址表示 , 如果已经分配 , 地址字段就是虚拟内存 ( 磁盘 ) 中虚拟页的起始地址 .

注: 因为 DRAM 缓存是全相联的 , 所以任意物理页都可以包含任意虚拟页 .

相关操作¶

在磁盘和内存之间传送页的活动叫做交换或者页面调度 (paging). 页从磁盘换入 ( 或者页面调入) DRAM 和从 DRAM 换出 ( 或者页面调出) 磁盘 . 所有现代系统都使用按需页面调度 (demand paging) 的方式 , 即当有不命中发生时猜换入页面 .

页命中¶

当 CPU 想要访问位于虚拟地址 x 中的数据字时，会首先通过地址翻译硬件将虚拟地址作为一个索引来定位 PTE ，然后通过 PTE 来确定对应的虚拟页的状态。如果 PTE 的有效位为 1，说明该虚拟页被缓存在物理内存了，则 CPU 可以通过该 PTE 的地址字段获得物理内存的地址，然后进行访问 , 这就是页命中.

e.g. 上图中假设我们访问 VP2, 即为一个页命中 .

缺页¶

DRAM 缓存不命中称为缺页 (page fault). 如上图中我们访问 VP3, 但从有效位我们可以推断处 VP3 并未被缓存到 DRAM 中 , 因此触发一个缺页异常, 随后异常处理程序选择一个牺牲页进行替换 .

分配页面¶

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

操作系统为每个进程提供了一个独立的页表 , 即一个独立的虚拟地址空间 .
注 : 多个虚拟页面可以映射到同一个共享物理页面 .

• 简化链接: 独立的地址空间允许每个进程的内存映像使用相同的基本格式 .
  如 对于 64 位地址空间, 代码段总是从虚拟地址 0x400000 开始, 数据段跟在代码段之后, 中间一段对其空白. 栈占据用户进程地址空间最高的部分, 并向下生长.

• 简化加载: 要把可执行文件中.text和.data节加载到一个新创建的进程中 , Linux 加载器为其分配虚拟页 , 把它们标记为无效 ( 即未被缓存 ), 将 PTE 指向目标文件中适当的位置 . 访问某一虚拟地址时，发现其对应的 PTE 是无效的，则会发起缺页异常，通过缺页异常处理程序自动地将虚拟页加载到物理页中 .
  加载器从不从磁盘到内存实际复制任何数据 .( 程序运行中可能会 )

• 简化共享: 这里只需要在进程中通过一个 PTE 指向该共享的数据或代码的物理页，就能实现在所有进程中共享的结果 .
• 简化内存分配: 当一个运行在用户进程的程序要求额外的堆空间 ( 如调用malloc时 ), 操作系统要分配一个适当数字个连续的虚拟内存页面 , 并将它们映射到物理内存中任意 k 个物理页面 . 由于页面映射 , 操作系统分配的物理页面可以随机分配在物理内存中 .

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

我们可以在 PTE 上添加一些额外的许可位来限制对一个虚拟页面的访问 .

这里引入了三个字段 :

• SUP: 确定该物理页的访问权限 , 确定是否需要内核模式才能访问
• READ: 确定该物理页的读权限
• WRITE: 确定该物理页的写权限

如果一条指令违反了许可条件 , 那么 CPU 触发一个一般保护保障 , 将控制传递给一个内核中的异常处理程序 . Linux shell 将这种异常报告称为段错误 (segment fault).

地址翻译¶

形式上说 , 地址翻译就是一个 N 元素的虚拟地址空间 (VAS) 中的元素和一个 M 元素的物理地址空间 (PAS) 中元素的一个映射 : \(MAP:VAS\rightarrow PAS \cup\empty\)

• 地址翻译: 虚拟页大小为 P 个字节，所以需要虚拟地址的低 p 位来索引一个虚拟页中的字节 , 得到虚拟页偏移量 Virtual Page Offset，VPO), 然后通过虚拟地址的高 n-p 位来确定虚拟页在页表中的索引 , 得到虚拟页号 (Virtual Page Number，VPN).
  而页表的起始地址保存在一个特殊的 CPU 寄存器 页表基址寄存器 (Page Table Base Register，PTBR) 中，所以可以通过 VPN 和 PTBR 组合得到想要的 PTE 的物理内存地址 .
  并且由于虚拟页和物理页的大小相同, 所以两者编码页中偏移量所需的位数 p 相同, 可以假设数据在虚拟页和在物理页中的偏移量相同, 由此就无需在页表中保存物理页偏移量 (Physical Page Offset，PPO), 只需要保存物理页号 (Physical Page Number，PPN), 可以直接将 VPO 复制给 PPO, 来确定数据在物理页中的偏移量 .
  注 : 从缓存角度看 , VPN 就是标志位 , VPO 就是块偏移 . 页表中只保存 PPN 和标志位.

• 页面命中主要执行以下步骤 :

  • 处理器生成一个虚拟地址 , 并传给 MMU
  • MMU 生成 PTE 地址 ( 因为页表保存在物理内存中 , 这里发送的 PTEA 即PTBR+VPN ), 并从高速缓存 / 主存请求得到它
  • 高速缓存 / 主存向 MMU 返回 PTE( 不包含 PPO)
  • MMU 构造物理地址 , 并把它传送给高速缓存 / 主存
  • 高速缓存 / 主存返回所请求的数据字给处理器

  * 页面不命中主要执行以下步骤:

  • 前三步与页面命中相同
  • PTE 中有效位是 0, 因此 MMU 触发异常 , 控制传递到缺页异常处理程序 .
  • 缺页处理程序确定物理内存 ( 高速缓存 / 内存 ) 中的牺牲页 , 如果如果页面已经被修改了就把它写回到磁盘
  • 缺页处理程序调入新的页面 , 并更新内存中的 PTE
  • 缺页处理程序返回到原来的进程 , 再次执行指令 .

  

结合高速缓存和虚拟内存¶

利用 TLB 加速地址翻译¶

可以发现每次 CPU 将一个虚拟地址发送给 MMU 时 , MMU 都会将需要的 PTE 物理地址发送给高速缓存 / 内存来获得 PTE, 如果高速缓存刚好保存了该 PTE，则 MMU 可以很快获得 , 否则需要等待很多时钟周期从内存中读取 .

在 MMU 中有一个关于 PTE 的小的缓存 , 称为快表 (Translation Lookaside Buffer, TLB). TLB 是一个小的 , 虚拟寻址的缓存 , 其中每一行都保存着一个由单个 PTE 组成块 . TLB 通常有高度的相联度 .

如果 TLB 有 \(T=2^t\) 个组 , 那么TLB 索引 (TLBI) 是由 VPN 的 t 个最低位组成的 , 而TLB 标记 (TLBT) 是由 VPN 中剩余的位组成的 .

• TLB 命中

  • CPU 产生一个虚拟地址
  • MMU 从 TLB 中取出相应的 PTE(PPN 和标记位 )
    • TLB 对 VPN 进行分解，得到 TLBI 和 TLBT，根据 TLBI 确定所在的高速缓存组，然后在高速缓存组中依次比较各个高速缓存行的标记是否和 TLBT 相同，如果相同，则 TLB 命中，将对应的 PPN 发送给 MMU.
  • MMU 将这个虚拟地址翻译为物理地址 , 并将它发送到高速缓存 / 主存
  • 高速缓存 / 主存将所请求的数据字返回给 CPU

• TLB 不命中 MMU 必须从 L1 缓存中取出相应的 PTE, 可能覆盖一个原有的条目.

多级页表¶

假设我们有一个 32 位的地址空间 , 页面大小为 4KB, PTE 大小为 4 字节 , 那么无论被使用的虚拟地址空间多小 , 我们都需要一个 4MB 的页表驻留在内存中 .

我们可以构造多级页表来压缩内容 :

一级页表中每个 PTE 负责映射虚拟地址空间中一个 4MB 的片 (chunk), 这里每一片都是由 1024 个连续页面组成 ( 因此二级页表中每一个片对应 1024 个 PTE). 对于 4GB 的地址空间 , 一级页表中 1024 个 PTE 已经足够覆盖整个内存空间 .
如果片 i 中的每个页面都未被分配, 那么其一级 PTEi 就为空. 如果至少有一个页是分配了的, 那么一级 PTEi 就指向一个二级页表的基址.

二级页表中每个 PTE 负责映射一个 4KB 的虚拟内存界面 . 我们一级和二级页表的 PTE 大小都是 4 字节 , 因此页表都是 4KB 的 , 刚好与页面大小一致 .

这种方法减少了内存要求 :

• 如果一级页表中的一个 PTE 是空的 , 那么二级页表根本不会存在 .
• 只有一级页表才需要总是在内存中 , 虚拟内存系统可以在需要时创建 , 页面调入或调出二级页表 , 这减少了主存的压力 . 只有最经常使用的二级页表才需要缓存在主存 中 .

案例分析 : Intel Core i7/Linux 内存系统¶

Core i7 支持 48 位虚拟地址空间和 52 位物理地址空间 , 还兼容 32 位虚拟和物理地址空间 .

Core i7 地址翻译¶

Core i7 采用四级页表层次结构 . CR3 控制寄存器指向第一级页表 (L1) 的起始位置 . CR3 的值是每个进程上下文的一部分 , 每次上下文切换时 CR3 的值都会被恢复 .
页大小可以在启动时被配置为 4KB 或 4MB. Linux 使用的是 4KB 的页, 因此 \(p=12\).

其中每个 PTE 为 8 字节 , 这里要求物理页 4KB 对齐 . 由于物理地址为 52 位 , PPO 为 12 位 , 则 PPN 为 40 位 , 所以这里的页表物理基地址为 40 位 . 这里增加了 3 个权限位来控制对页的访问 : R/W、U/S和XD , 其中XD是 64 位系统引入的 , 限制了只能在只读代码段执行 , 降低了缓冲区溢出攻击的风险。此外 , 当 MMU 访问一个页时 , 会设置引用位 (Reference Bit) A 位 , 让内核实现页替换算法 , 当 MMU 修改一个页时 , 会设置脏位 (Dirty Bit) D 位 , 使得内核对牺牲页进行写回 .

总体流程图 :

Linux 虚拟内存系统¶

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

其中内核虚拟内存包括内核中的代码和数据结构 . 内核虚拟内存的某些区域被映射到所有进程共享的物理页面 . Linux 还将一组连续的虚拟页面 ( 大小等于系统中 DRAM 总量 ) 映射到相应的一组连续的物理页面 . 这样内核可以在这个虚拟内存上进行读写，实际上就是对物理内存进行读写 , 这为内核提供一种便利的方法来访问物理内存。这部分内容对所有进程都是一样的 .

Linux 虚拟内存区域¶

Linux 将虚拟内存组织成一些区域( 也叫段) 的集合 , 一个区域就是已经存在着的 ( 已分配 ) 虚拟内存的连续片 , 这些页是以某种方式相关联的 , 如代码段、数据段、共享库段以及用户栈 , 这种组织成段的形式 , 允许虚拟地址空间存在间隙 .

内核为系统中每个进程维护一个单独的任务结构 ( 源代码中的task_struct , 存于最上面那块 ) 其中包括运行该进程所需要的所有信息 . 其中有一个条目指向mm_struct , 它描述了虚拟内存的当前状态 . 它包含两个有趣的字段 :

• pgd: 指向第一级页表 ( 页全局目录 ) 的基址 . 当内核运行进程时 , 就把pgd放在 CR3 控制寄存器下 .

• mmap: 指向一个vm_area_struct ( 区域结构 ) 的链表 .

  • vm_start: 指向这个区域的起始处
  • vm_end: 指向这个区域的结束处
  • vm_prot: 描述这个区域内包含的所有页的读写许可权限
  • vm_flags: 描述这个区域内的页面是与其他进程共享的 , 还是这个进程私有的
  • vm_next: 指向链表中下一个结构

Linux 缺页异常处理¶

假设 MMU 在试图翻译某个虚拟地址 A 时触发了一个缺页 , 处理程序随后执行下面的步骤 :

• 虚拟地址 A 是否合法: A 是否是在某个区域结构定义的区域内 ? 处理程序会把 A 与每个区域结构的vm_start和vm_end做比较 . 如果指令不合法 , 程序触发一个段错误 , 终止进程 .
• 对地址 A 的访问是否合法: 进程是否有读写或者执行这个区域内页面的权限 ? 如果访问不合法 , 程序会触发一个保护异常 , 终止进程 .
• 正常的缺页处理 : 选择一个牺牲页 , 如果被修改了就写回 , 随后将虚拟地址 A 对应的虚拟页写入物理页中 , 修改页表 , 从处理程序返回 .

内存映射¶

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

• Linux 文件系统中的普通文件
  一个区域可以映射到一个普通磁盘文件的连续部分, 例如一个可执行目标文件. 文件区 (section) 被分成页大小的片 , 用来初始化对应的虚拟内存段 , 如果段比文件大 , 则用 0 来填充剩下的内容 . 然后按需将虚拟页复制到物理页中 .
• 匿名文件
  一个区域也可以映射到一个匿名文件, 匿名文件是由内核创建的, 包含的全是二进制零. 因此映射到匿名文件的区域中的页面也被称为请求二进制零的页 (demand-zero page).

一旦一个虚拟页面被初始化了 , 它就在一个由内核维护的专门的交换文件之间换来换去 . 交换文件也叫做交换空间或者交换区域. 交换空间限制当前进程能够分配的虚拟页面的总数 .

共享对象¶

一个对象可以被映射到虚拟内存中的一个区域 , 要么作为共享对象, 要么作为私有对象. 映射到共享对象的虚拟内存区域叫共享区域, 类似地有私有区域.

• 如果一个进程将一个共享对象映射到它虚拟地址空间的一个区域内 , 那么这个进程对这个区域的任何写操作 , 对于那些也这样做的进程而言 , 也是可见的 , 而且这些变化会反映到磁盘上的原始对象中 .
• 对于一个映射到私有对象的区域的改变 , 对其他进程是不可见的 , 而且变化不会反映到磁盘上的对象中 .

在进程 1 中，当我们将磁盘上的一个对象通过内存映射与该进程的一个共享段关联起来时，就会使得虚拟页对应的 PTE 指向该对象，当引用该对象时，就会将对应的虚拟页加载到物理页中；而进程 2 也要将该对象与自己的一个共享段关联起来时，当对其引用时，由于每个对象都有一个唯一的文件名，所以内核可以发现进程 1 将该对象加载的物理页，就直接在进程 2 中将对应的 PTE 指向相同的物理页就行了 .
注: 进程 ½ 的虚拟地址空间不同 ; 即使一个对象与多个进程的共享段管理 , 物理内存中只放共享对象的一个副本 .

私有对象使用写时复制 (copy-on-write) 的方法 . 未对私有对象进行修改时 , 物理内存中只会保存同一个对象副本 , 且各个进程中对该对象的 PTE 都是只读的 , 而虚拟内存段标记为私有的写时复制.
只要没有进程试图写它自己的私有区域, 它们就可以继续共享物理内存中对象的一个副本.
但当有进程试图写私有区域的某个局面时, 会触发一个保护故障. 故障处理程序会在物理内存中创建这个页面的一个新副本, 更新 PTE 指向新副本, 然后恢复这个页面的可写权限. 故障处理程序返回后重新执行写操作即可.

通过写时复制这种策略，尽可能延迟物理内存中的拷贝，能最大效率地使用物理内存 .

fork函数¶

当fork函数被当前进程调用时 , 内核为新进程创建各种数据结构 , 并分配给它唯一的 PID. 为了创建一个独立虚拟地址空间 , 我们使用写时复制的技术 :

• 为了具有和父进程相同的虚拟内存状态，内核会复制父进程的mm_struct
• 为了具有和父进程相同的虚拟内存段分配，内核会复制父进程的vm_area_struct ( 区域结构 )
• 为了子进程和父进程具有相同的虚拟内存内容，内核会复制父进程的页表，就能将相同的磁盘内容映射到相同的虚拟页中，并将虚拟页缓存在相同的物理页中 .
• 为了子进程和父进程的虚拟地址空间能相互独立，两个进程的页都设置为只读的，且段都标记为私有的写回复制。当父子进程都没有对页进行修改时，父子进程是共享相同的物理内存的，当其中一个进程对页进行修改时，就会对该页进行写回复制，并为该页赋予写权限，并更新进程对应的页表 .

execve函数¶

当我们运行execve("a.out", NULL, NULL);时 , 加载并允许a.out需要以下步骤 :

• 删除已存在的用户区域: 删除当前进程虚拟地址的用户部分已存在的区域结构 , 即vm_area_struct和页表 .
• 映射私有区域: 为新程序的代码 , 数据 , bss 和栈区域创建新的区域结构 .
• 映射共享区域: 如果与共享对象链接 ( 如共享库 ), 那么在vm_area_struct中创建一个共享段 , 然后将其与共享库的内容关联起来 .
• 设置程序计数器 (PC): 使其指向代码段的入口点 .

mmap函数的用户级内存映射¶

Linux 进程可以使用mmap函数来创建新的虚拟内存区域 .

#include <unistd.h>
#include <sys/mman.h>
void *mmap(void *start, size_t length, int port, int flags, int fd, off_t offset);

其中，prot 对应于段结构中的vm_prot参数，用来确定该虚拟内存段的读写权限：PROT_EXEC表示该段中的页是可执行的；PROT_READ表示该段中的页是可读的；PROT_WRITE表示该段中的页是可写的；PROT_NONE表示该段内的页是不可访问的 .

flags 对应于段结构中的vm_flags : MAP_PRIVATE表示该段是私有的写时复制的；MAP_SHARED表示该段是共享的。也可以设置MAP_ANON，表示是一个匿名对象 .

当函数执行成功时，会返回指向该段的指针，如果失败，则返回MAP_FAILED .

munmap函数删除从虚拟地址 start 开始 , 由接下来 length 字节组成的虚拟内存区域

#include <unistd.h>
#include <sys/mman.h>
int munmap(void *start, size_t length); 

动态内存分配¶

虽然可以使用mmap和munmap来创建和删除虚拟内存的区域 , 但是 C 程序员用动态内存分配器 (dynamic memory allocator) 更方便 , 也有更好的移植性 .

动态内存分配器维护着一个进程的虚拟内存区域 , 称为堆 (heap). 对于每个进程内核都维护一个变量 brk, 它指向堆的顶部 .

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

分配器有两种风格 , 都要求应用显式地分配块 , 不同在于由哪个实体负责释放已分配的块 :

• 显式分配器 (explicit allocator): 要求应用显式地释放任何已分配的块 . 如 C 语言中的malloc``free函数 , C++ 中的new``delete函数 .
• 隐式分配器 (implicit allocator): 要求分配器检测一个已分配块何时不再被程序所使用 , 那么就释放这个块 . 隐式分配器也叫垃圾收集器 (garbage collector)*, 自动释放未使用的已分配的块的过程叫垃圾收集 **.

显式分配器¶

malloc和free函数¶

程序可以通过malloc函数来显示地从堆中分配块

#include <stdlib.h>
void *malloc(size_t size); 

程序可以通过free函数来释放已分配的堆块

#include <stdlib.h>
void free(void *ptr);

动态内存分配器可以使用mmap和munmap函数，也可以使用sbrk函数来向内核申请堆内存空间，只有先申请获得堆内存空间后，才能尝试对块进行分配让应用程序使用 .

#include <unistd.h>
void *sbrk(intptr_t incr); 

分配器的要求和目标¶

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

• 处理任意请求序列
  一个应用可以由任意的分配和释放请求序列, 只要满足先分配后释放. 分配器不可以假设分配和释放的顺序.
• 立即相应请求
  分配器必须立即相应请求, 不允许分配器为了提高性能重新排列或者缓冲请求.
• 只使用堆
  为了使分配器可扩展, 使用的任何非标量数据结构必须保存在堆里.
• 对齐块
  分配器必须对齐块, 使得它们可以保存任何类型的数据对象.
• 不修改已分配的块
  分配器只能操作改变空闲块, 一旦块被分配就不允许修改或者移动.

我们有两个性能目标 :

• 最大化吞吐率
  吞吐率定义为每个单位时间里完成的请求数 . 一般我们可以通过使满足分配和释放请求的平均时间最小化来使吞吐率最大化 . 合理性能的分配器指一个分配请求的最糟运行时间与空闲块数量成线性关系 , 而一个释放请求的运行时间是常数 .
• 最大化内存利用率 假设 n 个分配和释放的某种序列 \(R_0, R_1, \ldots, R_k,\ldots, R_{n-1}\), 用 \(H_k\) 表示当前堆的大小.
  • 有效载荷 (payload): 应用程序请求一个 p 字节的块 , 那么得到的已分配块的有效载荷是 p 字节 .
  • 聚焦有效载荷 (aggregate payload): 用 \(P_k\) 表示 , 为当前已分配的有效载荷之和 .
  • 峰值利用率 (peak utilization): 峰值利用率是最常用来评判内存利用率的标准 .
    假设 \(H_k\) 是单调不递减的, 那么前 k+1 个请求的峰值利用率 \(U_k=\frac{max_{i<=k}P_i}{H_k}\). 分配器的目标就是使得 \(U_{n-1}\) 最大化.
    注 : 我们可以放宽单调性假设 , 让 \(H_k\) 表示前 k+1 个请求的堆的最高峰 .

造成堆利用率低的主要原因之一就是碎片 (fragmentation).

• 内部碎片
  一个已分配块比有效载荷大, 比如分配器为了满足对齐要求, 就会申请额外的内存空间. 我们可以通过已分配块的大小与其有效载荷的差来量化内部碎片，则内部碎片的数量主要取决于之前请求的模式和分配器的实现方法.
• 外部碎片
  当空闲内存合计起来足够满足一个分配请求, 但是没有一个单独的空闲块足够大可以来处理这个请求时发生的. 如图
  外部碎片的量化更加困难, 因为它不仅取决于以前请求的模式和分配器的处理方式, 还取决于将来请求的模式. 所以分配器通常采用启发式策略来试图维持少量的大空闲块, 而不是大量的小空闲块.

为了平衡好吞吐率和利用率之间的平衡 , 我们需要考虑几个问题 :

• 空闲块组织: 如何记录空闲块 ?
• 放置: 如何选择一个合适的空闲块来放置一个新分配的块 ?
• 分割: 在将一个新分配的块放到某个空闲块之后 , 如何处理空闲块中的剩余部分 ?
• 合并: 如何处理一个刚刚释放的块 ?

隐式空闲链表¶

一个块由一个字的头部 , 有效载荷 , 以及可能的一些额外的填充组成的 .

• 头部
  头部大小为一个字. 头部编码了这个块的大小(块大小包括头部和对齐填充), 以及这个块是否分配.
  如果我们要满足双字对齐, 那么块的大小总是 8 的倍数, 因此块大小的第三位(二进制)总是 0, 我们就用其中的最低位来表示这个块的分配情况.
• 有效载荷
  应用malloc请求的有效载荷
• 填充
  可选的, 分配器用来满足对齐要求, 或者处理外部碎片.

我们称这种结构为隐式空闲链表, 因为空闲块通过头部的大小字段隐含地连接 . 分配器可以便利堆中的所有块 , 从而间接地遍历整个空闲块的集合 .
注: 我们需要某种特殊标记的结束块 , 这个例子中就是一个设置了已分配位而大小为 0 的终止头部 (terminating header).

由于地址对齐要求和分配器对块格式的选择，会对最小块的大小有限制，没有已分配的块和空闲块比最小块还小，如果比最小块还小，就会变成外部碎片 ( 所以最小块越大，内部碎片程度越高 ).

放置已分配的块¶

当一个应用请求一个 k 字节的块时 , 分配器搜索空闲链表 , 查找一个足够大可以放置所请求块的空闲块 . 分配器执行这种搜索的方式是由放置策略 (placement policy)确定的 .

• 首次适配 (first fit): 从头开始搜索空闲链表 , 选择第一个合适的空闲块 .

  • 优点: 将大的空闲块保留在后面
  • 缺点: 在靠近链表起始处留下小空闲块的 " 碎片 ", 增加了对较大块的搜索时间 .

  • 下一次适配 (next fit): 从上一次查询结束的地方开始搜索 , 选择第一个合适的空闲块 .

  • 优点: 运行比首次适配块一些 , 可以跳过开头的碎片

  • 缺点: 内存利用率比首次适配低很多

  • 最佳适配 (best fit): 检查每个空闲块 , 选择适合所需请求大小的最小空闲块 .

  • 优点: 内存利用率比前两者都高一些

  • 缺点: 需要遍历完整的空闲链表

分割内存块¶

一旦分配器找到一个匹配的空闲块 , 它必须做另一个策略决定 , 那就是分配空闲块中多少空间 . 一个选择是用整个空闲块 , 虽然简单快捷但会产生内部碎片 . 如果放置策略倾向于产生较好的匹配那么也可以接收额外的内部碎片 .
分配器通常会将这个空闲块分割成两部分, 第一部分变成分配块, 而剩下的变成一个新的空闲块.

获取额外的堆内存¶

如果分配器不能为请求找到合适的空闲块 , 一个选择是通过合并那些在内存中物理相邻的空闲块来创建一些更大的空闲块 . 另一个选择是调用sbrk函数 , 向内核请求额外的堆内存 . 分配器将额外的内存转化为一个大空闲块 , 将这个块插入到空闲链表中 , 然后将被请求的块放到这个新的空闲块中 .

合并空闲块¶

当分配器释放一个已分配块时 , 可能会由其他空闲块与中国新释放的空闲块相邻 . 这些邻接的空闲块引起一种现象 , 即假碎片 (fault fragmentation).

分配器可以选择立即合并或者推迟合并.

• 立即合并 (immediate coalescing): 每次一个块被释放时 , 就合并所有的相邻块 .
• 推迟合并 (deferred coalescing): 找不到合适的空闲块时 , 再扫描整个堆进行合并 .

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

具体实现合并中 : 合并下一个空闲块是简单高效的 , 因为当前块头部指向下一个块的头部 . 只需要检查下一个块的头部 , 看它是否空闲即可 . 如果是 , 将大小相加即可 .
但是合并前一个块, 需要使用边界标记 (boundray tag). 在每个块的结尾处添加一个脚部 (footer), 脚部就是头部的一个副本 . 如果每个块都包括这样一个脚部 , 那么分配器可以通过检查它的脚部判断前一个块的位置和状态 . 这个脚部总是在距当前块开始位置一个字的距离 .

可以将情况分为下面几种 :

• 前一块和后一块都是分配的：此时不会发生合并操作 .
• 前一块是已分配的，后一块是空闲的：当前块会将头部中的块大小设置为当前块的大小和下一块大小之和，并且修改下一块的脚部 .
• 前一块是空闲的，下一块是已分配的：前一块会将头部中的块大小设置为自己的块大小和当前块大小之和，并且修改当前块的脚部 .
• 前一块和当前快都是空闲的：前一块会将头部中的块大小设置为这三个块的大小之和，并修改下一块的脚部 .

该技术的缺点是会显著增加内存开销，由于引入了脚部，使得有效载荷大小变小，而使得内部碎片变多了，并且最小块的大小变大导致外部碎片也变多了 .

我们可以对其进行优化，有些情况是不需要边界标记的，只有在合并时才需要脚部，而我们只会在空闲块上进行合并，所以在已分配的块上可以不需要脚部，那空闲块如何判断前一个块是否为已分配的呢？可以在自己的头部的 3 个位中用一个位来标记前一个块是否为空闲的，如果前一个块为已分配的，则无需关心前一个块的大小，因为不会进行合并；如果前一个块为空闲的，则前一个块自己就有脚部，说明了前一个块的大小，则可以顺利进行合并操作 . 即 , 已分配块可以不用脚部.

实现隐式空闲链表¶

通用分配器设计¶

• mem_init函数将对于堆来说可用的虚拟内存模型化为一个大的 , 双字对齐的字节数组 . 在mem_heap和mem_brk之间的字节表示已分配的虚拟内存 ( 不包括mem_brk ). mem_brk之后的字节表示未分配的虚拟内存 .
• mem_sbrk移动mem_brk指针来调整堆内存 .

• 我们还引用了另一个源文件中的函数 :

  extern int mm_init(void);
  extern void *mm_malloc(size_t size);
  extern void mm_free(void *ptr);
  

  其中mm_malloc和mm_free函数与它们对应的系统函数有相同的接口和语义.
  mm_init初始化分配器, 成功就返回 0 否则 -1. 第一个字是双字边界对齐的不使用的填充字. 然后是一个 8 字节的已分配块(也叫序言块 (prologue block)), 只包括头部和尾部 , 且永不释放 .
  序言块后紧跟的是 0 或者多个调用创建的普通块. 最后是以一个特殊的结尾块 (epilogue block) 结束 , 这个块大小为 0, 只由一个头部组成 . 序言块和结尾块是一种消除合并时边界条件的技巧 .
  一个heap_listp指向序言块. (或者序言块的下一个块)

操作空闲链表的基本常数和宏¶

• PACK将大小和已分配位结合并返回一个值 , 可存放到头部或者尾部 .
• GET和PUT表示在地址 p 处读写一个字 . 注意这里需要强制类型转换 , 否则 void * 无法间接引用 .
• GET_SIZE和GET_ALLOC表示从地址 p 处获得块大小和是否分配 .
• HDRP和FTRP是输入 (bp) 指向第一个有效载荷字节的块指针 (Block Pointer), 用来获得块头部和脚部 .
• NEXT_BLKP和PREV_BLKP用来获得下一个和前一个块的块指针 (bp).

创建初始空闲链表¶

首先，最小的隐式空闲链表需要包含一个字用于对齐，以及两个字的序言块和一个字的结尾块，所以首先使用mem_sbrk申请 4 个字的堆内存 . 然后根据要求填充对应的内容，然后让heap_listp指向序言块脚部的起始地址。初始完后，由于是空的堆内存，所以需要调用extend_heap函数来申请CHUNKSIZE字节 .

extend_heap函数会在两种情况下被调用 : 堆被初始化时 ; mm_malloc不能找到一个合适的匹配块时 . 为了保持对齐将 size 大小向上舍入为最接近 2 字的倍数 .
注意：在第 8 行申请 size 个字节后，bp 指向的是结尾块的下一个字(因为mem_brk不放元素)，所以在第 12 行设置空闲块头部时，根据PUT定义，可知这里新申请的空闲块覆盖了之前的结尾块，将其作为了自己的头部字，然后在设置脚部时，留下了一个字用来作为新的结尾块.

最后尝试合并前面的空闲块 .

释放和合并块¶

我们这里可以发现 : 我们将序言块和结尾块都标记为已分配 , 可以帮助我们处理边界情况 .

分配块¶

首先字节数 size 传进来后，会现在第 12 行到 14 行判断是否满足对齐要求，然后得到满足对齐要求的字节数 asize。然后尝试寻找合适的空闲块进行分配，如果没有找到合适的空闲块，就需要向内核再申请堆内存空间，再尝试分配 .

显式空闲链表¶

堆可以组织成一个双向空闲链表 , 每个空闲块里都包含一个 pred( 前驱 ) 和 succ( 后继 ) 指针 .

这样可以使得首次适配的分配时间从块总数的线性时间减少到空闲块数量的线性时间 , 不过释放一个块的时间是取决于排序策略 :

• 后进先出 (LIFO): 将新释放的块放在链表开始处 . 这样释放一个块可以在常数时间完成 , 如果使用边界标记那么合并也是常数时间 . 当我们使用首次适配的放置策略时 , 分配器会最先检查使用过的块 .
• 地址顺序: 链表每个块的地址都小于后继的地址 . 这种情况下释放一个块需要线性时间来搜索定位合适的前驱 , 但可以有更高的内存利用率 .

分离的空闲链表¶

分离存储 (segregated storage) 维护多个空闲链表 , 其中每个链表中的块有大致相等的大小 . 一般思路是将所有可能的块大小划分为等价类 , 也叫大小类 (size class), 比如可以根据 2 的幂次来划分块大小 . \(\{1\}, \{2\}, \{3,4\}, \ldots, \{5,6,7, 8\}\)
分配器维护一个空闲链表数组, 每个大小类一个空闲链表, 按照大小升序排列. 当分配器需要一个大小为 n 的块时, 就搜索相应的空闲链表. 如果不能找到合适的块对应就搜索下一个链表.

简单分离存储¶

每个大小类的空闲链表包含大小相等的块 , 每个块的大小就是这个大小类中最大元素的大小 .
为了分配一个给定大小的块, 我们会检查相应的空闲链表. 如果链表非空, 我们简单地分配其中第一块的全部. 空闲块是不会分割以满足分配请求的. 如果链表为空, 分配器就向操作系统请求一个固定大小的额外内存片(通常是页大小的整数倍), 将这个片分成大小相等的块, 并将这些块连接起来形成新的空闲链表. 要释放一个块, 分配器只要简单地将这个块插入到相应的空闲链表的前部.

• 优点: 分配和释放块都是常数时间，不分割，不合并，已分配块不需要头部和脚部，空闲链表只需是单向的，因此最小块为单字大小 .
• 缺点: 由于使用分割和合并，所以会有大量的内部和外部碎片 .

分离适配¶

分配器维护一个空闲链表的数组 , 每个空闲链表是和一个大小类相关联的 , 并被组织成某种类型的显式或隐式链表 .
分配块时，确定请求的大小类，对适当的空闲链表做首次适配，如果找到合适的块，可以分割它，将剩余的部分插入适当的空闲链表中；如果没找到合适的块，查找更大的大小类的空闲链表。如果没有合适的块，就向内核请求额外的堆内存，从这堆内存中分割出合适的块，然后将剩余部分放到合适的大小类中。每释放一个块时，就进行合并，并将其放到合适的大小类中.

如 GNU malloc 包就是采用这种方法 . 这种方法既快、利用率也高 .

伙伴系统¶

伙伴系统 (buddy system) 是分离适配的一种特例 , 其中每个大小类都是 2 的幂 . 基本思想是假设堆的大小是 \(2^m\) 个字 , 我们为每个块大小 \(2^k\) 维护一个分离空闲链表 . 请求块大小向上舍入到最接近 2 的幂 .
为了分配一个大小为 \(2^k\) 的块, 我们找到第一个可用的 \(2^j, k<=j<=m\) 的块. 如果 \(j=k\) 那么分配完成, 否则我们递归地二分这个块直到 \(j=k\). 当我们进行这样的分割时, 每个剩下的半块(也叫伙伴) 被放置在相应的空闲链表中 .

一个关键事实是 , 给定地址和块的大小 , 很容易计算出他伙伴的地址 . 如 \(xxx\ldots x00000\) 和 \(xxx\ldots x10000\) 互为伙伴 . 一个块的地址和它的伙伴的地址只有一位不相同.

垃圾收集¶

垃圾收集器 (garbage collector) 是一种动态内存分配器 , 自动释放程序不再需要的已分配块 , 这些块称为垃圾.

垃圾处理器将内存看作一张有向可达图 (reachability graph).

• 每个堆节点对应堆中的一个已分配块 .
• 有向边 \(p\rightarrow q\) 意味着块 p 中某个位置指向块 q 中某个位置 .
• 根节点对应一种不在堆中的位置 , 包含指向堆中的指针 . 如寄存器的变量 , 虚拟内存中读写区域的全局变量等 .

当存在一条从任意根节点出发到达 p 的有向路径时 , 我们说 p 是可达的. 不可达节点对应于垃圾 , 不能被再次应用和使用 . 垃圾处理器就是维护可达图的某种表示 , 并通过释放不可达节点并把它们返回给空闲链表来定期回收它们 .

对于像 ML 和 Java 语言，其对指针创建和使用有严格的要求，由此来构建十分精确的可达图，所以能回收所有垃圾 . 而对于像 C 和 C++ 这样的语言，垃圾收集器无法维护十分精确的可达图，只能正确地标记所有可达节点，而有一些不可达节点会被错误地标记为可达的，所以会遗留部分垃圾，这种垃圾收集器称为保守的垃圾收集器 (Conservative Garbage Collector).

Mark & Sweep 垃圾收集器¶

Mark&Sweep 垃圾收集器由两个阶段组成 :

• 标记阶段: 标记出根节点的所有已达和已分配的后继
• 清理阶段: 释放每个未被标记的已分配块 . 块头部中空闲的低位中的一位表示这个块是否被标记了 .

我们将使用下面函数 :

• ptr isPtr(ptr p): 如果 p 指向一个已分配块中的某个字 , 那么就返回一个指向这个块的起始位置的指针 p, 否则返回 NULL.
• int blockMarked(ptr b): 如果块 b 已标记 , 返回 true.
• blockAllocated(ptr b): 如果块 b 已分配 , 返回 true.
• void markBlock(ptr b): 标记块 b
• int length(ptr b): 返回块 b 以字为单位的长度 ( 不含头部 )
• void unmarkBlock(ptr b): 将块 b 的状态由已标记改为未标记
• ptr nextBlock(ptr b): 返回堆中块 b 的后继

C 程序保守的 Mark & Sweep¶

C 程序想要使用 Mark&Sweep 垃圾收集器，在实现isPtr函数时具有两个困难：

• 进入isPtr函数时，首先需要判断输入的 p 是否为指针，只有 p 为指针，才判断 p 是否指向某个已分配块的有效载荷 . 但是在 C 语言不会用类型信息来标记内存位置，比如 int 或 float 这些标量就可能被伪装成指针，比如 p 对应的是一个 int 类型数据，但是 C 误以为是指针，而将该数据作为指针又正好指向某个不可达的已分配块中，则分配器会误以为该分配块时可达的，造成无法对该垃圾进行回收 . 这也是 C 程序的 Mark&Sweep 垃圾收集器必须是保守的原因 .
• 当判断 p 为指针时，如何确定它所在块的头部 . 这里可以将已分配的块组织成平衡二叉树的形式，如下所示，保证左子树所有的块都在较小的地址处，右子树所有的块都在较大的地址处 . 此时输入一个指针 p，从该树的根节点开始，根据块头部的块大小字段来判断指针是否指向该块，如果不是，根据地址大小可跳转到左子树或右子树进行查找 .

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

间接引用坏指针¶

对于每个进程内核都维护了一个vm_area_struct数据结构，来将虚拟内存划分成不同的段，这也造成虚拟内存可能是不连续的，如果我们尝试对不处于任何段的虚拟内存进行引用时，内核就会发出段异常终止程序 . 其次，不同段限制了不同页的读写权限，如果我们尝试对只读虚拟页进行写操作时，内核就会发出保护异常终止程序 .
如
scanf("%d, val"); 如果 val 对应虚拟内存某个合法的读写区域, 我们就覆盖了这块内存.

读未初始化的内存¶

我们定义的未初始化的全局变量处于.bss段中，该段会与匿名文件进行关联，使得未初始化的全局变量都为 0。但是使用malloc分配堆内存时，只是简单的修改了 brk 指针，并不会对已分配的块进行任何初始化，所以要对动态内存分配得到的堆内存进行初始化 .( calloc函数会进行初始化 )

允许栈缓冲区溢出¶

不检查输入串的大小就写入栈中的目标缓冲区 , 就会由缓冲区溢出错误 (buffer overflow bug).
如

void bufferoverflow()
{
    char buf[64];

    gets(buf);
    return;
}

假设指针和他们指向的对象是相同大小¶

int **makeArray1(int n, int m)
{
    int i;
    int **A = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
        A[i] = (int *)malloc(m * sizeof(int));
    return A;
}

错位错误¶

int **makeArray1(int n, int m)
{
    int i;
    int **A = (int *)malloc(n * sizeof(int *));
    for (i = 0; i <= n; i++)
        A[i] = (int *)malloc(m * sizeof(int));
    return A;
}

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

int *binheapDelete(int **binheap, int *size)
{
    int *packet = binheap[0];

    binheap[0] = binheap[*size - 1];
    *size--;
    heapify(binheap, *size, 0);
    return(packet);
}

误解指针运算¶

int *search(int *p, int val)
{
    while (*p && *p != val)
        p += sizeof(int);
    return p;
}

引用不存在的变量¶

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

引用空闲堆块中的数据¶

int *heapref(int n, int m)
{
    int i;
    int *x, *y;
    x = (int *)malloc(n * sizeof(int));
    ...
    free(x);

    y = (int *)malloc(n * sizeof(int));
    for (i = 0; i < m; i++)
        y[i] = x[i]++;
    return y;
}

引起内存泄漏¶

程序员忘记释放已分配块 , 而在堆里创建了垃圾 , 会逐渐占用虚拟地址空间的内存 .

void leak(n)
{
    int *x = (int *)malloc(n * sizeof(int));
    return;
}

评论