【OSTEP】分页: 快速地址转换(TLB) | TLB命中处理 | ASID 与页共享 | TLB替换策略: LRU策略与随机策略 | Culler定律

💭 写在前面

本系列博客为复习操作系统导论的笔记，内容主要参考自：

• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy PiecesA. Silberschatz, P. Galvin, and G. Gagne,
• Operating System Concepts, 9th Edition, John Wiley & Sons, Inc., 2014, ISBN 978-1-118-09375-7.Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

0x00 引入：如何加速地址转换？

使用分页作为核心机制以实现虚拟内存，可能会带来较高的性能开销。因为要使用分页，就要将内存地址空间切分成大量固定大小的单元(页)，并且需要记录这些单元的地址映射信息。因为这些映射信息一般存储在物理内存中，所以在转换虚拟地址时，分页逻辑上需要一次额外的内存访问。每次指令获取、显式加载或保存，都要额外读一次内存以得到转换信息，这慢得无法接受。因此我们面临如下问题。

关键问题：如何加速地址转换

如何次啊能加速地址转换，尽量避免额外的内存访问？需要什么样的硬件支持？操作系统该如何支持？

Page table is per-process data structure and is kept in main memory.

页表是每个进程的数据结构，保存在主内存中。

每个数据/指令访问都需要两次内存访问（一个是页表，一个是数据/指令）

The two memory access problem can be solved by the use of a special fast-lookup hardware cache inside the MMU called associative memory or translation look-aside buffers (TLBs).

两个内存访问问题可以通过在MMU内部使用一种特殊的快速查找硬件缓存来解决，这种硬件缓存被称为关联内存或 地址转换旁路缓冲存储器（TLB）。

• 一个典型的TLB有32、64或128个条目（小的--需要替换策略）。
• TLB 是通过完全关联方法管理的，这意味着任何给定的翻译可以在 TLB 的任何地方。
• 其他位：有效位、保护位、地址空间标识符（ASID）、脏位

0x01 TLB 中的地址转换

Hardware searches the entire TLB in parallel to find the desired translation

命中 (TLB hit) ： If p (VPN) is in a TLB, get f (PFN) out from the TLB.

未命中 (TLB hit)：Otherwise, get f (PFN) from the page table in memory. (额外开销)

一些条目可以被连接起来，以便永久快速访问，永久性快速访问。通常情况下，TLB条目是为关键的内核代码布线的。

0x02 TLB 基本算法

💬 TLB 控制流算法：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == TRUE) {  // TLB Hit
  if (CanAccess(TlbEntry.ProtectBit) == True) {
    offset = VirtualAddress & OFFSET_MASK
      PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
      AccessMemory(PhysAddr)
  } else {
    RaiseException(PROTECTION_ERROR)
  }
} else {    // TLB Miss
  PTEAddr = PTBR + (VPN * sizeof(PTE))
  PTE = AccessMemory(PTEAddr)  // 额外的内存引用 → 大的开销 !
  if (PTE.Valid == False) RaiseException(SEGMENTATION FAULT)
  else {
    tLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)  // 在这之后，翻译在TLB中被
                           // 找到，并且内存引用被快速处理。参考被快速处理。
    RetryInstruction()
  }
}

示例：访问数组

来看看 TLB 是如何提高性能的：

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

3次失误，7次击中。因此，TLB 的命中率为70%。

The TLB improves performance due to spatial locality (空间定位)

0x03 局域性：缓存设计背后的理念

时间定位：Temporal Locality

最近被访问的指令或数据项很可能在未来很快被重新访问。

空间定位：Spatial Locality

如果一个程序访问地址为x的内存，它可能很快就会访问x附近的内存

0x04 谁来处理 TLB 未命中？硬件或软件！

Hardware-managed TLB (mostly on CISC machine)

硬件管理的TLB（主要在CISC机器上）。

• 硬件必须确切地知道页表在内存中的位置以及它们的确切格式
• The hardware would “walk” the page table, find the correct page-table entry and extract the desired translation, update and retry instruction.  硬件将 "走过" 页表，找到正确的页表条目并萃取所需的翻译、更新和重试指令。
• 比如：Intel x86 (CR3寄存器指向当前页表的地址)

Software-managed TLB (on RISC machine)

• On a TLB miss, the hardware raises exception (trap handler).  在 TLB 缺失时，硬件会引发异常（陷阱处理程序）。
• Trap handler is code within the OS that is written with the purpose of handling TLB miss.  陷阱处理程序是操作系统中的代码，其目的是为了 处理TLB缺失。
• 比如 MIPS R10k，Sun的SPARC v9……

💬 TLB Control Flow Algorithm (Software Managed TLB)

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

0x05 地址空间标识符（ASID）

❓ 猜想：两个进程可以共享一个 TLB 吗？

Can’t distinguish which entry is meant for which process

💡 解决方案：增添一个 地址空间标识符（Adress Space Identifier，ASID）。

0x06 页共享（Page Sharing）

两个进程共享一个页：

• 进程1与进程2共享物理页101。
• P1将该页映射到其地址空间的第10页。
• P2将此页映射到其地址空间的第50页。

Sharing of pages is useful as it reduces the number of physical pages in use.

0x07 TLB替换策略（Replacement Policy）

TLB 和其他缓存一样，还有一个关键问题需要考虑 —— 内存替换问题（cache replacement）。

向 TLB 中插入新项时，会替换一个旧项，那么问题来了，应该替换哪一个呢？

❓ 思考：在向 TLB 添加新项时，应该替换哪一个旧项？

我们的目标自然是为了减少 TLB 为命中率，即提高命中率，从而改进性能……

💡 策略：LRU策略 和 Random策略

① 替换最最少使用的项：LRU (Least Recently Used)

Evicts an entry that has not recently been used.

• 一种常见的策略，替换最近最少使用的项（LRU）。
• 利用内存引用流中的局域性，假定最近没有用过的项是最适合卷铺盖走人的项目（不养闲人）。

② 随机策略：Random

Evicts an entry at random.

• 这种策略很简单，就是随机选择一项换出去，直接无脑叉出去就行。
• 并且可以避免一种极端情况，比如一个程序循环访问 n+1 页，但 TLB 的大小只能存放 n 个页，此时之前看似合理的 LRU 策略会表现的像个神经病，因为每次访问内存都会触发 TLB 未命中。但是这里如果选用随机策略，在这种情况下就会好太多了！

0x08 实际系统里的 TLB

最后，我们来看一下真实的 TLB，这个例子来自于 MIPS R4000，它是一种现代的系统。

- 支持32位地址空间的4KB页（20位虚拟+12位偏移）

卡勒定律（Culler Law）：RAM 不总是 RAM

随机存取存储器（RAM）暗示你访问 RAM 的任意部分都一样快。虽然一般这样想 RAM 没错，但因为 TLB 这样的硬件/操作系统功能，访问某些内存页的开销比较大，尤其是没有被 TLB 缓存的页。因此，最好记住这个实现的窍门：RAM 不总是 RAM。有时候随机访问地址空间，尤其是 TLB 没有缓存的页，可能导致严重的性能损失。

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！