页式内存管理 - TLB

这是 《Operating System: Three Easy Pieces》 的第 8 篇读书笔记。

有关 页式内存管理 介绍 。

主要介绍的是操作系统里加速页式内存管理一种方法。

上一篇笔记中,我们了解到,使用页式内存管理会导致昂贵的性能开销。因为要存储大量的页表,还要一次额外的内存访问查询虚拟页对应的物理页。

因此有了原文的这章节 《 Paging: Faster Translations (TLBs) 》

如何加速页式内存管理中的地址翻译过程呢?如何去掉那一次额外的内存访问?需要硬件提供什么支持?操作系统在这其中又需要做些什么?

当我们(其实是OS)想要事情变得更快的时候,操作系统通常会向一个老朋友请求帮助——硬件。

TLB ( Translation-Lookaside Buffer ),一小块存在于 内存管理单元 (MMU,Memory Management Unit)中的芯片,在虚拟地址翻译过程中提供硬件缓存功能,就是我们所需要的。

当然,配合它的作用,更贴切的名字叫做 地址翻译缓存(address-translation cache)。

在要去查页表之前,MMU 会先去 TLB 里面查询虚拟地址所对应的物理地址是否在里面(这个过程非常快),如果是,就直接返回,如果没有则再访问内存。

听起来挺简单的一个策略,实际中,这种策略的确令人满意。

基于 TLB 的基本内存访问逻辑

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)   // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else    // TLB miss
    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()

假设我们使用的内存模型还是跟上一节一样,下面讲解下上面代码。

基本的流程跟上一小节差不多,补不过多了些步骤,首先从访问的地址中提取出虚拟页的页号 VPN,接着检查下 TLB 中是否有缓存。
如果有,那么就称为发生了一次 TLB hit,接下来就从 TLB 中拿到 PTE,继续地址翻译的过程(这个过程是非常快的)。
如果没有,那么就称为发了一次 TLB miss,操作系统就需要去内存中加载对应的 PTE,然后把 PTE 插入到 TLB 中,重试这个过程,就可以得到物理内存的地址了。

TLB 被设计为 硬件的缓存,访问它的代价是远远要比访问内存少的,因此如果发生了 TLB hit,那么地址翻译过程是非常快速的。
但是,如果发生了 TLB miss,那么整个地址翻译过程的代价要比不用 TLB 的那个过程还要大,因为加上了 PTE 插入和 RetryInstruction() 这两个过程,甚至还可能更多(在遇到复杂的页表结构时)。

因此,我们希望的是能尽量避免 TLB miss。

一个访问数组的例子

下面我们举个例子来说明 TLB 是如何加速内存地址翻译过程。

假设我们需要访问 一个拥有 10 个整型的数组(整型占 4 字节),数组起始在虚拟地址 100 处。我们的虚拟地址空间的 8 位的,它拥有 16 字节的页大小。那么一个虚拟地址需要用 4 位大小来表示 VPN,剩下的 4 (2 ^ 4 = 16) 位来表示偏移( offset )。

如上图所示,我们的数组第一个元素(a[0])在 VPN = 06, offset = 04 处,剩下的元素分别在 VPN = 7 (a[3]...a[6]) 和 VPN = 8 (a[7]...a[9]) 对应的虚拟页上。

现在我看下一段简单的代码:

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

当第一个元素被访问 a[0] 的时候,操作系统要加载虚拟地址100,假设系统是第一次访问这篇内存,那么理所当然的就会发生一次 TLB miss。
现在访问到第二个元素 a[1] 了,由于前面访问 a[1] 的时候加载过一次 VPN = 6 对应的 PTE 了,所以这次很幸运的,a[1] 所在的虚拟页在 TLB 中有对应 PTE 缓存,这次内存访问很快。a[2] 跟 a[1] 的访问情况是一样的。

接下来,要访问 a[3] 了,不幸的是,a[3] 所在的虚拟页在 TLB 中没有缓存,TLB miss 再一次发生。而访问 a[4] a[6] 的时候不会发生 TLB miss。而访问 a[7] 发生的是最后一次 TLB miss。

我们来统计一下,TLB 命中率(hit rate),应该是 70 %,(7 hit / 10 TLB access)。看到这里,不知道读者有没有想到一个词,空间局部性(spatial locality)。

我们还注意到,如果我们把页大小扩大为 32 字节的话,这一次的数组访问会发生更少的 TLB miss。实际中,一个页大小通常是 4 KB,大数组访问的话可能仅仅会遇到一次 TLB miss。

另外,如果我们再这次遍历之后再一次遍历那个数组,操作系统将得到 100 % 的 TLB 命中率(假设 TLB 装得下那么多的缓存)。这其实都是得益于空间局部性和临时局部性

谁来处理 TLB miss?

操作系统 或者 硬件。

早些时候,硬件拥有复杂的指令集(CISC, complex-instruction set computers),那些搞硬件的信不过写操作系统的,因此处理 TLB miss 的任务就由硬件完全负责。
为了知道页表在哪里,硬件通过一个寄存器(page table base register)找到内存中的页表,然后遍历其中所有元组,找到对应的 PTE,然后重新重试。

现代操作系统更多的采用精简指令集(RISC,reduced-instruction set computers),硬件不支持 TLB miss 的逻辑了,因此处理 TLB miss 的任务就由 OS 负责,

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)   // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else // TLB miss
    RaiseException(TLB_MISS)

当发生 TLB miss 的时候,操作系统的执行流转入一段特定的代码(trap handler),运行这段代码操作性必须进入 privileged 状态(内核态吧,我想),找到对应的 PTE 之后,通过特殊的指令去更新 TLB,然后从“陷阱”中返回,操作性发起指令重试,这次就会发生 TLB hit 了。

大家可能感觉到了,这段特殊的代码其实是 OS 预先准备好的了,有点类似高级语言的回调函数。

注意,这次的 从“陷阱”中返回后执行的指令不是执行进入 trap 之后的指令,而导致 trap handler 发生的指令。因此才会发生一次 TLB hit 嘛。
另外,还要注意的是避免 TLB miss 的死循环。

TLB 里的内容

一个 TLB 元组可能会有这样的结构 VPN | FPN | other bits

other bits 可能包括

  • valid bit 表示这个元组是否有效
  • protection bit 表示这个页是否有权限访问
  • 可读可写可执行位
  • dirty bit 表示该物理页是否被修改过

上下文切换下的 TLB

一个显然的问题,进程上下文切换之后,TLB 里的内容改怎么处理。当然,TLB 可以保存全部进程的 TLB 缓存,但是这不实际,当运行的进程非常非常多,全部保存的代价就会非常昂贵。

因此,TLB 是随着进程切换而切换的。

但是如果进程频繁切换由此带来的 TLB 切换也是非常惊人的,如果 TLB 全部由现在占用着 CPU 的进程占有的话。

其实也有一个简单的方法,就是在 TLB 每个 Entry 里加上点东西,表明这个 Entry 是属于哪个进程的,这个“东西”叫做 Address Space Identifier (ASID),可是认为是进程 ID 吧。

这样子的话,TLB 就不用在进程每次切换的时候都刷新 TLB 了,只是在 PLB 中查询 PTE 的时候,如果发现当前 PTE 不是属于当前进程的,就替换好了。

这又抛个问题,只是简单的删除么?哈哈,这又涉及到下面一小节了。

TLB 的替换策略

这其实是作为一个缓存最常遇到的问题——过期的缓存,或者无效的缓存,应该选择怎样去替换才能使的 miss 率最小。

典型的就是如 LRU (least recently used) 策略,还有随机(random)替换策略这些。

为了支持这些策略,可能需要硬件和操作系统做些额外的支持,当然为了更高的命中率,这都是值得的。

现实中的 TLB Entry 是什么样子的?

书中举例了 MIPS R4000 这个操作系统的 TLBs 结构,它是由软件管理。

MIPS R4000 支持 32 位虚拟地址空间,有着 4 KB 的虚拟页,一个虚拟地址划分为 20 位的 VPN 和 12 位的偏移。

MIPS 提供四个指令供操作 TLB:

  • TLBP,检测是否有个对应的 虚拟页->物理页 的翻译
  • TLBR,读取一个 TLB Entry 到寄存器中
  • TLBWI,替换一个 TLB Entry
  • TLBWR,随机替换一个 TLB Entry

具体的介绍大家参考上面的引用吧,读读经典的论文还是很有趣的。

总结

本节中,我们看到了 TLB 是如何加速虚拟地址翻译的。

但是 TLB 可能不是都受所有软件的欢迎,比如说数据库管理系统(DBMS),因为它需要自己管理页,操作系统提供的策略可能对于它并不是最快的。

参考
《Translation Lookaside Buffers 》
《MIPS R4000 Microprocessor User’s Manual》

Comments
Write a Comment