第十章 虚拟存储器
虚拟存储器是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的、私有地址空间。通过一个很清晰的机制，虚拟存储器 提供了三个重要能力：
1、它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传递数据，通过这种方式，它高效地使用了主存；
2、它为每个进程提供了一致的地址空间，从而简化了存储器管理；
3、它保护了每个进程的地址空间不被其他进程破坏。
了解虚拟存储器对程序员有如下帮助：
1、虚拟存储器是核心的。虚拟存储器遍及计算机系统所有层面，在硬件异常、汇编器、链接器、加载器、共享对象、文件和进程的设计中都很重要。理解虚拟存储器将帮助你更好地理解系统是如何工作的。
2、虚拟存储器是强大的。虚拟存储器给予应用程序强大的能力，可以创建和破坏存储器块、将存储器块映射到磁盘文件的某个部分，以及与其他进程共享存储器。理解虚拟存储器将帮助你利用它的强大功能在你的应用程序中添加动力。
3、虚拟存储器是危险的。每次应用程序引用一个变量、间接引用一个指针，或者调用一个诸如malloc这样的动态分配程序时，它就会和虚拟存储器发生交互。如果虚拟存储器使用不当，应用将发生复杂的错误，
10.1 物理和虚拟地址
计算机系统的主存被组织成一个由M个连续字节组成数组。每个字节有唯一的物理地址（physical address，PA）。起始地址为0。CPU通过物理地址访问存储器的方式称为物理寻址（physical addressing）。下图展示了使用物理寻址的系统，指令是从物理地址4处寻址4个字节。执行过程：CPU执行这条加载指令时，它会生成一个有效的物理地址，通过存储器总线，把它传递给主存。主存取出从物理地址4处开始的4个字节，并将它返回给CPU，CPU会将它存放在一个寄存器里。
现代通用处理器不使用物理寻址，而是使用虚拟寻址（virtual addressing）其框图如下：
CPU通过生成一个虚拟地址（virtual address，VA）来 访问主存，这个虚拟地址在被送到存储器之前，通过存储器管理单元（memory management unit，MMU）专用硬件，利用存放在主存中的查询表成物理地址。
10.2 地址空间
地址空间（address space）是一个非负整数地址的有序集合，如果地址是连续的，称为线性地址空间（linear address space）。本书假设使用的都是线性地址空间。
在一个带虚拟存储器的系统中，CPU从一个有N=2^n个地址的地址空间中生成虚拟地址在，这个地址空间称为虚拟地址空间（virtual address space）。地址空间的大小是由表示最大地址所需要的位数来描述的。如，一个包含N=2^n个地址的虚拟地址空间就叫做一个n位地址空间。体统一般都是32位或64位虚拟地址空间。
系统还有一个物理地址空间（physical address space），它与物理存储器的M个字节相对应。M不要求是2的幂，但为了简化讨论，我们假设M=2^m.
地址空间的概念很重要，因为它清除地区分了数据对象（字节）和他们的属性（地址）。可以概括总结，允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。这就是虚拟存储器的基本思想。主存中的每个字节都有一个选自虚拟地址空间的虚拟地址，和一个选自物理地址空间的物理地址。
10.3 虚拟存储器作为缓存的工具
虚拟存储器被分割为称为虚拟页（virtual page，VP）的大小固定的块。VP的大小为P=2^p字节。物理存储器被分割为物理页（physical page， PP）,小小也为P字节。
任意时刻，虚拟页面的集合都分为三个不相交的子集：
1、未分配的：VM系统还未分配（或创建）的页，没有任何数据和它们关联，因此页不占用任何磁盘空间。
2、缓存的：当前缓存在为了存储器中的已分配页；
3、未缓存的：没有缓存在物理存储器中的已分配页。
下图是一个有8个虚拟页的小虚拟存储器。虚拟页0、3未被分配，所以在磁盘上不存在。虚拟页1、4、6被缓存在物理存储器中。页2、5、7已经被分配，但当前并未缓存到DRAM。
10.3.1 DRAM高速缓存的组织结构
这里用SRAM缓存表示CPU和主存之间的L1、L2高速缓存，用DRAM缓存表示虚拟存储器系统的缓存，它在主存中缓存虚拟页。
10.3.2 页表
虚拟存储器系统必须判断虚拟页是否存放在DRAM中，如果是，必须确定这个虚拟页存放在哪个物理页中。如果不命中，必须判断这个虚拟页存放在磁盘的哪个位置，在物理存储器中选择一个牺牲页，并将虚拟页从磁盘拷贝到DRAM中，替换这个牺牲页。提到的这些功能是由软硬件结合实现的，包括操作系统、MMU中的地址翻译硬件，和一个存放在物理存储器中叫做页表（page table）的数据结构。页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。
下图是一个页表的基本结构，有8个虚拟页和4个物理页。4个虚拟页被缓存在DRAM中，VP0和VP5未被分配，VP3和VP6已经分配，但未被缓存。页表的左边有一个有效位，用于标识是否被缓存。
10.3.3 页命中
CPU读取缓存在DRAM中的虚拟页称为页命中
10.3.4 缺页
CPU读取没有缓存的虚拟页称为缺页（page fault）。缺页会触发缺页异常，调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，然后替换。
10.3.5 分配页面
下图展示当操作系统分配一个新的虚拟存储器页时，对我们示例页表的影响。如调用malloc的结果。在这个示例中，通过在磁盘上创建空间，并跟新PTE5，使他指向磁盘上这个新创建的页面，从而分配VP5
10.3.6 局部性再次搭救
尽管在整个运行过程中程序引用的不同页面的总数可能超过物理存储器总的大小，但是局部性原则保证了任意时刻，这些页面将趋向于在一个较小的活动页面（active page）集合上，这个集合叫做工作集（working set）。
10.4 虚拟存储器作为存储器管理的工具
前面都假设只有一个页表，实际上，操作系统为每个进程都提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。如下图，多个虚拟页面可以映射到同一个共享物理页面上。
10.4.1 简化链接
独立的地址空间允许每个进程为它的存储器映像使用相同的基本格式，而不管代码和数据实际存放在物理存储器的何处。例如每个Linux进程都使用下图所示的格式。
文本区总是从虚拟地址0x08048000开始，栈是从地址0xbfffffff向下延展，共享库代码总是 从地址0x40000000开始，而操作系统代码和数据总是从0xc0000000开始。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成全链接的可执行文件，这些可执行文件是独立于物理存储器总代码和数据的最终位置的。
10.4.2 简化共享
独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。通常，每个进程有私有的代码、数据、堆以及栈区域，是不和其他进程共享的。此时操作系统创建页表，将相应的虚拟页映射到不同的物理页面。
然而，有时，还是需要进程来共享代码和数据。如每个进程必须调用相同的操作系统内核的代码，而每个C程序都会调用标准库中的程序。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个拷贝，而不是在每个进程中都包括单独的内核和C标准库的拷贝。
10.4.3 简化存储器分配
当一个运行在用户进程中的程序要求额外的堆空间时（如malloc），操作系统分配对应数量个连续的虚拟存储器页面，并且将它们映射到物理存储器中任意位置。由于页表的工作方式，操作系统没有必要分配连续的物理内存。
10.4.4 简化加载
10.5 虚拟存储器作为存储器保护的工具
通过添加三个许可位到PTE，来控制对一个虚拟页面的访问，如下图
SUP：表示进程是否必须运行在内核（超级用户） 模式下才能访问页面。内核模式可以访问任何页面，用户模式只允许访问SPU为0的页面。
READ和WRITE：控制对页面的读写访问。
如i进程在用户模式下，它只有读VP0的权限，有读写VP1的权限，不允许访问VP2;
如果指令违法了这些许可条件，CPU就触发一般保护故障，将控制传递给一个内核中的异常处理程序。
10.6 地址翻译
本节讲述地址翻译基础知识，目的是对硬件在支持虚拟存储器中的角色有正确的评价。下图是本节将用到的符号。
地址翻译时N元素的虚拟地址空间（VAS）中的元素和M元素的物理地址空间（PAS）中元素之间的映射。
下图展示了MMU是如何利用页表来实现这种映射的。CPU中的一个控制寄存器，页表机基址寄存器（page table base register，PTBR）指向当前页表。n位的虚拟地址包含两个部分：一个P位的虚拟页面偏移（virtual page offset，VPO）和一个（n-p）位的虚拟页号（virtual page number，VPN）。MMU利用VPN来选择设当的PTE。将页表条目中物理页号（physical page number，PPN）和虚拟地址中的VPO串联起来，就得到相应的物理地址。注意，因为物理和虚拟页面都是P字节的，所以物理页面偏移（physical page offset,PPO）和VPO是相同的。
下图展示了页面命中，CPU硬件执行的步骤
第一步：处理器生成一个虚拟地址，并把它传送到MMU。
第二步：MMU生成PTE地址，并从高速缓存/主存请求得到它。
第三步：高速缓存/主存向MMU返回PTE。
第四步：MMU构造物理地址，并把它传送到高速缓存/主存。
第五步：高速缓存/主存返回所请求的数据字给处理器。
页面命中完全由硬件处理，而处理缺页要求硬件和操作系统内核协作完成，如下图
第一步到第三步：和页面命中的前三步相同。
第四步：PTE中的有效位是0，所以MMU触发异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。
第五步：缺页处理程序确定出物理存储器中的牺牲页，如果这个页已经被修改，则把它页面换出到磁盘。
第六步：缺页处理程序页面调入新的页面，并更新存储器中的PTE。
第七步：缺页处理程序返回到原来的进程，驱使导致缺页的指令重新启动。CPU将引起缺页的指令重新发送给MMU。因为虚拟页面现在缓存在物理存储器中，所以就会命中，在MMU执行了上图中的步骤后，主存就会将所请求字返回给处理器。
10.6.1 结合高速缓存和虚拟存储器
在既使用虚拟存储器又使用SRAM缓存的系统中，大多数系统使用物理地址来访问高速缓存，这样多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块成为很简单的事情。而且，高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。
下图展示了物理寻址的高速缓存如何和虚拟存储器结合的，主要思路是地址翻译发生在高速缓存查找之前。注意页表条目也可以像其他的数据一样进行缓存。
10.6.2 利用TLB加速地址翻译
MMU中包含一个关于PTE的小缓存，称为翻译后备缓冲器（translation lookaside buffer，TLB），它通常有高度的相关性。下图，用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB有T=2^t个组，那么TLB索引（TLBI）是由VPN的t个最低位组成的，而TLB标记（TLBT）是由VPN中剩余的位组成的。
下图展示了当TLB命中时（通常情况）所包括的步骤。这里的关键点是，所有的地址翻译步骤都是在MMU上执行的。因此非常快。
第一步： CPU产生一个虚拟地址
第二步和第三步：MMU从TLB中取出相应的PTE
第四步：MMU将这个虚拟地址翻译成一个物理地址，并将它发送到高速缓存/主存：
第五步：高速缓存/主存将所请求的数据字返回给CPU。
下图展示了TLB不命中时的步骤。MMU必须从L1缓存中取出相应的PTE。新取出的PTE存放在TLB中，可能会覆盖一个已经存在的条目。
10.6.3 多级页表
假设32位虚拟地址空间被分为4KB的页，而每个页表条目都是4字节。还假设虚拟地址空间有如下形式：存储器的头2K个页面分配给了代码和数据，接下来的6K个页面还未分配，再接下来的1023个页面也未分配，接下来的1个页面分配给了用户栈。下图展示了两级页表的层次结构
一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的组块（chunk），这里每个组块都是由1024个连续的页面组成的。如PTE0映射第一个组块，PTE1映射接下来的组块，以此类推。假设地址空间是4GB，1024个PTE足够了。
如果每个组块i中的每个页面都未被分配，那么一级PTE i就为空。如图中，组块2~7是未被分配的。然而 ，如果在组块i中至少有一个页时分配了的，那么一级PTE i就指向一个二级页表的基址。如图中组块0、1、8的所有或者部分已被分配，所以它们的一级PTE就指向二级页表。
二级页表中的每个PTE都负责映射一个4KB的虚拟存储器页面，就像我们查看只有一级的页表一样。注意，使用4字节的PTE，每个一级和二级页表都是4KB字节，就刚好和一个页面的大小是一样的。
这种方法从两方面减少了存储器要求：
第一，如果一个页表中的一个PTE是空的，那么相应的二级页表就根本不存在。这是一种巨大的潜在节约，因为对于一个典型的程序，4GB的虚拟地址空间的大部分都是未分配的。
第二，只有一级页表才需要总是在主存中。虚拟存储器系统可以在需要时创建，把页面调入或调出二级页表，这就减少了主存的压力。只有最进程使用的二级页表才需要缓存在主存中。
10.6.4 综合：端到端的地址翻译
10.7 案例研究：Pentium/Linux存储器系统
下图是Pentium存储器系统
TLB是虚拟寻址的，缓存32位的页表条目。指令TLB缓存取址单元产生的虚拟地址的PTE，有32个题目数据TLB缓存数据的虚拟地址的PTE，有64个条目。页面大小可以在启动时配置成4KB或者4MB。运行在Pentium上的Linux使用4KB的页面。
L1、L2缓存是物理寻址的，块大小为32字节。每个L1高速缓存的大小是16KB，有128组，其中每组都包含4行。L2高速缓存的大小在128K~2Mb之间变化，典型值是512KB。
10.7.1 Pentium地址翻译
下图描述了Pentium系统上地址翻译的整个过程，从CPU产生虚拟地址，到数据字从存储器到达。
Pentium页表
Pentium系统使用下图所示两级页表。第一级页表叫做页面目录（page directory），包含1024个32位的页面目录条目（page directory entry，PDE），其中每个条目都指向1024个2级页表中的一个。每个页表包含1024个32位的PTE,其中每个都指向物理存储器或者磁盘上的一个页面。
每个进程都有一个唯一的页面目录和页表集合。当一个Linux进程正在运行时，尽管Pentium的体系结构允许页表换进换出，但是页表目录和已分配页面相关的页表都是常驻存储器的。页面目录基址寄存器指向页表目录的起始地址。
下图展示了PDE的格式。当P=1是，地址字段中包含一个20位的物业页号，指向相应的页表的起始位置。注意，这要求页表要4KB对齐。
下图展示了PTE格式。当P=1时，地址字段包含一个20位的物理页号，指向物理存储器中某个页的基址。同样，这也要求物理页面要4KB对齐。
PTE有两个许可位，用来控制对这个页面的访问。R/W位确定这个页面的内容的读写权限。U/S位确定用户模式是否有权限。
每次访问一个页面时，MMU就设置A位，也叫做引用位（reference 比）。内核可以用A位来实现 它的页面替换算法。每次写页面时，MMU就设置D位，也叫修改位（dirty bit）。一个已经被修改了的页面有时页叫做修改页面（dirty page）。D位告诉内核在它考入一个替代页面时，是否必须写回牺牲页面。内核可以调用一个特殊的内核模式指令来清除A位或D位。
Pentium页表翻译
下图展示了Pentium MMU如何使用2级页表，将一个虚拟地址翻译成物理地址。20位的VPN被分成2个10位的块。VPN1在PDBR指向的页目录中所以一个PDE。PDE中的地址指向的某个页表的基址被VPN2索引。被VPN2索引的PTE中的PPN和VPO连接起来形成了物理地址。
Pentium TLB翻译
下图描绘了Pentium系统中TLB翻译的过程。如果PTE被缓存在TLBI索引的组里（TLB命中），那么就从这个缓存的PTE中抽取PPN，并把这个PPN和VPO连接起来形成物理地址。如果没有缓存PTE，但是缓存了PDE（部分TLB命中），那么MMU必须在它形成物理地址之前，从存储器中提取相应的PTE。最后，如果PDE和PTE都没有被缓存（TLB不命中），那么MMU必须从存储器中取出PDE和PTE，以 形成物理地址。
10.7.2 Linux虚拟存储器系统
如下图所示，Linux为每个进程维持了一个单独的虚拟地址空间。内核虚拟存储器包含内核中的代码和数据。内核虚拟存储器的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据结构。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组联系的物理页面。这就为内核提供了一种便利的方法来访问物理存储器中任何特定的位置，例如，当它需要再一些设备上执行存储器映射的I/O操作时，而这些设备被映射到特定的物理存储器位置。
内核虚拟存储器的其他区域包含每个进程都不相同的数据。示例包括页表、内核在进程的上下文中执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。
Linux虚拟存储器区域
Linux将虚拟存储器组织成一些区域（也叫做段） 的集合。一个区域（area）就是已经存在着的（已分配的）虚拟存储器的连续组块（chunk），这些虚拟存储器的页面是以某种方式相关联的。例如，代码段、数据段、堆、共享库段，以及用户栈都是不同的区域。每个存在的虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页面是不存在的，并且不能被进程引用。区域的概念很重要，因为它允许虚拟地址空间有间隙。内核并不记录那些不存在的虚拟页，而这样的页面也不占用存储器、磁盘或者内核本身中的任何额外资源。
下图强调了记录一个进程中虚拟存储器区域的内核数据结构。内核在系统中为每个进程维护一个单独的任务结构（源代码中的task_struct）。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息（如PID、指向用户栈的指针、可执行目标文件的名字，以及程序计数器）。
task_struct中的一个条目指向mm_struct,它描述了虚拟存储器的当前状态。我们关注pgd和mmap两个字段，其中pgd指向页面目录表的基址，而mmap指向一个vm_area_structs（区域结构） 的链表，其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域（area）。当内核运行这个进程是，它就将pgd存放在PDBR控制寄存器中。
一个具体区域的区域结构（vm_area_struct）包含下面字段：
vm_start:指向这个区域的起始处。
vm_end:指向这个区域的结束处。
vm_prot:描述这个区域内包含的所有页面的读写许可权限。
vm_flags:描述这个区域内的页面与其他进程是共享的还是私有的。
vm_next:指向链表中下一个区域结构。
Linux缺页异常处理
假设MMU在试图翻译某个虚拟地址A时，触发了一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序将执行下面步骤：
1、缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较，判断A是否合法。如果不合法，那么缺页处理程序就会触发一个段错误，从而终止这个进程。
2、判断是否拥有访问权限 ，如果没有，会触发一个保护异常，从而终止这个进程。
3、内核选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将它交换出去，换入新的页面，并更新页表，从而处理这次缺页。当缺页处理程序返回时，CPU重新启动引起缺页的指令，这条指令将再次发送A到MMU，这次，MMU就能正常翻译A，而不会再产生一个缺页中断了。
10.8 存储器映射
Linux通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，这个过程称为存储器映射（memory mapping）。虚拟存储器区域可以映射到两种类型的对象：
1、Unix文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件（例如一个可执行目标文件）的联系部分。文件被分成页面大小的片，每个片包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际交换进入物理存储器，直到CPU第一次引用到页面（即发射一个虚拟地址，落在地址空间这个页面的范围之内）。如果区域比文件的这部分要大一些，那么就用0来填充这个区域的剩下部分。
2、匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制0。CPU第一次引用这样一个区域内的虚拟页面时，内核就在物理存储器中找到一个合适的牺牲页面，如果页面被修改过，就将这个页面换出来，用二进制0覆盖牺牲页面，并更新页表，将这个页面标记为是驻留在存储器中的。注意在磁盘和存储器之间并没有实际的数据传送。因此，映射到匿名文件的区域中的页面，有时也叫做请求二进制零的页（demand-zero page）。
无论在哪种情况，一旦一个虚拟页面被初始化，它就在一个有内核维护的专门的交换文件（swap file）之间换来换去。交换文件也叫做交换空间（swap space）或者交换区域（swap area）。需要注意，任何时刻，交换空间都限制着当前运行着 的进程能够分配的虚拟页面的总数。
10.8.1 再看共享对象
一个对象可以被映射到虚拟存储器的一个区域，作为共享对象或私有对象。如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共线对象映射到他们虚拟存储器的其他进程而言，也是可见的。而且这些变化也会反映在磁盘上的原始对象中。
另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。一个共享对象映射到的虚拟存储器区域叫做共享区域，同理也有私有区域。
下图所示，进程1和2都将同一个共享对象映射到自己进程的虚拟存储器中（1先，2后），因为每个对象都有唯一的路径文件名，内核可以迅速的判断有进程1已经映射了这个对象，而且可以使进程2中的页表条目指向相应的物理页面。关键点在于即使对象被映射到了多个共享区域，物理存储器中也只需要存放共享对象的一个拷贝。
私有对象是使用一种叫做写时拷贝（copy-on-write）的技术被映射到虚拟存储器中的。一个私有对象开始生命周期的方式基本上与共享对象的一样，在物理存储器中只保存有私有对象的一份拷贝。
下图中，两个进程将一个私有对象映射到它们虚拟存储器的不同区域，但是共享这个对象同一个物理拷贝。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时拷贝。只要没有进程试图写他自己的私有区域，它们就可以继续共享物理存储器中对象的一个单独拷贝。
然而只要有一个进程试图写私有区域内的某个页面，这个写操作就会触发一个保护故障。当故障处理程序注意到保护异常是由于进程试图写私有的写时拷贝区域引起的，它就会在物理存储器中创建一个新的拷贝，更新页表条目指向这个新拷贝，然后恢复这个页面的可写权限。如下图所示。
当故障处理程序返回时，CPU重新执行这个写操作，就可以正常执行了。通过延迟私有对象的拷贝，直到最后时刻，写时拷贝充分使用了稀有的物理存储器。
10.8.2 再看fork函数
当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给新进程创建虚拟存储器，它创建了当前进程的mm_struct、区域结构（vm_area_struct）和页表的原样拷贝。它标记两个进程中的每个页面为只读的，并标记两个进程中的每个区域结构为私有的写时拷贝。
当fork在新进程中返回时，新进程现在的那些存储器刚好和调用fork时存在的虚拟存储器相同。当这两个进程中的任意一个后来进行写操作时，写时拷贝机制就会创建新的页面，因此也就为每个进程保持了私有地址空间的抽象概念。
10.8.3 再看execve函数
假设运行在当前进程中的程序执行了如下的execve调用：
Execve("a..out", argv, environ);
execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out程序有效地替代了当前程序。加载并运行a.out需要以下几个步骤：
1、删除已存在的用户区域。删除当前进程虚拟地址的用户部分中已存在的区域结构。
2、映射私有区域。为新程序的文本、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的写时拷贝。文本和数据区域被映射为a.out文件中的文本和数据区。bss去域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。栈和堆区域也是请求二进制零的，初始长度为0.
3、映射共享区域。如果a.out程序域共享对象链接，如标准C库libc.so，那么这些对象都是动态链接到这个程序的，并且映射到用户虚拟地址空间中的共享区域内。
4、设置程序计数器。execve做的最后一件事就是设置当前进程上下文中的PC，使他指向文本区域的入口点。下一次调度这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。
下图概括了私有区域的不同映射
10.8.4 使用mmap函数的用户级存储器映射
Unix进程可以使用mmap函数来创建新的虚拟存储器区域，并将对象映射到这些区域
mmap函数要求内核创建一个新的虚拟存储器区域，最好是从地址start开始，并将文件描述符fd指定的对象的一个连续的组块（chunk）映射到这个新的区域。连续的对象组块大小为length字节，从距文件开始处偏移量为offset字节的地方开始。start地址仅仅是一个暗示，通常被定义为NULL。为了我们的目的，我们总是假设起始地址位NULL。下图描述了这些参数的意义。
参数port包含描述新映射的虚拟存储器区域的访问权限位（在相应区域结构中的vm_port位）
PROT_EXEC:这个区域内的页面由可以被CPU执行的指令组成。
PROT_READ:这个区域内的页面可读
PROT_WRITE:这个区域内的页面可写
PROT_NONE这个区域内的页面不能被访问。
参数flags由描述被映射对象类型的位组成。如果MAP_ANON标记位被设置，并且fd位NULL，那么被映射的对象就是一个匿名对象，而相应的虚拟页面是请求二进制零的。MAP_PRIVATE表示被映射的对象是一个私有的写时拷贝对象，而MAP_SHARED表示是一个共享对象。如
bufp=mmap（MULL, size, PROT_READ, MAP_PRIVATE|MAP_ANON, 0, 0）;
让内核创建一个新的包含size字节的只读、私有、请求二进制零的虚拟存储器区域。如果调用成功，那么bufp包含新区域的地址。
munmap函数删除虚拟存储器区域：
此函数删除从虚拟地址start开始的length字节的区域。
10.9 动态存储器分配
动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆（heap）。如下图。大多数Unix系统中，堆是一个请求二进制零的区域，它紧接在未初始化的bss区域后开始向上生长。对于每个进程，内核维护着一个变量brk（读做break），它指向堆的顶部。
分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟存储器组块，要么是已分配的，要么是空闲的。已分配块显式地保留给应用使用。空闲块保持空闲，直到它显式地被应用所分配。一个已分配的块保持到它被释放，这个释放可以是应用显式地执行的，也可以是存储器分配器自身隐式执行的。
分配器有两种基本风格，都要求应用显式地分配块，区别在于哪里负责释放：
显示分配器（explicit allocator）要求应用显式地释放已分配的块。例如C的malloc，需要free释放。c++中的new和dellete。
隐式分配器（implicit allocator），在另一方面，要求分配器检测到一个已分配的块不在被使用时释放。隐式分配器也叫垃圾收集器（garbage collector），而自动释放未使用的已分配的块的过程叫做垃圾收集（garbage collection）。如Lisp、ML以及java等高级语言都是用隐式分配器。
10.9.1 malloc和free函数
如果malloc失败，它就返回NULL，并设置errno。malloc不初始化它返回的存储器。想要初始化可以使用calloc，它将分配的存储器初始化为0.想要改变一个已分配块的大小可以使用realloc。
malloc可以通过mmap和munmap函数显式地分配和释放堆存储器，还可以使用sbrk函数：
sbrk函数通过将内核的brk指针增加incr来扩展和收缩堆。如果成功，它就返回brk的旧值，否则，它就返回-1，并将errno设置为ENOMEM。如果incr为零，那么sbrk就返回brk的当前值。用一个为负的incr来调用sbrk时合法的，而且很巧妙，因为返回值（brk的旧值） 指向距新堆顶上面的abs（incr）字节。
10.9.2 为什么要使用动态存储器分配
因为直到程序运行时，才直到某些数据结构的大小。
10.9.3 分配器的要求和目标
1、处理任意请求序列
2、立即响应
3、只使用堆
4、对齐
5、不修改已分配的块
6、目标1：最大化吞吐率
7、目标2：最大化存储器利用率
10.9.4 碎片
当有未使用的存储器但是不满足分配请求时的现象叫做碎片（fragmentation）现象。有两种形式：
内部碎片和外部碎片。
内部碎片是在一个已分配块比有效载荷大时发生的。
外部碎片是当空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。
10.9.5 实现问题
一个实际的分配器要在吞吐率和利用率之间把握好平衡，需要考虑以下问题：
1、空闲块组织：如何记录空闲块？
2、放置：如何选择一个合适的空闲块来放置一个新分配的块？
3、分割：将一个新分配的块放置到某个空闲块之后，如何处理这个空闲块中的剩余部分？
4、合并：如何处理一个刚被释放的块
本节后面的部分将详细讨论上述问题。
10.9.6 隐式空闲链表
实际的分配器需要数据结构来区别块边界，区别已分配块和空闲块，这些信息一般嵌入在块本身。如下图所示，块是由一个字的头部、有效载荷，以及一些可能的额外填充组成。
头部编码了这个块的大小，以及这个块是已分配的还是空闲的。如果强加一个双字的对齐约束条件，那么块的大小就总是8的倍数，且块大小的最低3位总是0.因此只需要存储块大小的29个高位，剩余3位用来编码其他信息。例如一个大小为24（0x18）字节的已分配块，它的头部是
头后面是应用调用malloc时的有效载荷。
有效载荷后面是一块不使用的填充块，其大小是任意的。需要填充有很多原因。比如，填充可能是分配器策略的一部分，用来对付外部碎片。或者也需要用它来满足对齐要求。
下图将堆组织为成为隐式空闲链表的结构。空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有块，从而间接遍历整个空闲块的集合。
10.9.7 放置分配的块
当应用请求k字节的块时，分配器搜索空闲链表，查找一个可以放下k字节的块。分配器执行这种搜索的方式是由放置策略（place policy）确定的。常见策略如下：
首次适配（first fit）：从头开始搜索，选择第一个满足条件的空闲块；有点是将大的空闲块保留在链表的后面，缺点是趋向于在靠近链表起始处留下小的“碎片”，增加了对较大块的搜索时间。
下一次适配（next fit）：从上一次查询结束的地方开始搜索。比首次适配快，但是利用率没首次适配高。
最佳适配（best fit）：查询每个空闲块，选择满足需求的最小的空闲块。利用率最高，但效率低。
10.9.8 分割空闲块
当分配器找到匹配的空闲块，就要决定分配这个空闲块中多少空间。一种方式是选择用整个空闲块。另一种方式是第一部分编程分配块，剩下的变成一个新的空闲块。
10.9.9 获取额外的堆存储器
如果分配器不能为请求块找到合适的空闲块，它将通过合并那些在存储器中物理上相邻的空闲块来创建更大的空闲块。如果这样还不够，那么分配器会向内核请求额外的堆存储器，通过调用mmap或sbrk。这两种情况，分配器都会将额外的存储器转化成一个大的空闲块，并插入到空闲链表中，被请求的块放置在这个新的空闲块中。
10.9.10 合并空闲块
当分配器释放一个已分配块时，可能与其他空闲块相邻。分配器将会合并相邻的空闲块，这个过程成为合并（coalescing）。有立即合并和推迟合并两种。
10.9.11 带边界标记的合并
在每个块的结尾处添加一个脚部，它是头部的一个副本。这样分配器可以检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块结尾位置一个字的距离。
10.9.12 综合：实现一个简单的分配器
10.9.13 显式空闲链表
块分配与堆块的总数呈线性关系，所以对于通用分配器，隐式空闲链表是不合适的。新的方法是将空闲块组织为某种形式的显式数据结构。因为根据定义，程序是不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个pred（祖先）和succ（后继）指针，如下图所示
使用双向链表，使首次适配的适配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，以可能是常数，取决于空闲链表中对块排序所选择的策略：
一种方法是用后进先出（LIFO）的顺序维护链表，将新释放的块放置在链表的开始处。使用LIFO的顺序和首次适配的放置策略，分配器会最先检查最近使用过的块。释放一个块可以在常数时间内完成。如果使用了边界标记，那么合并也可以在常数时间内完成。
另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它祖先的地址。此时，释放一个块需要线性时间的搜索，来定位合适的祖先。平衡点在于，按照地址排序的首次适配比LIFO排序的手册适配有更高的存储器利用率，接近最佳适配的利用率。
一般而言，显式链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在提高了内部碎片的程度。
10.9.14 分离的空闲链表
一个使用单向空闲链表的分配器需要与空闲块数量呈线性关系的时间来分配块。常见的优化方法称为分离存储（segregated storage）维护多个空闲链表，其中每个链表中的块致有大相等的大小。
10.10 垃圾收集
垃圾收集器（garbage collector）是一种动态存储分配器，它自动释放程序不再需要的已分配的块。
