操作系统-死锁

操作系统原理第3章进程管理第7讲进程死锁2019/12/302今日主题什么是死锁？（了解）死锁防止（熟悉）死锁避免（掌握）死锁检测和恢复（熟悉）[重点]：死锁必要条件、死锁防止、避免、检测和恢复[难点]：银行家算法。2019/12/303•汽车竞争路口•它们到达路口的时间很“凑巧”•每个车队既占有一个路口，又等待另一车队让出路口交通拥堵现象所有的车都在等待，如果没有交警来，只好无限等待下去！2019/12/304输出井满啦！不够！进程AABCCDEFABCD进程BABCD不够！•进程竞争资源•每一进程既占有一个资源，又等待另一进程让出资源•要是输出井再多一个就好啦!SPOOLing系统死锁示例一什么是死锁？•死锁的定义2019/12/305一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为进程死锁(Deadlock)，这一组进程就称为死锁进程。P1P2..GPS照相机每一进程既占有一个资源，又等待另一进程让出资源！进程P1和P2拍照并在照片上标定位置信息死锁的原因起因是并发进程的资源竞争。根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。是否死锁取决于各进程申请和释放资源的顺序。因此，死锁的原因归为两点：（1）系统资源不足。(资源数比进程需要量少)。（2）进程推进顺序不当。2019/12/306死锁的必要条件(1)互斥（MutualExclusion）•必须存在需要互斥使用的资源(2)不剥夺（NoPreemption）•进程占有的资源未主动释放时不可以剥夺(3)部分分配(又叫占有等待HoldandWait)•进程占有已分到的部分资源而又等待其它资源(4)环路（又叫循环等待CircularWait）•进程集合{P0,P1,……,Pn}，Pi等待Pi+1的资源，Pn等待P0的资源。形成等待环。2019/12/3074P0P1P2PnPiPi+1......死锁的解决方法•死锁预防（Deadlockprevention）•死锁避免（Deadlockavoidance）•死锁的检测和恢复（DeadlockDetectionandRecoveryfromDeadlock）•忽略（ignore)2019/12/308因为死锁的处理开销较大，所以很多操作系统，如Linux、Windows，都忽略死锁。二死锁预防•什么是死锁预防？•采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。•死锁预防方法•破坏“互斥”条件：共享使用资源。缺点：不一定可行。•破坏“部分分配”条件：进程申请资源时必须一次性申请其全部所需资源。缺点：资源利用率低，可能饥饿。•破坏“不剥夺”条件：当进程申请的资源不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。缺点：释放的资源的前期工作将失效。•破坏“环路”条件：系统将资源编号，进程按照资源序号递增的次序提出资源申请。缺点：限制了新设备增加，资源可能限制，用户变成受限制。2019/12/309三死锁避免•什么是死锁避免？•系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并加以避免的方法。•有代表性的死锁避免算法是Dijkstra提出的银行家算法。2019/12/3010借给Q:1银行家算法示意【例】设银行家有10万元，顾客P,Q,R分别需要8,3,9万元搞项目（假设任何人满足资金总额后都会归还所有贷款）。如果P、Q、R分别已借到了4万、2万、2万。以后银行家怎样放贷？2019/12/3011PQR422剩余：2PQR432剩余：1Q还款:3PQR402剩余：4借给P:4PQR802剩余：0P还款:8PQR002剩余：8借给R:7PQR009剩余：1R还款:9PQR000剩余：10得到借款的安全序列：QPR其他借款序列，如PQR、PRQ、…都不安全！•所谓安全状态，是指系统能按某种进程顺序(P1,P2,…,Pn)来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都能顺利地完成，则称这个系统处于安全状态，序列(P1,P2,…,Pn)称为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。2019/12/3012设单类资源系统中有n个进程，若存在一个序列(P1,P2,…,Pn)使得Pi(i＝1，2…n)以后还需要的资源可以通过系统现有资源加上所有Pj(j＜i)占有的资源来满足，则该系统处于安全状态，序列(P1，P2…Pn)称为安全序列。安全状态与安全序列讨论：安全状态与死锁的关系2019/12/3013•安全状态不是死锁状态。死锁状态是不安全状态。•并非所有的不安全状态都会死锁，但不安全状态可能导致死锁。•系统处于安全状态，可避免进入死锁状态。避免死锁就是要在系统在进行资源分配时，如何使系统不进入不安全状态。死锁不安全安全银行家算法（Banker’sAlgorithm）•把银行家比作系统，把资金比作资源，把顾客比作进程。•银行家算法：在系统处理资源申请时，判断在满足申请时，系统是否还处于安全状态？是则满足本次资源申请，否则拒绝。分3步进行：•第一步，根据资源数据结构建立资源分配表•第二步，试分配：按照进程申请分配，修改资源分配表•第三步，安全检查：对哦是分配状态进行安全检查，若出现不安全状态，则回复试分配资源，结束。若安全则结束。2019/12/3014银行家算法数据结构n：进程总数m：资源类型总数Available[m]：剩余资源。Available[j]=k;表示j类资源剩余k个。Max[n,m];资源最大需求量。Max[i,j]=k;表示进程Pi最多需要j类资源K个。Allocation[n,m];已分配资源。Allocation[i,j]=k;表示进程Pi已分配j类资源k个。Need[n,m];还需要的资源。Need[i,j]=k;表示进程Pi以后还需要j类资源k个。Request[m];进程申请的资源。Request[j]=k;表示进程申请j类资源k个。2019/12/3015Need[i,j]=Max[i,j]-Allocation[i,j];银行家算法描述：试分配＋安全检查试分配算法设进程Pi申请资源，申请资源向量为Request[j]，则有如下的资源分配过程：(1)if(Request[j]Need[i,j])报错返回;(2)if(Request[j]Available[j])进程Pi等待;返回;(3)假设进程Pi的申请已获准，修改系统状态：Available[j]=Available[j]–Request[j];Allocation[i,j]=Allocation[i,j]+Request[j]Need[i,j]=Need[i,j]–Request[j];(4)调用安全状态检查算法。(5)若系统处于安全状态，则将进程Pi申请的资源分配给进程Pi，返回。(6)若系统处于不安全状态，则进程Pi进入等待资源状态并恢复系统状态后返回：Available[j]=Available[j]+Request[j];Allocation[i,j]=Allocation[i,j]-Request[j];Need[i,j]=Need[i,j]+Request[j];2019/12/3016银行家算法描述：试分配＋安全检查安全检查算法为进行安全性检查，定义数据结构：Work[m]：为临时工作向量,表示剩余资源。Finish[n]：表示剩余资源是否满足进程的需要。安全性检查的步骤：(1)Work=Available;Finish=false;(2)寻找满足条件的i，使得：Need[i]≤Work&&Finish[i]==false;如果不存在，则转(4)(3)Work=Work+Allocation[i];Finish[i]=true;转(2)(4)若对所有i，Finish[i]==true,则系统处于安全状态，否则处于不安全状态2019/12/3017银行家算法举例【例】系统中有r1,r2,r3三类资源，在T0时刻P1,P2,P3,P4四个进程对资源的最大需求数分别为P1(3,2,2),P2(6,1,3),P3(3,1,4),P4(4,2,2)，已分配的资源数量分别为P1(1,0,0),P2(4,1,1),P3(2,1,1),P4(0,0,2),此时系统中可用的资源数为(2,1,2)。试问该状态安全吗？是否存在安全序列，为了避免死锁应如何进行分配。2019/12/3018【方法】（1）求资源分配表;（2）试分配;（3）安全检查资源进程最大需求已分配资源还需要资源剩余资源r1r2r3r1r2r3r1r2r3r1r2r3P1322100212P2613411P3314211P4422002【解答】T0时刻资源分配表：2019/12/3019P2申请资源后的安全检查表：资源进程工作向量已分配还需要工作+已分配完成情况r1r2r3r1r2r3r1r2r3r1r2r3P1100222P2411202P3211103P4002420212623①②623723③723934④934936满足满足满足满足资源进程最大需求已分配还需要剩余资源r1r2r3r1r2r3r1r2r3r1r2r3P1322100222212P2613411202P3314211103P4422002420T0时刻资源分配表：安全序列p2,p1,p3,p4四死锁的检测和恢复1死锁检测算法2019/12/30201)work=available；2)如果allocation[k,*]!=0，令finish[k]=false;否则finish[k]=true；3)寻找一个k，它应满足条件：(finish[k]==false)&&(request[k,*]=work[*]);若找不到这样的k，则转向5)；4)修改work[*]=work[*]+allocation[k,*];finish[k]=true;然后转向3)；5)如果存在k(1≤k≤n),finish[k]=false,则系统处于死锁状态，并且finish[k]=false的Pk为处于死锁的进程。四死锁的检测和恢复2资源分配图化简法2019/12/3021P1P2.r1.r2图G=(V,E);顶点集合V={P,R};进程顶点集合P={P1,P2};资源顶点集合R={r1,r2};边集合E={P1,r1,P2,r2,r1,P2,r2,P1};请求边P1,r1;P2,r2;分配边r1,P2;r2,P1;圆圈表示进程顶点，方框表示资源顶点，方框中圆点数表示资源数。请求边从进程指向资源，表示进程等待该资源。分配边从资源指向进程，表示进程占有该资源。•资源分配图(Resource-AllocationGraph)2资源分配图化简法资源分配图的简化过程：(1)循环遍历进程顶点Pi,判断Pi所有的请求边是否都能被满足。(2)若满足则把Pi的边全部删去，转(1)；(3)若不满足则化简过程结束。去掉了边的进程定点称为孤立点。如果化简后所有的进程顶点都成了孤立点，则称该图可完全化简；否则称该图是不可完全化简的。2019/12/3022系统中有死锁的充分条件是资源分配图不可完全化简。2019/12/3023[例]化简下列资源分配图，说明有无进程处于死锁状态？P5P3P4P1P2R1R2R3R4R5P5P3P4P1P2R1R2R3R4R5资源分配图可完全化简，没有进程处于死锁状态。死锁检测2019/12/3024若系统只有一种资源，设资源数为r个，供p个进程共享，如果每个进程最多申请m个资源，则：当r-1=(m-1)*p;时，系统不会死锁。一个结论[例]有3个并发进程各都需要使用4个串口，问，系统不会发生死锁的最少串口数是多少？[解]已知p=3;m=4;代入r-1=(m-1)*p;得r=10;所以，不会发生死锁的最少串口数是10。问题：上述哪种方法进程前期工作损失最小？哪种方法开销最大？对于