操作系统精美版2013os第7章死锁

第7章进程同步7.1系统模型7.2死锁特征(4个必要条件)7.3死锁处理方法7.4死锁预防7.5死锁避免(银行家算法)7.6死锁检测7.7死锁恢复7.1系统模型P209

死锁：在一个进程集合中的所有进程都在等待只能由该集合中的其它一个进程才能引发的事件而无限期地僵持下去的局面。

死锁:指多个进程因竞争共享资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再向前推进●死锁可能蔓延，最终导致整个系统瘫痪●死锁是进程并发需要处理的难题死锁例子

一个由于申请不同类型资源而产生死锁的例子

设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。

用信号量S1表示R1是否可用，用信号量S2表示R2是否可用，S1、S2初值为1。★这两个进程在并发执行过程中，可能会发生死锁

★大家可以思考一下，如何修改，进程才不会发生死锁。……P(S1)占用R1P(S2)占用R2V(S2)V(S1)……A进程……P(S2)占用R2P(S1)占用R1V(S2)V(S1)……B进程关于死锁的一些结论

参与死锁的进程最少是两个

参与死锁的进程至少有两个已经占有资源

参与死锁的所有进程都在等待资源

参与死锁的进程是当前系统中所有进程的子集

注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。使用资源的方式资源类型：R1,R2,…,RmCPU周期，内存空间，I/O设备每个资源类型Ri有Wi个实例每个进程用以下方式利用资源申请：request分配并使用释放：release7.2死锁特征死锁产生的原因（1）竞争资源当系统中多个进程共享资源如打印机、公共队列等，其数目不足以同时满足各进程的需要时，会引起各进程对资源的竞争而产生死锁（2）各进程之间的推进顺序不当进程在运行过程中，请求和释放资源的顺序不当，也可能会导致产生进程死锁竞争资源引起死锁①可剥夺资源和非剥夺性资源

可剥夺性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺（CPU，主存）

非剥夺性资源：系统把这类资源分配给进程后，再不能强行收回，只能在进程用完后自行释放（磁带机、打印机）②竞争非剥夺性资源：由于系统设置的非剥夺性资源不能满足诸进程运行的需要，有可能在竞争非剥夺性资源时产生死锁③竞争临时性资源（永久性资源，临时性资源）7.2.1必要条件

进程在运行的过程中可能发生死锁，但死锁的发生必须具备4个必要条件：①互斥条件②请求和保持条件（占有并等待）③不剥夺条件（非抢占）④环路等待条件（循环等待）死锁产生的必要条件7.2.2资源分配图

系统死锁可以利用资源分配图来描述（有向图）

二元组G=（N，E）

N：结点集，N=P∪R进程节点PP={p1,p2,…,pn}资源节点RR={r1,r2,…,rm}

E：边的集合，其元素为有序二元组:

资源请求边(pi,rj)资源分配边(rj,pi)资源分配图r1r2进程资源类资源实例资源申请边资源分配边资源类:用方框表示（资源的不同类型）资源实例:用方框中的黑圆点表示（存在于每个资源中）死锁定理

如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。

如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。P214图7.3存在死锁的资源分配图P214图7.4存在环但是没有死锁的资源分配图7.3死锁处理方法①预防死锁

（事先预防，采取限制措施去破坏4个必要条件）②避免死锁

（银行家算法）（事先预防，在资源的动态分配过程中，用某种方法防止系统进入不安全状态）③检测死锁（通过设置检测机构，及时检测出死锁的发生）④解除死锁（死锁的恢复）（当检测到已经发生死锁时，将进程从死锁状态中解除出来）7.4死锁的预防

预防死锁：事先限制（较严格）

避免死锁：事先限制（较宽松）

预防死锁：在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。

预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁7.4.1互斥对于非共享资源，必须要有互斥条件破坏互斥条件，会出错互斥条件绝对不能被破坏7.4.2占有并等待摒弃“占有并等待（请求和保持）”条件

资源一次性分配：所有进程在宽松运行之前，都必须一次性的申请在这个运行过程中所需的全部资源

优点：简单，易于实现

缺点：资源利用率低，进程可能长期等待资源7.4.3非抢占

可剥夺资源：当某进程新的资源申请未满足时，释放已占有的资源

缺点：复杂，实现的代价大，而且有些资源(如打印机)被剥夺会产生混乱有些进程会反复申请和释放资源(增加开销)摒弃“非抢占（不剥夺）”条件7.4.4循环等待

资源有序分配法:系统给每类资源赋予一个编号,每一个进程按编号递增的顺序请求资源，释放则相反.总有一个进程占据了较高序号的资源,此后它申请的资源必然是空闲的,因而进程可以一直向前推进

存在严重问题:①资源序号相对稳定,限制新类型设备的增加②资源的编号顺序不一定是实际需要资源的顺序,资源不能有效利用③限制用户编程自由(资源的申请顺序要符合编号顺序)摒弃“循环等待（环路等待）”条件7.5死锁避免

预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁

避免死锁时,把系统状态分为安全状态和不安全状态,只要系统始终处于安全状态,便可避免发生死锁

系统在运行过程中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁的所谓不安全状态，以达到避免死锁发生的目的7.5.1安全状态

安全状态:系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。安全状态一定是没有死锁发生的

若系统不存在这样一个序列，则称系统处于不安全状态。

允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。P219图7.5安全、不安全和死锁状态空间安全状态实例进程最大需求量已分配资源量仍需申请的资源量系统当前空闲资源量P110553P2422P3927

实例:假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：分析:

T0时刻是安全的,存在安全序列<p2,p1,p3>由安全状态向不安全状态转换进程最大需求量已分配资源量仍需申请的资源量系统当前空闲资源量P110553P2422P3927分析:

T0时刻是安全的,存在安全序列<p2,p1,p3>例如，在T1时刻，P3又请求1台磁带机若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态考虑：T1时刻，只有P2又请求1台磁带机，情况怎样（书P219最后一行有错，请改正）7.5.2资源分配图算法只适用于单资源实例情况有环则不安全分配边申请边需求边：将来某时刻可能申请的资源P221图7.7资源分配图的不安全状态当申请资源时，需求边变为申请边用“环检测算法”来检测是否有环，有环则不安全7.5.3银行家算法银行家算法是最有代表性的死锁避免策略，该策略是根据在银行系统所采用的借贷策略建立的模型，由Dijkstra于1965年提出死锁避免:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁（不安全），则不予分配，否则予以分配银行家算法的数据结构可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有j类资源K个最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要j类资源的最大数目为K个银行家算法的数据结构(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得j类资源的数目为K。(4)需求矩阵Need。是一个n×m的矩阵，用以表示每一个进程还需的各类资源数。Need［i,j］=K，则表示进程i还需要j类资源K个，方能完成其任务。Need［i,j］=Max［i,j］-Allocation［i,j］1.资源请求算法设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个j类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待1.资源请求算法(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，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待2.安全性算法设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available;②Finish:表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时，再令Finish[i]:=true2.安全算法(2)从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false;②Need［i,j］≤Work［j］若找到，执行步骤(3)，否则，执行步骤(4)(4)如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;3.举例P0,P1,P2,P3,P4；资源A有10个实例，B有5个实例，C有7个实例在T0时刻情况如下，则该时刻是否安全 Allocation Max Available ABCABC ABCP0 010 753 332P1 200 322 P2 302 902P3 211 222P4 002 433 NeedABC743122600011431（1）T0时刻的安全性：安全的，存在安全序列<p1,p3,p4,p2,p0>（2）P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图中的圆括号所示④再利用安全性算法检查此时系统是否安全

P1申请资源后的安全性：安全的，存在一个安全序列<p1,p3,p4,p2,p0>(3)P4请求资源：P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)<Available(2,3,0)，让P4等待。(4)P0请求资源：P0发出请求向量Requst0(0,2,0)，系统按银行家算法进行检查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系统暂时先假定可为P0分配资源，并修改有关数据

P0申请资源后的安全性：不安全的Requst0(0,2,0)问题：如果P0发出的请求时Request0(0,1,0),系统是否能将资源分配给它资源进程AllocationR1R2R3R4MaxR1R2R3R4NeedR1R2R3R4AvailableR1R2R3R4P12011321412031222P2012102520131P3400351051102P4021015301320P5103030332003银行家算法习题11、T0时刻安全吗？资源进程WorkR1R2R3R4NeedR1R2R3R4AllocationR1R2R3R4Work+AllocatioR1R2R3R4FinishP31222110240035225trueP15225120320117236trueP27236013101217357trueP47357132002107567trueP57567200310308597true解：T0时刻是安全的因为在T0时刻存在一个安全序列{P3,P1,P2,P4,P5}，资源进程AllocationR1R2R3R4MaxR1R2R3R4NeedR1R2R3R4AvailableR1R2R3R4P12011321412030221P2012102520131P3500451050101P4021015301320P5103030332003（2）T1时刻，P3提出Request3(1,0,0,1)，是否满足？解：按银行家算法检查： ①Request3(1,0,0,1)≦Need3(1,1,0,2) ②Request1(1,0,0,1)≦Available(1,2,2,2) ③假设满足进程P3的要求，为其分配所申请的资源，并且修改Available、Allocation3和Need3，得到如下表所示的资源分配表。资源进程WorkR1R2R3R4NeedR1R2R3R4AllocationR1R2R3R4Work+AllocationR1R2R3R4FinishP30221010150045225trueP15225120320117236trueP27236013101217357trueP57357200310308387trueP48387132002108597true④利用安全性检查算法，检查此时的系统是否安全。得到如下表所示的安全序列，因此系统是安全的，此次P3要求的资源可以真正分配给它使用。（3）T2时刻，P1提出Request1(1,2,0,1)，是否满足？解：系统仍要使用银行家算法进行检查，从T1时刻的资源分配表可以看出Request1(1，2，0，1)＞Available(0,2,2,1)即系统不能满足进程P1的申请，因此要阻塞P1。银行家算法习题2习题：操作系统分配资源时的一个主要考虑是避免死锁的发生。若系统中有同类资源16个，有4个进程p1、p2、p3、p4共享该资源。已知p1、p2、p3、p4所需的资源总数分别为8、5、9、6。各进程请求资源的次序如表8-1所示，若系统采用银行家算法为他们分配资源，那么____次申请分配会使系统进入不安全状态A.3、4

B.3、5

C.4、5

D.5、6序号进程申请量1P162P243P354P415P116P21C银行家算法习题2解答序号进程申请量最大需求还需系统还剩1P1682102P245163P359414P416如果分配，死锁5P112如果分配，死锁6P21100银行家算法习题3习题：某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程解答：安全的

进已最大还还程申请需求需剩P14842P2275P32424①②8③10银行家算法习题4习题：在银行家算法中，若出现下述资源分配情况：试问（1）该状态是安全的吗？（2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？ProcessAllocationNeedAvailableP00,0,3,20,0,1,21,6,2,2P11,0,0,01,7,5,0P21,3,5,42,3,5,6P30,3,3,20,6,5,2P40,0,1,40,6,5,6银行家算法习题4解答：

（1）安全的ProcessAllocationNeedAvailableP00,0,3,20,0,1,21,6,2,2P11,0,0,01,7,5,0P21,3,5,42,3,5,6P30,3,3,20,6,5,2P40,0,1,40,6,5,6①1,6,5,4②1,9,8,6③2,9,8,6④3,12,13,10⑤3,12,14,14能找到安全序列<P0,P3,P1,P2,P4>,所以是安全的银行家算法习题4解答:(2)进程P2提出请求Request(1,2,2,2)，不能分配ProcessAllocationNeedAvailableP00,0,3,20,0,1,21,6,2,2P11,0,0,01,7,5,00,4,0,0P21,3,5,42,5,7,62,3,5,61,1,3,4P30,3,3,20,6,5,2P40,0,1,40,6,5,6Availabe=(0,4,0,0)不能满足任何一个进程的需要，不安全，所以不能分配7.6死锁检测允许系统进入死锁状态检测算法恢复机制7.6.1每种资源类型只有单个实例资源分配图等待图在等待图中用搜索算法来检测是否有环（有环必死锁）7.6.2每种资源类有多个实例Available：长度为m的向量，表示各种资源的可用实例Allocation：n×m矩阵，表示当前各进程的资源分配情况Request：n×m矩阵，表示当前各进程的资源请求情况。如果Req