第5章：存储管理.doc

第五章一. 单项选择题*1. 在存储管理方案中,_可与覆盖技术配合.A. 页式管理B. 段式管理C. 段页式管理D. 可变分区管理 2. 在存储管理中,采用覆盖与交换技术的目的是_.A. 节省主存空间B. 物理上扩充主存容量C. 提高CPU效率D. 实现主存共享3. 动态重定位技术依赖于_.A. 重定位装入程序B. 重定位寄存器C. 地址机构D. 目标程序4. 虚拟存储器的最大容量_.A. 为内外存容量之和B. 由计算机的地址结构决定C. 是任意的D. 有作业的地址空间决定5. 在虚拟存储系统中,若进程在内存中占三块(开始时为空),采用先进先出也面淘汰算法,当执行访问页号序列为1、2、3、4、1、1、5、1、2、3、4、5、6时，将产生_次缺页中断.A. 7B. 8C. 9D. 106. 设内存的分配情况如图5.7所示.若要申请一块40K字节的内存空间,若采用最佳适应算法,则所得到的分区首址为_.A. 100KB. 190KC. 330KD. 410K 图5.7 内存分配情况7. 很好的解决了零头问题的存储管理方法是_.A. 页式存储管理B. 段式存储管理C. 多重分区管理D. 可变式分区管理8. 系统抖动现象的发生是由_引起的.A. 置换算法选择不当B. 交换的信息量过大C. 内存容量不足D. 请求页式管理方案9. 在可变式分区存储管理中的拼接技术可以_.A. 集中空闲区B. 增加主存容量C. 缩短访问周期D. 加速地址转换10. 分区管理中采用最佳适应分配算法时,宜把空闲区按_次序登记在空闲区表中.A. 长度递增B. 长并递减C. 地址递增D. 地址递减11. 在固定分区分配中,每个分区的大小是_.A. 相同B. 随作业长度变化C. 可以不同但预先固定D. 可以不同但根据作业长度固定12. 实现虚拟存储器的目的是_.A. 实现存储保护B. 实现程序浮动C. 扩充辅存容量D. 扩充主存容量13. 采用段式存储管理的系统中,若地址用24位表示,其中8位表示段号,则允许每段的最大长度是_.A. 224B. 216C. 28D. 23214. 作业在执行中发生了缺页中断,经操作系统处理后,应让其执行_指令.A. 被中断的前一条B. 被中断的C. 被中断的后一条D. 启动时的第一条15. 把作业地址窨中使用的逻辑地址变成内存中物理地址的过程称为_.A. 重定位B. 物理化C. 逻辑化D. 加载16. 首次适应算法的空闲区是_.A. 按地址递增顺序连在一起B. 始端指针表指向最大空闲区C. 按大小递增顺序连在一起D. 寻找从最大空闲区开始17. 在页系统环境下,程序员编制的程序,其地址窨是连续的,分页是由_完成的.A. 程序号B. 编译地址C. 用户D. 系统18. 在请求分页存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加是,缺页中娄的次数_.A. 减少B. 增加C. 玩影响D. 可能增加也可能减少19. 在段页式存储管理系统中,内存等分成_,程序按逻辑模块划分成若干_.A. 块B. 其址C. 分区D. 段E. 页号F. 段长20. 虚拟存储管理系统的基础是程序的_理论.A. 局部性B. 全局性C. 动态性D. 虚拟性21. 下述_页面淘汰算法会产生Belady现象.A. 先进先出B. 最近最少使用C. 最不经常使用D. 最佳22. 某段表的内容如下:一逻辑地址为(2，154),它对应的物理地址为_.A. 120K+2B. 480K+154C. 30K+154D. 2+480K23. 在一个页式存储管理系统中,页表内容如下所示:若页的大小为4K,则地址转换机构将逻辑地址0转换成的手理地址为_.A. 8192B. 4096C. 2048D. 102424. 如果一个程序为多个进程所共享,那么该程序的代码在执行的过程中不能被修改,即程序应该是_.A. 可执行码B. 可重入码C. 可改变码D. 可再现码选择题答案*1. D2. A3. B4. B5. D6. C7. A8. A9. A10. A11. C12. D13. B14. B15. A16. A17. D18. D19. _1,A 2,D20. A21. A22. B23. A24. B二、填空题1. 将作业地址窨中的逻辑地址转换为主存中的热处理地址的过程称为_.2. 分区分配中的存储保护通常采用_方法.3. 在请求页式管理中,页面置换算法常用的是_和_.4. 在页式和段式管理中,指令的地址部分结构形式分别为_和_.5. 段表表目的主要内容包括_.6. 假设某程序的页面访问序列为1、2、3、4、5、2、3、1、2、3、4、5、1、2、3、4且开始执行时主存中没有硬骨头同,则在分配给该程序的物理块数是3且采用FIFO方式时缺页次数是_;在分配给程序的物理块数是4且采用FIFO方式时,缺页次数是_.在分配给该程序的热处理块数是3且用LRU方式时,缺页次数是_.在分配给该程序的物理块数为4且采用LRU方式是,缺页次数是_.7. 把_地址转换为_地址的工作称为地址映射.8. 重定位的方式有_和_两种.9. 分区管理中条用首次适应分配算法时,应将空闲区按_次序登记在空闲区表中.10. 页表表目的主要内容包括_.11. 主存中一系列物理存储单元的集合称为_.12. 静态重定位在_时进行;而动态重定位在_时进行.13. 在虚存管理中,虚拟地址窨是指逻辑地址窨,实地址窨是指_;前者的大小只受_限制,而后者的大小受_.14. 在段式虚拟存储管理中,程序的使用的最大段数以及段的最大长度是由_来决定的.15. 在段页式存储管理系统中,每道程序都有一个_表和一组_表.16. 若选用的_算法不合适,可能会出现抖动现象.17. 在页式存储管理系统中,常用的页面淘汰算法有:_,选择淘汰不再使用或最远的将来才使用的页;_,选择淘汰在主存驻留时间最长的页;_,选择淘汰离当前时刻最近的一段时间内使用的最少的页.18. 对图5.8所示的内存分配情况(其中,阴影部分表示一占用块,空白部分表示空闲块),若要申请30K的存储空间,使首地址最大的分配策略是_.19.在虚拟段式存储管理中,若逻辑地址的段内地址大于段表中该段的段长,则发生_. 答:地址越界中断20.在请求页式存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,_的次数可能增加也可能减少. 答:缺页中断二填空题答案*1 地址交换2 界限寄存器和存储保护键3 先进先出 最近最久未使用4 页号及页内位移 段号及段内位移5 段号、段在内存的起始地址、段长度6 13 14 14 12 7 逻辑 物理8 静态重定位 动态重定位9 地址递增10 页号和块号11 存储空间12 程序装入内存 程序执行13 物理地址空间 机器的地址长度 物理内存大小限制14 逻辑地址结构15 段 页16 页面置换17 最佳算法 先进先出算法 最近最少使用18 最坏适应分配策略19 地址越界中断20 缺页中断21 *88基本题5答案解析题51 试述缺页中断与一般中断的主要区别。解：缺页中断作为中断，同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场等步骤。但缺页中断又是一种特殊的中断，它与一般中断的主要区别是：在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后去检查否有中断请求到达。若有便去响应中断；否则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的。一条指令在执行期间可能产生多次缺页中断。例如，对于一条读取数据的多字节指令，指令本身跨越两个页面，假定指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。2 已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有种淘汰算法，该算法淘汰页面的策略为当需要淘汰页时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率又为多少？解：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下：从上述页面置换图可以看出：页面引用次数为11次，缺页次为9次，所以所以缺页率为9/11。若采用后一种页面淘汰策略，其页面置换情况如下：从上述页面置换图可以看出：页面引用次数为11次，缺页次数为8次，所以缺页率为8/11。3 表5。2给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？解：若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大小一致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。为作业序列分配了内存空间后，空亲分区表如表5。3（a）所示。若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分区还剩下122K；接着申请20K，选中1号分区，分配后剩下12K；最后申请200K，现在足该作业序列的需求。这时空闲分区表如表5。3(b)所示。表5。3 分配后的空闲分区表4 在某系统中，采用固定分区分配管理方式，内存分区（单位字节）情况如图5。9所示。现在大小1K、9K、33K、121K的个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费有多大？解：从图5。9可以看出，该系统中共有四个分区，第一分区的大小为8K，第二分区的大小为32K，第三分区的大小为120K，第四分区的大小为332K。作业进入系统后的内存分配情况，如图5。10所示（每个分区中未被利用的那部分空间用阴影表示）；图5。9 某系统内存分区情况图5。10 作业进入系统后的分配情况从图5。10可以看出，作业进入系统后，第一分区剩余空间为7K，第二分区剩余空间为23K，第三分区剩余空间为87K，第四分区剩余空间为211K。主存空间浪费328K。5 有一请求分页存储管理系统，页面大小为每页100字节。有一个50*50的整型数组按行连续存放，每个整数占两个字节，将数组初始化为0的程序描述如下：int a5050;int I,j;for (I=0;I=49;I+) for (I=0;j=49;j+)aIj=0;若在程序执行时内存中只有一个存储块用来存放数组信息，试问该程序执行时产生多少次缺页中断？解：由题目可知，该数组中有2500个整数，每个整数占用2个字节，共需存储空间5000个字节；而页面大小为每页100字节，数组占用空间50页。假设数据从该作业的第m页开始存放，则数组分布在第m页到第m+49页中，它在主存中的排列顺序为：a00,a01,.,a049 第m页a10,a11,.,a149 第m+1页a490,a491,.a4949 第m+49页由于该初始化程序是按行进入的，因此每次缺页中断调进一页后，位于该页内的数组无素全部赋予0值，然后再调入下一页，所以涉及的页面走向为m,m+1,.,m+49,故缺页次数为50次。6 试述分页系统和分段系统的主要区别。解：分页和分段有许多相似之处，比如两者都不要求作业连续存放。但在概念上两者完全不同，主要表现在以下几个方式：页是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要。段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地实现共享，满足用户的需要。页的大小固定且由系统确定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分。分页的作业地址空间是一维的。分段的地址空间是二维的。7 设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间多少大？解：本题中，每页2048字节，所以页内伴移部分地址需要占据11个二进制位；逻辑地址空间最大为16页，所以页号部分地址需要占据4个二进制位。故逻辑地址至少应为15位。由于内存共有8个存储块，在页式存储管理系统中，存储块大小与页面的大小相等，因些内存空间为16K。8：在一个段式存储管理系统中，其段表为：试求下述逻辑地址对应的物理地址是什么？解：（1）由于第0段的内存始址为210，段长为500，故逻辑地址0。430是合法地址。逻辑地址0。430对应的物理地址为210+430=640。（2）由于第1段的内存始址为2350，段长为20，故逻辑地址1。10是合法地址。逻辑地址1。10对应的物理地址为2350+10=2360。（3）由于第2段起始地址为100，段长为90，所给逻辑地址2。500非法。（4）由于第3段的内存始址为1350，段长为590，故逻辑地址3，400是合法地址。逻辑地址3，400对应的物理地址为1350+400=1750。（5）由于第4段的内存始址为1938，段长为95，所给逻辑地址4，112非法。（6）由于系统中不存在第5段，所给逻辑地址5，32非法。9，某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。 若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请1500K，申请30K，申请40K，申请60K，释放30K回答下列问题：（1） 采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？（2） 采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？（3） 如再申请100K，针对（1）和（2）各有什么结果？解：（1）采用首次适应算法，在完成了题目所给的系列申请及释放内存操作后，内存分配情况如图5。11所示（用阴影表示空闲空间），空闲分区表如下所示。图5。11 采用首次适应算法的内存分配情况（2）采用最佳适应算法，完成了题目所给的系列申请及释放内存操作后，内存分配情况如图5。12所示（用阴影表示空闲空间），空闲分区表如下：图5012 采用最佳适应算法的内存分配情况（3）再申请100K空间，由上述结果可知，采用首次适应算法后剩下的空闲分区能满足这一申请要求；而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。10有一页式系统，其页表存放在主存中。（1） 如果对主存的一次存取需要1。5微秒，试问实现一次页面访问的存取时间是多少？（2） 如果系统加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为0，试问此时的存取时间为多少？解：若页表存放在主存中，则要实现一次页面访问需两次访问主存，一次是访问页表，确定所存取页面的物理地址，第二次才根据该地址存取页面数据。（1） 由于页表存放在主存，因此CPU必须两次访问主存才能获得所需数据，所以实现一次页面访问的存取时间是1。5*2=3微秒（2） 在系统增加了快表后，在快表中找到页表项的概率为85%，所以实现一次页面访问的存取时间为0。85*1。5+（1-0。85）*2*1。5=1。725微秒11若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，3000，4000，5012转化为相应的物理地址。解：本题中，为了描述方便，设页号为P，页内位移为W，逻辑地址为A，页面大小为L，则：P=int(A/L)W=A mod L对于逻辑地址1011P=int(1011/1024)=0W=1011 mod 1024=1011查页表第0页在第2块，所以物理地址为3059。对于逻辑地址2148P=int(2048/1024)=2W=2148 mod 1024=100查页表第2页在第1块，所以物理地址为1124对于逻辑地址3000P=(3000/1024)=2W=3000 mod 1024=952查页表第2页在第1块，所以物理地址为1976对于逻辑地址4000P=(4000/1024)=3W=4000 mod 1024=928查页表第3页在第6块，所以物理地址为7072对于逻辑地址5012P=(5012/1024)=4W=5012 mod 1024=916因页号超过页表长度，该逻辑地址非法。12在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块娄分别为3、4时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。（1） 最佳置换淘汰算法（2） 先进先出淘汰算法（3） 最近最久未使用淘汰算法解：（1）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下缺页率为：7/12缺页率为：6/12由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。（3） 根据所给页面走向，使用先进先出页面淘汰算法时，页面置换情况如下： 缺页率为：9/12缺页率为：10/12由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为Belady现象。（4） 根据给页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况如下：缺页率为：8/12由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。13在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？解：由题目所给条件可知，本页式系统的逻辑地址结构为：逻辑地址2F6AH的二进制表示如下：由此可知逻辑地址2F6AH的页号为2，该页存放在第11号物理块中，用十六进制表示块号为B，所以物理地址为BF6AH14在虚拟页式存储管理中，为解决抖动问题，可采用工作集模型以决定分给进程的物理块数，有如下页面访问序列：窗口尺寸=9试求t1、t2时刻的工作集；解：一个进程在时间t的工作集可形式化地定义为：W（t,h）=在时间t-h到t之间所访问的一串页面其中，h为工作集窗口尺寸。由题目所给条件可知，t1时刻的工作集为：1，2，3，6，7，8，9t2时刻的工作集为：3，415（北京大学1993年试题）有一矩阵：VAR A:ARRAY1.100,1.100OF integer;按先行后列次序存储。在一虚存系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数。其中第1页存放程序，且假定程序已在内存。程序A：FORI:=1 TO 100 DO FORJ:=1 TO 100 DO AI,J:=0;程序B：FORj:=1 TO 100 DO FORi:=1 TO 100 DO AI,J:=0;分别就程序A和B的执行过程计算缺页次数。解：对于程序A：由于程序A对矩阵A的访问是按行进行，即按照存储顺序进行。因此每次缺页中断调进一页后，位于该页内的数组元素全部赋予0值，然后再调入下一页，所以涉及的页面走向为m,m+1,.,m+49,故缺页次数为50次。对于程序B：由于程序B对矩阵A的访问是按列进行，而矩阵A每行有100个数据，每页可以存放200个数据，因此每页中有2个数据属于同一列，每次缺页中断调进一页时，只有其中的2个数据被赋予0值，即程序B对矩阵A每两次访问会遇到一次缺页。所涉及的页面走向为：m,m+1,.,m+49 处理1列m,m+1,.,m+49 处理2列m,m+1,.,m+49 处理100列故缺页次数为：100*50=5000次16（中国科学院软件研究所1999年试题）在一个请求分页系统中，假定系统分配分一个作业的物理块数为3，并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2。试用FIFO和LRU两种算法分别计算出程序访问进程中所发生的缺页次数。解：在本题中，分配给作业的物理块数为3。（1） 根据所给页面走向，使用FIFO算法时，页面置换情况如：缺页次数为：9（2） 根据所给页面走向，使用LRU算法时，页面置换情况如下：缺页次数为：717（南开大学1994年试题）在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映象表（即页表）如下：试借助地址变换图（即要求画出地址变换图）求出有效逻辑地址4868所对应的物理地址。解：在本题中，一页大小为2048字节，则逻辑地址4865的页号及内位移为：页号 4865/2048=2页内位移 4865-2048*2=769然后，通过页表查知物理块号为6，将物理块号与逻辑地址中的页内位移拼接，形成物理地址，即：6*2048+769=13057其地址变换过程如图5。13所示图5。13 页式存储管理系统中4865的地址变换示意图18.某系统采用动态分区方式管理内存，内存空间为640K，高端40K用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K，请分别画图表示首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。作业：1、已知某分页系统，主存容量为64K，页面大小为1K，对于一个4页大的作业，其0，1，2，3页分别被分配到主存的2、4、6、7块中。（1） 将十进制的逻辑地址1023、2500、3500、4500转换成物理地址；（2） 以十进制的逻辑地址1023为例画出地址变换的过程图。2、对于下表所示的段表，请将逻辑地址（0，137）、（1，4000），（2，3600），（5，230）转换成物理地址。段号基址段长050K10K160K3K270K5K3120K8K4150K4K补充题目：在一采用局部置换策略的请求分页系统中，分配给某个作业的内存块数为4，其中存放的四个页面的情况如下表：物理块虚页号装入时间最后一次访问时间访问位修改为0260157011116016110202615800332016311上面的所有数字均为10进制，所有时间是从进程开始运行时从0开始计数的时钟数。请问，如果采用下列置换算法，将选择哪一页进行换出？（1）FIFO算法；（2）LRU算法（3）改进的Clock算法。