计算机操作系统中的虚拟存储管理技术

5.5.1 虚拟存储器的概念

在前面介绍的各种存储管理方式中，必须为作业分配足够的存储空间，以装入作业的全部内容，作业的大小不能超出内存的可用空间，否则作业无法运行。但当把有关作业的全部信息都装入内存后，作业执行时不会同时使用全部信息的，有些部分运行一遍后就再也不用，甚至有些部分在作业执行的整个过程中都不会被调用（如错误处理部分）。作业在运行时不用的，或暂时不用的，或某种条件下才用的程序和数据，全部驻留于内存中是对宝贵的内存资源的一种浪费，大大降低了内存的利用率。于是提出了这样的想法：作业运行时，能否不把作业的全部信息同时装入内存，而是将其中当前使用部分先装入内存，其余暂时不用的部分先存放在外存中，待用到这些信息时，再由系统自动把它们装入到内存中，这就是虚拟存储器的基本思路。当一个进程访问的程序和数据在内存中，即可顺序执行。当处理器访问的程序或数据不在内存中，无法执行时，则需要由系统自动将这部分信息装入内存，这叫部分装入；如若此时内存中没有足够大的空闲空间，便需要把内存中暂时不用的信息转移到外存上去，这叫部分对换。如果“部分装入、部分对换”这个问题能解决的话，当内存空间小于作业需要量时，作业也能执行；更进一步，多个作业存储总量超出内存总容量时，也可以把它们全部装入内存，实现多道程序运行。这样不仅使内存空间能充分地被利用，而且用户编制程序时可以不必考虑内存的实际容量的大小，允许用户的逻辑地址空间大于内存的绝对地址空间。对于用户来说，好像计算机系统具有一个容量硕大的内存，把它称作为“虚拟存储器”（virtual memory）。

虚拟存储器的定义：在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理内存容量大得多的，可寻址的一种“内存储器”。实际上虚拟存储器是为扩大内存而采用的一种设计技巧，虚拟存储器的容量与内存大小无直接关系，而受限于计算机的地址结构及可用的辅助存储器的容量，如果地址线是20位，那么程序可寻址范围是1 MB，Intel pentium的地址线是32位，则程序可寻址范围是4 GB，Windows 2000／XP便为应用程序提供了一个4 GB的逻辑内存。图5-23给出了虚拟存储器的概念图。

图5-23 虚拟存储器概念图

在作业信息不全部装入内存的情况下能否保证作业的正确运行。回答是肯定的。早在1968年就开始研究了程序执行时的局部性（principle of locality）原理，发现程序和数据的访问都有聚集成群的倾向，在一个时间段内，仅使用其中一小部分（称空间局部性），或者最近访问过的程序代码和数据，很快又被访问的可能性很大（称为时间局部性）。对程序的执行进行分析可发现以下情况：

第一，程序中只有少量分支和过程调用，大部分是顺序执行的，即要执行的下一条指令紧跟在当前执行指令之后。

第二，程序往往包含若干个循环，这些是由相对较少的几个指令重复若干次组成的，在循环过程中，计算被限制在程序中一个很小的相邻部分中（如计数循环）。

第三，很少会出现连续不断的过程调用序列，相反，程序中过程调用被限制在一个小的范围内，因而在一段时间内，指令引用被局限在很少几个过程中。

第四，对于连续访问数组之类的数据结构，往往是对存储区域中的数据或相邻位置的数据（如动态数组）的操作。

第五，程序中有些部分是彼此互斥的，不是每次运行时都用到的，例如出错处理程序，仅当在数据和计算中出现错误时才会用到，正常情况下，出错处理程序不放在内存，不会影响整个程序的运行。

上述种种情况充分说明，作业执行时没有必要把全部信息同时存放入内存中，而仅仅装入一部分的假设是合理的。在装入部分信息的情况下，只要调度合适，不仅可以正常运行，而且可以在内存中放置更多进程，有利于充分利用处理器和提高内存的利用率。

虚拟存储器是基于程序局部性原理上的一种假想的而不是物理存在的存储器，允许用户程序以逻辑地址来寻址，而不必考虑物理上可获得的内存大小，这种将物理空间和逻辑空间分开编址但又统一管理和使用的技术为用户编程提供了极大方便。此时，用户作业空间称虚拟地址空间，其中的地址称虚地址。要实现虚拟存储器，必须解决好以下有关问题：内存统一管理问题、逻辑地址到物理地址的转换问题、部分装入和部分对换问题。

虚拟存储器的思想早在20世纪60年代初期就已在英国的Atlas计算机上出现。20世纪70年代初期开始推广应用，逐步为广大计算机研制者和用户接受，虚拟存储技术不仅用于大型机上，而且随着微型机的迅速发展，也研制出了微型机虚拟存储系统。实现虚拟存储器系统要付出一定的开销，其中包括管理地址转换各种数据结构所用的存储开销、执行地址转换的指令花费的时间开销和内存与外存交换页或段的I／O开销等。目前，虚拟存储管理主要采用以下几种技术实现：请求分页式、请求分段式和请求段页式虚拟存储管理。

5.5.2 请求分页虚拟存储管理

1.分页式虚拟存储系统的硬件支撑

操作系统的存储管理依靠低层硬件的支撑来完成任务，该硬件称为内存管理单元MMU（memory management unit），现代计算机中的MMU完成逻辑地址到物理地址的转换功能，通常它是由一个或一组芯片组成，接受虚拟地址作为输入，物理地址作为输出，直接送到总线上，对内存单元进行寻址，其位置和功能如图5-24a所示，其内部执行过程如图5-24b所示。

MMU主要功能包括：

图5-24 内存管理单元MMU

（1）管理硬件页表基址寄存器。每当发生进程上下文切换时，由系统负责把将要运行进程页表的基地址装入该寄存器，此页表便成为活动页表，MMU只对由硬件页表基址寄存器指出的活动页表进行操作。

（2）分解逻辑地址。把逻辑地址分解为页面号和页内位移，以便进行地址转换。

（3）管理快表TLB。MMU对TLB的管理有两项，一是直接查找快表，找到相应物理块后去拼接物理地址；二是执行TLB的两个基本操作——装入表目和清除表目，每次发生快表查找不命中的情况，待缺页中断处理结束后负责把相应页面和页框装入快表。此外，在每次写硬件页表基址寄存器时，负责清除快表项，将TLB清空。

（4）访问页表。当TLB不命中时，对进程页表的访问有软件处理和硬件处理两种方式。软件处理方式下，由MMU产生中断，转让给操作系统访问进程页表并修改TLB。硬件处理方式下，由MMU根据硬件页表基址寄存器直接访问进程页表。

（5）当出现页表中有页失效位或页面访问越界位时，MMU发出缺页中断或越界中断，并将控制权交给内核存储管理处理。

（6）MMU负责设置和检查页表中的引用位、修改位、有效位和保护权限等各个特征位。

下面来简单介绍MMU的工作过程。假如给出一个虚地址8196（二进制为0010000000 000100），MMU进行映射，输入的16位虚地址被解释为4位页号和12位的偏移量。用页号做索引，以查找到该虚页对应的物理块号。如果在内存位为1，表明该页在内存，把物理块号拷贝到输出寄存器的高三位中，再加上虚地址中的12位偏移，就生成了15位的物理地址（二进制为110000000000100），并把它作为物理地址送到内存总线。如果在主存位为0，则将引起一个缺页中断，由操作系统进行调页处理。

2.请求分页虚拟存储系统的基本原理

请求分页虚拟存储系统是将作业信息的副本存放在磁盘中，当作业被调度投入运行时，并不把作业的程序和数据全部装入内存，而仅仅装入即将使用的那些页面，在执行过程中访问到不在内存的页面时，再把它们动态地装入。用得较多的分页式虚拟存储管理是请求分页（demand paging），当需要执行的某条指令或使用的某个数据，不在主存时，产生一个缺页中断，由操作系统把该指令或数据所在的页面从磁盘调入内存。

由于请求分页虚存管理与分页式实存管理不同，仅将作业或进程的一部分放在内存中，执行过程中必然会发生某些页面不在内存的情况，那么如何发现页面不在内存中呢？如何处理这种情况呢？采用的办法是扩充页表的内容，增加驻留标志位和页面外存的地址等信息，扩充后的页表见图5-25。

驻留标志位（又称页失效中断位）表明该页是否已经装入内存，为1，则表示该页已经在内存；若驻留标志位为0，则表明不在内存中，此时产生一个缺页中断信号，可以根据外存地址将这个页面调入内存。缺页中断是由于发现当前访问页面不在内存时由硬件产生的一种特殊中断信号，通常CPU会在一条指令执行完成后再去检查是否有（一般）中断到达，也就是说只能在两条指令之间响应（一般）中断，但缺页中断却是在指令执行期间产生并处理的。而且一条指令可能涉及多个页面，例如指令本身跨页、指令处理的数据跨页，完全有可能执行一条指令过程中发生多次缺页中断。为此，系统需要提供寄存器和特殊的返回指令等硬件设施，确保在出现缺页中断时，保存未完成指令的状态和恢复原指令的执行。

为了对页面实施保护和淘汰等各种控制，可在页表中增加标志位，其他标志位包括修改位（Modified）、访问位（Referenced）和访问权限位等，用来跟踪页面的使用情况。当一个页面被修改后，硬件自动设置修改位，一旦修改位被设置，当该页被调出内存时必须先重新被写回磁盘，访问位则在该页被访问时（无论是读或写）设置，操作系统进行页面淘汰时考虑。访问权限位则限定了该页的访问权限如是否可写。有的操作系统中，还增加了年龄标志，表示页面在内存中已有多久未被访问过，用于页面淘汰。

可以看出，在请求分页虚拟存储系统中，页表的作用主要有三点：获得物理块号以实现虚实地址转换，设置各种访问控制位对页面信息进行保护，设置各种标志位来实现相应控制功能（如缺页标志、脏页标志、访问标志、锁定标志和淘汰使用的标志等）。

下面来讨论使用快表但页表放在内存的情况下（目前多数系统采用这个方案），请求分页虚存地址转换过程：当进程被调度到执行时，操作系统自动把该进程PCB中的页表起始地址装入到硬件页表基址寄存器中，此后进程开始执行并要访问某个虚拟地址，MMU硬件开始工作，完成图5-26虚线框内的任务，地址转换过程为：

（1）MMU接受CPU传送过来的虚地址并自动按页面大小把虚地址从某位起分解成两部分：页号和页内位移。

（2）以页号为索引搜索快表TLB。

图5-26 请求分页虚存地址转换

（3）如果命中TLB，立即送出物理块号，并与页内位移拼接成物理地址，然后进行权限检查，如通过进程就可以访问物理地址了。

（4）如果未命中TLB，以页号为索引搜索进程页表（硬件直接处理），页表的基址由硬件页表基址寄存器指出。

（5）如果在页表中找到此页面，说明该页面己在内存，可读出物理块号，并与页内位移拼接成物理地址，然后进行权限检查，如获通过进程就可以访问物理地址了。

（6）同时要把这个页面的信息装入快表TLB，以备再次访问。

（7）如果发现页表中对应页面页失效，MMU就发出一个缺页中断，请求操作系统进行调页处理，MMU工作结束。

（8）由存储管理软件按替换策略进行调页。

（9）把该页面装入内存，修改页表，返回用户进程重新执行被中断的指令。

MMU发现缺页并发出缺页中断后，操作系统进行缺页中断处理的过程如下：

步1：查看内存是否有空闲物理块，如有则可以找出一个空闲物理块，修改内存管理表和相应页表项内容，转步4。

步2：如内存中无空闲页框，按替换算法选择一个淘汰页面，淘汰页面被写过或修改过吗？若未则转步4；若是则转步3。

步3：若淘汰页面被写过或修改过，那么把淘汰页面的内容写回外存，转步4。

步4：按该页在外存中的地址把此页面调入，同时修改进程页表相应项；返回用户进程，重新执行被中断的指令。

在分页虚拟存储系统中，由于作业的页面是根据进程的请求装入内存的，因此这种存储系统也称为请求分页虚拟存储器管理。其有以下优点：作业的程序和数据可以按页分散存放在内存中，减少了移动的开销，有效地解决了碎片问题；由于采用请求分页虚存管理，用户可用的内存空间大大扩展，既有利于改进内存利用率，又有利于多道程序运行。其主要缺点是：要有一定硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大，此外，页内会出现碎片，如果页面较大，则内存的损失仍然较大。

3.页面装入策略和清除策略

页面装入策略决定何时把一个页面装入内存，有两种策略可供选择：请求页（demand paging）调入和预先页（prepaging）调入。

请求页调度是仅当需要访问程序和数据时，通过发生缺页中断并由缺页中断处理程序分配物理块再把所在页面装入内存。这样当某个进程第一次执行时，开始会有许多缺页中断，随着越来越多的页面装入内存，根据局部性原理，大多数未来访问的程序和数据都在最近被装入内存的页面中，一段时间之后，缺页中断就会下降到较低水平，程序进入相对平稳阶段。这种策略的主要优点是确保只有被访问的页才调入内存，节省内存空间；缺点是处理缺页中断次数过多和调页的系统开销较大，由于每次仅调一页，增加了磁盘I／O次数。

预先页调度装入内存的页并不是缺页中断请求的页面，而是由操作系统依据某种算法，动态预测进程最可能要访问哪些页面，在使用之前预先调入内存，尽量做到进程在访问页面之前已经预先调入该页，而且一次调入若干个页面，而不是像请求页那样仅调入一个页面。由于进程的页面大多数连续存放在磁盘中，一次调入多个连续的页面能减少磁盘I／O启动次数，节省寻道和搜索时间。但是如果调入的一批页面中多数未被使用，则效率较低，可见预先调页要建立在预测的基础上，目前所用预先调页的成功率在50%左右。

许多系统把预先调页调度应用在进程刚开始执行时（装入进程初始工作集）或每次缺页中断发生时（同时调入马上要用到的一些页面），对于前一种情况需要程序员提供所需程序部分的信息。预调式调度和进程的对换不是一码事，这点需要注意。

回收策略是与装入策略相对的，它需要考虑何时把一个修改过的页面写回磁盘，常用的两种方法是请求页式回收和预约式回收。请求页式回收是仅当被选中换出的页之前又被修改过，才把这个页面写回磁盘。预约式回收对更改过的页面，在需要调出之前就把它们都写回磁盘，因此可以成批进行。两个方法都有缺点，对于预约式回收，写出的页仍然在内存中，直到页替换算法选中该页从内存中移出，它允许成批地把页面写出，但如若刚刚写了很多页面，在它们被替换前，其中大部分又被更改，预约式回收就毫无意义。对于请求页式回收，写出一页是在读进一个新页之前进行的，它要双倍操作，虽然仅需要写出一页，但引发进程两次I／O操作，会降低CPU使用效率。

比较好的方法是采用页面缓冲技术，其策略如下：仅回收淘汰的页面，回收操作和替换操作不用同时进行。在页面缓冲中，被淘汰页面进入两个队列，修改页面队列和非修改页面队列。在修改页面队列中的页不时地成批写出并加入到非修改页面队列；非修改页面队列中的页面，当它被再次引用时回收，或者淘汰掉以做替换。

4.页面分配策略

分页式虚拟存储系统解决了内存实际容量的约束，能使更多的作业多道运行，进而提高了系统的效率，但缺页中断处理要付出代价的页面的调入、调出要会增加I／O的负担，影响系统效率，因此应尽可能减少缺页中断的次数。如何在相互竞争的多个可运行进程之间分配内存资源，究竟如何为进程分配页框？当出现一次缺页中断时，页面替换算法的作用范围究竟应该局限于本进程的页面还是整个系统的页面？这两个问题涉及进程驻留页面的管理。

在分页式虚拟存储管理中，不可能也没必要把一个进程的所有页面调入内存，那么操作系统决定为某进程分配多大的主存空间，需要考虑以下因素：

（1）分配给一个进程的空间越小，同一时间处于内存的进程就越多，于是至少有一个进程处于就绪态的可能性就越大，从而可减少进程对换的时间。

（2）如果进程只有一小部分在内存里，即使它的局部性很好，缺页中断率还会相当高。

（3）因为程序的局部性原理，分配给一个进程的主存超过一定限度后，再增加主存空间，也不会明显降低进程的缺页中断率。

基于这些因素，在请求分页式系统中，可采用两种策略分配物理块给进程：固定分配和可变分配。

如果在进程生命周期中，保持分配的物理块数固定不变，称为固定分配。在进程创建时，根据进程类型和程序员的要求决定分配的物理块数，只要有一个缺页中断产生，该进程就会有一页被替换。如果进程生命周期中，分得的物理块数可变，称页面分配为可变分配。当进程执行的某一阶段缺页率较高，说明进程程序目前的局部性较差，系统可多分些物理块以降低缺页率，反之说明进程程序目前的局部性较好，可以减少分给进程的页框数。固定分配策略缺少灵活性，而可变分配的性能会更好些，被许多操作系统所采用。采用可变分配策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况，这会增加操作系统的开销。

在进行页面替换时，可采用两种策略：局部替换和全局替换。如果页面替换算法的作用范围是整个系统，称为全局页面替换算法，它可以在可运行进程之间动态地分配物理块。如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法，它实际上需要为每个进程分配固定的页框。在通常情况下，尤其是驻留页面数量会在进程运行期间发生较大变化时，全局算法比局部算法好。如果使用局部算法，即使有大量的空闲物理块存在，需要物理量数量的增长仍然会导致颠簸；如果需要的少了，局部算法又会浪费内存。但是使用全局算法时，系统必须不断地确定应该给每个进程分配多少内存，这是比较困难的。

固定分配往往和局部替换策略配合使用，每个进程运行期间分得的物理块数不再改变，如果发生缺页中断，只能从进程在内存的页面中选出一页替换，以保证进程的物理块总数不变。这种策略的主要难点在于应给每个进程分配多少个物理块。分少了，缺页中断率高；分多了，会使主存中能同时执行的进程数减少，进而造成处理器空闲和其他设备空闲，并把许多时间花费在对换上。采用固定分配算法时，系统把可供分配的物理块分配给进程，可采用下列方式：

（1）平均分配，不论进程大小，每个进程得到的物理块数相等，这样做会造成大进程缺页中断率高。

（2）按比例分配，大进程获得物理块多，小进程获得物理块少。

（3）优先权分配，可以把物理块分成两类，一类按比例分配，另一类根据进程优先权适当增加份额。

可变分配往往和全局替换策略配合使用，这是采用得较多的一种分配和替换算法。先为系统中的每个进程分配一定数目的物理块，操作系统自己保留若干空闲物理块，当一个进程发生缺页中断时，从系统空闲物理块中选一个给进程，添加到它的驻留集中，于是可把缺页调入这个物理块中，这样产生缺页中断的进程的内存空间会逐渐增大。凡是产生缺页中断的进程都能获得新的物理块，有助于减少系统的缺页中断总次数，直到系统拥有的空闲物理块耗尽，才会从主存中选择一页淘汰，该页可以是内存中任一进程的页面，这样又会使那个进程的物理块数减少，缺页中断率上升。这个方法的难点在于选择哪个页面进行替换，选择范围是内存中除锁定外的全部物理块，应用一种淘汰策略选页时，并没有规则可以确定哪一个进程如果被选中进程的物理块块数减少会严重影响它的执行，那么这个选择就不是最佳的。解决可变分配全局替换性能问题的一种方法是使用页缓冲，按这种方法选择替换哪一页就不太重要了，因为如果在下次重写这些页面之前访问到的话，相应页面是可以回收的。可变分配配合局部替换可以克服可变分配全局替换的缺点，其实现要点如下：

（1）新进程装入内存时，根据应用类型、程序要求，分配给一定数目物理块，可用请求页式或预调式完成这个分配。

（2）当产生缺页中断时，从产生缺页中断的进程的驻留集中选一个页面替换。

（3）不时重新评价进程的分配，增加或减少分配给进程的物理块以改善系统总的性能。

5.页面替换策略

实现虚拟存储器能给用户提供一个容量很大的存储空间，但当内存空间已装满而又要装入新页时，必须按一定的算法把已在内存的一些页面调出去，这个工作称页面替换。所谓页面替换就是用来确定应该淘汰哪页的算法，也称淘汰算法。算法的选择非常重要，选择了不适合的算法，刚被淘汰的页面又立即要用，又要把它调入，而调入不久再被淘汰，淘汰不久再被调入。如此反复，使得整个系统的页面调度非常频繁以至于大部时间都花在来回调度页面上。这种处理机花费大量时间用于对换页面而不是执行计算任务的现象称为“抖动”（thrashing），又称“颠簸”，一个好的调度算法应减少和避免抖动现象。

替换策略要处理的是：当把一个新的页面调入内存时，选择已在内存的哪个页面做替换。替换策略需要考虑：

（1）分给每个活跃进程多少物理块？

（2）页面替换时，仅限于缺页中断进程还是包括内存中所有页面？

（3）在被考虑的页面集合中，选出哪个页面进行替换？

为了衡量替换算法的优劣，考虑在固定空间的前提下来讨论各种页面替换算法。这一类算法假定每道作业都分到固定数量的内存空间，即每道作业占用的内存物理块数不允许因页面替换算法而改变。如何衡量一个算法的好坏呢？假定作业p共计n页，而系统分配给它的物理块只有m块（m、n均为正整数，且1≤m≤n），即最多内存中只能容纳该作业的m页。如果作业p在运行中成功的访问次数为S（即所访问的页在内存中），不成功的访问次数为F（即缺页中断次数），则总的访问次数A为

A＝S＋F

又定义

f＝F／A

则称f为缺页中断率。影响缺页中断率f的因素有：

（1）分配的物理块数。作业分得的物理块数多，则缺页中断率就低；反之，缺页中断率就高。

（2）页面大小。如果划分的页面大，则缺页中断率就低；否则，缺页中断率就高。

（3）页面替换算法。替换算法的优劣影响缺页中断次数。

（4）程序特性。程序编制的方法不同，对缺页中断的次数有很大影响，程序的局部性要好。

例：有一个程序要将128×128的数组置初值为“0”。假定分给该程序的物理块数只有一块，页面的尺寸为128个字，数组中的元素每一行存放在一页中，开始时第一页在内存。若程序如下编制：

int ar ray［128］［128］(www.xing528.com)

for（j＝0；j＜128；j＋＋）

for（i＝0；i＜128；i＋＋）

｛array［i］［j］＝0｝；

则每执行一次array［i］［j］＝0就要产生一次缺页中断，于是总共要产生（128×128－1）次缺页中断。如果重新编写如下：

int ar ray［128］［128］

for（i＝0；i＜128；i＋＋）

for（j＝0；j＜128；j＋＋）

｛array［i］［j］＝0｝；

那么总共只产生（128－1）次缺页中断。

显然，虚拟存储器的效率与程序的局部性程度密切相关，局部性的程度因程序而异，一般说，总希望编出的程序具有较好的局部性。这样程序执行时可经常集中在几个页面上进行访问，减少缺页中断率。

同样存储容量与缺页中断次数有关。从理论上讲，分配内存后，每个作业只要能分到一个物理块就可以执行，从表面上看，这增加了可同时运行的作业个数，但却牺牲了效率。试验表明，当内存容量增大到一定程度，缺页中断次数的减少就不明显了。大多数程序都有一个物理块值，超过该值再增加内存容量收效就不大了，这个值随程序而变，试验分析表明，对每个程序来说，要使其有效地工作，它在内存中的页面数应不可低于它的总页面数的一半。即如果一个作业总共有n页，那么只有为它分配至少n／2个物理块时，才可以获得较高效率。

5.5.3 页面置换算法

下面介绍页面置换算法。一个理想的置换算法是：当要调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问或距现在最长时间后再访问的页。这种调度算法缺页中断率最低。但这样的算法是无法实现的，因为在程序运行过程中无法对以后要使用的页面做出精确的断言。不过这个理论上的算法可以用来作为衡量各种具体算法的标准。该算法由Belady提出来的，所以被称作Belady算法，又叫作最佳置换算法（Optimal）。举例：假如某进程的页面号引用串为：6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1，系统为进程分配三个内存物理块，其置换过程如下图。最佳页面置换算法缺页6次，缺页率为6／21。

图5-27 最佳页面置换算法

Belady算法是一种理想化的页面调度算法，下面分别介绍几个比较典型又实用的页面调度算法。

1）随机页面置换算法

要淘汰的页面由随机数产生程序所产生的随机数来确定，选择一个不常使用的页面会使系统性能较好，但这种调度算法做不到，虽很简单但效率却低，一般不采用。

2）先进先出页面置换算法（first in first out，FIFO）

先进先出调度算法是一种低开销的页面置换算法，基于程序总是按线性顺序来访问物理空间这一假设。这种算法总是淘汰最先调入内存的那一页，或者说在内存中驻留时间最长的那一页（锁定的页面除外），认为驻留时间最长的页不再被使用的可能性较大。这种算法可以采用不同的技术来实现。

假如某进程的页面号引用串同样为：6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1，系统为进程分配三个内存物理块。其置换过程如下图。FIFO置换算法缺页12次，缺页率为12／21。

图5-28 FIFO页面置换算法

这种置换算法较易实现，对具有线性顺序特性的程序比较适用，而对其他特性的程序效率不高，因为在内存中驻留时间最长的页面未必是最长时间以后才使用的页面，很可能有最近要被访问的页。也就是说，如果某一个页面要不断地被使用，采用FIFO算法，在一定的时间以后就会变成驻留时间最长的页，这时若把它淘汰了，可能立即又要用，必须重新调入。据估计，采用FIFO调度算法，缺页中断率为最佳算法的2至3倍。

3）最近最久未使用页面置换算法（least recently used，LRU）

最近最久未使用页面置换算法是一种通用的有效算法，被操作系统、数据库管理系统和专用文件系统广泛采用。该算法淘汰的页面是在最近一段时间里较久未被访问的那一页。它是根据程序执行时所具有的局部性来考虑的，即那些刚被使用过的页面，可能马上还要被使用，而那些在较长时间里未被使用的页面，一般说可能不会马上使用到。

为了能比较准确地淘汰最近最少使用的页，从理论上讲，必须维护一个特殊的队列——页面淘汰队列。该队列中存放当前在内存中的页号，每当访问一页时就调整一次，使队列尾总指向最近访问的页，队列头就是最近最少用的页。发生缺页中断时总淘汰队列头所指示的页；而执行一次页面访问后，需要从队列中把该页调整到队列尾。

假如在LRU置换算法中引用串同样为：6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1，为进程分配三个内存物理块。置换过程如下图所示。其缺页9次，缺页率为9／21。

图5-29 LRU页面置换算法

从实现角度讲，LRU算法的操作复杂，代价极高，因此，在实现时往往采用模拟的方法。

第一种模拟方法可以通过设置标志位来实现，给每一页设置一个引用标志位R，每次访问某一页时，由硬件将该页的标志R置1，隔一定的时间t将所有页的标志R均清0。在发生缺页中断时，从标志位R为0的那些页中挑选一页淘汰。在挑选到要淘汰的页后，也将所有其他页的标志R清0。这种实现方法开销小，但t的大小不易确定，精确性差。t大了，缺页中断时所有页的标志R值均为1；t小了，缺页中断时，可能所有页的R值均为0，同样很难挑选出应该淘汰的页面。

第二种模拟方法是为每个页设置一个多位寄存器r。当页面被访问时，对应的寄存器的最左边位置1；每隔时间t，将r寄存器右移一位；在发生缺页中断时，找最小数值的r寄存器对应的页面淘汰。

例如，r寄存器共有4位，页面P0、P1、P2在T1、T2、T3时刻的r寄存器内容如下：

在时刻T3时，应该淘汰的页面是P2。这是因为同P0比较，它不是最近被访问的页面；同P1比较，虽然它们在时刻T3都没有被访问，且在时刻T2都被访问过，但在时刻T1时P2没有被访问。

显然，第二种模拟方法优于第一种模拟方法。

第三种模拟方法是为每个页面设置一个多位计数器。每当访问一页时，使它对应的计数器加1。当发生缺页中断时，可选择计数值最小的对应页面淘汰，并将所有计数器全部清0，它是在最近一段时间里最不常用的页面。这种算法实现不难，但代价太高，而且选择多大的t也是个难题。

4）第二次机会页面置换算法

FIFO算法可能会把经常使用的页面淘汰掉，可以对FIFO算法进行改进，把FIFO算法与页表中的“引用位”结合起来使用，算法可实现如下：首先检查FIFO中的队首页面（这是最早进入内存的页面），如果它的“引用位”为0，那么该页面既老又没有用，选择该页面淘汰；如果它的“引用位”是1，说明虽然它进入内存较早，但最近仍在使用。把它的“引用位”清0，并把这个页面移到队尾，把它看作是一个新调入的页，再给它一个机会。这一算法称为第二次机会（second chance）算法，其含义是最先进入内存的页面，如果最近还在被使用的话，仍然有机会作为像一个新调入页面一样留在内存中。

5）时钟页面置换算法（clock policy）

如果利用标准队列机制构造FIFO队列，第二次机会页面调度算法将可能产生频繁的出队入队，实现代价较大。可采用循环队列机制构造页面队列，这样就形成了一个类似于钟表面的环形表，队列指针则相当于钟表面上的表针，指向可能要淘汰的页面，这就是时钟页面置换算法的得名。时钟页面置换算法与第二次机会算法本质上没有区别，仅仅是实现方法不同并做了改进，仍然要使用页表中的“访问位”，把作业已调入内存的页面链成循环队列，用一个指针指向循环队列中下一个将被替换的页面，算法见图5-30。

图5-30 Clock置换算法的流程和示例

（1）页面首次装入内存时，其“访问位”置1。

（2）在内存中的任何一个页面被访问时，其“访问位”置1。

（3）淘汰页面时，存储管理从指针当前指向的页面开始扫描循环队列，把“访问位”为1的页面的“访问位”清成0，并跳过这个页面；把“访问位”为0的页面淘汰掉，指针推进一步。

（4）扫描循环队列时，如果所有页面的“访问位”为1，指针就会绕整个循环队列一圈，把所有页面的“访问位”清0；指针停在起始位置，并淘汰掉这一页，然后指针推进一步。

淘汰一个页面时，如果已被修改过，必须将它重新写回磁盘；但如果淘汰的是未被修改过的页面，就不需要写回磁盘操作了，这样看来淘汰修改过的页面比淘汰未被修改过的页面开销要大。如果把页表中的“访问位”和“修改位”结合起来使用可以改进时钟页面替换算法，它们一共组合成四种情况：

（1）最近没有被访问，没有被修改（r＝0，m＝0）。

（2）最近被访问，没有被修改（r＝1，m＝0）。

（3）最近没有被访问，但被修改（r＝0，m＝1）。

（4）最近被访问过，也被修改过（r＝1，m＝1）。

改进的时钟算法可如下执行：

步1：选择最佳淘汰页面，从指针当前位置开始，扫描循环队列。扫描过程中不改变“访问位”，把第一个r＝0，m＝0的页面作为淘汰页面。

步2：如果步1失败，再次从原位置开始，查找r＝0且m＝1的页面，把满足条件的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的“访问位”r置0。

步3：如果步2失败，指针再次回到了起始位置，由于此时所有页面的“访问位”r均已为0，再转向步1操作，必要时再做步2操作，这次一定可以挑出一个可淘汰的页面。

改进的时钟页面替换算法就是扫描循环队列中的所有页面，寻找一个既没有被修改且最近又没有被访问过的页面，把这样的页面挑出来作为首选页面淘汰是因为没有被修改过，淘汰时不用把它写回磁盘。如果第一步没找到这样的页面，再次扫描循环队列，欲寻找一个被修改过但最近没有被访问过的页面；虽然淘汰这种页面需写回磁盘，但依据程序局部性原理，这类页面不会马上再次使用。如果第二步也失败了，则所有页面已被标记为最近未被访问，可进入第三步扫描。其主要优点是没有被修改过的页面会被优先选出来，淘汰这种页面时不必写回磁盘，从而节省时间，但查找一个淘汰页面可能会经过多轮扫描，算法的实现开销较大。

下面给出一个例子，分别用OPT、FIFO、LRU和时钟替换算法来计算缺页中断次数和被淘汰的页面，并对它们的性能做简单的比较。假设采用固定分配策略，进程分得三个物理块，它在执行中按下列次序引用5个独立的页面：2，3，2，1，5，2，4，5，3，2，5，2。图5-31给出了四种算法的计算过程和结果。

图5-31 四种算法比较

从图中可以看出，OPT共产生3次缺页中断，LRU共产生4次缺页中断，FIFO共产生6次缺页中断，时钟算法共产生5次缺页中断，图中*表示相应页面的“访问位”为1，可以看出FIFO性能最差，OPT性能最好，而时钟算法与LRU十分接近。

图5-32 四种算法对比曲线

图5-32是用上述四种算法计算的结果曲线。假设分配给进程的物理块数是固定的，运行的程序共有0.25×106次页面访问，页面大小为256个字。在这个实验中，分配给进程的物理块数分别为6、8、10、12和14。当分配给进程的物理块数比较少时，四种算法的差距明显，且FIFO所产生的缺页中断基本上是OPT的2倍，时钟算法则比较接近于LRU。

请求分页虚拟存储器需要从以下几点考虑页面大小问题：

（1）页表大小。在虚拟空间大小一定的前提下，不难看出页面大小的变化对页表大小的影响。如果页面较小，虚拟空间的页面数就增加，页表也随之扩大。由于每一个作业都必须有自己的页表，因此为了控制页表所占的内存量，页面的尺寸还是较大一点为好。

（2）内存利用率。内存是以块为分配单位的，作业程序一般不可能正好划分为整数倍的页面。于是作业的最后一个页面进入内存时，总会产生内部碎片，平均起来一个作业将造成半块的浪费。为了减少内部碎片，页面的尺寸还是小一点为好。

（3）读写一个页面所需的时间。作业都存放在辅助存储器上，从磁盘读入一个页面的时间包括等待时间（移臂时间＋旋转时间）和传输时间，通常等待时间远大于传输时间。显然，加大页面的尺寸，有利于提高I／O的效率。

（4）最佳页面尺寸。目前采用页式虚拟存储管理的计算机系统中，页面大小大多选择在512 B～4 KB，是从减少内部碎片和页表耗费的存储空间两个角度出发推导出来的。

5.5.4 请求分段虚拟存储管理

请求分段虚拟存储管理也为用户提供比内存实际容量大得多的虚拟内存空间。请求分段虚拟存储系统把作业的所有分段的副本都存放在辅助存储器中，当作业被调度投入运行时，首先把当前需要的一段或几段装入内存，在执行过程中访问到不在内存的段时再把它们动态装入。因此在段表中必须说明哪些段已在内存，存放在什么位置，段长是多少；哪些段不在内存，它们的副本在辅助存储器的位置。还可设置该段是否被修改过，是否能移动，是否可扩充，能否共享等标志。格式见图5-33。

在作业执行中访问某段时，由硬件的地址转换机构查段表，若该段在内存，则按分段式存储管理中给出的办法进行地址转换得到绝对地址。若该段不在内存中，则硬件发出一个缺段中断。操作系统处理这个中断时，查找内存分配表，找出一个足够大的连续区域容纳该分段。如果找不到足够大的连续区域则检查空闲区的总和，若空闲区总和能满足该分段要求，那么进行适当移动后，将该分段装入内存。若空闲区总和不能满足要求，则可调出一个或几个分段到磁盘上，再将该分段装入内存。

在执行过程中，有些表格或数据段随输入数据多少而变化。例如，某个分段在执行期间因表格空间用完而要求扩大分段。这只要在该分段后添置新信息即可，添加后的长度应不超过硬件允许的每段最大长度。对于这种变化的数据段，当要往其中添加新数据时，由于欲访问的地址超出原有的段长，硬件产生一个越界中断。操作系统处理这个中断时，先判别一下该段的“扩充位”标志，如可以扩充，则增加段的长度，必要时还要移动或调出一个分段以腾出内存空间。如该段不允许扩充，那么这个越界中断就表示程序出错。

请求分段虚拟存储器便于实现分段的共享和保护。为了实现分段的共享，除了原有的进程段表外，还要在系统中建立一张段共享表，每个共享分段占一个表项，每个表项包含两部分内容：第一部分有共享段名、段长、内存起址、状态位（如在不在内存位）、外存地址、共享进程个数计数器；第二部分有共享该段的所有进程名、状态、段号、存取控制位（通常为只读）。

由于共享段是供多个进程公用的，对它的内存分配及回收要如下进行：当出现第一个要使用某个共享段的进程时，由系统为此共享段分配物理内存区，再将共享段调入该区。同时将共享段内存区始址填入共享段表中对应项的内存始址处，共享进程个数计数器加1，修改状态位（“在内存位”为1），填写使用该共享段进程的有关信息（进程名、使用共享段的段号、存取控制等）。而进程段表中共享段的表项指向内存共享段表地址。此后，又有进程使用已调入内存的同名共享段时，仅需直接填写共享段表和进程段表，以及把共享进程个数计数器加1就行了。当进程不再使用共享段时，应释放该共享段，除了在共享段表中删去进程占用项外，还要把共享进程个数计数器减1。当共享进程个数计数器为0时，说明已没有进程使用此共享段了，系统需要回收该共享段的物理内存，并把占用表项也取消。这样做有许多优点：不同进程可以用不同段号使用同一个共享段；由于进程段表中共享段的表项指向内存共享段表地址，所以每当共享段被移动、调出或再装入时，只要修改共享段表的项目，而无需修改共享段的每个进程的段表。

分段存储器系统中，由于每个分段在逻辑上是独立的，实现存储保护也很方便。一是越界检查。在段表寄存器中存放了段长信息，在进程段表中存放了每个段的段长。在存储访问时，首先把指令逻辑地址中的段号与段表长度进行比较，如果段号等于或大于段表长度，将发出地址越界中断；其次还需检查段内地址是否等于或大于段长，若是则产生地址越界中断，从而确保每个进程只在自己的地址空间内运行。二是存取控制检查。在段表的每个表项中，均设有存取控制字段，用于规定此段的访问方式，通常设置的访问方式有只读、读写、只执行等。

5.5.5 请求段页式虚拟存储管理

段式存储是基于用户程序结构的存储管理技术，有利于模块化程序设计，便于段的扩充、动态链接、共享和保护，但往往会生成段之间的碎片浪费存储空间；页式存储是基于系统存储器结构的存储管理技术，存储利用率高，便于系统管理，但不易实现存储共享、保护和动态扩充。如果把两者优点结合起来，在分页式存储管理的基础上实现分段式存储管理就是段页式存储管理。下面介绍请求段页式虚拟存储管理的基本原理：

（1）虚地址以程序的逻辑结构划分成段，这是段页式存储管理的段式特征。

（2）实地址划分成位置固定、大小相等的页框（物理块），这是段页式存储管理的页式特征。

（3）将每一段的线性地址空间划分成与物理块大小相等的页面，于是形成了段页式存储管理的特征。

（4）逻辑地址形式见表5-3。对于用户来说，段式虚拟地址应该由段号s和段内位移d′组成，操作系统内部再自动把d′解释成两部分：段内页号p和页内位移d，也就是说，d′＝p×块长＋d。

表5-3_逻辑地址形式

（5）数据结构。请求段页式虚拟存储器管理的数据结构更为复杂，包括作业表、段表和页表三级结构。作业表中登记了进入系统中的所有作业及该作业段表的起始地址，段表中至少包含这个段是否在内存，以及该段页表的起始地址，页表中包含了该页是否在内存（中断位）、对应内存块号。

（6）动态地址转换。请求段页式虚拟存储器管理的动态地址转换机构由段表、页表和快表构成。当前运行作业的段表起始地址已被操作系统置入段表控制寄存器，其动态地址转换过程如下：从逻辑地址出发，先以段号s和页号p作为索引去查快表，如果找到，即获得页p的物理块号p′，并与位移d一起拼装得到访问内存的实地址，从而完成了地址转换。若查快表失败，就要通过段表和页表来做地址转换了，用段号s作为索引，找到相应表目，由此得到s段的页表的起始地址s′，再以p作为索引得到s段p页对应的表目，由此得到物理块号p′；这时一方面把s段p页和物理块号p′置换进快表，另一方面用p′和d生成内存的物理地址，完成地址转换，如图5-34所示。

上述过程是假设所需信息都在内存的情况下进行的，但也有可能有很多意外，如查段表时，发现s段不在内存，于是产生“缺段中断”，引起操作系统查找s段在外存的位置，并将该段页表调入内存；如查页表时，发现s段的p页不在内存，于是产生“缺页中断”，引起操作系统查找s段p页在外存的位置，并将该页调入内存，当内存已无空闲页框时，就会导致淘汰页面。图5-34是段页式存储动态地址转换和存储保护示意图。

图5-34 段页式存储动态地址转换和存储