【计算机体系结构】TLB和Cache

TLB的设计

在两级页表的虚拟存储系统中，需要访问两次物理内存才能得到虚拟地址所对应的物理地址，而物理内存的访问速度是远远慢于处理器的，为了对该过程进行加速，可以加入一个页表的缓存，该缓存将页表中最近使用的PTE缓存下来，因为它们在以后还可能被继续使用。这样的缓存被称为TLB(Translation Lookaside Buffer), TLB存储页表中最近被使用的PTE，从本质上来讲，TLB就是页表的缓存。
然而，TLB不同于一般的cache，它只有时间相关性，而至于空间相关性，TLB没有明显的规律。
和普通的cache一样，TLB也有三种可能的组织方法，分别是直接相联、组相联和全相联，一般为了减少TLB缺失发生的频率，会使用全相联的方式来设计cache，但全相联会导致TLB的容量不能太大，因此一些设计中采用了组相联的方式来设计容量较大的TLB。
在现代处理器中，TLB也是分级的，一般采用两级TLB结构。第一级TLB采用哈佛结构，分为指令TLB和数据TLB，一般采用全相联的方式；第二级TLB是指令和数据共用的，一般采用组相联的方式。

上图展示了全相联方式的TLB。处理器首先送出虚拟地址到TLB中进行查找，如果TLB对应的内容是有效的（valid=1），则表示TLB命中，可以直接从TLB得到物理地址；如果TLB缺失，那么就需要访问物理内存中的页表，此时包括两种情况：

1. 在页表中找到的PTE是有效的，即这个虚拟地址所属的页存在于物理内存中，那么就可以直接从页表中得到对应的物理地址，使用它来寻址物理内存而得到数据，同时将页表中的该PTE写回到TLB中，供后续使用。
2. 在页表中找到的PTE是无效的，即这个虚拟地址所属的页不在物理内存中，此时会产生page fault异常，由操作系统来处理这个情况。操作系统需要从硬盘中将相应的页搬移到物理内存中，将它在物理内存中的首地址放到页表内对应的PTE中，并将这个PTE更新到TLB中。

由于TLB是全相联的，所以相比页表，TLB多了一个Tag项，它存储的是虚拟地址的VPN。
此外，在上图中，除了使用位(use)和脏状态位(dirty)之外，其他的项在TLB中是不会发生改变的，它们的属性是只读的，但使用位和脏状态位可能在处理器执行load/store指令时发生修改。因此，如果TLB采用写回策略，那么在TLB中的某一个表项被替换时，只有这两个位需要被写回到页表中。
TLB的替换算法
和一般的cache一样，TLB也有自己的替换算法，例如可以使用最近最少使用算法(LRU)，但实际上对于TLB来说，随机替换算法是一种比较合适的算法。由于在实际实现上很难实现真正的随机，因此采用一种称为时钟算法的方法来实现近似的随机。它的工作原理其实就是一个计数器，这个计数器一直在运转，例如每个周期加1，计数器的宽度由TLB中表项的个数决定，当TLB中的内容需要被替换时，就会访问这个计数器，使用计数器当前的值作为被替换表项的编号，这样就近似实现了一种随机替换算法。
TLB的写入
根据虚拟内存的相关知识可知，当一个页从硬盘搬到物理内存之后，操作系统需要知道这个页中的内容在物理内存中是否被修改过，如果没有修改过，那么当这个页被替换时，可以直接进行覆盖。而如果这个页的内容在物理内存中曾经被修改过，那么在该页被替换时，首先需要将它从物理内存中写回到硬盘，因而需要在页表中设置一个脏状态位来指示某一个页是否在物理内存中被改写过。
然而，在使用了TLB之后，如果TLB采取写回策略，那么TLB中的使用位和脏状态位不会立即从TLB写到页表，只有等到该表项被替换时，才会写回这些信息。因此，在页表中记录的脏状态位可能是过时的，操作系统无法根据这些信息，在page fault发生时找出合适的页进行替换。一个简单的方法是发生page fault异常时，首先将TLB中的内容写回到页表，然后再根据页表中的内容进行处理，这个办法的缺点是会带来一定的时间开销，影响处理器性能。
事实上，操作系统完全可以认为，被TLB记录的所有页都是需要被使用的，这些页在物理内存中不能够被替换。操作系统可以采用一些办法来记录页表中哪些PTE被放到了TLB中，而且这样做的一个好处是，它避免了当物理内存中一个页被踢出之后，还需要查找它在TLB中是否被记录了，如果是，也需要在TLB中将其置为无效，因为在页表中已经没有这个映射关系了，因此TLB中也不应该有。总结起来就是，TLB中记录的所有页都不允许从物理内存中被替换。

cache的设计

virtual cache

TLB加速了从虚拟地址到物理地址的转换，可以很快的得到所需要数据的物理地址，但是如果直接从物理内存中取数也是很慢的。因此，可以采用cache来缓存物理内存中的数据。

如果首先将虚拟地址转换为物理地址，然后再用物理地址访问cache，那么这样的cache就是物理Cache(Physical Cache)。使用TLB和物理Cache一起进行工作的过程如上图所示。
由于经过TLB之后才能访问物理cache，因此必然会增加流水线的延迟，如果还想获得和以前一样的时钟频率，就需要将访问TLB的过程单独使用一级流水线，然而，这样会增加分支预测失败时的惩罚，也增加了load指令的延迟。
与物理Cache相对的是虚拟Cache(Virtual Cache)，顾名思义，虚拟cache可以直接使用虚拟地址进行访问。
如上图所示，在使用了虚拟cache之后，TLB仍然是需要的，因为当虚拟cache发生缺失的时候，就需要将虚拟地址转化为物理地址，然后使用物理地址去访问物理内存。
然而，使用虚拟cache存在以下两个问题：

1. 同义问题，也称作重名，即多个不同的名字对应相同的物理地址。在虚拟存储系统中，一个进程内或者不同进程间，不同的虚拟地址可以对应同一个物理内存中的位置。这就会导致在虚拟cache中，两个不同的虚拟地址虽然占据了不同的地方，但是它们实际上对应着同一个物理内存中的位置，这会引起两方面的问题，一是浪费了宝贵的cache空间，造成cache等效容量的减少，降低整体性能；二是当执行一条store指令而写数据到虚拟cache时，只会将这个虚拟地址在cache中对应的内容进行修改，而实际上，cache中其他有着相同物理地址的地方都需要被修改，否则，其他的虚拟地址读取cache时，就无法得到刚才更新过的正确值了。
2. 同名问题。即相同的名字对应不同的物理地址，在虚拟存储器中，因为每个进程都可以占用整个虚拟存储器的空间，因此不同的进程之间会存在很多相同的虚拟地址。而实际上，这些虚拟地址经过每个进程的页表转化后，会对应不同的物理地址，这就产生了同名问题：很多相同的虚拟地址对应着不同的物理地址。为了避免这一问题，最简单的办法就是在发生进程切换的时候，将虚拟cache中的所有内容都置为无效，TLB的处理方式也是类似。这种方法在进程切换很频繁的时候，会严重影响处理器的效率。另一种方法就是为每一个进程的虚拟地址都附加一个编号，这个编号称为PID(Process ID)，更通用的叫法是ASID(Address Space ID)，使用ASID相当于扩展了虚拟存储器的空间。

Virtually-Indexed, Physical-Tagged Cache
VIPT Cache在cache大小满足一定要求时，可以直接使用虚拟地址的一部分来寻址这个cache，而在cache中的tag则使用物理地址中的PFN，这种cache是目前被使用最多的，大多数的处理器都使用了这种方式。
在这样的方法中，访问Cache和TLB是可以同时进行的，假设在直接映射cache中，每个cacheline的大小为$2^b$字节，而cache set的个数是$2^L$，也就是说，寻址cache需要的地址长度是$b+L$，假设页大小为$2^k$字节，则当$k\ge L+b$时，寻址cache的低$L+b$位在虚拟地址到物理地址的转换过程中不会发生改变，因此可以直接使用虚拟地址进行寻址，这样就可以并行cache和TLB的访问，提高处理器的执行效率。当然，在进行Tag的比较时，需要使用经过TLB转换后的物理地址。
总结一下，VIPT Cache的访问可以分为两个阶段：第一个阶段，使用虚拟地址访问cache和TLB，分别在下一个阶段得到物理地址和Tag；第二个阶段，则将Tag和物理地址进行比较，以判断hit还是miss。显然，VIPT Cache可以加速cache的访问。
不过从上面也可以看到，VIPT Cache的大小是受限制的(要求$k\ge L+b$)，要继续增加cache的大小，只能增加cache的相联度，而不能增加cache的组数。