苏州大学操作系统概念第七章

第7章死锁6.2内容1.死锁问题2.死锁系统模型3.死锁预防4.死锁避免5.死锁检测和恢复1、死锁问题6.46.5过桥例子只能一个方向通行桥的每一个部分都可以看成资源如果死锁发生，它可以由一辆车返回而解决，抢占资源并回退如果死锁发生，可能很多车都不得不返回有可能产生饥饿6.6死锁问题一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源所有死锁进程无法推进原因竞争互斥资源进程推进不当例如系统有两个磁带设备进程P1和P2各占有一个磁带设备并且实际需要两个磁带6.7死锁例子/*threadonerunsinthisfunction*/void*do_work_one(void*param){pthread_mutex_lock(&first_mutex);pthread_mutex_lock(&second_mutex);/***Dosomework*/pthread_mutex_unlock(&second_mutex);pthread_mutex_unlock(&first_mutex);pthread_exit(0);}/*threadtworunsinthisfunction*/void*do_work_two(void*param){pthread_mutex_lock(&second_mutex);pthread_mutex_lock(&first_mutex);/***Dosomework*/pthread_mutex_unlock(&first_mutex);pthread_mutex_unlock(&second_mutex);pthread_exit(0);}6.8死锁的特性互斥：一次只有一个进程可以使用一个资源占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放循环等待：等待资源的进程之间存在环{P0,P1,…,P0}P0等待P1占有的资源,P1等待P2占有的资源,…,Pn–1等待Pn占有的资源,P0等待Pn占有的资源►四个条件同时出现，死锁将会发生（必要条件）2、死锁系统模型6.10系统模型资源类型R1,R2,...,RmCPU周期，内存空间，I/O设备每一种资源Ri有Wi种实例每一个进程通过如下方法来使用资源申请使用释放资源动态申请-常用方法在进程运行过程中申请资源资源静态申请在进程运行前一次申请所有资源6.11资源分配图（V被分为两个部分P={P1,P2,…,Pn},含有系统中全部的进程R={R1,R2,…,Rm},含有系统中全部的资源请求边：有向边P1Rj分配边：有向边R1Pj一个顶点的集合V和边的集合E6.12资源分配图进程有四个实例的资源类型Pi请求一个Rj的实例Pi持有一个Rj的实例PiPiRjRj6.13资源分配图的例子6.14有环有死锁的资源分配图6.15有环但没有死锁的资源分配图6.16基本事实如果图没有环，那么不会有死锁如果图有环如果每一种资源类型只有一个实例，那么死锁发生如果一种资源类型有多个实例，可能死锁6.17处理死锁的方法确保系统永远不会进入死锁状态允许系统进入死锁状态，然后恢复系统忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX设备虚拟化3、死锁预防6.19死锁的预防互斥：存在互斥资源，不能改变这个条件现代操作系统中的虚拟化技术占有并等待：必须保证进程申请资源的时候没有占有其他资源静态分配策略要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源）利用率低，可能出现饥饿抑制死锁发生的必要条件6.20死锁的预防非抢占:如果一个进程的申请没有实现，它要释放所有占有的资源先占的资源放入进程等待资源列表中进程在重新得到旧的资源的时候可以重新开始循环等待：对所有的资源类型排序进行总排序，并且要求进程按照递增顺序申请资源4、死锁避免6.22死锁避免一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量需要系统有一些额外的信息6.23安全状态当进程申请一个有效的资源的时候，系统必须确定分配后是安全的如果存在一个安全序列，系统处于安全态进程序列P1,P2,…,Pn是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数如果Pi需要的资源不能马上获得，那么Pi等待直到所有的Pi-1进程结束。当Pi-1结束后，Pi获得所需的资源，执行、返回资源、结束。当Pi结束后，Pi+1获得所需的资源执行，依此类推。6.24基本事实如果一个系统在安全状态，就没有死锁如果一个系统不是处于安全状态，就有可能死锁避免确保系统永远不会进入死锁状态6.25思考为什么系统处于不安全状态，但不一定发生死锁？6.26避免算法单实例资源资源分配图法多实例资源银行家算法6.27资源分配图边转换需求边PiRj：Pi可能以后需要申请Rj资源，用虚线表示Pi申请Rj资源，需求边转换为请求边请求边在资源分配后转换为分配边资源释放后，分配边转换为需求边6.28资源分配图算法假设Pi申请资源Rj请求能满足的前提是：把请求边转换为分配边后不会导致环存在6.29银行家算法多个实例每一个进程必须事先声明使用的最大量当一个进程请求资源，它可能要等待当一个进程得到所有的资源，它必须在有限的时间释放它们6.30银行家算法的数据结构Available:长度为m的向量。如果available[j]=k,那么资源Rj有k个实例有效Max:nxm矩阵。如果Max[i,j]=k,那么进程Pi可以最多请求资源Rj的k个实例Allocation:nxm矩阵。如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例Need:nxm矩阵。如果Need[,j]=k,那么进程Pj还需要k个资源Rj的实例Need[i,j]=Mx[i,j]–Allocation[i,j].N为进程的数目，M为资源类型的数目6.31安全算法1.让Work和Finish作为长度为m和n的向量初始化：Work:=AvailableFinish[i]=falsefori-1,3,…,n.2.查找i(a)Finish[i]=false(b)NeediWorkIfnosuchiexists,gotostep4.3.Work:=Work+AllocationiFinish[i]:=truegotostep2.4.如果对所有i的Finish[i]=true,则系统处在安全状态。6.32是否满足进程Pi的资源请求算法Requesti=进程Pi的资源请求向量.如果Requesti[m]=k则进程Pi想要资源类型为Rjm的k个实例1.如果RequestiNeedi转step2.否则报错,因为进程请求超出了其声明的最大值2.如果RequestiAvailable,转step3.否则Pi必须等待,因为资源不可用.3.假设通过修改下列状态来分配请求的资源给进程Pi:Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi–Requesti;;•如果系统安全将资源分配给Pi.•如果系统不安全Pi必须等待，恢复原有的资源分配状态6.33银行家算法的例子5个进程P0到P4；3个资源类型A(10个实例），B（5个实例），C（7个实例）时刻Tn的快照：AllocationMaxAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433系统处在安全的状态，因为序列P1,P3,P4,P2,P0满足了安全的标准NeedABCP0743P1122P2600P3011P44316.34例子续：P1request(1,0,2)检查RequestAvailable（就是说，(1,0,2)(3,3,2)为真AllocationNeedAvailableABCABCABCP0010743230P1302020P2302600P3211011P4002431执行安全算法表明序列P1,P3,P4,P0,P2满足要求思考：P4的请求(3,3,0)是否可以通过？P0的请求(0,2,0)是否可以通过？5、死锁检测和恢复6.36死锁检测和恢复允许进入死锁状态检测死锁恢复策略6.37每一种资源类型只有一个实例维护等待图节点是进程PiPj表明Pi在等待Pj定期调用算法来检查是否有环一个检查图中是否有环的算法需要n2的操作来进行，n为图中的节点数6.38一个资源类型的多个实例:Available：一个向量的长度m代表每一种资源类型有效的数目Allocation:一个nxm的矩阵定义了当前分配的每一种资源类型的实例数目Request:一个nxm的矩阵表明了当前的进程请求。如果Request[i，j]=k,那么进程Pi请求k个资源Rj的实例6.39检测算法1.让Work和Finish作为长度为m和n的向量初始化(a)Work:=Available(b)Fori=1,2,…,n,ifAllocationi0,thenFinish[i]:=false;otherwise,Finish[i]:=true.2.找到满足下列条件的下标i(a)Finish[i]=false(b)RequestiWork如果没有这样的i存在，转43.Work:=Work+AllocationiFinish[i]:=true转2.4.如果有一些i,1in,Finish[i]=false,则系统处在死锁状态。而且，如果Finish[i]=false,则进程Pi是死锁的。算法需要mxn2次操作来判断是否系统处于死锁状态6.40检测算法的例子五个进程Pn到P4,三个资源类型A（7个实例），B（2个实例）,C（6个实例）时刻Tn的状态AllocationRequestAvailableABCABCABCP0010000000P1200202P2303000P3211100P4002002对所有i，序列P0,P2,P3,P1,P4将导致Finish[i]=true。6.41例子（续）P2请求一个额外的C实例RequestABCP0000P1201P2001P3100P4002系统的状态？可以归还Pn所有的资源，但是资源不够完成其他进程的请求死锁存在，包括进程P1,P2,P3和P46.42检测算法的用法何时及多长时间的调用取决于死锁可能发生的频度有多少进程可能需要被回滚每一个独立的环需要一个如果检测算法被随意的调用，可能图中存在很多的环以至于无法判断是哪一个进程引起了死锁的发生6.43从死锁中恢复：进程终止中断所有的死锁进程一次中断一个进程直到死锁环消失应该选择怎样的中断顺序？进程的优先级进程需要计算多长时间，以及需要多长时间结束进程使用的资源进程完成还需要多少资源多少个进程需要被中断进程是交互的还是批处理6.44从死锁中恢复：抢占资源选择一个：最小化代价回退：返回到安全的状态，然后重新开始进程饥饿：同样进程的可能总是被选中