计算机操作系统存储器管理复习资料

《计算机操作系统存储器管理复习资料》由会员分享，可在线阅读，更多相关《计算机操作系统存储器管理复习资料（34页珍藏版）》请在装配图网上搜索。

1、第四章 存储器管理第一部分 教材习题（P159）15、在具有快表的段页式存储管理方式中，如何实现地址变换？答：在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若STL，表示未越界，利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表

2、，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍须再三次访问内存。19、虚拟存储器有哪些特征？其中最本质的特征是什么？答：虚拟存储器有以下特征：多次性：一个作业被分成多次调入内存运行，亦即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装

3、入内存即可；以后每当要运行到尚未调入的那部分程序时，再将它调入。多次性是虚拟存储器最重要的特征，任何其他的存储器管理方式都不具有这一特征。因此，认为虚拟存储器是具有多次性特征的存储器系统。对换性：允许在作业的运行过程中进行换进、换出，也即，在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换进）；甚至还允许将暂不运行的进程调至外存，待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。可见，虚拟存储器具有对换性特征。虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出

4、来的最重要特征，也是实现虚拟存储器的最重要的目标。虚拟性是以多次性和对换性为基础的，多次性和对换性又必须建立在离散分配的基础上。所以最本质特征应该是离散性。22、在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？答：在请求分页系统中的每一个页表项如下：页号物理块号状态位P访问字段A修改位M外存地址 l 状态位P：用于指示该页是否已调入内存，供程序访问时参考。l 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页已有多长时间没有被访问，供选择换出页面时参考。l 修改位M：表示该页在调入内存后是否被修改过，由于内存中的每一页都在外存上保留一分副本，因此，若没有被修改，在置换该页时

5、就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数，若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。简言之，M位供置换页面时参考。l 外存地址，用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。26、在一个请求分页系统中，采用 LRU 、FIFO页面置换算法时，如果一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得的结果。答：LRU133213513213221351321132113513215缺缺缺缺缺缺当物理块数为3时，缺页次数

6、为6，缺页率为6/12。 222553133213513213221351321132113513215缺缺缺缺当物理块数为4时，缺页次数为4，缺页率为4/12。FIFO 111132511313333251332132222513225缺缺缺缺缺缺缺缺当物理块数为3时，缺页次数为8，缺页率为8/12。111111111133333313333222222132222555555缺缺缺缺当物理块数为4时,缺页次数为4，缺页率为4/12。1、为什么要配置层次式存储器？2、可采用哪几种方式将程序装入内存？它们分别适用于何种场合？答: 绝对装入方式，在编译时，如果知道程序将驻留在内存的什么位置，那么

7、编译程序将产生绝对地址的目标代码。可重定位装入方式，在多道程序环境下，由于编译程序不能预知所编译的目标模块在内存的什么位置，因此目标模块的起始地址通常从0开始，程序中所有其他地址都相对于起始地址计算。动态运行时装入方式，程序在装入内存中后，允许程序在运行中在内存中移动位置。3、何谓静态链接？何谓装入时动态链接和运行时的动态链接？答: 静态链接:在程序运行之前,先将各目标模块及它们所需的库函数,链接成一个完整的装入模块,以后不再拆开。这种事先进行链接的方式叫静态链接方式。装入时动态链接:用户源程序编译后所得的一组目标模块,在装入内存时,采用边装入边链接的链接方式。运行时的动态链接:对某些目标模块

8、的链接,是在程序执行中需要该目标模块时,才对它进行的链接。4、在进行程序链接时，应完成哪些工作？答：在进行程序链接时，应完成：对相对地址的修改变换外部调用符号5、在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链？答：为了现实对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向的链，如图所示（空闲链结构），为了检索方便，在分区尾部重复设置状态位的分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已没有意义。前向指针N+20后向指针N+20N个字

9、节可用6、为什么要引入动态重定位？如何实现？答：在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。若想把作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。这种通过移动内存中作业的位置，以把原来多全分散的小分区拼接成一个大分区的方法方法，称为“拼接”或“紧凑”见图所示。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程

10、序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位，这也就引入的动态重定位。操作系统用户程序110KB用户程序330KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序680KB（A）紧凑前（B）紧凑后7、在采用首次适应算法回收内存时，可能出现哪几种情况？应怎样处理这些情况？答: 当进程运行完毕释放内时，系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一：l 回收区与插入点的前一个空闲分区F1相邻，见图（a）。此时应将回收区与插入点的前一区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。l

11、 回收区与插入点的后空闲分区F2相邻接，见图（b）。此时也可瘵两分区合并，形成拳的空闲分区，但用回收的首址作为新空闲分区的首址，大小为两者之和。l 回收区同时与插入点的前、后两个分区相邻接，见图(C)。此时将三个分区合并使用F1的首址，取消F2的表项，大小为三者之和。l 回收区既不与F1相邻接，也不与F2相邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。F1回收区F2回收区F1回收区F2ABC8、令buddyk(x)表示大小为2k、地址为x的块的伙伴系统地址，试写出buddyk(x)的通用表达式。9、分区存取管理中常用哪些分配策略？比较它们的

12、优缺点。10、在系统中引入对换后可带来哪些好处？答：引入对换后，可以解决由于内存不足而无法同时容纳多个用户程序的问题，并可以进一步提高内存的利用率。11、为实现对换，系统应具备哪几方面的功能？答:为了现实进程的对换，系统必须能实现三方面的功能：对换空间的主管理，进程的换出，以及进程的换入。12、在以进程为单位进行对换时，每次是否都将整个进程换出？为什么？答：并非要将整个进程换出，换出程序（进程）要换出某个进程时，只能换出那些非共享的程序和数据段。对于共享的程序段和数据段，则须先对每个段的引用计数执行减1操作。若其结果值不为0时，表示仍有进程需要用它，因而不能换出；否则表示该程序段或数据段，已不

13、被其他进程需要，于是可以将它们换出。13、为实现分页存储管理，需要哪些硬件支持？答：为了实现请求分页，系统必须提供一定的硬件支持，除了需要一台具有一定容量的内存及外存的计算机以外，还需要有页表机制、缺页中断机构以及地址变换机构。l 页表机制：作用是将用户地址空间是的逻辑地址变换为内存空间中的物理地址。l 缺页中断机构：在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，它们同样需要经历诸如保护CPU环境，分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。l 地址变换机构：请求分页系统中的地址变换机构，是在分页系统地

14、址机构的基础上，再为实现虚拟存储器而增加了某种功能而形成的，如产生和处理缺页中民，以及从内存中换出一页的功能等。在进行地址变换时，首先去检索快表，试图从中找出所要访问的页，若找到，便修改页表中的访问位，对于写指令还须将修改位置成“1”，然后利用页表中给出的物理号和页内地址，形成页内物理地址。地址变换过程到此结束。14、较详细地说明引入分段存储管理是为了满足用户哪几方面的需要。答：引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：l 方便编程：通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并有自己的名字和长度。因此，在访问的逻辑地址是由段名(段号)和段

15、内偏移量(段内地址)决定的。l 信息共享：要实现对程序和数据的共享时，是发信息的逻辑单位为基础的。比如，共享某个例程和函数。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的意义，不便于实现共享，然而段却是信息的逻辑单位，上此可知，为了现实段的共享，希望存储器管理能与用户程序分段的组织方式相适应。l 信息保护：信息保护同样是对信息的逻辑单位进程保护，分段管理方式能更有效和方便地实现信息保护功能。l 动态增长：在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切知道数据段会增长到多大。前述的其它几种存储管理试，都难以应付这种动态增长的情况，而分段存储管理方式

16、却能较好的解决这一问题。l 动态链接：动态链接是指在作业运行之前，并不把目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段(目标程序)调入内存，并进程链接，可见动态链接也要求以段作为管理的单位。16、为什么说分段系统比分页系统更易于实现信息的共享和保护？答：分段系统允许若干个进程共享一个或多个分段，对段的保护也十分简单易行。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来的方便，可以通过一个例子来说明这个问题：例如：有一个多用户系统，可同时接纳40个用户，它们都执行一个文本编辑程序，如果文本编辑程。序有160KB的代

17、码和加外40KB的数据区，由总共需有8MB的内存空间来个用户。如果160KB的代码是可重入的，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需要的内存空间仅为1760KB(160+40*40)，假定每个页面的大小为4KB，那么160KB的代码将占用40个页面，数据区占10个页面。为实现代码的共享，应在每个进程的页表中都建立40个页表项，它们的物理块号都是21#60#。在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是61#70#，71#80#，81#90#，等等，如A图为分页系统中共享editor的示意图。在分段系统中，

18、实现共享则容易得多，只需要在每个进程的段中为文本编辑程序设置一个段表项。图B是分段系统中共享editor的示意图。进程1页表进程2页表Ed1Ed2Ed40Data1Data10Ed1Ed2Ed40Data1Data1021226071802122607180主存Ed40Data1Data10Data1Data10Ed2Ed1021226061707180A图editorData 1进程1editorData 2进程2段长16040基址8024段表1604080380editorData 1Data 280240280380420B图17、分页和分段存储管理有何区别？答：分页和分段系统有许多相似

19、之处。比如，两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，主要表现在下述的三个方面：l 页是信息的物理单位，分页是为离散实现分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段由是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。l 页的大小固定全由系统决定，由系统把逻辑地址划分产号和怘内的地址两部分，是由机器硬件实现的，因而在 只能有一种大小的页面原则是段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编时，根据信息的性质来划分。l 分页的作业

20、地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；分段的作业地址空间则是二维的，程序员在标识一个地址时，即需给出段名，又需给出段内地址。分页分段信息单位物理单位逻辑单位信息完整性离散分配方式意义相对完整需要系统管理的需要用户的需要页的大小固定，由系统决定不固定，由用户决定地址空间一维二维试述分页系统和分段系统的主要区别。解：分页和分段有许多相似之处，比如两者都不要求作业连续存放。但在概念上两者完全不同，主要表现在以下几个方面：（1）页是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要。段是信息的逻辑单位，它含有一组

21、意义相对完整的信息，分段的目的是为了更好地实现共享，满足用户的需要。（2）页的大小固定且由系统确定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分。（3）分页的作业地址空间是一维的。分段的地址空间是二维的。18、试全面比较连续分配和离散分配方式?答：连续分配是指为一个用户程序分配一个连续的内存空间。又可进一步分为单一连续分配、固定分区分配、动态分区分配和动态重定位分区分配四种方式。连续分区方式可使一个进程分得一个连续的内存空间，这样一来有利于程序的执行，但同时又会产生很多的碎片，浪费大量的系统

22、资源。离散分区是采用段式或页式或段页式的分配方式将一个进程装入一些离散的内存中，这样有利于内存的利用，并且可以方便程序员在更大的空间进行编程工作。20、实现虚拟存储器需要哪些硬件支持？答：主要的硬件支持有：l 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构。l 缺页中断机构，即每当用户程序要访问的页面还没有调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存。l 地址变换机构，它同样是在纯分页地址变换机构的基础上形成的。21、实现虚拟存储器需要哪几个关键技术？答：为实现虚拟存储器，首先需要扩充页表，增加状态位以指出所需页是否在内存，增加外存始址以便

23、调入页面，增加引用位以供置换算法用，增加修改位使得换出时减少写盘次数。另外，还要使用两种关键技术：（1）请求调页技术。指及时将进程所要访问的、不在内存中的页调入内存。该功能是由硬件（缺页中断机构发现缺页）和软件（将所需页调入内存）配合实现的。（2）置换页技术。当内存中已无足够空间用来装入即将调入的页时，为了保证进程能继续运行，系统必须换出内存中的部分页，以腾出足够的空间。具体的置换操作并不复杂，其关键是应将哪些页换出，即采用什么置换算法。23、在请求分页系统中，应从何处将所需页面调入内存？答：在请求分页系统中将页面调入内存大致分为三种：系统拥有足够的对换空间，这时可以全部从对换区调入所需页面，

24、以提高调页速度。系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时就不必换出到对换区，以后再调入，仍从文件区直接调入。对于可能被修改的部分，换出时须换到对换区，以后需要时就须从对换区调入。对UNIX方式，由于系统中允许页面共享，某进程所请求的页面有可能已由其它进程调入内存，此时就无须再从对换区调入。24、在请求分页系统中，常采用哪几种页面置换算法？25、在请求分页系统中，通常采用哪种页面分配方式？为什么？27、实现LRU算法所需的硬件支持是什么？答：LRU算法须要有以下两类硬件支持：l 寄存器：为了记录某进程在内存中各页的使用说明，须为每个在内存中的页面

25、配置一个移位寄存器，可表示为： R=Rn-1Rn-2Rn-3R2R1R0,当进程访问某物理块时，要将相应寄存器的Rn-1位置变成1，此时，定时信号将每隔一定时间将寄存器右移一位。l 栈：可利用一个特殊的栈来保存当前使用的各个页面号，每当进程访问某页面时，便将该页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最久没有使用的页面号，假定现有一进程所访问的页面号序列为：4、7、0、7、1、0、1、2、1、2、6随着进程的访问，栈中页面号的变化情况如下图所示，在访问页面6时发生了缺页，此时页面4是最近最久没有被访问的页，应将它置换出去。44774007477041170

26、4001741107422107411207422107466210728、试说明改进型Clock置换算法的基本原理。29、说明请求分页系统中的缺页中断处理过程。30、如何实现分段共享？答：为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了人共享此分段的每个进程的情况。共享段表如下图所示。其中的各项说明如下：l 共享进程计数count。非共享段仅为一个进程所需要。当进程不再需要该段时，可立即释放该段，并由系统回收该段所有占用的空间。而共享段是为多个进程所需要的，当某进程不再需要而释放它时，系统并不

27、回收该段所占内存，仅当所有共享该段的进程全部都不再需要它时，才由系统回收该段所占内存区。为了记录有多少个进程需要共享该分段，特设置了一个整型变量count.l 存取控制字段。对于一个共享段，应给不同的进程以不同的存取权限。例如，对于文件主，通常允许他读和写，而对其它进程，则可能只允许读，甚至只允许执行。l 段号。对于一个共享段，不同的进程可以各用不同的段号去共享该段。共享段表段名 段长 内存始址 状态外存始址 状态进程名 进程号段号存取控制 共享进程计数count 第二部分 分析计算题1、在一请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、1、1、3、5、1、3、2、

28、1、5，当分配给该作业的物理块数M分别分3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得到的结果。M=3时：11133311311133135535115133132232112155缺 缺 缺 缺 缺 缺页率为：5/11=71.43%M=4时：11133311311133531331511535315255213153212 缺 缺 缺 缺缺页率为：4/11=36.37%比较：利用此算法的好处为，当分配的物理块数足够多时，可以将缺页率降低到每页只一次调入(如M=4的情况)。显然M=4时的缺页率小于M=3时的缺页率，但就内存的使用情况来就，M=3时的内存使用少于M=4时的内存，

29、由此可见利降低缺页率是物理块为牺牲的。2、表4.2给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？分析及相关知识首次适应算法要求空闲分区按地址递增的次序排列，在进行内存分配时，总是从空闲分区表的首部开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。最佳适应算法要求空闲分区按大小递增的次序排列，在进行内存分配时，总是从空闲分区表首开始顺序查

30、找，直到找到第一个能满足其大小要求的空闲分区为止。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲区仍留在空闲区表中。表4.2 空闲分区表分区号大小起始地址（递增）132K100K210K150K35K200K4218K220K596K530K解：（1） 若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大小一致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。为作业序列分配了内存空间后，空闲分区表如

31、表4.3（a）所示。（2） 若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分区还剩下122K；接着申请20K时，选中1号分区，分配后剩下12K；最后申请200K，现有的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进行内存分配，无法满足该作业序列的需求。这时的空闲分区表如表4.3（b）所示。表4.3空闲分区表（a）分区号大小起始地址112K100K(120?)210K150K35K200K418K220K(420?)（b）分区号大小起始地址112K100K210K150K35K200K4122K220K596K530K3、某操作系统采用可变分区分配存储管理

32、方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K回答下列问题：（1） 采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？（2） 采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？（3） 如再申请100K，针对（1）和（2）各有什么结果？分析及相关知识为描述方便起见，本题用“（分区首址，分区长度）”的形式描述系统中的分区。由题中所给条件可知，最初系统中只有一个空闲区，大小为512

33、K，始址为0，即（0，512K）。操作已分配空间空闲块初始无（0，512K）申请300K（0，300K）（300K，212K）申请100K（0，300K）（300K，100K）（400K，112K）释放300K（300K，100K）（0，300K）（400K，112K）申请150K（0，150K）（300K，100K）（150K，150K）（400K，112K）申请30K（0，150K）（150K，30K）（300K，100K）（180K，120K）（400K，112K）申请40K（0，150K）（150K，30K）（180K，40K）（300K，100K）（220K，80K）（400K，11

34、2K）申请60K（0，150K）（150K，30K）（180K，40K）（220K，60K）（300K，100K）（280K，20K）（400K，112K）释放30K（0，150K）（180K，40K）（220K，60K）（300K，100K）（150K，30K）（280K，20K）（400K，112K）采用最佳适应算法时的操作流程：操作已分配空间空闲块初始无（0，512K）申请300K（0，300K）（300K，212K）申请100K（0，300K）（300K，100K）（400K，112K）释放300K（300K，100K）（0，300K）（400K，112K）申请150K（0，150K）

35、（300K，100K）（150K，150K）（400K，112K）申请30K（0，150K）（300K，100K）（400K，30K）（150K，150K）（430K，82K）申请40K（0，150K）（300K，100K）（400K，30K）（430K，40K）（150K，150K）（470K，42K）申请60K（0，150K）（150K，60K）（300K，100K）（400K，30K）（430K，40K）（210K，90K）（470K，42K）释放30K（0，150K）（150K，60K）（300K，100K）（430K，40K）（210K，90K）（400K，30K）（470K，42K

36、）解：（1） 采用首次适应算法，在完成了题目所给的系列申请及释放内存操作后，内存分配情况如图5.11所示（用阴影表示空闲空间），空闲分区表如下所示。400K180K280K150K作业40K作业60K作业100K作业0150K220K300K512K-1图4.11采用首次适应算法的内存分配情况分区大小起始地址01230K20K112150K280K400K（2） 采用最佳适应算法，完成了题目所给的系列申请及释放内存操作后，内存分配情况如图4.12所示（用阴影表示空闲空间），空闲分区表如下：150K作业60K作业100K作业40K作业0150K210K300K400K430K470K512K-1

37、图4.12 采用最佳适应算法的内存分配情况分区大小起始地址01230K42K90K400K470K210K如再申请100K空间，由上述结果可知，采用首次适应算法后剩下的空闲分区能满足这一申请要求；而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。4、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？分析及相关知识在页式存储管理中，用户作业的地址空间被划分成若干大小相等的区域，称为页。相应地，将主存的存储空间也分成与页大小相等的区域，称为块。在为作业分配存储空间时，总是以块为单位来分配，可以将作

38、业中的任意一页放到主存的任意一块中。页式存储管理系统中的逻辑地址结构为：页号P页内位移W它包含两部分，前一部分为页号P，后一部分为页内位移W。解：（1） 本题中，每页2048字节，所以页内位移部分地址需要占据11个二进制位；逻辑地址空间最大为16页，所以页号部分地址需要占据4个二进制位。故逻辑地址至少应为15位。（2） 由于内存共有8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等，因此内存空间为8页*2048字节=16K。5、有一页式系统，其页表存放在主存中。（4） 如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取时间是多少？（5） 如果系统加有快表，平均命中率为85

39、%，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间为多少？解：若页表存放在主存中，则要实现一次页面访问需要两次访问主存，一次是访问页表，确定所存取页面的物理地址，第二次才根据物理地址存取页面数据。（1） 由于页表存放在主存，因此CPU必须两次访问主存才能获得所需数据，所以实现一次页面访问的存取时间是1.52=3微秒（2） 在系统增加了快表后，在快表中找到页表项的概率为85%，所以实现一次页面访问的存取时间为0.851.5+(1-0.85)21.5=1.725微秒6、若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011、2148、3000、

40、4000、5012转化为相应的物理地址。页号块号01232316分析及相关知识在页式存储管理系统中，当进程要访问某个逻辑地址中的数据时，分页地址变换机构自动地将逻辑地址分为页号和页内位移两部分，再以页号为索引去检索页表。在执行检索之前，先将页号与页表长度进行比较，如果页号超过了页表长度，则表示本次所访问的地址已超越进程的地址空间，系统产生地址越界中断。如果页访问合法，则由页表始址和页号计算出相应页表项的位置，从中得到该页的物理块号，并将它装入物理地址寄存器的块号部分。与此同时，再将逻辑地址寄存器中的页内地址直接送入物理地址寄存器的块内地址部分，这样便完成了从逻辑地址到物理地址的变换。解：本题中

41、，为了描述方便，设页号为P，页内位移为W，逻辑地址为A，页面大小为L，则：p=int(A/L)w=A mod L对于逻辑地址1011p=int(1011/1024)=0w=1011 mod 1024=1011查页表第0页在第2块，所以物理地址为2*1024+1011=3059对于逻辑地址2148p=int(2148/1024)=2w=2148 mod 1024=100查页表第2页在第1块，所以物理地址为1124。对于逻辑地址3000p=int(3000/1024)=2w=3000 mod 1024=952查页表第2页在第1块，所以物理地址为1976对于逻辑地址4000p=int(4000/10

42、24)=3w=4000 mod 1024=928查页表第3页在第6块，所以物理地址为7072。对于逻辑地址5012p=int(5012/1024)=4w=5012 mod 1024=916因页号超过页表长度，该逻辑地址非法。7、已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假设现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率为多少？分析及相关知识在进行内存访问时，若所访问的页已在主存，则称此次访问成功；若所访问的页

43、不在主存，则称此次访问失败，并产生缺页中断。若程序P运行过程中访问页面的总次数为s，其中产生缺页中断的访问次数为f，则其缺页率为：f/s。解：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下：页面走向12131242134物理块1（尾）1123122413物理块2（头）12231244134缺页缺缺缺缺缺缺缺缺缺从上述页面置换图可以看出：页面引用次数为11次，缺页次数为9次，所以缺页率为9/11。若采用后一种页面淘汰策略，其页面置换情况如下：页面走向12131242134物理块1（尾）12131242134物理块2(头)1222111222缺页缺缺缺缺缺缺缺缺从上述页面置换图可以看出：

44、页面引用次数为11次，缺页次数为8次，所以缺页率为8/11。8、有一请求分页存储管理系统，页面大小为每页100字节。有一个5050的整型数组按行连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下：int a5050;int i,j;for (i=0;i=49;i+) for (j=0;j=49;j+)aij=0;若在程序执行时内存中只有一个存储块用来存放数组信息，试问该程序执行时将产生多少次缺页中断？解：由题目可知，该数组中有2500个整数，每个整数占用2个字节，共需存储空间5000个字节；而页面大小为每页100字节，数组占用空间50页。假设数据从该作业的第m页开始存放，则数组分布在

45、第m页到第m+49页中，它在主存中的排列顺序为：a00, a01, a049 第m页a10, a11, a149 第m+1页a490,a491,a4949 第m+49页由于该初始化程序是按行进行的，因此每次缺页中断调进一页后，位于该页内的数组元素全部赋予0值，然后再调入下一页，所以涉及的页面走向为m，m+1，m+49，故缺页次数为50次。9、在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。（1） 最佳置换淘汰算法（理论算

46、法）（2） 先进先出淘汰算法FIFO（3） 最近最久未使用淘汰算法LRU解：（1）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：（自己分析！）走向432143543215块1块2块3缺页4缺43缺432缺431缺435缺235缺215缺缺页率为：7/12走向432143543215块1块2块3块4缺页4缺43缺432缺4321缺4325缺1325缺缺页率为：6/12由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。（2）根据所给页面走向，使用先进先出页面淘汰算法时，页面置换情况如下：走向432143543215块1块2块3缺页4缺43缺432缺321缺214缺143缺4

47、35缺352缺521缺缺页率为：9/12走向432143543215块1块2块3块4缺页4缺43缺432缺4321缺3215缺2154缺1543缺5432缺4321缺3215缺缺页率为：10/12由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为Belady现象。（3）根据所给页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况如下：走向432143543215块1块2块3缺页4缺43缺432缺321缺214缺143缺435缺354543432缺321缺215缺缺页率为：10/12走向432143543215块1块2块3块4缺页4缺43缺43

48、2缺4321缺321421431435缺135415435432缺4321缺3215缺缺页率为：8 /12由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。10、在一个请求分页系统中，假定系统分配给一个作业的物理块数为3，并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。解：在本题中，分配给作业的物理块数为3。（1） 根据所给页面走向，使用FIFO算法时，页面置换情况如下：走向232152453252块1块2块3缺页2缺23缺231缺315缺152缺524缺243缺435缺352缺缺页次数为：9

49、（2） 根据所给页面走向，使用LRU算法时，页面置换情况如下：走向232152453252块1块2块3缺页2缺23缺32321缺215缺152524缺245453缺532缺325352缺页次数为：711、在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3、4时，试设计访问过程中所发生的缺页次数和缺页率？比较所得结果。（补充题中有）【解】根据所给页面走向，使用LRU页面置换算法时，页面置换情况如下：走向432143543215块1块2块3缺页4缺43缺432缺321缺214缺143缺435缺3

50、54543432缺321缺215缺缺页率为：10/12走向432143543215块1块2块3块4缺页4缺43缺432缺4321缺321421431435缺135415435432缺4321缺3215缺缺页率为：8 /12由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。12、在动态分区分配方式中,可利用哪些分区分配算法?【解】在动态分区分配算法方式中,可利用首次适应算法循环首次适应算法最佳适应算法13、某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理

51、地址。【解】每页1KB，所以页内位移部分地址需要占据10个二进制位；逻辑地址空间最大为32页，所以页号部分地址需占据5个二进制位，故逻辑地址至少应为15位。虚拟地址 0A5C=0000 1010 1010 1100故物理地址：4*1KB+1001011100=1 0010 0101 1100 =125C虚拟地址 093C=0000 1001 0011 1100故物理地址：4*1KB+0100111100=1 0001 0011 1100=113C14、一个程序P的用户空间为16K,存储管理采用请求式分页系统，每个页面大小为2K，存在以下的页表：页框号有效位121310100211510081其

52、中，有效位1表示页面在内存；0表示页面不在内存。请将虚地址0x060C，0x1502，0x1d71，0x2c27，0x4000转换为物理地址。答：0x060C：1548+12*2048=0x660C0x1502：0x5020x1d71：缺页0x2c27：0x14270x4000：越界15、一个请求式分页存储系统，页表存放在内存：l 访问一次内存需要100nsl 如果仅调入一个页面，需要花费8ms（内存有空页面，或需要进行页面置换，单被置换的页面没有修改过）；l 如果调入一个页面同时需要进行被置换页面的写出，则需要20ms;l 假设页面被修改的比例是60%;请问，缺页率必须控制在多少以下，才能使

53、得EAT200ns?解： 假设缺页率为f_rate,则，EAT=(1-f_rate)*100+f_rate*(40%*8000+60%*20000)如EAT200,则，(1- f_rate)*100+f_rate*(40%*8000+60%*20000)200100-100*f_rate+15200*f_rate200151*f_rate1f_rate1/151即缺页率小于0.66%。16、什么是虚拟存储器？为什么要在存储管理中引入虚拟存储器。答：虚拟存储器由内存和外存组成，使得程序的部分装入内存就能运行的技术，引入的目的有二： 大作业能运行； 提高内存利用率。17、一个分页存储系统，页表存放在内存：l 如果访问一次内存需