操作系统复习考试第4章 调度与死锁 复习题课件

复习思考题第四章调度与死锁

1、分时操作系统中，进程调度通常采用什么算法？答：分时操作系统通常采用时间片轮转法的调度算法。2、一个作业从提交开始直到完成，往往要经历哪几级调度？答：要经历下述三级调度：高级调度、低级调度、中级调度。4、什么是死锁？答：所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。死锁是计算机系统和进程所处的一种状态。5、产生死锁的原因是什么？答：产生死锁的原因可归结为两点：（1）系统资源不足。（2）进程推进顺序不当。6、产生死锁的必要条件有哪些？答：同时具备下列四个必要条件时，就会产生死锁1、互斥（Mutualexclusion）条件：一个资源一次只能被一个进程所使用，即是排它性使用。2、不剥夺（Nopreemption）条件：进程已经获得的资源，在未使用完以前，不能被别的进程剥夺，只能在使用完以后，由自己释放。3、请求和保持（Hold-and-wait）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。4、环路等待（Circularwait）条件：存在一种进程资源的循环等待链，链中的每一个进程已经获得资源的同时被链中的下一个进程所请求。7、处理死锁有哪几种基本方法？答：用于处理死锁的方法主要有：1．预防死锁：静态方法。在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。2．避免死锁：动态的方法：事先不采取任何限制措施来破坏产生死锁的必要条件，而是在进程执行过程中采取的措施，在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。（如银行家算法）。3．检测和解除死锁：通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。9、当进程数大于资源数时，进程竞争资源一定会发生死锁吗？答：不一定。11、某系统有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是多少？答：最少要10个。由于各进程最大需求量之和要小于“进程数+资源数”3+x>12X>9所以最少要10个资源。12（续）系统中共有R1类资源2个，R2类资源3个，在当前状态仅有一个R2类资源空闲。进程P2占有一个R1类资源及一个R2类资源，并申请一个R2类资源；进程P1占有一个R1类资源及一个R2类资源，并申请一个R1类资源及一个R2类资源。因此，进程P2是一个既不孤立又非阻塞的进程，消去进程P2的资源请求边和资源分配边，便形成了下图所示的情况。R1R2P1P213、解除死锁的常用方法有那些？答：当发现有进程死锁时，使当立即把它们从死锁状态中解脱出来，常采用的两种方法是：（1）剥夺资源。是使用一个有效的挂起和解除机构来挂起一些死锁的进程，其实质是从被挂起的进程那里抢占资源给死锁进程，以解除死锁状态。（2）撤消进程。采用强制手段从系统中撤消一个或一部分死锁进程，以断开循环等待链，并剥夺这些进程的资源供其他死锁进程使用。14、

假设三个进程共享相同类型的四个资源，每个进程一次只能申请或释放一个资源，每个进程至多需要两个资源，证明该系统不会发生死锁。证： 假定该系统死锁，那么就说明其中的每一进程已占有一资源并正等待另一资源。由于该系统只有三个进程且有四个资源，因此，必有一进程能获得两个资源，不必等待。于是该进程不再申请资源，而且当它执行完后将归还它占有的资源。故该系统不会发生死锁。15、

假设系统中有m个同类资源，并被n个进程所共享，进程每次只申请或释放一个资源，如果

(1)每个进程至少需要一个资源，且最多不超过m个资源，即对i=1，2，…，n，有0<Need<=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，这意味着此刻至少存在一个进程，need(i)=0，即它已经获得全部的资源。既然进程已经获得了它所需要的全部资源，那么它就能执行完成并释放占有的全部资源，这与前面的假设矛盾，所以系统不会出现死锁。15（续）解(1)任何时候都不会引起死锁发生：(2)仅当每一进程的Max请求数不超过可用资源的总数时，系统才保持在安全态：(3)仅当每一进程的Max请求数不超过可用资源的总数时，系统才保持在安全态；(4)任何时候都不会引起死锁发生；(5)任何时候都不会引起死锁发生：(6)任何时候都不会引起死锁发生。

16（续） 考虑下图所示的交通死锁情况。（1）说明图中导致死锁的四个必要条件成立。（2）提出一个避免死锁的规则。交通死锁图17、考虑下表所示的系统瞬时状态，利用banker算法回答下面的问题：(1)数组Need的内容是什么?(2)该系统处于安全态吗?若是，给出一安全序列。 (3)若进程P1的请求(0420)到达，该请求是否能立即满足?

18、(1)由于Need：Max-Allocation，所以Need的内容是：0000 0750100200200642(2)是处于安全态，序列（P0，P2，P1，P3，P4）满足安全性要求。(3)能立即得到满足，因为①(0420)<=Available=(1520)②(0420)<=Maxi=(1750) ③分配后的新系统状态如下表所示，且序列（P0，P2，P1，P3，P4）满足安全性要求。18（解）

假定待处理的三个作业的到达时间和运行时间如下： 若采用下列调度算法，则这些作业的平均轮转时间是多少？(1)FCFS；(2)SJF19、解： (1)FCFS 10.53 (2)SJF 9.53解： (1)FCFS(8+12-0.4+13-1.0)/3=10.53 (2)SJF (8+9-1.0+13-0.4)/3=9.5319（续）假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单位），它们被进程P1和P2共享，且已知两个进程均以下列顺序使用两类资源：→申请R1→申请R2→申请R1→释放R1→释放R2→释放R1 试求出系统运行过程中可能到达的死锁点，并划出死锁点的资源分配图。20、P1P2死锁点资源分配图R1R221、生产者-消费者问题中，如果对调生产者进程中的两个P操作和两个V操作，则可能发生什么情况？解：生产者-消费者的同步问题中，如果对调生产者进程中的两个P操作和两个V操作，那么生产者和消费者的进程分别描述如下：producer(){while(生产未完成){生产一个产品；P(mutex);p(empty);送一个产品到有界缓冲区；V(full);V(mutex);}}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)时因没有空缓冲单元而受阻等待，等待消费者进程进入缓冲区取走产品后释放出缓冲单元；而消费者进程执行P(full)后再执行P(mutex)的时候，因缓冲区被生产者进程占据而无法进入。这样，就形成生产者在占有临界资源的情况下，等待消费者进程取走产品，而消费者进程又无法进入临界区取走产品的僵局，此时两进程陷入死锁。2222、假设就绪队列中有10个进程，系统将时间片设为200ms，CPU进行进程切换要花费10ms，试问系统开销所占的比率约为多少？答：因就绪队列中有10个进程，它们将以时间片轮转的方式使用CPU，时间片长度为200ms。当一个时间片用完时，调度进程将当前运行进程设置为就绪状态并放入就绪队列尾，再从就绪队列队首选择进程投入运行，这一过程（进程切换）要花费时间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）P