第九章 虚拟内存

物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每字节都有一个唯一的 物理地址(PA) 。

• 物理寻址：使用物理地址进行寻址。
• 虚拟寻址：使用虚拟地址进行寻址，现代处理器的CPU通过生成一个 虚拟地址(VA) 访问主存，虚拟地址在被送到内存之前先转换成适当的物理地址，CPU芯片上的内存管理单元(MMU)利用存放在主存中的查询表动态翻译虚拟地址，该表由操作系统管理。

物理地址空间对应于系统中物理内存的M个字节。
一个包含N=2 ⁿ 个地址的虚拟地址空间叫做一个N位地址空间，现代系统通常支持32或64位虚拟地址空间。

允许每个数据对象有多个独立的地址，每个地址选自一个不同的地址空间。
主存中的每字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

虚拟内存

一个系统中的进程与其他进程共享CPU和主存，为了更加有效的管理内存并减少出错，现代系统提出了一种对主存的抽象概念，叫做 虚拟内存(VM) 。它为每个进程提供了一个大的、一致的和私有的地址空间。虚拟内存提供三个重要功能：

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

虚拟内存系统通过把虚拟内存分割为虚拟页大小的块，每个虚拟页大小为P=2 ^p 字节。
物理内存也被分割为物理页，大小也为P字节，物理页也称为页帧。
任意时刻，虚拟页面的集合分为三个相交的子集：

1. 未分配的：虚拟内存系统还未创建的页，没有任何数据和它们关联，不占用任何磁盘空间
2. 缓存的：已缓存在物理内存中的已分配页
3. 未缓存的：未缓存在物理内存中的已分配页

SRAM缓存表示位于主存和CPU之间的L1、L2、L3高速缓存。
DRAM缓存表示虚拟内存系统的缓存，它在主存中缓存虚拟页，利用DRAM可以缓存来自通常更大的虚拟地址空间的页面。
虚拟页往往很大，DRAM缓存是全相联的，即任何虚拟页可以放在任何的物理页中。DRAM缓存总是使用写回，而不是直写。操作系统对DRAM缓存使用了复杂精密的替换算法。

页表(page table) 将虚拟页映射到物理页，是页表条目(Page Table Entry)的数组。
虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。
PTE通常有一个有效位和n位地址字段，如果设置了有效位那么地址字段表示DRAM中相应物理页的起始地址；如果没有设置有效位，空地址则表示该虚拟页还没被分配，否则这个地址字段表示该虚拟页在磁盘上的起始位置。

DRAM缓存不命中称为 缺页 ，缺页异常调用内核中的缺页异常处理程序。
该程序选择一个牺牲页，如果牺牲页被修改了就会被复制回磁盘，然后修改页表条目并把缺的页从磁盘复制到内存中。
异常处理程序返回时，会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发给地址翻译硬件，此时页命中。

操作系统分配一个虚拟页面时，在磁盘上创建空间并更新相应的页表条目，使它指向磁盘上这个新创建的空间。

虚拟内存工作良好主要归功于 局部性 ：局部性原则保证了在任意时刻，程序趋向于在一个较小的活动页面集合上工作，这个集合叫做工作集。初始开销将工作集页面调度到内存中，接下来对工作集的引用将导致页命中。
工作集大小超过物理内存大小时，程序可能会发生抖动，这时页面不断换进换出。

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

操作系统为每个进程提供了一个独立的页表 ，因而也就是一个独立的虚拟地址空间。

多个虚拟页面可以映射到同一个共享物理页面上

• 简化链接：独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。这样的一致性大大简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
• 简化加载：虚拟内存还使得容易向内存中加载可执行文件和共享对象文件，加载器从不从磁盘到内存实际复制任何数据，在每个页初次被引用时，要么是CPU取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射。
• 简化共享：操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的副本。
• 简化内存分配：用户进程要求额外的堆空间时，操作系统分配连续的虚拟内存页面，并将它们映射到物理内存中的任意位置，页面可以随机地分散在物理内存中。

提供独立的地址空间使得区分不同进程的私有内存变得容易。
通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问，如果一条指令违反了许可条件，CPU会触发一个一般保护故障，将控制传递给内核中的一个异常处理程序：

• SUP位：进程是否必须运行在内核模式下才能访问该页
• READ位和WRITE位：控制对页面的读和写访问

地址翻译

注：地址翻译部分省略了大量的细节，尤其是时序相关的细节

地址翻译是一个N元素的虚拟地址空间中的元素和一个M元素的物理地址空间中元素之间的映射。
CPU中有一个页表基址寄存器(Page Table Base Register,PTBR)指向当前进程的页表。
n位的虚拟地址包括一个p位的虚拟页面偏移量和一个(n-p)位的虚拟页号，物理页号由虚拟页号得到，物理页偏移等于虚拟页偏移。

页面命中时CPU步骤

1. 处理器生成虚拟地址，把它传送给内存处理单元MMU
2. 内存处理单元生成页表条目(PTE)地址，并从高速缓存/主存请求得到它
3. 高速缓存/主存向内存处理单元返回页表条目
4. 内存处理单元构造物理地址(串联物理页号和物理页偏移)，并把它传送给高速缓存/主存
5. 高速缓存/主存返回所请求的数据字给处理器

页面命中完全由硬件处理，处理缺页请求要求硬件和操作系统内核协作完成。

缺页时CPU步骤

1. 处理器生成虚拟地址，把它传送给内存处理单元MMU
2. 内存处理单元生成页表条目(PTE)地址，并从高速缓存/主存请求得到它
3. 高速缓存/主存向内存处理单元返回页表条目
4. 页表条目中的有效位是0，内存处理单元触发一次异常，传递CPU中的控制到操作系统内核中的缺页处理异常处理程序
5. 缺页处理程序确定出物理内存中的牺牲页，如果这个页面被修改了，则把它换出到磁盘
6. 缺页处理程序调入新的页面，并更新内存中的页表条目
7. 缺页处理程序返回原来的进程，再次执行导致缺页的指令，此时页面请求将会命中

大多数系统是 使用物理地址访问SRAM高速缓存 的，地址翻译是发生在高速缓存查找之前的。

为了减少从内存读取页表的开销，内存处理单元包括了一个关于页表条目的小缓存，称为 翻译后备缓冲器(TLB) 。
TLB是一个小的、虚拟寻址的缓存，其中每一行保存着一个由单个页表条目组成的块，TLB常有高度的相联度。
那么内存管理单元只有在TLB不命中时，才会从L1缓存中取出相应的页表条目。

64位系统中页表往往很大，用来压缩页表的常用方法是使用 层次结构的页表 。
比如，一级页表中的每个PTE映射虚拟地址空间中的一个4MB的片，二级页表中的每个PTE映射一个4KB的页。
Core i7处理器中的CR3控制寄存器指向第一级页表的起始位置，CR3的值是每个进程上下文的一部分。
如果片i中的每个页面都未分配，那么一级PTE i就为空。如果片i中至少有一个片是分配的，那么一级PTE i指向一个二级页表的基址。

• 如果一级页表中的一个页表条目是空的，相应的二级页表不会存在，这是巨大的节约
• 只有一级页表总是在主存中，需要时再创建、调入或调出二级页表，只有经常使用的二级页表缓存在主存中，减小了主存的压力
• TLB将不同层次上页表的PTE缓存起来，使得多级页表的地址翻译并不比单级页表慢很多

Linux虚拟内存

Linux将虚拟内存组织成一些区域的集合，一个区域就是已经存在的已分配虚拟内存的连续片。代码段、数据段、堆、共享库段以及用户栈都是不同的区域。允许虚拟地址空间有间隙。
内核为系统中的每个进程维护一个单独的任务结构task_struct，任务结构中的元素包含或指向内核运行该进程所需要的所有信息(如PID、指向用户栈的指针，可执行目标文件的名字以及程序计数器)。
任务结构中的一个条目指向mm_struct，它描述了虚拟内存的当前状态。
mm_struct中的pgd字段指向第一级页表的基址，mmap指向一个vm_area_struct(区域结构)的链表。
每个vm_area_struct描述了当前虚拟地址空间的一个区域，一个具体区域的结构包含以下字段:

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

内存映射

内存映射 ：将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容。
虚拟内存区域可以映射到两种类型的对象中的一种：

1. Linux文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件，文件区被分成页大小的片，每一片包含一个虚拟页面的初始内容，因为按需调度页面，这些虚拟页面直到CPU第一次引用到页面才会交换进入物理内存。
2. 匿名文件：匿名文件由内核创建，包含的全是二进制零，映射到匿名文件的区域中的页面叫做请求二进制零的页。

一个虚拟页面被初始化后，在由内核维护的交换文件之间换来换去，交换文件也叫交换空间。任何时刻，交换空间都限制着当前运行进程能够分配的虚拟页面的总数。

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

• 如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的，而且这些变化会反映在磁盘上的原始对象上。物理内存只存放共享对象的一个副本。
• 一个映射到私有对象的区域做的改变，对于其他进程而言不可见，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。私有对象使用写时复制的技术被映射到虚拟内存中，私有对象开始生命周期时在物理内存中也只保存一份副本。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，且区域结构被标记为私有的写时复制，只要有一个进程试图写私有区域内的某个页面，那么才会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的的副本，然后恢复这个页面的可写权限。 写时复制 充分使用了物理内存。

fork函数

被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID，新进程创建的虚拟内存是当前进程的原样副本，并将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构标记为私有的写时复制。当两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，为每个进程保持了私有地址空间。

execve函数

1. 调用execve("a.out", NULL, NULL)
2. 删除已存在的用户区域
3. 映射私有区域，为新程序的代码、数据、bss和栈区域创建新的区域结构，并标记这些区域为私有的写时复制的
4. 映射共享区域，目标程序如果与共享对象链接，那么将它们映射到用户虚拟地址空间中的共享区域内
5. 设置程序计数器(PC)，使之指向代码区域的入口点

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

#include <unistd.h>  
#include <sys/mman.h>  
// start:开始地址，通常定义为NULL  
// fd:文件描述符  
// length：文件描述符指定对象的连续对象片大小，单位字节  
// offset：文件描述符指定对象的开始处偏移量，单位字节  
// prot：描述新映射的虚拟内存区域的访问权限位  
// flags：描述被映射对象类型的位组成，表示私有写时复制对象/匿名对象/共享对象  
// 成功时返回指向映射区域的指针，出错返回MAP_FAILED(-1)  
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);  
// 创建一个新的包含size字节的只读、私有、请求二进制零的虚拟内存区域，调用成功时bufp包含新区域的地址  
bufp = Mmap(NULL, size, PROT_READ, MAP_PRIVATE|MAP_ANON, 0, 0);  

// 删除从虚拟地址start开始的length字节组成的区域，引用已删除区域会导致段错误  
// 成功返回0，出错返回-1  
int munmap(void *start, size_t length);  

动态内存分配

mmap和munmap可以创建和删除虚拟内存区域，但是C程序员使用 动态内存分配器 更方便且可移植。
动态内存分配器维护着一个进程的虚拟内存区域，称为 堆(heap) 。对于每个进程，内核维护着一个变量brk，指向堆的顶部。分配器将堆视为一组大小不同的块的集合，每个块是一个连续的虚拟内存片(chunk)，要么是已分配的，要么是空闲的。空闲块保持空闲，直到显式地被应用所分配。已分配块保持已分配状态，直到它被释放。

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

C程序通过调用malloc函数从堆中分配块。
malloc函数返回一个指针，指向大小至少size字节的内存块，这个块为可能包含在块内的任何数据对象类型做对齐。
32位模式中，malloc返回的块地址总是8的倍数；64位模式中，malloc返回的地址总是16的倍数。
malloc 不初始化 它返回的内存，calloc函数基于malloc，它将分配的内存初始化为0。
想要改变一个以前分配块的大小，可以使用realloc函数。

#include <stdlib.h>  
// 成功时返回已分配块的指针，出错返回NULL  
void *malloc(size_t size);  

sbrk函数将内核的brk指针增加incr来扩展和收缩堆。成功时返回brk的旧值，否则返回-1并将errno设为ENOMEM。
incr为0时返回brk的当前值，incr的值也可以是负的。

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

C程序通过free函数释放已分配的块。

#include <stdlib.h>  
// ptr参数必须指向一个从malloc、calloc或realloc获得的已分配块起始位置  
// 如果ptr参数不满足上述条件，行为就是未定义的，而且不会告诉应用出现错误  
void free(void *ptr);  

虚拟内存是一个有限的空间 ，系统中所有进程分配的虚拟内存的全部数量受磁盘上交换空间的数量限制。
显式分配器的编写者试图实现吞吐率(每个单位时间完成的请求数)最大化和内存利用率最大化。

显式分配器的约束条件

• 处理任意请求序列：一个应用可以有任意的分配请求和释放请求序列，只要每个释放请求对应于一个当前已分配块且这个块是由一个以前的分配请求获得的，分配器不可以假设分配和释放请求的顺序
• 立即响应请求：不允许分配器为了提高性能重新排列或者缓冲请求
• 只使用堆
• 对齐块：分配器必须对齐块，使得它们可以保存任何类型的数据对象
• 不修改已分配的块：分配器只能操作或者改变空闲块，一旦块被分配了就不允许修改或者移动

造成堆利用率低的主要原因是 碎片现象 ，产生碎片时系统有未使用的内存但不能满足分配请求，分配器通常试图维持少量的大空闲块，而不是维持大量的小空闲块：

• 内部碎片：已分配块的大小大于有效载荷(实际请求大小)，产生内部碎片原因有增加块大小满足对齐约束和分配器对块大小有最小值约束。内部碎片取决于以前的请求模式和分配器的实现方式。
• 外部碎片：当空闲内存合起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以处理分配请求。外部碎片不仅取决于以前的请求模式和分配器的实现方式，还取决于将来请求的模式。

空闲块组织

• 隐式空闲链表：一个块由一个的头部、有效载荷以及可能的一些额外填充组成，头部编码了块的大小以及标记这个块是已分配的还是空闲的，空闲块通过头部中的大小字段隐含地连接着。分配器可以通过遍历堆中所有的块，从而间接遍历整个空闲块的集合。
• 显式空闲链表：堆组织为一个双向空闲链表，空闲块头部和脚部相同，各占一个字，保存块大小和空闲标记，同时还包含pred(前驱)和succ(后继)指针，使用这种双向链表的结构使得首次适配分配时间减少为空闲块数量的线性时间。
• 分离的空闲链表：维护多个空闲链表，其中每个空闲链表中的块有大致相等的大小。将所有可能的块大小分为一些等价类/大小类，分配器维护一个空闲链表数组，每个大小类一个空闲链表，这种方法又叫做分离存储，不同的分离存储方法区别于如何定义大小类、何时合并、何时向操作系统请求额外的堆内存、是否允许分割等。

GNU malloc包采用的是 分离适配 ：
每个空闲链表和一个大小类相关联，并被组织成某种类型的显式或隐式链表。
每个链表包含潜在大小不同的块，这些块的大小是大小类的成员。
分配一个块时，对适当的空闲链表做首次适配，如果找到则分割它并将剩余部分插入到适当的空闲链表中。
如果找不到合适的块，就搜索下一个更大的大小类的空闲链表。
释放块时，执行合并操作，并将结果放置到相应的空闲链表中。

放置已分配的块

• 首次适配(first fit)：从头开始搜索空闲链表，选择第一个合适的空闲块
• 下一次适配(next fit)：从上一次查询结束的地方开始，选择第一个合适的空闲块
• 最佳适配(best fit)：检查每个空闲块，选择适合所需请求大小的最小空闲块

分配器找到匹配空闲块后，可以选择使用整个空闲块，也可能将这个块分割为分配块和空闲块两部分。
如果分配器找不到合适的空闲块，可以选择合并相邻空闲块来创建更大的空闲块，如果仍然不能满足请求，分配器会调用sbrk函数向内核请求额外的堆内存。

合并空闲块

• 立即合并：每次一个块被释放时，合并所有的相邻块
• 推迟合并：等到某个稍晚时候再合并空闲块，比如直到某个分配请求失败再合并空闲块
• 带边界标记的合并：在每个块的结尾添加脚部，脚部是头部的一个副本，脚部总是距当前块开始位置一个字的距离

快速的分配器通常使用某种形式的推迟合并

垃圾收集

垃圾收集器是一种动态内存分配器，它自动释放程序不再需要的已分配块。支持垃圾收集的系统中，应用显式分配堆，但从不显式地释放它们。

垃圾收集器将内存视为一张有向可达图，该图地节点被分成一组根节点和一组堆节点，每个堆节点对应于堆中的一个已分配块。有向边p → q意味块p中的某个位置指向块q中的某个位置。根节点不在堆中，它们包含指向堆中的指针，根结点可以是寄存器、栈里的变量或是虚拟内存中读写数据区域内的全局变量。当存在一条从任意根结点出发并到达p的有向路径时，则p是可达的。任何时刻， 不可达节点对应于垃圾 ，通过释放不可达节点且将它们返回给空闲链表来定期回收它们。

Java的垃圾收集器能够维护可达图的一种精确表示，因此可以回收所有垃圾；
C/C++的收集器通常不能维持可达图的精确表示，每个可达块可以被正确标记，但一些不可达节点却可能被错误标记为可达。C程序的垃圾收集器必须是保守的，根本原因是 C程序不会用任何类型信息标记内存位置 ，如int或者float这样的标量可能会伪装成指针。

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

1. 间接引用坏指针：虚拟内存的某些区域是只读的，某些区域也没有映射到任何有意义的数据，常见的错误是scanf错误，误把scanf("%d",&val)写为scanf("%d",val)
2. 读未初始化的内存：常见的错误是假设堆内存被初始化为零，使用malloc后需要显式地对堆中数据赋值或用calloc
3. 允许栈缓冲区溢出：不检查输入串大小就写入栈中的目标缓冲区，比如不该使用gets(buf)，应该使用fgets
4. 假设指针和它们指向的对象是相同大小的：比如sizeof(int *)不一定等于sizeof(int)
5. 错位错误：容易造成覆盖错误，比如n个元素的指针数组却使用了A[n]
6. 引用指针而不是它所指向的对象：注意C操作符的优先级和结合性，*size--是指针size减一，(*size)--是减少size指针指向的整数值
7. 误解指针运算：指针算术操作以它们指向的对象大小为单位进行，这种大小单位并不一定是字节
8. 引用不存在的变量：函数返回局部变量的地址，可能会导致令人困惑的后果
9. 引用空闲堆块中的数据：引用已经被free函数释放了的堆块中的数据，这种错误可能会在未来表现出来
10. 内存泄漏：忘记释放已分配的块，堆中会逐渐充满垃圾