搜索
第3章死锁内容提要：3.1资源3.2死锁概念3.3死锁的预防3.4死锁的避免3.5死锁的检测和恢复3.6处理死锁的综合方式3.1资源3.1.1资源使用模式1．申请2．使用3．释放3.1.2可剥夺资源与不可剥夺资源1．可剥夺资源•另外进程可以从拥有它的进程那里把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。2．不可剥夺资源•不能从当前占有它的进程那里强行抢占的资源，必须由拥有者自动释放，否则会引起相关计算的失效。3.1.2可剥夺资源与不可剥夺资源死锁和不可剥夺资源有关•硬件资源•软件资源•可再用资源（SR）•消耗性资源（CR）3.2死锁概念3.2.1什么是死锁1．死锁示例图3-1汽车过窄桥时的冲突3.2.1什么是死锁在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁。生产者进程Producer：消费者进程consumer：while(TRUE){while(TRUE){P(mutex);P(mutex);P(empty);P(full);……}}3.2.1什么是死锁2．死锁定义•所谓死锁，是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。•计算机系统产生死锁的根本原因就是资源有限且操作不当3.2.1什么是死锁有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。进程A进程B…………申请并占用R申请并占用S申请并占用S申请并占用R…………释放R释放S释放S释放R…………3.2.1什么是死锁图3-2进程推进顺序对引发死锁的影响3.2.2死锁的条件当计算机系统同时具备下面4个必要条件时，会发生死锁。1．互斥条件2．占有且等待条件3．不可抢占条件4．循环等待条件只要有一个必要条件不满足，则死锁就可以排除。3.2.3资源分配图1．资源分配图的构成•该图由结对组成：G=(V,E)。式中，V是顶点的集合，E是边的集合。顶点集合可分为两部分：P={p1,p2,…,pn}，它由系统中所有活动进程组成；R={r1,r2,…,rm}，它由系统中全部资源类型组成。•有向边pi→rj称为申请边，而有向边rj→pi称为赋给边。•在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。3.2.3资源分配图2．资源分配图示例:图3－3资源分配图示例:3.2.3资源分配图3．环路与死锁①如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。②如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。资源分配图中存在环路是死锁存在的必要条件，但不是充分条件。3.2.3资源分配图•如果资源分配图中没有环路，那么系统不会陷入死锁状态。如果存在环路，那么系统有可能出现死锁，但不确定。图3-4有死锁的资源分配图图3-5有环路但无死锁的资源分配图3.2.4处理死锁的方法①利用某些协议预防或避免死锁，保证系统不会进入死锁状态。②允许系统进入死锁状态，然后设法发现并克服它。③完全忽略这个问题，好像系统中从来也不会出现死锁。3.3死锁的预防3.3.1破坏互斥条件3.3.2破坏占有且等待条件•一种办法是预分资源策略静态分配•另一种办法是“空手”申请资源策略3.3.3破坏非抢占条件•申请•资源•进程当前所占有的全部资源可被抢占•另一种方法是抢占等待者的资源3.3.4破坏循环等待条件1。一种方法是实行资源有序分配策略设R={r1,r2,…,rm}，表示一组资源•定义一对一的函数F：R→N，式中N是一组自然数。例如，•F（磁带机）=1，F（磁盘机）=5，F（打印机）=12•做如下约定：所有进程对资源的申请严格按照序号递增的次序进行。2。另一种申请办法也很简单：先弃大，再取小。3.4死锁的避免排除死锁的动态策略——死锁的避免3.4.1安全状态•在当前分配状态下，进程的安全序列{P1,P2,…,Pn}是这样组成的：若对于每一个进程Pi（1≤i≤n），它需要的附加资源可被系统中当前可用资源与所有进程Pj（j＜i）当前占有资源之和所满足，则{P1,P2,…,Pn}为一个安全序列。这时系统处于安全状态。3.4死锁的避免•死锁是不安全状态中的特例时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T03229473T13429471T23029—75T33079—70T43009——7T5900———1T6000———10表3-1安全状态示意3.4死锁的避免表3-2不安全状态示意时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T0′3229473T1′4229472T2′4429470T3′4029—743.4死锁的避免①死锁状态是不安全状态。②如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。③如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。3.4.2资源分配图算法•单体资源类•多体资源类•除申请边和赋给边之外，还要有一种称为“要求边”的新边。要求边pirj表示进程pi能够申请资源rj，有时用虚线表示。3.4.2资源分配图算法图3-6资源分配图示例图3-7处于不安全状态的资源分配图3.4.3银行家算法•最著名的避免死锁的算法叫做“银行家算法”（Banker’sAlgorithm）。•银行家算法的设计思想是：当用户申请一组资源时，系统必须做出判断；如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。数据结构令n表示系统中进程的数目，m表示资源分类数。①Available是一个长度为m的向量，它表示每类资源可用的数量。Available[j]=k，表示rj类资源可用的数量是k。②Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max[i,j]=k，表示进程pi至多可申请k个rj类资源单位。③Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation[i,j]=k，表示进程pi当前分到k个rj类资源。④Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i,j]=k，表示进程pi尚需k个rj类资源才能完成其任务。可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。1．资源分配算法•令Requesti表示进程pi的申请向量。Requesti[j]=k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作：①若Requesti＞Needi，表示出错，②如果Requesti＞Available，则pi等待。③假设系统把申请的资源分给进程pi，则应对有关数据结构进行修改：Available：=Available–RequestiAllocationi：=Allocationi+RequestiNeedi：=Needi–Requesti④系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成③之前的情况。2．安全性算法①令Work和Finish分别表示长度为m和n的向量，最初，置Work：=Available，Finish[i]：=false，i=1,2,…,n。②搜寻满足下列条件的i值：Finish[i]=false，且Needi≤Work。若没有找到，则转向④。③修改数据值：Work：=Work+Allocationi（pi释放所占的全部资源）Finish[i]=true转向②。④若Finish[i]=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。3．算法应用示例•假定系统中有4个进程{A,B,C,D}和三类资源R1,R2和R3，各自的数量分别为9,3和6个单位。进程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420表3-3T0时刻资源分配表资源情况（1）T0时刻是安全的•存在一个安全序列{B,A,C,D}资源情况WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true进程表3-4T0时刻的安全序列（2）进程A请求资源•进程A发出请求Request（1,0,1）资源情况进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系统进入不安全的状态为了避免发生死锁，即使当前可用资源能满足某个进程的申请，也有可能不实施分配，让该进程阻塞。表3-5为进程A分配资源后的有关数据3.5死锁的检测和恢复死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。3.5.1对单体资源类的死锁检测等待图。它是从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的。•当且仅当等待图中有环路，系统存在死锁。图3-8资源分配图和对应的等待图3.5.2对多体资源类的死锁检测这个检测算法采用若干随时间变化的数据结构，与银行家算法中所用的结构相似。①Available是一个长度为m的向量②Allocation是一个n×m的矩阵③Request是一个n×m的矩阵•检测算法只是简单地调查尚待完成的各个进程所有可能的分配序列。3.5.2对多体资源类的死锁检测①令Work和Finish分别表示长度为m和n的向量，初始化Work：=Available；对于i=1,2,…,n，如果Allocationi≠0，则Finish[i]：=false；否则Finish[i]：=true。②寻找一个下标i，它应满足条件：Finish[i]=false且Requesti≤Work若找不到这样的i，则转到④。③修改数据值：Work：=Work+AllocationiFinish[i]=true转向②。④若存在某些i（1≤i≤n），Finish[i]=false，则系统处于死锁状态。此外，若Finish[i]=false，则进程pi处于死锁环中。3.5.2对多体资源类的死锁检测•设系统中有5个进程p1,p2,p3,p4和p5，有3类资源R1,R2和R3，每类资源的个数分别为7,2,6。AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002表3-6死锁检测示例资源分配情况可以找到序列{p1,p3,p4,p2,p5}，对于所有的i都有Finish[i]=true，系统在T0时刻没有死锁。资源情况进程假定，进程p3现在申请一个单位的R3资源，则系统资源分配情况如表3-7所示。AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202000p3303001p4211100p5002002由于对所有i=1,2,…,5，Allocationi≠0，所以Finish[i]=false。表3-7p3申请一个单位的R3资源后的资源分配数据资源情况进程3.5.3从死锁中恢复主要有三种方式：通过抢占资源实现恢复、通过回退执行实现恢复和通过杀掉进程实现恢复。1．通过抢占资源实现恢复•即临时性地把资源从当前占有它的进程那里拿过来，分给另外某些