存储器管理习题(2)

(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）求解过程如下表所示 页面号 B1 B2 B3 B4

√ √ √ √ √ √ √ √ √ √ √ √ √ 1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2 1 1 1 1 5 5 5 5 5 5 8 8 8 8 8 8 8 8 8 8 8 2 2 2 2 2 2 2 1 1 1 1 1 1 9 9 9 9 9 9 9 9 3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 5 5 5 5 4 4 4 4 4 4 7 7 7 7 7 7 7 7 7 4 4 4 89

C1 C2 C3 C4 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3

注：打“√”的表示缺页，共有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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库存储器管理习题(2)在线全文阅读。