操作系统习题及答案四

1、* PAGE PAGE 10四、计算题页号0123物理块号3711页号0123物理块号37118那么逻辑地址 0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由条件“用户编程空间共32 5 1KB10 由“16KB16 4 位。H 1010 0101 “000 111110 0101 1100 ，得10 1110 0101 2E5CH。2、对于如下的页面访问序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 53 时，试问：使用LRU 解：页面次序1234页面次序123412512345主存11144455

2、5页面22211133情况33322249 、3、1、。调度算法，页面调度过程如下：页面次序123412512345主存1114445333页面222111144情况33322225共产生缺页中断 10 次。依次淘汰的页是 1、2、3、4、5、1、2。3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。假设用首次适应算法和最正确适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的恳求，为什么?空闲分区表分区号大小起始地址132K100K210K150K35K200K4218K220K590K530K解：假设采用最正确适应算法

3、，在申请96K 5 小与申请空间大d,-致，应从空闲分区表中删去该表项；接着申请20K 1 号分区，分配1 12K200K4 18K。显然采用最正5-3(a)所示。96K 4 4 号分区122K20K1 12K200K，现有的该作业序列的需求。这时的空闲分区表如表53(b)所示。分配后的空闲分区表(a)分区号大小起始地址112K100K210K150K35K200K418K220K(b)分区号大小起始地址112K100K210K150K35K200K4122K220K596K530K4、某采用段式存储管理的系统为装入主存的一个作业建立下表所示的段表段表段号段号段长主存起始地址066022191

4、14033002100903580123749601959分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS 算法选择最早进入就绪队列分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS 算法选择最早进入就绪队列;SPFCPU;HRRF;RRFIFO,CPU答：各进程的完成时间、周转时间和带权周转时间(如表 2 所示)表 2 进程的完成时间和周转时间FCFS带权周转时间1.001.172.252.406.002.561计算该作业访问0, 432, l, 10, 2, 500 时方括号中第一元素为段号，第二元素为段内地址的绝对地址2总结段式存储管理的地址转换过程答：(1)0,432

5、 (432660)2219+432=2651 1，10 (10100 所以地址越界，产生中断) (2)总结段式存储管理的地址转换过程如下：从逻辑地址中取出段号和段内地址。根据段号，从段表中取出该段在主存中的始址和段长。中断()。计算本段始址+段内地址，得到绝对地址。11.假设一个系统中有51 所示,忽略I/0(FCFSSPF(HRRF(RR=1)调度算法进展 CPU表 1 进程到达和需效劳时间程时间时间B26C44D65E82进程ABCDE平 均完成时间39131820周转时间37912128.6完成时间39152011SPF(非抢占)周转时间37111437.6带权周转时间1.001.17

6、2.752.80 1.5 1.84完成时间31582010SPF(抢占)周转时间31341427.2带权周转时间1.002.16 1.002.801.00 1.59完成时间39132015HRRF周转时间3791478带权周转时间1.001.17 2.252.80 3.5 2.14完成时间418172015RR(q=1)周转时间4161314710.8带权周转时间1.33 2.67 3.25 2.8 3.5 2.713.在银行家算法中，假设出现下述资源分配情况：AllocationNeedAvailable进 程A B C D A B C D A B C DP000320012 1 6 2 2

7、P110001750P213542356P303320652P400140656试问:1)该状态是否平安?(2)假如进程P2 提出恳求Request0,2,2,2后,系统能否将资源分配给它?解:(1)利用银行家算法对此时刻的资源分配情况进展分析,可得此时刻的平安性分析情况。WorkNeedAllocation Work+Allocation进程FinishA B C D A B C D A B C DA B C DP01 6 2 20 0 1 2 0 0 3 P31 6 5 4 0 6 5 2 0 3 3 P41 9 8 6 0 6 5 6 0 0 1 P11 9 9 10 1 7 5 0 1

8、 0 0 P22 9 9 10 2 3 5 6 1 3 5 1 6 5 41 9 8 61 9 9 102 9 9 103 12 14 true true true true true从上述分析中可以看出，此时存在一个平安序列P0,P3,P4,P1,P2,故该状态是平安的。从上述分析中可以看出，此时存在一个平安序列P0,P3,P4,P1,P2,故该状态是平安的。2P2 提出恳求Request2(1,2,2,2),按银行家算法进展检查： Request2(1,2,2,2)Need2(2,3,5,6) Request2(1,2,2,2)Available(1,6,2,2)试分配并修改相应数据构造，

9、资源分配情况如下：P000320012 0 40 0P110001750P225761134P303320652P400140656AllocationNeedAvailable进 程A B C D A B C D A B C DAvailable (0,4,0,0)已不能满足任何进程的需要,故系统进入不平安状态,此时系统不能将资源分配给P2。某恳求分页系统，用户空间为32KBAllocationNeedAvailable进 程A B C D A B C D A B C DAvailable (0,4,0,0)已不能满足任何进程的需要,故系统进入不平安状态,此时系统不能将资源分配给P2。页号物

10、理块号是否在TLB08是17是24否310否45否53是62是1计算两个逻辑地址：0AC5H、1AC5H 对应的物理地址。2主存的一次存取为 1.5us，对于 TLB 表快表的查询时间可以忽略，那么访问上述两个逻辑地址共消耗多少时间？答 1kb 10 位，剩余的为页号，所以0AC5H 页号为 2，物理块为 4，说以物理地址为 12C5H, 同理可得 1AC5H 0AC5H.2耗时为 11.5us+21.5us=4.5us什么叫重定位？它有哪两种方式？这两种方式有什么区别？由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时假设不对程序和数据的地址加以修改变换动了的程序或数据进展重定位。在

11、具有快表的段页式存储管理方式中，如何实现地址变换？答：物理地址=该段在主存的起始地址+页框号*大小+页内地址。第二次作业：1在某恳求分页管理系统中，一个作业共5 ，分别采用 Clock 页面置换算法，试求出缺页中断的次数及缺页率。答 FIFO 缺页次数为 9，缺页率为 3/4 LRU 缺页数为 9，缺页率为 3/4 Clock 缺页数为 9，缺页率为 3/42、 某恳求分页管理系统，假设进程的页表如下：页号页框号有效位装入时间0101H12102254H14页面大小为 4KB，一次内存的访问时间为 100 nsTLB的访问时间10ns100 毫秒已含更新TLB 2 FIFO 1TLB 地址转换

12、TLBTLB TLB 0 表示页面不在内存中。请问：1该系统中，一次访存的时间下限和上限各是多少？给出计算过程2假设已经先后访问过 0、2 号页面，那么虚地址 1565H 的物理地址是多少？给出计算过程答1一次访存时间下限 10ns+100ns+100ns，上限 10ns+100ns+100ms+100ns2基于上述访问序列，当访问虚地址1565H 20 1565H 的对应页框号1565H 101565H3、设某计算机的逻辑地址空间和物理地址空间均为128KB，按字节编址。假设某进程最多需要 6 页数据存储空间，页面大小为 1KB，操作系统采用固定分配部分置换策略为该进程分配 4 个页框物理块

13、。在时刻 300 前该进程各页面的访问情况如下表所示：页号页框号块号装入时间访问位0713011423012220013391801当进程执行到时刻 300 时，要访问逻辑地址为 17CAH 的数据，请答复以下问题：1该逻辑地址对应的页号是多少？2假设采用先进先出FIFO置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。3假设采用时钟CLOCK置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。设搜索下一页的指针顺时针方向挪动，且当前指向2 号页框，示意图如下：9号2号页框3号页2号页 页框7号0号页 1号页4号页框页17CAH=(0001 0111 1100 1010)21

14、页大小为 1K，那么页内偏移地址为 10 位，前 6 位是页号，所以逻辑地址对应的页号为：5FIFO：被置换的页面所在页框为 7，所以对应的物理地址为0001 1111 1100 2=1FCAH0000 1011 1100 2=0BCAH并有一下恳求序列等待访问磁盘：恳求序列：1，2，3，4，5，6，7，8，9 预访问柱面号：150，50 ，178，167 ，87，43 ，23 ，160 试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述恳求的次序第一题：序列柱面号最短寻找时间优先算法第一题：序列柱面号最短寻找时间优先算法9(85)、5(87)、2(50)、6(43)、7(23)、1

15、(150)、8(160)、4(167)、3(178)电梯调度算法9(85)、5(87)、1(150)、8(160)、4(167)、3(178)、2(50)、6(43)、7(23)第二题：199 54#求序列等待访问磁盘：恳求序列12345678带访问的柱面号 99184 3812315 1256668试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述恳求的次序，并计算出他们的平均寻道长度他们的平均寻道长度第二题：序列柱面号最短寻找时间优先算法7(66)7(66) 8(68) 3(38) 5(15) 1(99) 4(123) 6(125) 2(184)12+2+30+23+84+24+

16、2+59=23612+2+30+23+84+24+2+59=236平均寻道长度 236/8=29.5 电梯调度算法3(38) 5(15) 7(66) 8(68) 1(99) 4(123) 6(125) 2(184)16+23+51+2+31+24+2+59=208平均寻道长度 208/8=26四、计算题1、假定在单CPU条件下有以下要执行的作业：作业作业123运行时间1043优先级235作业到来的时间是按作业编号顺序进展的即后面作业依次比前一个作业迟到一个时间单位。1用一个执行时间图描绘在采用非抢占式优先级算法时执行这些作业的情况。2对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？

17、3对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？解：3分作业1作业3作业2|0101317(2) 和3作业到达时间运行时间完成时间周转时间带权周转时间101010101.021417164.032313113.7平均周转时间12.32.92、假设后备作业队列中等待运行的同时有三个作业J1、J2平均周转时间12.32.9时间为a、b、c，且满足ab0可见，采用短作业优先算法调度才能获得最小平均作业周转时间。3、假设有如表所示四个作业进入系统，分别计算在、SJF 和 HRRF 周转时间与带权平均周转时间。作业作业1234提交时间时 估计运行时间分8:008:509:009:5

18、0120501020答：18:0010:001208:0010:001208:0010:00120210:0010:5012010:3011:2015010:1011:00130310:5011:0012010:0010:107010:0010:1070411:0011:209010:1010:304011:0011:2090作业FCFS开场完成周转时间时间时间SJF开场完成周转时间时间时间HRRF开场完成周转时间时间时间作业FCFS开场完成周转时间时间时间SJF开场完成周转时间时间时间HRRF开场完成周转时间时间时间平均周转时间T=112.5T=95T=102.5W=4.975W=3.25W=3.775行时间由下表给出：作业提交时间18:006028:203538: