《新编操作系统习题与解析》试读：3.3 知识点3：进程死锁

3.3 知识点3：进程死锁 3.3.1 要点归纳 1．死锁的概念 死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态，若无外力作用，这些进程都将无法向前推进。例如，某计算机系统中只有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2所占用，而P2在未释放打印机之前，又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。 归纳起来，产生死锁的两个原因如下：  系统资源不足。这是根本原因，设计操作系统的目的就是使并发进程共享系统资源。  进程推进顺序不当。当多个并发进程在运行中提出对多个不可抢占资源的请求时，若申请和释放资源的顺序恰当，则不会产生死锁；若申请和释放资源的顺序不当，则会产生死锁。 “饥饿”和死锁的主要区别是：“饥饿”并不表示系统一定死锁，进入“饥饿”的进程可能只有一个，而由于循环等待条件而进入死锁的进程却必须大于或等于两个；处于“饥饿”的进程可以是一个就绪进程，而处于死锁的进程则必定是阻塞进程。 2. 死锁的处理策略 目前，用于处理死锁的方法主要有以下几种：  忽略死锁。这种处理方式又称鸵鸟算法，是指像鸵鸟一样对死锁视而不见。不同的人对死锁现象有不同的反应。例如，数学家认为死锁现象完全不能容忍，应不惜代价地防止死锁的发生。而工程师则会问估计多长时间才会出现一次死锁，其他原因的系统故障又是多长时间出现一次，如果死锁平均每5年出现一次，而其他系统故障每月出现一次，那么大多数工程师就不愿意以高昂的代价来消除死锁。对用户来说，他们宁愿仍然出现一次死锁，也不愿有许多条条框框捆住他们的手脚。  预防死锁。通过设置某些限制条件，去破坏产生死锁的4个必要条件中的一个或几个来防止发生死锁。  避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全的状态，从而避免死锁。  检测及解除死锁。通过系统的检测机构及时地检测出死锁，然后采取某种措施解除死锁。 3. 死锁的预防 要想防止死锁的发生，只须破坏产生死锁的4个必要条件之一即可。下面具体分析与这4个条件相关的技术。 （1）互斥条件 为了破坏互斥条件，就要允许多个进程同时访问资源。但是这会受到资源本身固有特性的限制，有些资源根本不能同时访问，只能互斥访问，如打印机就不允许多个进程在其运行期间交替打印数据，打印机只能互斥使用。由此看来，企图通过破坏互斥条件防止死锁的发生是不大可能的。 （2）不剥夺条件 为了破坏不剥夺条件，可以制定这样的策略：一个已获得了某些资源的进程，若新的资源请求不能立即得到满足，则它必须释放所有已获得的资源，以后需要资源时再重新申请。这意味着，一个进程已获得的资源在运行过程中可以被剥夺，从而破坏了不剥夺条件。 该策略实现起来比较复杂，释放已获得的资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。 （3）请求和保持条件 为了破坏请求和保持条件，可以采用静态资源分配法。静态资源分配法要求进程在其运行之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源要求，这样就可以保证系统不会发生死锁。 这种方法既简单又安全，但降低了资源利用率。采用这种方法必须事先知道作业（或进程）需要的全部资源，即使有的资源只在运行后期使用，甚至有的资源在正常运行中根本不用，也不得不预先统一申请，结果使得系统资源不能充分利用。以打印机为例，一个作业可能只在最后完成时才需要打印计算结果，但在作业运行前就把打印机分配给了它，那么在作业整个执行过程中打印机基本处于闲置状态。 （4）循环等待条件 为了破坏循环等待条件，可以采用有序资源分配法。有序资源分配法的实现思想是将系统中的所有资源都按类型赋予一个编号（如打印机为1，磁带机为2等），要求每一个进程均严格按照编号递增的次序来申请资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中，只能申请资源编号排在Ri后面的那些资源（i为资源编号），不能再申请资源编号低于Ri的资源。对资源申请作了这样的限制后，系统中不会再出现几个进程对资源的请求形成环路的情况。 这种方法存在的主要问题是各种资源编号后不宜修改，从而限制了新设备的增加；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费。 4. 死锁的避免 预防死锁的方法中所采取的几种策略，总的说来都对资源的使用施加了较强的限制条件，虽然实现起来较为简单，但却严重地损害了系统性能。在死锁的避免方法中，不对进程申请资源施加限制条件，而是检查进程的资源申请是否会导致系统进入不安全状态，只要能使系统始终处于安全状态，便可以避免死锁的发生。由于该方法对进程使用资源所施加的限制条件较弱，从而可能获得较好的系统性能。 （1）系统安全状态 在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。 如果在某一时刻，系统能按某种顺序如<P1,P2,…,Pn>来为每个进程分配其所需要的资源，直至最大需求，使每个进程都可以顺利运行完成，则称此时的系统状态为安全状态，称序列<P1,P2,…,Pn>为安全序列。若某一时刻系统中不存在一个安全序列，则称此时的系统状态为不安全状态。 虽然并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，便可以避免进入死锁状态。 （2）银行家算法 具有代表性的死锁避免算法是Dijkstra给出的银行家算法，其主要思想是避免系统进入不安全状态，在每次进行资源分配时，首先检查系统是否有足够的资源满足要求，如果有则先进行分配，并对分配后的新状态进行安全性检查，如果新状态安全，则正式分配上述资源，否则就拒绝上述资源，这样它保证系统始终处于安全状态，从而避免死锁现象的发生。为实现银行家算法，系统中必须设置若干数据结构。假定系统中有n个进程（P1,P2,…,Pn），m类资源（R1,R2,…,Rm），银行家算法中使用的数据结构如下：  可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类资源的空闲资源个数，其初始值是系统中所配置的该类资源的个数，其数值随该类资源的分配和回收而动态地改变。如果Available(j)=k，表示系统中现有空闲的Rj类资源k个。  最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中每一个进程对各类资源的最大需求个数。如果Max(i,j)=k，表示进程Pi需要Rj类资源的最大个数为k。  分配矩阵Allocation。这是一个n×m的矩阵，它定义了系统中当前已分配给每一个进程的各类资源个数。如果Allocation(i,j)=k，表示进程Pi当前已分到Rj类资源的个数为k。Allocationi表示进程Pi的分配向量，由矩阵Allocation的第i行构成。  需求矩阵Need。这是一个n×m的矩阵，它定义了系统中每一个进程还需要的各类资源个数。如果Need(i,j)=k，表示进程Pi还需要Rj类资源k个，才能完成其任务。Needi表示进程Pi的需求向量，由矩阵Need的第i行构成。 上述3个矩阵间存在关系： Need(i,j)=Max(i,j)-Allocation(i,j) 银行家算法的实现思想如下：设Requesti是进程Pi的请求向量，Requesti(j)=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti≤Needi，则转向②；否则出错，因为进程所需要的资源个数已超过它所宣布的最大值。 如果Requesti≤Available，则转向③；否则，表示系统中尚无足够的资源满足进程Pi的申请，Pi必须等待。 系统试着把申请的资源分配给进程Pi，并修改下面数据结构中的数值： Available = Available-Requesti; Allocationi = Allocationi + Requesti; Needi = Needi-Requesti; 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试分配作废，恢复原来的资源分配状态，让进程Pi等待。 系统所执行的安全性算法描述如下： 设置如下两个向量。  Work：表示系统可提供给进程继续运行的各类资源的空闲资源个数，它含有m个元素，执行安全性算法开始时，Work=Available。  Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finish(i)=false；当有足够资源分配给进程Pi时，令Finish(i)=true。 从进程集合中找到一个能满足下述条件的进程： Finish(i) == false; Needi≤Work; 如找到则执行③；否则执行④。 当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行： Work=Work + Allocationi ; Finish(i)=true; 然后转向②。 若所有进程的Finish(i)都为true，则表示系统处于安全状态；否则，系统处于不安全状态。 【例3.2】 假定系统中有4个进程P1、P2、P3、P4，3种类型的资源R1、R2、R3，数量分别为9、3、6，在T0时刻的资源分配情况如表3.2所示。试问： （1）T0时刻是否安全？ （2）T0时刻以后，若进程P2发出资源请求Request2(1,0,1)，系统能否将资源分配给它？ （3）在进程P2申请资源后，若P1发出资源请求Request1(1,0,1)，系统能否将资源分配给它？ （4）在进程P1申请资源后，若P3发出资源请求Request3(0,0,1)，系统能否将资源分配给它？ 表3.2 T0时刻的资源分配表 进程 Max Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 P2 P3 P4 3 6 3 4 2 1 1 2 2 3 4 2 1 5 2 0 0 1 1 0 0 1 1 2 2 1 1 4 2 0 0 2 2 2 3 0 1 1 2 解：（1）T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析，可得表3.3所示的T0时刻的安全性分析，从中得知，T0时刻存在着一个安全序列{P2,P1,P3,P4}，故系统是安全的。 表3.3 T0时刻的安全性检查 进程 Work Need Allocation Work+Allocation Finish R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P2 P1 P3 P4 1 6 7 9 1 2 2 3 2 3 3 4 1 2 1 4 0 2 0 2 2 2 3 0 5 1 2 0 1 0 1 0 1 0 1 2 6 7 9 9 2 2 3 3 3 3 4 6 true true true true （2）P2请求资源：P2发出请求向量Request2(1,0,1)，系统按银行家算法进行检查，并执行如下操作。  Request2(1,0,1)≤Need2(1,0,2)  Request2(1,0,1)≤Available(1,1,2) 系统先假定可为P2分配资源，并修改Available、Allocation2、Need2向量，由此形成的资源变化情况如表3.4所示。 表3.4 P2申请资源后的资源分配表 进程 Max Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 P2 P3 P4 3 6 3 4 2 1 1 2 2 3 4 2 1 6 2 0 0 1 1 0 0 2 1 2 2 0 1 4 2 0 0 2 2 1 3 0 0 1 1 再利用安全性算法检查此时系统是否安全，可得如表3.5所示的安全性分析。 表3.5 P2申请资源后的安全性检查 进程 Work Need Allocation Work+Allocation Finish R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P2 P1 P3 P4 0 6 7 9 1 2 2 3 1 3 3 4 0 2 1 4 0 2 0 2 1 2 3 0 6 1 2 0 1 0 1 0 2 0 1 2 6 7 9 9 2 2 3 3 3 3 4 6 true true true true 由所进行的安全性检查得知，可以找到一个安全序列{P2,P1,P3,P4}，因此，系统是安全的，可以立即将P2所申请的资源分配给它。 （3）P1请求资源：P1发出请求向量Request1(1,0,1)，系统按银行家算法进行检查：  Request1(1,0,1)≤Need1(2,2,2)  Request1(1,0,1)＞Available(0,1,1)，让P1等待。 （4）P3请求资源：P3发出请求向量Request3(0,0,1)，系统按银行家算法进行检查：  Request3(0,0,1)≤Need3(1,0,3)  Request3(0,0,1)≤Available(0,1,1) 系统先假定可为P3分配资源，并修改有关数据，如表3.6所示。 再利用安全性算法检查此时系统是否安全。从表3.6中可以看出，可用资源Available(0,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不能分配资源。 表3.6 P3申请资源后的资源分配表 进程 Max Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 P2 P3 P4 3 6 3 4 2 1 1 2 2 3 4 2 1 6 2 0 0 1 1 0 0 2 2 2 2 0 1 4 2 0 0 2 2 1 2 0 0 1 0 5. 死锁检测和解除 前面介绍的死锁预防和死锁避免算法，都是在系统为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供死锁检测和死锁解除的方法。 （1）资源分配图 检测死锁的基本思想是在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。为此，将进程和资源间的申请和分配关系描述成一个有向图，即资源分配图。 资源分配图又称进程资源图，该图由一组节点N和一组边E所构成，具有下述形式的定义和限制：  N被分成两个互斥的子集，一个是进程节点子集P={p1,p2,…,pn}，另一个是资源节点子集R={r1,r2,…,rm}，N=P∪R。在如图3.35所示的例子中，P={p1,p2}，R={r1,r2}，N={p1,p2}∪{r1,r2}。  凡属于E中的一条边e∈E，都连接着P中的一个节点pi和R中的一个节点rj，e={pi,rj}是资源请求边，由进程节点pi指向资源节点rj，它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边，由资源节点rj指向进程节点pi，它表示把一个单位的rj资源分配给进程pi。在图3.35中，有两条资源请求边和4条资源分配边。 通常，用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，用方框中的一个小圆圈代表一类资源中的一个资源。此时，资源请求边由进程指向方框中的一个资源，分配边始于方框中的一个资源。 图3.35 资源分配图 （2）死锁的定理 可以使用将资源分配图简化的方法，来检测系统状态S是否是死锁状态。简化方法如下： 在资源分配图中，找出一个既不阻塞又非孤立的进程节点pi（即从进程集合中找到一个有边与它相连，且资源申请数量小于系统中已有空闲资源数量的进程）。因进程pi获得了它所需要的全部资源，它能继续运行直至完成，然后释放它所占有的所有资源。这相当于消去pi的所有请求边和分配边，使之成为孤立的节点。在图3.35中，进程p1是一个既不阻塞又非孤立的进程节点，将p1的两条分配边和一条请求边消去，便形成了如图3.36（a）所示的情况。 进程pi释放资源后，可以唤醒因等待这些资源而阻塞的进程，原来阻塞的进程可能变为非阻塞进程。图3.35中的进程p2原为阻塞进程，但在图3.36（a）中变成了非阻塞进程。根据①中的化简办法，消去两条分配边和一条请求边，就形成了如图3.36（b）所示的情况。 重复上述过程对资源分配图进行化简，直到找不出一个既不阻塞又非孤立的进程节点为止。若能消去图中所有的边，使所有进程节点都成为孤立节点，则称该图是可完全化简的，否则称该图是不可完全化简的。 图3.36 资源分配图的化简 可以证明所有的化简顺序将得到相同的不可化简图。S为死锁状态的条件是：S状态的资源分配图不可完全化简，该定理称为死锁定理。 （3）死锁的检测算法 死锁检测的思想是考查某一时刻的系统状态是否合理，即是否存在一组可以实现的系统状态，能使所有进程都得到它们所申请的资源而运行结束，其实现算法的思想如下：获得某时刻t系统中各类可利用资源的个数w(t)，对于系统中的一组进程{P1,P2,…,Pn}，找出那些对各类资源请求个数均小于系统现有的各类可利用资源个数的进程，这样的进程可以获得它们所需要的全部资源并运行结束，当它们运行结束后将释放所占有的全部资源，从而使可用资源个数增加，将这样的进程加入到可运行结束的进程序列L中（检测开始时，L为空），然后对剩下的进程再作上述考查。如果一组进程{P1,P2,…,Pn}中有几个进程不属于序列L中，那么它们将陷入死锁状态。 从死锁检测算法的实现思想中可以看出，死锁检测算法比较复杂，因而需要确定何时进行死锁检测。一种实现方法是每次分配资源后进行死锁检测，这样能尽早发现死锁，但会花费大量的CPU时间。另一种方法是定期检查，如每隔一段时间检查一次，或者当CPU使用率下降到某个下限值时进行检查。 （4）死锁的解除 一旦检测出系统中出现了死锁，就应将陷入死锁的进程从死锁状态中解脱出来，常用的解除死锁方法有如下两种：  资源剥夺法：当发现死锁后，从其他进程那里剥夺足够数量的资源给死锁进程，以解除死锁状态。  撤销进程法：最简单的方法是撤销全部死锁进程，使系统恢复到正常状态，但这种做法付出的代价太大。另一方法是按照某种顺序逐个撤销死锁进程，直到有足够的资源供其他未被撤销的进程使用，消除死锁状态为止。 3.3.2 例题解析 1. 单项选择题 【例3-3-1】在操作系统中，死锁出现是指 。 A. 计算机系统发生重大故障 B. 资源个数远远小于进程数 C. 若干进程因竞争资源而无限等待其他进程释放已占有的资源 D. 进程同时申请的资源数超过资源总数 解：死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态，若无外力作用，这些进程都将无法向前推进。本题答案为C。 【例3-3-2】在 的情况下，系统出现死锁。 A. 计算机系统发生了重大故障 B. 有多个封锁的进程同时存在 C. 若干进程因竞争资源而无休止地相互等待他方释放已占有的资源 D. 资源数远远小于进程数或进程同时申请的资源数远远超过资源总数 解：解释同上例。本题答案为C。 【例3-3-3】当出现 情况下，系统可能出现死锁。 A. 进程释放资源 B. 一个进程进入死循环 C. 多个进程竞争资源出现了循环等待 D. 多个进程竞争共享型设备 解：循环等待是出现死锁的条件之一。本题答案为C。 【例3-3-4】为多道程序提供的可共享资源不足时可能出现死锁。但是在进程之间不适当的 也可能产生死锁。 A. 进程优先权 B. 资源的线性分配 C. 进程推进顺序 D. 分配队列优先权 解：产生死锁的原因是系统资源不足及进程推进顺序不正确。本题答案为C。 【例3-3-5】采用资源剥夺法可以解除死锁，还可以采用 方法解除死锁。 A. 执行并行操作 B. 撤销进程 C. 拒绝分配新资源 D. 修改信号量 解：解除死锁有资源剥夺法和撤销进程法，本题答案为B。 【例3-3-6】若系统在分配资源时不加以特别的限制，则可采用死锁检测的方法来解决死锁问题。所以该系统 。 A. 提高了资源利用率 B. 不会发生死锁 C. 有时要抢夺某进程的资源进行再分配 D. 能加快进程的执行速度 解：其中破坏死锁的条件之一只有选项C。本题答案为C。 【例3-3-7】死锁产生的原因之一是 。 A. 系统中没有采用SPOOLing技术 B. 使用的P、V操作过多 C. 有共享资源存在 D. 资源分配不当 解：资源分配不当是死锁产生的原因之一。本题答案为D。 【例3-3-8】产生死锁的4个必要条件是：互斥、 、循环等待和不剥夺。 A. 请求与阻塞 B. 请求与保持 C. 请求与释放 D. 释放与阻塞 解：产生死锁的4个必要条件是互斥、请求与保持、不剥夺和循环等待。本题答案为B。 【例3-3-9】一个进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁必要条件的 。 A. 互斥条件 B. 请求和释放条件 C. 不剥夺条件 D. 循环等待条件 解：C。 【例3-3-10】死锁的预防是根据 而采取措施实现的。 A. 配置足够的系统资源 B. 使进程的推进顺序合理 C. 破坏死锁的4个必要条件之一 D. 防止系统进入不安全状态 解：C。 【例3-3-11】资源的有序分配策略可以破坏死锁的 条件。 A. 互斥 B. 请求和保持 C. 不剥夺 D. 循环等待 解：有序资源分配法的实现思想是将系统中的所有资源都按类型赋予一个编号（如打印机为1，磁带机为2等），要求每一个进程均严格按照编号递增的次序来申请资源，同类资源一次申请完。这样不会造成循环等待。本题答案为D。 【例3-3-12】发生死锁的必要条件有4个，要防止死锁的发生，可以通过破坏这4个必要条件之一来实现，但破坏 条件是不太实际的。 A. 互斥 B. 不可抢占 C. 部分分配 D. 循环等待 解：互斥条件是设备本身固有的特性，有些设备只能互斥访问。本题答案为A。 【例3-3-13】某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台。当N的取值不超过 时，系统不会发生死锁。 A. 4 B. 5 C. 6 D. 7 解：当每个进程都获得了2台打印机且系统中剩余打印机不少于1台时，系统不会发生死锁，即11-2N≥1，由此知N≤5。本题答案为B。 【例3-3-14】银行家算法在解决死锁问题中是用于 的。 A. 预防死锁 B. 避免死锁 C. 检测死锁 D. 解除死锁 解：银行家算法用于避免死锁。本题答案为B。 【例3-3-15】某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是 。 A. 9 B. 10 C. 11 D. 12 解：因系统中存在3个进程，且都需要同类资源4个，当系统中资源数等于10时，无论怎样分配资源，其中至少有一个进程可以获得4个资源，该进程可以顺利运行完毕，从而可以将分配给它的资源归还给系统，其他进程也能顺利执行完成。若系统中资源数小于10，不妨设系统中有9个资源且每个进程都已获得3个资源，此时系统中已无空闲资源，当其中的任何一个进程再次申请资源时将进入等待状态，其他进程的情况类似，此时出现死锁。本题答案为B。 【例3-3-16】在下列解决死锁的方法中，属于死锁预防策略的是 。 A. 银行家算法 B. 有序资源分配法 C. 死锁检测法 D. 资源分配图化简法 解：有序资源分配法是死锁预防策略。本题答案为B。 【例3-3-17】死锁定理是用于处理死锁的 方法。 A. 预防死锁 B. 避免死锁 C. 检测死锁 D. 解除死锁 解：死锁定理是用于检测死锁的方法。本题答案为C。 【例3-3-18】以下关于预防死锁的论述中正确的是 。 A. 由于产生死锁的基本原因是系统资源不足，因而预防死锁的有效方法是根据系统规模配置足够的系统资源 B. 由于产生死锁的另一种基本原因是进程推进顺序不当，因而预防死锁的有效方法是使进程的推进顺序合法 C. 因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的有效方法是防止系统进入不安全状态 D. 可以通过破坏产生死锁的4个必要条件之一或其中几个的方法来预防发生死锁 解：D。 2. 填空题 【例3-3-19】计算机系统产生死锁的根本原因是 ① 和 ② 。 解：本题答案为：①资源有限 ②操作不当。 【例3-3-20】目前抢占式的分配策略只适合于 ① 和 ② 。 解：本题答案为：①主存空间 ②CPU。 【例3-3-21】两个进程争夺同一个资源时， 产生死锁。 解：两个进程争夺同一个资源时，不一定产生死锁，这与它们申请资源的顺序有关。本题答案为：不一定。 【例3-3-22】产生死锁的4个必要条件是 ① 、 ② 、 ③ 和 ④ 。 解：本题答案为：①互斥条件 ②不可剥夺条件 ③请求与保持条件 ④循环等待条件。 【例3-3-23】解决死锁的方法分为 ① 、 ② 、 ③ 和 ④ 。 解：本题答案为：①死锁的预防 ②死锁的避免 ③死锁的检测 ④死锁的解除。 【例3-3-24】避免死锁的实质是 。 解：本题答案为：如何使系统不进入不安全状态。 【例3-3-25】只要能保持系统处于安全状态就可 的发生。 解：本题答案为：避免死锁。 【例3-3-26】当若干进程需求资源的总数大于系统能提供的资源数时，进程间就会出现竞争资源的现象，如果对进程竞争的资源 就会引起死锁。 解：本题答案为：管理或分配不当。 【例3-3-27】如果资源分配图中有环路，且每个资源类中只有一个资源，则环路中的进程都 。 解：本题答案为：处于死锁状态。 【例3-3-28】如果操作系统能保证所有的进程在有限时间内得到需要的全部资源，则称系统处于 。 解：本题答案为：安全状态。 【例3-3-29】设系统有N（N>2）个进程，则系统中最不可能的是有 个进程处于死锁状态。 解：在系统中两个或多个进程无限期地等待永远不会发生的条件，称此系统处于死锁状态，不可能只有一个进程处于死锁状态。本题答案为：1。 【例3-3-30】可以证明，m个同类资源被n个进程共享时，只要不等式 成立，则系统一定不会出现死锁，其中x为每个进程申请该类资源的最大数。 解：本题答案为：n(x-1)+1≤m。 【例3-3-31】操作系统中要兼顾资源的使用效率和安全可靠，对不同的资源采用不同的分配策略，往往采用死锁的 ① 、避免和 ② 的混合策略。 解：本题答案为：①防止 ②检测。 【例3-3-32】解除死锁的方法有两种，一种是 ① 一个或几个进程的执行以破坏循环等待，另一种是从涉及死锁的进程中 ② 。 解：本题答案为：①终止 ②抢夺资源。 【例3-3-33】如果资源分配图中无环路，则系统中 发生。 解：本题答案为：没有死锁。 3. 判断题 【例3-3-34】判断以下叙述的正确性。 （1）当进程数大于资源数时，进程竞争资源必然产生死锁。 （2）死锁预防是排除死锁的静态策略。 （3）产生死锁后，系统未必处于不安全状态。 （4）系统处于不安全状态不一定是死锁状态。 （5）系统存在安全序列时，一定不会有死锁发生。 （6）系统进入不安全状态时，必定会产生死锁。 （7）导致死锁的4个必要条件在死锁时会同时发生。 （8）若想预防死锁，4个必要条件必须同时具备。 （9）银行家算法是防止死锁发生的方法之一。 （10）一旦出现死锁，所有进程都不能运行。 （11）所有进程都阻塞时系统一定陷入死锁。 （12）有m个进程的操作系统出现死锁时，死锁进程的个数为1<k≤m。 （13）参与死锁的进程至少有两个已经占有资源。 （14）如果资源分配图中存在环路，则系统一定存在死锁。 解：（1）错误。当进程数大于资源数时，进程竞争资源不一定产生死锁。 （2）正确。 （3）错误。产生死锁后，系统必然处于不安全状态。 （4）正确。 （5）正确。 （6）错误。系统进入不安全状态时，不一定产生死锁。 （7）正确。 （8）错误。若想预防死锁，只须破坏4个必要条件之一即可。 （9）错误。银行家算法是避免死锁的方法之一。 （10）错误。部分进程出现死锁，其他进程仍可运行。 （11）错误。所有进程都阻塞时，系统不一定陷入死锁，可能是由于所有进程等待某一I/O事件引起的。 （12）正确。 （13）正确。 （14）错误。资源分配图中存在环路，整个系统不一定存在死锁 4. 问答题 【例3-3-35】什么是死锁，产生死锁的原因是什么？ 解：所谓死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态，若无外力作用，这些进程都将无法向前推进。 产生死锁的原因：一是由于多进程共享的资源不足而引起竞争资源；二是由于进程在运行过程中具有异步性特征，进程推进顺序非法。 【例3-3-36】产生死锁的必要条件是什么？解决死锁问题常采用哪几种措施？ 解：产生死锁的必要条件如下：  互斥条件。指在一段时间内某资源仅为一个进程所占有。  不剥夺条件。指进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，而只能由该进程自己释放。  请求和保持条件。指进程每次申请它所需要的一部分资源，在等待分配新资源的同时，进程继续占有已分配到的资源。  循环等待条件。指存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被链中下一个进程所请求。 解决死锁问题常采用的措施有：  死锁的预防。通过破坏死锁产生的必要条件中的后三条之一来预防死锁的发生。  死锁的避免。在资源动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。  死锁的检测及解除。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。 【例3-3-37】在某一时刻，系统中是否可能出现既无运行态进程又无就绪态进程？若可能，在什么情况下会产生？ 解：有可能。例如在系统死锁的状态下，进程处于占有等待资源的状态，应当既不属于运行态，也不属于就绪态；或者在进程都处于阻塞状态等待I/O完成时，这些进程既不属于运行态，也不属于就绪态。 【例3-3-38】进程死锁与“饥饿”之间有何相同点和不同点？ 解：进程“饥饿”与死锁有一定联系：两者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面：  从进程状态考虑，死锁进程都处于等待状态，忙而等待（处于运行或就绪状态）的进程并非处于等待状态，但却可能被“饿死”。  死锁进程等待永远不会被释放的资源，“饥饿”进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上限（排队等待或忙而等待）。  死锁一定发生了循环等待，而“饥饿”则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程“饿死”。  死锁一定涉及多个进程，而“饥饿”或被“饿死”的进程可能只有一个。 进程“饥饿”和“饿死”与资源分配策略有关，因而防止“饥饿”与“饿死”可从公平性考虑，确保所有进程不被忽视，如FCFS分配算法。 【例3-3-39】简述防止死锁的分配策略中各自存在哪些缺点。 解：在防止死锁的分配策略中，有的只适用于某些资源的分配，有的则会影响资源的使用效率。例如，抢占式分配目前只适合于对CPU和主存资源的分配；静态分配策略把资源预先分配给进程，而这些进程占用了资源但可能在一段时间内并不使用它，这时其他想使用这些资源的进程又因得不到而等待，降低了资源的利用率；采用按序分配时各进程要求使用资源的次序往往不能与系统安排的次序一致，但申请资源时必须按编号的次序来申请，可能出现先申请到的资源很长一段时间闲置不用，也降低了资源的利用率。 【例3-3-40】为什么说不能通过破坏“互斥条件”来预防死锁。 解：破坏互斥条件，即允许多个进程同时访问资源。但这受到资源本身的使用方法所决定，有些资源必须互斥访问，不能同时访问，如几个进程同时使用打印机，而打印机的使用必须是互斥的。所以企图通过破坏互斥条件来防止死锁是不太实际的。 【例3-3-41】下面关于死锁问题的叙述哪些是正确的，哪些是错误的？说明原因。 （1）参与死锁的所有进程都占有资源。 （2）参与死锁的所有进程中至少有两个进程占有资源。 （3）死锁只发生在无关进程之间。 （4）死锁可发生在任意进程之间。 解：（1）是错误的，应该是参与死锁的所有进程都等待资源。如图3.37所示，参与的进程有P1、P2、P3和P4，尽管P3、P4不占有资源，但也陷入死锁。 （2）是正确的。参与死锁的进程至少有两个，设为P1和P2，典型的死锁情况是P1占有资源R1而等待资源R2，P2占有资源R2而等待资源R1。 （3）是错误的。死锁也可能发生在相关进程之间，如死锁的两个进程P1和P2也可能是相关进程（如同步或互斥）。 （4）是正确的。死锁既可能发生在相关进程之间，也可能发生在无关进程之间，即死锁可发生在任意进程之间。 图3.37 一个资源分配图 【例3-3-42】设系统中仅有一类数量为M的独占型资源，系统中N个进程竞争该类资源，其中各进程对该类资源的最大需求量为W，当M、N、W分别取下列值时，试判断哪些情况会发生死锁，为什么？ （1）M2，N=2，W=1 （2）M=3，N=2，W=2 （3）M=3，N=2，W=3 （4）M=5，N=3，W=2 （5）M=6，N=3，W=3 解：在资源分配系统中，死锁发生的原因是由于多个进程共享有限的独占型资源。当多个进程占有了部分资源又需要更多的资源时，就可能形成循环等待链而导致死锁。 假设系统中的某种资源的个数为M，共享该资源的进程数为N，每个进程对该资源的最大需求量为W。最极端的资源分配情况是：每个进程都已经占有了W-1个资源，同时都需要再分配一个资源，这时如果要保证不发生死锁，系统中必须至少还有一个可分配的资源，即M满足关系式：M≥N(W-1)+1。 因此保证系统不会发生死锁的最小M值为：M=N(W-1)+1。 （1）N(W-1)+1=2×0+1=1，而M=3，即M≥N(W-1)+1成立，故不会出现死锁。 （2）N(W-1)+1=2×1+1=3，而M=3，即M≥N(W-1)+1成立，故不会出现死锁。 （3）N(W-1)+1=2×2+1=5，而M=3，即M≥N(W-1)+1不成立，故可能出现死锁。出现死锁的情况是：两个进程一个占用2个资源，一个占用1个资源，同时都需要再分配资源。 （4）N(W-1)+1=3×1+1=4，而M=5，即M≥N(W-1)+1成立，故不会出现死锁。 （5）N(W-1)+1=3×2+1=7，而M=6，即M≥N(W-1)+1不成立，故可能出现死锁。出现死锁的情况是：3个进程都已经占有了2个资源，同时都需要再分配一个资源。 【例3-3-43】一台计算机有8台磁带机。它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险，并说明原因。 解：当N为1、2、3时，系统没有产生死锁的危险。因为，当系统中只有1个进程时，它最多需要3台磁带机，而系统有8台磁带机，其资源个数已足够系统内的1个进程使用，因此绝不可能发生死锁；当系统中有2个进程时，最多需要6台磁带机，而系统有8台磁带机，其资源个数也足够系统内的2个进程使用，因此也不可能发生死锁；当系统中有3个进程时，无论系统如何分配资源，3个进程中必有进程可以获得3台磁带机，该进程已获得了它所需要的全部资源并将顺利运行完毕，从而可将它占有的3个资源归还给系统，这就保证了其余进程能顺利运行完毕。当N＞3时，若资源分配及释放顺序不当时，系统有可能出现死锁。 由此可知，当N为1、2、3时，该系统不会由于对这种资源的竞争而产生死锁。 【例3-3-44】回答以下问题： （1）3个进程共享4个同类型资源，每个进程最大需要两个资源，请问该系统是否会因为竞争该资源而死锁？ （2）n个进程（编号为1～n）共享m个同类资源，若每个进程都需要用该类资源，且各进程最大需求量之和小于m+n，试证明这个系统不会因为竞争该资源而发生死锁。 Max(1)+…+Max(n)=Need(1)+…+Need(n)+Alloc(1)+…+Alloc(n)<m+n （3）在（2）中，如果没有“每个进程都需要用该类资源”的限制，情况又会如何？ 解：（1）该系统不会因为竞争该资源而死锁。因为必有一个进程获得两个资源，故能顺利完成，并释放给其他进程使用，使它们也顺利完成。 （2）根据题意有：Need(i)>0， <m+n 若系统进入死锁状态，则意味有一个以上进程因申请不到资源而无限阻塞，而m个资源已全部分配出去，即： ＝m。 因此， = - <m+n-m=n，即 <n。 这样，至少存在一个进程，其Need(i)≤0，这显然与题意不符，所以该系统不可能因竞争该类资源而进入死锁状态。 （3）此时系统可能发生死锁，如n=4，m=3时，若进程P1的Max为0，而其余3个进程P2、P3、P4的Max都为2，则仍然满足最大需求量之和（即6）小于m+n（即7）的要求，但当除P1以外的其余3个进程P2、P3、P4各得到一个资源时，这3个进程将进入死锁状态。 【例3-3-45】Dijkstra于1965年提出的银行家算法，其主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？ 解：银行家算法是避免死锁的一种方法，其实现思想是：允许进程动态地申请资源，系统在每次实施资源分配之前，先计算资源分配的安全性，若此次资源分配安全（即资源分配后，系统能按某种顺序来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利的完成），便将资源分配给进程，否则不分配资源，让进程等待。 银行家算法具有较好的理论意义，但在实际系统中却难以实施。其原因是：难以预先获得进程申请的最大资源数；运行过程中进程的个数是不断变化的，所以银行家算法难以用来解决实际中的死锁问题。 【例3-3-46】一个系统具有150个存储单元，在T0时刻按表3.7所示分配给3个进程。 表3.7 3个进程分配情况 进程 最大需求存储单元 当前已分配单元数 P1 70 25 P2 60 40 P3 60 45 对下列请求应用银行家算法分析判断是否安全？ （1）第4个进程P4到达，最大需求60个存储单元，当前请求分配25个单元。 （2）第4个进程P4到达，最大需求50个存储单元，当前请求分配35个单元。 如果是安全的，请给出一个可能的进程安全执行序列；如果不是安全的，请说明原因。 解：（1）计算得到T0时刻的资源分配表如表3.8所示，剩余单元数=150- (25+40+45)=40。此时40不小于P4进程请求的单元数25。将25分配给P4进程，还余15个单元，将其分配给P3进程，此时刻的安全性检测表如表3.9所示，得到一个安全序列{P3,P2,P1,P4}（结果不唯一）。 表3.8 T0时刻的资源分配表 进程 Max Allocation Need Available P1 70 25 45 40 P2 60 40 20 P3 60 45 15 P4 60 表3.9 安全性检测表 进程 Max Work Need Allocation Work+Allocation Finish P3 60 15 15 45 60 true P2 60 60 20 40 100 true P1 70 100 45 25 125 true P4 60 125 35 25 150 true （2）此时的剩余单元数=150-(25+40+45)=40。此时40不小于P4进程请求的单元数35，将其35个单元分配给P4进程，余下5个单元，其资源分配表如表3.10所示，4个进程都不够分配，找不到一个安全序列，所以是不安全状态。 表3.10 T0时刻的资源分配表 进程 Max Allocation Need Available P1 70 25 45 5 P2 60 40 20 P3 60 45 15 P4 50 35 15 【例3-3-47】若系统运行中出现如表3.11所示的资源分配情况，该系统是否安全? 如果进程P2此时提出资源申请（1,2,2,2），系统能否将资源分配给它？为什么？ 解：（1）利用安全性算法对此刻的资源分配情况进行分析，可得到如表3.12所示的安全性检测情况，从该表中可以看出，此时存在一个安全序列{P0,P3,P4,P1,P2}，故该系统是安全的。 表3.11 系统资源分配表 进程 Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 表3.12 安全性检测表 进程 Work Need Allocation Work+Allocation Finish P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 true P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 true P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10 true P1 1 9 9 10 1 7 5 0 1 0 0 0 2 9 9 10 true P2 2 9 9 10 2 3 5 6 1 3 5 4 3 12 14 14 true （2）P2提出请求（1,2,2,2），按银行家算法进行检查：  Request2(1,2,2,2)≤Need2(2,3,5,6)  Request2(1,2,2,2)≤Available(1,6,2,2) 试分配并修改相应的数据结构，由此形成的资源分配情况如表3.13所示。 表3.13 P2申请资源后的资源分配表 进程 Allocation Need Available P0 0 0 3 2 0 0 1 2 0 4 0 0 P1 1 0 0 0 1 7 5 0 P2 2 5 7 6 1 1 3 4 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 再利用安全性算法检查系统是否安全，可利用资源Available(0,4,0,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不能将资源分配给P2。 【例3-3-48】有相同类型的5个资源被4个进程所共享，且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。 解：该系统不会由于对这种资源的竞争而产生死锁。因为每个进程最多需要2个这样的资源，无论系统如何分配资源，4个进程中必有一个进程可以获得2个资源，该进程将顺利运行完毕，从而可以将它占有的2个资源归还给系统，同理其余3个进程也能顺利运行完毕。由此可知，该系统不会由于对这种资源的竞争而产生死锁。 【例3-3-49】现有某类资源12个，供3个进程共享。假定进程A已占1个资源，其最大需求4个，进程B已占4个资源，其最大需求6个，进程C已占5个资源，其最大需求8个。当进程都请求尚需的资源时，系统应按怎样的次序为它们分配以保证不发生死锁，并解释之。 解：资源有12个，已分配10个，还剩下2个，进程B正好还需要2个，应先为进程B分配，进程B执行结束归还资源后，再为进程A和C分配资源。因系统的12个资源已分配了10个，剩下的2个资源不能满足进程A和C的需求，而能满足B的最大需求，故先分配给进程B，当它执行结束归还6个资源后，系统的资源就能满足进程A和C的需求，故均能执行结束，系统不会发生死锁。 【例3-3-50】设系统中有3种类型的资源（A、B和C）和5个进程P1、P2、P3、P4、P5，A资源的数量为17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如表3.14所示。系统采用银行家算法实施死锁避免策略。 表3.14 T0时刻系统状态 进程 最大资源需求量 已分配资源数量 A B C A B C P1 5 5 9 2 1 2 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 剩余资源数 A B C 2 3 3 （1）T0时刻是否为安全状态？若是，请给出安全序列。 （2）若在T0时刻进程P2请求资源（0,3,4），是否能实施资源分配？为什么？ （3）在（2）的基础上，若进程P4请求资源（2,0,1），是否能实施资源分配？为什么？ （4）在（3）的基础上，若进程P1请求资源（0,2,0），是否能实施资源分配？为什么？ 解：由题目所给出的最大资源需求量和已分配资源数量，可以计算出T0时刻各进程的资源需求量Need，Need最大资源需求量－已分配资源数量，如表3.15所示。 表3.15 T0时刻的资源分配表 进程 Allocation Need Available A B C A B C A B C P1 2 1 2 3 4 7 2 3 3 P2 4 0 2 1 3 4 P3 4 0 5 0 0 6 P4 2 0 4 2 2 1 P5 3 1 4 1 1 0 （1）利用银行家算法对T0时刻的资源分配情况进行分析，可得此时刻的安全性分析情况，如表3.16所示。 表3.16 T0时刻的安全性检测表 进程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P5 2 3 3 1 1 0 3 1 4 5 4 7 true P4 5 4 7 2 2 1 2 0 4 7 4 11 true P3 7 4 11 0 0 6 4 0 5 11 4 16 true P2 11 4 16 1 3 4 4 0 2 15 4 18 true P1 15 4 18 3 4 7 2 1 2 17 5 20 true 从T0时刻的安全性分析中可以看出，存在一个安全序列{P5,P4,P3,P2,P1}，故T0时刻的状态是安全的。 （2）若在T0时刻进程P2请求资源（0,3,4），因请求资源数（0,3,4）大于剩余资源数（2,3,3），所以不能分配。 （3）在（2）的基础上，若进程P4请求资源（2,0,1），按银行家算法进行检查：  P4请求资源（2,0,1）≤ P4资源需求量（2,2,1）  P4请求资源（2,0,1）≤ 剩余资源数（2,3,3） 试分配并修改相应的数据结构，由此形成的资源分配情况如表3.17所示。 再利用安全性算法检查系统是否安全，可得到如表3.18所示的安全性检测表。 表3.17 P4请求资源后的资源分配表 进程 Allocation Need Available A B C A B C A B C P1 2 1 2 3 4 7 0 3 2 P2 4 0 2 1 3 4 P3 4 0 5 0 0 6 P4 4 0 5 0 2 0 P5 3 1 4 1 1 0 表3.18 P4请求资源后的安全性检测表 进程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P4 0 3 2 0 2 0 4 0 5 4 3 7 true P5 4 3 7 1 1 0 3 1 4 7 4 11 true P3 7 4 11 0 0 6 4 0 5 11 4 16 true P2 11 4 16 1 3 4 4 0 2 15 4 18 true P1 15 4 18 3 4 7 2 1 2 17 5 20 true 从表3.23中可以看出，此时存在一个安全序列{P4,P5,P3,P2,P1}，故该状态是安全的，可以立即将P4所申请的资源分配给它。 （4）在（3）的基础上，若进程P1请求资源（0,2,0），按银行家算法进行检查：  P1请求资源（0,2,0）≤ P1资源需求量（3,4,7）  P1请求资源（0,2,0）≤ 剩余资源数（0,3,2） 试分配并修改相应的数据结构，由此形成的资源分配情况如表3.19所示。 再利用安全性算法检查系统是否安全，可用资源Available(0,1,2)已不能满足任何进程的资源需求，故系统进入不安全状态，此时系统不能将资源分配给P1。 表3.19 P1请求资源后的资源分配表 进程 Allocation Need Available A B C A B C A B C P1 2 3 2 3 2 7 0 1 2 P2 4 0 2 1 3 4 P3 4 0 5 0 0 6 P4 4 0 5 0 2 0 P5 3 1 4 1 1 0 【例3-3-51】某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表3.20所示，此时系统的可用资源向量为（2,1,2）。试问： 表3.20 T0时刻4个进程对资源的占用和需求情况 进程 最大资源需求量 已分配资源数量 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 P2 6 1 3 4 1 1 P3 3 1 4 2 1 1 P4 4 2 2 0 0 2 （1）将系统中各种资源总数和此刻各进程对各资源的需求个数用向量或矩阵表示出来。 （2）如果此时P1和P2均发出资源请求向量Request(1,0,1)，为了保证系统的安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因。 （3）如果（2）中两个请求立即得到满足后，系统此刻是否处于死锁状态？ 解：（1）系统中资源总量为某时刻系统中可用资源量与各进程已分配资源量之和，即： （2,1,2）+（1,0,0）+（4,1,1）+（2,1,1）+（0,0,2）=（9,3,6） 各进程对资源的需求量为各进程对资源的最大需求量与进程已分配资源量之差，即：   （2）若此时P1发出资源请求Request1(1,0,1)，按银行家算法进行检查：  Request1(1,0,1)≤Need1(2,2,2)  Request1(1,0,1)≤Available(2,1,2) 试分配并修改相应的数据，由此形成的资源分配情况如表3.21所示。 表3.21 P1请求资源后的资源分配表 进程 Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 1 1 2 1 1 1 1 P2 4 1 1 2 0 2 P3 2 1 1 1 0 3 P4 0 0 2 4 2 0 再利用安全性算法检查系统是否安全，可用资源Available(1,1,1)已不能满足任何进程，系统进入不安全状态，此时系统不能将资源分配给P1。 若此时P2发出资源请求Request2(1,0,1)，按银行家算法进行检查：  Request2(1,0,1)≤Need2(2,0,2)  Request2(1,0,1)≤Available(2,1,2) 试分配并修改相应的数据结构，由此形成的资源分配情况如表3.22所示。再利用安全性算法检查系统是否安全，可得到如表3.23所示的安全性检测情况，从该表中可以看出，此时存在一个安全序列{P2,P3,P4,P1}，故该状态是安全的，可以立即将P2所申请的资源分配给它。 表3.22 P2请求资源后的资源分配表 进程 Allocation Need Available R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 1 0 0 2 2 2 1 1 1 P2 5 1 2 1 0 1 P3 2 1 1 1 0 3 P4 0 0 2 4 2 0 表3.23 P2请求资源后的安全性检测表 进程 Work Need Allocation Work+Allocation Finish R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P2 1 1 1 1 0 1 5 1 2 6 2 3 true P3 6 2 3 1 0 3 2 1 1 8 3 4 true P4 8 3 4 4 2 0 0 0 2 8 3 6 true P1 8 3 6 2 2 2 1 0 0 9 3 6 true （3）如果（2）中两个请求立即得到满足，此刻系统并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源请求没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态。 【例3-3-52】现有5个进程A、B、C、D、E，有4种类型的资源R1、R2、R3、R4。在T0时刻系统状态如表3.24所示。R1、R2、R3、R4的剩余资源数依次为3、3、0、3。若采用银行家算法避免死锁，回答下列问题： （1）T0时刻是否为安全状态？ （2）若这时D提出申请(1,2,0,3)，是否能实施资源分配？ 表3.24 T0时刻5个进程对资源的占用和需求情况 进程 已占资源数 最大需求数 R1 R2 R3 R4 R1 R2 R3 R4 A 0 0 1 2 0 0 1 2 B 2 0 0 0 2 7 5 0 C 0 0 3 4 6 6 5 6 D 1 1 5 1 4 3 5 6 E 0 3 3 2 0 6 5 2 解：（1）利用安全性算法对此时刻的资源分配情况进行分析，可得到如表3.25所示的安全性检测情况。从中可以看出，存在一个安全序列{A，D，E，B，C}，故T0时刻处于安全状态。 表3.25 T0时刻的安全性检测情况 进程 Work Need Allocation Work+Allocation Finish R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 A 3 3 0 3 0 0 0 0 0 0 1 2 3 3 1 5 true D 3 3 1 5 3 2 0 5 1 1 5 1 4 4 6 6 true E 4 4 6 6 0 3 2 0 0 3 3 2 4 7 9 8 true B 4 7 9 8 0 7 5 0 2 0 0 0 6 7 9 8 true C 6 7 9 8 6 6 2 2 0 0 3 4 6 7 12 12 true （2）进程D提出申请(1,2,0,3)，按银行家算法进行检查：  RequestD(1,2,0,3)<NeedD(3,2,0,5)  RequestD(1,2,0,3)<Available(3,3,0,3) 此时存在一个安全序列{A、D、E、B、C}，如表3.26所示，故该状态是安全的，可以立即将D进程所申请的资源分配给它。 表3.26 D进程请求资源后的安全性检测表 进程 Work Need Allocation Work+Allocation Finish R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 A 2 1 0 0 0 0 0 0 0 0 1 2 2 1 1 2 true D 2 1 1 2 2 0 0 2 2 3 5 4 4 4 6 6 true E 4 4 6 6 0 3 2 0 0 3 3 2 4 7 9 8 true B 4 7 9 8 0 7 5 0 2 0 0 0 6 7 9 8 true C 6 7 9 8 6 6 2 2 0 0 3 4 6 7 12 12 true 【例3-3-53】假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单位），它们被进程P1和P2所共享，且已知两个进程均以下列顺序使用两类资源： →申请R1→申请R2→申请R1→释放R1→释放R2→释放R1→ 试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图（或称进程-资源图）。 解：在本题中，当两个进程都执行完第1步后，即进程P1和进程P2都申请到了一个R1类资源时，系统进入不安全状态。随着两个进程的向前推进，无论哪个进程执行完第2步，系统都将进入死锁状态。可能到达的死锁点是：进程P1占有一个单位的R1类资源及一个单位的R2类资源，进程P2占有一个单位的R1类资源，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的情况下继续申请资源，从而造成死锁；或进程P2占有一个单位的R1类资源及一个单位的R2类资源，进程P1占有一个单位的R1类资源，此时系统内已无空闲资源，而两个进程都在保持已占有资源不释放的情况下继续申请资源，从而造成死锁。 假定进程P1成功执行了第2步，则死锁点的资源分配图如图3.38所示。 图3.38 死锁点的资源分配图 【例3-3-54】试化简图3.39中的进程资源图，并利用死锁定理给出相应的结论。 图3.39 两个进程-资源图 解：在图3.39（a）中，系统中共有R1类资源2个，R2类资源3个，在当前状态下仅有一个R2类资源空闲。进程P2占有一个R1类资源及一个R2类资源，并申请一个R2类资源；进程P1占有一个R1类资源及一个R2类资源，并申请一个R1类资源及一个R2类资源。因此，进程P2是一个既不孤立又非阻塞的进程，消去进程P2的资源请求边和资源分配边，便形成了如图3.40（a）所示的情况。当进程P2释放资源后，系统中有2个R2类空闲资源、1个R1类空闲资源，因此系统能满足进程P1的资源申请，使得进程P1成为一个既不孤立又非阻塞的进程，消去进程P1的资源请求边和资源分配边，便形成了如图3.40（b）所示的情况。由死锁定理可知，图3.39（a）中的进程-资源图不会产生死锁。 图3.40 资源分配图的化简 在图3.39（b）中，系统中共有R1类资源1个、R2类资源2个、R3类资源2个、R4类资源1个。在当前状态下仅有一个R3类资源空闲。进程P1占有一个R2类资源，并申请一个R1类资源；进程P2占有一个R1类资源及一个R3类资源，并申请一个R4类资源；进程P3占有一个R4类资源及一个R2类资源，并申请一个R3类资源及一个R2类资源，因此，该资源分配图中没有不孤立又不阻塞的进程节点，即系统中的3个进程均无法向前推进，由死锁定理可知，图3.39（b）的进程-资源图会产生死锁。 【例3-3-55】有3个进程P1、P2和P3并发工作，进程P1需用资源S3和S1，进程P2需用资源S1和S2，进程P3需用资源S2和S3。试回答下面两个问题。 （1）若对资源分配不加限制，会发生什么情况？为什么？ （2）为保证进程正确工作，应采用怎样的资源分配策略？ 解：（1）可能会发生死锁现象。例如，进程P1、P2和P3分别获得资源S3、S1和S2后再继续申请资源时都要等待，这是循环等待。 （2）可有以下几种分配策略：  采用静态分配，由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象（或不会出现循环等待资源现象）。  采用按序分配，不会出现循环等待资源现象。  采用银行家算法，在分配时，保证了系统处于安全状态。 【例3-3-56】进程资源的使用情况和可用情况如表3.27所示（4个进程和3类资源），回答以下问题： （1）请画出资源分配图。 （2）分析目前系统中是否会发生死锁。 表3.27 进程资源的使用情况和可用情况 进程 当前已分配资源数量 最大需求量 系统可用资源数量 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 0 3 1 0 0 0 0 P2 3 1 0 3 1 0 P3 1 3 0 1 3 1 P4 0 1 1 0 2 1 解：（1）对应的资源分配图如图3.41所示。 图3.41 一个资源分配图 （2）从进程对各类资源的占有量、尚需量和系统中各类资源的剩余量来考虑是否有死锁存在。可以看出进程P2已得到全部资源，能在有限的时间内归还资源，得到可分配的资源数为： (3,1,0)+(0,0,0)=(3,1,0) 可满足进程P1的申请，P1也能在有限的时间内归还资源，于是可分配的资源数增加为： (3,1,0)+(2,0,0)=(5,1,0) 接着，对进程P4的申请也能满足，最后让进程P3运行。所以存在一个进程推进的序列为(P2,P1,P4,P3)，先后都能完成，目前系统是安全的，没有死锁。