2016年考研核心题型―【计算机操作系统】【第3章 处理机调度和死锁】

2016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任33第17章进程管理（处理机调度与死锁）17.1处理机调度温馨提示：本考点考查处理机调度的基本概念、准则和进程（作业）调度算法。请同学们掌握常见的进程调度算法的特点，并能够利用这些进程调度算法求作业的执行情况、周转时间和平均周转时间。1.下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。A.时间片轮转调度算法B.短进程优先调度算法C.先来先服务调度算法D.高响应比优先调度算法【2009年统考——第24题】【考查内容】高响应比优先调度算法的特点。【解析】高响应比优先算法的响应比=（等待时间+运行时间）/运行时间=1+等待时间/运行时间。该算法综合考虑了进程的等待时间和执行时间。故而，本题选择D答案。【参考答案】D2.下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（）。A.先来先服务B.高响应比优先C.时间片轮转D.非抢占式短任务优先【2011年统考——第23题】【考查内容】高响应比优先算法的特点。【解析】先来先服务有利于短作业，不利于长作业，但是不是短作业优先。时间片轮转算法不是短作业优先，而是每一个就绪队列的进程依次轮流执行一个时间片。对于非抢占式短作业优先算法，有利于短作业，但不利于长作业，可能会产生“饥饿”现象。高响应比优先是先来先服务算法和短作业优先算法的一种综合平衡。该算法满足短作业优先，长作业在等待时间长了之后，优先级会增大，最终会获得被调度的机会，不会发生“饥饿”现象。故而，本题选择B答案。2016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任34【参考答案】B3.操作系统中调度算法是核心算法之一，下列关于调度算法的论述中正确的是（）。A.先来先服务调度算法对即对长作业有利也对段作业有利B.时间片轮转调度算法只对长作业有利C.实时调度算法也要考虑作业的长短问题D.高相应比者优先调度算法既有利于短作业又兼顾长作业【2014年——南京航空航天大学】【考查内容】进程（作业）调度算法。【解析】本题是一个总结题，我们总结如下：(1).短作业优先算法有利于短作业而不利于长作业。可能致使长作业出现“饥饿”现象。短作业优先算法使得平均周转时间最短。(2).FCFS算法对短进程不公平，当长进程排在就绪队列的前面时必将增加后面短小进程的等待时间，从而增加系统的平均周转时间。FCFS算法有利于I/O型作业，不利于CPU繁忙型作业。(3).交互系统如我们常见的分时系统，采用的是时间片轮转算法。时间片足够大时，则该算法退化成FCFS算法。时间片太小，系统切换进程的开销大。影响时间片长短设置的因素为系统的响应时间、就绪队列的进程个数、系统的处理能力等。关于这个算法，我们认为既有利于长作业也有利于短作业。短作业可以在几次轮转中执行完毕，长作业也不会长期得不到执行。(4).最高响应比优先算法是对FCFS算法与SJF（短作业优先）算法的一种综合平衡。响应比的计算公式为响应比=（等待时间+允许时间）/运行时间从公式看，该算法有利于短作业，同时兼顾长作业，只要某长进程等待了足够长时间，总会成为最高响应比者而被调度执行。(5).实时调度算法则根据作业（进程）的紧迫程度来给作业（进程）设定优先级，调度算法选择当前就绪进程中优先级最高的进程调度执行，不考虑作业的长短问题。【参考答案】D4.一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序如下：P1：计算60ms，I/O80ms，计算20msP2：计算120ms，I/O40ms，计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。A.240msB.260msC.340msD.360ms【2012年统考——第29题】【考查内容】在并发条件下作业完成所需要的时间。2016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任35【解析】两个作业并发运行情况如下图17.1所示。P20100200T/msI/O操作计算300P1P1P2P1P2图17.1作业P1、P2并发运行情况由上图可知，完成两个作业需要的时间最少为260ms。故而，选择B答案。【参考答案】B5.若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。A.在进程结束时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统调用完成并返回用户态时能进行处理机调度【2012年统考——第29题】【考查内容】处理机调度合理时机。【解析】进程处于临界区，正在执行访问临界资源的代码，仍然可能引起处理机调度。比如临界资源为我们常见的打印机等慢速设备。为了提高系统的性能，可进行处理机调度。故而，选择C答案。【参考答案】C6.某系统正在执行三个进程P1、P2和P3，各进程的计算（CPU）时间和I/O时间比例如表17.1所示。表17.1进程计算时间I/O时间P190%10%P250%50%P315%85%为提高系统资源利用率，合理的进程优先级设置应为（）。A.P1P2P3B.P3P2P12016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任36C.P2P1=P3D.P1P2=P3【2009年统考——第23题】【考查内容】I/O繁忙型和计算型作业的优先级分配方法。【解析】根据题意，P1是计算繁忙型作业，P2是计算型和I/O型均衡的作业，P3是I/O繁忙型作业。为了提高系统的利用率，应该使得P3的优先级最高，P2次之，P1优先级最低。故而，选择B答案。【参考答案】B7.下列调度中，不可能导致饥饿现象的是（）。A.时间片轮转B.静态优先数调度C.非抢占式短作业优先D.抢占式短作业优先【2010年统考——第27题】【考查内容】进程（作业）调度算法。【解析】静态优先数调度算法中，若有大量的优先数比较高的作业到达，那么之前到达的优先数较低的作业将长期得不到执行，产生“饥饿”现象。非抢占式短作业优先和抢占式短作业优先的区别在于，当有比当前处理器运行的作业更短的作业到达时，能不能被抢占当前运行作业的处理机。显然，只要有大量的短作业陆陆续续到达，长作业可能长期得不到执行而产生“饥饿”现象。时间片轮转算法为就绪队列中的每一个作业分配一个时间片，每一个作业在一轮中都有一次运行的机会。所以，短作业可以在一次或者几次轮转中执行完毕，长作业也不会长期得不到执行。故而，不会产生“饥饿”现象。【参考答案】A8.某系统采用静态抢占式优先级进程调度算法。A进程0时刻到达，优先级为5，需运行10s；B进程3时刻到达，优先级为7，需运行5s；C进程5时刻到达，优先级为8，需运行3秒，则CPU的服务顺序为（）。A.A-B-C-AB.A-B-C-B-AC.A-B-A-CD.A-B-C-A-B【2013年——广东工业大学】【考查内容】静态抢占式优先级进程调度算法。【解析】静态优先级进程调度算法在进程调度之前预先设置优先级。可以看到，A进程在0时刻进入系统，此时系统中只有A一个进程，所以A被调度执行。在3时刻，进程B到达，其优先级为7，高于进程A的优先级5。因为系统采用抢占式进程调度算法，所以B被调度执行。在5时刻，进程C到达，其优先级为8，均高于A、B两个进程的优先级。所以C进程一直执行，直到完毕。在8时刻，进程C执行完毕，系统中剩下A和B两个进程。因为进程B的优先级高于进程A的优先级，所以B被调度执行。在11时刻，进程B执行完毕。A在0~3s被执行了3秒，在B执行完毕之后再执行7秒，到第18秒时执行完毕。2016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任37综上，A、B、C三个进程的执行情况如图17.2所示。01020T/sBAC图17.2由上图可以看出，程序的执行顺序为A-B-C-B-A，选择B答案。【参考答案】B17.2死锁温馨提示：本考点考查进程间的死锁问题，请同学们掌握死锁产生的原因，以及死锁预防、避免和检测方法。其中，银行家算法是本章的一个重要考点，请同学们务必能够根据进程资源的分配情况以及请求序列，推导安全序列（或死锁）。1.某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（）。A.2B.3C.4D.5【2009年统考——第25题】【考查内容】死锁。【解析】K个进程竞争使用资源，每个进程需要3台打印机，则一个极端的情况是每个进程都获得两台打印机，此时系统已经没有打印机，这种情况仍会致使系统死锁。故而最少需要2K+1台打印机，才能解除系统死锁。即2K+1≥8,得出K≥4。故而，K的最小值为4，选择C答案。【参考答案】C【经典总结】n个并发进程，每个进程需要R类资源m个，一个极端的情况就是每个进程都获得了(m-1)个资源，但是此时系统仍然死锁。故而还需要一个额外的资源来解除这种死锁。资源R最少为n×(m−1)+1=n×m+1−n2016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任382.某时刻进程的资源使用情况如表17.2所示。表17.2进程已分配资源尚需分配可用资源R1R2R3R1R2R3R1R2R3P1200001021P2120132P3011131P4001200此时的安全序列是（）。A.P1，P2，P3，P4B.P1，P3，P2，P4C.P1，P4，P3，P2D.不存在的【2011年统考——第27题】【考查内容】用银行家算法求安全序列。【解析】用银行家算法寻找一个安全序列，如表17.3所示。表17.3利用银行家算法寻找安全序列到此为止，已经找不到一个安全序列。故而，选择D答案。【参考答案】D3.假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如表17.4所示。表17.4进程已分配资源资源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4314424资源进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P1021001200221trueP4221200001222trueP4P12016年考研核心考点命题思路解密操作系统部分梦享团队主编我方慎重声明，各盈利机构若采用我方资料，必追究法律责任39此时存在的一个安全序列是（）。A.P0,P2,P4,P1,P3B.P1,P0,P3,P4,P2C.P2,P1,P0,P3,P4D.P3,P4,P2,P1,P0【2012年统考——第27题】【考查内容】用银行家算法求安全序列。【解析】用银行家算法寻找安全序列，系统可用在资源为（2,3,3）。Need矩阵如下图所示。need=[237133006221110]故而，P0、P1、P2开头的序列都会死锁。用排除法选择D答案。时间上，我们可以得到一个安全序列，如表17.5所示。表17.5利用银行家算法寻找安全序列此时，不管把（4,3,7）分配给任何一个余下的进程，都是一个安全序列。故而选择D答案。【参考答案】D4.下列关于银行家算法的叙述中，正确的是（）。A.银行家算法可以预防死锁B.当系统处于安全状态时，系统中一定无死锁进程C.当系统处于不安全状态时，系统中一定会出现死锁进程D.银行家算法破坏了死锁必要条件中的“请求和保持”条件【2013年统考——第32题】【考查内容】银行家算法。【解析】银行家算法是死锁避免算法，不是死锁预防算法。故而A错误。当系统处于安全状态，则系统中一定五死锁。但是处于不安全状态也可能没有死锁。故而，B答案正确。