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来说，只能映射12884KB=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中只存储虚拟地址的a部分，而是应该存储整个的虚拟地址。

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处理完毕后，才会继续执行这个被雪藏的进程。