第九章

虚拟存储器

2014/02/12 14:43

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

2，虚拟寻址（virtual addressing）。

使用虚拟寻址时，CPU通过生成一个虚拟地址（Virtual Address,VA）来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译（address translation）。就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。CPU芯片上叫做存储器管理单元（Memory Management Unit,MMU）的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容是由操作系统管理的。

3，地址空间（address space）是一个非负整数地址的有序集合：｛0，1，2，...｝。如果地址空间中的整数是连续的，那么我们就说它是一个线性地址空间（linear address space）.在一个带虚拟存储器的系统中，CPU从一个有个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间（virtual address space）：｛0，1，2，...，N-1｝。一个地址空间的大小是由表示最大地址所需要的位数来描述的。例如，一个包含个地址的虚拟地址空间就叫做一个n为地址空间。现代系统典型地支持32位或者64位虚拟地址空间。

    一个系统还有一个物理地址空间（physical address space），它与系统中物理存储器的M个字节相对应：｛0，1，2，...，M-1｝,M不要求是2的幂，但是为了简化讨论，我们假设。
4，主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

5，概念上而言，虚拟存储器（VM）被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每个字节都有一个唯一的虚拟地址，这个唯一的虚拟地址是作为到数组的索引的。磁盘上数组的内容被缓存在主存中。和存储器层次结构中其他缓存一样，磁盘上的数据被分割成块，这些块作为磁盘和主存之间的传输单元。VM系统通过将虚拟存储器分割为称为虚拟页（Virtual Page,VP）的大小固定块来处理这个问题。每个虚拟页的大小为字节。类似的，物理存储器被分割为物理页（Physical Page,PP）,大小也为P字节（物理页也称为页帧（page frame））.

2014/02/13 18:54

6，页表（page table）

    页表就是一个页表条目（Page Table Entry,PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。我们假设每个PTE是由一个有效位（valid bit）和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在DRAM中。如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么一个空地址表示这个虚拟页还未被分配。否则，这个就指向该虚拟页在磁盘上的起始地址。

    

    上图示例展示了一个有8个虚拟页和4个物理页的系统的页表。四个虚拟页（VP1,VP2,VP4和VP7）当前被缓存在DRAM中。两个页（VP0和VP5）还未被分配，而剩下的页（VP3和VP6）已经被分配了，但是当前还未被缓存。（上图中有一个要点要注意，因为DRAM缓存是全相连的，任意物理页都可以包含任意虚拟页。）

7，在虚拟存储器的习惯说法中，块被称为页。在磁盘和存储器之间传送页的活动叫做交换（swapping）或者页面调度（paging）。页从磁盘换入DRAM和从DRAM换出磁盘。一直等待，直到最后时刻，也就是当有不命中发生时，才换入页面的这种策略称为按需页面调度（demand paging）.

8，在虚拟存储器的习惯说法中，DRAM缓存不命中称为缺页（page fault）。

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

    在这个示例中，进程i的页表将VP1映射到PP2，VP2映射到PP7.相似的，进程j的页表将VP1映射到PP7，VP2映射到PP10.注意，多个虚拟页面可以映射到同一个共享物理页面上。

2014/02/14 17:40

10，将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作存储器映射（memory）。

2014/02/15 10:07

11，地址翻译是一个N元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）中的元素之间的映射，

2014/02/25 13:28

12，fork函数：

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

13，execve函数：

    假设运行在当前进程中的程序执行了如下的调用：

    execve("a.out",NULL,NULL);

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

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

    1）删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。

    2）映射私有区域。为新程序的文本，数据，bss和栈区域创建新的区域结构。所有这些新的区域都是私有的，写时拷贝的。文本和数据区域被映    

    射为a.out文件中的文本和数据。bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。栈和堆区域也是请求二进制零的，初始长   

    度为零。

    3）设置共享区域。如果a.out程序与共享对象（或目标）链接，比如标准C库libc.so，那么这些对象都是动态连接到这个程序的，然后再映射到   

    用户虚拟地址空间中的共享区域内。

    4）设置程序计数器（PC）。execve做的最后一件事情就是设置当前进程上下文中的程序计数器，十指指向文本区域的入口点。

14，动态存储器分配器（dynamic memory allocator）维护着一个进程的虚拟存储器区域，称为堆（heap）。系统之间细节不同，但是不失通用性，我们假设堆是一个请求二进制零的区域，它紧接在未初始化的bss区域后开始，并向上生长（向更高的地址）。对于每个进程，内核维护着一个变量brk，它指向堆的顶部。

15，程序使用动态存储器分配的最重要的原因是经常直到程序实际运行时，它们才知道某些数据结构的大小。

2014/02/26 11:03

16，首次适配（first fit）：从头开始搜索空闲链表，选择第一个合适的空闲块。

    下一次适配（next fit）：和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。

    最佳适配（best fit）：查询每个空闲块，选择适合所需请求大小的最小空闲块。

17，边界标记（boundary tag）：在每个块的结尾处添加一个脚部（footer,边界标记），其中脚部就是头部的一个副本。

    边界标记的优化：如果我们把前面块的已分配/空闲位存放在当前块中多出来的低位中，那么以分配的块就不需要脚部了。但是，空闲块仍然需要脚部。  

18，垃圾收集器（garbage collector）是一种动态存储分配器，它自动释放程序不再需要的已分配块。这些块称为垃圾（garbage）。自动回收堆存储器的过程叫做垃圾收集（garbage collection）。在一个支持垃圾收集的系统中，应用显示分配堆块，但是从不显示地释放它们。

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