计算机学科专业基础综合-计算机操作系统内存管理(三)

计算机学科专业基础综合-计算机操作系统内存管理(三)(总分：94.02，做题时间：90分钟)一、{{B}}拔高题{{/B}}(总题数：0，分数：0.00)二、{{B}}单项选择题{{/B}}(总题数：33，分数：33.00)1.测得某个采用按需调页(Demanding-paging)策略的计算机系统部分状态数据为：CPU利用率20%，用于对换空间的硬盘利用率为97.7%，其他设备的利用率为5%。由此断定系统出现异常。此种情况下______能提高利用率。∙A.安装一个更快的硬盘∙B.通过扩大硬盘容量增加对换空间∙C.增加运行进程数∙D.加内存条来增加物理空间容量（分数：1.00）A.B.C.D. √解析：利用率=忙时间/(忙时间空时间)。对换空间的磁盘利用率已达97.7%，说明交换操作非常频繁，故断定物理内存严重短缺。2.在使用交换技术时，如果一个进程正在______时，则不能交换出主存。∙A.创建∙B.I/O操作∙C.处于临界段∙D.死锁（分数：1.00）A.B. √C.D.解析：进程正在进行I/O操作时不能换出主存，否则它的I/O数据区将被新换入的进程占用，导致错误。不过可以在操作系统中开辟I/O缓冲区，将数据从外设输入或将数据输出到外设的I/O活动在系统缓冲区中进行，这时在系统缓冲区与外设进行I/O操作时，进程交换不受限制。3.下列哪些存储分配可能使系统抖动______。Ⅰ．动态分区分配Ⅱ．简单页式分配Ⅲ．虚拟页式Ⅳ．简单段页式Ⅴ．简单段式Ⅵ．虚拟段式∙A.Ⅰ、Ⅱ和Ⅴ∙B.Ⅲ和Ⅳ∙C.只有Ⅲ∙D.Ⅲ和Ⅵ（分数：1.00）A.B.C.D. √解析：要通过对存储分配的理解来推断系统是否会发生抖动，所以本题也需要了解不同的存储分配方案的内容。抖动现象是指刚刚被换出的页很快又要被访问，为此又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上。对换的信息量过大，内存容量不足不是引起系统抖动现象的原因，而选择的置换算法不当才是引起抖动的根本原因。例如，先进先出算法就可能会产生抖动现象。本题中只有虚拟页式和虚拟段式才存在换入/换出的操作，简单页式和简单段式已经全部将程序调入内存，因此不需要置换，也就没有了抖动现象。4.对外存对换区的管理应以______为主要目标。∙A.提高系统吞吐量∙B.提高存储空间的利用率∙C.降低存储费用∙D.提高换入、换出速度（分数：1.00）A.B.C.D. √解析：内存管理是为了提高内存利用率。引入覆盖和交换技术就是为了在较小的内存空间中用重复使用的方法来节省存储空间。覆盖和交换技术付出的代价是，需要消耗更多的处理器时间。它实际上是一种以时间换空间的技术。为此，从节省处理器时间来讲，换入、换出速度越快，付出的时间代价就越小，反之就越大，当时间代价达到一定程度时，覆盖和交换技术就没有意义了。5.下列关于页式存储的说法中，正确的是______。Ⅰ．在页式存储管理中，若关闭TLB，则每访问一条数据都要访问两次内存Ⅱ．页式存储管理不会产生内部碎片Ⅲ．页式存储管理当中的页面是用户可以感知的Ⅳ．页式存储方式可以采用静态重定位∙A.Ⅰ、Ⅱ和Ⅳ∙B.Ⅰ和Ⅳ∙C.Ⅰ∙D.Ⅰ和Ⅲ（分数：1.00）A.B.C. √D.解析：页式存储是内存管理部分最重要的知识点之一。对于页式存储，无论选择题、分析题还是计算题，都比较常见。不仅要知道简单的原理和优缺点，更要深入理解页式存储的各方面特点和具体操作处理过程。关闭了TLB之后，每访问一条数据都要先访问页(内存中)，得到物理地址后，再访问一次内存进行相应操作，Ⅰ正确。凡是分区固定的都会产生内部碎片，而无外部碎片，Ⅱ错误。页式存储管理对于用户是透明的，Ⅲ错误。静态重定位是在程序运行之前，在程序装入内存的过程中完成的，而页式存储管理方式在运行过程中可能改变程序位置，Ⅳ错误。6.在可变式分区分配方案中，某一作业完成后，系统收回其主存空间并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是______。∙A.无上邻空闲区也无下邻空闲区∙B.有上邻空闲区但无下邻空闲区∙C.有下邻空闲区但无上邻空闲区∙D.有上邻空闲区也有下邻空闲区（分数：1.00）A.B.C.D. √解析：A选项的情况下，空闲区数增1。B选项、C选项的情况空闲区数不变。D选项的情况，将上邻空闲区、下邻空闲区和回收区合并为一个空闲区，因此空闲区数减少了一个。7.下面哪种内存管理方法有利于程序的动态链接______。∙A.分段存储管理∙B.分页存储管理∙C.可变式存储管理∙D.固定式存储管理（分数：1.00）A. √B.C.D.解析：动态链接是指在作业运行之前，并不把几个目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段程序时，才将该段(目标程序)调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。8.设内存的分配情况见下表。要申请一块40KB的内存空间，若采用最佳适应算法，则所得到的分区首址为______。{{B}}内存的分配情况{{/B}}地址范围分配情况0～100KB-1占用100～180KB-1180～190KB-1占用190～280KB-1280～330KB-1占用330～390KB-1390～410KB-1占用410～512KB-1∙A.100KB∙B.190KB∙C.330KB∙D.410KB（分数：1.00）A.B.C. √D.解析：若采用最佳适应算法，则所得的分区首址见下表。{{B}}采用最佳适应算法内存的分配情况{{/B}}地址范围分区大小100～180KB-180KB190～280KB-190KB330～390KB-160KB410～512KB-1102KB按照最佳适应算法，330～390KB～1的空闲块被选中，所以所得到的分区首址为330KB。9.采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是______(默认字长为1B)。∙A.16MB∙B.64KB∙C.256B∙D.4GB（分数：1.00）A.B. √C.D.解析：分段地址中的地址结构如下：[*]在该地址中，允许一个作业最长有28个段，每个段的最大长度为216B，即64KB。10.在请求分页存储管理中，若采用FIFO页面淘汰算法，则当可供分配的页帧数增加时，缺页中断的次数______。∙A.减少∙B.增加∙C.无影响∙D.可能增加也可能减少（分数：1.00）A.B.C.D. √解析：减少的例子很明显，访问序列为123412341234，当帧数为3时，缺页数为12；当帧数为4时，缺页数为4。采用FIFO算法时可能出现。Belady现象，也就是增加的情况。所谓Belady现象是指在分页式虚拟存储器管理中，发生缺页时的置换算法采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE(S，N)。当N增大时，PE(S，N)时而增大，时而减小。FIFO是最早出现的页置换算法之一。Belady现象的原因是FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的，因而FIFO并不是一个好的置换算法。举个例子：访问序列为012301401234，当帧数为3时，缺页数为8；当帧数为4时，缺页数为10。这样的序列，可以用程序来生成。下面都是算出来的序列，帧数为3和4。615216196981391021038568838439841041023912342639411.某段表的内容见下表。{{B}}某段表的内容{{/B}}段号段首址/KB段长度(最大长度为64)/KB012040176030248020337020一逻辑地址为0002009AH，它对应的物理地址为______。∙A.120KB2∙B.480KB154∙C.30KB154∙D.480KB2（分数：1.00）A.B. √C.D.解析：由段最大长度可得段内地址的位数为16位，即二进制地址的前16位为段号，后16位为段内地址。相对在16进制地址中，就是前4位为段号，后4位为段内地址，0002对应段号为2，段首址为480KB，009A对应的段内地址为154，所以该逻辑地址对应的物理地址为段首址段内地址，即480KB154。12.在采用请求分页式存储管理的系统中，地址变换过程可能会因为下列______而产生中断。Ⅰ．地址越界Ⅱ．缺页Ⅲ．访问权限错误Ⅳ．存取控制∙A.Ⅰ和Ⅱ∙B.Ⅱ和Ⅲ∙C.Ⅰ、Ⅱ和Ⅲ∙D.Ⅰ、Ⅲ和Ⅳ（分数：1.00）A. √B.C.D.解析：请求分页中的地址变换过程如图所示，所以可能发生的是越界中断和缺页中断。故选择A选项。访问权限错误和存储控制均是文件管理的内容，不可能发生在地址变换过程中。[*]13.设一段表见下表。{{B}}某一段表{{/B}}段号基地址段长度/KB02196001230014290100313275804195296那么逻辑地址(2，88)和(4，100)对应的物理地址分别是______。∙A.90，1952∙B.90，2952∙C.178，2952∙D.178，超过段长而产生越界中断（分数：1.00）A.B.C.D. √解析：逻辑地址(2，88)，段号为2，其对应的基地址为90，段长度为100。检查段内偏移量88＜100,，得到物理地址9088=178。逻辑地址(4，100)，段号为4，其对应基地址为1952，段长度为96。检查段内偏移量100＞96。段内偏移量超过段长，产生越界中断。分段存储管理系统中的地址变换过程如下：1)从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。2)比较段号S和段表长度M，若S≥M，则产生越界中断，否则转向下一步。3)段表中段号S对应的段表项地址=段表起始地址段号S×段表项长度，取出该段表项的前几位得到段长C，后几位得到段的起始地址b。若段内偏移量W≥C，则产生越界中断，否则转至下一步。4)计算E=bW。5)用得到的物理地址E去访问内存。14.静态重定位和动态重定位分别是由______来完成的。Ⅰ．硬件地址变换机构Ⅱ．重定位装配程序∙A.都是Ⅰ∙B.Ⅰ、Ⅱ∙C.Ⅱ、Ⅰ∙D.都是Ⅱ（分数：1.00）A.B.C. √D.解析：静态重定位：在程序装入内存的过程中完成，是指在程序开始运行前，程序中的各个地址有关的项均已完成重定位，地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。2)动态重定位：它不是在程序装入内存时完成的，而是CPU每次访问内存时由动态地址变换机构(硬件)自动进行把相对地址转换为绝对地址。动态重定位需要软件和硬件相互配合完成。15.某系统的空闲分区表见表，采用可变式分区管理策略，现有如下作业序列：96KB、20KB、200KB。若用首次适应算法和最佳适应算法来处理这些作业序列，则______该作业序列请求。{{B}}某系统的空闲分区表{{/B}}分区号大小/K8起始地址/KB132100210150352004218220596530∙A.首次适应算法能满足，最佳适应算法不能满足∙B.首次适应算法不能满足，最佳适应算法能满足∙C.都能满足∙D.都不能满足（分数：1.00）A.B. √C.D.解析：采用首次适应算法时，96KB大小的作业进入4号空闲分区，20KB大小的作业进入1号空闲分区，此时再无空闲分区可以满足200KB大小的作业，所以该作业序列请求无法满足。采用最佳适应算法时，作业序列分别进入5、1、4号空闲分区，可以满足其请求。16.一台裸机需安装Windows7系统，有下面两个版本的操作系统a)Windows_7_ultimate_x86b)Windows_7_ultimate_x64在其他硬件条件都满足的情况下，单纯从内存的角度来看，下列叙述中，正确的是______。∙A.内存超过2GB的裸机适合安装a版本的OS，反之应该装b版本∙B.内存超过2GB的裸机适合安装b版本的OS，反之应该装a版本∙C.内存超过4GB的裸机适合安装a版本的OS，反之应该装b版本∙D.内存超过4GB的裸机适合安装b版本的OS，反之应该装a版本（分数：1.00）A.B.C.D. √解析：Windows7的两个版本中，x86代表32位操作系统，x64代表64位操作系统。单纯从内存的角度来看，32位操作系统的地址空间=232B=4GB，64位操作系统的地址空间=264B[*]4GB。选择安装哪个版本的系统，可以根据其内存是否超过4GB来判断。内存超过4GB的裸机，如果安装32位系统的话，会有一部分内存无法访问到，造成浪费。所以超过内存4GB的裸机适合安装64位的系统，反之应该安装32位的系统。17.设主存容量为lMB，外存容量为400MB，计算机系统的地址寄存器有24位，那么虚存的最大容量是______(默认字长为1B)。∙A.1MB∙B.16MB∙C.17MB∙D.401MB（分数：1.00）A.B. √C.D.解析：当外存容量足够大时，虚拟存储空间只跟地址结构的位数相关的，即虚拟存储空间小于等于内存加上外存容量之和。当外存容量不足时，外存容量便成为虚拟存储空间的一个限制条件，即虚拟存储空间等于内存加上外存容量之和。本题是外存容量足够大的情况，虚拟存储器的最大容量是由计算机的地址结构确定的，其虚拟地址空间=224B=16MB＜401MB(400MB1MB)。18.在请求页式存储管理中，页面的大小与可能产生的缺页中断次数______。∙A.成正相关∙B.成反相关∙C.无关∙D.成固定比例（分数：1.00）A.B. √C.D.解析：页面越大，找到对应数据的机会越大，产生缺页中断的可能性越低，反之产生缺页中断的可能性越高。19.某虚拟存储系统采用LRU页面淘汰算法，假设系统为每个作业分配3个页面物理内存，其中一页用来存放程序，其余两页用于存放数据。现有某作业的部分语句如下：inta[150][100];inti,j;for(i=0;i＜150;i)for(j=0;j＜100;j)a[i][j]=0;设每个页面可存放150个整型变量，变量i、j放在程序页面中，初始时程序和变量在内存，其余两页空闲，数组a按行序存放。最后留在内存中的是数组a的最后______。∙A.2行∙B.2列∙C.3行∙D.3列（分数：1.00）A.B.C. √D.解析：数组a是按行存放，所以最后剩下的也肯定是行，不可能是列。系统用两页存放数据，功能存放150×2=300个整型变量，即能够存放3行数据。20.已知某系统页面长为4KB，页表项为4B，采用多层分页策略映射64位虚拟地址空间。若限定最高层页表占1页，问它可以采用分页策略的层数为______。∙A.5∙B.6∙C.7∙D.8（分数：1.00）A.B. √C.D.解析：由页面长为4KB(即212B)知，页内偏移量占12位。由每一页页表项占4B知，每页可有表项210个，最高层页表的页号占10位。由于最高层页表占1页，也即该页最多存放页表项210个，每项指向一页，每页又存放页表项个数为210，以此类推，最多可采用的分页策略层数为[*]。21.在一分页存储管理系统中，页面大小为4096B，现有一逻辑地址为2F6AH，且第0、1、2页一次存放在物理块5、10、11中，该逻辑地址对应的物理地址为______。∙A.2F6AH∙B.5F6AH∙C.5A6AH∙D.BF6AH（分数：1.00）A.B.C.D. √解析：由题目所给条件可知该页表系统的逻辑地址结构。逻辑地址2F6AH的二进制表示如下：页号P页内位移W0010111101101010由此可知逻辑地址2F6AH的页号为2，该页存放在第11号物理块中，用十六进制表示块号为B，所以该逻辑地址对应的物理地址为BF6AH。注意：在数制使用时，常将各种数制用简码来表示，如十进制数用D表示或省略，二进制用B来表示，十六进制数用H来表示。例如，十制数123表示为123D或者123，二进制数1011表示为1011B，十六进制数3A4表示为3A4H。另外，在编程中十六进制数也用“0x”作为开头。22.下列存储管理方案中，可以采用静态重定位的是______。∙A.固定分区管理方案∙B.可变分区管理方案∙C.页式管理方案∙D.段式管理方案（分数：1.00）A. √B.C.D.解析：在固定分区方式中，作业分区情况一旦确定便不会改变，故可以采用静态重定位。其余3种管理方案均可能在运行过程中改变作业分区情况，故不可以采用静态重定位。23.采用分页存储管理和采用分段存储管理，两者提供给用户的物理地址空间______。∙A.分页存储管理支持更大的物理地址空间∙B.分段存储管理支持更大的物理地址空间∙C.一样大∙D.不能确定（分数：1.00）A.B.C.D. √解析：页表和段表同样存储在内存中，系统给用户的物理地址空间为总的空间大小减去页表或段表的长度。由于页表和段表的长度不能确定，所以提供给用户的物理地址空间大小也不能确定。24.操作系统采用分页存储管理方式，要求______。∙A.每个进程拥有一张页表，且进程的页表驻留在内存中∙B.每个进程拥有一张页表，但只有执行进程的页表驻留在内存中∙C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中∙D.所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中，以最大限度地节省有限的内存空间（分数：1.00）A. √B.C.D.解析：每个进程都有一张属于自己的页表，所以C、D选项排除。在多个进程并发时，所有进程的页表大多数驻留在内存中，在系统中只设置一个页表寄存器(PTR)，在其中存放页表在内存的起始地址和页表的长度。平时，进程未执行时，页表的起始地址和页表长度存放在本进程的PCB中，当调度到某进程时，才将这两个数据装入页表寄存器中。25.以下存储管理方式中，会产生内部碎片的是______。Ⅰ．分段虚拟存储管理Ⅱ．分页虚拟存储管理Ⅲ．段页式分页管理Ⅳ．固定式分区管理∙A.Ⅰ、Ⅱ和Ⅲ∙B.Ⅲ和Ⅳ∙C.只有Ⅱ∙D.Ⅱ、Ⅲ和Ⅳ（分数：1.00）A.B.C.D. √解析：只要是固定的分配就会产生内部碎片，其余的都会产生外部碎片。如果固定和不固定同时存在(如段页式)，物理本质还是固定的，解释如下：分段虚拟存储管理：每一段的长度都不一样(对应不固定)，所以会产生外部碎片。分页虚拟存储管理：每一页的长度都一样(对应固定)，所以会产生内部碎片。段页式分区管理：地址空间首先被分成若干个逻辑分段(这里的分段只是逻辑上的，而我们所说的碎片都是物理上真实存在的，所以是否有碎片还是要看每个段的存储方式，所以页才是物理单位)，每段都有自己的段号，然后再将每个段分成若干个固定的页。所以其仍然是固定分配，会产生内部碎片。固定式分区管理：很明显固定，会产生内部碎片。综上所述，本题选择D选项。注意：凡涉及页的都有内存零头，即段页式管理也存在内存零头。页式其实也是固定式分区的一种形式。26.在页式存储管理中选择页面的大小，需要考虑的因素有______。Ⅰ．页表的大小Ⅱ．内部碎片引起的内存浪费Ⅲ．磁盘访问时间∙A.Ⅰ和Ⅲ∙B.Ⅰ和Ⅱ∙C.Ⅰ、Ⅱ和Ⅲ∙D.Ⅱ和Ⅲ（分数：1.00）A.B. √C.D.解析：选择页面大小是一个需要权衡的问题。较大页面的优点如下：1)页表的大小与页面的大小成反比，较大的页面可以节省实现地址映射所需的存储空间及其他资源。2)较大的页面可使虚拟存储器的实现更加简单。3)在主存和辅存之间传送较大页面比传送小页面更加有效。4)联想存储器(也称快表)的项数有限，对于同样项数的快表，较大页面意味着可高效实现更多存储空间的地址变换，从而减少快表失效的次数。较小页面的优点如下：1)节省存储空间，即减少内存零头(内碎片)。2)节省进程的启动时间，许多进程都比较小，所以采用小页面可以加快进程的调用。27.已知一个虚拟页式存储系统，内存实地址有32位，采用48位虚拟地址，页面大小为4KB，页表项大小为8B，则要采用______级页表，页内偏移为______位。∙A.3，12∙B.3，14∙C.4，12∙D.4，14（分数：1.00）A.B.C. √D.解析：页面大小为4KB，故页内偏移为12位。系统采用48位虚拟地址，故虚页号为(48-12)位=36位。采用多级页表时，最高级页表项不能超出一页大小，每页能容纳页表项数为：4KB/8B=512=29，36/9=4故应采用4级页表，最高级页表项正好占据一页空间，所以本题选择C选项。28.在现代计算机系统中，存储器是十分重要的资源，能否合理有效地使用存储器在很大程度上反映了操作系统的性能，并直接影响到整个计算机系统作用的发挥。可以通过______来提高主存利用率。Ⅰ．将连续分配方式改为离散分配方式Ⅱ．增加对换机制Ⅲ．引入虚拟存储机制Ⅳ．引入存储器共享机制∙A.Ⅰ、Ⅱ和Ⅲ∙B.Ⅰ、Ⅱ和Ⅳ∙C.Ⅱ、Ⅲ和Ⅳ∙D.全是（分数：1.00）A.B.C.D. √解析：Ⅰ对，将连续分配方式改为离散分配方式以减少内存的零头。Ⅱ对，增加对换机制，将那些暂时不能运行的进程或暂不需要的程序或数据换出至外存，以腾出内存来装入运行的程序。Ⅲ对，引入虚拟存储机制，使更多的作业能够装入内存，提高CPU和内存利用率。引入动态链接机制，当程序在运行中需要调用某段程序时才将该程序装入内存，从而避免装入不会用到的程序段和数据。Ⅳ对，引入存储器共享机制，允许一个正文段或数据段被若干程序共享以消除内存中的重复复制现象。29.在分页式存储管理系统中，进程无法访问不属于它的存储空间的原因是______。∙A.该页面不在此进程的页表内∙B.因为会发生缺页中断∙C.因为无法完成地址变换∙D.都错，任何进程任何时候都可以访问全部存储空间（分数：1.00）A. √B.C.D.解析：分页式存储管理系统中的逻辑地址由页号和页内偏移量组成。通过进程的页表才可以查到逻辑地址的页号所对应的物理页号。因为所有页表的内容都是由操作系统控制的，操作系统就有可能限制任一进程，仅让进程访问已经分配给它的页帧。进程根本无法访问不属于它的页面，因为该页面不在此进程的页表内。为了让进程访问不属于它的存储空间，可以在进程页表里增加额外的页表项，这些页表项就指向那些物理空间。30.下列关于虚拟存储器的叙述中，正确的是______。∙A.作业在运行前，必须全部装入内存，且在运行过程中也要一直驻留内存∙B.作业在运行前，不必全部装入内存，且在运行过程中不必一直驻留内存∙C.作业在运行前，不必全部装入内存，且在运行过程中必须一直驻留内存∙D.作业在运行前，必须全部装入内存，且在运行过程中不必一直驻留内存（分数：1.00）A.B. √C.D.解析：基于局部性原理，应用程序在运行之前不必全部装入内存，仅需将当前运行到的那部分程序和数据装入内存便可启动程序的运行，其余部分仍驻留在外存上。当要运行的指令或访问的数据不在内存时，再由操作系统通过请求调入功能将它们调入内存，以使程序能继续运行。如果此时内存已满，则还需通过置换功能，将内存中暂时不用的程序或数据换出到外存上，腾出足够的内存空间后，再将要访问的程序或数据调入内存，使程序继续运行。知识点回顾：对于每个运行作业，只装入当前运行需要的一部分页面集合，该集合称为“工作集”。也就是说，工作集是最近n次内存访问的页面集合，n即为工作集的大小。31.假设一个请求分页系统具有一个平均访问和传输时间为20ms的分页硬盘，为了提高性能，加入了快表，多数活动页表项都可以存在其中。如果页表存放在内存中，内存访问时间是1μs，检索快表的时间为0.2μs，若快表的命中率是80%，未命中快表访问中的50%会导致页错误，则内存的有效存取时间是______。∙A.1001.4μs∙B.1401.6μs∙C.2001.4μs∙D.2401.6μs（分数：1.00）A.B.C. √D.解析：计算过程：(0.21)×80%μs(0.211)×(1-80%)×50%μs(0.21200001)×(1-80%)×(1-50%)μs=2001.4gs故选择C选项。这种题目只需搞清楚分几种访问情况的比例和各自的访问时间即可轻松列出计算式。第一种是直接快表命中的，占总访问数的80%，这种访问只需要访问一次快表，然后直接从内存访问目标页即可，访问时间为(0.21)μs。第二种是快表未命中，但目标页存在于内存中的，这种占总访问数的(1-80%)×50%。这种访问在访问一次快表后未命中，需再访问一次内存中的页表，最后才可访问到内存中的目标页，访问时间为(0.211)μs。第三种是最不理想的一种情况，目标页并不在内存中，所以无论是快表，还是页表都未命中，发生页错误，需要调入内存，这种占总访问数的(1-80%)×(1-500%)，访问时间一次快表，一次页表，页面调入时间，一次从内存访问目标页：(0.21200001)μs。注意：在有快表的分页存储系统中，计算有效存取时间时，需注意访问快表与访问内存的时间关系。通常系统中先访问快表，未命中时再访问内存；在有些系统中，快表与内存的访问同时进行，当快表命中时就停止对内存的访问。这里题目未具体指明，按照前者进行计算。但如果题中有具体的说明，计算时则应注意区别。本题明确给出了快表访问时间，但在有的题目中，对快表的访问时间是忽略不计的，这点考生也要注意一下。32.下列叙述中，错误的是______。∙A.覆盖对程序员是透明的∙B.交换对程序员是透明的∙C.在分页系统环境下，分页对程序员是透明的∙D.联想寄存器的地址变换对操作系统是透明的（分数：1.00）A. √B.C.D.解析：覆盖对程序员是不透明的。为了节省内存，提高覆盖的效果，用户在编制程序时就要安排好程序的覆盖结构，覆盖的目的是希望运行更大的程序。为节省内存，覆盖技术用于一个作业的内部，交换技术则用于不同的作业。交换对程序员是透明的，交换的目的是希望能够运行更多的程序。因此A选项错误，B选项正确。C选项正确，分页的实现是由操作系统自动实现的，因此分页对程序员是透明的。D选项正确，联想寄存器的地址变换是由硬件实施的，不需要通过操作系统软件(指令)实施。但在实施快表的淘汰算法时，要通过操作系统实施。33.释放和合并空闲内存页时，采用下列______方式速度最快。∙A.空闲页位图∙B.空闲页栈∙C.空闲页链表∙D.空闲表（分数：1.00）A. √B.C.D.解析：在位图上很容易判断释放页的上邻和下邻页是否空闲，故合并空闲内存页时只要经过两步或数步的判断。栈和链表都需要遍历才能找到释放页的上邻和下邻页。空闲表也是需要遍历一遍表才能确定释放页的上邻和下邻是否空闲。综上，采用位图管理空闲内存页，在释放和合并空闲内存页时速度是最快的。三、{{B}}综合应用题{{/B}}(总题数：5，分数：61.00)某操作系统采用动态分区存储管理技术。操作系统在低地址占用了100KB的空间，用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为已分配区。在执行以下申请、释放操作序列后：请求300KB、请求100KB、释放300KB、请求150KB、请求50KB、请求90KB，进行以下回答。（分数：12.00）(1).采用首次适应算法时，主存中有哪些空闲分区?画出主存分布图，并指出空闲分区的首地址和大小。（分数：3.00）__________________________________________________________________________________________正确：(采用首次适应算法时，其内存分配过程如图所示。产生的空闲分区有：块1(首地址为390KB，大小为10KB)，块2(首地址为500KB，大小为112KB)。[*])解析：(2).采用最佳适应算法时，主存中有哪些空闲分区?画出主存分布图，并指出空闲分区的首地址和大小。（分数：3.00）__________________________________________________________________________________________正确答案：(采用最佳适应算法时，其内存分配过程如图所示。产生的空闲分区有：块1(首地址为340KB，大小为60KB)，块2(首地址为550KB，大小为62KB)。[*])解析：(3).若随后又要请求80KB，针对上述两种情况会产生什么后果?说明了什么问题?（分数：3.00）__________________________________________________________________________________________正确答案：(若随后又要请求80KB，采用首次适应算法时，由于存在112KB的空闲分区，即块2，则在其中分配空间，这样可以分配。采用最佳适应算法时，由于块1和块2的空间都不够，所以无法分配。说明：首次适应算法的优点在于优先分配低地址部分的空闲分区，保留高地址部分的空闲分区，使得当需要大分区时可以找到。)解析：(4).已知一个采用了LRU置换算法的请求分页存储管理系统中，页面大小为4KB，内存访问速度为100ns/次，快表访问速度为20ns/次，缺页中断处理时间为25ms/次。现有一个长度为30KB的进程P进入系统，分配给P的存储块有3块，进程的所有页面都是在该进程运行中动态装入。若访问快表的命中率为20%，对应于下述页面访问序列：1、4、3、1、2、5、1、4、2、1、4、5请计算12个页面的平均有效访问时间。（分数：3.00）__________________________________________________________________________________________正确答案：(采用LRU置换算法时的页面置换情况见表。{{B}}采用LRU置换算法时的页面置换情况{{/B}}页面走向143125142145按最后访问时间排序，越早排越后143125142145143125142141431251421缺页√√√√√√√√访问这12个页面时，缺页次数为8，缺页率为8/12=2/3。一次内存访问时间t为100ns。一次快表访问时间ε为20ns。快表命中率α为20%。缺页率f为2/3，一次缺页处理时间t1=25ms。有效访问时间用EAT表示EAT=εαt(1-β)[tf(t1εt)(1-f)(εt)]=20ns20%×100ns(1-20%)[100ns2/3(25ms20ns100ns)(1-2/3)(20ns100ns)]≈13333549ns求解方法提示：请求分页管理方式中的有效时间计算法。归纳起来，简化的请求分页访问过程如图所示，其中方框表示的操作都要花费访问时间。[*]1)不考虑命中率和缺页率的有效访问时间计算。从图可以看到，访内操作共有以下三种情况。①访问的页在主存中，且访问页的页表项在快表中(若访问页的页表项在快表中，则一定不会缺页)。EAT=查找快表时间形成物理地址并访问内存数据的时间=εt②访问的页在主存中(不缺页)，且访问页的页表项不在快表中。EAT=查找快表时间查找页表时间修改快表时间形成物理地址并访问内存数据的时间=εtct=2(εt)③访问的页不在内存中(缺页)，设处理缺页中断的时间为t1(产生缺页中断并将该页调入内存，更新快表和页表的时间)。EAT=查找快表时间查找页表时间处理缺页中断的时间t1查找快表时间形成物理地址并访问内存数据时间=εtt1εt=t12(εt)2)考虑命中率和缺页率的有效访问时间计算。从图可以看出，共有3条路径(当产生缺页中断后，页表项会放入快表中)，则：ENT=查找快表时间α×形成物理地址并访问内存数据时间(1-α)×[查找页表时间f×(处理缺页中断的时间t1查找快表时间形成物理地址并访问内存数据时间)(1-f)×(修改快表时间形成物理地址并访问内存数据时间)]=εαt(1-α)[tf(t1εt)(1-f)(εt)]3)处理缺页中断的时间t1的计算。如果题目中没有给出被置换的页面修改和不修改两种情况，则将缺页中断处理时间看成t1。如果题目中给出被置换页面修改和不修改两种情况，前者的概率为β，处理时间为ta，后者处理的时间为tb，则t1=β×ta(1-β)×tb。4)推论。如果题目中没有给出快表等，也就是说，ε=0，α=0，则有效访问时间为：EAT=cf(t1t)(1-f)t如果f等于0，则不存在缺页中断处理，其计算过程同基本分页管理方式。从有效时间的计算可以看到，考生必须牢固掌握请求分页中的访问过程。)解析：某计算机采用段页式虚拟存储器，已知虚拟地址为32位，按字编址，每个段最多可以有1K页，每页为16KB，主存容量为64MB，回答以下问题：（分数：19.02）(1).求虚拟存储器容量。（分数：3.17）__________________________________________________________________________________________正确答案：(虚拟存储器容量=232B=4GB。)解析：(2).给出逻辑地址和物理地址的格式。（分数：3.17）__________________________________________________________________________________________正确答案：(每个段最多可以有1KB=210个页，所以逻辑页号为10页。每页为16KB=214B，所以物理地址为14位。虚拟地址的段号=32-10-14=8位。这样，逻辑地址由8位段号、10位页号和14位页内偏移量组成，逻辑地址的示意图如图所示。[*]主存容量=64MB=226B，所以物理地址为26位，其中页号为12位，页内偏移量为14位，物理地址的示意图如图所示。[*])解析：(3).求一个段表空间开销的最大值，该段对应页表的空间开销为多少?（分数：3.17）__________________________________________________________________________________________正确答案：(段号8位，段表长度=28行，每行指出页表的起始地址(物理地址26位)和有效位等(即需要27位)，取[*]，所以段表所占空间最大值=28×4B。页号10位，每段页表长度=210行，每行指出物理页号(12位)和有效位等(即需要13位)，取[*]，页表所占空间最大值=28×210×2B=219B。)解析：(4).下面三个函数，以不同的空间局部性程度执行相同的操作。请对这些函数就空间局部性进行排序，并解释是如何得到排序结果的。#defineN1000typedefstruct{intvel[3];intacc[3];}point;pointp[N];voidclear1(point*p,intn){inti,j;for(i=0;i＜n;i){for(j=0;j＜3;j)p[i].vel[j]=0;for(j=0;j＜3;j)p[i].acc[j]=0;}}voidclear2(point*p,intn){inti,j;for(i=0;i＜n;i){for(j=0;j＜3;j)p[i].vel[j]=0;p[i].acc[j]=0;}}voidclear3(point*p,intn){inti,j;for(j=0;j＜n;j){for(i=0;i＜3;i)p[i].vel[j]=0;for(i=0;i＜3;i)p[i].acc[j]=0;}}（分数：3.17）__________________________________________________________________________________________正确答案：(解决这个问题的关键在于想象出数组是如何在存储器中排列的，然后分析引用模式。函数clear1以步长1的引用模式访问数组，因此明显地具有最好的空间局部性。函数clear2依次扫描N个结构中的每一个，但是在每个结构中，它以步长不为1的模式跳到下列相对于结构起始位置的偏移处(一个int变量所占的空间为4)：0、12、4、16、8、20。所以，clear2的空间局部性比clear1的要差。函数clear3不仅在每个结构中跳来跳去，而且还从结构跳到结构，所以clear3的空间局部性比clear2和clear1都要差。)解析：(5).在虚拟分页存储管理的系统中，程序员编写了下面这段代码。已知A是一个10000000×1000的稀疏矩阵，非零元素个数为8737953个。S是1000×1000的矩阵(二维数组)，所有元素初始化为0。每个页面可以容纳1024个元素。for(i=0;i＜10000000;i)for(j=0;j＜999;j)if(A[i][j]!=0){for(k=j1;k＜1000;k)if(A[i，k]!=0)S[j,k]=1;}该程序员运行该程序后，发现严重超时，通过代码分析工具得知，A[i][k]!=0耗时异常严重。试解释原因，并写出改进后的代码。（分数：3.17）__________________________________________________________________________________________正确答案：(A是稀疏矩阵，但该稀疏矩阵的实现方式没有给出。从代码分析工具的结果，A[i][k]!=0语句耗时严重，可以推断稀疏矩阵很可能没有按行有序存储，导致同一行的元素不在同一页中。程序员可以重新修改稀疏矩阵的实现，但题目没有给出，无从修改。还有种简单的改进方式就是在取A[i][k]值的时候，不从稀疏矩阵中取值。改进后的代码如下：inttemp[1000];for(i=0;i＜10000000;i){for(j=0;j＜999;j)temp[j]=A[i][j];for(j=0;j＜999;j)if(temp[j]!=0){for(k=j1;k＜1000;k)if(temp[k]!=0)S[j,k]=1;}})解析：(6).某一个计算机系统采用虚拟页式存储管理方式，当前在处理器上执行的某一个进程的页表见下表，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节编址，每页的大小为1024B。{{B}}某一进程的页表{{/B}}逻辑页号存在位引用位修改位页框号01104111132000—310014000—510151)将下列逻辑地址转换为物理地址，写出计算过程，对不能计算的说明其原因。0793，1197，2099，3320，4188，53322)假设程序欲访问第2页，页面置换算法为改进的CLOCK算法，请问该淘汰哪页?页表如何修改?上述地址的转换结果是否改变?变成多少?（分数：3.17）__________________________________________________________________________________________正确答案：(地址转换过程一般是先将逻辑页号取出，然后查找页表，得到页帧号，将页帧号与页内偏移量相加，即可获得物理地址，若取不到页帧号，那么该页不在内存，于是产生缺页中断，开始请求调页。若内存有足够的物理页面，那么可以再分配一个新的页面。若没有页面了，就必须在现有的页面之中找到一个页，将新的页与之置换，这个页可以是系统中的任意一页，也可以是本进程中的一页；若是系统中的一页，则这种置换方式称为全局置换；若是本进程的页面，则称为局部置换。置换时为尽可能地减少缺页中断次数，可以有多种算法来应用，本题使用的是改进的CLOCK算法，这种算法必须使用页表中的引用位和修改位，由这两位组成4种级别，没被引用和没修改的页面最先淘汰，没引用但修改了的页面其次，然后淘汰引用了但是没修改的页面，最后淘汰既引用又修改的页面，当页面的引用位和修改位相同时，随机淘汰一页。1)根据题意，每页1024B，地址又是按字节编址，计算逻辑地址的页号和页内偏移量，合成物理地址见表1。{{B}}表1合成物理地址{{/B}}逻辑地址逻辑页号页内偏移量页帧号物理地址079307934488911971173332452099251缺页中断33203248112724188492缺页中断53325212553322)第2页不在内存，产生缺页中断，根据改进CLOCK算法，第3页为没被引用和没修改的页面，故淘汰。新页面进入，页表修改见表2。{{B}}表2页表修改情况{{/B}}逻辑页号存在位引用位修改位页帧号011041111320→10→10—→1调入31→0001→—淘汰4000—51015因为页面2调入是为了使用，所以页面2的引用位必须改为1。地址转换见表3。{{B}}表3地址转换{{/B}}逻辑地址逻辑页号页内偏移量页帧号物理地址0793079344889119711733324520992511107533203248—缺页中断4188492—缺页中断5332521255332注意：页帧号与页块号是一样的，对应的英文单词是frame，指的是物理页。但页号就不一样了，对应的单词是page，指的是逻辑页。)解析：设一个没有设置快表的虚拟页式存储系统，页面大小为100B。一个仅有460B的程序有下述内存访问序列(下标从0开始)：10、11、104、170、73、309、185、245、246、434、358、364，为该程序分配有两个可用页帧(Pageframe)。（分数：9.00）(1).试叙述缺页中断与一般中断的主要区别。（分数：3.00）__________________________________________________________________________________________正确答案：(缺页中断是一种特殊的中断，它与一般中断的区别是：①在指令执行期间产生和处理中断信号，CPU通常在一条指令执行完后检查是否有中断请求；而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的。②一条指令在执行期间可能产生多次缺页中断。如一条读取数据的多字节指令，指令本身跨越两个页面，若指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。)解析：(2).若分别采用FIFO和LRU算法，试计算访问过程中发生缺页中断的次数。（分数：3.00）__________________________________________________________________________________________正确答案：(每个页面大小为100B，则页面的访问顺序见表1。{{B}}表1页面的访问顺序{{/B}}101110417073309185245246434358364001103122443采用FIFO算法的页面置换情况见表2，共产生缺页中断6次。{{B}}表2采用FIFO算法的页面置换情况{{/B}}走向001103122443块号1001113322443块号20001133224淘汰0132缺页√√√√√√采用LRU算法的页面置换情况见表3，共产生缺页中断7次。{{B}}表3采用LRU算法的页面置换情况{{/B}}走向001103122443块号1001103122443块号20010311224淘汰10312缺页√√√√√√√)解析：(3).若一次访存的时间是10ms，平均缺页中断处理时间为25ms，为使该虚拟存储系统的平均有效访问时间不大于22ms，则可接受的最大缺页中断率是多少?（分数：3.00）__________________________________________________________________________________________正确答案：(设可接受的最大缺页中断率为ρ。若要访问的页面在内存中，一次访问的时间是10ms(访问内存页表)10ms(访问内存)=20ms。如果不在内存，所花时间为：10ms(访问内存页表)25ms(中断处理)10ms(访问内存页表)10ms(访问内存)=55ms。平均有效访问时间：20ms×(1-ρ)55ms×ρ≤22ms，得可接受的最大缺页中断率ρ为5.7%。)解析：已知系统为32位实地址，采用48位虚拟地址，页面大小为4KB，页表项大小为8B，每段最大为4GB。（分数：15.00）(1).假设系统使用纯页式存储，则要采用多少级页表?页内偏移多少位?（分数：3.00）__________________________________________________________________________________________正确答案：(已知页面大小为4KB=212B，即页内偏移量的位数为12。采用48位虚拟地址，故虚页号为48位-12位=36位。页表项的大小为8B，则每页可容纳4KB/8B=512=29项。那么所需多级页表的级数=[*]，故应采用4级页表。)解析：(2).假设系统采用一级页表，TLB命中率为98%，TLB访问时间为10ns，内存访问时间为100ns，并假设当TLB访问失败后才开始访问内存，问平均页面访问时间是多少?（分数：3.00）__________________________________________________________________________________________正确答案：(系统进行页面访问操作时，首先读取页面对应的页表项，有98%的概率可以在TLB中直接读取到(10ns)，然后进行地址变换，访问内存读取页面(100ns)，所需要的时间为10ns100ns=110ns。如TLB未命中(10ns)，则要通过一次内存访问来读取页表项(100ns)，地址变换后，再访问内存(100ns)，因TLB访问失败后才开始访问内存，因此所需时间为10ns100ns100ns=210ns。页面平均访问时间为：[98%×110(1-98%)×210]ns=112ns)解析：(3).如果是二级页表，页面平均访问时间是多少?（分数：3.00）__________________________________________________________________________________________正确答案：(二级页表的情况下，TLB命中的访问时间还是110ns，未命中的访问时间加上一次内存访问时间为210ns100ns=310ns，那么平均访问时间为：[98%×110(1-98%)×3101ns=114ns)解析：(4).