5.2.9　虚拟页式存储管理

前面介绍的几种存储管理方式属于物理存储管理，针对实际物理内存空间。其共同点是作业或进程是一次性装入的，并在装入内存后，一直驻留在内存中直到运行结束，这使得主存的利用率降低；另外，如果作业或进程所需的内存空间大于目前系统实际物理内存空间，该作业或进程不能装入，即内存不足。为解决该问题，出现了虚拟存储管理方式。

从分区管理到页式存储管理，进程内存地址由连续到不连续的变化为实现虚拟存储器管理提供了基础。此外，程序局部性原理否定了程序一次性装入和驻留的必要性。这些使得虚拟存储成为可能。虚拟存储技术将内存与外存结合，用户程序可以部分装入，利用调入、调出等操作，从逻辑上扩充了内存。

虚拟页式存储管理也称为动态页式存储管理，是在普通分页管理的基础上，采用虚拟存储技术发展起来的，是一种具有交换技术的分页存储管理方式。

1.基本思想

当某作业被调度时，先为作业中的部分页面分配内存块，在该作业执行过程中，每当需要访问的页面不在内存中时，则产生缺页中断，请求将该页调至内存。这时，如果内存中有空闲块，那么存储分配程序为这个即将访问的页面分配内存块，将新调入页装入内存，并修改页表中相应表项。如果内存空间已满，而又需要装入新的页面时，则根据某种算法从内存中淘汰某个页面，以便装入新的页面。若换出的页在内存期间被修改过，则要将其写回外存。

2.实现方法

请求分页存储管理主要需要解决以下问题：如何提出页面请求；何时提出页面请求；被请求的页面何时、从何处调入内存；如何判断被请求的页面是否已调入内存；调入的新页放在内存的什么地方；如果内存已满，还有调入新页的请求时，系统又是如何处置等。

（1）页表

与分页存储管理相比，虚拟页式管理中的页表要复杂些。页表的内容包括：页号、内存块号、内存标志位（驻留标志位或中断位，用于表示该页是否在内存）、引用位（访问位，记录该页在一段时间内被访问的次数，为系统进行页面置换提供数据）、修改位（用于记录页面是否被修改。若修改过，则需要将该页在换出主存之前必须先写回外存）、访问权限位（限定页面允许的访问权限）等。

当访问的页面不在内存时，产生缺页异常，操作系统将从外存将该页调入内存。为了对外存进行管理，需要记录下进程各页面在外存中的位置，当请求调入该页时才能正确找到该页，故设置一张页表，叫做外页表，其内容包括：页号和外存地址。每个进程的内存页表对应一张外页表。进程启动运行前系统为其建立外页表，为节省内存空间，外页表通常存放在磁盘中，发生缺页中断时才被调入内存。

（2）缺页中断

当发现所要访问的页不在内存时，则产生缺页中断。操作系统收到此中断信号后，就调用缺页中断处理程序，根据外页表中给出的外存地址，并在内存有空闲块的情况下将该页调入内存，使进程继续运行下去。如果内存没有空闲块，则先需要调用页面置换算法将内存中的某个页面换出到外存，腾出空间调入请求页。若被淘汰的页面在内存中修改过，还需要将其回写到外存，以保留最新版本。

因为内存中存在多个进程，所以当某个进程在执行过程中发生缺页中断时，该进程会阻塞自己，让出CPU，进程调度程序会调度其他进程获得CPU。当需要的页面调入内存后，唤醒该进程，进入就绪队列等待下一次调度。再次执行时，从原断点继续执行。

（3）页面调入与时机

确定什么时候应从外存往内存调入新页，而且是调入哪一页。根据调页时机的不同，动态页式管理可以分为两种，一种是预调入页式管理，另一种是请求页式管理。为了提高对内存使用的灵活性和系统效率，总是希望把内存分配的时机尽量向后推迟。

请求页式管理和预调入页式管理，在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分，其他部分则在执行过程中动态装入。它们的区别在于调入新页的时机和方式。请求页式管理的调入方式是，当需要执行某条指令，而又发现该条指令不在内存时，或当执行某条指令，需要访问其他的数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。

预调入方式是先行调度，在发生缺页异常之前就将需要的页面调入内存。系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和访问的顺序，并按此顺序将它们顺次调入和调出内存。

请求页式管理比预调入页式管理易于实现，用得比较普遍。虚拟页式管理通常指请求页式管理。

（4）页面淘汰算法

页面淘汰算法，即页面置换算法。这里是指全局页面淘汰算法。在多道程序正常运行的过程中，不同进程的页面分散在不同的内存块中。当内存中没有空闲页面，而又有程序和数据需要从外存装入内存运行时，需要根据某种规则从内存中选出一个或多个页面淘汰出去，以便新的程序和数据装入运行。

将内存和外存统一管理的真正目的，是把那些访问概率非常高的页存放在内存中，置换算法应该淘汰那些访问概率最低的页，将它们移出内存。当然，置换算法的选择将直接影响到内存利用率和系统效率。若置换算法选择不当，将可能出现页面被频繁地换进换出，即抖动（thrashing）或颠簸现象。

页面置换算法的性能直接影响系统效率。评价该算法的指标通常包括：访问成功次数、缺页次数、缺页率等。比较常见的置换算法有以下几种：

1）随机淘汰算法。在系统设计人员认为无法确定哪些页被访问的概率较低时，随机选择某个用户的页面并将其换出。

2）轮转法。循环换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已驻留内存很长时间。

3）先进先出算法（First In First Out,FIFO）。FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。FIFO算法认为先调入内存的页不再被访问的概率要比其他页的大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配页面按页面分配时间顺序链接起来，组成FIFO队列，并设置一个置换指针指向FIFO队列的队首页面。

FIFO算法忽略了一种现象的存在，就是在内存中停留时间最长的页往往也是经常被访问的页。将这些页面淘汰，很可能刚置换出去，又请求调用该页，致使缺页中断太频繁，严重降低内存的利用率。FIFO算法的另一个缺点是它有一种异常现象。一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。但是，使用FIFO算法时，在未给进程或作业分配它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象，或称为Belady异常。

4）最近最久未使用页面置换算法（Least Recently Used,LRU）。该算法的基本思想是：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰，即淘汰没有使用的时间最长的页。

该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。

最近最久未使用算法实现起来需要花费巨大的系统开销，因此，实际系统中往往使用LRU的近似算法，比较常用的有：最不经常使用页面淘汰算法（Least Frequently Used,LFU）、最近没有使用页面淘汰算法（Not Used Recently,NUR）、理想型淘汰算法（Optimal Replacement,OPT）。

5）最不经常使用页面淘汰算法（LFU）。该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。

6）最近没有使用页面淘汰算法（NUR）。该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1；否则，访问位置0。系统周期性地对所有访问位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。

7）理想型淘汰算法（OPT），也称为最佳置换算法，或最优置换算法。该算法淘汰在访问串中将来再也不出现的，或者在离当前最远的位置上出现的页。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。

3.页面分配

页面分配就是根据某种策略，将物理内存块分配给诸多进程。页面分配策略一般分为静态分配和动态分配两种。

静态分配指创建进程时，根据进程的类型和系统规则分配固定数目的内存块，并在进程的生命周期中保持内存块数目不变。常用的规则有：

1）平均分配：将内存中所有可分配的内存块平均分配给系统内的进程。

2）按进程长度分配：根据进程各自长度的比例进行内存块的分配。

3）按进程优先级分配：为高优先级的进程分配较多的内存块。

4）按进程长度和优先级分配：首先按进程长度分配部分内存块，然后将剩余的内存块根据进程的优先级进行分配。

静态分配没有考虑进程在实际运行过程中对内存块需求的动态性和差异性。

动态分配指创建进程时，先分配一定数目的内存块使之运行。在进程运行过程中发生缺页时，系统从空闲内存块队列中取出一个空闲块分配给新调入的页。动态分配策略常与全局页面置换算法配合使用，为系统进程分配一定数目的内存块，操作系统保留若干空闲内存块。当系统拥有的空闲内存块分配完后，通过页面置换算法淘汰内存中某个进程的某个页面。

4.地址转换

虚拟页式存储管理中逻辑地址又称为虚拟地址（虚地址），包括虚拟页号和页内地址（偏移量）。地址转换需要页表、缺页中断、页面调入调出、快表等软、硬件支持。转换过程如下：

1）当进程运行时，操作系统通过该进程的PCB得到对应页表的地址和长度，并送入页表寄存器中。当访问某个虚地址时，主存管理部件（Memory Managing Unit,MMU）接收CPU传送来的逻辑地址并自动将其分成页号和页内地址两部分。

2）查找快表，找到页号和对应的内存块号，则将块号与页内地址拼接成物理地址，执行5）。

3）若在快表中没有找到页号，则通过页表寄存器查找页表，查找页号，如果找到，则将块号与页内地址拼接成物理地址，执行5）。

4）若在页表中没有找到页号，则MMU发出缺页中断，转由操作系统进行相应处理。

5）检查该页的访问权限，如果当前操作符合规定权限，进程就可以访问物理地址；否则，访问失败，系统产生一个“非法操作”的程序性中断事件。

5.缺页中断率

缺页中断率简称为缺页率。假定某进程执行过程中访问页面的总次数为N，产生了x次缺页中断，则缺页率f=x/N。由此看出，缺页率与缺页中断的次数有关。影响缺页率的因素有：

1）分配给作业的内存块数。分配给作业的内存块数多，则同时装入内存的页面数就多，缺页率就低。

2）页面的大小。页面长度越大，装入的程序内容就越多，就降低了缺页中断的次数；反之，缺页率就高。

3）程序代码实现方法。程序代码实现的方法不同，对缺页中断的次数有很大影响。缺页率与程序的局部化程度密切相关。好的程序代码实现能使程序段经常集中在几个页面上进行访问，以减少缺页率。

6.请求页式管理的优缺点

请求页式管理的优点如下：

1）由于请求页式管理不要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。

2）提供了内存和外存统一管理的虚存实现方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用率，又有利于组织多道程序执行。

请求页式管理的缺点如下：

1）要求有相应的硬件支持。例如地址变换机构、缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持，这就增加了机器成本。

2）增加了系统开销，例如缺页中断处理等。

3）请求调页的算法如选择不当，有可能产生抖动现象。

4）虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用。如果页面较大，则这部分的损失仍然较大。