《操作系统练习.docx》由会员分享,可在线阅读,更多相关《操作系统练习.docx(10页珍藏版)》请在金锄头文库上搜索。
1、 存储管理综合题分析 1、在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的指令地址序列为:110,215,128,86,456,119,301,445,266,337。单位(字)若该作业的第0页已经装入内存,现分配给该作业的主存共300字,页的大小为100字,请回答下列问题。 a按FIFO调度算法将产生多少次缺页中断?缺页中断率为多少? b按LRU调度算法将产生多少次缺页中断?缺页中断率为多少?【答案】 采用FIFO调度算法时,缺页中断率为4/10 = 40%;采用LRU调度算法时,缺页中断率为5/10 = 50%。 【分析】本题给出的是具体的逻辑地址,要求根据页面大小写出虚页
2、号,从而得出页面踪迹。计算时注意起始地址,假设逻辑地址从0开始,页面大小为100字,可以求得页面走向的虚页号分别为:1,2,1,0,4,1,3,4,2,3。根据题意,0页已经调入内存,分配的内存为300字,每页100字,则分配给该进程的是3个页框,那么,采用FIFO调度算法时,其页面置换如下表所示虚页号 1 2 1 0 4 1 3 4 2 3 A 1 2 2 2 4 4 3 3 3 3 B 0 1 1 1 2 2 4 4 4 4 C000112222缺页 Y Y N N Y N Y N N N 共缺页4次。 当采用LRU调度算法时,其页面置换如下表所示。虚页号 1 2 1 0 4 1 3 4
3、2 3 A 1 2 1 0 4 1 3 4 2 3 B 0 1 2 1 0 4 1 3 4 2 C002104132缺页 Y Y N N Y N Y N Y N 共缺页5次。2、在某个请求分页管理系统中,假设某进程的页表内容如下表所示。页号 页框(Page Frame)号 有效位(存在位) 0 120H 1 1 - 0 2 850H 1 页面大小为4KB,一次内存的访问时间是200ns,一次快表(TLB)的访问时间是20ns,处理一次缺页的平均时间为109ns(己含更新TLB和页表的时间),进程的驻留集大小固定为二页,采用最近最久未使用置换算法(LRU)和局部置换策略。假设TLB初始为空;地址
4、转换时先访问TLB,若TLB未命中,再访问页表(忽略访问页表之后的TLB更新时间);有效位为0表示页面不在内存,产生缺页中断,缺页中断处理后,返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2345H、1876H、258FH,请问: a依次访问上述三个虚地址,各需多少时间?给出计算过程。 b基于上述访问序列,虚地址1876H的物理地址是多少?请说明理由。【答案】 (a) 根据页式管理的工作原理,应先将页号和页内位移地址分解出来。页面大小为4KB,即212,则得到页内偏移量占虚地址的低12位,那么页号占剩余高4位。可得三个虚地址的页号如下表。(b) 地址 页号 页内位移 2345H 2 3
5、45H 1876H 1 876H 258FH 2 58FH 2345H指令,页号为2,访问快表20ns,找不到页框,因条件所给初始为空,需要再到内存访问页表,花费200ns得到页框号,合成物理地址后去主存取指令需要花费200ns。 总时间 20ns + 200ns + 200ns = 420ns。 1876H指令页号为1,访问快表20ns,不在TLB,访问页表200ns,不在内存,发生缺页中断花费109ns,取得新页框号(含TLB更新),合成物理地址后去主存取指令需要花费200ns。 总时间 20ns + 200ns + 109ns + 200ns 109ns。 258FH指令,页号为2,访问
6、快表,因第一次访问己将该页号放入快表,因此花费20ns便可合成物理地址,访问主存取指200ns,共计20ns + 200ns = 220ns。 (b)当访问虚地址1876H时,因不在内存而产生缺页中断,因驻留集为二页,现在已有0页和2页在内存,必须从中淘汰一个页面,从而将新1页调入内存。 根据LRU置换算法,0页和2页除有效位以外的其它信息未知,但是,第2页刚刚访问过,其引用位应刚置为1且时间间隔不长,根据最近最久未使用置换算法,相比之下应首先淘汰0号页面,因此1876H的对应页框号为120H。由此可得1876H的物理地址为120876H。 3、某虚拟存储器的用户地址空间为32个页面,每页1K
7、,主存有16K。假定某时刻操作系统为用户的第0,1,2,3页分配的物理页面为5,10,4,7,见下表,而该用户的作业长度为6页,试将十六进制虚拟地址0A5C,103C,1A5C,转换成物理地址,并分析转换过程中可能发生的现象。 0 5 1 10 2 4 3 7 【答案】 由于用户地址为32X1K = 32K大小,主存有16K,显然只能部分装入。页面和页框的大小为1K,故, 地址0A5C(Hex) = 0000101001011100 = 000010 1001011100(bin) 其中,前6位为页号,后10位为页内地址,页号为 000010(bin)= 2(Hex) 查表,对应页框号为 4(
8、Hex)= 000100(bin) 那么,000100 1001011100 = 0001001001011100(bin)= 125C(Hex)物理地址 同理103C(Hex) = 000100 0000111100(bin) 其中,页号为 0000100(bin)= 4(Hex) 6页(06已经7页了),因此产生越界中断。 【分析】内存地址转换是本章中经常会出现的题目,同学注意找出逻辑地址和物理地址的对应关系,逻辑地址的长度和物理地址的长度。例3.10已经说明了,逻辑地址(虚拟地址)可以少于物理地址,也可以大于物理地址,在例3.10的分析里已经说明。通常,逻辑地址会大于物理地址,因此,大部
9、分逻辑地址的位数会大于物理地址,此时就需要页表来进行映射了。因是多对少,因此必然会有对应不上的(即不在内存的),甚至会有超出范围越界的(如本题第三问)。又由于有时页面的分配是非16位进制,因此还需要展开为2进制来进行分析。4、设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(Page Frame)。在时刻260前的该进程访问情况如下表所示(访问位即使用位)。页号 页框号 装入时间 访问位 0 7 130 1 1 4 230 1 2 2 200 1 3 9 160
10、1 当该进程执行到时刻260时,要访问的逻辑地址为17CAH的数据,请回答下列问题: (1)该逻辑地址对应的页号是多少? (2)若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。 (3)若采用时钟(CLOCK)置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针沿顺时针方向移动,且当前指向2号页框,示意图如下)【答案】本题涉及操作系统中内存管理的页面置换算法 (1)该页的页号为5。 (2)物理地址为1FCAH。 (3)物理地址为0BCAH。 【分析】 (1)17CAH=0001011111001010B。页的大小为1KB,那么,取
11、低10位为页内偏移量为1111001010B,高6位为页号000101=5H,所以,该页的页号为5。 (2)由于该页不在内存,因此需要进行页面置换,按FIFO算法,0页面(7页框)进入内存最早,故淘汰,将5页装入该页,那么物理地址为(7页框)000111B合成1111001010B为0001111111001010B=1FCAH。 (3)由于该页不在内存,因此需要进行页面置换,按Clock算法,2页面(2页框)被选中,故淘汰,将5页装入该页,那么物理地址为(2页框)000010B合成1111001010B为0000101111001010B=0BCAH。 【知识链接】页面置换算法也是考试的重点
12、,考生应注意掌握FIFO,LRU,OPT以及CLOCK算法的基本点。计算过程要细心。传统的FIFO,LRU,OPT可以用堆栈表来计算(考生可以参阅相关知识点),CLOCK算法因为循环的关系需要逐步推导。本题中加入的地址转换计算并不复杂,页面字长的分割要细心,转换到十六进制时注意位数的合理性,缺的要补全。 操作系统,死锁,银行家算法习题进程已分配需要可分配P00,0,3,20,0,1,21,6,2,2P11,0,0,01,7,5,0P21,3,5,42,3,5,6P30,3,3,20,6,5,2P40,0,1,40,6,5,6试问:(1)该状态是否安全?(2)如果进程P2 提出请求Request
13、2(1,2,2,2)后,系统能否将资源分配给它?解: (1)利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况进程可分配需要已分配运行结束剩余结果P01,6,2,20,0,1,20,0,3,21,6,5,4安全P11,6,5,40,6,5,20,3,3,21,9,8,6安全P21,9,8,60,6,5,60,0,1,41,9,9,10安全P31,9,9,101,7,5,01,0,0,02,9,9,10安全P42,9,9,102,3,5,61,3,5,43,12,14,14安全从上述分析中可以看出,此时存在一个安全序列P0,P3,P4,P1,P2,故该状态是安全的。(2)P
14、2 提出请求Request2(1,2,2,2),按银行家算法进行检查:Request2(1,2,2,2) Need2(2,3,5,6),P2 的请求是合理的;Request2(1,2,2,2) Available(1,6,2,2),P2 的请求是可以满足的;试分配并修改相应数据结构,资源分配情况如下:进程已分配需要可分配P00,0,3,20,0,1,20,4,0,0P11,0,0,01,7,5,0P22,5,7,61,1,3,4P30,3,3,20,6,5,2P40,0,1,40,6,5,6再利用安全性算法检查系统是否安全,可用资源Available(0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。2. 有相同类型的 5