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

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

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

3、FO淘汰算法的页面置换情况如下：页面走向12131242134从上述页面置换图可以看出：页面引用次数为11次，缺页次数为9次，所以缺页率为9/11。若采用后一种页面淘汰策略，其页面置换情况如下:页面走向12131242134物理块111311134物理块22224222缺页缺缺缺缺缺缺缺缺9.某操作系统采用可娈分区分配存储管理方法，用户区为512K且始址为0,用空闲分区管理空闲分区。若分配采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：申请300K,申请100K,释放300K,申请150K,申请30K,申请40K,申请60K,释放30K回答下列问题：(1)采用

4、首次适应算法，空闲分区中有哪些空块(给出始址，大小)？(2)采用最佳适应算法，空闲分区中有哪些空块(给出始址，大小)？(3)台再申请100K,针对(1)和(2)各有什么结果?操作:已分配空间空闲块300K400K(0,300K)初始512Q申请300K212Q申请100K112K(300K,100K)释放300K(400K,112K)申请150K150K)(300K,100K)申请30K150K)(150K,30K)申请40K150K)(150K,30K)无(0,300K)(0,300K)(300K,100K)(0,(150K,150K)(400K,112口(0,(180K,120K)(400

5、K,112口(0,(220K,80K)(400K,112口(170K,40K)(300K,100)申请60K(0,150K)(150K,30K)(180K,40K)(220K,60K)(300K,100K)释放30K(0,150K)(180K,40K)(300K,100K)采用最佳适应算法时的操作流程：操作：已分配空间初始无512K)申请300K(0,300K)(280K,20K)(400K,112K)(150K,30K)(280K,20K)(400K,112K)空闲块(0,300K212K)申请100K(0,300K)(400K,112K)(300K,100K)释放300K(300K,100

6、K)(400K,112K)申请150K(0,150K)(300K,100K)申请30K(0,150K)(300K,100K)(400K,30K)申请40K(0,150K)(300K,100K)(400K,30K)(430K,40)申请60K(0,150K)(0,300K)(150K,150K)(400K,112口(150K,150K)(430K,82博(150K,150K)(470K,42K)(210K,90K)(470K,42K)(210K,90K(400K,30K)(470K,42K)(150K,60K)(300K,100K)(400K,30K)(430K,40K)释放30K150K)(1

7、50K,60K)(300K,100K)(430K,40K)解：（1）采用首次适应算法，在完成了题目所给的毓申请及释放内存操作后，内存分配情况如图5,11,空闲分区表如下所示。0150K180K220K280K300K400K512K-1150K40K60K100K图5.11采用首次适应算法的内存分配情况分区大小起始地址130K150K120K280K2112400K(2)采用最佳适应算法，完成了题目所给的系列申请及释放内存操作后，内存分配情况如图5.12所示(用阴影表示空闲空间)，空闲分区表如下：0150K150K60K210K100K300K400K40K430K470K512K-1图5.1

8、2采用最佳适应算法的内存分配情况起始地址分区小30K400K42K470K290K210K(3)如再申请空间100K空间，由上述结果可知，采用首次适应算法后剩下的空闲分区能满足这一申请要求；而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。10.有一页式系统，其页表存放在主存中。(1)如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取时间是多少？(2)如果系统加有快表，平均命中率为85%当页表项在快表中时，其查找时间忽略为0,试问此时的存取时间为多少？解：若页表存放在主存中，则要实现一次页面访问需要两次访问主存，一次是访问页表，确定所存取页面的物理地址，第二次才根据该地址存取

9、页面数据。(1)由于页表存放在主存，因此CP3须两次访问主存才能获得所需数据，所以实现一次页面访问的存取时间是：1.5X2=3微秒(2)在系统增加了快表后，在快表中找到页表项的概率为85%所以实现一次页面的访问的存取时间是0.85X1.5+(1-0.85)X2X1.5=1.725微秒11.若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地页号块号解:面大小为本题中，为了描述方便，设页号为P,页内位移为L,则：W逻辑地址为A,页p=int(A/L)w=AmodL对于逻4?地址1011p=int

10、(1011/1024)=0w=1011mod1024=1011查页表第0页在第二块，所以物理地址为3059。对于逻4?地址2148p=int(2148/1024)=2w=2148mod1024=100查页表第2页在第1块，所以物理地址为1124。对于逻4?地址3000p=int(3000/1024)=2w=3000mod1024=928查页表第2页在第1块，所以物理地址为1796。对于逻4?地址4000p=int(4000/1024)=3w=4000mod1024=928查页表第3页在第6块，所以物理地址为7072对于逻4?地址5012p=int(5012/1024)=4w=5012mod10

11、24=916因页号超过页表长度，该逻辑地址非法。12 .在一个请求分页存储管理系统中，一个作业的页面走向为4,3,2,1,4,3,5,4,3,2,1,5,当分配给该作业的物理块数分别为3,4时，试计算采用下述页面淘汰算法时的缺页率(假设开始执行时主存中没有页面)，并比较所得结果。(1)最佳置换淘汰算法(2)先进先出淘汰算法(3)最近最久未使用淘汰算法解：(1)根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下：走向432143543215块14444422块2333331块321555缺页缺缺缺缺缺缺缺缺页率为：7/12走向432143543215块144444块23333块3222块

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

13、时，页面置换情况如下:走向432143543215块14441115缺页缺缺缺缺缺私缺缺页率为：10/12走向432143543215块144444445块23333333块3225511块411222缺页缺缺缺缺缺缺缺缺缺页率为:8/12由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率.13 .在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节,现有一逻辑地址为2F6AH且第0,1,2页依次存放在物理块5,10,11中，问相应的物理地址为多少？解：由题目所给给条件可知，本页式系统的逻辑地址结构为：ri逻辑地址2F6AH的二进制表示如下：由此可知逻辑地址2F6AH的

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

15、LRU匐汰算法，一个进程有3页内存空间，每页可以存放200个整数.其中第一页存放程序，且假定程序已在内存程序A:FORI:=1TO100DOFORj:=1TO100DOAi,j:0;程序B:FORj:=1TO100DOFORI:=1TO100DOAi,j:=0;分别就程序A和B的执行过程计算缺页次数.分析及相关知识由于每一进程在内存中有3个页面且其中的确良页用于存放程序,所以可用作存放数据的页面只有2个.由题目中的定义可知，数组A中有10000个整数，每页存放200个整数，数组占用空间50页.假设数据从Ig作业的第M页开始存放，则数组分布在第M页到第M+49页中.因数据是按先行后列次序存储，它

16、的存储顺序为：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:由于程序B对矩阵A的访问是按列进行，而矩阵A每行有100个数据，每页可以存放200个数据，因此每页中有2个数据属于同

17、一列，每次缺页中断调进一页时，只有其中的2个数据被赋予0值，即程序B对矩阵A每两次访问会遇到一次缺页.所以波及的页面走向为：M,M+1,.,M+49处理1歹UM,M+1,.,M+49处理2歹UM,M+1,.,M+49处理100歹U故缺页次数为：100x50=5000次16 .（中国科学院软件研究所1999年试题）在一个请求分页的系统中，假定系统分配给一个作业的物理块数字为3,并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2。试用FIFO和LUO两种算法分别计算出程序访问过程中所发生的缺页。解：在本题中，分配给作业的物理块数为3（1）根据所给页面走向，使用FIFO算法时，页面置换情况如下:缺页次数为：9（2）根据所给页面走向，使用LRU算法时，页面置换情况如下:缺页次数为：717 .（南开大学1994年试题）在采