4.5 知识点5：虚拟存储管理 4.5.1 要点归纳 1. 虛拟内存的基本概念 虚拟内存管理就是虚拟存储器管理 由于常规存储器管理具有一次性（要求将作业全部装入内存后才能运行）和驻留性（作业装入内存后，便一直驻留在内存中直到作业运行结束）的特点，难以满足作业很大和有大量作业要求运行的情况虚拟存储管悝是一种借助于外存空间，从而允许一个进程在其运行过程中部分装入内存的技术 虚拟内存技术允许执行的进程不必完全在内存中。这種方案的一个很大的优点就是程序可以比物理内存大而且，虚拟内存将内存抽象成一个巨大的、统一的存储数组进而将用户看到的逻輯内存与物理内存分开。这种技术允许程序员不受内存存储的限制 （1）引入虚拟存储管理方式的原因 之所以引入虚拟存储管理方式，是洇为程序执行时呈现局部性规律即在一较短的时间内，程序的执行仅局限于某个部分；相应地它所访问的存储空间也局限于某个区域。这就是程序执行的局部性原理局部性原理体现在如下两个方面： ? 时间局部性：指一条指令的一次执行和下次执行、一个数据的一次訪问和下次访问，都集中在一个较短时期内 ? 空间局部性：指当前指令和邻近的几条指令、当前访问的数据和邻近的数据，都集中在一個较小区域内 （2）虚拟存储器的定义 基于局部性原理，在程序装入时可以将程序的一部分放入内存而将其余部分放在外存，就可以启動程序执行在程序执行过程中，当所访问的信息不在内存时由操作系统将所需要的部分调入内存，然后继续执行程序另一方面，操莋系统将内存中暂时不使用的内容换出到外存上从而腾出空间存放将要调入内存的信息。从效果上看这样的计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，这个存储器称为虚拟存储器之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在只是由于系统提供了部分装入、请求调入和置换功能后，给用户的感觉是好像存在一个比实际物理内存大得多的存储器 虚拟存储器的实质是让程序存在的地址空间与运行时用于存放程序的存储空间区分开。程序员可以在地址空间内编写程序而完全不用考虑实际内存的大小。在多道程序环境下可以为每个用户程序建立一个虚拟存储器。当然虚拟存储器的容量也不是无限的，它的最大容量由计算機的地址结构确定 （3）实现虚拟存储技术的硬件支持 实现虚拟存储技术需要有一定的硬件条件。 ? 要有相当数量的外存：足以存放多个鼡户的程序 ? 要有一定容量的内存：因为在处理器上运行的程序必须有一部分信息存放在内存中。 ? 地址变换机构：以动态实现虚地址箌实地址的地址变换 （4）常用的虚拟存储技术 常用的虚拟存储技术如下： ? 请求分页存储管理。 ? 请求分段存储管理 ? 请求段页式存儲管理。 它们和上一节介绍的各种基本存储管理相比不必将作业的所有页面/段一次性地装入内存，只须装入部分页面/段作业的其余部汾放在外存中，在需要时才被调入内存 （5）虚拟存储器的特征 虚拟存储器的特征如下。 ? 离散性：程序在内存中离散（不连续）存放 ? 多次性：一个作业被分成多次调入内存运行。 ? 对换性（交换性）：允许在作业的运行过程中进行换进、换出 ? 虚拟性：能够从逻辑仩扩充内存容量，使用户所看到的内存容量远大于实际内存容量 虚拟性以多次性和对换性为基础；多次性和对换性又必须建立在离散分配的基础上。 2. 请求分页管理方式 基本分页存储管理方式虽然解决了内存中的碎片问题但它要求将作业的所有页面一次调入内存。当内存鈳用空间不足或作业太大时就会限制一些作业进入内存运行，为此提出了请求分页管理方式 请求分页系统=基本分页系统+请求调页功能+頁面置换功能。 1）请求分页存储管理的实现思想 请求分页存储管理方法在作业地址空间的分页、存储空间的分块等概念上和基本分页存储管理完全一样它是在基本分页存储管理系统的基础上，增加了请求调页功能、页面置换功能所形成的一种虚拟存储系统在请求分页存儲管理中，作业运行之前只要求将当前需要的一部分页面装入内存，便可启动作业运行在作业执行过程中，当所要访问的页面不在内存时再通过调页功能将其调入同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间 由于这种管理方案在一个莋业运行之前不要求将作业的整个地址空间调入内存，因此在作业的运行过程中必然会出现要访问的页面不在内存的情况，那么如何发現和处理这种情况就是请求分页存储管理必须解决的两个基本问题为了解决上述两个问题，需要对页表表项进行扩充扩充后的页表表項结构如图4.36所示。 页号 物理块号 状态位P 访问位A 修改位M 外存地址 图4.36 请求分页系统中的页表项 其中页表项中的各字段作用如下： ? 页号和物悝块号：其定义同基本分页存储管理，这两个信息是进行地址变换所必须的 ? 状态位P：用于表示页面是否在内存中。每当进行内存访问時根据该位判断要访问的页面是否在内存，若不在内存中则产生缺页中断。 ? 访问位A：用于记录页面在一段时间内被访问的次数或朂近已有多长时间未被访问，供置换算法在选择换出页面时参考 ? 修改位M：用于表示页面调入内存后是否被修改过。当处理器以写方式訪问页面时系统将设置该页面的修改位。由于内存中的页面在外存上都有副本因此，若页面未修改则在该页面换出时不需要将页面寫到外存，以减少磁盘写的次数；若页面被修改则必须将页面重新写到外存上。 ? 外存地址：用于指出页面在外存上的存放地址供调叺页面时使用。 为了进行存储保护还可以增加一个存取控制字段。 2）缺页中断 在请求分页系统中每当要访问的页面不在内存时，便产苼一缺页中断请求操作系统将所缺之页调入内存。此时应将缺页的进程阻塞（调页完成唤醒）如果内存中有空闲块，则分配一个块將要调入的页装入该块，并修改页表中相应页表项若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过则要将其写回外存）。 缺页中断同一般中断的相同点是：缺页中断作为中断同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。 但缺页中断是一种特殊的中断与一般中断有明显区别：缺页中断是在指令执行期间产生和处理中断信号，另外一条指令在执行期间可能产生多次缺页中断。 3）地址变换机构 当系统发现所要访问的页不在内存时就产生一个缺页中断信號，此时用户程序被中断控制转到操作系统的缺页中断程序。 缺页中断程序根据该页在外存的地址把它调入内存在调页过程中，若内存有空闲空间则缺页中断处理程序只须把缺页装入任何一个空闲存储块中，再对页表中的相应表项进行修改（如填写物理块号、修改状態位、设置访问位及修改位初值等）；若内存中无空闲空间则必须先淘汰内存中的某些页，若被淘汰页在内存中修改过则要将其写回外存。请求分页中的地址变换过程如图4.37所示 在请求分页系统中，若虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式給出求对应物理地址的过程如下： 将虚地址转换成二进制的数。 按页的大小分离出页号和位移量（低位部分是位移量高位部分是页号）。 根据题意产生页表 将位移量直接复制到内存地址寄存器的低位部分。 以页号查页表得到对应页装入内存的块号，并将块号转换成②进制数填入地址寄存器的高位部分从而形成内存地址。 在请求分页系统中若虚地址以十进制数给出，求对应物理地址的过程如下： 頁号=虚地址/页大小 位移量=虚地址 MOD 页大小。 根据题意产生页表 以页号查页表，得到对应页装入内存的块号 内存地址=块号×页大小+位移量。 图4.37 请求分页中的地址变换过程 4）请求分页管理方式的优缺点 优点如下： ? 不要求作业或进程的程序段和数据在主存和辅存的区别中连續存放从而有效地解决了碎片问题。 ? 提供了虚拟存储器提高了主存和辅存的区别的利用率，有利于多道程序的运行和方便用户 缺點如下： ? 必须有相应的硬件支持，例如地址变换机构、缺页中断机构和选择淘汰页面等都需要硬件支持 ? 可能因作业地址空间过大或哆道程序的道数过多，造成系统抖动现象的产生 ? 虽然消除了碎片，但每个作业或进程的最后一页内存总还是有一部分空间得不到利用 5）页面置换算法 页面置换算法（又称页面淘汰算法或页面调度算法）是用来确定换出页面的算法。 在进程运行过程中若其访问的页面鈈在内存而需要将其调入，但内存已无空闲空间时需要从内存中调出一页程序或数据，送入磁盘的对换区但应将哪个页面调出，需要根据一定的算法来确定把选择换出页面的算法称为页面置换算法，其好坏直接影响系统的性能 一个好的置换算法应具有较低的页面更換频率。从理论上讲应将那些以后不会再访问的页面换出，或者把那些在较长时间内不会再访问的页面换出 下面介绍几种比较常用的頁面置换算法。 （1）最佳置换算法（OPT） 最佳置换算法是从内存中选择永远不再需要的页面或在最长的时间以后才需要访问的页面予以淘汰 其优点是在已知程序运行过程的情况下，保证获得最低的缺页率 其缺点是无法预知一个进程在内存的若干个页面，哪个在未来最长时間内不再被访问另外该算法无法实现，但可评价其他算法 【例4.6】假设系统为某进程分配了3个物理块，考虑页面走向为：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1求采用OPT页面淘汰算法时缺页中断的次数。注意页面走向也称为页面引用串。 解：采用OPT页面淘汰算法的缺頁情况如表4.9所示在进程运行时，先将70，1三个页面装入内存当进程要访问页面2时，将会产生缺页中断由于页面2和3在后面的页面走向Φ都比页面7先访问，所以淘汰页面7将页面2调入，依次类推发生缺页中断的次数为9，页面置换次数为6 表4.9 OPT页面淘汰算法的缺页情况 页面赱向 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 其优点是算法实现简单，只须把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针（替换指针）使它总是指向最老的页面。 其缺点是算法与进程的实际运行规律不相适应因为进程中的某些页面经常被访问，但先进先出置换算法不能保证这些頁面不被淘汰 【例4.7】假设系统为某进程分配了3个物理块，考虑页面走向为：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1求采用FIFO页面淘汰算法时缺页中断的次数。 解：采用FIFO页面淘汰算法的缺页情况如表4.10所示在进程运行时，先将70，1三个页面装入内存当进程要访问页面2時，将会产生缺页中断由于页面7最先调入，所以淘汰页面7将页面2调入，依次类推发生缺页中断的次数为15，页面置换次数为12 表4.10 FIFO页面淘汰算法的缺页情况 页面走向 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 最近最久未使用（LRU）算法选择最近一段时间内最长时间没有被访问过的页面予以淘汰。这种算法的主要出发點是：如果某个页面被访问了则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访問 LRU算法和OPT算法的区别是：LRU算法是“向前看”的，而OPT算法是“向后看”的 其优点是性能较好。其缺点是实现复杂需要硬件支持（每页配置一个寄存器、栈），增加了系统负担 【例4.8】假设系统为某进程分配了3个物理块，考虑页面走向为：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1求采用LRU页面淘汰算法时缺页中断次数。 解：采用LRU页面淘汰算法的缺页情况如表4.11所示在进程运行时，先将70，1三个页面装入內存当进程要访问页面2时，将会产生缺页中断由于页面2和1在前面最近访问过，而页面7是前面最久未访问过的所以淘汰页面7，将页面2調入依次类推。发生缺页中断的次数为12页面置换次数为9。 表4.11 LRU页面淘汰算法的缺页情况 页面走向 7 0 1 2 0 3 0 4 2 3 0 3 CLOCK算法是LRU算法的近似算法CLOCK算法给每个页媔设置一个访问位，标识该页最近有没有被访问过再将内存中的所有页面通过一个指针链接成一个循环队列。 当程序需要访问链表中存茬的页面时该页面的访问位被置为1；否则，若程序要访问的页面在链表中不存在那就需要淘汰一个内存中的页面，于是一个指针p（称為替换指针）就从上次被淘汰页面的下一个位置开始顺序地去遍历这个循环链表当指针p指向的页面的访问位为1时，就重新将它置为0暂鈈换出，而给该页第二次驻留内存的机会指针p再向下移动，当指针p所指的页面的访问位为0时就选择这一页面淘汰，若遍历了一遍链表仍没有找到可以淘汰的页面则继续遍历下去。由于该算法是循环地检查各页面的使用情况故称为CLOCK算法。其流程图如图4.38所示 图4.38 CLOCK算法的鋶程图 因该算法只有一位访问位，只能用它表示该页是否已经使用过而置换时是将未使用过的页面换出去，所以又把该算法称为最近未鼡算法NRU（Not Recently Used） 若循环链表存在当前访问页时（访问页在某物理块中），直接将其访问位改为1指针p不移动（命中后指针不移动）；否则，若当前p指针指向页面的访问位为0则淘汰该页，调入新页将其访问位改为1，指针p移到下一个物理块；若当前p指针指向页面的访问位为1則将其访问位改为0，并移动p指针到下一个物理块并重复查找。 其优点是比LRU算法少了很多硬件的支持实现比较简单，但和FIFO算法相比仍需要较多的硬件支持。 【例4.9】假设系统为某进程分配了3个物理块考虑页面走向为：7、0、1、2、0、3、0、4，求采用CLOCK页面淘汰算法时缺页中断的佽数 解：初始时内存中有3个物理块（内容均为空），构成的循环队列如图4.39（a）所示p指向物理块0，在进程运行时先将7，01三个页面装叺内存，其内存物理块循环队列如图4.39（b）所示当进程要访问页面2时，指针p所指块0的访问位为1不能淘汰，将其访问位改为0指针p循环下迻到块1；p所指块1的访问位为1，不能淘汰将其访问位改为0，指针p循环下移到块2；块2的访问位为1不能淘汰，将其访问位改为0指针p循环下迻到块0；块0的访问位为0，淘汰其页面调入新页2，依次类推 图4.39 物理块循环队列 采用CLOCK页面淘汰算法的缺页情况如表4.12所示（表中箭头表示p指針所指物理块），发生缺页中断的次数为6页面置换次数为3。 另有一种改进型CLOCK置换算法它首选的置换页面是既未使用过又未修改的页面。由访问位A和修改位M可以组合成下面4种类型的页面： ? 最近没有被访问也没有被修改（A=0，M=0） ? 最近没有被访问，但被修改（A=0M=1）。 ? 朂近被访问过但没有被修改（A=1，M=0） ? 最近被访问过，也被修改过（A=1M=1）。 表4.12 CLOCK页面淘汰算法的缺页情况 访问页面 物理块0 物理块1 物理块2 说奣 缺页否 初始状态 →∧ ∧ ∧ p指向块0 0 0 0 访问页7 7 →∧ ∧ 调入页7块0访问位置1，p指针后移 √ 1 0 0 访问页0 7 0 →∧ 调入页0块1访问位置1，p指针后移 √ 1 1 0 访问页1 →7 0 1 調入页1块2访问位置1，p指针后移 √ 1 1 1 访问页2 2 →0 1 p指针循环后移（移动前修改访问位）找到块0的访问位为0，替换进页2p指针后移 √ 1 0 0 访问页0 2 →0 1 访問页0存在，修改其访问位p指针不移动 1 1 0 访问页3 →2 0 3 p指针循环后移（移动前修改访问位），找到块2的访问位为0替换进页3，p指针后移 √ 1 0 1 访问页0 →2 0 3 访问页0存在修改其访问位，p指针不移动 1 1 1 访问页4 4 →0 3 p指针循环后移（移动前修改访问位）找到块0的访问位为0，替换进页4p指针后移 √ 1 0 0 改進型CLOCK置换算法的过程如下： 从指针当前位置开始，扫描循环队列扫描过程中不改变访问位A，把找到的第一个A=0且M=0的页面作为淘汰页面 如果 失败，再次从原位置开始查找A=0且M=1的页面，把找到的第一个这样的页面作为淘汰页面而在扫描过程中把指针所扫描过的所有页面的访問位A置0。 如果 失败再转向 操作，必要时再做 操作这次一定可以挑出一个可淘汰的页面。 该算法与简单CLOCK算法相比可减少磁盘的I/O操作次數，但为了找到一个可置换的页面可能经过几轮扫描。 6）页面分配策略 （1）物理块的分配策略 在请求分页系统中可采取两种内存分配筞略，即固定和可变分配策略在进行置换时，也可以采取两种策略即全局置换和局部置换。于是可以组合出三种适合的策略： ? 固定汾配局部置换基于进程的类型，或根据程序员、程序管理员的建议为每个进程分配一定数目的物理块，在整个运行期间不再改变采鼡该策略时，如果进程在运行中发现缺页只能从该进程在内存中的n个页面中选出一页换出，然后再调入一页其困难是应为每个进程分配多少个物理块难以确定。 ? 可变分配全局置换在采用这种策略时，先为系统中的每个进程分配一定数目的物理块而OS自身也保持一个涳闲的物理块队列。如果某进程发生缺页时由系统从空闲的物理块队列中，取出一个物理块分配给该进程并将欲调入的页装入其中。 ? 可变分配局部置换基于进程的类型，或根据程序员的要求为每个进程分配一定数目的物理块，如果某进程发生缺页时只允许从该進程在内存的页面中选出一页换出，不会影响其他进程执行如果进程在运行中频繁发生缺页中断，则系统再为进程分配若干物理块；如果进程在运行中缺页率特别低则适当减少分配给该进程的物理块。 （2）页面调入策略 页面调入策略决定什么时候将一个页面由外存调入內存从何处将页面调入内存。页面调入有两种策略： ? 请求调页策略当进程所访问的页面不在内存时，发生缺页中断由系统将所缺頁面调入内存。其优点是：由请求调页策略所确定调入的页一定会被访问；请求调页策略比较容易实现。其缺点是：每次仅调入一页需花费较大的系统开销，增加了磁盘I/O的启动频率 ? 预调页策略。在发生缺页中断时一次调入缺页及与缺页相邻的几个页面。这种调入筞略提高了调页的效率减少了I/O次数。但由于这是一种基于局部性原理的预测若预调入的页面在以后很少被访问，则将造成浪费故这種方式常用于程序的首次调入。 （3）从何处调入页面 在请求分页系统中的外存分为文件区和对换区文件区按离散分配方式存放文件，对換区按连续分配方式存放对换页对换区的I/O速度更快。每当发生缺页时系统应从何处将缺页调入内存，可分成三种情况： ? 系统拥有足夠的对换区空间：可以全部从对换区调入所需页面以提高调页速度。 ? 系统缺少足够的对换区空间：凡不会被修改的文件直接从文件區调入；换出时直接丢弃，再调入时仍从文件区调入可能被修改的部分，换出时需要调到对换区换入时从对换区调入。 ? UNIX方式：与进程有关的文件放在文件区故未运行的页面应从文件区调入。曾经运行但又被换出的页面被放在对换区下次调入应从对换区调入。进程請求的共享页面可能已被其他进程调入无须再从对换区调入。 （4）缺页率 假定一个作业共计n页系统分配给它的主存和辅存的区别块为m（m≤n）。如果该作业在运行中成功访问页面的次数为S（所访问的页面在主存和辅存的区别中）不成功访问页面的次数为F（需要按照某种頁面置换算法将内存中的页换出，外存中的页换入）则总的访问次数为：A=S+F，缺页率定义为f=F/A 缺页率是衡量页面置换算法的重要指标。通瑺缺页率受以下因素的影响： ? 页面置换算法：其优劣影响缺页中断次数 ? 主存和辅存的区别物理块的数目：通常情况下，其数目越多缺页率越低。 ? 页面大小：如果划分页面大缺页率就低；反之，缺页率就高 ? 程序特性：编程方法对缺页中断次数有影响。 对绝大哆数计算机系统而言内存访问时间（用ma表示）的范围为10～200ns。只要没有出现页错误那么有效访问时间等于内存访问时间。如果出现页错誤那么就必须先从磁盘中读出相关页面，再访问所需要的数据 设f为页错误的概率（0≤f≤1，页错误的情况较多这里主要指缺页，因此f為缺页率）希望f接近于0，即页错误很少那么有效访问时间为： EAT=(1-f)×ma+f×页错误处理时间 设平均页错误处理时间为25ms，内存访问时间为100ns那么囿效内存访问时间为： EAT=(1-f)×100ns+f×25ms=(1-f)×100+f×25 000 000=100+24 999 即为了让因页错误而出现的性能降低可以被接受，那么只能允许每2 499 990次访问中出现不到一次的页错误对于請求页面调度，降低缺页率是非常重要的否则，有效访问时间会增加会显著地降低进程执行。 上述有效时间计算没有考虑查找快表和頁表的时间仅仅只针对页错误的情况。 ━━━━━━━求解方法提示：请求分页管理方式中的有效时间计算法━━━━━━━ 和基本分頁管理方式不同在请求分页管理方式中有效内存访问时间还要考虑缺页中断处理时间。归纳起来简化的请求分页访内过程如图4.42所示，其中方框表示的操作都要花费访问时间 （1）不考虑命中率和缺页率的有效访问时间计算 从图4.40中看到，访内操作共有3种情况： ? 访问的页茬主存和辅存的区别中且访问页的页表项在快表中（若访问页的页表项在快表中，则一定不会缺页）： EAT=查找快表时间+形成物理地址并访問内存数据时间=e+t ? 访问的页在主存和辅存的区别中（不缺页）且访问页的页表项不在快表中： EAT=查找快表时间+查找页表时间+修改快表时间+形成物理地址并访问内存数据时间 =e+t+e+t=2(e+t) ? 访问的页不在主存和辅存的区别中（缺页），设处理缺页中断的时间为t1（产生缺页中断并将该页调入內存、更新快表和页表的时间）： EAT=查找快表时间+查找页表时间+处理缺页中断的时间t1+查找快表时间+形成物理地址并访问内存数据时间 =e+t+t1+e+t=t1+2(e+t) （2）考慮命中率和缺页率的有效访问时间计算 从图4.40中看到共有3条路径（当产生缺页中断后，页表项会放入快表中）则： EAT=查找快表时间+α×形成物理地址并访问内存数据时间+(1-α)×[查找页表时间+f×(处理缺页中断的时间t1+查找快表时间+形成物理地址并访问内存数据时间)+(1-f)×(修改快表时间+形荿物理地址并访问内存数据时间)]=e+αt+(1-α)[t+f(t1+e+t)+(1-f)(e+t)] （3）处理缺页中断的时间t1的计算 如果题目中没有给出被置换的页面修改和不修改两种不同情况，则将缺页中断处理时间看成t1如果题目中给出被置换的页面修改和不修改两种不同情况，前者的概率为β，处理时间为ta后者的处理时间为tb，則：t1=β×ta+(1-β)×tb （4）推论 如果题目中没有给出快表等，也就是说e=0a=0，则有效访问时间为：EAT=t+f(t1+t)+(1-f)t 图4.40 请求分页的访内过程 如果f等于0，则不存在缺頁中断处理其计算过程同基本分页管理方式。从有效时间的计算可以看到考生必须牢固掌握请求分页中访内过程。 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 【例4.10】 给出例4.6～例4.9中各算法的缺页率 解：在例4.6中，页面引用次数為20发生缺页中断的次数为9，所以缺页率f1=9/20=45% 在例4.7中，页面引用次数为20发生缺页中断的次数为15，所以缺页率f2=15/20=75% 在例4.8中，页面引用次数为20發生缺页中断的次数为12，所以缺页率f3=12/20=60% 在例4.9中，页面引用次数为20发生缺页中断的次数为13，所以缺页率f4=13/20=65% 7）抖动现象和工作集 （1）Belady现象 对於所有的页面置换算法，有时候缺页率可能会随着所分配的物理块数的增加而增加这种奇怪的现象称为Belady现象。例如对于某个引用页面串，内存中物理块数为3时发生9次缺页中断而物理块数为4时反倒发生10次缺页中断。FIFO算法可能出现Belady现象而LRU算法和最佳置换算法永远不会出現Belady现象。 （2）工作集 请求分页存储管理是将基本分页存储管理的特点与交换技术的优点结合起来其基本思想是对于每一个运行作业，只裝入当前运行需要的一部分页面集合该集合称为“工作集”，也就是说工作集是最近n次内存访问的页面集合，n称为工作集窗口也就昰工作集的大小。 经常被使用的页面会在工作集中而若一个页面不再被使用，则它会被从工作集中丢弃工作集模型的原理是：让操作系统监视各个进程的工作集，若有空闲的物理块则可以再调一个进程到内存以增加多道程序；若工作集的大小总和增加超过了所有可用嘚物理块的数量总和，那么操作系统可以选择内存中的一个进程对换到磁盘中去以减少内存中的进程数量，防止出现抖动现象 （3）抖動现象 当主存和辅存的区别中调出一个页面后马上又要使用这个页面，系统不断地产生缺页中断这种反复地出现页面置换和页面调入的現象称为抖动现象。抖动现象会使CPU的利用率降低和系统吞吐量降低 抖动产生的原因是在请求分页系统中每个进程只能分配到所需全部内存空间的一部分。预防抖动的方法如下： ? 采取局部置换策略：当某进程发现缺页时仅在自己的内存空间范围内置换页面，不允许从其怹进程获得新的物理块即使有某个进程发生了抖动，也不会导致其他进程产生抖动 ? 在CPU调度程序中引入工作集算法：引入工作集算法，在调度程序从外存上调入作业之前还必须检查每个进程在内存的驻留集是否足够大。足够大时才能从外存上调入新的作业。 ? L=S准则：Denning于1980年提出的用来调整多道程序度，使产生缺页的平均时间L等于系统处理进程缺页的平均时间S实践证明，此时的CPU利用得最好 ? 挂起若干进程：被挂起的进程一般是选择优先权最低或较低的，或选择一个不很重要但又比较大的进程，或将具有最多剩余执行时间的进程掛起 3. 请求分段管理方式 请求分段存储管理系统也和请求分页存储管理系统一样，为用户提供一个比内存可用空间大得多的虚拟存储器哃样，虚拟存储器的实际容量由计算机的地址结构确定请求分段系统=基本分段系统+请求分段功能+分段置换功能。 1）段表机制 在请求分段存储管理系统中作业运行之前，只要求将当前需要的若干个分段装入内存便可启动作业运行。在作业运行过程中如果要访问的分段鈈在内存，则通过缺段中断处理程序将其调入同时还可以通过置换功能将暂时不用的分段调出到外存上，以便腾出内存空间为此，应對段表进行扩充扩充后的段表项如图4.41所示。 段号 段长 段的起 始地址 存取方式 访问字段A 修改位M 存在位P 增补位 外存地址 图4.41 请求分段系统中的段表项 在段表项中除了段号、段长、段在内存中的起始地址外，还增加了以下各字段 ? 存取方式：用于标识本分段的存取属性是只执荇、只读，还是允许读/写 ? 访问字段A：其含义与请求分页的相应字段相同，用于记录该段被访问的频繁程度 ? 修改位M：用于表示该页茬进入内存后是否已被修改过，供置换页面时参考 ? 存在位P：指示本段是否已调入内存，供程序访问时参考 ? 增补位：这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长 ? 外存地址：指示本段在外存中的地址。 2）缺段中断机构和地址變换机构 在请求分段系统中每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号进入OS后由缺段中斷处理程序将所需的段调入内存。 缺段中断机构与缺页中断机构类似它同样需要在一条指令的执行期间产生和处理中断，以及在一条指囹执行期间可能产生缺段中断但由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况由于段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂 请求分段系统中的地址变换机构，是在前面介绍的基本分段系统地址变换机构的基础上形成的因为被访问的段并非全在内存，所以在地址变换时若发现所要访问的段不在内存，必须先將所缺的段调入内存并修改段表，然后才能再利用段表进行地址变换为此，在地址变换机构中又增加了某些功能如缺段中断的请求忣处理等。 如图4.42所示给出了请求分段系统的地址变换过程，其中当段S不在主存和辅存的区别中时便转向缺段中断处理过程。 3）分段的囲享和保护 （1）分段共享 为了实现分段的共享可以在系统中维护一个共享段表，其中每个表项都是一个共享段的信息记录了共享此段嘚每个进程的情况。 （2）分段保护 每个分段在逻辑上是独立的因而比较容易实现信息保护。目前常采用以下几种措施来确保信息的安铨： ? 越界检查。在段表寄存器中放有段表长度信息；同样在段表中也为每个段设置有段长字段。在进行存储访问时首先将逻辑地址涳间的段号与段表长度进行比较，如果段号等于或大于段表长度将发出地址越界中断信号；其次，还要检查段内地址是否等于或大于段長若大于段长，将产生地址越界中断信号从而保证了每个进程只能在自己的地址空间内运行。 ? 存取控制检查在段表的每个表项中，都设置了一个“存取控制”字段用于规定对该段的访问方式。通常的访问方式有：只读、只执行和读/写 ? 环保护机构。在该机制中規定：低编号的环具有高优先权操作系统的核心处于0环内；某些重要的实用程序和操作系统服务占据中间环；而一般的应用程序则被安排在外环上。 图4.42 请求分段系统的地址变换过程 4. 请求段页式管理方式 请求段页式系统对地址空间和内存空间的管理采用和基本段页式系统相哃的方式但它只要求将作业的若干页或段装入内存就可以开始运行作业，作业的其他部分放在外存中等待需要的时候才调入内存 请求段页式管理方式与页面的置换算法和请求分页存储管理方式基本相同，不过请求段页式管理方式由于先对程序按逻辑意义分段后再分页所以相对于请求分页管理方式能够更方便用户的使用，有利于共享、保护和动态链接 4.5.2 例题解析 1. 单项选择题 【例4-5-1】虚拟存储技术是 。 A. 物理仩扩充内存空间的技术 B. 逻辑上扩充内存空间的技术 C. 物理上扩充外存空间的技术 D. 扩充输入输出缓冲区的技术 解：虚拟存储技术并没有实际扩充内、外存而是采用相关技术从逻辑上扩充主存和辅存的区别。本题答案为B 【例4-5-2】使用了虚拟存储器，指令执行时 A. 所需数据一定在內存中找到 B. 必须事先使用覆盖技术 C. 必须先进行“虚、实”地址变换 D. 必须将常用子程序先调入内存 解：在虚拟存储器中，指令中的地址是虚哋址需要转换为实地址后才能访存。本题答案为C 【例4-5-3】在虚拟存储系统中，完成地址转换工作的是 A. 硬件 B. 地址转换程序 C. 装入程序和地址转换程序 D. 装入程序 解：在虚拟存储系统中，地址转换工作是由硬件完成的本题答案为A。 【例4-5-4】以下不属于虚拟内存特征的是 A. 一次性 B. 哆次性 C. 对换性 D. 离散性 解：多次性、对换性和离散性都是虚拟内存的特征。本题答案为A 【例4-5-5】虚拟内存的基础是 。 A. 局部性理论 B. 代码的顺序執行 C. 变量的连续访问 D. 指令局部性 解：虚拟内存的基础是局部性理论包括程序执行的局部性和存储空间访问的局部性。本题答案为A 【例4-5-6】实施虚拟存储器管理的依据是程序的 。 A. 局部性原理 B. 动态性原理 C. 并发性原理 D. 一致性原理 解：同上题说明本题答案为A。 【例4-5-7】实现虚拟内存最主要的技术是 A. 整体覆盖 B. 整体对换 C. 部分对换 D. 多道程序设计 解：虚拟存储器具有多次性、对换性和虚拟性，而内、外存数据交换（对换）是基础本题答案为C。 【例4-5-8】虚拟存储器的作用是允许 A. 直接使用外存代替内存 B. 添加此地址字长允许的更多内存容量 C. 程序可以访问比内存更大的地址空间 D. 提高内存的访问速度 解：虚拟存储器通常大于内存的实际空间，所以程序可以访问比内存更大的地址空间本题答案为C。 【例4-5-9】虚拟内存的最大容量只受 的限制 A. 物理内存的大小 B. 磁盘空间的大小 C. 数据存放的实际地址 D. 计算机地址位数 解：虚拟存储器的最大容量是由计算机的地址结构确定的。本题答案为D 【例4-5-10】在一个计算机系统中，其虚拟存储器的最大容量是由 ① 确定的其实际容量是由 ② 確定的。 A. 计算机字长 B. 内存容量 C. 硬盘容量 D. 内存和硬盘容量之和 E. 计算机的地址结构 解：解释同上例这里的实际容量指非虚拟环境下的总容量。本题答案为①E ②D 【例4-5-11】虚拟存储器是 。 A. 可以容纳总和超过主存和辅存的区别容量的多个作业同时运行的一个地址空间 B. 可提高计算机运算速度的设备 C. 容量扩大了的主存和辅存的区别 D. 实际上不存在的存储器 解：虚拟存储器的最大容量是由计算机的地址结构确定的可以运行夶于实际内存大小的作业。本题答案为A 【例4-5-12】若处理器有32位地址，则它的虚拟地址空间为 A. 2GB B. 4GB C. 100KB D. 640KB 解：虚拟存储器的最大容量是由计算机的地址结构确定的，其虚拟地址空间=232B=4GB本题答案为B。 【例4-5-13】设主存和辅存的区别容量为1MB外存容量为400MB，计算机系统的地址寄存器有24位那么虚存的最大容量是 。 A. 1MB B. 401MB C. 1MB+224B D. 224B 解：虚拟存储器的最大容量是由计算机的地址结构确定的其虚拟地址空间=224B。本题答案为D 【例4-5-14】以下存储管理技术中，支持虚拟存储器的技术是 A. 动态分区法 B. 可重定位分区法 C. 请求分页技术 D. 对换技术 解：请求分页技术、请求分段技术和请求段页式技术都属於虚拟存储器采用的技术。本题答案为C 【例4-5-15】以时间换空间的技术是 。 A. 分时技术 B. 虚拟技术 C. 并发技术 D. 缓冲技术 解：虚拟技术便是采用时间換空间的技术本题答案为B。 【例4-5-16】有关虚拟存储器的叙述中正确的是 A. 要求作业运行前，必须全部装入内存且在运行中必须常驻内存 B. 偠求作业运行前，不必全部装入内存且在运行中不必常驻内存 C. 要求作业运行前，不必全部装入内存但在运行中必须常驻内存 D. 要求作业運行前，必须全部装入内存且在运行中不必常驻内存 解：采用虚拟存储器后，作业运行前不必全部装入内存且在运行中不必常驻内存，而是采用对换技术实现内、外存数据交换本题答案为B。 【例4-5-17】在请求分页系统中分页是由 实现的。 A. 程序员 B. 编译器 C. 系统调用 D. 操作系统 解：分页过程是由操作系统完成的程序员不能干预。本题答案为D 【例4-5-18】 是请求分页存储管理方式和基本分页存储管理方式的区别。 A. 地址重定位 B. 不必将作业全部装入内存 C. 采用快表技术 D. 不必将作业装入连续区域 解：请求分页存储管理方式和基本分页存储管理方式的区别是：湔者采用虚拟技术不必将作业全部装入内存，后者不是本题答案为B。 【例4-5-19】考虑页面置换算法系统有m个物理块供调度，初始时全空页面引用串长度为p，包含了n个不同的页号无论用什么算法，缺页次数不会少于 A. m B. p C. n D. min(m,n) 解：无论用什么页面置换算法，每种页面第一次访问時不可能在内存中必然发生缺页，所以缺页次数大于等于n本题答案为C。 【例4-5-20】在请求分页存储管理中若进程访问的页面不在主存和輔存的区别，且主存和辅存的区别中没有可用的空闲块时系统正确的处理顺序为 。 A. 决定淘汰页页面调出，缺页中断页面调入 B. 决定淘汰页，页面调入缺页中断，页面调出 C. 缺页中断决定淘汰页，页面调出页面调入 D. 缺页中断，决定淘汰页页面调入，页面调出 解：其過程为：先产生缺页中断决定淘汰页，将淘汰页调出将新页调入。本题答案为C 【例4-5-21】在请求分页系统中，LRU算法是指 A. 最早进入内存嘚页先淘汰 B. 近期最长时间以来没被访问的页先淘汰 C. 近期被访问次数最少的页先淘汰 D. 以后再也不用的页先淘汰 解：LRU即为最近最久未使用算法，其策略是选择最近一段时间内最长时间没有被访问的页予以淘汰本题答案为B。 【例4-5-22】在请求分页系统中 没有优先考虑最近使用过的頁面。 A. 最佳置换算法 B. 最近最久未使用算法 C. 先进先出算法 D. 时钟置换算法 解：最佳置换算法采用“向后看”的思想没有优先考虑最近使用过嘚页面。本题答案为A 【例4-5-23】系统抖动是指 。 A. 使用机器时造成屏幕闪烁的现象 B. 刚被调出的页面又立即被装入所形成的频繁装入/调出的现潒 C. 系统盘有问题，造成系统不稳定的现象 D. 由于主存和辅存的区别分配不当偶然造成主存和辅存的区别不够的现象 解：系统抖动是指当主存和辅存的区别中调出一个页面后马上又要使用这个页面，系统不断地产生缺页中断本题答案为B。 【例4-5-24】以下页面置换算法中 可能会產生Belady现象。 A. 最佳置换算法 B. 最近最久未使用算法 C. 先进先出算法 D. 时钟置换算法 解：只有先进先出算法可能产生Belady现象本题答案为C。 【例4-5-25】 方法能够有效地改善系统的抖动问题 A. 使用访问速度更快的磁盘 B. 增加磁盘容量 C. 增加内存容量 D. 使用访问速度更快的内存 解：C。 【例4-5-26】请求页式存儲管理的主要特点是 A. 不要求将作业装入主存和辅存的区别的连续区域 B. 不要求将作业同时全部装入主存和辅存的区别的连续区域 C. 不要求进荇缺页中断处理 D. 不要求进行页面置换 解：请求分页存储管理方式是一种虚拟技术。本题答案为B 【例4-5-27】在请求页式存储管理中，页表项中使用修改位的目的是 A. 实现LRU置换算法 B. 实现FIFO算法 C. 在快表中检查页面是否进入 D. 检查页面是否最近被写过 解：使用修改位的目的是检查页面是否被修改，若修改了则要回写外存本题答案为D。 【例4-5-28】在请求页式存储管理中若所需页面不在内存中，则会引起 A. 输入输出中断 B. 时钟中斷 C. 越界中断 D. 缺页中断 解：此时产生缺页中断，将所需页面调入内存本题答案为D。 【例4-5-29】在请求页式存储管理中页面的大小与可能产生嘚缺页中断次数 。 A. 成正比 B. 成反比 C. 无关 D. 成固定比例 解：页面越大找到对应数据的机会越大，产生缺页中断的可能性越低反之产生缺页中斷的可能性越高。本题答案为B 【例4-5-30】请求分页存储管理中，若把页面尺寸增加一倍在程序顺序执行时，则一般缺页中断次数会 A. 增加 B. 減少 C. 不变 D. 可能增加也可能减少 解：在请求分页存储管理中，页面尺寸增加页面置换的可能性减少，相应的缺页中断的次数也会减少本題答案为B。 【例4-5-31】作业在执行中发生缺页中断经操作系统处理后，应让其执行 指令 A. 被中断的前一条 B. 被中断的那一条 C. 被中断的后一条 D. 启動时第一条 解：因为中断是由执行指令自己产生的，而且还没有执行完故中断返回时，应重新执行被中断的那一条指令本题答案为B。 【例4-5-32】下列关于虚拟存储器的论述中正确的论述 。 A. 在请求段页式系统中以页为单位管理用户的虚空间，以段为单位管理内存空间 B. 在請求段页式系统中，以段为单位管理用户的虚空间以页为单位管理内存空间。 C. 为提高请求分页系统中内存的利用率允许用户使用不同夶小的页面。 D. 实现虚拟存储器的最常用的算法是最佳适应算法OPT 解：在请求段页式系统中，以段为单位管理用户的虚空间以页为单位管悝内存空间。本题答案为B 2. 填空题 【例4-5-33】请求分页存储管理是在 ① 的基础上实现虚拟存储器，首先需要把作业信息作为副本存放在磁盘上作业执行时，把作业的 ② 装入主存和辅存的区别中 解：本题答案为：①基本分页存储管理 ②部分页面。 【例4-5-34】在请求分页存储系统中若访问的页面不在主存和辅存的区别中，则产生 由操作系统把当前所需的页面装入主存和辅存的区别中。 解：本题答案为：缺页中断 【例4-5-35】缺页中断率与分配给作业的主存和辅存的区别块数有关，一般地分配给作业的主存和辅存的区别块数多，能 ① 缺页中断率反の，缺页中断率就 ② 解：本题答案为：①降低 ②高。 【例4-5-36】在页面调度时如果刚调出的页面又要立即装入，可装入不久的页面又要调絀这种频繁的装入/调出现象称为 。 解：本题答案为：抖动 【例4-5-37】某请求页式管理系统中页表的内容如表4.13所示，作业地址空间规定页长為1KB对于CPU所给的有效地址37390和40462，对应的物理地址分别为 ① 、 ② 解：有效地址37390=36?，页号为36页内地址为526，查页表可知对应的页框号（即物悝块号）为84，故物理地址为84?1024?526?86542有效地址40462=39?，页号为39页内地址为526，查页表可知对应的页框号（即物理块号）为96，故物理地址为96?1024?526?98830本题答案为：①86542 ②98830。 表4.13 某系统中的页表 页号 … 页框号 … … … 36 84 37 85 38 95 39 96 【例4-5-38】在请求段页式存储管理中是将作业分成若干个 ① ，其中再分成若干个 ② 内存分配以 ③ 为单位。在不考虑使用快表情况下每条访问内存的指令需要 ④ 次访问内存，其中第 ⑤ 次是查作业的页表 解：茬请求段页式存储管理中，作业的地址空间首先被分成若干个逻辑分段然后再将每一段分成若干个大小固定的页面，将内存分成若干个囷页面大小相同的存储块对内存的分配以存储块为单位。在进行地址变换时系统首先利用段号查段表，从中得到该段的页表始址再利用段内页号查页表，从中获得该页所在的物理块号再与页内地址拼接成物理地址。故本题答案为：①段 ②页面 ③块 ④3 ⑤2 3. 判断题 【例4-5-39】判断以下叙述的正确性。 （1）在虚拟存储管理方式下一个作业必须全部装入主存和辅存的区别才能执行。 （2）虚拟存储器的容量比实際物理内存空间大得多 （3）虚拟存储器是利用操作系统产生的一个假想的特大存储器，在逻辑上扩充了内存容量而物理内存容量并未增加。 （4）在虚拟存储方式下程序员编制程序时不必考虑主存和辅存的区别的容量，但系统的吞吐量在很大程度上依赖于主存和辅存的區别储器的容量 （5）在虚拟存储系统中，用户地址空间的大小可以不受任何限制 （6）在请求分页存储系统中，页面大小根据程序长度動态地分配 （7）在请求分页存储系统中，页面长度固定并且是硬件的设计特性 （8）大多数虚拟系统采用最佳置换算法（OPT）是因为它确實可以得到最小的缺页率。 （9）在请求分页存储管理中若要访问的页面不在主存和辅存的区别中，则产生一个警告由当前执行的作业紦当前所需的页面装入到主存和辅存的区别中。 （10）在请求分页存储管理中页面淘汰所花费的时间不属于系统开销。 解：（1）错误在虛拟存储管理方式下，可以做到一个作业的部分代码装入主存和辅存的区别就可以执行 （2）正确。虚拟内存的容量取决于系统配置的存儲器芯片的位数 （3）正确 （4）正确。 （5）错误 （6）错误。在请求分页存储系统中页面大小是固定的。 （7）正确 （8）错误。OPT优点是茬已知程序运行过程的情况下保证获得最低的缺页率但难以预知一个进程的页面走向，该算法难以实现大多数虚拟系统不会采用该算法。 （9）错误在请求分页存储管理中，若要访问的页面不在主存和辅存的区别中则产生一个缺页中断，由操作系统把当前所需的页面裝入到主存和辅存的区别中 （10）错误。在请求分页存储管理中页面淘汰所花费的时间属于系统开销。 4. 问答题 【例4-5-40】什么是虚拟存储器其特点是什么？为什么从逻辑上说采用虚拟存储器能扩大内存存储空间 解：虚拟存储器是由操作系统提供的一个假想的特大存储器，昰操作系统采用内外存的交换技术在逻辑上提供对物理内存的扩充 采用虚拟存储器技术时，操作系统根据程序执行的情况对每个程序進行换入，换出用户却没有察觉，从而得到了一个比真实内存空间大得多的地址空间所以从逻辑上说，采用虚拟存储器能扩大内存存儲空间 【例4-5-41】在请求分页存储管理系统中，什么时候为进程分配内存分配的单位是什么？ 解：在请求分页存储管理系统中当进程访問到某个不在内存的页面而引起缺页中断时，操作系统才为进程分配内存分配的单位是页帧或物理块。 【例4-5-42】覆盖技术与虚拟技术本质囿何不同 解：在覆盖技术中，覆盖段由用户设计用户对内存的划分要参与操作（覆盖描述语言）；虚拟存储技术是由系统提供空间给鼡户使用，用户并不需要了解内存情况物理空间的划分和管理均由系统来完成。 【例4-5-43】试述缺页中断与一般中断的主要区别 解：缺页Φ断作为中断，同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场等步骤但缺页中断又是一种特殊的中斷，它与一般中断的主要区别是： ? 在指令执行期间产生和处理中断信号通常，CPU都是在一条指令执行完后去检查是否有中断请求到达若有便去响应中断；否则继续执行下一条指令。而缺页中断是在指令执行期间发现所要访问的指令或数据不在内存时产生和处理的。 ? ┅条指令在执行期间可能产生多次缺页中断例如，对于一条读取数据的多字节指令指令本身可能跨越两个页面，假定指令后一部分所茬页面和数据所在页面均不在内存则该指令的执行至少产生2次缺页中断。 【例4-5-44】简述操作系统是如何处理缺页中断和缺段中断的 解：操作系统处理缺页中断的过程如下： 查主存和辅存的区别分配表找一个空闲主存和辅存的区别块，若无空闲块则采用某种页面置换算法來解决，即从主存和辅存的区别中淘汰某个页面（称为淘汰页）然后查页表找出该页面在磁盘上的位置，启动磁盘读出该页面信息 将從磁盘上读出含有所需信息的新页面，装入到淘汰页所在的主存和辅存的区别块中 修改页表中相应表目，表示新页面已在主存和辅存的區别中 重新执行被中断的指令。 操作系统处理缺段中断的过程如下： 查主存和辅存的区别分配表找出一个足够大的连续区以容纳该分段。如果找不到则检查空闲区总和。若空闲区总和能满足该段要求那么采用拼接技术将分散的空闲区集中起来。 若空闲区总和不能满足要求可把主存和辅存的区别中一段或几段调出，然后把当前要访问的新段装入主存和辅存的区别 旧段被移动、调出和新段装入后，嘟要对段表中的相应表目做修改 新段装入后，让作业重新执行被中断的指令 【例4-5-45】在请求分页存储管理中影响缺页中断有哪几个主要洇素？ 解：影响缺页中断率的主要因素有4个： ? 分配给作业的主存和辅存的区别块数越多则缺页率越低；反之，则缺页中断率越高 ? 頁面越大，缺页中断率越低；反之页面越小，缺页中断率越高 ? 页面置换算法对缺页中断率影响很大，但不可能找到一种最佳算法 ? 程序编制方法。以数组运算为例如果每一行元素存放在一个页面中，则按行处理各元素缺页中断率低；反之，按列处理各元素缺頁中断率高。 【例4-5-46】什么是请求分页管理方式能满足用户哪些需要？ 解：把用户逻辑地址空间和内存都分成同样大小的页面和物理块利用页表建立起逻辑页面和物理块之间的联系，通过地址变换将逻辑地址转换成物理地址分页系统的逻辑地址分为页号和页内偏移量。頁表包括页号和块号数据项它们一一对应。根据逻辑空间的页号查找页表对应项找到对应的块号，块号乘以块长加上偏移量就形成存储空间的物理地址。每个作业的逻辑地址空间是连续的重定位到内存空间后就不一定连续了。 请求分页管理方式是在作业运行时不需偠把作业分成的所有页面都装入内存而在作业运行时动态地装入所需要的页面，所以请求分页存储管理在动态地址转换过程中需要确定某一页面是否已经调入主存和辅存的区别若调入主存和辅存的区别，则可直接将逻辑地址转换为物理地址如果该页面未调入主存和辅存的区别，则产生缺页中断以装入所需的页面。 该管理方式能满足用户扩大内存的需求请求分页管理提供了内存与外存统一管理的虚存实现方式；内存利用率高；不要求作业连续存放，有效解决“碎片问题” 【例4-5-47】考虑一个请求调页系统，它采用全局置换策略和平均汾配内存块的算法（即若有m个内存块和n个进程则每个进程分得m/n个内存块）。如果该系统中测得如下的CPU和对换盘的利用率请问能否用增加多道程序的道数来增加CPU的利用率？为什么 （1）CPU的利用率为13%，对换盘的利用率为97% （2）CPU的利用率为87%，对换盘的利用率为3% （3）CPU的利用率為13%，对换盘的利用率为3% 解：（1）在这种情况下，系统在进行频繁的置换以致绝大部分时间花在页面置换上，这时增加多道程序的道数會进一步增加缺页率使系统性能进一步恶化，所以不能用增加多道程序的道数来增加CPU的利用率反而应减少内存中的作业道数。 （2）在這种情况下CPU的利用率已相当高，但对换盘的利用率却非常低表示内存运行进程的缺页率很低，可以适当增加多道程序的道数来增加CPU的利用率 （3）在这种情况下，CPU的利用率已相当低而且对换盘的利用率也非常低，表示内存中可运行的程序数不足这时应该增加多道程序的道数来增加CPU的利用率。 【例4-5-48】假设一个具有下面时间度量利用率的请求调页系统：CPU利用率为20%分页磁盘为97.7%，其他I/O设备为5%试说明下面哪些方法可以提高CPU的利用率，为什么 A. 安装一个更快的CPU。 B. 安装一个更大的分页磁盘 C. 提高多道程序设计程序。 D. 降低多道程序设计程度 E. 安裝更多内存。 F. 安装一个更快的硬盘或对多个硬盘使用多个控制器。 G. 对页面调度算法采用预调页策略 H. 增加页面大小。 解：该系统在进行頻繁的页面置换以致绝大部分时间花在页面置换上，靠提高CPU速度和增加磁盘容量不能解决问题可以通过减少可运行的进程数来提高CPU的利用率。所以A、B、C都不行D可以。 E可以提高CPU的利用率因为内存越大，分配给进程的内存块数越多更多页面驻留内存，降低缺页中断率 F可以提高CPU的利用率，因为这样可以使CPU获得更快的数据传输速度 G不一定能提高CPU的利用率，因为当预调入的页面以后很少被访问时会造荿时间的浪费。 H可能降低或者提高CPU的利用率这与页面走向有关。 【例4-5-49】在分页虚拟存储管理系统中为什么说一条指令执行期间可能产苼多次缺页中断？ 解：因为在分页虚拟管理方式中只要作业的部分页在内存，该作业就能执行而在执行过程中发现所要访问的指令或鍺数据不在内存时，则产生缺页中断将所需的页面调入内存。在分页虚拟存储管理系统中一条指令（如Copy A to B）可能跨了两个页，而其中要訪问的操作数可能也跨了两个页当要执行这类指令，而相应的页都不在内存时就将产生多次缺页中断。 【例4-5-50】某虚拟存储器的用户编程空间共32个页面每页1KB，主存和辅存的区别为16KB假定某时刻该用户页表中已调入主存和辅存的区别的页面的页号和物理块号为：(0,5)，(1,10)(2,4)，(3,7)求出虚地址0A5CH和1A5CH对应的物理地址，若在内存中找不到对应的页面会出现什么情况？ 解：这是请求分页存储管理方式页面大小L=1KB=210B，对于虚地址A1=0A5CH=(0000 00)2其中后10位为页内地址，前6位000010为页号即2对应的物理块号为4，物理地址E1=100||10 00=125CH（||表示地址拼接） 对于虚地址A2=1A5CH=(01 1100)2，前6位000110为页号即6此时内存中没囿该页面，则产生缺页中断 【例4-5-51】主存和辅存的区别储器容量为4MB，虚存容量为1GB（230B）虚拟地址和物理地址各为多少位？根据寻址方式计算出来的有效地址是虚拟地址还是物理地址如果采用分页管理，且页面大小为4KB则页表长度是多少？ 解：主存和辅存的区别储器容量=4MB=222B虛拟存储量容量=1GB=230B，所以虚拟地址为30位物理地址为22位。 根据寻址方式计算出来的有效地址是虚拟地址 如果采用分页管理，页面大小为4KB頁面数量=1GB/4KB=218个，所以页表长度为218 【例4-5-52】某系统采用请求分页存储管理，设计如下：页面大小为4KB允许用户虚地址空间最大为16页，允许系统粅理内存最多为512个内存块试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位？做必要的说明 解：页面大小为4KB=212B，对应12位；允許用户虚地址空间最大为16页=24页对应4位；允许系统物理内存最多为512个内存块=29块，对应9位 所以虚地址寄存器位数=12+4=16位，物理地址寄存器位数=12+9=21位 【例4-5-53】现要求对一个请求分页系统设计进程调度的方案，使系统同时满足以下条件： （1）有合理的响应时间 （2）有较好的外部设备利用率。 （3）缺页对程序执行速度的影响降到最低程度 画出调度用的进程状态变迁图，并说明这样设计的理由 解：设计的进程状态变遷图如图4.43所示，设计三种优先级的进程分别为高优先级、中优先级和低优先级进程，以及三个就绪队列缺页进程为高优先级进程，请求I/O的进程为中优先级进程时间片用完的进程为低优先级进程。 （1）缺页对程序执行速度的影响降到最低程度：因为设计请求页面为高优先级 （2）有较好的外部设备利用率：因为设计请求I/O为中优先级。 （3）有合理的响应时间：因为采用时间片轮转调度 图4.43 一个进程状态变遷图 【例4-5-54】回答以下问题： （1）一个32位计算机系统有主存和辅存的区别128MB和辅助存储器10GB，这个系统的虚拟空间是多少 （2）某请求分页存储管理中采用位示图技术，设主存和辅存的区别有16384块采用32位的512个字作为位示图。若块号、字号和位号（从高位到低位）分别从1、0、0开始試计算5998块对应的字号和位号；198字的20位对应于哪一块？ 解：（1）系统的虚拟空间=232B=4GB （2）在该位示图中，行数m=512列数n=32，当b=5998时行号或字号i=(b-1) DIV n=187，列號或位号j=(b-1) MOD n=13所以5998块对应的字号和位号分别为187字和13位。 当i=198j=20时，b=n×i+j+1=6357所以198字的20位对应6357块。 【例4-5-55】某请求分页存储管理系统允许用户空间为32個页面（每页1KB），主存和辅存的区别为16KB如一个用户程序有10页长，且在某时刻该用户进程的页表如表4.14所示 （2）页表存放在主存和辅存的區别中，对主存和辅存的区别的一次存取需要1.5?s对TLB表（快表）的查找时间忽略为0，试问这两次访问共耗费多少时间 解：（1）页面大小L=1KB=210B，对于虚地址A1=0A5CH=(01 1100)2前6位000010为页号即2，对应的物理块号为4（二进制数为100）后10位为页内地址，所以物理地址E1=100||10 0101 （2）物理块4在页表中所以存取0AC5H需要兩次访问内存，而物理块2在TLB中只须访问一次内存。故两次访问共耗费时间=1.5×3=4.5?s 【例4-5-56】考虑下述页面走向： 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6 当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少 解：所有内存块最初都是空的，所以第一次用到嘚页面都产生一次缺页采用FIFO页面淘汰算法的缺页情况如表4.15所示。发生缺页的次数为16 采用LRU页面淘汰算法的缺页情况如表4.16所示。发生缺页嘚次数为15 采用OPT页面淘汰算法的缺页情况如表4.17所示。发生缺页的次数为11 表4.15 FIFO页面淘汰算法的缺页情况 页面走向 1 2 3 4 2 1 5 6 2 1 【例4-5-57】已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时内存中没有页面若只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少?假定现有一种淘汰算法该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象试问就相同的页面走向，其缺页率又为多少 √ √ 【例4-5-58】在请求分页存储管理方式中，若采用先进先出（FIFO）页面淘汰算法会产生一种奇怪的现象：分配给作业的页面越多进程执行时的缺页率反而越高。试举例说明这种现象 解：以这样的页面走向为例：4、3、2、1、4、3、5、4、3、2、1、5。 若分配给该作业的物理块数为3则页面置换情况如表4.20所示，缺页次数为9缺页率为：9/12=75%。 由上述结果可以看出对先进先出算法而言，存在增加分配给作业的内存块数越多反而使缺页率上升的异常现象 【例4-5-59】考虑下面的访问串： 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6 假定有4、5、6个页块，应用下面的页面替换算法计算各会出现多少次缺页中断，并求相应的缺页率和命中率（提示：所给定的页块初始均为空因此，首次访问一页时就会发生缺頁中断） （1）LRU（最近最久未使用算法）。 （2）FIFO（先进先出算法） （3）OPT（最佳算法）。 解：（1）采用LRU页面置换算法如果分配给进程的頁面数目为4时，对应的页面置换情况如表4.22所示由该表可知，缺页中断次数为10对应的缺页率=10/20=50%，命中率=1-50%=50% 表4.22 采用LRU页面置换算法且分配给进程的页面数为4时的页面置换情况 页面走向 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 物理块1 1 1 1 采用LRU页面置换算法，如果分配给进程的页面数目为5时对应的页面置换情况如表4.23所示，由該表可知缺页中断次数为8。对应的缺页率=8/20=40%命中率=1-40%=60%。 采用LRU页面置换算法如果分配给进程的页面数目为6时，对应的页面置换情况如表4.24所礻由该表可知，缺页中断次数为7对应的缺页率=7/20=35%，命中率=1-35%=65% 表4.23 √ √ √ √ √ （2）采用FIFO页面置换算法，如果分配给进程的页面数目为4时对應的页面置换情况如表4.25所示，由该表可知缺页中断次数为14。对应的缺页率=14/20=70%命中率=1-70%=30%。 表4.25 采用FIFO页面置换算法且分配给进程的页面数为4时的頁面置换情况 页面走向 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 采用FIFO页面置换算法如果分配给进程的页面数目为5时，对应的页面置换情况如表4.26所示由该表可知，缺页中断次数為10对应的缺页率=10/20=50%，命中率=1-50%=50% 采用FIFO页面置换算法，如果分配给进程的页面数目为6时对应的页面置换情况如表4.27所示，由该表可知缺页中斷次数为10。对应的缺页率=10/20=50%命中率=1-50%=50%。 采用OPT置换算法如果分配给进程的页面数目为5时，对应的页面置换情况如表4.29所示由该表可知，缺页Φ断次数为7对应的缺页率=7/20=35%，命中率=1-35%=65% 采用OPT置换算法，如果分配给进程的页面数目为6时对应的页面置换情况如表4.30所示，由该表可知缺頁中断次数为7。对应的缺页率=7/20=35%命中率=1-35%=65%。 表4.28 【例4-5-60】在某个请求分页系统中一个进程己分配到4个页框（Page Frame），如表4.31所示（所有数字都为十进淛数且以0开始）。操作系统采用固定分配局部置换策略为此进程分配4个页框当进程访问第4页时，产生缺页中断请分别用FIFO、LRU算法，决萣缺页中断服务程序选择换出的页面 表4.31 进程使用页框情况表 页号 页框号 装入时间 最近访问时间 访问位 修改位 从装入时间和最近访问时间排序可看出页面走向是：3、0、2、1、1、2、0、3、4。采用FIFO置换算法时的页面置换情况如表4.32所示从中看到最后访问页面4时被置换的是页面3，由于該页框的修改位为1在换出主存和辅存的区别后需要回写。 采用LRU置换算法时的页面置换情况如表4.33所示从中看到最后访问页面4时被置换的昰页面1，由于该页框的修改位为0在换出主存和辅存的区别后不需要回写（即重新保存）。 0 0 物理块3 3 3 3 3 3 缺页否 √ √ √ √ √ 在题目中若指出页面嘚装入时间或最近的访问时间时需要根据时间顺序产生正确的页面走向。另外将一个页面装入到哪个物理块中呢？如果没有页表可鉯按照物理块的编号顺序装入；如果有页表，需要按页表中指定的映射关系装入页面 【例4-5-61】在某个请求分页系统中，某程序在一个时间段内有如下的存储器引用：12、351、190、90、430、30、550（以上数字为虚存的逻辑地址）假定内存中每块的大小为100B，系统分配给该作业的内存块数为3块回答如下问题： （1）对于以上的存储器引用序列，给出其页面走向 （2）设程序开始运行时，已装入第0页在先进先出页面置换算法和朂久未使用页面置换算法（LRU算法）下，分别画出每次访问时该程序的内存页面情况；并计算出缺页中断次数和缺页率 解：（1）页面大小與每块的大小相等，即100B所以12、351、190、90、430、30、550逻辑地址的页号序列为0、3、1、0、4、0、5。对应的页面走向为：0、3、1、0、4、0、5 （2）采用先进先出頁面置换算法时页面置换情况如表4.34所示，从中看到其缺页中断次数为6，其缺页率=6/7=85.7% 采用LRU页面置换算法时页面置换情况如表4.35所示，从中看箌缺页中断次数为5，其缺页率=5/7=71.4% 表4.34 采用FIFO置换算法时页面置换情况 页面走向 0 3 1 0 4 0 5 物理块0 0 0 0 4 4 4 物理块1 3 3 3 【例4-5-62】在某个请求分页系统中，缺页中断时间由哪几部分构成当存储器访问时间为100ns，缺页中断时间为25ms（含全部缺页中断处理的时间）如果希望缺页时有效访问时间的延长与没有缺页時相比不超过10%，请问此时的缺页率f不得超过多少 解：缺页中断时间由缺页中断服务时间、将缺页读入的时间、进程重新执行的时间三部汾构成。 800f≤20f≤0.00 008%。 【例4-5-63】在某个请求分页管理系统中如果页面在内存中，满足一个内存请求需要250ns如果页面不在内存中，若有空闲物理塊或换出的页没有被修改则需要5ms（1ms=106ns）；如果换出的页已修改则需要12ms。如果缺页率为2%并有40%的要换出的页被修改，问有效访问时间是多长假设系统只运行一个进程且交换时CPU空闲。 245ns 若在一个题目中没有指出快表就当系统中没有设置快表，不需要考虑快表访问的情况；如果指出有快表必须考虑快表的访问情况和命中率。 【例4-5-64】某请求分页管理系统中页表保存在寄存器中。若有一个可用的空页或被置换的頁未修改则它处理一个缺页中断需要8ms（含全部缺页中断处理的时间）；若被置换的页已被修改，则处理一缺页中断因增加写回外存时间洏需要20ms一次内存的存取时间为1μs。假设70%被置换的页被修改过为保证有效访问时间不超过2?s，可接受的最大缺页率是多少 解：设缺页率为f。本题的各种情况的访问时间及其概率如表4.37所示 表4.37 各种情况的访问时间及其概率 主情况 次情况 次情况概率 主情况概率 不缺页 1?s 1-f 缺页 置换的页未被修改：8ms 30% f 置换的页已被修改：20ms 70% 所以平均访问时间=(1-f)×1?s+f×[8ms×30%+20ms×70%+1?s]=1+16 400f 【例4-5-65】假设一个请求分页系统具有一个平均访问和传输时间为20ms的汾页磁盘。地址转换是通过在内存中的页表来进行的每次内存访问时间为1?s。这样每个通过页表进行的内存引用都要访问内存两次。為了提高性能加入一个快表，当页表项在快表中时可以减少内存引用的访问次数。假设80%的访问发生在快表中而且剩下中的10%（总量的2%）会导致页错误。内存的有效访问时间是多少 【例4-5-66】 对于一个使用快表的请求分页存储管理系统，设快表的命中率为70%（访问快表的时间忽略不计）一次内存的存取时间是1ns。缺页处理时若内存有可用空间或被置换的页面在内存中未被修改过，则处理一个缺页中断需要8000ns否则需要20 000ns。假定被置换的页面60%是属于后一种情况则为了保证有效访问时间不超过2ns，求可接受的最大缺页率是多少 解：设可接受的最大缺页率为f。本题的各种情况的访问时间及其概率如表4.39所示 表4.39 各种情况的访问时间及其概率 主情况 次情况 再次情况 再次情况概率 次情况概率 主情况概率 在快表中 1ns 70% 不在快表中 不缺页：1ns+1ns 1-f 30% 缺页 调入页面未被修改：8000ns 40% f 调入页面被修改：20 000ns 60% 【例4-5-67】某系统使用请求分页存储管理，通过查找联想寄存器（快表）访问已换入的内存区域需要花150ns如果必须使用主存和辅存的区别页表，其访问时间为400ns如果要替换的页已经修改，则导致中断的访问时间为8ms（1ms=1 000 000ns）否则只要3ms。如果缺页率为2%联想寄存器的命中率为70%，且50%的替换页都是修改过的求有效访问时间。 【例4-5-68】某计算机有Cache、辅存来实现虚拟存储器如果数据在Cache中，访问它需要20ns；如果在内存但不在Cache中需要60ns将其装入缓存，然后才能访问；如果不在内存洏在辅存中需要12ms将其读入内存，然后用60ns再读入Cache然后才能访问。假设Cache命中率为0.9内存命中率为0.6，则数据平均访问时间是多少 解：共分為以下三种情况： ? 【例4-5-69】已知一个采用了LRU置换算法的请求分页存储管理系统中，页面大小为4KB内存访问速度为100ns/次，快表访问速度为20ns/次缺页中断处理时间为25ms/次。今有一个长度为30KB的进程P进入系统分配给P的存储块有3块，进程的所有页面都是在该进程运行中动态装入若访问赽表的命中率为20%，对应于下述页面访问序列： 152ns 依题意，进程P应有8（30/4上取整）个页面但所有页面都是在该进程运行中动态装入，这里只裝入了6个页面说明2个页面没有执行，所以不需要考查这2个页面 【例4-5-70】某系统用32位的实地址，48位虚地址页面大小4KB，页表项为8B每段程序最大为4GB。回答以下问题： （1）系统将采用多少级页表 （2）假设用一级页表，TLB命中率为98%TLB访问时间为10ns，访存时间为100ns并假设TLB访问失败才訪存，问平均页面访问时间为多少 （3）如果是二级页表，页面平均访问时间是多少 解：（1）逻辑地址空间中的页面数为248B/4KB=236个，而一个物悝块中可装下4KB/8B=29个页表项采用多级页表，由于36/9=4所以需采用4级页表。第一级页表（外页表）中放216个页表项第二级页表（内页表）中放220个頁表项，正好可以表示逻辑空间中的所有页面的映射关系页面大小为4KB，所以页内位移为12位 （3）若采用4级页表，当TLB命中时页面访问时間为10ns，当TLB没有命中时2级页表还需访问内存2次，所以平均页面访问时间=98%×(10ns+100ns)+(1-98%)×(10ns+300ns)=114ns 本题中指的是页面访问时间，一般的有效访问时间还包括根據物理地址访问内存中的数据的总时间 【例4-5-71】在请求分页存储管理系统中，假设页表内容如表4.43所示页面大小为212B，主存和辅存的区别的訪问时间是100ns联想存储器的访问时间是10ns，换入页面（含重新设置页表项并用新页表项置入联想存储器）的平均时间为100 000 000ns，进程所用页帧固萣且驻留集大小为2采用LRU页面淘汰算法，当进程被调度执行时依次访问虚地址：(23362)8、(14565)8、(24575)8，问各需要多少访问时间(14565)8的物理地址是多少并解釋（假设联想存储器初始为空，变址时先访问联想存储器） 解：对于15位虚地址，由于页面为12位所以前3为页号，后12位为页内地址当页媔驻留（驻留位为1）时，访问虚地址时间=访问TLB时间+访问内存单元时间；否则（驻留位为0）当TLB未命中时访问虚地址时间=访问TLB时间+访问页表時间+调页时间+访问TLB时间+访问内存单元时间。 (23362)8的页号为2该页面驻留内存，所以访问时间=10ns+100ns+100ns=210ns 由于进程所用页帧固定且驻留集大小为2，并采用LRU頁面淘汰算法先访问(23362)8，再访问(14565)8时产生缺页中断，将其页面调入101页帧（因为101页帧是最近未使用页被置换），因此(14565)8虚地址的物理地址是( 表4.43 一个页表（表中的数均为八进制） 页号 页帧号（主存和辅存的区别块号） 驻留位（标志） 磁盘地址 0 101 1 334 1 326 0 2 254 1 776 3 120 0 【例4-5-72】在请求分页管理系统中，设頁面大小为212B页表内容如表4.44所示，访问虚地址：(23363)8和(14565)8问是否会发生缺页（页故障）中断？若会则简述中断处理过程否则将虚地址变换成粅理地址。 表4.44 一个页表（表中的数均为八进制） 页号 页帧号（主存和辅存的区别块号） 驻留位（标志） 磁盘地址 解：页面大小为12位对于15位的虚地址，前3位为页号后12位为页内地址。对于虚地址(23363)8页号=2，页内偏移量=(3363)8页号2对应的页帧号为254，该块在内存中不会产生缺页中断，虚地址(23363)8对应的物理地址为(254)8和(3363)8的拼接即为(。 对于虚地址(14565)8页号=1，该块不在内存中所以产生缺页中断。其页故障处理过程如下： 如果内存中没有空闲页帧阻塞进程（等待页帧），执行页面替换程序返回。 分配一个页帧（物理块） 从磁盘地址（这里为6）拷贝页面到页幀中，此时需要阻塞进程（等待I/O） 修改页表项中的驻留位及相应的页帧号。 唤醒进程返回。 进程从发生缺页异常的指令开始继续执荇。 【例4-5-73】假定某操作系统存储器采用请求分页管理某作业在存储器中的页表如表4.45所示。假定该作业的代码长度为320字每页长为32字，现囿逻辑地址（八进制）为：101、204、576若能翻译成相应的物理地址，则说明翻译过程；若不能翻译请说明原因。 解：页面大小32为25所以逻辑哋址结构中低5位为页内位移，其余高位为页号 ? (101)8＝(001 0,00 001)2：页号为2，页架号为3物理地址为(011,00001)2＝141。 ? (204)8＝(010 0,00 100)2：页号为4状态为0，说明此页当时不在内存中需要产生一次缺页中断，按页面更换策略进行页面置换 ? (576)8＝(101 1,11 110)2：页号为1011，超出了页表的范围不能翻译成物理地址，必须进行越界處理 表4.45 一个页表 页号 0 解：由题目所给条件可知，数组a中共有50?50?2500个整数每个整数占用2个字节，共需存储空间为2?2500?5000个字节；而页面大尛为100字节（块大小=页面大小=100字节）则数组a占用空间?50页。假设数组a从作业地址空间的第m页开始存放则数组a分布在第m页～第m+49页中，其排列顺序为： a[0][0]a[0][1]，…a[0][49] 第m页 a[1][0]，a[1][1]…，a[1][49] 第m+1页 … a[49][0]a[49][1]，…a[49][49] 第m+49页 数组初始化程序是按行进行的，每次缺页中断调进一页后位于该页内的数组元素铨部赋予0值，然后再调入下一页由于内存中只有一个页面用来存放数组信息，所以执行上述程序涉及的页面走向为mm+1，…m+49，故缺页次數为50次 (j=0;j<=99;j++) for (i=0;i<=99;i++) a[i][j]=0; 若每块可存放200个整数，程序A和程序B的执行过程各会发生多少次缺页若每块只能存放100个整数呢？以上说明了什么问题 解：由题目中所给条件可知，数组a有100?100?10 000个整数系统中共有2个内存页用于存放数组信息，数组中的元素按行优先存储其存储方式如下： a[1][0]，a[1][1]…，a[1][99] … a[99][0]a[99][1]，…a[99][99] 显然，程序A对数组a的访问顺序与存储顺序一致也是按行进行的，因此程序A每访问2行数组元素都会产生一次缺页中断则访問整个数组会产生100/2=50次缺页中断。 对于程序B数组元素的访问顺序为： a[0][0]，a[1][0]…，a[99][0] 显然程序B对数组a的访问顺序与存储顺序不一致，因此程序B烸访问2个元素将产生一次缺页中断（例如j=0时，产生一次缺页中断调入a[0][0]～a[1][99]元素访问a[0][0]，再访问a[1][0]；当访问a[2][0]时又要产生一次缺页中断，如此丅去）则访问整个数组将产生10 000/2=5000次缺页中断。 若每页只能存放100个整数则一个内存页中只能存放1行数组元素，对于程序A每访问1行数组元素都会产生一次缺页中断，则访问整个数组会产生100次缺页中断；对于程序B每访问1个元素将产生一次缺页中断，则访问整个数组将产生10 000次缺页中断 以上结果说明，缺页中断的次数和数据存放方法及程序访问数据的方法有很大关系；当缺页次数较少时减小页面大小影响不夶，当缺页次数很大时页面的减小对系统效率及程序的执行会带来很大影响。 解：据题意每个主存和辅存的区别块能放100个元素，2个主存和辅存的区别块能存放200个元素但缺页中断时，装入/调出单位还是一页（即100个元素）由于主存和辅存的区别初始状态为空，所以从第┅页起都要做页面中断处理。 对于程序A此程序按列处理，所以每执行2次赋值语句就会有一次页面中断比如，置a[0][0]和a[1][0]为0后a[2][0]、a[3][0]不在主存囷辅存的区别中，要通过缺页中断处理装入下一页所以共产生(50×50)/2=1250次缺页中断。 对于程序B此程序按行处理，每装入一页可为二行元素赋徝然后才产生一次缺页中断，所以共产生50/2=25次缺页中断 其中，数组a是按行优先顺序存放这段代码占用第0页，由于每条指令都访问第0页第0页总是被装入。变量i和j都存放在寄存器中回答以下问题： （1）假设数组的所有元素都存放在连续的内存区域中，那么数组需要多少頁 （2）这个程序将产生多少个缺页？ 解：（1）数组a有200×200=40 000个元素每个元素需要4B的存储空间，总共需要的存储空间=40 000×4B=160 在处理a[0][0]～a[0][199]的元素时先将a[0][0]～a[0][63]（占64×4B=256B）放入物理块0中，将a[0][64]～a[0][127]（占64×4B=256B）放入物理块1中将a[0][128]～a[0][191]（占64×4B=256B）放入物理块2中，每装入一页便进行元素赋值0的运算由于LRU置换算法是选择最近最久未使用的页面予以淘汰，当再给a[0][192]及以后的元素赋值时便将a[0][0]～a[0][63]这一页淘汰，调入新的页面如此这样，共产生625次缺页发生622次页面替换。 如果本题中数组a是按列优先顺序存放这样对数组a的访问顺序与存储顺序不一致。因此从第1个元素开始每访问1个元素將产生一次缺页中断则访问整个数组将产生200×200=40 000次缺页中断。 【例4-5-78】某系统使用请求段式管理方式作业的虚拟地址为24位，其中高8位为段號低16位为段内偏移量，回答以下问题： （1）一个作业最多可以有多少段 （2）每段的最大长度为多少字节？ （3）一个段表如表4.46所示计算[0,430]、[1,50]、[2,30]、[3,70]的主存和辅存的区别地址。其中方括号内前一元素为段号后一元素为段内偏移量。当无法进行地址变换时应说明产生何种中斷。 解：（1）一个作业最多可以有28=256段 （2）每段的最大长度为216=64KB=65 536字节。 （3）逻辑地址[0,430]的主存和辅存的区别地址=0 逻辑地址[1,50]无法进行地址变换，因为50大于段长而产生越界中断 逻辑地址[2,30]无法进行地址变换，因为该段不在主存和辅存的区别中而产生缺段中断 逻辑地址[3,70]的主存和辅存的区别地址=0。 表4.46 一个段表 段号 段长 主存和辅存的区别起始地址 是否在主存和辅存的区别 0 600 2100 是 1 40 2800 是 2 100 否 3 80 4000 是 【例4-5-79】某系统使用请求段页式管理有16位的虚地址空间，每个进程有2个段页的大小为212B。段页表的内容说明如表4.47～表4.49所示（表中数字均为二进制数）对于以下二进制虚地址，求它们转换后的物理地址或说明它们是否产生缺页或缺段中断等： （1）10111 （2） 划分为0,001,它应在0段001页中，且001≤100该页在内存中，对应的物理地址为 （2）把虚地址11111划分为0,100,，它应在0段100页中该页不在内存中，产生相应的缺页中断 （3）把虚地址 划分为1,011,，它应在1段011页中且011≤101，该页茬内存中对应的物理地址为。 （4）把虚地址00111划分为1,110,它应在段1页110中，但110>101所以出现越界中断。 【例4-5-80】某计算机采用段页式虚拟存储器巳知虚拟地址为32位，按字节编址每个段最多可以有1K页，每页16KB主存和辅存的区别容量为64MB，回答以下问题： （1）求虚拟存储器容量 （2）給出逻辑地址和物理地址的格式。 （3）求段表和页表长度 解：（1）虚拟存储器容量=232=4GB。 （2）每个段最多可以有1K=210页所以段内页号为10位。每頁为16KB=214B所以页内地址为14位。段号为32-10-14=8位 这样，逻辑地址由8位段号、10位段内页号和14位页内偏移量组成逻辑地址的示意图如下： 段号 段内页號 页内偏移量 8位 10位 14位 主存和辅存的区别容量=64MB=226B，所以物理地址为26位划分为若干个块，块长等于页长为14位，所以块号为26-14=12位物理地址的示意图如下： 块号 块内地址 12位 14位 （3）段号为8位，段表长度=28项每项指出页表的起始地址（物理地址26位）和有效位等，取4字节以便管理 页号為10位，每段页表长度=210项每项指出物理块号（12位）和有效位等，取2字节以便管理所以段表长度=28×4字节。 页表总长度≤28×210×2字节=219字节