《Operating Systems: Three Easy Pieces》学习笔记(十五) 分页：快速地址转换（TLB）
对每次内存访问，硬件先检查 TLB，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表 （其中有全部的转换映射）。因此，更好的名称应该是地址转换缓存（address-translation cache）。
TLB 的基本算法
TLB 命中（TLB hit）,直接取
TLB 未命中，硬件访问页表来寻找转换映射，并用该转换映射更新 TLB，当 TLB 更新成功后，系统会重新尝试该指令
示例：访问数组
访问 a[1]后，TLB 有了 VPN=06 的映射，下次访问 a[2]或 a[0]也能 TLB 命中.
硬件缓存背后的思想是利用指令和数据引用的局部性（locality）。通常有两种局部性：
时间局部性（temporal locality）和空间局部性（spatial locality）。时间局部性是指，最近访问过的指令或数据项可能很快会再次访问。空间局部性是指，当程序访问内存地址 x 时，可能很快会访问邻近 x 的内存。
谁来处理 TLB 未命中
硬件：
发生未命中时， 硬件会“遍历”页表，找到正确的页表项，取出想要的转换映射，用它更新 TLB，并重试该指令
一个例子是 x86 架构，它采用固定的多级页表（multi-level page table）
软件：
精简指令集计算机上。
发生 TLB 未命中时，硬件系统会抛出一个
异常（见图 19.3 第 11 行），这会暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序（trap handler）。接下来你可能已经猜到了，这个陷阱处理程序是操作系统的一段代码，用于处理 TLB 未命中。这段代码在运行时，会查找页表中的转换映射，然后用特别的“特权”指令更新 TLB，并从陷阱返回。此时，硬件会重试该指令（导致 TLB 命中）。可能导致
无限递归，比如陷阱处理程序中也有未命中的。可以把 TLB 未命中陷阱处理程序直接放到物理内存中 [它们没有映射过（unmapped），不用经过地址转换]。或者在 TLB 中保留一些项，记录永久有效的地址转换，并将其中一些永久地址转换槽块留给处理代码本身，这些被监听的（wired）地址转换总是会命中 TLB。
TLB 的内容
VPN ｜ PFN ｜ 其他位
VPN和PFN同时存在于TLB中，因为一条地址映射可能出现在任意位置（用硬件的术语，TLB 被称为全相联的（fully-associative）缓存）。硬件并行地查找这些项，看看是否有匹配。
其他位:TLB 通常有一个有效（valid）位，用来标识该项是不是有效地转换映射。通常还有一些保护（protection）位，用来标识该页是否有访问权限。例如，代码页被标识为可读和可执行，而堆的页被标识为可读和可写。还有其他一些位，包括地址空间标识符（address-space identifier）、脏位（dirty bit）等。
上下文切换时对 TLB 的处理
TLB 中包含的虚拟到物理的地址映射只对当前进程有效，对其他进程是没有意义的。
一些系统增加了硬件支持，实现跨上下文切换的 TLB 共享。比如有的系统在 TLB 中添加了一个地址空间标识符（Address Space Identifier，ASID）。可以把 ASID 看作是进程标识符（Process Identifier，PID），但通常比 PID 位数少（PID 一般 32 位， ASID 一般是 8 位）。
ASID 标识不同进程，可以存在相同的 VPN。
操作系统在上下文切换时，必须将某个特权寄存器设置为当前进程的 ASID。
上图表示两个进程共享同一物理页（例如代码段的页），因为是只读和执行的，可以共享，比如代码段存放的内存。
TLB 替换策略
- 最少使用（least-recently-used，LRU）
- 随机（random）策略
随机（random）策略可以避免极端情况，如一个程序循环访问 n+1 个页，但 TLB 大小只能存放 n 个页，每次访问内存都会触发 TLB 未命中
实际系统的 TLB 表项
这个例子来自 MIPS R4000[H93]，它是一种现代的系统，采用软件管理 TLB。
MIPS R4000 支持 32 位的地址空间，页大小为 4KB。所以在典型的虚拟地址中，预期会看到 20 位的 VPN和 12 位的偏移量。但是，你可以在 TLB 中看到，只有 19 位的 VPN。事实上，用户地址只占地址空间的一半（剩下的留给内核），所以只需要 19 位的 VPN。VPN 转换成最大 24 位的物理帧号（PFN），因此可以支持最多有 64GB 物理内存（224 个 4KB 内 存页）的系统。
3 个一致性位（Coherence，C），决定硬件如何缓存该页（其中一位超出了本书的范围）；脏位（dirty），表示该页是否被写入新数据（后面会介绍用法）；有效位（valid），告诉硬件该项的地址映射是否有效。还有没在图 19.4 中展示的页掩码（page mask）字段，用来支持不同的页大小。
MIPS 的 TLB 通常有 32 项或 64 项，大多数提供给用户进程使用，也有一小部分留给操作系统使用。操作系统可以设置一个被监听的寄存器，告诉硬件需要为自己预留多少 TLB 槽。这些保留的转换映射，被操作系统用于关键时候它要使用的代码和数据，在这些时候，TLB 未命中可能会导致问题（例如，在 TLB 未命中处理程序中）。
由于 MIPS 的 TLB 是软件管理的，所以系统需要提供一些更新 TLB 的指令。MIPS 提供了 4 个这样的指令：
TLBP，用来查找指定的转换映射是否在 TLB 中；TLBR，用来将 TLB 中的内容读取到指定寄存器中；TLBWI，用来替换指定的 TLB 项；TLBWR，用来随机替换一个 TLB 项。操作系统可以用这些指令管理 TLB 的内容。
当然这些指令是特权指令
小结
如果一个程序短时间内访问的页数超过了 TLB 中的页数，就会产生大量的 TLB 未命中，运行速度就会变慢。这种现象被称为超出 TLB 覆盖范围（TLB coverage）。可以用更大的页来缩小页的数量，增加命中率
访问 TLB 很容易成为 CPU 流水线的瓶颈，尤其是有所谓的物理地址索引缓存（physically-indexed cache）,这是 CPU 内部的缓存。有了这种缓存，地址转换必须发生在访问该缓存之前，这会让操作变慢。虚拟地址索引缓存（virtually-indexed cache）解决了一些性能问题，但也为硬件设计带来了新问题。
物理地址索引缓存详见Physically indexed, physically tagged (PIPT) caches