19. Translation Lookaside Buffers

Paging: Faster Translations (TLBs)

使用分页可能会导致高性能开销，因为分页需要大量的映射信息。由于该映射信息存储在物理内存中，所以对其进行查找要产生额外的内存开销。
为了解决这一问题，我们就需要依赖OS的老朋友硬件，在芯片的MMU中添加TLB（translation-lookaside buffer）。每次引用虚拟内存时，硬件首先检测TLB，查看其是否保留了所需的地址转换。如果保留了，那么无须查看page table。

1. TLB Basic Algorithm

下图给出了硬件如何处理虚拟地址转化的示意图

2. Example: Accessing An Array

为了更好地了解TLB，我们举一个例子。
假设内存中有10个4字节整数数组，从虚拟地址100开始。虚拟地址空间为8位，具有16字节page，因此虚拟空间分为4位VPN和4位offset。
下图展示了数组的位置：

让我们进行如下代码操作：

int sum = 0;
for (int i = 0; i < 10; i++)
{
	sum += a[i];
}

我们主要集中注意力于获取数组a中的元素。首先是获取a[0]，CPU看到虚拟地址100，硬件从中提取VPN = 06并检查TLB是否保留该VPN。假设这是第一次访问该数组，那么肯定TLB Miss，然后TLB保留了VPN = 06。继续获取a[1]、a[2]会有TLB Hit。然后获取a[3]有TLB Miss； a[4]、a[5]、a[6]有TLB Hit，如此进行下去。

3. Who Handles The TLB Miss?

我们必须回答一个问题：谁处理TLB Miss。
对此有两种方法，一种是通过硬件，一种是通过软件(OS)。
在以前的计算机中是通过硬件处理，现今的计算机中是通过软件处理。

下图是软件处理过程：

4. TLB Contents: What’s In There?

我们知道TLB是用来干什么的了，但是TLB里面有什么呢？
A TLB entry可能如下所示：

注意上图所示，VPN和PFN存在于每一个entry中。
更有趣的是 other bits，里面通常有上一章讲述的有效位、保护位等一系列特殊作用位。

5. TLB Issue: Context Switches

使用TLB时，在进程之间切换必须十分小心，以确保即将运行的进程不会使用其他进程的地址转换。
我们假设有一个进程P1正在运行，它的第10个虚拟地址page映射到物理frame 100。还有个进程P2，P2是第10个虚拟地址page映射到物理frame 170。马上就要进行进程转换，从P1转换到P2，如果两个进程的entry都在TLB中，如下：

上图产生了一个问题，VPN = 10转换成PFN = 100或PFN = 170，但是硬件无法区别哪个转换代表哪个进程，所以对TLB就要做进一步改进。
一种方法就是每次进行进程转换的时候刷新TLB。意思是每次进程转换都把TLB清空，但是这就增加TLB Miss的几率而且增加了开销。
另一种方法就是硬件支持。在硬件系统的TLB中提供address space identifier (ASID)，你可以将ASID视为进程标识符，通常情况下ASID位数非常少。

对上面遗留的问题就有了如下解决方法：

6. Issue: Replacement Policy

其实TLB就和Cache差不多。
在后面介绍page与磁盘进行交互的时候会详细介绍策略。

7. A Real TLB Entry

阴影表示未使用的位。

G（全局位）：用于进程之间全局共享的page。
C（Coherence）：确定硬件如何缓存page。