操作系统快表

什么是快表

快表(TLB - translation lookaside buffer),直译为旁路快表缓冲,也可以理解为页表缓冲,地址变换高速缓存。

由于页表存放在主存中,因此程序每次访存至少需要两次:一次访存获取物理地址,第二次访存才获得数据。提高访存性能的关键在于依靠页表的访问局部性。当一个转换的虚拟页号被使用时,它可能在不久的将来再次被使用到。

TLB 是一种高速缓存,内存管理硬件使用它来改善虚拟地址到物理地址的转换速度。当前所有的个人桌面,笔记本和服务器处理器都使用 TLB 来进行虚拟地址到物理地址的映射。使用 TLB 内核可以快速的找到虚拟地址指向物理地址,而不需要请求 RAM 内存获取虚拟地址到物理地址的映射关系。这与 data cache 和 instruction caches 有很大的相似之处。

快表(TLB)原理

当 cpu 要访问一个虚拟地址/线性地址时,CPU 会首先根据虚拟地址的高 20 位(20 是 x86 特定的,不同架构有不同的值)在 TLB 中查找。如果是表中没有相应的表项,称为 TLB miss,需要通过访问慢速 RAM 中的页表计算出相应的物理地址。同时,物理地址被存放在一个 TLB 表项中,以后对同一线性地址的访问,直接从 TLB 表项中获取物理地址即可,称为 TLB hit。

想像一下 x86_32 架构下没有 TLB 的存在时的情况,对线性地址的访问,首先从 PGD 中获取 PTE(第一次内存访问),在 PTE 中获取页框地址(第二次内存访问),最后访问物理地址,总共需要 3 次 RAM 的访问。如果有 TLB 存在,并且 TLB hit,那么只需要一次 RAM 访问即可。

TLB表项

TLB 内部存放的基本单位是页表条目,对应着 RAM 中存放的页表条目。页表条目的大小固定不变的,所以 TLB 容量越大,所能存放的页表条目越多,TLB hit 的几率也越大。但是 TLB 容量毕竟是有限的,因此 RAM 页表和 TLB 页表条目无法做到一一对应。因此 CPU 收到一个线性地址,那么必须快速做两个判断:

  1. 所需的也表示否已经缓存在 TLB 内部(TLB miss 或者 TLB hit)
  2. 所需的页表在 TLB 的哪个条目内

为了尽量减少 CPU 做出这些判断所需的时间,那么就必须在 TLB 页表条目和内存页表条目之间的对应方式做足功夫。

全相连 - full associative

在这种组织方式下,TLB cache 中的表项和线性地址之间没有任何关系,也就是说,一个 TLB 表项可以和任意线性地址的页表项关联。这种关联方式使得 TLB 表项空间的利用率最大。但是延迟也可能相当的大,因为每次 CPU 请求,TLB 硬件都把线性地址和 TLB 的表项逐一比较,直到 TLB hit 或者所有 TLB 表项比较完成。特别是随着 CPU 缓存越来越大,需要比较大量的 TLB 表项,所以这种组织方式只适合小容量 TLB。

直接匹配

每一个线性地址块都可通过模运算对应到唯一的 TLB 表项,这样只需进行一次比较,降低了 TLB 内比较的延迟。但是这个方式产生冲突的几率非常高,导致 TLB miss 的发生,降低了命中率。

比如,我们假定 TLB cache 共包含 16 个表项,CPU 顺序访问以下线性地址块:1, 17 , 1, 33。当 CPU 访问地址块 1 时,1 mod 16 = 1,TLB 查看它的第一个页表项是否包含指定的线性地址块 1,包含则命中,否则从 RAM 装入;然后 CPU 方位地址块 17,17 mod 16 = 1,TLB 发现它的第一个页表项对应的不是线性地址块 17,TLB miss 发生,TLB 访问 RAM 把地址块 17 的页表项装入 TLB;CPU 接下来访问地址块 1,此时又发生了 miss,TLB 只好访问 RAM 重新装入地址块 1 对应的页表项。因此在某些特定访问模式下,直接匹配的性能差到了极点。

组相连 - set-associative

为了解决全相连内部比较效率低和直接匹配的冲突,引入了组相连。这种方式把所有的 TLB 表项分成多个组,每个线性地址块对应的不再是一个 TLB 表项,而是一个 TLB 表项组。CPU 做地址转换时,首先计算线性地址块对应哪个 TLB 表项组,然后在这个 TLB 表项组顺序比对。按照组长度,我们可以称之为 2 路,4 路,8 路。

经过长期的工程实践,发现 8 路组相连是一个性能分界点。8 路组相连的命中率几乎和全相连命中率几乎一样,超过 8 路,组内对比延迟带来的缺点就超过命中率提高带来的好处了。

这三种方式各有优缺点,组相连是个折衷的选择,适合大部分应用环境。当然针对不同的领域,也可以采用其他的 cache 组织形式。

TLB表项更新

TLB 表项更新可以有 TLB 硬件自动发起,也可以有软件主动更新:

  1. TLB miss 发生后,CPU 从 RAM 获取页表项,会自动更新 TLB 表项
  2. TLB 中的表项在某些情况下是无效的,比如进程切换,更改内核页表等,此时 CPU 硬件不知道哪些 TLB 表项是无效的,只能由软件在这些场景下,刷新 TLB。

在 Linux kernel 软件层,提供了丰富的 TLB 表项刷新方法,但是不同的体系结构提供的硬件接口不同。比如 x86_32 仅提供了两种硬件接口来刷新 TLB 表项:

  1. 向 cr3 寄存器写入值时,会导致处理器自动刷新非全局页的 TLB 表项
  2. 在 Pentium Pro 以后,invlpg 汇编指令用来无效指定线性地址的单个 TLB 表项无效