第3章 虚拟存储器 摘录

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中。当虚拟地址p1部分不发生变化时，只是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空间的大小。
        （4）利用虚拟存储器，可以管理每一个页的访问权限。从硬件的角度来看，单纯的物理内存本身不具有各种权限的属性，它的任何地址都可以被读写，而操作系统则要求在物理内存中实现不同的访问权限。这些权限的管理是通过页表Page Table来实现的，通过在页表中设置每个页的属性，操作系统和内存管理单元MMU可以控制每个页的访问权限。

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

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时的过程处理。

 3.3 程序保护

不同的进程之间应该加以保护，一个进程不能让其他的进程随便修改自己的内容，以保证各个进程之间运行的稳定。

访问权限在硬件上就加以控制，通常这种控制是通过页表来实现的，因为要访问存储器的内容，必须要经过页表，所以在页表中对各个页规定不同的访问权限是很自然的事情。

主要注意的是，操作系统本身也需要指令和数据，但是考虑到它需要能够访问物理内存中所有的空间，所以操作系统一般不适用页表，而是直接可以访问物理内存，在物理内存中有一部分地址范围专门供操作系统使用，不允许别的进程随便地访问它。

ARM处理器采用两级页表的方法，第二级页表的每个PTE中都有一个AP部分，AP部分直接决定了每个页的访问权限。

在ARMv7架构中，规定处理器可以工作在User模式和Privileged模式，在Privileged模式下，可以访问处理器内部所有的资源，因此操作系统会运行在这种模式下，而普通的用户程序则是运行在User模式下，第二级页表可以控制控制每个页的访问权限，这样可以使一个页对于不同的进程有着不同的访问权限。

既然在页表中加入了每个页的访问权限，那么一旦发现当前的访问不符合规定，会产生一个异常来通知处理器，使处理器跳转到异常处理程序中，这个处理程序一般是操作系统的一部分。

在地址转换的过程中加入权限检查的过程，注意此时在PTE中多了进行权限控制的AP部分。

当然，如果采用了二级页表结构，事实上在第一级页表也可以进行权限控制，而且可以控制更大的地址范围。也就是在一个页大小为4KB的系统中，第一级页表可以映射一个完整的第二级页表，也就是4MB的地址范围，而第二级页表只能映射4KB的地址范围。

第一级页表中的每个PTE都可以控制4MB的地址范围，这样可以更高效地对大片的地址进行权限设置和检查。例如，可以在第一级页表的每个PTE中设置一个两位的权限控制位，当其为00时，它对应的整个4MB空间都不允许被访问；当11时，对应的4MB空间进程将不设限制，随便访问；当为01时，需要查看第二级页表的PTE，以获得关于每个页自身访问权限的情况；通常这种粗粒度(第一级页表的权限控制)和细粒度(第二级页表的权限控制)的组合，可以在一定程度上提高处理器的执行效率。

如果访问芯片外的外设寄存器，例如访问LCD驱动模块和寄存器，此时对这些寄存器的读写是为了对外设进行操作，因此这些地址是不允许经过D-Cache被缓存的，如果被缓存了，那么这些读写将只会在D-Cache中起作用，并不会传递到外设寄存器中而真正对外设模块进行操作，因为在处理器的存储器映射中，总会有一块区域，是不可以被缓存的。

到目前为止，在页表的每个PTE都包括如下内容：
        1. PFN，表示虚拟地址对应的物理地址的页号；
        2. Valid，表示对应的页当前是否在物理内存中；
        3. Dirty，表示对应页的内容是否被修改过；
        4. Use，表示对应页的内容最近是否被访问；
        5. AP，访问权限控制，表示操作系统和用户程序对当前这个页的访问权限；
        6. Cacheable，表示对应页是否允许被缓存

3.4 加入TLB和Cache

3.4.1 TLB的设计

1.概述

访问多级页表时需要多次访问物理内存才可以得到虚拟地址对应的物理地址，而物理内存的运行速度相对应处理器本身来说，有几十倍差距。此时借鉴Cache的设计理念，使用一个速度比较快的缓存，将页表中最近使用的PTE缓存下来，因为它们在以后还可能继续使用，尤其对于取指令来说，考虑程序本身是串行性，会顺序地从页内取指令，此时将PTE缓存起来是大有益处的，能够加快一个页内4KB内容的地址转换速度。

由于历史的原因，缓存PTE的部件一般不称为Cache，而是称之为TLB Translation Lookside Buffer，在TLB中存储了页表中最近被使用过的PTE，从本质上来看，TLB就是页表的Cache。但是TLB又不同于一般的Cache，它只有时间相关性，也就是说，现在访问的页，很有可能在以后继续被访问，至于空间相关性，TLB并没有明显的规律，因为在一个页内有很多情况，都可能使程序跳转到其他不相邻的页中取指令或数据。正因为如此，Cache设计中很多优化方法，例如预取prefetching，是没有办法应用到TLB中的。

一般为减少TLB miss发生的频率，会采用全相连的方式来设计TLB，但是这样导致TLB的容量不能太大，因此也有一些设计中采用了组相连的方式来实现容量比较大的TLB，容量过小的TLB会影响处理器的性能，因此在现代的处理器中，很多都采用了两级TLB，第一级采用哈佛结构，分为指令和数据TLB，一般采用全相连方式，第二级TLB是指令和数据共用，一般采用组相连方式，这种设计方式和多级Cache是一样的。

下面展示一个全相连方式的TLB，从处理器送出的虚拟地址首先会送到TLB中进行查找，如果TLB对应的内容是有效的，即表示TLB命中，可以直接使用从TLB得到的物理地址来寻址物理内存；如果TLB缺失，那么就需要访问物理内存中页表，此时有如下两种情况：
        1. 在页表中找到的PTE是有效的，即这个虚拟地址所属的页在物理内存中；
        2.在页表中找到的PTE是无效的，即这个虚拟地址所属的页不在物理内存中，造成这种现象的原因有很多，例如这个页在以前没有被使用过，或者这个页已经被交换到硬盘中等，此时就应该产生Page Fault类型异常，通知操作系统来处理这个情况，操作系统需要从硬盘中将相应的页搬移到物理内存中，将它在物理内存中的首地址放到页表对应的PTE，并将这个PTE的内容写到TLB。

因为TLB采用了全相连的方式，所以相对于页表，多了一个Tag项，它保存了虚拟地址的VPN，用来对TLB进行匹配寻找，TLB中其他的项完全来自于页表，每当发生TLB miss，将PTE从页表中搬移到TLB中。

在很多处理器中，还支持容量更大的页，因为随着程序越来越大，4KB大小的页已经不能够满足要求了，对于一个有着128个表项的I-TLB来说，只能映射128*4KB=512KB大小的程序，这对于当代程序来说显然是不够的，因此需要使用容量更大的页，例如1MB或者4MB的页，这样可以使TLB映射到更大的范围，避免频繁地对TLB进行替换。当然，更大的页也是存在缺点的，对于很多程序来说，如果它利用不到这么大的页，那么就会造成一个页内的很多空间被浪费，这种现象被称为页内碎片Page Fragment，它降低了页的利用效率，而且，每次当发生Page Fragment时，更大的页也意味着要搬移更多的数据，需要更长的时间才能将这样大的页从下级存储器搬移到物理内存中，使得处理Page Fragment的时间变得更长了。

为了解决这种矛盾，在现代的处理器中都支持大小可变的页，由操作系统进行管理，根据不同应用特点选用不同大小的页，可以最大限度地利用TLB中有限的空间，同时又不至于在页内产生更多的碎片。为了支持这种特性，在TLB中需要相应的位进行管理，例如MIPS处理器的TLB中，有一个12位的Pagemask项，它用来指示当前被映射的页的大小。

采用不同大小的页，在寻址TLB时，进行的地址比较也是不同的，对于1MB大小的页，只需要将VA[31:20]作为Tag。参与地址比较就可以了，虚拟地址剩余的20位将用来寻址页的内部。不仅如此，对TLB的寻址还受到其他内容的影响，例如ASID和Global位。

在TLB以上所有的项中，除了use和dirty之外，其他的项在TLB中是不会改变的，它们的属性都只是只读，以D-TLB为例，当执行load/store指令时，都会访问D-TLB，如果是TLB命中，会将TLB中对应的use置为1；如果执行了store指令，还会降dirty也置为1。因此TLB采用write back方式，在TLB中某个表项被替换时，也只有这两个位需要被写回页表。

2. TLB缺失

当一个虚拟地址查找TLB，发现需要的内容不在其中时，就发生了TLB缺失，由于TLB本身的容量很小，所以TLB缺失发生的频率还是比较高的，原因如下：
        1. 虚拟地址对应的页不在物理内存中，此时页表中的就没有对应的PTE，由于TLB是页表的Cache，所以TLB的内容应该是页表的一个子集，也就是说，在页表中不存在的PTE，也不可能出现在TLB中。
        2. 虚拟地址对应的页已经存在于物理内存中，因此在页表中也存在对应的PTE，但是这个PTE还没有放到TLB中，这种情况是经常发生的，毕竟TLB的容量远小于页表。
        3. 虚拟地址对应的页已经存在于物理内存中，因此在页表页存在对应的PTE，这个PTE也曾经存在于TLB中，但是后来从TLB中被替换了。

解决TLB缺失的本质就是要从页表中找到相应的映射关系，并将其写回到TLB中，这个过程称为Page Table Walk，可以使用硬件的状态机来完成这个事情，也可以使用软件。
        （1）软件实现：软件实现跨越保持最大的灵活性，但是一般也需要硬件的配合，这样可以减少软件工作了。一旦发现TLB miss，硬件把产生TLB缺失的虚拟程序保存到一个特殊寄存器中，同时产生一个TLB缺失类型的异常。在异常处理程序中，软件使用保存到特殊寄存器中的虚拟地址去寻找物理内存中的页表，找到相应的PTE，并写回到TLB中。对于超标量处理器来说，由于对异常进行处理时，会将流水线中所有的指令进行抹掉，会产生性能损失，但是可以实现一些灵活的TLB替换算法。
        （2）硬件实现：硬件实现一般由MMU完成，当发现TLB缺失时，MMU自动使用当前的虚拟地址去寻址物理内存中的页表。多级页表最大优点就是容易使用硬件查找。由硬件自动完成，软件不需要做任何事情。如果MMU发现查找到的PTE是无效的，那么硬件就无能为力。使用硬件处理TLB miss的方法更适合超标量处理器，它不需要打断流水线，因此从理论上来说，性能也会好一些，但是这需要操作系统保证页表已经在物理内存中建立好了，并且操作系统也需要将页表的基地址预先写到处理器内部对应的寄存器中，这样才能保证硬件可以正确地寻址页表。

采用软件处理TLB miss可以减少硬件设计复杂度，尤其在超标量处理器中，可以采用普通的异常处理过程。而硬件处理除了需要硬件状态机来寻址页表之外，还需要将整个流水线都暂停，等待MMU处理TLB miss。从时间角度来看，软件处理TLB miss除了对应的异常处理程序本身需要占据时间外，还需要考虑到从异常处理程序退出后，将流水线回复到TLB缺失发生异常之前的状态所需要的时间。硬件处理只需要将流水线全部暂停，等待硬件处理完毕即可恢复流水线。

MMU硬件寻址页表所耗费的时间，一般情况下要小于TLB缺失的异常处理程序的执行时间，但是二者差别不会很大。

当发生TLB缺失时，如果所需要的PTE在页表中，则TLB缺失的处理时间大约需要十几个周期；如果由于PTE不在页表中而发生的Page Fault，则处理周期需要成百上千个周期了，此时不管采用硬件处理还是软件处理TLB miss，都不会有明显差别了。

在典型的页大小为4KB的系统中，只要此时运行的指令或数据在4KB的边界之内，就不会发生TLB缺失，一般普通的串行程序都会满足这个规律。当然，TLB miss发生的频率还取决于TLB的大小以及关联度，还有页的大小等因素。一旦有TLB miss转变为Page Fault，所需要的处理时间就取决于页的替换算法，以及被替换的页是否是dirty等因素了。

实际设计很难实现严格的随机，此时仍然可以采用一种称为时钟算法的方法来近视的随机。

3. TLB的写入

使用TLB作为页表的缓存之后，处理器送出的虚拟地址会首先访问TLB，如果命中，那么直接从TLB中就可以得到物理地址，不需要再访问页表。

如果TLB采用write back实现策略，那么use和dirty信息并不会马上从TLB中写回到页表，只有等到TLB中一个表项要被替换的时候，才会将它对应的信息写回到页表中，这种工作方式给操作系统进行页替换带来了新的问题，因为此时在页表中记录的状态位(use和dirty)有可能是“过时”的，操作系统无法根据这些信息，在Page Fault发生时找出合适的页进行替换。一种容易想到的解决方法就是当操作系统在Page Fault发生时，首先将TLB中的内容写回到页表，然后就可以根据页表中的信息进行后续的处理了，这个办法显然会耗费一些时间。

实际上，这个过程是可以省略的，操作系统完全可以认为，被TLB记录的所有页都是需要被使用的，这些页在物理内存中不能够被替换。操作系统可以采用一些办法来记录页表中那些PTE被放到了TLB中，而且这样做还有一个好处，它避免了当物理内存中一个页被提出之后，还需要查找它在TLB是否被记录了，如果是，需要在TLB中将其置为无效，因为在页表中已经没有这个映射关系了，因此TLB中也不应该有。总结起来就是TLB中记录的所有页都不允许从物理内存中被替换。

4. 对TLB进行控制

如果由于某些原因导致一个页的映射关系在页表中不存在了，那么它在TLB中也不应该存在，而操作系统在一些情况下，会把某些页的映射关系从页表中抹掉，例如：
        （1）当一个进程结束时，这个进程的code、data和stack所占据的页表就需要变为无效，这样也就释放了这个进程所占据的物理内存空间。最简单的做法就是将I-TLB和D-TLB中的全部内容都置为无效。如果实现了ASID，那么只将这个进程对应的内容在TLB中置为无效即可。
        （2）当一个进程占用的物理内存过大时，操作系统可能会将这个进程中的一部分不经常使用的页写回到硬盘中，这些页在页表中对应的映射关系也应该置为无效。但是，一般操作系统会尽力避免将存在于TLB中的页置为无效，因为这些页在以后很有可能会被继续使用。

抽象出来，对TLB的管理需要包括的内容有如下几点：
        1.能够将I-TLB和D-TLB的所有表项置为无效；
        2.能够将I-TLB和D-TLB中某个ASID对应的表项置为无效；
        3.能够将I-TLB和D-TLB中某个VPN对应的表项置为无效；

3.4.2 Cache的设计

1. Virtual Cache

TLB只是加速了虚拟地址到物理地址的转换，可以很快地得到所需要的数据或指令在物理内存中的位置，也就是得到了物理地址，但是如果直接从物理内存中取数据或指令，显然也是很慢的。实际上，从虚拟地址转换之后，后续过程如前文所述一样。因为这种Cache使用物理地址进行寻址，因此称为物理Cache Physical Cache。

如果不使用虚拟存储器，处理器送出的地址会直接访问物理Cache，而现在要先经过TLB才能再访问物理Cache，因此必然会增加流水线的延迟，如果还想获得以前一样的运行频率，就需要将访问TLB的过程单独使用一级流水线，但是这样就增加了分支预测失败时的惩罚penalty，也增加了load指令的延迟，不是一个很好的做法。

为什么不使用Cache来直接缓存从虚拟地址到数据的关系呢？当然是可以的，因为这个Cache使用虚拟地址来寻址，称之为虚拟Cache Virtual Cache。既然使用虚拟Cache，可以直接从虚拟地址得到对应的数据，那么是不是就不使用TLB了呢？当然不是这样，因为一旦Cache发生miss，仍然需要将对应的虚拟地址转换为物理地址，然后再去物理内存中获得对应的数据，因此还需要TLB来加速从虚拟地址到物理地址的转换过程。

如果使用虚拟地址，从虚拟Cache中找到了需要的数据，那么就不需要再访问TLB和物理内存，在流水线中使用这种虚拟Cache，不会对处理器的时钟产生明显的负面影响，不过它会引起一些新的问题，需要耗费额外的硬件进行解决。

但是直接使用虚拟Cache则会引入新的问题，主要概况为两方面：
      （1）  同义问题synonyms，也称为重名，即多个不同的名字对应的相同的物理位置，在虚拟存储器的系统中，一个进程内或者不同进程之间，不同的虚拟地址可以对应同一个物理内存中的位置。然而，如果使用了虚拟Cache，由于直接使用虚拟地址进行寻址，则不同的虚拟地址会占用Cache中不同的地方，那么当很多虚拟地址都对应着一个物理地址时，就会导致在虚拟Cache中，这些虚拟地址虽然占据了不同的地方，但是它们实际上就是对应着同一个物理内存中的位置，这样会引起两方面问题，一是浪费宝贵的Cache空间，造成Cache等效容量的减少；二是当执行一条store指令而写数据到虚拟Cache中时，只会将这个虚拟地址在Cache中对应的内容进行修改，而实际上，Cache中其他有着相同物理地址的地方需要被修改，其他的虚拟地址读取Cache时，就无法得到刚才更新过的正确值。

虚拟Cache的同义问题取决于页的大小和Cache的大小。前文所言虚拟地址转换为物理地址的时候，页内的偏移量是不变的。对于一个4KB的页来说，虚拟地址的低12位不会发生变化，如果此时一个直接相连的虚拟Cache容量小于4KB，那么寻址Cache的地址就不会大于12位，此时即使两个不同的虚拟地址对应同一个物理位置，它们的寻址虚拟Cache的地址也是相同的，因此会占据虚拟Cache中的同一个地方，不会存在不同的虚拟地址占用Cache中不同的位置。

一个大小为8KB、直接相连的Cache，内部被分为两个4KB的bank，使用VA[11:0]作为两个Bank公用地址。需要注意，在Cache中的数据部分和Tag部分都使用了bank结构，这种Cache的读写过程如下：
        1. 读取Cache时，两个bank都会被VA[11:0]寻址而得到对应的内容，这两个bank的输出被送到一个由物理地址PA[12]控制的多路选择器上，当物理地址PA[12]为0时，选择bank0输出的值，当物理地址PA[12]为1时，选择bank1输出的值。由于物理地址需要经过TLB才可以得到，所以当Cache中两个bank输出的值送到多路选择器时，物理地址可能还没有从TLB中得到，这在一定程度上增加了处理器的周期时间。需要注意的是，由于Cache中的Tag部分也采用了bank结构，可以得到Cache最终输出的Tag值，这个值会跟TLB输出的PFN值进行比较，从而判断Cache是否命中。
        2. 写Cache时候，由于一条指令只有retire时候，才会真正地写Cache，此时的物理地址已经得到了，所以在写Cache时可以根据物理地址PA[12]的值，将数据写到相应bank中。

该做法相当于PFN为偶数的所有地址写到Cache中的bank0，PFN(PA[12])为奇数的所有地址写到bank1中，这样不会造成Cache的存储空间的浪费，缺点则是增加了硬件复杂度，并且在Cache中的way的个数不增加的情况下，随着Cache的容量增大，需要使用的硬件也越来越多。例如使用大小为16KB、直接相连结构的Cache时，就需要使用4个bank，采用PA[13:12]来控制多路选择器。由于采用了bank结构，Cache的输入需要送到所有的bank中，造成输入端的负载变得很大，而且每次读取Cache时所有的bank都会参与动作，所以功耗相比普通的Cache也会增大，这些都是采用bank结构的虚拟Cache需要面临的缺点。

        （2）同名问题homonyms，即相同的名字对应不同的物理位置，在虚拟存储器中，因为每个进程都可以占用整个虚拟存储器空间，因此不同的进程之间会存在很多相同的虚拟地址。而实际上，这些虚拟地址经过每个进程的页表转换后，会对应不同的物理地址，这就产生了同名问题：很多相同的虚拟地址对应着不同的物理地址。当从一个进程切换切换到另一个进程时，新的进程使用虚拟地址来访问Cache的话(假设使用虚拟地址作为Cache中的Tag部分)，从Cache中可能得到上一个进程的虚拟地址对应的数据，这样就产生了错误，为了避免这种情况发生，最简单的方法就是在进程切换的时候将虚拟地址Cache中所有的内容置为无效，这样就保证了一个进程在开始执行的时候，使用的虚拟Cache是干净的。同理，对于TLB也是一样，在进程切换之后，新的进程在使用虚拟地址访问TLB时，可能会得到上一个进程中虚拟地址的映射关系，这样显然也会产生错误，因此在进程切换时候，也要将TLB的内容清空，保证新的进程使用的TLB是干净的。当进程切换很频繁时，就需要将TLB和虚拟Cache的内容清空，这样可能浪费大量有用的值，降低了处理器的执行效率。

既然无法直接从虚拟地址中判断它属于哪个进程，那么就为每个进程赋一个编号，每个进程中产生的虚拟地址都附上这个编号，它的编号就相当于是虚拟地址的一部分，这样不同的虚拟地址肯定是不一样的，该编号即PID Process ID，当然更常见的叫法是ASID(Address Space IDentifier)。

使用ASID也引入了一个新的问题，当多个进程共享同一个页时，如何实现这个功能？这需要在ASID之外在增加一个标志位，称之为Global位，或简称G位。当一个页不只是属于某一个进程，而是被所有的进程共享时，就可以将Global置为1，这样查找页表时，如果发现G为1，就不需要理会ASID的值，这样就实现了一个页被所有进程共享的功能。

ASID和原来的虚拟地址一起组成了新的虚拟地址，这就相当于使虚拟地址的位数增加了，例如在3位的处理器中采用8位的ASID，则相当于虚拟地址是40位，此时还可以使用两级页表，将这40位的虚拟地址进行划分，假设仍旧使用4KB的页，查找第一级页表使用14位，查找第二级页表使用14位，那么第一级和第二级页表的大小都是2^14*4B=64KB，过大的页表可能导致其内部出现碎片，降低页表的利用效率。

为了解决这个问题，可以采用三级页表方式。增加一个额外的页表，它使用ASID进行寻址，这个页表中的每个PTE都存放第二级页表的基地址，此时仍旧需要PTR寄存器存放第一级页表的基地址。

当然这种方式造成要从虚拟地址中得到所需数据，相比于二级页表，多一次物理内存访问，这会造成TLB缺失的处理器时间变长，是使用ASID一个负面影响，尤其是TLB缺失发生的频率很高时。

在使用多级页表的系统中，只有第一级页表才会常驻在物理内存中，第一级页表的基地址由处理器当中专用的寄存器制定，例如PTR寄存器。支持ASID的处理器中还会有一个寄存器来保存当前进程的ASID值，每次操作系统创建一个进程时，就会给当前进程分配ASID值，并将其写到ASID寄存器中。在TLB中，ASID和VPN一起组成了新的虚拟地址，参与地址的比较，这样就对TLB中对不同的进程进行了区分。

当系统中运行的进程个数超过ASID能够表示的最大范围时，例如有多于256个进程存在于8位ASID的系统中，此时就需要操作系统从已经存在的256个ASID中挑出一个不经常使用的值，将它在TLB中对应的内容清空，并将这个ASID分配给新的进程。为了能够对旧的进程进行恢复，操作系统需要将被覆盖的PTR寄存器的值保存起来。

2. 对Cache进行控制

在Cache中缓存着物理内存的内容，因此Cache中的内容都是物理内存的子集，但是要保持这种关系，需要对下列情况进行特殊处理：
        （1）当DMA需要将物理内存中的数据搬移到其他地方，当此时物理内存中最新数据还存在于D-Cache中，因此在进行DMA搬移之前，需要将D-Cache中所有dirty的内容写回到物理内存中。
        （2）当DMA从外界搬移数据到物理内存的一个地址上，而这个地址又在D-Cache中被缓存，那么此时就需要将D-Cache中这个地址的内容置为无效。
        （3）当发生Page Fault时，需要从硬盘读取一个页并写到物理内存中，如果物理内存中被覆盖的页是dirty状态，并且这个页的部分内容还存在于D-Cache中，那么就需要先将D-Cache的内容写到物理内存，然后才能够将这个页写回到硬盘，此时就可以对物理内存的这个页进行覆盖了。
        （4）处理器有可能执行一些“自修改”的指令，将处理器后续要执行的指令进行修改，这些新的指令会先作为数据写到D-Cache中，如果想要处理器能够正确地执行这些被修改过的指令，需要将D-Cache的这些内容都写到物理内存中，同时需要将I-Cache中的所有内容都清空，这样才能够保证处理器能够执行最新的指令。在处理器中，D-Cache和I-Cache之间没有直接的通路，只能通过物理内存进行交互。

和TLB多采用全相连的结构不同，Cache一般采用组相连的结构，为了能够找到Cache中的某个Cache line，可以使用的寻址手段有以下两种：
        （1）set/way，通过提供set和way的信息，可以定位到Cache中的一个Cache line。
        （2）地址，在Cache真正工作的时候，是通过地址来查找Cache的，这个地址可以是虚拟地址，也可以是物理地址，这取决于采用物理Cache还是虚拟Cache。这个地址的Index部分用来找到Cache中的某个Cache set，Tag部分用来将从不同way中选出匹配的Cache line(如果Cache中使用物理地址作为Tag，还需要先将虚拟地址转换为物理地址)。

在ARM处理器中，仍旧使用系统协处理器即CP15 中的寄存器来管理Cache，而MIPS处理器，则直接使用专用的指令来管理Cache。

3.4.3 将TLB和Cache放入流水线

1. Physically-indexed，Physically-Tagged

在使用虚拟存储器的系统中，仍旧可以使用物理Cache，这是最保守的一种做法，因为处理器送出的虚拟地址VA会首先被TLB转换为对应的物理地址PA，然后使用物理地址来寻址Cache，此时就像是没有使用虚拟存储器一样，直接使用了物理Cache，并且使用物理地址的一部分作为Tag，因此称其为Physically-indexed，Physically-Tagged。

由于寻址TLB的过程需要一定时间，为了不至于对处理器的周期时间造成太大的负面影响，可以需要将访问TLB的过程单独作为一个流水段，这样相当于增加了流水线级数，对于I-Cache来说，增加一级流水线会导致分支预测失败时有更大的惩罚penalty；而对于D-Cache来说，增加一级流水线会造成load指令的延迟latency变大。这种设计在理论上完全没有问题，但是在真实的处理器中很少使用，因此它完全串行了TLB和Cache的访问。而实际上，这是没有必要的，因为从虚拟地址到物理地址的转换过程中，低位的offset部分是保持不变的。如果物理地址中寻址Cache的部分使用offset就足够的话，那么就不需要等到TLB中得到物理地址之后才去寻址Cache，而是直接使用虚拟地址的offset部分，这样访问TLB和访问Cache的过程是同时进行的。

这种设计在不影响流水线深度的情况下获得很好的性能，但是对Cache的大小有了限制。

2. Virtually-index，Physical-Tagged

使用虚拟Cache，根据Cache的大小，直接使用虚拟地址的一部分来寻址这个Cache(这就是virtually-indexed)，而在Cache的Tag则使用物理地址中的PFN(这就是physically-tag)，这种Cache是目前被使用最多的，大多数的现代处理器都使用了这种方式。

在这样的方式中，访问Cache和访问TLB是可以同时进行的，假设在直接映射Cache中，每个Cache line包含2^b字节的数据，而Cache set的个数是2^L，也就是说寻址Cache需要的地址长度是L+b，它直接来自于虚拟地址，假设页的大小是2^k字节，因此有以下三种情况：
        （1）k>L+b，此时Cache的容量小于一个页的大小；
        （2）k=L+b，此时Cache的容量等于一个页的大小；
        （3）k<L+b，此时Cache的容量大于一个页的大小；

在前两种情况中，寻址Cache的地址虽然直接来自于虚拟地址，但是这个地址并没有超过offset部分，所以寻址Cache的地址在虚拟地址到物理地址的转换过程中不会发生变化的，这个地址也可以认为是来自于物理地址，只不过它并行访问了TLB和Cache，提高了处理器的执行效率。

        （1）情况1：k>L+b或者k=L+b

此时Cache容量小于或等于一个页的大小，直接使用虚拟地址中的[L+b-1:0]部分来寻址Cache，找到相应的Cache line中数据，并将这个Cache line的Tag部分和TLB转换得到的PFN进行比较，用来判断Cache是否命中。这种设计避免虚拟Cache中的重名问题，因为它本质使用物理地址来寻址Cache，相当于直接使用了物理Cache。为什么会有这样的效果呢？假设有几个不同的虚拟地址映射到同一个物理地址，那么这些虚拟地址的offset部分肯定相同，也就是说这些虚拟地址用来寻址Cache的地址是一样的，因此这些不同的虚拟地址必然位于直接映射Cache中的同一个位置，这样出现重名的这些虚拟地址就不可能同时共存Cache中，因为Cache内只有一个位置可以容纳这些重名的虚拟地址中。

即使在组相连的结构的Cache中，这些重名的虚拟地址也不能占据不同的way，因为此时本质使用的是物理Cache，在物理Cache中，同一个地址只能占据一个way，只有index部分相同的不同地址才可以占据不同的way。

上面这种方法使用了直接映射结构的Cache，它的容量大小等于一个页的大小，因此对于页大小为4KB的典型设计来说，Cache的容量就被限制在4KB，不能够在大了。要想使用更大的Cache，就需要使用组相连的Cache，因为增加way的个数不会引起寻址所需地址位数的增加，使用这种方式的Cache容量的大小是有限制的。

（2）情况2：k<L+b

考虑到速度的限制，不可能在组相连结构的Cache中无限制增加way的个数，因此只能够增加每个way的容量，此时就会导致虚拟地址中寻址Cache的index位数的增加，这就变成L+b的值大于offset的位数k，这种设计就是真正地virtually-indexed，虽然这样可以在不增加way个数的情况下获得容量比较大的Cache，但是会面临重名的问题：不同的虚拟地址会对应同一个物理地址，映射到同一个物理地址PA，有一个直接映射结构的Cache，容量为8KB，需要13位index才可以对其寻址，如

此时不能保证VA1和VA2寻址Cache的index是相同的，因为它们的位[12]有可能不相同，此时的位[12]已经属于VPN了，正因为如此，才造成VA1和VA2寻址Cache的index不同，它们会被放到不同的Cache set上，这时候问题就出现了：Cache中两个不同的位置对应着物理存储器同一个物理位置，这样不但造成Cache空间的浪费，而且当Cache中VA2对应数据被改变时，VA1的数据不会随着改变，因此造成了一个物理地址在Cache中有两个不同的值，当后续的load指令从地址VA1读取数据时，就不会从Cache中读取到正确的数值了。

如何解决这个问题呢？在前面讲述虚拟Cache时，介绍了使用bank结构的Cache来解决这种同义问题，将所有同义的虚拟地址都分门别类地放到Cache中指定的地方。

也可以使用L2 Cache来实现这个功能，是L2 Cache中包括所有L1 Cache的内容，也就是采用之前介绍的inclusive的方式。

在大多数处理器中，L2 Cache都是纯粹的物理Cache，也就是采用physically index，physically tag。

3. Virtually index，Virtually tagged

直接缓存了从虚拟地址到数据的过程，它会使用虚拟地址来寻址Cache，并用虚拟地址作为Tag。如果Cache命中，直接就可以从Cache中获得数据，都不需要访问TLB；如果Cache缺失，那么仍旧需要使用TLB来将虚拟地址转换为物理地址，然后使用物理地址去寻址L2 Cache，从而得到缺失的数据(在现代的处理器中，L2及其更下层的Cache都是物理Cache)。

使用这种方法，仍旧会遇到同义的问题，当存在多个虚拟地址对应同一个物理地址的情况时，L1 Cache中也可能出现一个物理地址占据多个Cache line的问题，解决办法是让那些同义的虚拟地址值有一个可以存在于L1 Cche中，只是此时不能在L2 Cache中只存储虚拟地址的部分，而是应该存储整个的虚拟地址。

4 小结

到目前为止可以知道，对于访问存储器的指令来说，它在执行的时候，涉及到如下4种部件的访问(暂不考虑硬盘)：TLB、物理内存中的页表(Page Table)、D-Cache、物理内存中的页；

它们之间的关系如下：
        （1）如果TLB命中，则物理内存中的页表也必然是命中的；
        （2）如果D-Cache命中，则物理内存中的页也是必然命中的；
        （3）如果物理内存中的页表命中，则物理内存中的页也必然是命中的；

最好的情况发生在TLB和Cache同时命中，此时load/store指令在执行的时候需要经历的流水线最短，并不需要访问物理内存。

最坏的情况时TLB和Cache都缺失，切伴随Page Fault，需要通知操作系统来处理这个情况，操作系统会从物理内存的下一级存储器中将这个缺失的页搬移到物理内存中，设置好Page Table对应的PTE，并将TLB和Cache也进行更新，然后才可以重新执行这条发生Page Fault的load/Store指令。为提高整体的执行效率，操作系统此时会保存当前进程的状态，转而执行其他的进程，等到从硬盘中读取到需要的页，并将Page Fault处理完毕后，才会继续执行这个被雪藏的进程。