搜索
死锁的产生及解决方法死锁含义：多个进程在运行过程中因竞争资源而造成的一种僵局。各并发进程彼此等待对方拥有的资源，且得到对方资源前不释放自己拥有的资源。导致死锁的原因：（1）竞争资源资源（打印机，公共队列）数目不能满足进程的需要。（2）进程间的推进顺序不当进程在运行过程中，请求和释放资源的顺序不当，也会导致进程死锁。竞争资源引起死锁（1）可剥夺（CPU、主存）和非剥夺性资源（磁带机、打印机）（2）竞争非剥夺性资源非剥夺性资源的数量不能满足进程运行的需要，可能使进程在运行过程中产生死锁。（3）进程临时性资源由一个进程产生由另一个进程使用短暂时间后便无用的资源。产生死锁的必要条件（1）互斥条件（2）请求和保持条件（3）不剥夺条件（4）环路等待条件互斥条件：进程对所分配到的资源进行排他性使用。请求和保持条件：进程已经保持至少一个资源，但又提出新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己获得的其他资源保持不放。不剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时自己释放。环路等待条件：发生死锁时，必然存在一个进程-资源的环行链。处理死锁的基本方法（1）预防死锁（2）避免死锁（3）检测死锁（4）解除死锁（1）、（2）死锁发生前的办法，（3）、（4）死锁发生后的办法预防死锁：设置某些限制条件，破坏四个必要条件中的一个或多个条件。简单、好实现避免死锁：在资源的动态分配过程中，用某种方法去预防系统进入不安全状态。可获得较高的资源利用率及系统吞吐量。实现上有一定难度检测死锁：允许系统在发生死锁，通过系统设置的检测机构，及时检测出死锁的发生，并精确的确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。解除死锁：当检测到系统已发生死锁时，撤销或挂起一些进程。预防死锁：互斥条件（不可以打破）请求和保持条件（可以）不剥夺条件（可以）环路等待条件（可以）破坏“请求和保持”条件：规定所有进程在开始运行之前，都必须一次性的申请其在整个运行过程所需要的全部资源。优点：简单，安全缺点：资源严重浪费，恶化了系统的利用率；破坏“不剥夺”条件进程逐个的提出资源请求，当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。缺点：实现复杂，代价大因为反复地申请和释放资源，而使进程的执行无限的推迟、延长了进程的周转时间增加系统开销、降低系统吞吐量。破坏“环路等待”条件将所有的资源按类型进行线性排队，并赋予不同的序号。所有进程请求资源必须按照资源递增的次序提出，防止出现环路。缺点：（1）序号必须相对稳定，限制了新设备类型的增加（2）作业（进程）使用资源顺序和系统规定的顺序不同而造成资源的浪费（3）限制了用户编程避免死锁系统安全状态：指系统能按照某种顺序如（P1、P2、…、Pn），来为每一个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个安全序列，则称系统处于不安全状态。系统进入不安全状态可能产生死锁。避免死锁的实质：如何使系统不进入不安全状态。银行家算法避免死锁：（1）银行家算法中的数据结构（2）银行家算法（3）安全性算法（4）银行家算法之例银行家算法的数据结构：可利用的资源向量Available：含有m个元素；每个元素代表一类可用的资源数目；初值是该类全部可用资源的数目；数值随该类资源的分配和回收动态地改变；Available[j]=K,表示第j类资源的个数为K最大需求矩阵Max：N*m的矩阵；定义了n个进程中每一个进程对m类资源的最大需求。如Max[I,j]=K,表示进程i需要Rj类资源的最大数值为K。分配矩阵Allocation：N*m的矩阵；定义系统中每一类资源当前已分配给每个进程的资源数。Allocation[I,j]=k,表示进程i当前以分得Rj类资源的数目为K；需求矩阵NeedN*m的矩阵；表示一个进程尚需的各类资源数。Need[I,j]=K，表示进程i当前还需要Rj类资源的数目为K。银行家算法设Requesti是进程Pi的请求向量。如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。Pi发出资源请求后。按下述步骤检查：（1）Requesti[j]小于等于Need[I,j],则转向步骤2；否则，认为出错；（2）Requesti[j]小于等于Available[j]则转向步骤3；否则，进程Pi等待（3）系统试探着把资源分配给进程Pi：Available[j]=Available[j]-Requesti[j],Allocation[I,j]=Allocation[I,j]+Requesti[j];Need[I,j]=Need[I,j]-Requesti[j];（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全才将资源分配给进程；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法（1）设置两个向量工作向量Work：供进程继续运行的各类资源数，含M个元素，初值Work=AvailableFinish：表示系统是否有足够的资源分配给进程。初值：finish[i]=false,当有足够资源分配时Finish[i]=true.（2）找满足下列条件的进程：Finish[i]=falseNeed[I,j]小于等于Work[j];若找到执行步骤（3），否则执行步骤（4）（3）Work[j]=work[i]+Allocation[I,j];Finish[i]=true;Gotostep（2）（4）如果所有的进程Finish[i]=true,则系统处于安全状态。银行家算法之例：系统中有五个进程{P0,P1,P2,P3,P4}，三类资源{A,B,C},数目为：10,5,7.在T0时刻的资源分配情况如图。资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431（1）T0时刻的安全性：资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1332122200532TrueP3532011211743TrueP4743431002745TrueP27456003021047TrueP010477430101057True(2)P1请求资源P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：①Request1(1,0,2)≤Need1②Request1(1,0,2)≤Available1③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图3-15④再利用安全性算法检查此时系统是否安全。资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1230020302532TrueP3532011211743TrueP4743431002745TrueP0745743010755TrueP27556003021057True(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：①Request4(3,3,0)≤Need4②Request4(3,3,0)Available(2,3,0)，让P4(4)P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：①Request0②Request0③系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。资源进程WorkNeedAllocationABCABCABCP0030723210P1302020P2302600P3211011P4002431死锁的解除常用的两种方法：（1）剥夺资源：从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态。（2）撤销进程a)使全部死锁进程都夭折掉b)按照某种顺序逐个的撤销进程，直至有足够的资源可用，使死锁状态消除为止。