学习目标 理解并掌握请求分页存储管理系统中的硬件支持 理解请求分页存储管理系统中的内存分配策略和分配算法 掌握主要页面置换算法

§4.7 请求分页存储管理方式 请求分页存储管理的基本思想 请求分页存储管理方式是实现虚拟存储器的一种常用技术； 基本思想：在进程开始运行之前，仅装入当前要执行的部分页面即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的页面；当内存空间已满，而又需要装入新的页面时，者根据置换功能适当调出某个页面，以便腾出空间而装入新的页面。 为了实现页式虚存，系统需要解决下面三个问题： 1）系统如何感知进程当前所需页面不在主存（页表机制）； 2）当发现缺页时，如何把所缺页面调入主存（缺页中断机构）； 3）在置换页面时，根据什么策略选择欲淘汰的页面（置换算法）。

4.7.1 请求分页的硬件支持 1、页表机制 页号 状态位 物理块号 外存地址 访问位 修改位 状态位（中断位）：标识该页是否在内存（0或1）； 访问位：标识该页面的近来的访问次数或时间（换出）； 修改位：标识此页是否在内存中被修改过； 外存地址：记录该页面在外存上的地址，即(外存而非内存的)物理块号。

2.缺页中断机构 程序在执行时，首先检查页表，当状态位指示该页不在主存时，则引起一个缺页中断发生，其中断执行过程与一般中断相同： 保护现场（CPU环境）； 中断处理（中断处理程序装入页面）； 恢复现场，返回断点继续执行。

缺页中断与一般中断的不同点： 一般中断是一条指令完成后检查是否有中断 缺页中断是在指令执行期间产生和处理中断， 一条指令执行时可能产生多个缺页中断(如指令可能访问多个内存地址，这些地址在不同的页中)。 相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。缺页中断的处理过程是由硬件和软件共同实现的。

缺页中断引发的连续中断

4.7.2　内存分配策略和分配算法 　　1．最小物理块数的确定 　　这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。

　　2．物理块的分配策略 　　1) 固定分配局部置换(Fixed Allocation，Local Replacement) 　　这是指基于进程的类型(交互型或批处理型等)，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变。采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n个页面中选出一个页换出，然后再调入一页，以保证分配给该进程的内存空间不变。实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。若太少，会频繁地出现缺页中断，降低了系统的吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而可能造成CPU空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。

　　2) 可变分配全局置换(Variable Allocation，Global Replacement) 　　这可能是最易于实现的一种物理块分配和置换策略，已用于若干个OS中。在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。这样，凡产生缺页(中断)的进程，都将获得新的物理块。仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。

　　3) 可变分配局部置换(Variable Allocation，Local Replacement) 　　这同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。

　　3．物理块分配算法 　　1) 平均分配算法 　　这是将系统中所有可供分配的物理块平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。

　　2) 按比例分配算法 　　这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：   　　又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有： b应该取整，它必须大于最小物理块数。

　3) 考虑优先权的分配算法 　　在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。

4.7.3　调页策略 　1．调入页面的时机 　1) 预调页策略 　　如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但遗憾的是，目前预调页的成功率仅约50%。故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

　　2) 请求调页策略 　　当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。由请求调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启动频率。

§4.8 页面置换算法 4.8.1 最佳置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。最佳理论上有指导意义，实际上无法实现（需要能看见未来！）。 假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

算法名称、思想及实现是关键！ 2.先进先出(FIFO)页面置换算法

为了说明FIFO页面置换算法相关的可能问题，考虑一下引用串：1，2，3，4，1，2，5，1，2，3，4，5。 注意到对4个可用内存块的缺页次数（10）比3个内存块的缺页次数（9）还要大。这种令人难以相信的结果称为Belady异常现象，即缺页次数随内存块增加而增加。

3.最近最久未使用(LRU)置换算法 最近最久未使用置换算是用过去的引用串的情况来预测将要到来的引用串的情况（以“最近的过去”作为“不久将来”的近似），选择过去的最近一段时间内最久没有使用的页面淘汰掉。它的实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰 。

LRU算法实现时需要为每个页面设置一个时间项，用来记录该页面上次被访问的时间，每次将时间数值最小的页面淘汰掉。 1) 寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 … R2R1R0

图 4-28 某进程具有8个页面时的LRU访问情况

2) 栈： 栈顶始终存放最新被访问的页面，而栈底则存放最近最久 未访问的页面 图 4-29 用栈保存当前使用页面时栈的变化情况

LRU近似算法 要完全实现LRU算法是一件十分困难的事情。因为要找出最近最久未被使用的页面的话，就必须对每一个页面都设置有关的访问记录项，而且每一次访问都必须更新这些记录。这显然要花费巨大的系统开销（包括硬件开销和时间开销）。因此，在实际系统中往往使用LRU的近似算法，包括NRU（最近未使用）算法和LFU（最少使用）算法。

NRU算法——Clock置换算法 NRU（Not Recently Used）：最近未使用页面淘汰算法

又称为二次机会算法、NRU最近未使用算法 4.8.3 Clock置换算法 又称为二次机会算法、NRU最近未使用算法 1. 简单的Clock置换算法 实现：需要构建循环队列，引入一个查找指针 图 4-31 简单Clock置换算法的流程和示例

2. 改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。

其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

4.7.4 其它置换算法 最少使用(LFU： Least Frequently Used)置换算法： 该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。 

在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。 原因： 页面淘汰算法不合理 分配给进程的物理页面数太少

重点概念和内容提示 地址映射、虚拟地址空间、绝对地址空间、静态重定位和动态重定位、交换、虚拟存储器、缺页中断、页表和段表 可变分区的放置算法 分页存储管理的原理和地址变换 分段存储管理的原理和地址映射 请求分页的原理和页面置换算法