操作系统基础36-请求页面调度概念

2020-12-28 10:54·重学IT的老猫

如何从磁盘加载可执行程序到内存? 一种选择是在程序执行时将整个程序加载到物理内存，这种方法的问题是最初可能不需要整个程序都处于内存。假设程序开始时带有一组用户可选的选项。加载整个程序会导致所有选项的执行代码都加载到内存中，而不管这些选项是否最终使用。另一种策略是仅在需要时才加载页面。这种技术被称为请求调页，常常用于虚拟内存系统。对于请求调页的虚拟内存，页面只有在程序执行期间被请求时才被加载。因此，从未访问的那些页从不加载到物理内存中。 请求调页系统类似于具有交换的分页系统，如下图所示，这里进程驻留在外存上（通常为磁盘）。当进程需要执行时，它被交换到内存中。不过，不是将整个进程交换到内存中，而是采用惰性交换器。惰性交换器除非需要某个页面，否则从不将它交换到内存中。

从分页内存到连续磁盘空间的传输

在请求调页的上下文中，使用术语“交换器”在技术上是不正确的。交换器操纵整个进程，而调页程序只涉及进程的页面。因此，在讨论请求调页时，我们使用“调页程序”，而不是“交换器”。

请求调页的基本概念

当换入进程时，调页程序会猜测在该进程被再次换出之前会用到哪些页。调页程序不是调入整个进程，而是把那些要使用的页调入内存。这样，调页程序就避免了读入那些不使用的页，也减少了交换时间和所需的物理内存空间。使用这种方案需要一定形式的硬件支持，以区分内存的页面和磁盘的页面。前面分页保护所述的有效-无效位方案可用于这一目的。然而此时，当该位被设置为“有效”时，相关联的页面是合法的，并且在内存中。当该位被设置为“无效”时，页面无效（即不在进程的逻辑地址空间中），或有效但只在磁盘上。对于已调入内存的页面，它的页表条目是照常设置的；但是对于不在内存的页面，它的页表条目可简单标记为无效，或者包含磁盘上的页面地址。这种情况如下图所示。

有些页面不在内存的页表

注意，如果进程从不试图访问标记为无效的页面，那么并没有什么影响。因此，如果猜测正确并且只调入所有实际需要的页面，那么进程就如同所有页面都已调入内存一样正常运行。当进程执行和访问那些内存驻留的页面时，执行会正常进行。但是，如果进程试图访问那些尚未调入内存中的页面时，情况会如何呢？对标记为无效的页面访问会产生缺页错误。分页硬件在通过页表转换地址时会注意到无效位被设置，从而陷入操作系统。这种陷阱是由于操作系统未能将所需的页面调入内存引起的。

处理缺页错误的步骤

处理这种缺页错误的程序很简单(上图 )：

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

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

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

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

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

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

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

获取并解码指令(ADD)；
获取A；
获取B；
将A和B相加；
将结果存入C中；

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

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

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

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

这绝不是通过向现有架构添加分页以允许请求调页而产生的唯一的架构问题，不过它已说明了所涉及的一些困难。分页是在计算机系统的CPU和内存之间添加的，它应该对用户进程完全透明。因此，人们经常假定分页能够添加到任何系统。这个假定对于非请求调页环境来说是正确的，因为在这种环境中，缺页错误就代表了一个致命错误。然而，对于缺页错误仅意味着另外一个额外页面需要调入内存，然后进程重新运行的情况来说，这个假定就是不正确的。