请求调页（请求页面调度）原理及性能详解

想一想，如何从磁盘加载可执行程序到内存。

一种选择是在程序执行时将整个程序加载到物理内存，这种方法的问题是最初可能不需要整个程序都处于内存。假设程序开始时带有一组用户可选的选项。加载整个程序会导致所有选项的执行代码都加载到内存中，而不管这些选项是否最终使用。

另一种策略是仅在需要时才加载页面。这种技术被称为请求调页，常常用于虚拟内存系统。对于请求调页的虚拟内存，页面只有在程序执行期间被请求时才被加载。因此，从未访问的那些页从不加载到物理内存中。

请求调页系统类似于具有交换的分页系统，如图 1 所示，这里进程驻留在外存上（通常为磁盘）。当进程需要执行时，它被交换到内存中。不过，不是将整个进程交换到内存中，而是采用惰性交换器。惰性交换器除非需要某个页面，否则从不将它交换到内存中。
在请求调页的上下文中，使用术语“交换器”在技术上是不正确的。交换器操纵整个进程，而调页程序只涉及进程的页面。因此，在讨论请求调页时，我们使用“调页程序”，而不是“交换器”。

请求调页的基本概念

当换入进程时，调页程序会猜测在该进程被再次换出之前会用到哪些页。调页程序不是调入整个进程，而是把那些要使用的页调入内存。这样，调页程序就避免了读入那些不使用的页，也减少了交换时间和所需的物理内存空间。

使用这种方案需要一定形式的硬件支持，以区分内存的页面和磁盘的页面。前面所述的有效-无效位方案可用于这一目的。然而此时，当该位被设置为“有效”时，相关联的页面是合法的，并且在内存中。当该位被设置为“无效”时，页面无效（即不在进程的逻辑地址空间中），或有效但只在磁盘上。对于已调入内存的页面，它的页表条目是照常设置的；但是对于不在内存的页面，它的页表条目可简单标记为无效，或者包含磁盘上的页面地址。这种情况如图 2 所示。
注意，如果进程从不试图访问标记为无效的页面，那么并没有什么影响。因此，如果猜测正确并且只调入所有实际需要的页面，那么进程就如同所有页面都已调入内存一样正常运行。当进程执行和访问那些内存驻留的页面时，执行会正常进行。

但是，如果进程试图访问那些尚未调入内存中的页面时，情况会如何呢？对标记为无效的页面访问会产生缺页错误。分页硬件在通过页表转换地址时会注意到无效位被设置，从而陷入操作系统。这种陷阱是由于操作系统未能将所需的页面调入内存引起的。
处理这种缺页错误的程序很简单（图 3）:

1. 检查这个进程的内部表（通常与 PCB（进程控制块）一起保存），以确定该引用是有效的还是无效的内存访问。
2. 如果引用无效，那么终止进程。如果引用有效但是尚未调入页面，那么现在就应调入。
3. 找到一个空闲帧（例如，从空闲帧链表上得到一个）。
4. 调度一个磁盘操作，以将所需页面读到刚分配的帧。
5. 当磁盘读取完成时，修改进程的内部表和页表，以指示该页现在处于内存中。
6. 重新启动被陷阱中断的指令。该进程现在能访问所需的页面，就好像它总是在内存中。

在极端情况下，我们可以开始执行一个没有内存页面的进程。当操作系统将指令指针设置为进程的第一条指令时，由于它所在的页面并不在内存中，进程立即出现缺页错误。当该页面调入内存后，进程继续执行；根据需要发生缺页错误，直到所需每个页面都在内存中。这时，它可以在没有更多缺页错误的情况下执行。这种方案为纯请求调页，即只有在需要时才将页面调入内存。

理论上，有些程序的每次指令执行可以访问多个新的页面（一个用于指令，其他的多个用于数据），从而每条指令可能引起多个缺页错误。这种情况会导致不可接受的系统性能。幸运的是，对运行进程的分析表明，这种行为是极不可能的。如前面所述，程序具有局部引用，这使得请求调页具有较为合理的性能。

支持请求调页的硬件与分页和交换的硬件相同：

• 页表：该表能够通过有效-无效位或保护位的特定值将条目标记为无效。
• 外存（或辅助存储）：这种外存用于保存不在内存（主存）中的那些页面。外存通常为高速硬盘，称为交换设备，用于交换的这部分磁盘称为交换空间。

请求调页的关键要求是在缺页错误后重新启动任何指令的能力。因为当发生缺页错误时，保存了被中断的进程状态（寄存器、条件代码、指令计数器），所以应能够在完全相同的位置和状态下，重新启动进程，只不过现在所需的页面已在内存中并且是可以访问的。在大多数情况下，这个要求很容易满足。任何内存引用都可能引起缺页错误。如果在获取指令时出现了缺页错误，那么可以再次获取指令。如果在获取操作数时出现了缺页错误，那么可以再次获取指令、再次译码指令，然后再次获取操作数。

作为最坏情况的示例，假设一个具有三个地址的指令 ADD，它可将 A 和 B 的内容相加，并将结果存入 C。这个指令的执行步骤是：

1. 获取并解码指令（ADD）；
2. 获取 A；
3. 获取 B；
4. 将 A 和 B 相加；
5. 将结果存入 C 中；

如果在尝试保存到 C 时出现缺页错误（因为 C 所在的页面并不在内存中），那么应获取所需的页面，将其调入，更正页表，然后重新启动指令。重新启动需要再次获取指令，再次对指令译码，再次获取两个操作数，然后相加。然而，没有多少重复工作（少于一条完整指令），并且仅当发生缺页错误时才需要重复。

当一条指令可以修改多个不同的位置时，就会出现重要困难。例如，IBM System 360/370 的 MVC（移动字符）指令，可以从一个位置移动多达 256 字节到另一个位置（可能重叠）。如果任何一块（源或目的）跨越页边界，那么在执行了部分移动时可能会出现缺页错误。此外，如果源块和目的块有重叠，源块可能已被修改；在这种情况下，我们不能简单重新启动指令。

这个问题可有两种不同的解决方法：

• 一种解决方案是，微代码计算并试图访问两块的两端。如果会出现缺页错误，那么在这一步就会出现（在任何内容被修改之前）。然后可以执行移动。我们知道不会发生缺页错误，因为所有相关页面都在内存中。
• 另一个解决方案使用临时寄存器来保存覆盖位置的值。如果有缺页错误，则在陷阱发生之前，所有旧值都将写回到内存中。该动作将内存恢复到指令启动之前的状态，这样就能够重复该指令。

这绝不是通过向现有架构添加分页以允许请求调页而产生的唯一的架构问题，不过它已说明了所涉及的一些困难。分页是在计算机系统的 CPU 和内存之间添加的，它应该对用户进程完全透明。

因此，人们经常假定分页能够添加到任何系统。这个假定对于非请求调页环境来说是正确的，因为在这种环境中，缺页错误就代表了一个致命错误。然而，对于缺页错误仅意味着另外一个额外页面需要调入内存，然后进程重新运行的情况来说，这个假定就是不正确的。

请求调页的性能

请求调页可以显著影响计算机系统的性能。为了说明起见，下面计算一下请求调页内存的有效访问时间。

对大多数计算机系统而言，内存访问时间（用 ma 表示）的范围为 10〜200ns。只要没有出现缺页错误，有效访问时间就等于内存访问时间。然而，如果出现缺页错误，那么就应先从磁盘中读入相关页面，再访问所需要的字。

设 p 为缺页错误的概率（0≤p≤1）。希望 p 接近于 0，即缺页错误很少。那么有效访问时间为：

有效访问时间=(1 - p) X ma + p X 缺页错误时间

为了计算有效访问时间，应知道需要多少时间来处理缺页错误。缺页错误导致发生以下一组动作：

1. 陷入操作系统。
2. 保存用户寄存器和进程状态。
3. 确定中断是否为缺页错误。
4. 检查页面引用是否合法，并确定页面的磁盘位置。
5. 从磁盘读入页面到空闲帧：
   • 在该磁盘队列中等待，直到读请求被处理。
   • 等待磁盘的寻道或延迟时间。
   • 开始传输磁盘页面到空闲帧。
6. 在等待时，将 CPU 分配给其他用户（CPU 调度，可选）。
7. 收到来自 I/O 子系统的中断（I/O 完成）。
8. 保存其他用户的寄存器和进程状态（如果执行了第 6 步）。
9. 确认中断是来自上述磁盘的。
10. 修正页表和其他表，以表示所需页面现在已在内存中。
11. 等待 CPU 再次分配给本进程。
12. 恢复用户寄存器、进程状态和新页表，再重新执行中断的指令。

以上步骤并不是在所有情况下都是必要的。例如，假设第 6 步在执行 I/O 时将 CPU 分配给另一进程。这种安排允许多道程序以提高 CPU 使用率，但是在执行完 I/O 时也需要额外时间来重新启动缺页错误的处理程序。在任何情况下，缺页错误的处理时间有三个主要组成部分：

1. 处理缺页错误中断。
2. 读入页面。
3. 重新启动进程。

第一个和第三个任务通过仔细编码可以减少到几百条指令。这些任务每次可能需要 1〜100ms。然而，页面切换时间可能接近 8ms（典型硬盘的平均延迟为 3ms，寻道时间为 5ms，传输时间为 0.05ms。因此，总的调页时间约为 8ms，包括硬件的和软件的时间）。而且，要注意，这里只考虑了设备处理时间。如果有一队列的进程正在等待设备，那么应加上等待设备的时间，以便等待调页设备空闲来处理请求，从而增加了更多的交换时间。

如果缺页错误处理的平均时间为 8ms，内存访问时间为 200ns，那么有效内存访问时间（以 ns 计）为：

有效访问时间=(1-p) X (200) + p(8ms)=(1 -p)X 200 + p X 8 000 000 = 200 + 7 999 800 X p

这样，我们看到有效访问时间与缺页错误率成正比。如果每 1000 次访问中有一次缺页错误，那么有效访问时间为 8.2μs。由于请求分页，计算机会减速 40 倍。如果我们希望性能下降小于 10%，则需要将缺页错误的概率保持在以下级别：

220 >200 + 7 999 800 X p
20 > 7 999 800 X p
p < 0.000 002 5

也就是说，为了因缺页错误而产生的性能降低可以接受，那么只能允许每 399 990 次访问中出现不到一次的缺页错误。总之，对于请求调页，降低缺页错误率是极为重要的。否则，会增加有效访问时间，从而极大地减缓了进程的执行速度。

请求调页的另一个方面是交换空间的处理和整体使用。交换空间的磁盘 I/O 通常要快于文件系统的。交换空间的文件系统更快，因为它是按更大的块来分配的，且不采用文件查找和间接分配方法。

因此，系统可以在进程启动时将整个文件映像复制到交换空间中，然后从交换空间执行请求调页，从而获得更好的分页吞吐量。另一选择是，开始时从文件系统进行请求调页，但是在置换页面时则将页面写入交换空间。这种方法确保只从文件系统读取所需的页面，而所有后续调页都是从交换空间完成的。

对于二进制文件的请求调页，有些系统试图限制交换空间的用量。这些文件的请求调页是从文件系统中直接读取的。然而，当需要页面置换时，这些帧可以简单地覆盖（因为它们从未被修改），当再次需要时，从文件系统中再次直接读入。

采用这种方法，文件系统本身用作后备存储。然而，对于与文件无关的页面还是需要使用交换空间（称为匿名内存），这些页面包括进程的堆栈和堆。这种方法似乎是一个很好的折中，并用于多个操作系统，如 Solaris 与 BSD UNIX。

移动操作系统通常不支持交换。当内存变得有限时，这些系统从文件系统请求调页，并从应用程序中回收只读页面（例如代码）。如果以后需要，可以从文件系统中请求这些数据。对于 iOS，不会从应用程序中回收匿名内存页面，除非应用程序终止或显式释放内存。