TLB - 加速地址翻译

上一篇《页式内存管理 - 简介》 介绍了页式内存管理的机制,留下了一个问题,那就是 ,因为多访问了一次内存。

有没有办法减少内存访问次数的办法呢?

有。那就是 Cache,TLB (Translation Lookaside Buffer)——一小块集成在 MMU 中的芯片。

在每一次内存访问里,硬件先看下 TLB 中是否已经有想要的 Page Entry——如果有,那就返回不用访问内存了(这是非常快的,和访问内存差几个数量级),如果没有,再去访问内存。

TLB 的基本算法

加上 TLB 这个硬件之后,访问内存的逻辑变成了下面这样:

VPN = (VirtualAddress & VPN_MASK) >> SHIFT

(Success, TLBEntry) = TLB_Lookup(VPN)

if (Success == True)
    if (CanAccess(TLBEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TLBEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else if (CanAccess(PTE.ProtectBits) == False)
        RaiseException(PROTECTION_FAULT)
    else
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

算法比较简单,基本上涉及到 Cache 的业务逻辑都是这样。

一个例子:访问连续的数组

00

地址空间如上图,8 位虚拟地址空间,高 4 位用作 VPN,低 4 位用作页内偏移,因此一个页的大小是 16 字节(2^4)。

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

我们来解释下上面的代码:

  1. 当我们开始访问数组第一个元素,CPU 发起一个对虚拟内存地址 100 的访问,硬件抽取出 VPN=6,然后查询 TLB,假设 TLB 没有经过“预热”,这时候会发生 TLB miss。此时新的的 TLB Entry 将会被插入到 TLB 中
  2. 下一个要访问的元素是 a[1],这时候情况就好起来了,TLB hit 了!因此此时 VPN -> FPN 的 Entry 已经被 load 进来,所以直接就能知道 FPN,不用再多访问一次内存
  3. 下一个要访问的 a[2] 也是如此
  4. 到 a[3] 了,不幸的是此时又遇到了一个 TLB miss,处理情况如 1。接下来的 a[3]...a[6] 访问会触发 TLB hit。
  5. 最后到了 a[7]、a[8]、a[9],情况如 4。

我们总结下 TLB 的行为,miss, hit, hit, miss, hit, hit, hit, miss, hit, hit,TLB 命中率达到 70%。

大家可能想到了,TLB 命中率提升的关键点在于 空间局部性
把要访问的元素尽量放在相邻的位置有助于提升 TLB 命中率,加快程序运行速度。

另外一个可选的优化手段是可以调大 page size,这样一次能访问更多的数据,不用频繁的查询页表也是可以加快程序运行速度的。

谁来处理 TLB Miss

第一个,硬件。在早些时候,支持 CISC 指令集的硬件可以自动地帮 OS 做这个事情(因为那时候设计芯片的人不相信写操作系统的人)。
当发生 TLB Miss,硬件必须找到进程的页表,然后从进程的页表里找到 PTE,然后计算出提取出 FPN,接着访问内存,更新 TLB,然后通知操作系统。

早些时候的 Intel x86 架构处理器使用硬件管理 TLB 的策略,可以使用多级页表,当前页表的位置存在 CR3 寄存器当中。

第二个,OS,操作系统利用 trap 来处理 TLB miss。当发生 TLB miss 了,操作系统能收到硬件的通知,让调用相应的 TLB miss handler,利用“特权指令”更新 TLB。

有个地方要注意:之前的 return-from-trap 指令是恢复执行流到 system call 的下一条指令,而在 TLb miss handler 处理之后,执行流是要回到陷入 trap 之前的一条指令的,也就说说要再 retry 一次,这时候就发生了一次 TLB hit。

既然有 retry,操作系统这时候就要警惕户不会发生无限循环的 retry 了。

软件管理 TLB(software-managed TLB)的优点是灵活简单,操作系统能用任何它想要的数据结构去实现页表,不用 care 硬件的限制。

TLB 存什么 ?

VPN | FPN | other bits

other bits 存储这个页面的一些权限信息

使用 TLB 之后,进程切换怎么做?

有了 TLB 之后,进程间切换逻辑要注意下。因为 TLB 中包含的仅仅是当前运行中的进程的 虚拟地址物理地址 的映射记录。(因为如果通过 TLB 查到的欲访问物理地址此时还不在内存中,直接访问内存不是完蛋了嘛),这些记录对其他的进程来说是没有意义的。

因此,当发生进程间切换的时候,OS 必须确保准备运行的进程的地址翻译行为不会意外地影响到之前的进程。

例如下图, 属于进程 P1, 属于进程 P2:
01

那进程切换之后,对于 VPN=10 这个虚拟内存地址的访问将会出现偏差。

一种解决方案是再给进程维护一个 TLB 的数据结构,当进程切换的时候把下一个进程的 TLB 状态全部恢复,这是可行的,不过代价也比较昂贵。

另外一种解决办法是给 TLB Entry 加一个标识字段,标识这个 TLB Entry 属于哪个进程的就可以了。
02

当然,也可能发生下图的情况,不同的进程共享了同一个物理 frame
03

这种情况可能是合理的,比如说共享库,这样可以减少内存的不必要消耗。

TLB Cache 的替换策略

一般的就是 LRU ( least recently used ) 最少最近使用替换策略吧。

一个真实的 TLB 例子

总结

TLB 是一小块专门用于加速地址翻译过程的芯片。

通常情况下,对付一般程序 TLB 的命中率可能可以很好,但是对付那些需要大且多页面的程序,需要经常随机访问内存、硬盘的程序,可能效果就不是很好。比如说数据库。

还有个叫做 physically-indexed cachevirtually- indexed cache 的东西,可以用于加速 地址翻译,这部分还没有研究。详细的可以 Google。

参考
《Translation Lookaside Buffers》

Comments
Write a Comment