虚拟存储（CSAPP Chapter 9）

虚拟存储的动机主要有两个：多个程序之间高效安全地共享内存，例如云计算的多个虚拟机；消除小而受限的主存容量对程序设计造成的影响。如果希望多个虚拟机共享内存，必须确保他们各自的程序只读写分配给它的那一部分主存。而反过来说，主存只需要存放一个程序的活跃部分，因而局部性原理也是适用于虚拟存储的。

所以，本质上虚拟存储是将程序地址空间转换为物理地址。

页：虚拟存储块，其失效被称为缺页失效。

虚拟内存通过重定位简化了执行时程序的载入，例如我们可以用重定位来把程序的虚拟地址映射到主存的不同物理位置。此外，所有的虚拟存储系统都将程序重定位为一组固定大小的块，这样不需要找连续内存块来放置程序。所以，操作系统只要在主存找到足够多的页就行了。

1. 物理和虚拟寻址

计算机的主存是一个由 M 个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址，这很好理解。如果使用物理寻址的话，加载指令应当是这样实现的：它生成一个有效物理地址，并通过内存总线传递给主存，主存从那里取出 4 开始的 4 字节字，并返回给 CPU，CPU 将其放在一个寄存器里。

但现代处理器用的是虚拟寻址：CPU 生成一个虚拟地址来访问主存，这个虚拟地址通过地址翻译（硬件/操作系统）来翻译成物理地址。CPU 芯片上叫做内存管理单元（MMU）的硬件利用存放在主存中的查询表来动态翻译虚拟地址，而这个表是操作系统管理的。

2. 地址空间

CPU 从一个有 \(N=2^n\) 个地址的地址空间中生成虚拟地址，这就是虚拟地址空间（n 位）。另外，一个系统也有一个物理地址空间，对应于系统中物理内存的 M 个字节（M 不一定是 2 的幂）

3. 虚拟内存作为缓存的工具

概念上而言，虚拟内存被组织为一个磁盘上的大数组，每个字节都有一个虚拟地址作为索引，而磁盘上数组的内容被缓存在主存中。VM 系统通过将虚拟内存分割为虚拟页（大小固定的块）来解决磁盘和主存传输的问题，每个虚拟页的大小为 \(P=2^p\)。类似地，物理内存也可以做类似的分割。

任何时候，虚拟页面的集合都可以分成三个不相交的子集：

未分配的：还没分配，没有数据与之关联，自然不占用磁盘空间
缓存的：被缓存在物理内存中的已分配页
未缓存的

3.1 DRAM 缓存的组织结构

存储结构中，DRAM 非常慢，缓存不命中代价十分昂贵，这是因为其不命中需要用磁盘来服务。因而，虚拟页往往很大（4 kB to 2 MB）。另外，DRAM 缓存是全相联的，即任何虚拟页可以放在任何物理页中。同样，我们也需要非常复杂的替换算法。最后，缓存的写策略是写回而非直写。

3.2 页表

虚拟内存系统必须有方法来判断某个虚拟页是否被缓存在 DRAM 中的某个地方，以及在哪个物理页。如果不命中，还要思考在磁盘上的哪个位置，并且牺牲物理内存中的一个位置。这是由软硬件共同提供的，包括操作系统软件，地址翻译硬件和物理内存中的页表。

页表大概长这样，由一个有效位和一个 \(n\) 位地址字段组成。虚拟地址空间的每个页都在给定偏移量处有一个页表条目。有效位表示是否有被在 DRAM 中缓存，如果有效位为 1，那地址字段就代表 DRAM 中相应物理页码的起始位置。如果没有有效位，那么我们可以用空地址来表示 VM 还没有分配，否则就指向该虚拟页在磁盘上的起始地址。