[操作系统]分页系统的实现问题

• 分页系统的实现问题
  • 与分页有关的工作
  • 缺页中断处理
  • 指令备份
  • 锁定内存中的页面
  • 后备存储
  • 策略和机制的分离

1. 与分页有关的工作

操作系统在四段时间里做与分页有关的工作：进程创建时，进程执行时，缺页中断时和进程终止时。

1. 当在分页系统中创建一个一个新进程时，操作系统需要确定该进程的程序和数据在初始时有多大，并为它们创建一个页表。操作系统还要在内存中为页表分配空间并对其进行初始化。当进程被换出时，页表不需要驻留在内存中，但当进程运行时，页表必须在内存中。

   另外，操作系统要在磁盘交换区中分配空间，以便在一个进程换出时在磁盘上有放置此进程的空间。操作系统还要用程序正文和数据对交换区进程初始化，这样当新进程发生缺页中断时，可以调入需要的页面。某些操作系统直接从磁盘上的可执行文件对程序正文进行分页，以节省磁盘空间和初始化时间。

   最后，操作系统必须把有关页表和磁盘交换区的信息存储在进程表中。

2. 当调度一个进程执行时，必须为新进程重置MMU，刷新TLB，以清除以前的进程遗留下的痕迹。

3. 当缺页中断发生时，操作系统必须通过读硬件寄存器来确定是哪个虚拟地址造成的缺页中断。并计算出需要的页面以及要替换的老的页面。最后，还要备份程序计数器，使其指向引起缺页终端的指令，并重新执行该指令。

4. 当进程退出的时候，操作系统需要释放进程的页表，页面和页面在硬盘上所占用的空间。但如果有些页面是被共享的，那只有当所有使用共享页面的进程终止时，该共享页面才会被释放。

2. 缺页中断处理

缺页中断时，发生的的事件顺序如下：

1. 硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。

2. 启动一个汇编代码例程保存通用寄存器和其他易失的消息，以免被操作系统破坏。

3. 当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这以信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。

4. 一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。

5. 如果选择的页框被修改过了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。

6. 一旦页框干净后，操作系统查找所需页面的在磁盘上的地址，通过磁盘操作将其装入。该页面被装入后，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。

7. 当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。

8. 恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。

9. 调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。

10. 该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

3. 指令备份

当程序访问不在内存中的页面时，引起缺页中断的指令会半途停止并引发操作系统的陷阱，系统取出所需的页面后，需要重新启动引起陷阱的指令。

为了重启指令，操作系统需要知道指令第一个字节的位置。在陷阱发生时，程序计数器的值依赖于引起缺页中断的那个操作数以及CPU中微指令的实现方式。

可以，使用一个隐藏的内部寄存器。在每条指令执行之前，把程序计数器的内容复制到该寄存器。可能会有第二个寄存器，用来提供哪些寄存器已经自动增加或者自动减少以及递减的数量信息。通过这些信息就可以重启指令了。

4. 锁定内存中的页面

假如一个进程刚刚通过系统调用从文件或其他设备中读取数据到其地址空间中的缓冲区。在等待I/O完成时，该进程被挂起，另一个进程被允许运行，而这个新运行的进程产生一个缺页中断。

如果分页算法是全局算法，包含I/O缓冲区的页面有可能会被淘汰出内存。如果一个I/O设备正处在对该页面进程DMA传输的过程之中，将这个页面移出去将会导致部分数据写入它们所属的缓冲区中，而部分数据被写入到最新装入的页面中。

一种解决方法是锁住正在做I/O操作的内存中的页面以保证
它不会被移出内存。锁住一个页面通常称为在内存中钉住页面。另一种方法是在内核缓冲区中完成所有的I/O操作，然后再将数据复制到用户页面。

5. 后备存储

在内存中被置换出的页面应该放在磁盘中的什么位置？

1. 静态交换区分页

   在磁盘上分配页面空间的最简单的算法是在磁盘上设置特殊的交换分区，甚至从文件系统划分一块独立的磁盘。

   当系统启动时，以该交换分区为空，并在内存中以单独的项给出它的起始大小。在最简单的情况下，当第一个进程启动时，留出与这个进程一样大的交换区块，剩余的为总空间减去这个交换分区。当新进程启动后，同样被分配与其核心映像同等大小的交换分区。进程结束后，会释放其磁盘上的交换区。交换分区以空闲块列表的形式组织。

   与每个进程对应的是其交换区的磁盘地址，即进程映像保存的地方。这一信息是记录在进程表里的。

   写回一个页面时，计算写回地址的过程为：将虚拟地址空间中页面的偏移量加到交换区开始的地址。但在进程启动前必须初始化交换区，一种方法是将整个进程映像复制到交换区，以便随时可以将所需内容装入，另一种方法是将整个进程装入内存，并在需要时换出。

   这种方法可能出现的问题是：进程再启动后可能增大。所以最好为正文、数据和堆栈分别保留交换区，并且允许这些交换区在磁盘上多于一个块。

2. 动态备份页面

   另一个极端的情况是，事先什么也不分配，在页面换出时为其分配磁盘空间，并在换入时回收磁盘空间，这样内存中的进程不必固定于任何交换空间。缺点是内存中的每个页面都要记录相应的磁盘地址，即每个进程都必须有一张表，记录每一个页面在磁盘上的位置。

如图所示，在a中，页面0，3，4，6在内存中，页面1，2，5和7在磁盘上。磁盘上的交换区与进程虚拟地址空间一样大(8个页面)，每个页面有固定的位置，当它从内存中被淘汰时，便写道相应位置。该地址的计算需要知道进程的分页区域的起始位置，因为页面是按照它们的虚拟页号的顺序连续存储的。内存中的页面通常在磁盘上有镜像副本，但是如果页面装入内存后被修改过，那么这个副本可能已经过期，磁盘上的页面应该被内存中的所替代。但如果一个内存页面要被换回磁盘，并且未被修改过，那么应该使用磁盘中的副本。

在b中，页面在磁盘上没有固定地址。当页面换出时，要及时选择一个空磁盘页面并据此来更新磁盘映射，即每个虚拟页面都有一个磁盘地址空间。内存中的页面在磁盘上没有副本，它们在磁盘映射表中的表项包含一个非法的磁盘地址或者一个表示它们未被使用的标记位。

不能保证总能够实现固定的交换分区，例如没有磁盘分区可用时，这种时候可以利用正常文件系统中的一个或多个较大的，事前定位的文件。

更好的方法是，由于程序正文通常是只读的，当内存紧张时，可以丢弃程序页，在需要的时候从可执行文件(因为每个进程的程序正文来自可执行文件)读入即可。共享库也可用这个方式工作。

6. 策略和机制的分离

使大多数存储管理器作为用户级进程运行。

如图所示，其中存储管理系统被分为三个部分：

1. 一个底层MMU处理程序。
2. 一个作为内核一部分的缺页中断处理程序。
3. 一个运行在用户空间中的外部页面调度程序。

当一个进程启动时，需要通知外部页面调度程序以建立进程页面映射，如果需要的话还要在磁盘上分配后备存储。

当进程正在运行时，可能要把新对象映射到其地址空间，还要通知外部页面调度程序。

当进程开始运行，有可能出现缺页中断，此时由缺页中断处理程序找出需要的虚拟页面，然后发送一条消息给外部页面调度程序通知它。

外部页面调度程序从磁盘中读入所需页面，把它复制到自己地址空间的某一位置。并告诉缺页中断处理程序该页面的位置。

缺页中断处理程序从外不页面调度程序的地址空间中清除该页面映射，然后请求MMU处理程序把它放到用户地址空间的正确位置，最后重启用户进程。

在这个方法中，可以将页面置换算法存储在外部页面调度程序中。但外部页面调度程序无权访问页面的访问位和修改位。所以需要某种机制把这些信息传递给外部页面调度程序，或者把算法存储在内核中。如果算法存储在内核中，那么缺页中断处理程序负责告诉外部页面调度程序，应该被淘汰的页面。

这种方法优点是模块化和好的适应性，缺点是用户陷入内核需要开销。

参考书目：现代操作系统第三版