操作系统原理-第四章--处理机调度(有答案).docx

《操作系统原理-第四章--处理机调度(有答案).docx》由会员分享，可在线阅读，更多相关《操作系统原理-第四章--处理机调度(有答案).docx（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除第四章 处理机调度4.3 习题4.3.1 选择最合适的答案1某系统采用了银行家算法，则下列叙述正确的是（ ）。A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁2银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（ ）。A.Maxi,j=Allocationi,j+Needi,jB.Needi,j= Allocationi,j+ Maxi,jC.Max

2、i,j= Availablei,j+Needi,jD.Needi,j= Availablei,j+ Maxi,j3下列进程调度算法中，（ ）可能会出现进程长期得不到调度的情况。A.非抢占式静态优先权法B.抢占式静态优先权法C.时间片轮转调度算法D.非抢占式动态优先权法4在下列选项中，属于预防死锁的方法是（ ）。A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法5在下列选项中，属于检测死锁的方法是（ ）。A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法6在下列选项中，属于解除死锁的方法是（ ）。A剥夺资源法 B.资源分配图简化法 C银行家算法 D.资源静

3、态分配法7为了照顾紧迫型作业，应采用（ ）。A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法8在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（ ）相同。A.先来先服务调度算法B.短作业优先调度算法C.时间片轮转调度算法 D.长作业优先调度算法9作业从后备作业到被调度程序选中的时间称为（ ）。A.周转时间 B.响应时间 C.等待调度时间 D.运行时间10资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（ ）不成立。A.互斥条件 B.请求和保持条件 C.不可剥夺条件 D.环路等待条件4.3.2 选

4、择所有正确答案1下列选项中，（ ）可能是非抢占方式进程调度中引起调度的原因。A.当前的运行进程调用阻塞原语而进入阻塞状态 B.当前的运行进程提出申请I/O而阻塞 C.有更高优先级的进程到达而从执行状态变为就绪状态 D.正在执行的进程执行了P原语操作，由于资源不足而阻塞2选择排队作业中等待时间最长的作业被优先调度，该调度算法不可能是（ ）。A.先来先服务调度算法 B.高响应比优先调度算法 C.优先权调度算法 D.短作业优先调度算法3作业控制块JCB连成一串而形成的一个排队队列，该队列称为（ ）。A挂起队列 B.阻塞队列 C.就绪队列 D.后备队列4下列哪个选项描述的时间属于响应时间的一部分（ ）

5、。A.处理机对请求信息进行处理的时间 B.从键盘输入的请求信息传送到处理机的时间 C.所形成的响应回送到终端显示器的时间D.用户查看响应回送到的信息 5下列四个选项描述的时间组成了周转时间，其中可能发生多次的是（ ）。A.等待I/O操作完成的时间 B.作业在外存后备队列上等待作业调度的时间 C.进程在CPU上的执行时间 D.进程在就绪队列上等待进程调度的时间6下面列出的是选择调度方式和算法的4个面向用户的准则。其中，不完全适用于实时系统的准则是（ ）。A.优先权准则B.响应时间快 C.截止时间的保证 D.周转时间短7下面列出了选择调度方式和算法的4个准则。其中，对批处理、分时、实时系统都可以采

6、用的是（ ）。A.周转时间短 B.响应时间快 C.截止时间的保证 D.优先权准则8下列选项中，（ ）是分时系统中确定时间片大小需要考虑的因素。A.各类资源的平衡利用 B.就绪队列中进程的数目C.系统的处理能力D.系统对响应时间的要求9下面列出的选项中，属于可剥夺性资源的有（ ）。A.CPU B.内存 C.磁盘 D.磁带机10在多级队列调度和多级反馈队列调度的叙述中，正确的是（ ）。A.多级反馈队列调度中就绪队列的设置不是象多级队列调度一样按作业性质划分，而是按时间片的大小划分 B.多级队列调度用到优先权，而多级反馈队列调度中没有用到优先权C.多级队列调度中的进程固定在某一个队列中，而多级反馈队

7、列调度中的进程不固定 D.多级队列调度中每个队列按作业性质不同而采用不同的调度算法，而多级反馈队列调度中除了个别队列外，均采用相同的调度算法4.3.3 判断正误，简要说明理由1作业调度能够使作业获得CPU。2在多道程序系统中，系统的现有空闲可用资源能否满足一个后备作业J的资源要求，是选择作业J进入内存的必要条件。3短作业（进程）优先调度算法具有最短的平均周转时间，因此这种算法是最好的算法。4在优先权调度算法中确定静态优先权时，一般说，计算进程的优先权要高于磁盘I/O进程的优先权。5摒弃不可剥夺条件的方法可用于预防多个打印进程死锁的发生。6操作系统处理死锁，只要采用预防、解除、检测、避免之中的一

8、种就足够了。7如果系统在所有进程运行前，一次性地将其在整个运行过程所需的全部资源分配给进程，即所谓“静态分配”法，是可以预防死锁发生的。8多个进程竞争比进程数目少的资源时就可能产生死锁，而当资源数目大于进程数目时就一定不会发生死锁。9在银行家算法中，对某时刻的资源分配情况进行安全分析，如果该时刻状态是安全的，则存在一个安全序列，且这个安全序列是唯一的。10进程调度算法各种各样，但是如果选择不当，就会造成死锁。4.3.4 简答题1高级调度和低级调度的主要任务是什么？为什么要引入中级调度？2在作业调度中需作出哪些决定？3在剥夺调度中，有哪些剥夺原则？4在OS中引起进程调度的主要因素有哪些？5在选择

9、调度方式和调度算法时，应遵循的原则是什么？6在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？7为什么说多级反馈队列能较好地满足各种用户的需要？8在多用户分时系统中，时间片轮转调度的算法在确定时间片的大小时，应考虑哪些因素？9为实现实时调度，对实时系统提出了哪些要求？10目前常用的调度方式和算法，能否应用到实时系统中？11在多处理机系统中，比较有代表性的线程调度方式有哪几种？12试比较自调度和成组调度？13在OS/2中采用哪种调度方式和调度算法？14何为死锁？产生死锁的原因和必要条件是什么？15在解决死锁问题的几个方法中，哪种方法最容易实现？哪种方法使资源的利用率最高？16

10、请详细说明可通过哪些途径预防死锁？17在银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0)，问系统可否将资源分配给它？4.4 习题解答要点 4.4.1 选择最合适的答案1.B 2.B 3.B 4.D5.D 6.A 7.D 8.A 9.C 10.B4.4.2 选择所有正确答案1.ABD 2.BCD 3.D 4.ABC 5.ACD 6.AD 7.D 8.BCD 9.ABC 10.ACD4.4.3 判断题1. 错误作业调度是高级调度。它只能使某作业获得使用CPU的资格。而只有进程调度或线程调度才能使作业真正获得CPU。2. 错误多道系统中的资

11、源分配有两种方法：静态分配：作业调度的功能之一是审查系统能否满足用户作业的资源要求；之二是按照一定的算法选取作业。动态分配：进程所需的资源是在运行中分配的，作业调度并不考虑当前空闲的资源量，只是按照一定的算法选取作业。3.错误前半句话讲的正确，但由此说短作业（进程）优先调度算法是最好的，就不正确了。因为一个算法的好坏要看其是否适于系统的需要而判定。4.错误因为磁盘I/O进程属于系统进程。而系统在确定进程的静态优先权时遵循的原则是：系统进程的优先权高于一般用户进程的优先权（除非用户的进程特别紧迫或重要）5.错误因为摒弃不剥夺条件的方法可预防死锁的发生。6.错误因为，操作系统要兼顾资源的使用效率和

12、安全性两个方面，常见的是，将预防、解除、检测、避免四种处理混合起来使用。举例来说，只有检测死锁而无解除死锁，检测出死锁又有什么用呢？7.正确因为资源的“静态分配”方法，可以摒弃“请求和保持”条件，是可以预防死锁的。8.错误进程是否发生死锁，需要考虑每个进程申请资源的数目、所申请资源的种类、进程推进情况等因素。不能简单地比较进程数目和资源数目就来确定是否死锁。9.错误系统在调用银行家算法进行安全检查时，只要找到一个安全序列就可断定系统是安全的。但安全序列可能不止一个，有的情况下可能是只有一个，有的情况下可能有2个或者更多。10.错误如果进程调度算法选择不当，会造成某些进程的长期等待。我们将这种进

13、程称为“饥饿”进程（长期“饥饿”的极端情况是“饿死”）。“饿死”和“死锁”具有完全不同的含义。4.4.4 简答题1高级调度和低级调度的主要任务以及引入中级调度原因如下：高级调度又称为作业调度。它是批处理系统中使用的一种调度。其主要任务是，按照某种算法从外存的后备队列上选择一个或多个作业调入内存，并为它们创建进程、分配必要的资源，然后再将创建的进程控制块挂入就绪队列上。低级调度又称进程调度。它是距离硬件最近的一级调度。其主要任务是，按照某种算法从就绪队列上选择一个（或多个）进程，使其获得CPU。引入中级调度的目的是为了提高内存利用率和系统吞吐量。其功能是，让那些暂时不能运行的进程不再占用宝贵的内

14、存资源，而是调出到外存上等待。此时的进程状态为挂起状态。当这些进程重新具备运行条件且内存空闲时，由中级调度选择一部分挂起状态的进程调入内存，将其状态变为内存就绪状态。2在作业调度中需作出的决定如下：作业调度需要按照多道程序度（即，最大道数）决定一次接纳多少作业进入内存。如果太少将导致系统资源利用率低，且系统吞吐量低；太多将导致内存空间紧张，系统服务质量下降，使作业运行周期过长。作业调度需要决定接纳哪些作业进入内存。常用的算法是，先来先服务，短作业优先，最高优先级调度、响应比高者优先等。3在剥夺进程调度中，剥夺原则如下：时间片原则。在轮转算法中，CPU轮流为诸多进程服务，每个进程运行完自己的时间

15、片后，系统就将它的CPU剥夺过来，交给下一个进程使用。优先级原则。为紧迫的作业赋予较高的优先级，这种作业到达系统，或者由阻塞状态被唤醒后，若其优先级高于当前运行的进程的优先级，可以剥夺其CPU。短作业（进程）优先原则。若一个作业（进程）到达系统，其运行长度比当前运行的进程长度明显的短，则剥夺它的CPU。4引起进程调度的主要因素主要有：一个进程运行完毕；一个正在运行的进程被阻塞；在抢占式调度中，一个高优先级的进程被创建；在抢占式调度中，一个高优先级进程由阻塞被唤醒；在轮转式调度中，正在运行的进程运行完一个时间片。5在选择调度方式和调度算法时，应遵循的原则如下：面向用户准则。首先，对于用户的紧迫性

16、作业，系统能够及时地处理，不至于运行延误。其次，对于批处理系统，还应追求作业的周转时间短；分时系统中作业的响应时间块；实时系统中作业的截止时间有保证。面向系统准则。系统的吞吐量高，处理机的利用率高，各类系统资源能够得到平衡利用。6批处理系统、分时系统和实时系统中的主要调度算法如下：批处理系统中的作业调度算法有先来先服务（FCFS）、短作业优先（SJF）、优先级调度（HPF）和高响应比优先（RF）。批处理系统的进程调度算法有：先进先出（FIFO）、短进程优先（SPF）、优先级调度（PRI）和高响应比优先（RF）。分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。实时

17、系统中只设有进程调度（不设作业调度），其进程调度算法有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求不严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序度，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序度，使优先级低的作业呆在外存的后备队列上。7多级反馈队列能较好地满足各种用户的需要的原因：终端用户的作业一般比较短小精悍，大多数在进入多级队列的第一级队列中后运行一个时间片就可以完成

18、，因而感到满意。批处理作业用户，其作业进入多级队列的第一级队列中后，若作业较短，运行一个时间片就可以完成。对于稍长一些的作业，只需在第二或第三队列上各执行一个时间片就可完成，因而感到满意。对于长作业来说，它将依次在第1，2，n个队列上运行，不会因作业太长而长期得不到处理。8在多用户分时时间片长度的选择上，既要保证交互性，又要保证系统的效率。系统对响应时间T的要求（一般应小于等于23秒钟）；就绪队列中的进程数目N（N与终端上的用户数目有关）；系统的处理能力，一个时间片的长度q应能保证用户的大部分常用命令可处理完；进程的转换时间p；三者的关系可表示为：T=N(q+p)。9对实时系统提出了要求如下：

19、任务要提供必要的调度信息：主要包括：开工的最后期限或完工的最后期限、处理时间长度、优先级、就绪时间，以及资源需求。采用适当的调度方式：如果实时任务的运行长度较长且时间要求严格，那么实时系统应采用抢占式调度；如果所有的实时任务都比较小，且预知任务的开工最后期限，也可以采用非剥夺式调度。能够快速响应外部中断：这要求，硬件上要有较高的中断机制，软件上要使“封中”的时间间隔尽量短，以免贻误时机。快速的任务分派能力：尽量减少任务切换时间开销，使得一个任务完成后可以较快地切换到下一个任务去。10抢占方式和非抢占方式都可以用于实时系统中。能够使用的算法有：轮转算法（RR）和优先级调度算法（HPF）；不可以使

20、用的算法有：先进先出（FIFO）和短进程优先算法（SPF）。11在多处理机系统中，有代表性的线程调度方式有：自调度方式：诸多CPU可以共享同一就绪队列，从中获取就绪线程运行。成组调度方式：由系统将若干相关的线程同时分配到多台CPU上运行。线程与CPU一一对应。专用处理机分配方式：将若干同属于一个应用程序的线程分配到一组CPU上。让这组CPU专门处理它们。12调度方式的比较如下：自调度方式中，就绪队列与单机的相同，调度算法也与之相同。系统没有集中调度机制，任何CPU都可调用系统的调度例程去选择一个线程。只要就绪队列不空，就不会有空闲的CPU。它存在的问题是，多CPU共享一个就绪队列将产生瓶颈；各

21、线程在其生命周期中可能要换好几台CPU，每次更换都要将CPU中的高速缓存（Cache）重新拷入现场数据，造成效率低下；由于合作的一组线程很难同时获得CPU，一些运行的线程只好阻塞等待未获得CPU的线程，所以线程切换频繁。成组调度中，合作的各线程可以同时获得CPU，减少因同步造成的阻塞，减少了切换次数。同时，也可减少调度的频率。13多优先级的抢占式调度，调度的基本单位是线程。优先级分为3类：每一类共细分32级，以31级为最高级。其中：时间紧迫类为最高类，对应的是实时线程及通信管理等；常规类为中档优先类，对应的是一般线程；空闲时间类为较低类，对应的是紧迫度低的线程。调度算法：在同一类的同一优先级中

22、采用轮转算法。每当运行完一个时间片就检查是否有更高优先级线程到来，若有便抢占CPU。14死锁是指多个进程因竞争资源而造成的一种僵持状态。若无外力作用，这些进程都将永远处于阻塞状态，不能再运行下去。产生死锁的原因有：资源不足资源、进程推进次序不当。产生死锁的必要条件有：互斥条件、请求和保持条件、不可剥夺条件、环路等待条件。15预防死锁方法，主要是破坏产生死锁的必要条件。该方法是最容易实现的，但系统资源利用率较低。避免死锁方法，比较实用的有银行家算法（Banker Algorithm）。该算法需要较多的数据结构，实现起来比较困难，但资源利用率最高。（3）检测死锁方法是基于死锁定理设计的，定期运行该

23、算法对系统的状态进行检测，发现死锁便予以解除。其中，需要比较一下各种死锁解除方案的代价，找到代价最小的方案。该方法最难实现，资源利用率较高。16预防死锁方法是破坏产生死锁的必要条件，主要有：摈弃请求和保持条件。采用静态分配方案，一次性地分配给进程所请求的全部资源。进程运行过程中不可再请求新资源。摈弃不剥夺条件。采用动态分配方案，进程运行中可以请求新资源。若进程请求资源不能满足时，就应使其释放已占有的资源。摈弃环路等待条件。采用动态分配方案，要求进程请求资源时，按资源序号递增（或递减）顺序提出。17系统的资源数量为：（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表所示。进程MAX

24、 A B CAllocation A B CNeed A B CAvailable A B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1Request1(1,0,2)：P1请求满足后的占用情况如下。进程MAX A B CAllocation A B CNeed A B CAvailable A B CP07 5 30 1 07 4 32 3 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 3

25、0 0 24 3 1（2）检测系统此刻存在一条安全序列P1，P3，P4，P0，P2。检测过程为：资源可用量（230），不能满足P0，可满足P1。资源可用量（532），不能满足P2，可满足P3。资源可用量（743），可满足P4。资源可用量（745），可满足P0。资源可用量（755），可满足P2。待其完成后使系统的资源可用量达到初始值（10，5，7）。（3）Request4(3,3,0)：P4的请求超过系统当前的可用量（2,3,0），应推迟分配。（4）Request0(0,1,0)：P0请求满足后的占用情况如下：进程MAX A B CAllocation A B CNeed A B CAvaila

26、ble A B CP07 5 30 2 07 3 32 2 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1检测系统此刻存在安全序列P1，P3，P4，P0，P2。资源可用量（220），不能满足P0，可满足P1。资源可用量（522），不能满足P2，可满足P3。资源可用量（733），可满足P4。资源可用量（735），可满足P0。资源可用量（755），可满足P2。待其完成后使系统的资源可用量达到初始值（10，5，7）。FCFS 运行时间 等待时间 周转时间1：120 0 120 12：60 100 160 2.

27、673：30 140 170 5.674：18 160 178 10SJF 运行时间 等待时间 周转时间1 120 0 1204 18 70 883 30 98 1282 60 148 2084.5 考研试题精选及解析1.在银行家算法中，若出现以下资源分配情况：（北京理工2002死锁题）ProcessallocationclaimavailableA B CA B CA B CP00 1 07 5 33 2 2P12 1 03 2 2P23 0 29 0 2P32 1 12 2 2P40 0 24 3 3问：1 该状态是否安全? 2 若进程依次有以下资源请求： p1 资源请求：Request(

28、1,0,2) p4 资源请求：Request(3,3,0)p0 资源请求：Request(0,1,0)则系统如何分配资源可避免死锁?答：（1） 资源分配情况为： 资源进程currentavilCki-Akiallocationcurrentavil+allocationpossibleABCABCABC A B C P1322112210532TRUE P3532011211743TRUE P0743743010753TRUE P27536003021055TRUE P410554310021057TRUE可见存在一个安全序列P1,P3,P0,P2,P4，故为安全状态。 （2） 只需考虑进程P

29、1和P0的资源申请。现在假定进程P1又要申请1个A类资源和2个C类资源，为了判别这个申请能否立即准许，按银行家算法进行检查：l request1(1,0,2) Ck1-Ak1(1,1,2)l request1(1,0,2) Available(3,2,2)此时，系统可用资源向量为(2,2,0)。 进程p0 的资源请求为Request(0,1,0)，按银行家算法进行检查：l request1(0,1,0) Ck1-Ak1(7,4,3)l request1(0,1,0) Available(2,2,0)试分配并修改数据结构，processallocationCki-AkiavailableA B

30、CA B CA B CP00 2 07 3 32 1 0P13 1 20 1 0P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1再用安全性算法检查： 资源进程currentavilCki-Akiallocationcurrentavil+allocationpossibleABCABCABC A B C P1210010312522TRUE P3522011211733TRUE P0733733020753TRUE P27536003021055TRUE P410554310021057TRUE可见存在一个安全序列P1,P3,P0,P2,P4，故为安全状态。可满足进程P

31、1,P0对资源的申请。2.一个操作系统有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使有3个资源。若仅考虑这类资源，该系统有可能产生死锁，为什么？（北京大学1995年死锁题）解：在本题中，若仅考虑这一类资源的分配，则不会产生死锁。因为死锁产生的原因有两点：系统资源不足或进程推进顺序不当。在本题介绍的系统中，进程所要的最大资源数为：20360，而系统中共有该类资源65个，其资源数目已足够系统内的各地进程使用，因此绝不可能发生死锁。3.一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为

32、多少时，系统没有死锁危险，并说明原因。（上海交通大学1999年死锁题）解：当N为1，2，3时，系统没有产生死锁的危险。因为，当系统中只有1个进程时，它最多需要3台磁带机，而系统有8台磁带机，其资源数目已足够系统内的1个进程使用，因此绝不可能发生死锁；当系统中有2个进程时，最多需要6台磁带机，而系统有8台磁带机，其资源数目也足够系统内的2个进程使，因此也不可能发生死锁； 当系统中有3个进程时，在最坏情况下，每个进程都需要3个这样的资源，且假定每个进程都已申请到了2个资源，那么系统中还剩下2个,无论系统为了满足哪个进程的资源申请而将资源分配给该进程，都会因为该进程已获得了它所需要的全部资源而确保它

33、运行完毕,从而可将它占有的3个资源归还给系统,这就保证了其余进程能顺利运行完毕.由此可知当N为1，2，3时，该系统不会由于对这种资源的竞争而产生死锁。4.假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单位），它们被进程P1，P2所共享，且已知两个进程均以下列顺序使用两类资源：申请R1申请R2申请R1释放R1释放R2释放R1试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图。（南开大学1994年死锁题）解：在本题中，当两个进程都执行完第1步后，即进程P1和进程P2都申请到了一个R1类资源时，系统进入不安全状态。随着两个进程的向前推进，无论哪个进程执行完第

34、2步，系统都将进入死锁状态。可能到达的死锁点是：进程P1占有一个单位的R1类资源及一个单位的R2类资源，进程P2占有一个单位的R1类资源，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的情况下继续申请资源，从而造成死锁；P1P2。R1R2或进程P2占有单位的R1类资源及一个单位的R2类资源，进程P1占有一个单位的R1类资源，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的情况下继续申请资源，从而造成死锁。假定进程P1成功执行了第2步，则死锁点的资源分配图如图所示： 图4-5 5. 某系统有同类资源m个，被并发执行的n个进程共享，若每个进程申请该类资源的最大量为x (1x

35、m)，试给出保证系统不产生死锁的n、x、m之间的关系式。解 ： 当每个进程分得资源的最大量x-1个后，只要系统还拥有一个资源时，系统便不会产生死锁，故可推出关系式：n(x-1)+1m。其中，当mn时，x=1。mn时，x=1+(m-1)/n其中， 为取下界、即去掉小数点。6.某系统有同类资源m个，被并发执行的n个进程共享，若每个进程申请该类资源的最大量为x (1xm)，试证明：当n(x-1)+1m时，系统不产生死锁。（西安理工2000死锁题）解 ： 当每个进程分得资源的最大量x-1个后，只要系统还拥有一个资源时，系统便不会产生死锁，故可推出关系式：n(x-1)+1m。其中，当mn时，x=1。mn

36、时，x=1+(m-1)/n其中， 为取下界、即去掉小数点。7.假设系统由相同类型m个资源组成，系统有n个进程，每个进行至少请求一个资源。证明当n个进程最多需要的资源数之和小于m+n时，该系统没有死锁。（国防科大2001死锁题）答：设max （i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知： max(1)+max(n)=(need(1)+need(n)+(alloc(1)+alloc(n)m+n如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去， alloc(1)+ +alloc(n)=

37、m另一方面所有进程将陷入无限等待状态。可以推出 need(1)+ +need(n)n时，w=1+(m-1)/n 其中， 为取下界。 (1) 不会死锁。 (2) 不会死锁。 (3) 可能出现死锁。 (4) 不会死锁。 (5) 可能出现死锁。9.N个进程共享M个资源，每个进程一次只能申请/释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不会产生死锁。（西北工大2000死锁题）答1：设max （i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：max(1)+max

38、(n)=(need(1)+need(n)+(alloc(1)+alloc(n)m+n如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去， alloc(1)+ +alloc(n)=m另一方面所有进程将陷入无限等待状态。可以推出 need(1)+ +need(n)n上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i,need(i)=0,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么，它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。答2：设每个进程对共享资源的最大需求量为x（0xm），由

39、于每个进程最多申请使用x个资源，在最坏情况下，每个进程都得到了（x-1）个资源，并且都需申请最后一个资源。这时系统剩余资源数为：m-n（x-1）。只要系统还有一个资源可用，就可使其中的一个进程获得所需的全部资源，该进程运行结束后释放出它所占用的资源，其他进程的资源需求也可得到全部满足。因此，当m-n（x-1）1时，即x（m+n-1）/n时系统不会发生死锁。进而可得系统中所有进程最大需求量之和nx（m+n-1）时系统不会发生死锁。该题中，所有进程最大需求量之和小于m+n，所以，该系统是死锁无关的。答3：由题意知道， nmm+n 是成立的，等式变换 n(m-1)+nn+m即 n(m-1)m于是有

40、n(m-1)+1m+1或 n(m-1)+1m这说明当n个进程都取得了最大数减1个即(m-1)个时，这时至少系统还有一个资源可分配。故该系统是死锁无关的。10.设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共3个，每个进程至少请求一个资源，它们所需资源求最大量的总和为x，则发生死锁的必要条件是x6。（南京航空航天大学2002死锁题）解：设3个进程各需x1,x2和x3个资源，根据题意，x=x1+x2+x3若发生了死锁，那么，每个进程至还缺个资源，但系统己没有空闲的可分配了、即有：(x1-1)+(x2-1)+(x3-1) 3x1+x2+x3-3 3故有 x-3 3所以 x611.有

41、一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。（北京大学1995年进程调度题）作业名 到达时间 估计运行时间 优先数A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6 (1)列出所有作业进入内存时间及结束时间。 (2)计算平均周转时间。分析：每个作业的运行将经历两级调度：作业调度和进程调度。作业调度采用短作业优先调度算法，进程调度采用基于优先数的抢占式调度算法，高优先级的进程可以抢占系统处理机。只有当作业调度程序将作业装入内存后，方能参与进程调度。本题中的批处理系统是两道作业系统，因此每次只能有两道作业进入系统内存。本题中的作业和进程推进顺序如下：10：00时，A作业到达。因系统的后