页面交换

到目前为止，我们假设地址空间小得不切实际，并且适合物理内存。事实上，我们一直假设每个正在运行的进程的每个地址空间都适合内存。现在，我们将放宽这些重大假设，并假设我们希望支持许多并发运行的大型地址空间。

为此，我们需要在内存层次结构中增加一个级别。到目前为止，我们假设所有页面都驻留在物理内存中。然而，为了支持大地址空间，操作系统需要一个地方来存放当前需求不大的部分地址空间。一般来说，这样的位置的特点是容量要大于内存；因此，它通常会比较慢（如果它更快，我们就会将它用作内存，不是吗？）。在现代系统中，此角色通常由硬盘驱动器担任。因此，在我们的内存层次结构中，大而慢的硬盘驱动器位于底部，内存位于上面。

因此，我们找到了问题的关键： 如何超越物理内存？操作系统如何利用更大、更慢的设备来透明地提供大虚拟地址空间的假象？

您可能有一个问题：为什么我们要为进程支持单个大地址空间？答案再次是方便和易用。有了大的地址空间，您就不必担心内存中是否有足够的空间来容纳程序的数据结构；相反，您只需自然地编写程序，根据需要分配内存即可。这是操作系统提供的强大幻觉，使您的生活变得更加简单。与此形成鲜明对比的是使用内存覆盖的旧系统，它要求程序员在需要时手动将代码或数据移入或移出内存。试着想象一下这将会是什么样子：在调用函数或访问某些数据之前，你需要首先安排代码或数据进入内存。

除了单个进程之外，添加交换空间还允许操作系统为多个并发运行的进程提供大虚拟内存的假象。多道程序设计（“同时”运行多个程序，以更好地利用机器）的发明几乎需要交换某些页面的能力，因为早期的机器显然无法同时容纳所有进程所需的所有页面。因此，多道程序设计和易用性的结合使我们希望支持使用比物理可用内存更多的内存。这是所有现代 VM 系统都会做的事情；现在我们将进一步了解这一点。

1 交换空间

我们需要做的第一件事是在磁盘上保留一些空间用于来回移动页面。在操作系统中，我们通常将此类空间称为交换空间，因为我们将内存中的页面交换出来，又将内存中的页面交换进去。因此，我们简单地假设操作系统可以以页面大小为单位读取和写入交换空间。为此，操作系统需要记住给定页面的磁盘地址。

交换空间的大小很重要，因为它最终决定了系统在给定时间可以使用的最大内存页数。为了简单起见，我们假设它现在非常大。

如下图所示，，您可以看到一个 4 页物理内存和 8 页交换空间的小例子。在示例中，三个进程（Proc 0、Proc 1 和 Proc 2）正在主动共享物理内存；然而，这三个页面中的每一个都只有一些有效页面位于内存中，其余部分位于磁盘上的交换空间中。第四个进程 (Proc 3) 已将其所有页面换出到磁盘，因此显然当前未运行。一区块的交换仍然是空闲的。即使从这个小例子中，希望您可以看到使用交换空间如何让系统假装内存比实际更大。

我们应该注意，交换空间并不是交换流量的唯一磁盘位置。例如，假设您正在运行一个程序二进制文件（例如 ls 或您自己编译的主程序）。该二进制文件中的代码页最初在磁盘上找到，当程序运行时，它们被加载到内存中（或者在程序开始执行时一次全部加载，或者像在现代系统中一样，在需要时一次加载一页）。但是，如果系统需要在物理内存中腾出空间来满足其他需求，它可以安全地重新使用这些代码页的内存空间，因为它知道以后可以从文件系统中的磁盘二进制文件中再次交换它们。

2 存在位

现在我们在磁盘上有了一些空间，我们需要在系统中添加一些更高级别的机器，以支持与磁盘之间的页面交换。为简单起见，我们假设我们有一个带有硬件管理的 TLB 的系统。

首先回想一下内存引用上发生的情况。运行的进程生成虚拟内存引用（用于指令获取或数据访问），在这种情况下，硬件在从内存中获取所需数据之前将它们转换为物理地址。

请记住，硬件首先从虚拟地址中提取 VPN，检查 TLB 是否匹配（TLB 命中），如果命中，则生成结果物理地址并从内存中获取它。这希望是常见情况，因为它速度很快（不需要额外的内存访问）。

如果在 TLB 中未找到 VPN（即 TLB 未命中），硬件将在内存中定位页表（使用页表基址寄存器），并使用 VPN 查找该页的页表条目 (PTE)：一个索引。如果该页有效并且存在于物理内存中，则硬件从 PTE 中提取 PFN，将其安装到 TLB 中，并重试该指令，这次生成 TLB 命中；到目前为止，一切都很好。

然而，如果我们希望允许页面交换到磁盘，我们必须添加更多的机器。具体来说，当硬件查看PTE时，它可能会发现物理内存中不存在该页。硬件（或操作系统，在软件管理的 TLB 方法中）确定这一点的方式是通过每个页表条目中的一条新信息（称为存在位，the present bit）。如果存在位设置为 1，则意味着该页存在于物理内存中，并且一切按上述进行；如果它设置为零，则该页面不在内存中，而是在磁盘上的某个位置。访问不在物理内存中的页面的行为通常称为页面错误。

出现页面错误时，将调用操作系统来处理页面错误。正如我们现在所描述的，运行一段称为页面错误处理程序的特定代码，并且必须为页面错误提供服务。

3 页面错误

回想一下，对于 TLB 未命中，我们有两种类型的系统：硬件管理的 TLB（硬件在页表中查找所需的转换）和软件管理的 TLB（操作系统执行的操作）。在任一类型的系统中，如果页面不存在，操作系统将负责处理页面错误。操作系统页面错误处理程序将运行以确定要做什么。几乎所有系统都通过软件来处理页面错误；即使使用硬件管理的 TLB，硬件也会信任操作系统来管理这项重要职责。

如果页面不存在并且已交换到磁盘，操作系统将需要将该页面交换到内存中以解决页面错误。因此，出现了一个问题：操作系统如何知道在哪里可以找到所需的页面？在许多系统中，页表是存储此类信息的自然位置。因此，操作系统可以使用 PTE 中通常用于数据的位，例如磁盘地址页面的 PFN。当操作系统收到页面的缺页错误时，它会在 PTE 中查找地址，并向磁盘发出请求以将该页面提取到内存中。

当磁盘 I/O 完成时，操作系统将更新页表以将页面标记为存在，更新页表项 (PTE) 的 PFN 字段以记录新获取的页面在内存中的位置，并重试该指令。下一次尝试可能会生成 TLB 未命中，然后将对其进行处理并通过转换更新 TLB（可以在处理页错误时交替更新 TLB，以避免此步骤）。最后，最后一次重新启动将在 TLB 中找到转换，从而继续从内存中转换后的物理地址获取所需的数据或指令。

请注意，当 I/O 正在进行时，进程将处于阻塞状态。因此，在处理页面错误时，操作系统将可以自由地运行其他就绪进程。由于 I/O 的成本很高，因此一个进程的 I/O（页面错误）与另一个进程的执行的重叠是多道程序系统最有效地利用其硬件的另一种方式。

4 如果内存已满怎么办？

在上述过程中，您可能会注意到，我们假设有足够的可用内存可从交换空间调入页面。当然，情况也可能并非如此；内存可能已满（或接近满）。因此，操作系统可能希望首先调出一个或多个页面，以便为操作系统即将引入的新页面腾出空间。选择要踢出或替换的页面的过程称为页面替换策略。

事实证明，我们在创建良好的页面替换策略时花费了很多心思，因为踢出错误的页面可能会给程序性能带来巨大的损失。做出错误的决定可能会导致程序以类似磁盘的速度而不是类似内存的速度运行；在当前技术中，这意味着程序的运行速度可能会慢 10,000 或 100,000 倍。所以，这样的策略是值得我们仔细研究的。事实上，这正是我们在下一章中要做的事情。现在，只要理解这样的政策的存在就足够了，它建立在此处描述的机制之上。

5 页面错误控制流

有了这些知识，我们现在就可以大致勾勒出内存访问的完整控制流程，如下图所示。

换句话说，当有人问你 “当程序从内存中获取一些数据时会发生什么？“时，你应该对所有不同的可能性有一个相当好的概念，如下面两段代码所示。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Page-Fault Control Flow Algorithm (Hardware)
1 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2 (Success, TlbEntry) = TLB_Lookup(VPN)
3 if (Success == True) // TLB Hit
4     if (CanAccess(TlbEntry.ProtectBits) == True)
5         Offset = VirtualAddress & OFFSET_MASK
6         PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
7         Register = AccessMemory(PhysAddr)
8     else
9         RaiseException(PROTECTION_FAULT)
10 else // TLB Miss
11    PTEAddr = PTBR + (VPN * sizeof(PTE))
12    PTE = AccessMemory(PTEAddr)
13    if (PTE.Valid == False)
14        RaiseException(SEGMENTATION_FAULT)
15    else
16        if (CanAccess(PTE.ProtectBits) == False)
17            RaiseException(PROTECTION_FAULT)
18        else if (PTE.Present == True)
19            // assuming hardware-managed TLB
20            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
21            RetryInstruction()
22        else if (PTE.Present == False)
23            RaiseException(PAGE_FAULT)

1
2
3
4
5
6
7
8

// Page-Fault Control Flow Algorithm (Software)
1 PFN = FindFreePhysicalPage()
2 if (PFN == -1) // no free page found
3     PFN = EvictPage() // run replacement algorithm
4     DiskRead(PTE.DiskAddr, PFN) // sleep (waiting for I/O)
5     PTE.present = True // update page table with present bit
6     PTE.PFN = PFN // and translation (PFN)
7     RetryInstruction() // retry instruction

第一段代码显示了硬件在转换过程中的操作，第二段代码显示了操作系统在发生页面错误时的操作。

从第一段代码中的硬件控制流程可以看出，当发生 TLB 未命中时，有三种重要情况需要了解。第一种情况是页面既存在又有效（第 18-21 行）；在这种情况下，TLB 未命中处理程序可以简单地从 PTE 中获取 PFN，重试指令（这次会导致 TLB 命中），然后继续之前（多次）描述的操作。在第二种情况下（第 22-23 行），必须运行页面错误处理程序；虽然进程访问的页面是合法的（毕竟是有效的），但它不在物理内存中。第三种（也是最后一种）情况是访问的页面无效，例如由于程序中的错误（第 13-14 行）。在这种情况下，PTE 中的其他位都不重要；硬件会捕获这种无效访问，操作系统中断处理程序也会运行，从而终止违规进程。

从第二段代码的软件控制流中我们可以看到操作系统处理页面错误的大致步骤。首先，操作系统必须为即将发生错误的页面找到一个物理页号；如果没有这样的页面，我们就必须等待替换算法运行，将一些页面踢出内存，从而释放出这些页面供此处使用。有了物理页，处理程序就会发出 I/O 请求以从交换空间读入页面。最后，当缓慢的操作完成时，操作系统会更新页表并重试该指令。重试将导致 TLB 未命中，然后，在另一次重试时，TLB 命中，此时硬件将能够访问所需的项。

6 当替换真正发生时

到目前为止，我们描述替换如何发生的方式是假设操作系统等待内存完全满，然后才替换（逐出）页面为其他页面腾出空间。正如您可以想象的那样，这有点不现实，操作系统主动保留一小部分内存的原因有很多。

为了保持少量内存空闲，大多数操作系统都有某种高水位线（HW）和低水位线（LW）来帮助决定何时开始从内存中逐出页面。其工作原理如下：当操作系统注意到可用的 LW 页数较少时，负责释放内存的后台线程就会运行。该线程逐出页面，直到有可用的硬件页面。**后台线程（有时称为交换守护程序或页面守护程序）**然后进入睡眠状态，很高兴它释放了一些内存供正在运行的进程和操作系统使用。

通过同时执行多个替换，新的性能优化成为可能。例如，许多系统会将多个页面聚集或分组并立即将它们写入交换分区，从而提高磁盘的效率；正如我们稍后更详细地讨论磁盘时将看到的那样，这种集群减少了磁盘的查找和旋转开销，从而显着提高了性能。

为了与后台分页线程一起工作，上面的第二段代码控制流应该稍微修改一下；该算法不会直接执行替换，而是简单地检查是否有可用的空闲页面。如果没有，它会通知后台分页线程需要空闲页面；当线程释放一些页面时，它会重新唤醒原始线程，然后原始线程可以调入所需的页面并继续其工作。