3.6 有关实现的问题
实现虚拟内存系统要在主要的理论算法&＃xff08;如第二次机会算法与老化算法&＃xff0c;局部页面分配与全局页面分配&＃xff0c;请求调页与预先调页&＃xff09;之间进行选择。但同时也要注意一系列实际的实现问题。
3.6.1 与分页有关的工作
操作系统要在下面的四段时间里做与分页相关的工作&＃xff1a;进程创建时&＃xff0c;进程执行时&＃xff0c;缺页中断时和进程终止时。
当在分页系统中创建一个新进程时&＃xff0c;操作系统要确定程序和数据在初始时有多大&＃xff0c;并为它们创建一个页表。操作系统还要在内存中为页表分配空间并对其进行初始化。当进程被换出时&＃xff0c;页表不需要驻留在内存中&＃xff0c;但当进程运行时&＃xff0c;它必须在内存中。另外&＃xff0c;操作系统要在磁盘交换区中分配空间&＃xff0c;以便在一个进程换出时在磁盘上有放置此进程的空间。操作系统还要用程序正文和数据对交换区进行初始化&＃xff0c;这样当新进程发生缺页中断时&＃xff0c;可以调入需要的页面。某些系统直接从磁盘上的可执行文件对程序正文进行分页&＃xff0c;以节省磁盘空间和初始化时间。最后&＃xff0c;操作系统必须把有关页表和磁盘交换区的信息存储在进程表中。
当调度一个进程执行时&＃xff0c;必须为新进程重置MMU&＃xff0c;刷新TLB&＃xff0c;以清除以前的进程遗留的痕迹。新进程的页表必须成为当前页表&＃xff0c;通常可以通过复制该页表或者把一个指向它的指针放进某个硬件寄存器来完成。有时&＃xff0c;在进程初始化时可以把进程的部分或者全部页面装入内存中以减少缺页中断的发生&＃xff0c;例如&＃xff0c;PC&＃xff08;程序计数器&＃xff09;所指的页面肯定是需要的。
当缺页中断发生时&＃xff0c;操作系统必须通过读硬件寄存器来确定是哪个虚拟地址造成了缺页中断。通过该信息&＃xff0c;它要计算需要哪个页面&＃xff0c;并在磁盘上对该页面进行定位。它必须找到合适的页框来存放新页面&＃xff0c;必要时还要置换老的页面&＃xff0c;然后把所需的页面读入页框。最后&＃xff0c;还要备份程序计数器&＃xff0c;使程序计数器指向引起缺页中断的指令&＃xff0c;并重新执行该指令。
当进程退出的时候&＃xff0c;操作系统必须释放进程的页表、页面和页面在硬盘上所占用的空间。如果某些页面是与其他进程共享的&＃xff0c;当最后一个使用它们的进程终止的时候&＃xff0c;才可以释放内存和磁盘上的页面。
3.6.2 缺页中断处理
缺页中断发生时的事件顺序如下&＃xff1a;
1) 硬件陷入内核&＃xff0c;在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
2) 启动一个汇编代码例程保存通用寄存器和其他易失的信息&＃xff0c;以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
3) 当操作系统发现一个缺页中断时&＃xff0c;尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息&＃xff0c;如果没有的话&＃xff0c;操作系统必须检索程序计数器&＃xff0c;取出这条指令&＃xff0c;用软件分析这条指令&＃xff0c;看看它在缺页中断时正在做什么。
4) 一旦知道了发生缺页中断的虚拟地址&＃xff0c;操作系统检查这个地址是否有效&＃xff0c;并检查存取与保护是否一致。如果不一致&＃xff0c;向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生&＃xff0c;系统则检查是否有空闲页框。如果没有空闲页框&＃xff0c;执行页面置换算法寻找一个页面来淘汰。
5) 如果选择的页框“脏”了&＃xff0c;安排该页写回磁盘&＃xff0c;并发生一次上下文切换&＃xff0c;挂起产生缺页中断的进程&＃xff0c;让其他进程运行直至磁盘传输结束。无论如何&＃xff0c;该页框被标记为忙&＃xff0c;以免因为其他原因而被其他进程占用。
6) 一旦页框“干净”后&＃xff08;无论是立刻还是在写回磁盘后&＃xff09;&＃xff0c;操作系统查找所需页面在磁盘上的地址&＃xff0c;通过磁盘操作将其装入。该页面被装入后&＃xff0c;产生缺页中断的进程仍然被挂起&＃xff0c;并且如果有其他可运行的用户进程&＃xff0c;则选择另一个用户进程运行。
7) 当磁盘中断发生时&＃xff0c;表明该页已经被装入&＃xff0c;页表已经更新可以反映它的位置&＃xff0c;页框也被标记为正常状态。
8) 恢复发生缺页中断指令以前的状态&＃xff0c;程序计数器重新指向这条指令。
9) 调度引发缺页中断的进程&＃xff0c;操作系统返回调用它的汇编语言例程。
10) 该例程恢复寄存器和其他状态信息&＃xff0c;返回到用户空间继续执行&＃xff0c;就好像缺页中断没有发生过一样。
3.6.3 指令备份
当程序访问不在内存中的页面时&＃xff0c;引起缺页中断的指令会半途停止并引发操作系统的陷阱。在操作系统取出所需的页面后&＃xff0c;它需要重新启动引起陷阱的指令。但这并不是一件容易实现的事。
我们在最坏情形下考察这个问题的实质&＃xff0c;考虑一个有双地址指令的CPU&＃xff0c;比如Motorola 680x0&＃xff0c;这是一种在嵌入式系统中广泛使用的CPU。例如&＃xff0c;指令
- MOVE.L#6(A1), 2(A0)
为6字节&＃xff08;见图3-28&＃xff09;。为了重启该指令&＃xff0c;操作系统要知道该指令第一个字节的位置。在陷阱发生时&＃xff0c;程序计数器的值依赖于引起缺页中断的那个操作数以及CPU中微指令的实现方式。
在图3-28中&＃xff0c;从地址1000处开始的指令进行了3次内存访问&＃xff1a;指令字本身和操作数的2个偏移量。从可以产生缺页中断的这3次内存访问来看&＃xff0c;程序计数器可能在1000、1002和1004时发生缺页中断&＃xff0c;对操作系统来说要准确地判断指令是从哪儿开始的通常是不可能的。如果发生缺页中断时程序计数器是1002&＃xff0c;操作系统无法弄清在1002位置的字是与1000的指令有关的内存地址&＃xff08;比如&＃xff0c;一个操作数的位置&＃xff09;&＃xff0c;还是一个指令的操作码。
这种情况已经很糟糕了&＃xff0c;但可能还有更糟的情况。一些680x0体系结构的寻址方式采用自动增量&＃xff0c;这也意味着执行这条指令的副作用是会增量一个或多个寄存器。使用自动增量模式也可能引起错误。这依赖于微指令的具体实现&＃xff0c;这种增量可能会在内存访问之前完成&＃xff0c;此时操作系统必须在重启这条指令前将软件中的寄存器减量。自动增量也可能在内存访问之后完成&＃xff0c;此时&＃xff0c;它不会在陷入时完成而且不必由操作系统恢复。自动减量也会出现相同的问题。自动增量和自动减量是否在相应访存之前完成随着指令和CPU模式的不同而不同。
幸运的是&＃xff0c;在某些计算机上&＃xff0c;CPU的设计者们提供了一种解决方法&＃xff0c;就是通过使用一个隐藏的内部寄存器。在每条指令执行之前&＃xff0c;把程序计数器的内容复制到该寄存器。这些机器可能会有第二个寄存器&＃xff0c;用来提供哪些寄存器已经自动增加或者自动减少以及增减的数量等信息。通过这些信息&＃xff0c;操作系统可以消除引起缺页中断的指令所造成的所有影响&＃xff0c;并使指令可以重新开始执行。如果该信息不可用&＃xff0c;那么操作系统就要找出所发生的问题从而设法来修复它。看起来硬件设计者是不能解决这个问题了&＃xff0c;于是他们就推给操作系统的设计者来解决这个问题。
3.6.4 锁定内存中的页面
计算机有虚拟内存并不意味着I/O不起作用了。虚拟内存和I/O通过微妙的方式相互作用着。设想一个进程刚刚通过系统调用从文件或其他设备中读取数据到其地址空间中的缓冲区。在等待I/O完成时&＃xff0c;该进程被挂起&＃xff0c;另一个进程被允许运行&＃xff0c;而这个进程产生一个缺页中断。
如果分页算法是全局算法&＃xff0c;包含I/O缓冲区的页面会有很小的机会&＃xff08;但不是没有&＃xff09;被选中换出内存。如果一个I/O设备正处在对该页面进行DMA传输的过程之中&＃xff0c;将这个页面移出将会导致部分数据写入它们所属的缓冲区中&＃xff0c;而部分数据被写入到最新装入的页面中。一种解决方法是锁住正在做I/O操作的内存中的页面以保证它不会被移出内存。锁住一个页面通常称为在内存中钉住&＃xff08;pinning&＃xff09;页面。另一种方法是在内核缓冲区中完成所有的I/O操作&＃xff0c;然后再将数据复制到用户页面。
3.6.5 后备存储
在页面置换算法中&＃xff0c;已经知道如何选择换出内存的页面。但是却没有讨论当页面被换出时会存放在磁盘上的哪个位置。磁盘管理相关的问题&＃xff1a;
在磁盘上分配页面空间的最简单的算法是在磁盘上设置特殊的交换分区&＃xff0c;甚至从文件系统划分一块独立的磁盘&＃xff08;以平衡I/O负载&＃xff09;。大多数UNIX是这样处理的。在这个分区里没有普通的文件系统&＃xff0c;这样就消除了将文件偏移转换成块地址的开销。取而代之的是&＃xff0c;始终使用相应分区的起始块号。
当系统启动时&＃xff0c;该交换分区为空&＃xff0c;并在内存中以单独的项给出它的起始和大小。在最简单的情况下&＃xff0c;当第一个进程启动时&＃xff0c;留出与这个进程一样大的交换区块&＃xff0c;剩余的为总空间减去这个交换分区。当新进程启动后&＃xff0c;它们同样被分配与其核心映像同等大小的交换分区。进程结束后&＃xff0c;会释放其磁盘上的交换区。交换分区以空闲块列表的形式组织。更好的算法在第10章里讨论。
与每个进程对应的是其交换区的磁盘地址&＃xff0c;即进程映像所保存的地方。这一信息是记录在进程表里的。写回一个页面时&＃xff0c;计算写回地址的过程很简单&＃xff1a;将虚拟地址空间中页面的偏移量加到交换区的开始地址。但在进程启动前必须初始化交换区&＃xff0c;一种方法是将整个进程映像复制到交换区&＃xff0c;以便随时可将所需内容装入&＃xff0c;另一种方法是将整个进程装入内存&＃xff0c;并在需要时换出。
但这种简单模式有一个问题&＃xff1a;进程在启动后可能增大&＃xff0c;尽管程序正文通常是固定的&＃xff0c;但数据有时会增长&＃xff0c;堆栈也总是在随时增长。这样&＃xff0c;最好为正文、数据和堆栈分别保留交换区&＃xff0c;并且允许这些交换区在磁盘上多于一个块。
另一个极端的情况是事先什么也不分配&＃xff0c;在页面换出时为其分配磁盘空间&＃xff0c;并在换入时回收磁盘空间&＃xff0c;这样内存中的进程不必固定于任何交换空间。其缺点是内存中每个页面都要记录相应的磁盘地址。换言之&＃xff0c;每个进程都必须有一张表&＃xff0c;记录每一个页面在磁盘上的位置。这两个方案如图3-29所示。
在图3-29a中&＃xff0c;有一个带有8个页面的页表。页面0、3、4和6在内存中。页面1、2、5和7在磁盘上。磁盘上的交换区与进程虚拟地址空间&＃xff08;8页面&＃xff09;一样大&＃xff0c;每个页面有固定的位置&＃xff0c;当它从内存中被淘汰时&＃xff0c;便写到相应位置。该地址的计算需要知道进程的分页区域的起始位置&＃xff0c;因为页面是按照它们的虚拟页号的顺序连续存储的。内存中的页面通常在磁盘上有镜像副本&＃xff0c;但是如果页面装入后被修改过&＃xff0c;那么这个副本就可能是过期的了。内存中的深色页面表示不在内存&＃xff0c;磁盘上的深色页面&＃xff08;原则上&＃xff09;被内存中的副本所替代&＃xff0c;但如果有一个内存页面要被换回磁盘并且该页面在装入内存后没有被修改过&＃xff0c;那么将使用磁盘中&＃xff08;深色&＃xff09;的副本。
在图3-29b中&＃xff0c;页面在磁盘上没有固定地址。当页面换出时&＃xff0c;要及时选择一个空磁盘页面并据此来更新磁盘映射&＃xff08;每个虚拟页面都有一个磁盘地址空间&＃xff09;。内存中的页面在磁盘上没有副本。它们在磁盘映射表中的表项包含一个非法的磁盘地址或者一个表示它们未被使用的标记位。
不能保证总能够实现固定的交换分区。例如&＃xff0c;没有磁盘分区可用时。在这种情况下&＃xff0c;可以利用正常文件系统中的一个或多个较大的、事前定位的文件。Windows就使用这个方法。然而&＃xff0c;可以利用优化方法减少所需的磁盘空间量。既然每个进程的程序正文来自文件系统中某个&＃xff08;可执行的&＃xff09;文件&＃xff0c;这个可执行文件就可用作交换区。而更好的方法是&＃xff0c;由于程序正文通常是只读的&＃xff0c;当内存资源紧张、程序页不得不移出内存时&＃xff0c;尽管丢弃它们&＃xff0c;在需要的时候再从可执行文件读入即可。共享库也可以用这个方式工作。
3.6.6 策略和机制的分离
控制系统复杂度的一种重要方法就是把策略从机制中分离出来。通过使大多数存储管理器作为用户级进程运行&＃xff0c;就可以把该原则应用到存储管理中。
一个如何分离策略和机制的简单例子可以参见图3-30。其中存储管理系统被分为三个部分&＃xff1a;
1) 一个底层MMU处理程序。
2) 一个作为内核一部分的缺页中断处理程序。
3) 一个运行在用户空间中的外部页面调度程序。
所有关于MMU工作的细节都被封装在MMU处理程序中&＃xff0c;该程序的代码是与机器相关的&＃xff0c;而且操作系统每应用到一个新平台就要被重写一次。缺页中断处理程序是与机器无关的代码&＃xff0c;包含大多数分页机制。策略主要由作为用户进程运行的外部页面调度程序所决定。
当一个进程启动时&＃xff0c;需要通知外部页面调度程序以便建立进程页面映射&＃xff0c;如果需要的话还要在磁盘上分配后备存储。当进程正在运行时&＃xff0c;它可能要把新对象映射到它的地址空间&＃xff0c;所以还要再一次通知外部页面调度程序。
一旦进程开始运行&＃xff0c;就有可能出现缺页中断。缺页中断处理程序找出需要哪个虚拟页面&＃xff0c;并发送一条消息给外部页面调度程序告诉它发生了什么问题。外部页面调度程序从磁盘中读入所需的页面&＃xff0c;把它复制到自己的地址空间的某一位置。然后告诉缺页中断处理程序该页面的位置。缺页中断处理程序从外部页面调度程序的地址空间中清除该页面的映射&＃xff0c;然后请求MMU处理程序把它放到用户地址空间的正确位置&＃xff0c;随后就可以重新启动用户进程了。
这个实现方案没有给出放置页面置换算法的位置。把它放在外部页面调度程序中比较简单&＃xff0c;但会有一些问题。这里有一条原则就是外部页面调度程序无权访问所有页面的R位和M位。这些二进制位在许多页面置换算法起重要作用。这样就需要有某种机制把该信息传递给外部页面调度程序&＃xff0c;或者把页面置换算法放到内核中。在后一种情况下&＃xff0c;缺页中断处理程序会告诉外部页面调度程序它所选择的要淘汰的页面并提供数据&＃xff0c;方法是把数据映射到外部页面调度程序的地址空间中或者把它包含到一条消息中。两种方法中&＃xff0c;外部页面调度程序都把数据写到磁盘上。
这种实现的主要优势是有更多的模块化代码和更好的适应性。主要缺点是由于多次交叉“用户&＃xff0d;内核”边界引起的额外开销&＃xff0c;以及系统模块间消息传递所造成的额外开销。现在看来&＃xff0c;这一主题有很多争议&＃xff0c;但是随着计算机越来越快&＃xff0c;软件越来越复杂&＃xff0c;从长远来看&＃xff0c;对于大多数实现&＃xff0c;为了获得更高的可靠性而牺牲一些性能也是可以接受的。
京公网安备 11010802041100号