计算机操作系统自测题调度与死锁

《计算机操作系统自测题调度与死锁》由会员分享，可在线阅读，更多相关《计算机操作系统自测题调度与死锁（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 ）条件：进程已经保持 了至少一个资源，但又提出了新的资源要求，而该资源 又已被其它进程占有，此时请求进程阻塞，但又对已经 获得的其它资源保持

3、不放。 4、环路等待（ Circular wait ）条件：存在一种进程资源 的循环等待链，链中的每一个进程已经获得资源的同时 被链中的下一个进程所请求。7、处理死锁有哪几种基本方法？答：用于处理死锁的方法主要有： 1预防死锁：静态方法。在进程执行前采取的措施 ，通过设置某些限制条件，去破坏产生死锁的四个必要 条件之一，防止发生死锁。 2避免死锁：动态的方法：事先不采取任何限制措 施来破坏产生死锁的必要条件，而是在进程执行过程中 采取的措施，在进程申请资源时用某种方法去防止系统 进入不安全状态，从而避免发生死锁。 （如银行家算法 ）。 3检测和解除死锁：通过系统的检测机构及时地 检测出死锁的发

4、生，然后采取某种措施解除死锁。8、银行家算法最根本是要解决什么 问题？答：银行家算法最根本是一种能够避免 死锁的调度方法。9、当进程数大于资源数时，进 程竞争资源一定会发生死锁吗？答：不一定。10、下列解决死锁的方法中，属 于死锁预防策略的哪一个？A. 银行家算法B. 资源有序分配法 C. 死锁检测法D. 资源分配图化简法答：B11、某系统有3个并发进程，都需要同 类资源4个，试问该系统不会发生死锁的 最少资源数是多少？ 答：最少要10个。 由于各进程最大需求量之和要小于“进 程数+资源数” 3+x12 X9 所以最少要10个资源。12、你如何理解资源分配图简化法中 “找出个既不阻塞又非独立的

5、进程结 点Pi ”这句话。答： 个既不阻塞又非独立的进程结点Pi ，也就是从进 程集合中找到一个有边与它相连，且资源申请数量小于 系统中已有空闲资源数量的进程Pi 。如下图： P1P2R1R212（续）系统中共有R1类资源2个，R2类资源3个，在当前 状态仅有一个R2类资源空闲。进程P2占有一个R1 类资源及一个R2类资源，并申请一个R2类资源； 进程P1占有一个R1类资源及一个R2类资源，并申 请一个R1类资源及一个R2类资源。因此，进程P2 是一个既不孤立又非阻塞的进程，消去进程P2的资 源请求边和资源分配边，便形成了下图所示的情况 。 R1R2P1P213、解除死锁的常用方法有那些 ？答

6、：当发现有进程死锁时，使当立即把它们从死 锁状态中解脱出来，常采用的两种方法是：（1）剥夺资源。是使用一个有效的挂起和解除机构来 挂起一些死锁的进程，其实质是从被挂起的进程那里抢 占资源给死锁进程，以解除死锁状态。 （2）撤消进程。采用强制手段从系统中撤消一个或一 部分死锁进程，以断开循环等待链，并剥夺这些进程的 资源供其他死锁进程使用。14、 假设三个进程共享相同类型的四个资源，每个进 程一次只能申请或释放一个资源，每个进程至多 需要两个资源，证明该系统不会发生死锁。证： 假定该系统死锁，那么就说明其中的每一进程已 占有一资源并正等待另一资源。由于该系统只有 三个进程且有四个资源，因此，必有

7、一进程能获 得两个资源，不必等待。于是该进程不再申请资 源，而且当它执行完后将归还它占有的资源。故 该系统不会发生死锁。15、 假设系统中有m个同类资源，并被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另一方面所有进

8、程将陷入无限等待状态。上述两式得 知need(1)+need(2)+.+need(n) n上式表示死锁发生后，n个进程还需要的资源量之和 小于n，这意味着此刻至少存在一个进程， need(i)=0，即它已经获得全部的资源。既然进程已 经获得了它所需要的全部资源，那么它就能执行完成 并释放占有的全部资源，这与前面的假设矛盾，所以 系统不会出现死锁。15（续）在一个实际的计算机系统中，资源可以更新和增减，进 程可以创建和撤销。如果系统用banker算法处理死锁，那 么，在什么情况下，下列改变可以安全地进行而不会引起 死锁发生?(1)增加Available(增添新资源)；(2)减少Available

9、(资源永久性地从系统中删除)：(3)增大Max(对一进程而言，它可能希望更多的资源)； (4)减少Max(一进程决定不需要那么多资源)； (5)增加进程数； (6)减少进程数。16、解 (1)任何时候都不会引起死锁发生：(2)仅当每一进程的Max请求数不超过可用资源的总数时 ，系统才保持在安全态：(3)仅当每一进程的Max请求数不超过可用资源的总数时 ，系统才保持在安全态；(4)任何时候都不会引起死锁发生；(5)任何时候都不会引起死锁发生：(6)任何时候都不会引起死锁发生。16（续）考虑下图所示的交通死锁情况。 （1）说明图中导致死锁的四个必要条件成立。 （2）提出一个避免死锁的规则。交通死锁

10、图17、解 (1)此例中导致死锁的四个条件成立： 互斥。每条道路只能被一辆车占用。 占用并等待每辆车都占用了一段道路，并等待其 前方的道路被释放。 非抢占。资源不可抢占。单行线，汽车不能抢路超 车。 循环等待。每辆车都等待着前方的汽车把路让出来 ，且形成了一个环路。 (2)在每个十字路口设置红绿灯，当南北方向的路通 车时，东西方向的路上汽车等待反之亦然。17（续）考虑下表所示的系统瞬时状态，利用banker算法回答下面的问 题：(1)数组Need的内容是什么?(2)该系统处于安全态吗?若是，给出一安全序列。(3)若进程P1的请求(0420)到达，该请求是否能立即满足? 18、(1)由于Need

11、：Max-Allocation，所以Need的 内容是：0000 0750 1002 0020 0642 (2)是处于安全态，序列（P0，P2，P1，P3， P4）满足安全性要求。 (3)能立即得到满足，因为(0420)=Available=(1520)(0420)=Maxi=(1750)分配后的新系统状态如下表所示，且序列 （P0，P2，P1，P3，P4）满足安全性要求。18（解）18（续）假定待处理的三个作业的到达时间和运行时间如下：若采用下列调度算法，则这些作业的平均轮转时间 是多少？ (1) FCFS； (2) SJF19、解： (1) FCFS10.53 (2) SJF9.53解：

12、(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、解：在本题中，当两个进程都执行完第一步后，即进 程P1和P2都申请到一个R1资源以后，系统进入不 安全状态。随着两个进程的向前推进，无论哪个进 程执行完第2步，系统都将

13、进入死锁状态。可能到 达的死锁点是：进程P1占有一个单位的R1类资源 及一个单位的R2类资源，P2占有一个单位的R1类 资源，此时系统已经没有空闲资源，而两个进程都 在保持已占有的资源不释放的情况下继续申请资源 ，从而造成死锁。或者是进程P2占有一个单位的 R1类资源及一个单位的R2类资源，P1占有一个单 位的R1类资源，此时系统已经没有空闲资源，而两 个进程都在保持已占有的资源不释放的情况下继续 申请资源，从而造成死锁。 假定进程P1成功执行了第二步，则死锁点的资源 分配图如下所示：P1P2死锁点资源分配图R1R221、生产者-消费者问题中，如果对调生产者进程中的两 个P操作和两个V操作，则

14、可能发生什么情况？ 解：生产者-消费者的同步问题中，如果对调生产者进程中的两个P操作 和两个V操作，那么生产者和消费者的进程分别描述如下：producer() while(生产未完成) 生产一个产品；P(mutex);p(empty);送一个产品到有界缓冲区 ；V(full);V(mutex); consumer() while(还要继续消费) P(full);p(mutex);从有界缓冲区中取产品；V(mutex);V(empty); n由于V操作是释放资源，所以对调V操作的次序无关紧要。而 对调P操作的次序可能导致死锁。n因为对调P操作的次序后，有可能出现这样一种特殊情况：在 某一时刻缓冲

15、区中已经装满了产品，且缓冲区中无进程工作 （这时信号量full=n,empty=0,mutex=1），若系统此时调度 生产者进程运行，生产者生产了一个产品，它执行P(mutex) 并顺利进入临界区（进入临界区后，mutex=0），随后它执 行P(empty)时因没有空缓冲单元而受阻等待，等待消费者进 程进入缓冲区取走产品后释放出缓冲单元；而消费者进程执 行P(full)后再执行P(mutex)的时候，因缓冲区被生产者进程 占据而无法进入。n这样，就形成生产者在占有临界资源的情况下，等待消费者 进程取走产品，而消费者进程又无法进入临界区取走产品的 僵局，此时两进程陷入死锁。2222、假设就绪队列

16、中有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）