第9章 虚拟存储器
虚拟存储器提供了三个重要的能力：
1、将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式高效使用了主存。
2、为每个进程提供了一致的地址空间，简化了存储器管理。
3、保护了每个进程的地址空间不被其他进程破坏。
9.1 物理和虚拟地址
物理寻址：计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每字节都有一个唯一的物理地址。CPU访问存储器的最自然的方式就是使用物理地址，这种寻址方式称为物理寻址。
虚拟寻址：CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址，将一个虚拟地址转换为物理地址的任务叫做地址翻译。
地址翻译需要CPU硬件和操作系统之间的紧密合作，CPU芯片上叫做存储器管理单元的专用硬件利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。
9.2 地址空间
地址空间是一个非负整数地址的有序集合：{0，1,2，…}
线性地址空间：地址空间中的整数是连续的。
虚拟地址空间：CPU从一个有N=2n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间：{0,1,2，…，N-1}
一个包含N=2n个地址的虚拟地址空间就叫做一个n位地址空间。现代系统支持32位或者64位虚拟地址空间。
物理地址空间与物理存储器的M字节相对应：{0,1,2，…，M-1}
每个数据对象可以有多个独立的地址，其中每个地址都选自不同的地址空间，这是虚拟存储器的基本思想。
主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。
9.3 虚拟存储器作为缓存的工具
虚拟存储器（VM）被组织为一个由存放在磁盘上的N歌连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，这个唯一的虚拟地址是作为到数组的索引的。
磁盘上数组的内容被缓存在主存中，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高层）之间的传输单元，VM系统通过将虚拟存储器分割为称为虚拟页（VP）的大小固定的块来处理这个问题，每个虚拟页的大小为P=2p字节。类似的，物理存储器被分割为物理页（PP），也称页帧。
任何时刻，虚拟页面的集合都分为三个不相交的子集：未分配的，缓存的，未缓存的。
9.3.1 DRAM缓存的组织结构
DRAM缓存表示虚拟存储器系统的缓存，它在主存中缓存虚拟页。
DRAM缓存使用写回。
9.3.2 页表
页表是一个页表条目的数组，虚拟地址空间中的每个页在页表中的一个固定偏移量处都有一个PTE。假设每个PTE是由一个有效位和一个n位地址字段组成的，有效位表明了该虚拟页当前是否被缓存在DRAM中，如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该缓存页，如果没有设置有效位，那么一个空地址表示这个虚拟页还未被分配，否则这个地址就指向该虚拟页在磁盘上的起始位置。
上图展示了一个有8个虚拟页和4个物理页的系统的页表。VP1247当前被缓存，05还未被分配，36已被分配并未缓存，需要注意的一点是：DRAM缓存是全相联的，任意物理页都可以包含任意虚拟页。
9.3.3 页命中
9.3.4 缺页
DRAM缓存不命中称为缺页。
磁盘和存储器之间传送页的活动叫做变换或者页面调度。
按需页面调度：当有不命中发生时，才换入页面。
9.3.5 分配页面
9.3.6 局部性
局部性保证在任意时刻，程序将旺旺在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集。
如果工作集的大小超过了物理存储器的大小，程序将产生一种状态：颠簸，页面将不断换进换出。
9.4 虚拟存储器作为存储器管理的工具
操作系统为每个进程提供了一个独立的页表，将一个虚拟地址空间映射到物理地址空间。多个虚拟页面可以映射到同一个共享物理页面上。
VM简化了链接和加载、代码和数据共享，以及应用程序的存储器分配。
简化链接：独立的地址空间允许每个进程的存储器映像使用相同的基本格式，而不管代码和数据实际存放在物理存储器的何处。允许链接器生成全链接的可执行文件，这些文件独立于物理存储器中代码和数据的最终位置。
简化加载：虚拟存储器使得容易向存储器中加载可执行文件和共享对象文件。
简化共享：独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般而言，每个进程都有自己私有的代码、数据、堆以及栈区域，是不与其他进程共享的，这种情况下，操作系统创建页表，将相应的虚拟页映射到不同的物理页面。
简化存储器分配：提供一个简单的分配额外存储器的机制。
9.5 虚拟存储器作为存储器保护的工具
通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问。
如果一条指令违反了这些许可条件，那么CPU久出发一个一般保护故障，将控制传递给一个内核中的异常处理程序，Unix外壳一般讲这种异常报告为段错误。
9.6 地址翻译
地址翻译是一个N元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）中元素之间的映射，MAP：VAS→PAS∪∅
这里MAP：如果虚拟地址A处的数据在PAS的物理地址A‘处，MAP（A）=A’
如果虚拟地址A处的数据不在物理存储器中，MAP（A）=∅
CPU中的一个控制寄存器（页表基寄存器）指向当前页表，n位的虚拟地址包含两个部分：一个p位的虚拟页面偏移，一个（n-p）位的虚拟页号，MMU利用VPN来选择适当的PTE，将页表条目中物理页号和虚拟地址中的VPO串联起来，就得到相应的物理地址。物理页面偏移和VPO相同。
页面命中时CPU硬件执行的步骤：
1.处理器生成一个虚拟地址，并把它传送给MMU
2.MMU生成PTE地址，并从高速缓存/主存请求得到它
3.高速缓存/主存向MMU返回PTE
4.MMU构造物理地址，并把它传送给高速缓存/主存
5.高速缓存/主存返回所请求的数据字给处理器
缺页处理：
1-3.同命中
4.PTE中的有效位是0，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序
5.缺页处理程序确定出物理存储器中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘
6.缺页处理程序页面调入新的页面，并更新存储器中的PTE
7.缺页处理程序返回到原来的进程，再次执行导致缺页的指令，CPU将引起缺页的虚拟地址重新发送给MMU。
9.6.1 结合高速缓存和虚拟存储器
主要思路：地址翻译发生在高速缓存查找之前。注意：页表条目可以缓存。
9.6.2 利用TLB加速地址翻译
TLB（翻译后备缓冲器）是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块，TLB通常有高度的相联性。
命中：
1.CPU产生一个虚拟地址
2-3.MMU从TLB中取出相应的PTE
4.MMU将这个虚拟地址翻译成一个物理地址，将它发送到高速缓存/主存
5.高速缓存/主存将所请求的数据字返回给CPU
未命中时，MMU必须从L1缓存中取出相应的PTE
9.6.3 多级页表
用来压缩页表的常用方法是使用层次结构的页表。
如果片i中的每个页面都未被分配，那么一级PTEi就为空，如果在片i中至少有一个页是分配了的，那么一级PTEi就指向一个二级页表的基址，二级页表中的每个PTE都负责映射一个4kb的虚拟存储器页面。
这种方法从两个方面减少了存储器要求
1.一级页表PTE为空，二级页表就不存在
2.只有一级页表才需要总是在主存中，虚拟存储器系统可以在需要时创建、页面调入或者调出二级页表，减少主存的压力，经常使用的二级页表才需要缓存在主存中。
9.7 Linux存储器系统
内核虚拟存储器包含内核中的代码和数据结构，内核虚拟存储器的某些区域被映射到所有进程共享的物理界面。
内核虚拟存储器的其他区域包含每个进程都不相同的数据。
1.Linux虚拟存储器区域
Linux将虚拟存储器组织成一些区域（也称段）的集合，一个区域就是已经存在着的虚拟存储器的连续片，这些页是以某种方式相关联的。
区域允许虚拟地址空间有间隙。
vm_start：指向区域起始处
vm_end：指向区域结束处
vm_prot：描述这个区域内包含的所有页的读写许可权限
vm_flags：描述这个区域内的页面是与其他进程共享的还是这个进程私有的
vm_next：指向链表中下一个区域结构
2.缺页处理
1.判断虚拟地址是否合法
2.判断试图进程的存储器访问是否合法（进程是否有权限）
3.确定这个缺页是进行合法操作造成的，内核选择一个牺牲页面。
9.8 存储器映射
Linux（及其他形式的Unix）通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，这个过程称为存储器映射
虚拟存储器区域可以映射到两种类型的对象中的一种：
1.Unix文件系统中的普通文件
2.匿名文件
一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件之间换来换去，交换文件也叫做交换空间或交换区域。
交换空间限制当前运行着的进程能够分配的虚拟页面的总数。
9.8.1 再看共享对象
一个对象可以被映射到虚拟存储器的一个区域，作为共享对象或者私有对象
对一个映射到私有对象的区域所做的改变，对于其他进程是不可见的。一个映射到共享对象的虚拟存储器区域叫做共享区域，类似的，也有私有区域。
即使对被映射到了多个共享区域，物理存储器中也只需要存放共享对象的一个拷贝。
私有对象使用一种叫做写时拷贝的技术被映射到虚拟存储器中。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时拷贝。只要没有进程试图写它自己的私有区域，它们就可以继续共享物理存储器中对象的一个单独拷贝。然而只要有一个进程试图写私有区域的某个页面，这个写操作就会触发一个保护故障。
9.8.2 再看fork函数
fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。
当fork在新进程中返回时，新进程现在的虚拟存储器刚好和调用fork时存在的虚拟存储器相同。
9.8.3 再看execve函数
删除已存在的用户区域
映射私有区域
映射共享区域
设置程序计数器
9.8.4 使用mmap函数的用户级存储器映射
Unix进程可以使用mmap函数来创建新的虚拟存储器区域，并将对象映射到这些区域中。
mmap函数要求内核创建一个新的虚拟存储器区域，最好从地址start开始的额一个区域，并将文件描述符fd制定的对象的一个连续的片映射到这个新的区域，连续的对相片大小为length，从距文件开始处偏移量为offset字节的地方开始。
参数prot包含描述新映射的虚拟存储器区域的访问权限位：
PROT_EXEC：这个区域内的页面由可以被cpu执行的指令组成
PROT_READ：本区域页面可读
PROT_WRITE：本区域页面可写
PROT_NONE：本区域页面不可访问
参数flag由描述被映射对象类型的位组成
MAP_ANON被映射对象为匿名对象
MAP_PRIVATE私有对象
MAP_SHARED共享对象
munmap函数删除虚拟存储器区域
9.9 动态存储器分配
动态存储器分配器维护着一个进程的虚拟存储器区域——堆
分配器的两种风格：
显式分配器：显式地释放任何已分配的块
隐式分配器（垃圾收集器）：检测一个已分配块什么时候不再被程序所使用，释放这个块
9.9.1 malloc和free函数
程序通过调用malloc函数从堆中分配块
malloc函数返回一个指针，指向大小至少为size字节的存储器块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。
若malloc函数遇到问题，返回NULL并设置errno。
malloc不初始化它返回的存储器，可以使用基于malloc的瘦包装函数calloc函数初始化，将分配的存储器初始化为0。改变一个以前已分配块的大小使用realloc函数。
动态存储器分配器可以通过使用mmap和munmap函数显式地分配和释放堆存储器，或者使用sbrk函数。sbrk函数通过将内核的brk函数指针增加incr来扩展和收缩堆，如果成功，它返回brk的旧值，若失败，返回-1，并将errno设置为ENOMEM，如果incr为0，返回brk当前值，用一个负的incr调用sbrk是合法的。
程序使用free函数来释放已分配的堆块。
ptr参数必须指向一个从malloc、calloc、realloc获得的已分配块的起始位置，如果不是，那么free的行为就是未定义的。
free函数无返回。
9.9.2 为何使用动态存储器分配
原因：直到程序实际运行时，程序才知道某些数据结构的大小。
9.9.3 分配器的要求和目标
显式分配器必须在一些相当严格的约束条件下工作：
处理任意请求序列
立即响应请求
只使用堆
不修改已分配的块
在这些限制条件下，尽量实现吞吐率最大化和存储器使用率最大化。
9.9.4 碎片
碎片：有未使用的存储器但不能用来满足分配请求。
碎片的两种形式：
内部碎片：已分配块比有效载荷大时发生。
外部碎片：空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求。
由于外部碎片难以量化且不可能预测，分配器通常采用启发式策略来试图维持少量大空闲块
9.9.6 隐式空闲链表
隐式空闲链表的优点是简单，缺点是任何操作的开销要求空闲链表的搜索与堆中已分配块和空闲块的总数呈线性关系。
系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。
9.9.7 放置已分配的块
当一个应用请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大可以放置所请求块的空闲块，执行这种搜索的方式由放置策略确定。
首次分配:从头开始搜索空闲链表
下一次适配：从上一次查询结束的地方开始搜索
最佳适配：检查每个空闲块，选择适合所请求大小的最小空闲块
9.9.8 分割空闲块
9.9.9 获取额外的堆存储器
若不能找到合适的空闲块，分配器会通过调用sbrk函数向内核请求额外的堆存储器。分配器将额外的存储器转化成一个大的空闲块，然后使用
9.9.10 合并空闲块
合并策略：
立即合并：每次一个块被释放就合并周围所有块
推迟合并
9.9.11 带边界标记的合并
9.9.12 实现一个简单的分配器
1.一般分配器设计
2.操作空闲链表的基本常数和宏
GET宏读取和返回参数p引用的字，PUT宏将val存放在参数p指向的字中，GET_SIZE和GET_ALLOC宏从地址p处的头部或者脚部分别返回大小和已分配位。
3.创建初始空闲链表
调用mm_init函数初始化堆，调用extend_heap扩展堆，并创建初始的空闲块
4.释放和合并块
调用mm_free释放已分配的块
5.分配块
调用mm_malloc函数向存储器请求大小为size字节的块
9.9.13 显式空闲链表
显式链表的缺点是空闲块必须足够大，导致更大的最小块大小，潜在的提高了内部碎片的程度。
9.9.14 分离的空闲链表
分离存储：维护多个空闲列表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，也叫作大小类。
1.简单分离存储
每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。
优点：分配和释放块快
缺点：容易造成碎片
2.分离适配
分配一个块：确定请求的大小类，对适当的空闲链表做首次适配，查找一个合适的块，找到一个之后，可选的分割它，并将剩余部分插入适当的空闲链表中，如果找不到合适的块，就搜索下一个更大的大小类的空闲链表，直到找到一个合适的块，如果没有合适的块，就向操作系统请求额外的堆存储器，并从这个新的堆存储器中分配出一个块，将剩余部分放置在适当的大小类中，释放块时，执行合并，并将结果放置在相应的空闲链表里。
3.伙伴系统
伙伴系统是分离适配的一种特例，每个大小类都是2的幂。
优点：快速搜索和快速合并。
缺点：内部碎片。
9.10 垃圾收集
垃圾收集器是一种动态存储分配器，它自动释放程序不再需要的已分配块，这些块称为垃圾。自动回收堆存储的过程叫做垃圾收集。
9.10.1 垃圾收集器的基本知识
当存在一条从任意根节点出发并到达p的又向路径时，我们说节点p是可达的。在任何时刻，不可达节点对应于垃圾，是不能被应用再次使用的，垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点并将它们返回给空闲链表，来定期回收它们。
收集器可以按需提供它们的服务，或者它们可以作为一个和应用并行的独立线程，不断更新可达图和回收垃圾。
9.10.2 Mark&Sweep垃圾收集器
Mark&Sweep垃圾收集器由标记阶段和清除阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，清除阶段释放每个未被标记的已分配块。
9.11 c程序中常见的与存储器有关的错误
1. 间接引用坏指针
进程的虚拟地址空间中有较大的洞，当我们试图间接引用一个指向这些洞的指针，操作系统就会以段异常终止程序。而且，虚拟存储器的某些区域是只读的，试图写这些区域将会以保护异常终止这个程序。
2.读未初始化的存储器
3.允许栈缓冲区溢出
如果一个程序不检查输入串的大小就写入栈中的目标缓冲区，那么这个程序就会有缓冲区溢出错误。
4.假设指针和它们指向的对象是相同大小的
5.造成错位错误
6.引用指针，而不是它所指向的对象
7.误解指针运算
8.引用不存在的变量
9.引用空闲堆块中的数据
10.引起存储器泄露
忘记释放已分配块。
参考资料
教材
原文：http://www.cnblogs.com/echo178905/p/5040484.html