预计时间：10h
实际时间：11h
虚拟存储器是对主存的抽象概念。
虚拟存储器提供三个重要的能力：
地址空间：一个非负整数地址的有序集合。
线性地址空间：地址空间中的整数是连续的
虚拟地址空间：一个带有虚拟存储器的系统中，CPU从一个有N=2^n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间。
地址空间的概念区分了数据对象（字节）和它们的属性（地址）。
虚拟存储器的基本思想：我们允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。
虚拟存储器——虚拟页VP，每个虚拟页大小为P=2^平字节
物理存储器——物理页PP，也叫页帧，大小也为P字节。
任意时刻，虚拟页面的集合都被分为三个不相交的子集：
1、DRAM缓存的组织结构是由巨大的不命中开销驱动的。
2、页表：
虚拟地址空间中的每个页在页表中的固定偏移量出都有一个PTE。
假设每个PTE，一般由一个有效位和一个n位地址字段组成。有效位表明了该虚拟页是否被缓存在DRAM中。
3、缺页:
DRAM缓存不命中称为缺页。当cpu引用一个DRAM中的一个字时，该字并未缓存在DRAM中，地址翻译硬件从存储器中读出这个字，从有效位推断它未被缓存，并且触发一个缺页异常。缺页异常再调用内核中的缺页异常处理程序，选择一个牺牲页并拷贝引用的字回磁盘，更新并返回。
分配页面：通过磁盘上创建空间，并更新，使它指向磁盘上这个新创建的页面，从而进行分配。
程序的局部性保证了在任意时刻，程序往往在一个小的工作集中活动。工作集大小超出物理存储器大小时会出现颠簸现象。
操作系统每个进程都有一个独立的页表，因而也就是一个独立的虚拟地址空间。
按需页面调度和独立的虚拟地址空间的结合，对系统中存储器的使用和管理造成了深远的影响。特别地，VM简化了链接和加载、代码和数据共享，以及应用程序的存储器分配。
在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问。例如：SUP位表示进程是否必须运行在内核模式下才能访问网页；READ位和WRITE位的读和写进行访问。
如果一条指令违反了这些许可条件，那么cpu就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。
形式上说。地址翻译是一个N元素的虚拟地址空间（VAS）中元素和一个M元素的物理地址空间（PAS）中元素的映射。
使用页表的地址翻译：页表基址寄存器指向当前页表，通过n位的虚拟地址中n-p位的虚拟页号（VPN）从页表中选出适当的页表条目，将页表条目中中的物理页号（PPN）和虚拟地址中的p位虚拟页面偏移（VPO）串联起来，得到物理地址。因为VPO和PPO是相同的。
当既使用虚拟存储器又使用SRAM高速缓存的系统中，一般使用物理寻址，多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块将成为简单的事情，而且地址翻译将处理保护问题。
主要的思路：将地址翻译发生在高速缓存查找之前。
为了消除因MMU查阅PTE而产生的对存储器的额外开销，通过在MMU中包含一个关于PTE的小的缓存，称为翻译后备缓冲器（TLB），它是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。
步骤：
一个系统若只有一个页表会造成需要一个很大的空间来储存页表且远远大于应用所需，所以一般采用多级页表结构。一般虚拟地址被划分为K个VPN和1个VPO，每个VPNi都是一个到第i级页表的索引，当i<k时，第i级页表中的每个PTE都是指向第i+1级的某个页表的基址，而第K级页表中的PTE都包含某个物理页面的PPN或者一个磁盘块的地址。
在这里，PTE有三个权限位：
还有连个缺页处理程序涉及到的位：
Linux为每个进程维持了一个单独的虚拟地址空间，
内核虚拟存储器包括：内核中的代码和数据结构。
一部分区域映射到所有进程共享的物理页面
另一部分包含每个进程都不相同的数据。
区域：就是已分配的虚拟存储器的连续片。
区域的例子：
每个存在的虚拟页面都保存在某个区域中。内核为系统中的每个进程维护一个单独的任务结构task_struct：
一个具体区域的区域结构包括：
不合法，触发段错误，终止进程
合法，进入下一条
不合法，触发保护异常，终止程序
合法，进入下一条
通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，这个过程叫做存储器映射。
虚拟存储器区域可以映射到两种类型的对象：
共享对象对于所有把它映射到自己的虚拟存储器进程来说都是可见的
即使映射到多个共享区域，物理存储器中也只需要存放共享对象的一个拷贝。
私有对象一般使用一种写时拷贝的技术来映射到虚拟存储器中。
一个私有对象开始时与共享对象一样，都是每个进程虚拟空间中各自有一个映射，但物理存储器中只有一份拷贝。
而当到某个进程试图写私有对象的某个区域时，会触发一个保护故障，故障处理程序就会在物理存储器中创建这个页面的一个新拷贝，并更新相应PTE和恢复写权限，再将控制返回到写指令处。
#include <unistd.h>#include <sys/mman.h>
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
成功返回指向映射区域的指针，若出错则为-1
参数含义：
prot：访问权限位，具体如下：
PROT_EXEC:由可以被CPU执行的指令组成PROT_READ:可读PROT_WRITE:可写PROT_NONE:不能被访问
flag：由描述被映射对象类型的位组成，具体如下：
MAP_ANON:匿名对象，虚拟页面是二进制0MAP_PRIVATE:私有的、写时拷贝的对象
MAP_SHARED：共享对象
include
include <sys/mman.h>
int munmap(void *start, size_t length);
成功返回0，失败返回-1从start开始删除，由接下来length字节组成的区域。
大多数C程序在运行时需要额外虚拟存储器时，会使用一个动态存储器分配器，它维护者一个进程的虚拟存储器区域，称为堆。堆是一个请求二进制零的区域，它紧接在未初始化的bss区域后开始，并向上生长，对于每个进程，内核维护着一个变量brk，它指向堆的顶部。
分配器将堆视为一组不同大小的块的集合来维护，每个块就是虚拟存储器组块，分配的或空闲的。分配的供应用使用或被进程释放，空闲的等待被应用所分配。
分配器有两种基本风格：
1、malloc和free函数
C标准库提供了称为malloc程序包的显式分配器，可以调用它来从堆中分配块。Malloc不会初始化它返回的存储器。Free用来释放已分配的堆块，注意其参数必须指向一个从malloc中获得的已分配块的起始位置。
为什么要使用动态分配器分配：
程序使用动态存储器分配的最重要的原因是它经常直到程序实际运行时才知道某些数据结构的大小。
分配器的要求：
2、碎片
造成堆利用率低的主要原因，在虽然有未使用的存储器但不能满足分配请求时就称出现碎片。
3、隐式空闲链表：
通过将空闲块和已分配块的头部的信息将这些块连接起来直到最后一个设置了已分配位和大小为零的终止头部，成为一个链表结构。
放置已分配的块：
当应用请求一个K字节的块时，分配器搜索空闲链表，并查找出足够大、可以放置所请求的空闲块的方式。一般有首次适配、下一次适配和最佳适配策略。
4、分配空闲块：
当查找出空闲块后决定分配这个块中多少空间给分配请求。
两个选择：
5、获得额外的对存储器
当分配器不能为请求块找到合适的空闲块时，通常会合并空闲块或者向内核请求额外的堆存储器。
6、合并空闲段块
假碎片：两个相邻的空闲块没有被合为一块。任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并。
7、带边界标记的合并
边界标记：通过在每个块的结尾处添加一个脚部作为一种边界标记，其中脚部就是头部的一个副本，这样分配器就可以通过检查前面一个块的脚部来判断前面一个块的起始位置和状态。
注意前面一个块的脚部总是位于当前块起始位置的一个字的距离处。
8、显式空闲链表：
通过将空闲块组织为某种形式的显式数据结构，即可以将实现这个数据结构的指针放在空闲块的主体里面。这样就可避免想隐式空闲链表那样仍需遍历已分配的块。
维护这种链表有后进先出和按地址顺序两种方式。
9、分离存储：
通过维护多个空闲链表的方式来管理堆，其中每个链表中的块有大致相等的大小，而不同的链表中的块的大小一般不同，通常按大小类来分。
垃圾收集器是一种动态存储分配器，它自动释放程序不再需要的已分配块，这些块被称为垃圾，自动回收堆存储的过程叫做垃圾收集。
垃圾收集器将存储器视作一张有向可达图，只有当存在一条从任意根节点出发并到达p的有向路径时，才说节点p是可达的，而不可达点就是垃圾。
有两个阶段：
相关函数：
ptr定义为typedef void *ptr
参考资料
原文：http://www.cnblogs.com/20135231hj/p/5042567.html