操作系统习题及答案四Word格式文档下载.doc

1、共产生缺页中断10次。依次淘汰的页是1、2、3、4、5、1、2。3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么?空闲分区表32K10K5K218K90K100K150K200K 220K530K分区号1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小起始地址3解：若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大d,-致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区

2、，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。为作业序列分配了内存空间后，空闲分区表如表5-3（a）所示。 若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分区还剩下122K；接着申请20K，选中1号分区，分配后剩下12K；最后申请200K，现有的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进行内存分配，无法满足该作业序列的需求。这时的空闲分区表如表53（b）所示。 分配后的空闲分区表（a）12K18K （b）122K96K4、某采用段式存储管理的系统为装入主存的

3、一个作业建立下表所示的段表 段表段号段长主存起始地址660221914033001009058012379601959回答下列问题：（1）计算该作业访问0, 432, l, 10, 2, 500时（方括号中第一元素为段号，第二元素为段内地址）的绝对地址（2）总结段式存储管理的地址转换过程4答： （1）0,432 （432660）2219+432=2651 1，10 （10100所以地址越界，产生中断） （2）总结段式存储管理的地址转换过程如下： 从逻辑地址中取出段号和段内地址。 根据段号，从段表中取出该段在主存中的始址和段长。 比较段内地址和段长，如段内地址段长，则继续下一步，否则产生越界中段

4、，程序中断（非法操作）。 计算本段始址+段内地址，得到绝对地址。1.假设一个系统中有5个进程,它们的到达时间和服务时间如表1所示,忽略I/0以及其他开销时间,若分别按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRF）、时间片轮转（RR,时间片=1）调度算法进行CPU调度,请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。表1进程到达和需服务时间进程到达时间服务时间AB6CDE分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时

5、,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则新进程将抢占CPU;HRRF算法选择响应比最高的进程投入执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片。答：各进程的完成时间、周转时间和带权周转时间（如表2所示）表2进程的完成时间和周转时间进程平 均FCFS完成时间周转时间带权周转时间1.0091.17132.2518122.40206.008.62.56SPF（非抢占）152.75142.801.57.61.84SPF（抢占）2.16107.21.59HRRF3.52.14RR（q=1）1.33162.67173.252.810.82

6、.713.在银行家算法中，若出现下述资源分配情况：进程AllocationNeedAvailableABCP0P10315726试问:（1）该状态是否安全?（2）如果进程P2提出请求Request（0,2,2,2后,系统能否将资源分配给它?解:（1）利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。进 程WorkWork+AllocationFinishD989 1214true从上述分析中可以看出，此时存在一个安全序列P0,P3,P4,P1,P2,故该状态是安全的。（2）P2提出请求Request2（1,2,2,2）,按银行家算法进行检查：Request2（1,2,2

7、,2）Need2（2,3,5,6）Request2（1,2,2,2）Available（1,6,2,2）试分配并修改相应数据结构，资源分配情况如下：4再利用安全性算法检查系统是否安全,可用资源Available （0,4,0,0）已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。3某请求分页系统，用户空间为32KB，每个页面1KB，主存16KB。某用户程序有7页长，某时刻该用户进程的页表如下：是否在TLB是否（1）计算两个逻辑地址：0AC5H、1AC5H对应的物理地址。（2）已知主存的一次存取为1.5us，对于TLB表（快表）的查询时间可以忽略，则访问上述两个逻辑地

8、址共耗费多少时间？答 （1） 每页1kb代表页内偏移量为低地址10位，剩余的为页号，所以0AC5H对应的页号为2，物理块为4，说以物理地址为12C5H, 同理可得1AC5H对应的物理地址为0AC5H.（2）耗时为11.5us+21.5us=4.5us4什么叫重定位？它有哪两种方式？这两种方式有什么区别？ 由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。5在具有快表的段页式存储管理方式中，如何实现地址变换？ 答：物理地址=该段在主存的起始地址+页框号*大小+页内地址

9、。第二次作业：1、 在某请求分页管理系统中，一个作业共5页，作业执行时一次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为3，分别采用FIFO，LRU，Clock页面置换算法，试求出缺页中断的次数及缺页率。答 FIFO 缺页次数为9，缺页率为3/4LRU缺页数为9，缺页率为3/4Clock缺页数为9，缺页率为3/42、 某请求分页管理系统，假设进程的页表如下：页框号有效位装入时间101H254H页面大小为4KB，一次内存的访问时间为100纳秒（ns），一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为100毫秒（已含更新TLB和页表的时间）

10、，进程的驻留集大小固定为2个页框，采用FIFO法置换页面。假设1）TLB初始为空；2）地址转换时，先访问TLB，若TLB未命中时再访问页表（忽略TLB更新时间）；3）有效位为0表示页面不在内存中。请问：（1）该系统中，一次访存的时间下限和上限各是多少？（给出计算过程）（2）若已经先后访问过0、2号页面，则虚地址1565H的物理地址是多少？答（1）一次访存时间下限10ns+100ns+100ns，上限10ns+100ns+100ms+100ns （2）基于上述访问序列，当访问虚地址1565H时产生缺页中断，合法驻留集为2，必须从表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H

11、的对应页框号为101H。由此可得1565H的物理地址为101565H3、设某计算机的逻辑地址空间和物理地址空间均为128KB，按字节编址。若某进程最多需要6页数据存储空间，页面大小为1KB，操作系统采用固定分配局部置换策略为该进程分配4个页框（物理块）。在时刻300前该进程各页面的访问情况如下表所示：页框号（块号）访问位130230200180当进程执行到时刻300时，要访问逻辑地址为17CAH的数据，请回答下列问题：（1）该逻辑地址对应的页号是多少？（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（3）若采用时钟（CLOCK）置换算法，该逻辑地址对

12、应的物理地址是多少？设搜索下一页的指针顺时针方向移动，且当前指向2号页框，示意图如下：17CAH=（0001011111001010）2（1）页大小为1K，则页内偏移地址为10位，前6位是页号，所以逻辑地址对应的页号为：（2）FIFO：被置换的页面所在页框为7，所以对应的物理地址为（000111111010）2=1FCAH（3）CLOCK：被置换的页面所在页框为2，所以对应的物理地址为（000010111010）2=0BCAH并有一下请求序列等待访问磁盘：请求序列： 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9预访问柱面号：150，50 ，178，167 ，87，43 ，23 ，160

13、，85试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述请求的次序第一题：序列（柱面号）最短寻找时间优先算法9（85）、5（87）、2（50）、6（43）、7（23）、1（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#磁道上，并向磁道号减小的方向上移动，现有一下请求序列等待访问磁盘：请求序列 1 2 3 4 5 6 7 8 带访问的柱面号 99 184 38 123 15 125 66 68试用最短寻找时间优先算

14、法和电梯调度算法，分别排出实际处理上述请求的次序，并计算出他们的平均寻道长度 7（66） 8（68） 3（38） 5（15） 1（99） 4（123） 6（125） 2（184）12+2+30+23+84+24+2+59=236平均寻道长度236/8=29.53（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=261、假定在单CPU条件下有下列要执行的作业：作业运行时间优先级 作业到来的时间是按作业编号顺序进行的（即后面作业依次比前一个作业迟到一个时间单位）。 （1）用一个

15、执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？ （1） 非抢占式优先级算法（3分） 作业1 作业3 作业2 | | | | t 0 10 13 17 （2） 和（3）1.04.03.7平均周转时间12.3平均带权周转时间2.92、若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行 时间为a、b、c，且满足ab可见，采用短作业优先算法调度才能获得最小平均作业周转时间。3、若有如表所示四个作业进入系统，分别计算在FCFS

16、、SJF和HRRF算法下的平均周转时间与带权平均周转时间。提交时间（时）估计运行时间（分）8:00509:1203答：SJF开始 完成 周转时间 时间 时间00 10:00 12010:00 10:50 12050 11:11:00 11:20 9030 11:20 15010 7010 10:30 4010 11:00 130平均周转时间T=112.5T=95T=102.5带权平均周转时间W=4.975W=3.25W=3.7754、有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：提交时间估计运行时间（分钟）2530354060系统采用剩余SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时 可被剩余时间更短作业抢占。（1）分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。（2）计算平均作业周转时间。作业号需运行时间开始运行时间被抢占还需运行时间J1155J25595J345J4J5J6说明：（1） J2到达时抢占J1；J3到达时抢占J2。（2）但J4到达时，因不满足SJF，故J4不能被运行，J3继续执行5分钟。（3）由于是4道的作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束（4）根据进程调度可抢占原则，J3第一个做完。而这时J5、J6均己进入