转译后备缓冲

什么？时间太慢？加缓存！

利用时空局部性 (temporal and spatial locality)，MMU 中的转译后备缓冲 (Translation Lookaside Butter, TLB) 通过缓存高频访问的 PTE 来加速地址翻译过程。

TLB

一个 TLB 项包括 VPN，PFN 和其他位如有效位，保护位等。

TLB 是全相联映射 (fully associative) 的：对于给定 VPN 的搜索是并行 (in parallel) 的，速度相当快。

Paging address translation with TLB
c
while (!Success) {  // retry instruction
    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
        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)
}

TLB 未命中的处理

硬件处理：硬件通过 PTBR 查找页表，找到对应的 PTE，更新 TLB 中后重试指令。

OS 处理：硬件触发异常，OS 切入并运行陷阱处理器，搜索页表，使用特权指令更新 TLB 后从陷阱返回 (return from trap)，硬件重试指令。

  • 系统调用后的从陷阱返回是从引发陷阱的指令之后继续执行的
  • TLB 未命中后的从陷阱返回是从引发陷阱的指令之前继续执行的，因此是重试指令

OS 处理可以使用自定义的算法与数据结构，更为灵活简单。

线程共享

上下文切换后，TLB 能在不同线程间共享吗？

  • 不能：将 TLB 中的所有项的有效位置 0，从而清空 (flush) TLB。
    • 每次线程切换后都将产生大量的 TLB 未命中
  • 能：在 TLB 中添加额外的地址空间标识符 (address space identifier, ASID) 对不同线程的 TLB 缓存进行标记。MMU 每次需要查找 VPN 与 ASID 两个字段。

替换策略

TLB 满后增加新条目，应当遵循怎样的替换策略？=> 最近最少使用 (least recently used, LRU)

阅读

Chapter 19 – Paging: Faster Translation (TLBs), OSTEP, http://pages.cs.wisc.edu/~remzi/OSTEP/vm-tlbs.pdf