《计算机操作系统自测题第4章调度与死锁.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统自测题第4章调度与死锁.ppt（37页珍藏版）》请在三一办公上搜索。
1、复习思考题,第四章 调度与死锁,1、分时操作系统中，进程调度通常采用什么算法？,答：分时操作系统通常采用时间片轮转法的调度算法。,2、一个作业从提交开始直到完成，往往要经历哪几级调度？,答：要经历下述三级调度：高级调度、低级调度、中级调度。,3、说出四种常用的调度算法,答：常用的调度算法有：（1）先来先服务调度算法（2）（进程）优先级调度算法（3）时间片轮转调度算法（4）多级反馈队列调度算法,4、什么是死锁？,答：所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。死锁是计算机系统和进程所处的一种状态。,5、产生死锁的原因是什么？
2、,答：产生死锁的原因可归结为两点：（1）系统资源不足。（2）进程推进顺序不当。,6、产生死锁的必要条件 有哪些？,答：同时具备下列四个必要条件时，就会产生死锁1、互斥（Mutual exclusion）条件：一个资源一次只能被一个进程所使用，即是排它性使用。2、不剥夺（No preemption）条件：进程已经获得的资源，在未使用完以前，不能被别的进程剥夺，只能在使用完以后，由自己释放。3、请求和保持（Hold-and-wait）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。4、环路等待（Circula
3、r wait）条件：存在一种进程资源的循环等待链，链中的每一个进程已经获得资源的同时被链中的下一个进程所请求。,7、处理死锁有哪几种基本方法？,答：用于处理死锁的方法主要有：1预防死锁：静态方法。在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。2避免死锁：动态的方法：事先不采取任何限制措施来破坏产生死锁的必要条件，而是在进程执行过程中采取的措施，在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。（如银行家算法）。3检测和解除死锁：通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。,8、银行家算法最根本是要解决什
4、么问题？,答：银行家算法最根本是一种能够避免死锁的调度方法。,9、当进程数大于资源数时，进程竞争资源一定会发生死锁吗？,答：不一定。,10、下列解决死锁的方法中，属于死锁预防策略的哪一个？,A.银行家算法B.资源有序分配法C.死锁检测法D.资源分配图化简法答：B,11、某系统有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是多少？,答：最少要10个。由于各进程最大需求量之和要小于“进程数+资源数”3+x12X9所以最少要10个资源。,12、你如何理解资源分配图简化法中“找出个既不阻塞又非独立的进程结点Pi”这句话。,答：个既不阻塞又非独立的进程结点Pi，也就是从进程集合中
5、找到一个有边与它相连，且资源申请数量小于系统中已有空闲资源数量的进程Pi。如下图：,R1,R2,12（续）,系统中共有R1类资源2个，R2类资源3个，在当前状态仅有一个R2类资源空闲。进程P2占有一个R1类资源及一个R2类资源，并申请一个R2类资源；进程P1占有一个R1类资源及一个R2类资源，并申请一个R1类资源及一个R2类资源。因此，进程P2是一个既不孤立又非阻塞的进程，消去进程P2的资源请求边和资源分配边，便形成了下图所示的情况。,13、解除死锁的常用方法有那些？,答：当发现有进程死锁时，使当立即把它们从死锁状态中解脱出来，常采用的两种方法是：（1）剥夺资源。是使用一个有效的挂起和解除机构
6、来挂起一些死锁的进程，其实质是从被挂起的进程那里抢占资源给死锁进程，以解除死锁状态。（2）撤消进程。采用强制手段从系统中撤消一个或一部分死锁进程，以断开循环等待链，并剥夺这些进程的资源供其他死锁进程使用。,14、假设三个进程共享相同类型的四个资源，每个进程一次只能申请或释放一个资源，每个进程至多需要两个资源，证明该系统不会发生死锁。,证：假定该系统死锁，那么就说明其中的每一进程已占有一资源并正等待另一资源。由于该系统只有三个进程且有四个资源，因此，必有一进程能获得两个资源，不必等待。于是该进程不再申请资源，而且当它执行完后将归还它占有的资源。故该系统不会发生死锁。,15、假设系统中有m个同类资
7、源，并被n个进程所共享，进程每次只申请或释放一个资源，如果(1)每个进程至少需要一个资源，且最多不超过m个资源，即对i=1，2，n，有0Need=m。(2)所有最大需求量之和小于m+n。证明该系统不会发生死锁。,证：依题意 max(1)+max(2)+.+max(n)m+n(由条件(2)知)如果这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即 alloc(1)+alloc(2)+.+alloc(n)=m 另一方面所有进程将陷入无限等待状态。上述两式得知 need(1)+need(2)+.+need(n)n上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个
8、进程，need(i)=0，即它已经获得全部的资源。既然进程已经获得了它所需要的全部资源，那么它就能执行完成并释放占有的全部资源，这与前面的假设矛盾，所以系统不会出现死锁。,15（续）,在一个实际的计算机系统中，资源可以更新和增减，进程可以创建和撤销。如果系统用banker算法处理死锁，那么，在什么情况下，下列改变可以安全地进行而不会引起死锁发生?(1)增加Available(增添新资源)；(2)减少Available(资源永久性地从系统中删除)：(3)增大Max(对一进程而言，它可能希望更多的资源)；(4)减少Max(一进程决定不需要那么多资源)；(5)增加进程数；(6)减少进程数。,16、,
9、解(1)任何时候都不会引起死锁发生：(2)仅当每一进程的Max请求数不超过可用资源的总数时，系统才保持在安全态：(3)仅当每一进程的Max请求数不超过可用资源的总数时，系统才保持在安全态；(4)任何时候都不会引起死锁发生；(5)任何时候都不会引起死锁发生：(6)任何时候都不会引起死锁发生。,16（续）,考虑下图所示的交通死锁情况。（1）说明图中导致死锁的四个必要条件成立。（2）提出一个避免死锁的规则。,交通死锁图,17、,解(1)此例中导致死锁的四个条件成立：互斥。每条道路只能被一辆车占用。占用并等待每辆车都占用了一段道路，并等待其前方的道路被释放。非抢占。资源不可抢占。单行线，汽车不能抢路超
10、车。循环等待。每辆车都等待着前方的汽车把路让出来，且形成了一个环路。(2)在每个十字路口设置红绿灯，当南北方向的路通车时，东西方向的路上汽车等待反之亦然。,17（续）,考虑下表所示的系统瞬时状态，利用banker算法回答下面的问题：(1)数组Need的内容是什么?(2)该系统处于安全态吗?若是，给出一安全序列。(3)若进程P1的请求(0420)到达，该请求是否能立即满足?,18、,(1)由于Need：Max-Allocation，所以Need的内容是：00000750 1002 0020 0642(2)是处于安全态，序列（P0，P2，P1，P3，P4）满足安全性要求。(3)能立即得到满足，因为
11、(0420)=Available=(1520)(0420)=Maxi=(1750)分配后的新系统状态如下表所示，且序列（P0，P2，P1，P3，P4）满足安全性要求。,18（解）,18（续）,假定待处理的三个作业的到达时间和运行时间如下：,若采用下列调度算法，则这些作业的平均轮转时间是多少？(1)FCFS；(2)SJF,19、,解：(1)FCFS10.53(2)SJF9.53,解：(1)FCFS(8+12-0.4+13-1.0)/3=10.53(2)SJF(8+9-1.0+13-0.4)/3=9.53,19（续）,假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单位
12、），它们被进程P1和P2共享，且已知两个进程均以下列顺序使用两类资源：申请R1 申请R2 申请R1 释放R1 释放R2 释放R1 试求出系统运行过程中可能到达的死锁点，并划出死锁点的资源分配图。,20、,解：在本题中，当两个进程都执行完第一步后，即进程P1和P2都申请到一个R1资源以后，系统进入不安全状态。随着两个进程的向前推进，无论哪个进程执行完第2步，系统都将进入死锁状态。可能到达的死锁点是：进程P1占有一个单位的R1类资源及一个单位的R2类资源，P2占有一个单位的R1类资源，此时系统已经没有空闲资源，而两个进程都在保持已占有的资源不释放的情况下继续申请资源，从而造成死锁。或者是进程P2占
13、有一个单位的R1类资源及一个单位的R2类资源，P1占有一个单位的R1类资源，此时系统已经没有空闲资源，而两个进程都在保持已占有的资源不释放的情况下继续申请资源，从而造成死锁。假定进程P1成功执行了第二步，则死锁点的资源分配图如下所示：,21、生产者-消费者问题中，如果对调生产者进程中的两个P操作和两个V操作，则可能发生什么情况？解：生产者-消费者的同步问题中，如果对调生产者进程中的两个P操作和两个V操作，那么生产者和消费者的进程分别描述如下：,producer()while(生产未完成)生产一个产品；P(mutex);p(empty);送一个产品到有界缓冲区；V(full);V(mutex);
14、,consumer()while(还要继续消费)P(full);p(mutex);从有界缓冲区中取产品；V(mutex);V(empty);,由于V操作是释放资源，所以对调V操作的次序无关紧要。而对调P操作的次序可能导致死锁。因为对调P操作的次序后，有可能出现这样一种特殊情况：在某一时刻缓冲区中已经装满了产品，且缓冲区中无进程工作（这时信号量full=n,empty=0,mutex=1），若系统此时调度生产者进程运行，生产者生产了一个产品，它执行P(mutex)并顺利进入临界区（进入临界区后，mutex=0），随后它执行P(empty)时因没有空缓冲单元而受阻等待，等待消费者进程进入缓冲区取走
15、产品后释放出缓冲单元；而消费者进程执行P(full)后再执行P(mutex)的时候，因缓冲区被生产者进程占据而无法进入。这样，就形成生产者在占有临界资源的情况下，等待消费者进程取走产品，而消费者进程又无法进入临界区取走产品的僵局，此时两进程陷入死锁。,22,22、假设就绪队列中有10个进程，系统将时间片设为200ms，CPU进行进程切换要花费10ms，试问系统开销所占的比率约为多少？答：因就绪队列中有10个进程，它们将以时间片轮转的方式使用CPU，时间片长度为200ms。当一个时间片用完时，调度进程将当前运行进程设置为就绪状态并放入就绪队列尾，再从就绪队列队首选择进程投入运行，这一过程（进程切
16、换）要花费时间10ms。因此系统开销所占比率为：10/（200+10）=4.8%,23、,银行家算法中，当一个进程提出资源请求时，何时系统会拒绝它的资源请求？答：当一个进程提出资源请求时，如果将导致系统从安全状态进入不安全状态，系统就会拒绝它的资源请求。,24、,假定系统中有4个进程P1、P2、P3、P4和3中类型的资源R1、R2、R3，数量分别为9、3、6，在T0时刻的资源分配情况如下表所示。试问：（1）T0时刻是否安全？（2）P2发出请求向量Request(1，0，1)，系统能否将资源分配给它？,24（续）,解：（1）我们用银行家算法对T0时刻的安全性分析，从上表中可以得出，在T0时刻系统存在一个安全系列P2、P1、P3、P4，故系统是安全的。（或回答出其他的安全系列也对）（2）P2发出请求向量Request(1，0，1)，系统按银行家算法检查Request(1，0，1)Need2(1，0，2)Request(1，0，1)Available(1，1，2)假设系统可为P2分配资源，形成下表所示的资源分配情况表,24（续）,对以上情况作安全性检查，可以找到一个安全序列P2、P1、P3、P4。因此系统是安全的，可以立即将P2所申请的资源给它。,
