Ch 3 虚拟存储器
3.1 概述
虚拟存储器（Virtual Memory） 但基本思想是，对于一个程序来说，它的 code/data/stack 的总大小可以超过实际物理内存的大小。操作系统把当前使用的部分放到物理内存中，而把其他未使用的部分放到更下一级存储器，如 disk/flah 中。比如一个大小为 32 MB 的程序运行在物理内存只有 16 MB 的机器上，操作系统通过选择，决定各个时刻将程序中的一部分 16 MB（或更小）的内容放在物理内存中，而把其他内容放到硬盘中，并在需要的时候在物理内存和硬盘之间交换程序片段。
可以说，一个程序就是运行在虚拟存储器空间的，它的大小由处理器的位宽决定。如 32 位处理器地址范围是 即 4 GB 这个范围就是程序可以产生的地址范围，其中的某个地址就称为虚拟地址。和虚拟存储器对应的是物理存储器，它是现实中可以直接使用的存储器，其中的某个地址就称为物理地址。物理存储器的大小不能超过处理器的最大可寻址空间。
没有使用虚拟地址的系统，处理器输出的地址直接送到物理存储器。使用了虚拟地址，处理器输出虚拟地址，这个地址会经过内存管理单元（Memory Manage Unit, MMU） 进行地址转换。
使用虚拟存储器不仅便于程序运行，还可以给程序编写带来好处。直接使用物理存储器，如果需要同时运行多个程序，每个程序需要分配一块地址空间，这限制了程序的编写，而且不能使处理器随意执行程序。这对于应用领域比较单一的嵌入式系统是没问题的。对于扩展性要求高的复杂系统，需要虚拟存储器，这时每个程序总认为它占有处理器的所有地址空间，因此程序可以任意使用处理器的地址资源。编写程序时不需要考虑地址的限制，每个程序认为处理器中只有自己在运行，这些程序放到处理器中运行的时候，由操作系统负责调度，将物理存储器动态地分配各个程序，将每个程序的虚拟地址转化为相应的物理地址。
使用虚拟存储器不仅可以降低物理存储器的容量需求，还可以带来另外的好处，如保护和共享。通过操作系统动态地将每个程序的虚拟地址转化为物理地址，还可以实现程序的保护，即使两个程序都使用了同一个虚拟地址，它们也会对应到不同的物理地址，保证每个程序的内容不会被其他程序随便改写。而且通过这样的方式还可以实现程序简单共享，如操作系统内核提供了打印函数，第一个程序在地址 A 使用了 printf 函数，第二个程序在地址 B 使用了 printf 函数，操作系统在地址转换赌场罪，会将地址 A 和 B 都转换为相同的物理地址，这个物理地址就是 printf 函数在物理存储器中的实际地址，这样实现了程序的共享。虽然两个程序都使用了 printf 函数，但与不会使得 printf 函数占用物理存储器的两个地方。
3.2 地址转换
虚拟存储器最通用的方式是基于分页 page。虚拟地址空间的划分以页为单位，典型的页的大小为 4 KB，相应的物理地址空间也进行相同大小的划分，物理地址空间称为 frame（由于历史原因），和页大小相等。当程序开始运行时，会将当前需要的部分内容从硬盘中搬移到物理内存，每次搬移的单位就是一个页的大小。由于只有在需要的时候才将一个页的内容放到物理内存中，这种方式称为 demand page，它使处理器可以运行比物理内存大的程序。对于一个虚拟地址 VA 来说， 用来表示页内的位置，称为 page offset，VA 剩余部分用来表示哪个页，也称为 VPN Virtual Page Number。相应的，对于一个物理地址 PA 来说， 用来表示 frame 内的位置，称为 frame offset，而 PA 剩余的部分用来表示哪个 frame，也成为 PFN Physical Frame Number。由于页和 frame 的大小是一样的，所以从 VA 到 PA 的转化实际上也就是从 VPN 到 PFN 的转化，offset 不变。
例如，假设处理器是 16 位，它的虚拟地址范围是 ，共 64 KB，页的大小是 4 KB。因此 64 KB 的虚拟地址包含了 16 个页，即 16 个 VPN；而这个系统的物理内存只有 32 KB，包含 8 个 PFN。现在有一个程序，它的大小大于 32 KB，这个程序在执行的时候，不能一次性调入内存中，这个机器必须有一个可以存放这个程序的下级存储器，以保证程序在需要的时候可以被调用。如下图所示，一部分虚拟地址已经被映射到物理空间，如 VPN 0（地址范围 ）被映射为 PFN 2（地址范围 ），VPN 1（地址范围 ）被映射为 PFN 0（地址范围 ）等。（配图有误）
程序中使用的地址是虚拟地址，虚拟地址会被送到处理器中专门负责地址转换的部件，即 MMU，被转换为物理地址后，再去访问物理内存而得到真正的数据。下面以 load 指令为例，仅考虑取数据的过程，实际每条指令本身的地址也是虚拟地址。对虚拟地址到物理地址的转换，只对 VPN 操作，页内的偏移不进行转化。也即页是地址转换的最小单元，例如：
Load R2, 5[R1]; // 假设 R1 为 0
Load R2, 0[R1]; // 假设 R1 为 20500
Load R1, 0[R1]; // 假设 R1 为 32780第一条指令执行时，得到的取数据的虚拟地址是 ，地址 5 被送到 MMU，对于 page 0（范围 ），被映射到物理空间的 frame 2（范围 ），MMU 将地址转换为物理地址 8197，并在物理内存中取数据。
第二条指令，虚拟地址落在 Page 5（范围 ），和页起始地址有 20 个字节距离，映射到物理内存的 frame 3，物理地址为 。
第三条指令，虚拟地址落在 Page 8，而 Page 8 没有一个有效映射，即此时 Page 8 的内容没有存在物理内存中，而是在硬盘中，MMU 发现这个页没有被映射后，产生一个 Page Fault 异常给处理器，这时候处理器转到 Page Fault 对应的物理异常处理程序中（操作系统），它从物理内存的八个 Frame 寻找一个很少被使用的，假设选中了 frame 1，对应映射 Page 2，首先解除这两者的映射关系，此时虚拟地址 page 2 的地址范围被标记为没有映射，然后把需要的内容即 Page 8，从硬盘搬移到物理内存 frame 1 的空间，并标记这个映射关系。如果这个被替换的 frame 1 是脏 dirty 状态的，还需要将他的内容搬移到硬盘中，这里脏的概念和 cache 的一样，表示这个 frame 被修改过，被修改的数据还没来得及更新到硬盘中。处理完上述内容，就可以从异常处理中返回，此时返回到产生这个异常的指令，重新执行。
3.2.1 单级页表
访问硬盘的时间是以 ms 为单位的，这使得发生 Page Fault 异常处理需要很长时间，降低了处理器性能。因此为了减少 Page Fault 发生的频率，需要优化页在物理内存中的摆放。
如果允许一个页能够放到物理内存地任意一个 frame 中，这时候操作系统就可以在发生 Page Fault 的时候，将物理内存中任意一个页进行替换，这样，操作系统可以利用一些比较复杂地算法，将物理内存中哪些最近一段时间都没有使用的页进行替换，这样可以保证不会降一些当前很活跃地内容踢出物理内存。也就是说，灵活的替换算法可以减少 Page Fault 发生的概率。
这种在物理内存中任意的替换方法（类似全相联的 Cache）直接实现起来并不容易，所以在使用虚拟存储器的系统中，都是使用一张表格来存储从虚拟地址到物理地址（VPN 到 PFN）的关系，这个表格称为页表 Page Table PT，这个表格一般放在物理内存，使用虚拟地址来寻址，表格中被寻址到的内容就是这个虚拟地址对应的物理地址。每个程序都有自己的页表, 用来将这个程序中的虚拟地址映射到物理内存中的某个地址。为了指示一个程序页表在物理内存中的起始地址，处理器中一般会包括一个寄存器，用来存放当前运行的程序的页表在物理内存中的起始地址，这个寄存器称为页表寄存器 Page Table Register PTR，每次操作系统将一个程序调入物理内存中执行的时候，就会将寄存器 PTR 设置好。
下图表示了如何使用 PTR 从物理内存中定位到一个页表，并用虚拟地址来寻址页表，从而找到对应的物理地址的过程。使用 PTR 和虚拟地址共同来寻址页表，就相当于使用它们两个共同组成一个地址，使用这个地址来寻址物理内存。图中假设每个页表的大小是 4 KB，使用 PTR 和虚拟地址共同来寻址页表，找到对应的表项 entry。当这个表项对应的有效位是 1 时，就表示这个虚拟地址所在的 4 KB 空间已经被操作系统映射到了物理内存中，可以直接从物理内存中找到这个虚拟地址对应的数据，这时候访问当前页任意的地址，就是访问物理内存中被映射的那个 4 KB 的空间。相反，如果有效位是 0，则表示这个虚拟地址对应 4 KB 空间还没有被操作系统映射到物理内存中（为了节省物理内存的使用，操作系统只会把当前那些被使用的页映射到物理内存中），则此时就产生了 Page Fault 类型的异常，需要操作系统从更下一级的存储器中将这个页对应的 4 KB 内容搬移到物理内存中。
图 3.4 中，使用 32 位虚拟地址，页表在物理内存中的起始地址是用 PTR 来指示的。虚拟地址的寻址空间是 字节，即 4 GB；物理地址寻址空间是 字节，也就是 1 GB，就像是目前使用的 32 位 PC，虽然最大支持 4 GB 内存，但是很多时候，计算机实际安装的内存可能只有 1 GB 甚至 512 MB，这对应实际的物理地址的寻址空间。在页表中的一个表项 entry 能够映射 4 KB 大小，为了映射整个 4 GB 空间，需要的表项个数是 ，即需要 20 位来寻址，也就是虚拟地址中除了 Page Offset 之外的部分。自然地，32 位虚拟地址来寻址 4 GB 的空间，人为的将地址分为两个部分，低 12 位用来寻址一个页的内容，高 20 位用来寻址哪个页。真正寻址页表的不是虚拟地址的所有位数，而是 VPN，从页表中找到的内容也不是整个物理地址，而是 PFN。从图中可以看出，页表中的每个表项似乎只需要 18 位 PFN 和 1 位有效位就够了，实际上页表放在物理内存中，二物理内存中的数据位宽都是 32 位，导致页表中每个表项的大小也是 32 位，剩余的位用来表示一些其他的信息，如每个页的属性信息（是否可读可写等），这样页表的大小就是 ，所有，一个程序在运行时，需要在物理内存中划分出 4 MB 的连续空间来存储它的页表。
需要注意，页表的结构不同于 Cache，页表中包含了所有 VPN 的映射关系，所以可以直接使用 VPN 对页表进行寻址，而不需要使用 Tag。
在处理器中，一个程序对应的页表，连同 PC 和寄存器一起，组成了这个程序的状态，如果当前程序执行时，另一个程序需要访问这个处理器，就需要将当前的程序状态进行保存，这样在一段时间后将这个程序恢复，从而这个程序可以继续执行。操作系统中，将这样的程序叫做进程 process，当一个进程被处理器执行的时候，称这个进程是活跃 active 的，否则称为不活跃 inactive 的。操作系统通过将一个进程的状态加载到处理器中，就可以使这个进程进入活跃的的状态。可以说，进程是一个动态的概念，当一个程序只是放在硬盘中，并没有被处理器执行的时候，它只是一个由一条条指令组成的静态文件，只有当这个程序被处理器执行时，例如用户打开了一个程序，此时才有了进程，需要操作系统为其分配物理内存中的空间，创建页表和堆栈等，这时候一个静态的程序就变为了动态的进程，这个进程可能是一个，也可能是多个，这取决于程序本身。当然，进程是有生命期的，一旦用户关闭了这个程序，进程也就不存在了，它所占据的物理内存也会被释放掉。
一个进程的页表指定了它能够在物理内存中访问的地址空间，这个页表当然也是位于物理内存中的，在一个进程进行状态保存的时候，其实并不需要保存整个的页表，只需要将这个页表对应的 PTR 进行保存即可。因为每个进程都拥有有全部的虚拟存储器空间，因此不同的进程肯定会存在相同的虚拟地址，操作系统需要负责这些不同的进程分配到物理内存中不同的地方，并将这些映射 (mapping) 信息更新到页表中 (使用 store 指令就可以完成这个任务)，这样不同的进程使用的物理内存就不会产生冲突了。
图 3.5 表示了在处理器中存在三个进程的情况，每个进程都都有自己的页表，虽然在三个进程中都存在相同的虚拟地址 VA 1，但是通过每个进程自己的页表，将它们的 VA 1 映射为物理内存中不同的物理地址。同理，虽然三个进程中存在不同的虚拟地址 VA2、VA3 和 VA4，但是它们都是访问同一个函数，因此通过每个进程的页表将它们都映射到了物理内存中的同一个地址，通过这种方式，实现不同进程之间的保护和共享。
但是在之前说过，为了节省硅片面积，都会把页表放到物理内存中，这样要得到一个虚拟地址对应的数据，需要访问两次物理内存。第一次访问物理内存中的页表，得到对应的物理地址；第二次使用这个物理地址来访问物理内存，这样才能得到需要的数据，如图 3.6 表示了这个过程。
按照图 3.6 的这种访问过程，要执行一条 load 指令而得到数据，需要的时间肯定会很长，毕竟物理内存的访问速度和处理器的速度相比是很慢的。可以说，图 3.6 的这种访问数据的方法没有错误，但是效率不高，现实当中的处理器都会使用 TLB 和 Cache 来加快这个过程，这些内容将在后文介绍。
在前面已经计算过，如果一个 32 位处理器中，页的大小是 4KB，并且页表中每个表项的大小是 4 字节的这种典型结构，在页表中需要的表项个数是 ，所以页表的大小是 。这也就是说，对于在处理器中运行的每个进程，都需要在物理内存中为其分配连续的 4MB 空间来存储它的页表。当然，如果处理器中只运行一个进程的话，那么看起来问题不大，但是，如果一个处理器中同时运行着上百个进程时，每个进程都要占用 4MB 的物理内存空间来存储页表，那显然就不可能了。而且，对于 64 位的处理器来说，仍旧有可能采用大小为 4KB 的页，可以计算出此时页表需要的空间是非常巨大的的，大小是 ，这显然已经不可能了。
事实上，一个程序很难用完整个 4GB 的虚拟存储器空间，大部分程序只是用了很少一部分，这就造成了页表中大部分内容其实都是空的，并没有波实际地使用，这样整个页表的利用效率其实是很低的。可以采用很多方法来减少一个进程的页表对于存储空间的需求，最常用的方法是多级页表 (Hierarchical Page Table)，这种方法可以减少页表对于物理存储空间的占用，而且非常容易使用硬件来实现，与之对应的，本节所讲述的页表表就称为单级页表 (Single PageTable)，也被称为线性页表 (LinearPage Table)。
3.2.2 多级页表
在多级页表 (Hierarchical Page Table) 的设计中，将 3.2.1 节介绍的一个 4MB 的线性页表划分为若干个更小的页表，称它们为子页表，处理器在执行进程的时候，不需要一下子把整个线性页表都放入物理内存中，而是根据需求逐步地放入这些子页表。而且，这些子页表不再需要占用连续的物理内存空间了，也就是说，两个相邻的子页表可以放在物理内存中不连续的位置，这样也提高了物理内存的利用效率。但是，由于所有的子页表是不连续地放在物理内存中，所以仍旧需要一个表格，来记录每个子页表在物理内存中存储的位置，称这个表格为第一级页表 (LevellPageTable)，而那些子页表则为第二级页表 (Level2 Page Table)，如图 3.7 所示。
这样，要得到一个虚拟地址对应的数据，首先需要访问第一级页表，得到这个虚拟地址所属的第二级页表的基地址，然后再去第二级页表中才可以得到这个虚拟地址对应的物理地址，这时候就可以在物理内存中取出相应的数据了。举例来说，对于一个 32 位虚拟地址、页大小为 4KB 的系统来说，如果采用线性页表，则页表中的表项个数是 ，将其分为 1024 () 等份，每个等份就是一个第二级页表，共有 1024 个第二级页表，对应着第一级页表中的 1024 个表项。也就是说，第一级页表需要 10 位地址进行寻址。每个二级页表中，表项的个数是 220/210=210 个, 也需要 10 位地址才能寻址第二级页表，如图 3.8 所示为上述过程的示意图。