按需分页：计算有效内存访问时间

Question

我无法理解这个问题的答案：

考虑使用带有 TLB 寄存器的一级分页的操作系统。如果页面错误率为 10%，需要时应重新加载脏页，则计算有效访问时间：

• TLB 查找 = 20 ns
• TLB命中率=80%
• 内存访问时间 = 75 ns
• 交换页面时间 = 500,000 ns
• 50% 的页面是脏的。

答案：

T = 0.8(TLB+MEM) + 0.2(0.9[TLB+MEM+MEM] + 0.1[TLB+MEM + 0.5(磁盘) + 0.5(2磁盘+MEM)]) = 15,110 ns

你能解释一下为什么吗？

Answer 1

在这种情况下，“有效”时间意味着“预期”或“平均”时间。因此，您需要计算每种情况下访问该页面所需的时间，并将每种情况乘以它的概率。由于将情况分为多个级别，该表达式有些复杂。案例有：

• 80% 的时间物理地址位于 TLB 缓存中。这让我们有 80% 的时间访问 TLB 寄存器以及访问页面本身：

  0.8(TLB + MEM)

• 剩余 20% 的时间不在 TLB 缓存中。这又分为更多情况，所以它给了我们

  0.2(loooong expression)

  （该表达式实际上没有那个括号，但我将其视为一个拼写错误，因为没有它，系数加起来不会等于 1，并且它不会如果他们不这样做，那就有意义）。案例有：
  • 90%（其中 20%）的时间页面仍然被映射，但地址已超出缓存，因此我们必须从页面映射中读取额外的内存。所以 90% 的时间是访问 TLB 寄存器加上访问页表加上访问页面本身：

    0.9(TLB + MEM + MEM)

    。提到了一级分页，所以这里只是 1 次额外的内存访问，但实际实现通常有两级分页，因此会有 2 次额外的内存访问。
  • 10%（在这 20% 中；表达式暗示了这一点，但问题不清楚，而是暗示总体为 10%）页面需要从磁盘加载的次数。这使得对 TLB 寄存器的（失败）访问和对页表（失败）的访问比加载页面所需的次数少了 10%。要加载它，它必须为其腾出空间，因此它必须放下另一个页面。这分为两个选项：
    • 50%要删除的页面是干净的，因此系统只需要读取新内容即可：

      0.5(Disk)

      。
    • 50%要删除的页面是脏的，因此系统需要将其写入磁盘

      (MEM+Disk)

      并读入新内容

      (Disk)

      ，给出

      0.5(2Disk + MEM)

我认为在最后两种（交换）情况中应该包含一些额外的内存访问，因为需要两次访问来标记页表中的前一页不可用和新页可用。

这也是非常不现实的，因为在实际系统中，当需要在页面中留出阅读空间时，系统总是选择一个干净的页面来替换。为了确保它有干净的页面，有一个后台进程会检查脏页面并将其写出。它需要一些计算资源，因此它实际上应该稍微计入内存访问，但要少得多，因为页面错误不需要等待写入完成。

这个表达其实是错误的。应该是其中之一

T = 0.8(TLB + MEM) + 0.2((0.9(TLB + MEM + MEM)) + 0.1(TLB + MEM + 0.5(磁盘) + 0.5(2 磁盘 + MEM)))

如果页面错误占 TLB 未命中的 10% 或

T = 0.8（TLB + MEM）+ 0.1（TLB + MEM + MEM）+ 0.1（TLB + MEM + 0.5（磁盘）+ 0.5（2 个磁盘 + MEM））

如果页面错误占所有访问的 10%。你没有明确说明这一点，但如果公式不包含 0.2*0.9，我会假设后者，这表明前者。

Answer 2

阅读这个问题时，我正在考虑一个更现实的场景，例如基于两级分页系统。

在这种情况下，据我所知，页表（PT）本身可能不驻留在内存中（PT本身可能已从RAM调出到交换区域（例如Linux）或页面文件（例如Linux）中。 Windows））。

关于页目录（分页层次结构的第一级），它必须始终驻留在RAM中（否则，在上下文切换时，x86 CR3寄存器内容将完全无用......）

因此，我们至少必须包括一定百分比的出现：

• 读取 PT 本身并将其引入内存（从交换区域或页面文件）所需的磁盘访问时间
• 现在访问内存中的 PT 所需的 MEM 时间