存储器管理习题

本文格式为Word版，下载可任意编辑——存储器管理习题第4章存储器管理

5.2例题解析

例5.2.1为什么要引入规律地址？解引入规律地址有如下原因：

(1)物理地址的程序只有装入程序所规定的内存空间上才能正确执行，假使程序所规定内存空间不空闲或不存在，程序都无法执行；(2)使用物理地址编程意味着由程序员分派内存空间，这在多道程序系统中，势必造成程序所占内存空间的相互冲突；

(3)在多道程序系统中，程序员门无法事先协商每个程序所应占的内存空间的位置，系统也无法保证程序执行时，它所需的内存空间都空闲。

(4)基于上述原因，必需引入一个统一的、在编程时使用的地址，它能够在程序执行时根据所分派的内存空间将其转换为对应的物理地址，这个地址就是规律地址。

(5)规律地址的引入为内存的共享、保护和扩展提供便利。

例5.2.2静态重定位的特点有哪些？

(1)实现简单，无需增加硬件地址变换机构；(2)一般要求为每个程序分派一个连续的存储区；(3)在重定位过程中，装入内存的代码发生了改变；(4)在程序执行期间不在发生地址的变换；

(5)在程序执行期间不能移动，且难以做到程序和数据的共享，其内存利用率低。

例5.2.3动态重定位的特点有哪些？

(1)动态重定位的实现要依靠硬件地址变换机构，且存储管理的软件算法比较繁杂；

(2)程序代码是按原样装入内存的，在重定位的过程中也不发生变化，重定位产生的物理地址存放在内存地址寄放器中，因此不会改变代码；

(3)同一代码中的同一规律地址，每执行一次都需要重位一次；

(4)只要改变基地址，就可以很简单地实现代码在内存中的移动；(5)动态重定位可以将程序分派到不连续的存储区中；(6)实现虚拟存储器需要动态重定位技术的支持；

83

尽管动态重定位需要硬件支持，但他支持程序浮动，便于利用零散的内存空间，利于实现信息共享和虚拟存储，所以现代计算机大都采用动态重定位。

例5.2.4装入时动态链接的优点有哪些？（1）便于软件版本的修改和更新在采用装入时动态链接方式时，要修改或更新各个目标模块，是件十分简单的事，但对于经静态链接以装配在一起的装入模块，假使要修改或更新其中的某个目标模块时，则要求重新开启装入模块，这不仅是低效的，而且对于普通用户是不可能的。

（2）便于实现目标模块共享

若采用装入时动态链接方式，OS能够将一个目标模块链接到几个应用程序中去。即实现多个应用程序对该模块的共享；然而，采用静态链接方式时每个应用模块都必需含有该目标模块的拷贝，则无法实现共享。

例5.2.5覆盖技术与虚拟存储技术有何本质不同？交换技术与虚存中使用的调入调出技术有何一致和不同之处？

解覆盖技术与虚拟存储技术的本质不同是：

(1)虚拟存储器对于程序员时透明的，不需要程序员了解程序结构、覆盖的区域、时机，不需要精心的设计程序及其数据结构，所有的操作由操作系统自动完成。

(2)覆盖的程序段的最大长度要受到物理内存容量的限制，而虚拟存储器的最大长度不受物理内存容量的限制，只受计算机地址结构的限制。

交换技术与虚存中使用的调入调出技术一致和不同之处：

(1)主要一致点是都要在内存与外存之间交换信息；

(2)主要区别在于交换技术换出换进一般是整个进程(proc结构和共享正文段除外)，因此一个进程的大小受物理存储器的限制；而虚存中使用的调入调出技术在内存与外存之间来回传递的是存储页或存储段，而不是整个进程，从而使得进程映射具有了更大的灵活性，且允许进程的大小比可用的物理存储空间大的多。

例5.2.7有一计算机系统，内存容量为512K，辅存容量为2G，规律地址形式如下：

段号段内地址2920190

求其虚拟存储器的实际容量？

解虚拟内存的实际大小由系统的规律地址结构、主存辅存容量共同决定。虚拟内存容量的理论值是210*220=1G；最大段内地址为220=1M，远大

84

于内存容量，其段长超过512K的内存容量，故最大实际段长为512k而不是1M。

所以可计算虚拟存储容量为2*512K=2*0.5M=0.5G。0.5G(2)对分段式系统，被共享的程序或数据可作为单独的一段。在物理上它是一段，在不同的进程中，可以对应不同的规律段，相对来说比较易于实现。

(3)对分页管理，则要困难的多。首先，必需保证被共享的程序或数据占有整数块，以便与非共享部分分开。其次，由于共享程序或数据被多个进程访问，所以每个进程对共享程序或数据的访问都应当是有限制条件的。

(4)因此，从共享和保护的实现上来看，须共享的程序段或数据段是一个规律单位，而分段存储管理中被共享的程序或数据作为一个整体（一段）,实现共享和保护就要便利得多。

(5)分段系统的共享是通过两个（或多个）进程的段表之相应表目都指向同一个物理段，并设置共享计数来实现的。每段设置访问方式，就可以实现段的保护。

例5.2.16为什么分段管理下的程序共享和保护比分页管理更有意义？

解主要是由于段是一个有意义的规律整体，如主程序、子程序、数据表格、工作空间等，就如书本上的一章或一个自然段。而页只是一个物理尺寸，不一定有完整的意义，如书本上的一页。程序共享当然希望被共享的对象是一个有意义的整体，如一个子程序；至于程序保护，指的是每个进程都应按所拥有的存取权访问不同的程序，而存取权(R,W,E等)当然对一个有完整意义的对象才更有意义。所以就共享和保护而言，分段管理比分页管理更有意义。

例5.2.17虚存与单、多道程序设计，程序重定位，程序动态链接以及覆盖和交换技术之间有什么关系？

解从原理上讲，单道程序设计系统也可实现虚存管理，但从实际上看，虚存主要是应用在多道程序设计系统中。

虚存的实现需要程序的动态重定位技术的支持，由于程序的对换会导致同一部分程序屡屡进出内存并有可能在内存中不断地移动位置。

虚存与程序的动态链接没有必然的因果关系，但程序的动态链接可以避免无用的程序进入内存，使虚存的效率提高实现；

虚存需要覆盖和交换技术的支持，但覆盖和交换与虚存是不同的概念。在实存管理下覆盖和交换是一种可以节省内存的技术，对用户是不透明，覆盖和交换的区由程序结构和程序员决定。而在虚存下的交换和覆盖对程序员是透明的，操作是由OS根据某种算法决定的。

例5.2.18说明什么是置换算法的异常现象，为什么LRU算法不会有异常现象？

88

解页面置换算法的异常现象，也叫Belady异常，是在局部置换前提下的一种现象。所谓局部置换，指的是当一进程创立时，分给其一定数量的页面（例如8页），然后，在运行过程中，若该进程需调入新页且须置换一个页面时，则只能置换其自己的一个页面而不能置换别的进程的页面。

页面置换的异常现象，是指在一定置换算法和一定页面走向下，分给进程的页面数增多其页面失效率反而增加这样一种状况。这种异常，只在一定的算法和一定的页面走向下才会出现。大量算法，如OPT.和LRU，在任何状况下都不会有异常现象。LRU之所以不会有“异常〞，是由于最近的过去使用的n个页面一定在最近的过去使用的n+1个页面之中。

例5.2.19什么是抖动现象？如何消除这种现象？

解抖动现象，是在虚存管理下，用于页面（在内、外存之间）对换的时间比程序的有效运行时间还要多的这样一种现象。它可以是一进程内部的局部性抖动，也可以是整个系统的全局性抖动。造成这种状况纵然与置换算法和页面走向有关，但其根本原因是多道系统内的进程数太多，从而分给每个进程的页面数太少。因此，解决这一问题的最有效的方法是减少系统内的进程数。Denning于1980年提出了“L=S准则〞，即调整系统内的进程数，使得产生缺页的平均间隔时间（L）等于系统处理进程缺页的平均时间（S）。理论和实践说明，此时的CPU利用率最高。

例5.2.20有这样一种页面置换算法，它给每一个内存块(块与页大小相等)设置一个计数器，以计数曾经装入过该块的页面数。当需要置换一个页面时，该算法总是将其计数值最小的那个块内的页面换掉，当有多个最小值时，按FIFO执行。

若某进程分得4个内存块，现对1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，解答如下问题：

(1)求在上述算法下的页面失效数；(2)求在OPT.算法下的页面失效数。解（1）求解过程如下表所示页面号B1B2B3B4

√√√√√√√√√√√√√1234534167878978954542111155555588888888888222222211111199999999333333666666666555544444477777777744489

C1C2C3C4111122222233333333333401111112222223333333300111111222222222333330001111112222222223333

注：打“√〞的表示缺页，共有13次缺页。

说明：在上面的求解过程中，B1～B4表示进程分得的4个块号，C1～

C4表示与这4块对应的计数器；表中的每一列记录了每一块当前装入的页面及其计数器的值。

（2）在OPT.算法下的页面失效次数为11。

例5.2.20在可变分区分派的存储管理方案中，基于链表的存储分派算法有哪几种？它们的思想是什么？

解：在可变式分区分派的存储管理方案中，基于链表的存储分派算法主要有三种：首次适应算法、循环首次适应算法和最正确适应算法。

（1）首次适应算法

在首次适应算法中，每个空白区按其位置的顺序链在一起，即每个后继的空白区其起始地址总是比前者的大。当系统要分派一个存储块时，就依照空白块链的顺序，一次查询，直到找到第一个满足要求的空白块为止。由这种算法确定的空白块其大小不一定刚好满足要求。假使找到的这个空白区比要求的大，则把它分成两个分区，一个为已分派分区，其大小刚好等于所要求的；另一个依旧为空白块，且留在链中原来的位置上。若是在空白链中从头到尾找一遍，找不到满足要求的空白块，则返回“暂不能分派〞。系统在回收一个分区时，首先检查该分区是否有邻接的空白块，假使有，则应将这个分区与之合并，并将该空白块保存在链中原来的位置。假使回收的分区不和空白块邻接，则应根据其起始地址大小，把它插在链中的相应位置上。

首次适应算法的实质是，尽可能地利用存储器低地址部分的空白块，尽量保存在高地址部分的大空白块。其优点在于：当需要一个较大的分区时，便有希望找到足够大的空白块以满足要求。其缺点是：在回收一个分区时，需要花费较多的时间去查找链表，确定它的位置。

（2）循环首次适应算法

循环首次适应算法与首次适应算法类似，只是在每次分派分区时，系统不是从第一个空白块开始查找，而是从上次分派的空白块处查找。当查找至链尾时，便从链首继续查找，直到找完整个链表。在系统回收一个分区时，为了减少在插入一个空白区时查询链表的时间，假使这个分区不和空白块邻接，则把它插入到前向指针链的最终一个空白块后；假使有空白块相邻，则根据状况作相应处理。由此可见，这些空白块在链中的位置没有一定的规则。

90

这种循环首次适应算法的实质是，使得小的空白块均匀地分布在可用存储空间内。这样，当回收一个分区时，它和一个较大空白块相邻的可能性比较大，因而合并后可得到大的空白块。和首次适应算法相比，它产生过小空白块的现象比较小。

（3）最正确适应算法

在最正确适应算法中，空白块按大小顺序链在一起。系统在寻觅空白块时，总是从最小的一个开始。这样，第一次找到的满足要求的空白块必然是最适合的，由于它最接近于要求的大小。这种算法的优点是：假使存储空间中具有正好是所要求大小的空白块，则必然被选中；假使不存在这样的空白块，也只对比要求稍大的空白块划分，而绝不会去划分一个更大的空白块。此后，遇到有大的存储要求时，就比较简单满足了。

最正确适应算法的缺点在于：寻觅一个较大空白块时花费的时间较长；回收一个分区时，把它插入到空白块链中适合的位置上也较为费时；此外，由于每次都划分一个与要求大小最接近的空白块，使得系统中小的空白块较多。其实质是，在系统中寻觅与要求的空间大小最接近的一个空白块。

例5.2.21在虚拟页式存储系统为什么要引入缺页中断？缺页中断实现由哪几部分组成，并分别说明其实现方法。

解页式虚存管理是在页式存储管理的基础上实现虚拟存储器的，作业在执行时并不是所有的页均放在主存，若欲访问的页面不在主存，则须由操作系统把当前所需页面从辅存装入主存。这一过程就交由中断系统完成，称为缺页中断。

缺页中断由缺页处理和页淘汰组成，缺页处理过程如下：

(1)中断触发：在地址变换过程中，当查询页表时，发现规律页面

不在内存，即其状态位为0，则发生缺页中段。

(2)页面调入：OS在页表中找到对应页面的辅存地址，进行页面的淘汰，将所缺页调入内存；

(3)修改页表：将该页面的内存地址填入页表，修改状态位为1；

缺页中断终止，恢复现场，重新执行指令。

页面淘汰处理如下：

(1)假使内存有空闲的页面，直接调入外存的页面，修改页表；（2）假使内存没有空间，根据页面淘汰算法，在内存中找到可淘汰的页面；

（3）假使被淘汰页面修改位为0，则直接调入外存页面将其覆盖，修改页表；

（4）假使被淘汰页面修改位为1，则要申请一块交换空间，将该内存的内容保存到交换区中，然后将辅存的页面调入其中，修改页表。

91

例5.2.22何谓虚拟机存储器，并举一例说明操作系统如何实现虚拟内存的？

解虚拟存储器通过把主、辅存统一起来管理，给用户造成一种仿佛系统内有巨大主存供用户使用的假象。例如页式存储管理，一道作业被划分成若干页，其中较活跃的几页放在内存，而其余不活跃的页被放在辅存，当需要访问辅存内的页时，就可通过页面调度将其调入内存运行；但用户感觉不到这种变化，他会以为作业的所有部分都存在于主存。这样可以让更多的作业进入主存，提高系统的效率。

例5.2.23在内存管理中，“内零头〞和“外零头〞各指的是什么？在固定式分区分派、可变式分区分派、页式虚拟存储系统、段式虚拟存储系统中，各会存在何种零头？为什么？

解内零头（又称内部碎片）：给一个作业分派的存储单元长度为n，该块存储的作业长度为m，则剩下的长度为（n-m）的空间，成为该单元的内部碎片；若存储单元长度为n，在该系统所采用的调度算法下，较长时间内无法选出一道长度不超过该块的作业，则称该块为外零头（外部碎片）。

在固定式分区分派中两种零头均会存在，由于空间划分是固定的，无论作业长短，存储单元均不会随之变化，若作业短而存储块长则产生内零头，若作业长而存储块短则产生外零头。

在可变式分区分派中只有外零头而无内零头，由于空间划分是依作业长度进行的，是要多少给多少，但剩下的部分太短而无法再分，则称为外零头。

页式虚存中会存在内零头而无外零头，因存储空间与作业均分为等长单元，所以不存在无法分派的单元，但作业长度并不刚好为页面大小的整数倍，因此在最终一页会有剩余空间，即为内零头。

段式虚存中会存在外零头而无内零头，因段式的空间划分类似于可变分区分派，根据段长分派，要多少给多少，但会剩余小空间无法分派，则为外零头。

例5.2.24常用的内存信息保护方法有哪几种？它们各自的特点是什么？

解常用的内存保护方法有硬件法、软件法和软硬件结合保护法三种。界地址保护法，即上下界保护法，是一种常用的硬件保护法。上、下界存储保护技术要求为每个进程设置一对上、下界寄放器。上、下界寄放器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中，在对内存进行访问操作时，首先进行访问地址合法性检查，即检查经过重定位之后的内存地址是否在上、下界寄放器所规定的范围之内。若在规定的范围之内，则访问是合法的，否则是非法的，并产生访问越界中断。

保护键法也是一种常用的软件存储保护法。保护键法为每一个被保护的存储块分派一个单独的保护键。在程序状态字中设置相应的保护键开关字段，对不同的进程赋予不同的开关代码，与被保护的存储块中的保护键匹配。

92

C.提高内存的利用率D.使系统能运行更大的程序

15．（）存储管理中存在页表。

A.页式B.段式C.分区D.段页式

5.3.3判断正误，错误的简要说明理由

1．请求分页存储管理系统，若把页面的大小增加一倍，则缺页中断次数会减少一倍。

2．虚地址即程序执行时所要访问的内存地址。

3．交换可以解决内存不足的问题，因此，交换也实现了虚拟存储器。4．为了使程序在内存中浮动，编程时都使用规律地址。因此，必需在地址转换后才能得到主存的正确地址。

5．在请求分页式存储管理中，页面的调入.调出只能在内存和对换区之间进行。

6．请求分页存储管理中，页面置换算法好多，但只有最正确置换算法能完全避免进程的抖动，因而目前应用最广。其他（如改进型CLOCK）算法虽然也能避免进程的抖动，但其效率一般很低。

7．虚拟存储器的实现是基于程序局部性原理，其实质是借助外存将内存较小的物理地址空间转化为较大的规律地址空间。

8．虚存容量仅受外存容量的限制。

9．UNIX操作系统没有提供虚拟存储器，为了使容量有限的内存能支持较大规模的程序，系统除采用正文段共享和自我覆盖技术外，主要采用了程序对换技术来扩展存储容量，使其具有类似于虚拟存储器的作用。

10．静态页式管理可以实现虚存。11.用可变分区法可以比较有效地消除外部碎片，但不能消除内部碎片。

12．页表的作用是实现规律地址到物理地址的映射。13．系统中内存不足，程序就无法执行。

14．用绝对地址编写的程序不适合多道程序系统。

5.3.4简答题

1．什么是动态链接？用何种内存分派方法可以实现这种链接技术？2．为什么静态重定位后的程序在内存中不能移动？动态地址重定位的程序在内存中可以移动什么？

3．在什么时候只能使用交换的方法，而不能使用覆盖的方法？4．虚拟存储器的理论容量与什么有关，实际容量与什么有关？

5．考虑一个由8个页面，每页1K字节组成的规律空间，把它映射到由32个物理块组成的存储器。问：

103

（1）有效的规律地址有多少位？（2）有效的物理地址有多少位？

6．程序员如何识别系统采用的是分页式虚存还是段式虚存？

7．设某进程分得的内存页面数为m，其需访问的页面个数为p，其中有n个不一致的页面，对于任意置换算法，

（1）求页面失效次数的下限（2）求页面失效次数的上限

8．在某分页虚存系统中，测得CPU和磁盘的利用率如下，试指出每种状况下的问题和措施。

(1)CPU的利用率为15％，盘利用率为95％；(2)CPU的利用率为88％，盘利用率为3％；(3)CPU的利用率为13％，盘利用率为5％。

9．对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO和LRU替换算法的缺页次数。结果说明白什么？

10．存储管理的主要任务是什么？

11．实现虚拟存储器的物质基础是什么？

12．分页存储管理如何战胜分区存储管理的缺点的？13．快表的引入为何能明显改进系统的性能？14．操作系统中存储管理的主要对象是什么？15．覆盖技术的基本思想是什么？

5.35解答题

1．分页存储管理与分段管理的主要区别是什么？提出分页管理和分段管理的目的分别是什么？

2．考虑一个分页存储器，其页表存放在内存。

（1）若内存的存取周期为0.6us，则CPU从内存取一条指令（或一个操作数）需多少时间？

（2）若使用快表且快表的命中率为75％，则内存的平均存取周期为多少？

3．虚存管理与实存管理的根本区别是什么？

4．就虚存回复以下问题：(1)虚存的应用背景是什么？(2)虚存的可行性基础是什么？(3)实现虚存的主要技术是什么？

(4)虚存可以有多大？

5．设某进程访问内存的页面走向序列如下：

1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

104

则在局部置换的前提下，分别求当该进程分得的页面数为1，2，3，4，5，6，7时，以下置换算法的缺页数：

①LRU②FIFO③Optimal

6．考虑一个有快表的请求分页系统，设内存的读写周期为1us,内外存之间传送一个页面的平均时间为5ms，快表的命中率为80%，页面实效率为10％，求内存的有效存取时间。

7．对于一个使用快表的页式虚存，设快表的命中率为70％，内存的存取周期为1us；缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8ms，否则需20ms。假定被置换的页面60％是属于后一种状况，则为了保证有效存取时间不超过2us，问可接受的最大缺页率是多少？

8.为什么要引入动态链接?

9．在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us。假设页表的查询与快表的查询同时进行，当查询页表时，假使该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保存3个页面在内存。现开始执行一作业，系统连续对作业的２、４、5、２、7、6、4、2各页面的数据进行1次存取，如分别采用FIFO算法和最优页面置换算法，求每种算法下存取这些数据需要的总时间？

105

5.4习题解答要点

5.4.1选择最适合的答案

1.B2.B3.A4.A5.A6.B7.C8.A9.B10.B11.D12.D13.C14.C15.B16.C17.D18.D19.B20.C21.A22.D23.D24.B25.D26.B27.C28.C29.C30.D31.C32.A33.B34.A35.D36.A37.B38.D39.D40.C41.D42.B43.A44.B45.A46.C47.B48.D49.B50.A51.D52.C53.A54.B55.B56.C57.D58.B59.D60.B

5.4.2选择所有正确的答案

1.BCD2.ABC3.AE4.ACD4.AC(批处理是C，其它是A)4.AC5.ABCD6.BCD7.ABC8.BD9.ABCD10.BCD11.BCD12.CD13.AD

5.4.3判断正误，错误的简要说明理由

1．错误

产生页面中断的次数与页面大小的关系不是绝对的，它还和访问页面的踪迹P、主存的容量M、以及淘