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

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.解：根据所给

3、页面走向，采用 FIFO淘汰算法的页面置换情况如下: 页面走向1 2 1 3 1 2 4 2 1 3 4从上述页面置换图可以看出：页面引用次数为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,用空闲分区管理空闲分区。若分配采用分配空闲区低地址部分的方案，且初始 时用户区的512K空间空闲，对下述申请序列：申请300K,申请100K,释放3

4、00K,申请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)释放 300K(300K，100K)(0，300K)(400K，112K)申请 150K(0，150K)(150K，150K)(300K，100K)(400K，112K)申请 30

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

6、, 112K)空闲块( 0,300K,212K)申请 100K0，300K）400K，112K）（300K，100K）释放 300K（300K，100K）（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，112K）150K，150K）（430K，82K）150K，150K）（470K，42K）210K，90K）(470K, 42K)(2

7、10K, 90K)(400K, 30K)(470K, 42K)(150K 60K)(300K, 100K)(400K, 30K)(430K, 40K)释放30K150K)(150K 60K)(300K, 100K(430K, 40K)解：（1）采用首次适应算法，在完成了题目所给的毓申请及释放内存操作 后，内存分配情况如图5，11,空闲分区表如下所示。0150K180K220K280K300K400K 512K-1150K40K60K100K图5.11采用首次适应算法的内存分配情况分区大起始地址1 30K150K20K280K112400K(2)采用最佳适应算法，完成了题目所给的系列申请及释放内

8、存操作后，内存分配情况如图5.12所示(用阴影表示空闲空间)，空闲分区表如下：0150K150K60K210K300K400K430K470K512K-1100K40K图5.12采用最佳适应算法的内存分配情况分区小大起始地址30K400K142K470K290K210K(3)如再申请空间100K空间，由上述结果可知，采用首次适应算法后剩下的 空闲分区能满足这一申请要求；而采用最佳适应算法后剩下的空闲分区不能满足这 一申请要求。10.有一页式系统，其页表存放在主存中。(1) 如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取 时间是多少？(2) 如果系统加有快表，平均命中率为 85%

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

10、1011，2148, 3000, 4000, 5012转化为相应的物理地 址。页号块号解:面大小为本题中，为了描述方便，设页号为P,页内位移为L，贝W逻辑地址为A,p=int(A/L)w=A mod L对于逻辑地址 1011p=int(1011/1024)=0w=1011 mod 1024=1011查页表第 0 页在第二块，所以物理地址为对于逻辑地址 2148p=int(2148/1024)=2w=2148 mod 1024=100查页表第 2 页在第 1 块，所以物理地址为对于逻辑地址 3000p=int(3000/1024)=2w=3000 mod 1024=928查页表第 2 页在第 1

11、 块, 所以物理地址为对于逻辑地址 4000p=int(4000/1024)=33059。1124。1796。w=4000mod 1024=928查页表第3页在第6块,所以物理地址为7072 对于逻辑地址5012p=i nt(5012/1024)=4w=5012mod1024=916 因页号超过页表长度，该逻辑地址非法。12.在一个请求分页存储管理系统中，一个作业的页面走向为4，3，2，1,4,3,5,4,3,2，1,5,当分配给该作业的物理块数分别为3, 4时，试计算采用下述页面淘汰算法时的缺页率(假设开始执行时主存中没有页面)，并比较所得 结果。(1) 最佳置换淘汰算法(2) 先进先出淘汰

12、算法(3) 最近最久未使用淘汰算法解：(1)根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如 下：块1444442 2块233333 1块32 1555缺页缺缺 缺缺缺缺缺缺页率为：7/12走向432143543215缺页缺页率为:1444446/12由上述结果可以看出，增加分配 给作业 的内存块数可以降低缺页率(2)根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下:走向432143543215缺页块1块2块3缺缺页率为:444111555333444322223321缺 缺缺缺缺 缺9/12块 2333块322块4134444522333311

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

14、，增加分配给作业的内存块数可以降低缺页率.13. 在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096字节, 现有一逻辑地址为2F6AH且第0, 1,2 页依次存放在物理块5, 10 ,11中，问相应 的物理地址为多少？解:由题目所给给条件可知，本页式系统的逻辑地址结构为：逻辑地址2F6AH的二进制表示如下：由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中,用十六进 制表示志号为B,所以物理地址为BF6AH.14. 在虚拟页式存储管理中，为解决抖动问题，可采用工作集模型以决定因素 分给进程的物理块数，有如下页面访问序列：窗口尺寸 =9, 试求 t1,t2 时刻的工作

15、集 .解: 一个进程在时间 t 的工作集可形成化地定义为 :w(t,h)= 在时间 t-h 到 t 之间所访问的一串页面 其中 ,h 为工作集窗口尺寸 .由题目所给条件可知 ,t1 时刻的工作集为 :1,2,3,6,7,8,9t2 时刻的工作集为 :3,415. ( 北京大学 1993年试题)有一距阵 :VAR A:ARRAY1.100,1 .100 OF integer;按先行后列次序存储 .200在一虚存系统中，采用LRU淘汰算法,一个进程有3页内存空间，每页可以存放个整数.其中第一页存放程序 ,且假定程序已在内存 .程序 A:FOR I:=1 TO 100 DOFORj:=1 TO 10

16、0 DOAi,j:0;程序 B:FOR j:=1 TO 100 DOFOR I:=1 TO 100 DOAi,j:=0;分别就程序 A 和 B 的执行过程计算缺页次数 . 分析及相关知识 由于每一进程在内存中有 3 个页面且其中的确良页用于存 放程序,所以可用作存放数据的页面只有 2 个.由题目中的定义可知,数组A中有10000个整数,每页存放200个整数,数组占 用空间50页.假设数据从该作业的第 M页开始存放，则数组分布在第M页到第M+49 页中 . 因数据是按先行后列次序存储 , 它的存储顺序为 :A99,1,A99,2,A99,100,A100,1,A100,2,A100,100A1,

17、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页第M+49页解 : 对于程序 A:由于程序A对矩阵A的访问是按行进行，即按照存储顺序进行因此每次缺页 中断调进一页后 ,位于该页内的数组元素全部赋予 0值,然后再调入下一页 ,所以涉 及的页面走向为M,M+1,M+49，故缺页次数为50次.对于程序B：由于程序B对矩阵A的访问是按列进行,而矩阵A每行有100个数据,每页可 以存放 200个数据,因此每页中有 2个数据属于同一列 ,每次缺页中断调进一页时 , 只有其中的2个数据被赋予0值,即程序B对矩阵A每

18、两次访问会遇到一次缺页所 以波及的页面走向为 :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。试用FIFO和LUO两种算法分别计算出程序访问过程中所发生的缺页。解：在本题中，分配给作业的物理块数为 3（1）根据所给页面走向，使用 FIFO算法时，页面置换情况如下:缺页次数为：9（2）根据所给页面走向，使用LRU算法时，页面置换情况如下:缺页次数为：717.（南开大