超标量处理器设计 姚永斌 第3章 虚拟存储器 --3.1~3.2 小节摘录

3.1 概述

在此之前都认为处理器送出的取指令和取数据的地址是实际的物理地址，而现代的高性能处理器都是支持虚拟地址的，为什么？

随着图形界面的兴起，以及用户需求的不断增大，应用程序的规模也越来越大，于是一个难题出现了：应用程序太大以至于物理内存以及无法容纳下这样的程序了，于是通常的做法是人工手动将程序分割成许多片段，尽管片段在物理内存中的交换是操作系统完成的，但是分割程序是人工完成，耗时许久。于是虚拟存储器出现，它的基本思想是对于一个程序来说，它的程序code、数据data和堆栈stack的总大小可以超过实际物理内存的大小，操作系统把当前使用的部分放到物理内存中，而把其他未使用的内容放到更下一级存储器，如硬盘disk或闪存flash，而且运行之前也不要程序员对程序进行分割。

一个程序是运行在虚拟存储器的，它的大小由处理器的位数决定的，例如一个32位处理器，其地址范围0~0xFFFFFFFF，也就是4GB；而对于64位处理器来说，其虚拟地址范围就是0~0xFFFFFFFFFFFFFFFF，这个范围就是程序能够产生的地址范围，其中的某一地址就称为虚拟地址。现实世界中能够直接使用的存储器，其中的某一个地址就是物理地址。物理存储器的大小不能超过处理器最大可以寻址的空间。

在没有使用虚拟地址的系统中，处理器输出的地址会直接送到物理存储器中。而如果使用了虚拟地址，则处理器输出的地址就是虚拟地址了，这个地址不会直接送到物理存储器中，而是需要先进行地址转换，因为虚拟地址是没有办法直接寻址到物理存储器的，负责地址转换的部件一般称为内存管理单元Memory Manage Unit，MMU。

在直接使用物理存储器的处理器中，如果要同时运行多个程序，就需要为每个程序都分配一块地址空间，每个程序都需要在这个地址空间内运行，这样极大地限制了程序的编写，而且不能够使处理器随便地运行程序，这样的限制对于应用程序比较专一的嵌入式系统来说还好。

在使用虚拟存储器之后，在编写程序的时候，不需要考虑地址的限制，每个程序都认为处理器只有自己在运行，当这些程序真正放到处理器中运行的时候，由操作系统负责调度，将物理存储器动态地分配给各个程序，将每个程序的虚拟地址转换为相应的物理地址，使程序能够正常地运行。

通过操作系统动态地将每个程序的虚拟地址转化为物理地址，还可以实现程序的保护，即使两个程序都使用了同一个虚拟地址，它们也会对应的不同的物理地址，因此可以保证每个程序的内容不会被其他的程序随便改写，而且还可以实现程序间的共享。

使用存储器不仅可以降低物理存储器的容量需求，它还可以带来另外的好处，如保护protect和共享share。

3.2 地址转换

虚拟存储器从最开始出现一直到现在，有很多实现的方式，本节介绍最通用的方式--基于分页page虚拟存储器。虚拟地址空间的划分以页为单位，典型的页大小为4KB，相应的物理地址空间也进行同样大小的划分，由于历史的原因，在物理地址空间中不叫做页，而称为frame，它的页的大小必须相等。

由于只有在需要的时候才将一个页的内容放到物理内存中，这种方式就称为demand page，它使处理器可以运行比物理内存更大的程序。对于一个虚拟地址VA来说，VA[11:0]用来表示页内的位置，称为page offset，VA剩余部分用来表示那个页，称为VAN（Virtual Page Number）。相应的物理地址PA来说，PA[11:0]用来表示frame内的位置，称为frame offset，剩余的PA部分用来表示PFN，由于页和frame的大小是一样的，所以从VA到PA的转换实际也是VPN到PFN的转换。

物理内存并不知道MMU做了什么映射，它只看到一个物理地址进行操作的任务。

MMU发现某页没有被映射之后，就产生一个Page Fault的异常送给处理器，处理器转为Page Fault对应的异常处理器处理这个事情。它必须从物理内存的某个frame找到一个当前很少使用的，假设选中了frame1，它和page2有着映射关系，所以首先将frame1和page2接触映射关系，此时虚拟地址空间中的page2的地址范围被标记为没有映射状态，然后把需要的内容，例如page8，从硬盘搬移到物理内存frame1，并将page8标记为映射到frame1，如果这个替换的frame1是drity，还需要现将它的内容搬移到硬盘中。

3.2.1 单级页表

对于处理器来说，当它需要的页page不在物理内容使，就发生Page Fault类型的异常，需要访问更下一级的存储器，如硬盘。而硬盘的访问时间一般是以ms为单位，严重降低处理器性能，因此应尽量减少Page Fault发生的频率，这就需要优化页在物理内存中摆放。

如果允许一个页能够放在物理内存中的任意一个frame中，这时候操作系统就可以在发生Page Fault的时候，将物理内存中任意一个页进行替换，操作系统可以利用一些复杂算法，将最近最少使用页进行替换，比较灵活的替换算法能够减少Page Fault发生的频率。

但是这种在物理内存中任意的替换方式(类似于全相连的Cache)直接实现起来并不容易，所以在使用虚拟存储器的系统中，都是使用一张表格来存储从虚拟地址到物理地址的对应关系，这个表格称为页表Page Table。因为表格耗费不菲的硬件资源，一般都是放在物理内存中，而非寄存器中，使用虚拟地址来寻址，表格中被寻址到的内容就是这个虚拟地址对应的物理地址。

每个程序都有自己的页表，用来将这个程序中虚拟地址映射到对应的物理地址，为了指示一个程序的页表在物理内存中的位置，在处理器中一般都会包括一个寄存器，用来存放当前运行程序的页表在物理内存中的起始地址，这个寄存器被称为页表寄存器Page Table registerr，PTR。上面的这种机制可以工作的前提是页表位于物理内存中一片连续的地址空间。

仍然假设每个页的大小为4KB，使用PTR和虚拟地址共同来寻找页表，找到对应的表项entry，当这个表项对应的valid被设为1，就表示这个虚拟地址所在的4KB空间已经被操作系统映射到物理内存中，可以直接从物理内存中找到虚拟地址对应的数据。

 若使用32位虚拟地址，页表在物理内存中使用PTR来指示的。虚拟地址的寻址空间是2^32字节，也就是4GB；物理空间寻址2^30字节，也就是1GB。计算机上实际安装的内存可能只有1GB，甚至是512MB。

为了能够 映射整个4GB的空间，需要的表项数目应该是4GB/4KB=1M，也就是2^20，因此需要20位来寻址，也就是虚拟地址中除了Page Offset之外的其他部分。这个其实是很自然的，因为32位的虚拟地址能够寻址4GB的空间，将其人为的分为两部分，低12位用来寻址一个业内的内容，高20位用来寻址那个页。也就说说，真正寻址的其实不是虚拟地址的所有位数，而只是VPN就可以了，从页表中找到的内容也不是整个屋里地址，而只是PFN。则页表中的每个表项似乎只需要18位的PFN和1位的有效位，也就是19位就够了。

实际上页表是放置在物理内存中，而物理内存中的数据位宽都是32位，所以导致页表中的每个表项的大小也是32位，剩余的位用来表示一些其他的信息，如每个页的属性信息(是否可读或可写)，这样每个页表的大小是4B*1M=4MB。按目前讲述，一个程序在运行的时候，需要在物理内存中划分4MB的连续空间来存储它的页表，然后才能够正常运行这个程序。

需要注意的是，页表的结构不同于Cache，在页表中包括了所有VPN的映射关系，所有可以直接使用VPN对页表进行寻址，而不要使用Tag。

在处理器中，一个程序对应的页表，连同PC和通用寄存器一起，组成了这个程序的状态，如果在当前程序执行的时候，想要另外一个程序使用这个处理器，就需要将当前程序的状态进行保存。进程的创建需要操作系统为期分配物理内存中的空间，创建页表和堆栈等。

一个进程的页表指定了它能够在物理内存中访问的地址空间，这个页表当然也是位于物理内存中，在一个进程进行状态保护的时候，其实并不需要保存整个页表，只需要将这个页表的PTR进行保存即可。因为每个进程都拥有全部的虚拟地址空间，因此不同的进程肯定会存在相同的虚拟地址，操作系统需要负责将这些不同的进程分配到物理内存中的不同的地方，并将这些映射信息更新到页表(使用store指令即可完成这个任务)，这样不同的进程使用物理内存就不会发生冲突了。

虽然三个进程中都存在相同的虚拟地址VA1，但是通过每个进程自己的页表，将它们的VA1映射为物理内存中不同的物理地址。同理，虽然三个进程存在不同的虚拟地址VA2，VA3和VA4，但是它们都是访问同一个函数，因此通过每个进程的页表将它们都映射到了物理内存中的同一个地址，通过这种方式，实现不同进程之间的保护和共享。

 为了节省硅片面积，都会把页表放到物理内存中，这样要得到一个虚拟地址对应的数据，需要访问两次物理内存，一次访问物理内存中的页表，得到相应的物理地址；第二次使用这个物理地址来访问物理内存，才得到相应的数据。这种访问数据的方法并没有错误，但是效率不高，现实当中的处理器都会使用TLB和Cache来加快这个过程。

如果处理器中只运行一个进程的话，看起来问题不大，但是如果一个处理器同时运行上百个进程，每个进程占用4MB的物理空间来存储页表，那显然就不可能了。

事实上，一个程序很难使用完整个4GB的存储器空间，大部分程序只是占用了很少的一部分，这就造成了页表中大部分内存其实都是空的，并没有被实际使用，这样整个页表的利用效率其实是很低的。

可以采用很多方法来减少一个进程的页表对于存储空间的需求，最常见的方法是多级页表Hierarchical Page Table，这种方法可以减少页表对于存储空间的占用，而且非常容易使用硬件来实现。之前所讲述的页表为单级页表，也被称为线性页表。

3.2.2 多级页表

介绍一个4MB的线性页表划分为若干个更小的页表，称它们为子页表，处理器在执行进程的时候，不需要一下子把整个线性页表都放入物理内存中，而是根据需求逐步地放入这些子页表。而且，这些子页表不再需要占用连续的物理内存空间了。也就是说，相邻的子页表可以放在物理内存中不连续的位置，这样也提高了物理内存的利用效率。但是，由于所有的子页表是不连续地放在物理内存中，所以依旧需要一个表格，来记录每个子页表在物理内存中存储的位置，称这个表格为第一级页表Level1 Page Table，而那些子页表称为第二集页表Level2 Page Table。

注意，这样要得到一个虚拟地址对应的数据，首先访问第一级页表，得到第二级页表的基地址，然后再去第二级页表才可以得到这个虚拟地址对应的物理地址，然后就可以在物理内存中取出相应的数据了。

对于一个32位虚拟地址、页大小位4KB的系统来说，如果采用线性页表，则页表中表项个数为2^20，将其等分为2^10等份，每个等份就是一个第二级页表，共有1024个第二级页表，对应着第一级页表的1024个表项。也就是说，第一级页表共需要10为地址来进行寻址。每个二级页表中个数也是1024，也需要10位地址来寻址。

一个页表中的表项简称为PTE，当操作系统创建一个进程时，就在物理内存中为这个进程找到一个连续的4KB空间，存在这个进程的第一级页表，并且将第一级页表在物理内存中起始地址放到PTR寄存器中，在ARM是TTB寄存器，X86是CR3寄存器等。随着这个进程的进行，操作系统会逐步在物理内存中创建第二级页表，每次创建一个第二级页表，操作系统就要将它的起始地址放到第一级页表对应的表项中。

每次当虚拟地址中的p1部分变化时(例如0x003FFFFF变化为0x0040000)，此时p1从0x000变化为0x001，操作系统就需要在物理内存中创建一个新的第二级页表，并将这个页表的起始地址写到第一级页表对应的PTE中。当虚拟地址pq部分不发生变化时，只是p2部分的变化范围在0x000~0x3FF。此时不需要创建新的第二级页表。每当虚拟地址中的p2部分发生变化，就表示要使用一个新的页，操作系统将这个新的页从下级存储器中取出来并放到物理内存中，然后将这个页在物理内存中的起始地址填充到第二级页表对应的PTE，于是虚拟地址的页内偏移offset部分，只是用来在一个页的内部找到它对应的数据，它不会影响第一级和第二级页表的创建。

实际上，绝大部分进程只会使用到全部虚拟地址范围的一部分地址。

4MB程序，不考虑数据大小，考虑两种极端情况，

（1）程序的虚拟地址是连续的，这个大小为4MB的程序需要使用第一级页表的PTE0以及一个完整的第二级页表，一共8KB。

（2）程序中包含很多跳转，必须占用的物理存储空间是一个第一级页表和1024个第二级页表=1024*4KB=4100KB。

实际上，没有编译器会这样编译程序，大部分程序在编译时候，所占用的虚拟存储器的地址范围还是尽量集中。

当处理器开始执行一个程序时，就会把第一级页表放到物理内存中，直到这个程序被关闭为止，因此第一级页表所占用4KB存储空间是不可避免的，而第二级页表是否在物理内存当中，则是根据一个程序当中虚拟地址的值来决定的，操作系统会逐个地创建第二级页表。

事实上，伴随着一个页被放入到物理内存中，必然会有第二级页表中的一个PTE被建立，这个PTE会被写入该页在物理内存中的起始地址，如果这个页对应的第二级页表还不存在，那么就需要操作系统建立一个新的第二级页表，这个过程是很自然的。

很多硬件实现Page Table Walk的处理器中，都采用了多级页表的结构。Page Table Walk是指当发生TLB缺失时，需要从页表中找到对应的映射关系并将其写回到TLB的过程中。这种多级页表还有一个优点，那就是它容易扩展，例如当处理器的位数增加时，可以通过增加级数的方式来减少页表对物理内存的占用。

使用这种多级页表结构，每一级的页表都需要存储在物理内存中，因此要得到一个虚拟地址对应的数据，需要多次访问物理内存，很显然，这个过程消耗的时间是很长的。对于一个二级页表而言，需要访问两次物理内存，才能得到虚拟地址对应的物理地址，然后还需要访问一次物理内存得到数据，因此要得到虚拟地址对应的数据，共需要访问三次物理内存。

虚拟存储器的优点进行总结：

（1）让每个程序都有独立的地址空间。

（2）引入虚拟地址到物理地址的映射，为物理内存的管理带来了方便，可以更灵活地对其进行分配和释放，在虚拟存储器上连续的地址空间可以映射到物理内存上不连续的空间。

（3）在处理中如果存在多个进程，为这些进程分配的物理内存之和可能大于实际可用的物理内存，虚拟存储器的管理使得这种情况下各个进程仍能够正常运行，此时为各个进程分配的只是虚拟存储器的页，这些页有可能存在于物理内存中，也可能面临存在于更下一级的硬盘中，在硬盘中这部分空间被称为swap空间。当物理内存不够用时，将物理内存中一些不常用的页保存到硬盘上的swap空间。因此处理器等效可以使用的物理内存的总量是物理内存的大小+硬盘中swap空间的大小。

将一个页从物理内存中写到硬盘的swap空间称为Page Out，将一个页从硬盘的swap空间放回到物理内存的过程称为Page In。

（4）利用虚拟存储器，可以管理每一个页的访问权限。从硬件的角度来看，单纯的物理内存本身不具有各种权限的属性，它的任何地址都可以被读写，而操作系统则要求在物理内存中实现不同的访问权限。这些权限的管理是通过页表Page Table来实现的，通过在页表中设置每个页的属性，操作系统和内存管理单元MMU可以控制每个页的访问权限。

3.2.3 Page Fault

如果一个进程中的虚拟地址在访问页表时，发现对应的PTE中，有效位为0，这就表示这个虚拟地址所属的页没有被放到物理内存中，因此在页表中就没有存储这个页的映射关系，这时候就说发生了Page Fault，需要从下级存储器，例如硬盘中，将这个页取出来，放到物理内存中，并将这个页在物理内存中的起始地址写到页表中。Page Fault是异常的一种，通常它的处理过程不是由硬件完成，而是通过软件中操作系统来完成的，原因有二：

（1）由于Page Fault时要访问硬盘，这个过程需要的时间相当长，通常是毫秒级别，和这个漫长时间相比，即使处理Page Fault对应的异常处理程序需要使用几百条指令，这个时间相比于硬盘访问时间也是微乎其微的，因此没有必要使用硬件来处理Page Fault。

（2）发生Page Fault时，需从硬盘中搬移一个或几个页到物理内存中，当物理内存中没有空余的空间时，就需要从其中找到一个最近不常使用的页，将其进行替换。如果使用硬件的话，很难实现复杂的替换算法，而且不能根据实际情况进行调整，缺少灵活性。

需要注意，直接使用虚拟地址并不能知道一个页位于硬盘的那个位置，也需要一个机制来记录一个进程的每个页位于硬盘中的地址。通常，操作系统会在硬盘中为一个进程的所有页开辟一块空间，这就是之前说过的swap空间，在这个空间中存储一个进程所有页，操作系统在开辟swap空间时，还会使用一个表格来记录每个页在硬盘中存储的位置。

虽然映射到物理内存的页表和映射到硬盘的页表可以放到一起，但是在实际中，物理上它们仍然是分开放置的，因为不管一个页是不是在物理内存中，操作系统都必须记录一个进程的所有页在硬盘中的位置，因此需要单独地使用一个表格来记录它。

当物理内存被修改后，在硬盘中的存储的内容就过时了，有两种处理方法：

（1）写通write through，将这个改变的内容马上写回到硬盘中，考虑到硬盘的访问时间非常慢，这样的做法是不现实的。

（2）写回write back，只有等到这个地址的内容在物理内存中要被替换时，才将这个内容写回到硬盘中，这种办法减少了硬盘的访问次数，因此被广泛使用。

其实write through的方式只可能在L1 Cache和L2 Cache之间使用，因为L2 Cache的访问时间在一个可接受的范围之内，而且这样可以降低Cache一致性的管理难度，但是更下层的存储器需要的访问时间越来越长，因此只有写回write back方式才可以接受的方法。

为了支持写回方式，需要记录每个页是否在物理内存中被修改过，通常是在页表的每个PTE中增加一个dirty，当一个页内的某个地址被写入时，这个脏的状态位会被设置为1。当操作系统需要将一个页进行替换之前，会首先去页表中检查它对应PTE的脏状态位，如果为1，则需要先将这个页的内容写回到硬盘中。如果为0，则表示这个页从来没有被修改过，那么久可以直接将其覆盖了，因为在硬盘中还保存着这个页的内容。

为了帮助操作系统实现替换算法记录使用情况功能，需要在硬件层面提供支持，这可以在页表的每一个PTE中增加一位，用于记录每个页最近是否被访问过，这个位称为使用位use，当一个页被访问时，使用位被置为1，操作系统周期性地将这一位清零，然后过段时间再去查看它，这样就能知道每个页在这段时间是否被访问过。由于使用了use位，操作系统的任务量大大地减轻了。

总结来说，为了处理Page Fault，处理器在硬件上需要提供的支持如下:

（1）在发现Page Fault时，能够产生对应类型的异常，并且能够跳转到它的异常处理程序的入口地址。

（2）当要写物理内存时，例如执行了store指令，需要硬件将页表中对应的PTE的dirty状态置为1.

（3）当访问物理内存时，例如load/store指令，需要硬件将页表中对应PTE的use置为1，表示这个页最近被访问过。

到目前为止，页表中每个PTE内容如

 3.2.4 小结

在处理器中，有一个模块专门负责虚实地址转换，并且处理Page Fault，这个模块就是之前介绍的MMU。

下面以单级页表为例，进行小结;

（1）当没有Page Fault发生时，整个过程如

具体过程如下：

1. 处理器送出的虚拟地址VA首先送到MMU中。

2. MMU使用页表基址寄存器PTR和VA[31:12]组成一个访问页表的地址，这个地址被送到物理内存中。

3. 物理内存将页表中被寻址到的PTE返回给MMU。

4. MMU判断PTE中的有效位，发现其为1，表示对应的页存在于物理内存中，因此使用PTE中的PFN和原来地址虚拟地址VA[11:0]组成的实际物理地址，即PA={PFN,VA[11:0]}，并用这个地址来寻找物理内存，得到最终的数据。

（2）当发生Page Fault时，整个过程如

1~3步骤和上面情况是一样的，处理器送出VA到MMU，MMU使用PTR和VA[31:12]组成访问页表的地址，从物理内存中得到相应的PTE，送回到MMU。

4. MMU查看PTE当中的有效位，发现其为0，也就是需要的页此时不再物理内存当中，此时MMU会触发一个Page Fault类型的异常送给处理器，这会使处理器跳转到Page Fault对应的异常处理程序中，这一步，MMU还会把发生Page Fault的虚拟地址VA页保存到一个专门的寄存器中，供异常处理程序使用。

5. 假设此时物理内存中没有空闲的空间了，那么Page Fault的异常处理程序需要按照某种替换算法，从物理内存中找出一个未来可能不被使用的页，将其替换，这个页被称为Victim page，如果这个页的对应的dirty位是1，表示这个页的内容在以前曾经被修改过，因此需要首先将它从物理内存写到硬盘中。当然，如果dirty位是0，那么就不需要写回硬盘的过程。

6. Page Fault的异常处理程序会使用刚刚保存的VA来寻址硬盘，找到对应的页，将其写到物理内存中Victim page所在位置，并将这个新的映射关系写到页表中，这里需要注意，寻址硬盘的时间是很长的，通常是毫秒级别，因此这一步的处理时间也是很长。

7. 从Page Fault异常处理中返回的时候，那条引起Page Fault的指令会被重新取到流水线中执行，此时处理器会重新发出虚拟地址到MMU，因为所需要的页被放到物理内存中，因此这次访问肯定不会发生 Page Fault，会按照不发生Page Fault时的过程处理。