第九章 虚拟存储器

知识点

• 虚拟存储器是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。通过一个很清晰的机制，虚拟存储器提供了三个重要的能力：

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

9.1 物理和虚拟寻址

1. 物理寻址

• 计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址PA。第一个字节的地址为0，接下来的字节的地址为1，再下一个为2，依此类推。
• 给定这种简单的结构，CPU访问存储器的最自然的方式就是使用物理地址，我们把这种方式称为物理寻址。

2. 虚拟寻址

• 使用虚拟寻址时，CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译。
• CPU芯片上叫做存储器管理单元的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容是由操作系统管理。

9.2 地址空间

• 一个非整数地址的有序集合：{0,1,2,...}。
• 如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间。
• 在一个带虚拟存储器的系统中，CPU从一个有N = 2 ^ n个地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间：{0,1,2,3,...,N-1}。
• 一个地址空间的大小是由表示最大地址所需要的倍数来描述的。
• 一个系统还有一个物理地址空间，它与系统中物理存储器的M字节相对应：{0,1,2,...M-1}。
• 地址空间清楚地区分了数据对象(字节)和它们的属性(地址)。
  虚拟存储器的基本思想：允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。

9.3 虚拟存储器作为缓存的工具

• 虚拟存储器被组织为一个由存放在磁盘上N个连续的字节大小的单元组成的数组。每个字节都有一个唯一的虚拟地址，这个唯一的虚拟地址是作为到数组的索引的。
• 每个虚拟页的大小为P = 2 ^ n字节。
• 物理存储器被分割为物理页(PP)，大小也为P字节(物理页也称为页帧)。

• 在任意时刻，虚拟页面的集合都分为三个不相交的子集：

  未分配的：VM系统还未分配(或者创建)的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。(没有调用malloc或者mmap的)
  缓存的：当前缓存在物理存储中的已分配页。(已经调用malloc和mmap的，在程序中正在引用的)
  未缓存的：没有缓存在物理存储器中的已分配页。(已经调用malloc和mmap的，在程序中还没有被引用的)

1. 页表

• 页表就是一个页表条目的数组。
  

• 页表将虚拟地址映射为物理地址，每个页表项(PTE)，有一个有效位，标识该地址是否在内存的缓存中，还有物理页号或磁盘地址。

• 页命中，收到虚拟地址时，根据该虚拟地址查找页表，如果有效位有效，则说明在内存中，则利用该地址构造物理地址。
  

• 缺页，如果地址不再页表中，则牺牲一条记录，加载进新的地址映射和内容。
  

9.4 虚拟存储器作为存储器管理的工具

• 存储器映射：将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，一旦一个虚拟页面被初始化了，他就在一个由内核维护的专门的交换文件之间换来换去。
• 传统的文件系统，这样通过存储器的映射，高效的把数据加载到存储器中。
• 简化链接
• 简化加载
• 简化共享
• 简化存储器分配

9.5 虚拟存储器作为存储器保护的工具

9.6 地址翻译

• 得到虚拟地址之后，分为两部分，前部分虚拟页号，后部分偏移地址，根据虚拟页号在页表中找到物理页号，偏移地址不变，直接物理页号和偏移地址构成物理地址。该模块位于cpu内。
• 每次翻译虚拟地址时，都需要到内存访问页表，为了加快速度，在cpu内直接再弄一个缓存表，缓存TBE的内容，称为TLB。
• 翻译整个过程：地址翻译单元从虚拟地址中拿到虚拟页号，检查TLB，看是否存在TPE的缓存，如果有返回，若没有，查询主存的页表，页表可以实现多级，拿到物理页号，如没有产生中断，调入地址，内核重新发送解析指令，最终返回物理地址；得到物理地址之后，将物理地址发给L1缓存，L1没有L2、L3、主存。

9.7 Linux虚拟存储器系统

• Linux为每个进程维持了一个单独的虚拟地址空间。
• 内核虚拟存储器包含内核中的代码和数据结构。
• 内核虚拟存储器的某些区域被映射到所有进程共享的物理页面。
  

1. Linux虚拟存储器区域

• 每个存在的虚拟页存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。
• 区域允许虚拟地址空间有间隙。

• 内核不用记录那些不存在的虚拟页，而这样的页也不占用存储器、磁盘或者内核本身的任何额外资源。
  

• 一个具体区域结构包含下面的字段：

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

9.8 存储器映射

• Linux通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，这个过程称为存储器映射。

• 虚拟存储器区域可以映射到两种类型的对象的一种：

  Unix文件上的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分。

  匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。

• 无论在哪种情况下，一旦一个虚拟页面被初始化了， 它就在一个由内核维护的专门的交换文件之间换来换去。

• 在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

1.再看共享对象

• 一个对象可以被映射到虚拟存储的一个区域，要么作为共享对象，要么作为私有对象。
• 对一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。

• 一个映射到共享对象的虚拟存储器区域叫做共享区域。类似地，也有私有区域。

• 共享对象的关键点在于即使对象被映射到了多个共享区域，物理存储器也只需要存放共享对象的一个拷贝。
  一个共享对象物理页面不一定是连续的。
  

• 私有对象是使用写时拷贝巧妙技术被映射到虚拟存储器中的。

• 对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时拷贝。
  

2. 再看fork函数

• 当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。
• 当fork在新进程中返回时，新进程现在的虚拟存储器刚好和调用fork时存在的虚拟存储器相同。当这两个进程中的任一个后来进行写操作时，写时拷贝机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

3. 再看execve函数

• execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out程序有效地替代了当前程序。

• 加载并运行a.out需要以下几个步骤：

  删除已存在的用户区域。删除当前进程虚拟地址用户部分中的已存在的区域结构。
  映射私有区域。为新程序的文本、数据、bss和栈区域创建新的区域结构。
  映射共享区域。如果a.out程序与共享对象(或目标)链接，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
  设置程序计数器(PC)。execve做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向文本区域的入口点。

• 下一次调度这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。
  

4. 使用mmap函数的用户级存储器映射

• mmap函数要求内核创建一个新的虚拟存储器区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片映射到这个新区域。
• 连续的对象片大小为length字节，从距文件开始处偏移量为offset字节的地方开始。start地址仅仅是一个暗示，通常被定义为NULL。

9.9 动态存储分配

• 一个动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆。
• 堆是一个请求二进制0的区域；对于每个进程，内核维护着一个变量brk，它指向堆的顶部。
• 分配器将堆视为一组不同大小的块的集合来维护。
• 每个块就是一个连续的虚拟存储器组块，要么是已分配的，要么是未分配的。
• 显式分配器：如通过malloc,free或C++中通过new,delete来分配和释放一个块。
• 隐式分配器：也叫做垃圾收集器。自动释放未使用的已分配的块的过程叫做垃圾回收。
• malloc不初始化它返回的存储器，calloc是一个基于malloc的包装函数，它将分配的存储器初始化为0。
• 想要改变一个以前已分配的块的大小，可以使用realloc函数。
• 分配器必须对齐块，使得它们可以保存任何类型的数据对象。
• 在大多数系统中，以8字节边界对齐。
• 不修改已分配的块：分配器只能操作或者改变空闲块。一旦被分配，就不允许修改或者移动它。

1. 碎片（fragmentation）

• 外部碎片：在一个已分配块比有效载荷在时发生的。

• 外部碎片：当空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。

  2. 显式空间链表

  

• 放置分配的块的策略有：

  首次适配（first fit），下一次适配（next fit），和最佳适配（best fit）。

• 如果空闲块已经最大程度的合并，而仍然不能生成一个足够大的块，来满足要求的话，分配器就会向内核请求额外的堆存储器，要么是通过调用nmap，要么是通过调用sbrk函数;

• 分配器都会将额外的存储器转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

• 减少分配时间的方法，称为分离存储，维护多个空闲链表，其中每个链表中的块有大致相等的大小。

9.10 垃圾收集

• 垃圾收集器将存储器视为一张有向可达图。
  

• Mark%Sweep垃圾收集器由标记（mark）阶段和清除（sweep）阶段组成。标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个被标记的已分配块。典型地，块头部中空闲的低位中的一位来表示这个块是否被标记了。

遇到问题

• 虚拟存储器的基本思想：允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间
• 我理解的是地址不是连续的。

总结体会

这章的内容是讲虚拟存储器，和操作系统最近学的内容大致一样，这本书上讲解的非常详细，从概念的定义解读到函数使用实现，都使我更加理解了指令访问内存的过程。最近这两章的内容对操作系统的学习来讲是一个非常大的补充。这本书在今后的学习过程中仍然值得作为一个学习的重要读物，对我的学习帮助是很大的。