操作系统存储管理综合试题.pdf

《操作系统存储管理综合试题.pdf》由会员分享，可在线阅读，更多相关《操作系统存储管理综合试题.pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、存储管理综合题1 试述缺页中断与一般中断的主要区别。解：缺页中断作为中断，同样需要经历保护CPU 现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU 现场等步骤。但缺页中断又是一种特殊的中断，它与一般中断的主要区别是：（1）在指令执行期间产生和处理中断信号。通常，CPU 都是在一条指令执行完后去检查是否有中断请求到达。若有便去响应中断；否则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的。（2）一条指令在执行期间，可能产生多次缺页中断。例如，对于一条读取数据的多字节指令，指令本身跨越两个页面，假定指令后一部分所在页面和数据所在页面均不在内存

2、，则该指令的执行至少产生两次缺页中断。2 已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给该作业分配2 个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，缺页率又为多少？分析及相关知识 在进行内存访问时，若所访问的页已在主存，则称此次访问成功；若所访问的页不在主存，则称此次访问失败，并产生缺页中断。若程序 P在运行过程中访问页面的总次数为S,其中产生缺页中断的访问次数为F,则其缺页率为：F/s.解：根据所给页面走向，采用FIFO淘汰算

3、法的页面置换情况如下：页面走向 1 2 1 3 1 2 4 2 1 3 4 物理块 1 1 1 3 3 2 2 1 1 4 物理块 2 2 2 1 1 4 4 3 3 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺从上述页面置换图可以看出：页面引用次数为11 次，缺页次数为 9 次，所以缺页率为 9/11。若采用后一种页面淘汰策略，其页面置换情况如下：页面走向 1 2 1 3 1 2 4 2 1 3 4 物理块 1 1 1 3 1 1 1 3 4 物理块 2 2 2 2 4 2 2 2 缺页 缺 缺 缺 缺 缺 缺 缺 缺9某操作系统采用可娈分区分配存储管理方法，用户区为512K且始址为0，用空闲分

4、区管理空闲分区。若分配采用分配空闲区低地址部分的方案，且初始时用户区的 512K空间空闲，对下述申请序列：申请 300K，申请 100K，释放 300K，申请 150K，申请 30K，申请 40K，申请60K，释放 30K 回答下列问题：（1）采用首次适应算法，空闲分区中有哪些空块（给出始址，大小）？（2）采用最佳适应算法，空闲分区中有哪些空块（给出始址，大小）？（3）台再申请 100K，针对（1）和（2）各有什么结果？操作：已分配空间空闲块初始无（0，512K）申请 300K（0，300K）（300K，212K）申请 100K（0，300K）（400K，112K）（300K，100K）释放

5、300K（300K，100K）（0，300K）（400K，112K）申请 150K （0，150K）（150K，150K）（300K，100K）（400K，112K）申请 30K（0，150K）（180K，120K）（150K，30K）（400K，112K）申请 40K（0，150K）（220K，80K）（150K，30K）（400K，112K）（170K，40K）（300K，100）申请 60K（0，150K）（280K，20K）（150K，30K）（400，）（180K，40K）（220K，60K）（300K，100K）释放 30K（0，150K）（150K，30K）（180K，40K）（

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

7、00K，100K）（470K，42K）（400K，30K）（430K，40）申请 60K（0，150K）（210K，90K）（150K，60K）（470，4）（300K，100K）（400K，30K）（430K，40K）释放 30K（0，150K）（210K，90K）（150K，60K）（400K，30K）（300K，100K）（470K，42K）（430K，40K）解：（1）采用首次适应算法，在完成了题目所给的毓申请及释放内存操作后，内存分配情况如图5，11，空闲分区表如下所示。0 150K 180K 220K 280K 300K 400K 512K-1 150K 40K 60K 100K

8、图 5.11 采用首次适应算法的内存分配情况分区大小起始地址1 30K 150K 1 20K 280K 2 112 400K（2）采用最佳适应算法，完成了题目所给的系列申请及释放内存操作后，内存分配情况如图 5.12 所示（用阴影表示空闲空间），空闲分区表如下：0 150K 150K 60K 210K 300K 400K 430K 470K 512K-1 100K 40K 图 5.12 采用最佳适应算法的内存分配情况分区大小起始地址0 30K 400K 1 42K 470K 2 90K 210K(3)如再申请空间 100K空间，由上述结果可知，采用首次适应算法后剩下的空闲分区能满足这一申请要求

9、；而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。10有一页式系统，其页表存放在主存中。（1）如果对主存的一次存取需要1.5 微秒，试问实现一次页面访问的存取时间是多少？（2）如果系统加有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略为 0，试问此时的存取时间为多少？解：若页表存放在主存中，则要实现一次页面访问需要两次访问主存，一次是访问页表，确定所存取页面的物理地址，第二次才根据该地址存取页面数据。（1）由于页表存放在主存，因此CPU 必须两次访问主存才能获得所需数据，所以实现一次页面访问的存取时间是：1.52=3 微秒(2)在系统增加了快表后，在快表中找到页表项的概率

10、为85%，所以实现一次页面的访问的存取时间是0.851.5+(1-0.85)21.5=1.725 微秒11若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，3000，4000，5012转化为相应的物理地址。页号块号0 2 1 3 2 1 3 6 解：本题中，为了描述方便，设页号为P，页内位移为 W，逻辑地址为 A，页面大小为 L，则：p=int(A/L)w=A mod L 对于逻辑地址 1011 p=int(1011/1024)=0 w=1011 mod 1024=1011 查页表第 0 页在第二块，所以物理地址为3059。对于逻辑地址

11、 2148 p=int(2148/1024)=2 w=2148 mod 1024=100 查页表第 2 页在第 1 块，所以物理地址为1124。对于逻辑地址 3000 p=int(3000/1024)=2 w=3000 mod 1024=928 查页表第 2 页在第 1 块,所以物理地址为 1796。对于逻辑地址 4000 p=int(4000/1024)=3 w=4000mod 1024=928 查页表第 3 页在第 6 块,所以物理地址为 7072。对于逻辑地址 5012 p=int(5012/1024)=4 w=5012mod1024=916 因页号超过页表长度，该逻辑地址非法。12在一

12、个请求分页存储管理系统中，一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，当分配给该作业的物理块数分别为3，4 时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。（1）最佳置换淘汰算法（2）先进先出淘汰算法（3）最近最久未使用淘汰算法解：（1）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 4 2 2 块 2 3 3 3 3 3 1 块 3 2 1 5 5 5 缺页缺缺缺 缺缺缺缺缺页率为：7/12 走向 4 3 2 1 4 3 5 4 3 2

13、1 5 块 1 4 4 4 4 4 1 块 2 3 3 3 3 3 块 3 2 2 2 2 块 4 1 5 5 缺页缺缺缺 缺缺缺缺缺页率为：6/12 由上述结果可以看出，增加分配给作业 的内存块数可以降低缺页率（2）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 1 1 1 5 5 5 块 2 3 3 3 4 4 4 3 2 块 3 2 2 2 3 3 2 1 缺页缺缺缺 缺缺缺缺缺页率为：9/12 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 5 5 5 5 1 1 块 2

14、 3 3 3 3 4 4 4 4 5 块 3 2 2 2 2 3 3 3 3 块 4 1 1 1 1 2 2 2 缺页缺缺缺 缺缺缺缺缺页率为：10/12 由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为Belady 现象。(3)根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 1 1 1 5 2 2 2 块 2 3 2 4 4 4 4 1 1 块 3 2 3 2 3 3 3 3 5 缺页缺缺缺 缺缺缺缺缺页率为：10/12 走向 4 3 2 1 4 3 5 4

15、 3 2 1 5 块 1 4 4 4 4 4 4 4 5 块 2 3 3 3 3 3 3 3 块 3 2 2 5 5 1 1 块 4 1 1 2 2 2 缺页 缺 缺 缺 缺 缺 缺 缺 缺缺页率为:8/12 由上述结果可以看出,增加分配给作业的内存块数可以降低缺页率.13.在一分页存储管理系统中,逻辑地址长度为16位,页面大小为 4096字节,现有一逻辑地址为2F6AH,且第 0,1,2页依次存放在物理块5,10,11中,问相应的物理地址为多少?解:由题目所给给条件可知,本页式系统的逻辑地址结构为:逻辑地址 2F6AH的二进制表示如下:由此可知逻辑地址2F6AH的页号为 2,该页存放在第 1

16、1 号物理块中,用十六进制表示志号为 B,所以物理地址为 BF6AH.14.在虚拟页式存储管理中,为解决抖动问题,可采用工作集模型以决定因素分给进程的物理块数,有如下页面访问序列:窗口尺寸 =9,试求 t1,t2时刻的工作集.解:一个进程在时间t 的工作集可形成化地定义为:w(t,h)=在时间 t-h 到 t 之间所访问的一串页面 其中,h 为工作集窗口尺寸.由题目所给条件可知,t1时刻的工作集为:1,2,3,6,7,8,9 t2 时刻的工作集为:3,4 15.(北京大学 1993年试题)有一距阵:VAR A:ARRAY1.100,1.100 OF integer;按先行后列次序存储.在一虚存

17、系统中,采用 LRU淘汰算法,一个进程有 3 页内存空间,每页可以存放200 个整数.其中第一页存放程序,且假定程序已在内存.程序 A:FOR I:=1 TO 100 DO FORj:=1 TO 100 DO Ai,j:0;程序 B:FOR j:=1 TO 100 DO FOR I:=1 TO 100 DO Ai,j:=0;分别就程序 A和 B的执行过程计算缺页次数.分析及相关知识 由于每一进程在内存中有3 个页面且其中的确良页用于存放程序,所以可用作存放数据的页面只有2 个.由题目中的定义可知,数组 A中有 10000个整数,每页存放 200个整数,数组占用空间 50 页.假设数据从该作业的

18、第M页开始存放,则数组分布在第 M页到第 M+49页中.因数据是按先行后列次序存储,它的存储顺序为:A1,1,A1,2,A1,100,A2,1,A2,2,A2,100第 M页A3,1,A3,2,A3,100,A4,1,A4,2,A4,100第 M+1页.A99,1,A99,2,A99,100,A100,1,A100,2,A100,100第 M+49页解:对于程序 A:由于程序 A对矩阵 A的访问是按行进行,即按照存储顺序进行.因此每次缺页中断调进一页后,位于该页内的数组元素全部赋予0 值,然后再调入下一页,所以涉及的页面走向为 M,M+1,M+49,故缺页次数为50 次.对于程序 B:由于程序

19、 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 x 50=5000 次16（中国科学院软件研究所 1999 年试题）在一个请求分页的系统中，假定系统分配给一个作业的物理块数字为3，并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2。试用

20、 FIFO和 LUO两种算法分别计算出程序访问过程中所发生的缺页。解：在本题中，分配给作业的物理块数为3。（1）根据所给页面走向，使用FIFO算法时，页面置换情况如下：缺页次数为：9（2）根据所给页面走向，使用LRU算法时，页面置换情况如下：缺页次数为：7 17（南开大学 1994年试题）在采用页式存储管理的系统中，默作业J 的逻辑地址空间为 4 页（每页 2048 字节），且已知该作业的页面映象表（即页表）如下：试借助地址变换图（即要求画出地址变换图）求出有效逻辑地址4865所对应的物理地址。解：在本题中，一页大小为2048字节，则逻辑得志4865的页号机页内位移:为：页号：4865/2048=2 页内位移 4865-2048x2=769 然后，通过页表查知物理块号为6，将物理块号与逻辑地址中的页内位移拼接，形成物理地址，即：6*2048+769=13057 其地址变换过程如图5。13所示。图 5.13 页式存储管理系统中4865 的地址变换示意图