搜索
第3章死锁本章内容提要资源死锁概念死锁的预防死锁的避免死锁的检测和恢复处理死锁的综合方式3.1资源3.1.1资源使用模式●申请●使用●释放3.1.2可剥夺资源与不可剥夺资源●按占有方式划分：▲可剥夺资源当该资源被某进程拥有后，其它进程仍可以把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。▲不可剥夺资源该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。◎死锁和不可剥夺资源有关●按其它方式划分3.2死锁概念3.2.1什么是死锁1．死锁示例汽车过窄桥时的冲突▲在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁2．死锁定义死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。计算机系统产生死锁的根本原因就是资源有限且操作不当死锁的危害系统瘫痪资源浪费……什么是死锁有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。进程A进程B…………申请并占用R申请并占用S申请并占用S申请并占用R…………释放R释放S释放S释放R…………什么是死锁进程推进顺序对引发死锁的影响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称为赋给边在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。2．资源分配图示例（1）集合P,R和E如下：P={p1,p2,p3}R={r1,r2,r3,r4}E={p1→r1,p2→r3,r1→p2,r2→p2,r2→p1,r3→p3}（2）资源数量分别为1，2，1，3（3）进程状态该图不含环路，没有死锁资源分配图示例3．环路与死锁①如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。环路与死锁有死锁的资源分配图有环路但无死锁的资源分配图②如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。●资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。3.2.4处理死锁的方法■利用某些协议预防或避免死锁，保证系统不会进入死锁状态。■允许系统进入死锁状态，然后设法发现并克服它。■完全忽略这个问题，好像系统中从来也不会出现死锁。3.3死锁的预防3.3.1破坏互斥条件3.3.2破坏占有且等待条件●预分资源策略——静态分配●“空手”申请资源策略——不占有资源时才可以申请资源▲存在以下4个主要缺点◎不可预测◎利用率低◎降低并发性◎“饥饿”现象3.3.3破坏非抢占条件隐式抢占方式抢占等待者资源3.3.4破坏循环等待条件①资源有序分配策略●资源编号设R={r1,r2,…,rm}，表示一组资源定义一对一的函数F：R→N，N是一组自然数。如：F（磁带机）=1，F（磁盘机）=5，F（打印机）=12●依序分配约定：所有进程对资源的申请严格按照序号递增的次序进行。破坏循环等待条件②先弃大，再取小一个进程申请资源rj，它应释放所有满足F(ri)≥F(rj)关系的资源ri▲这两种办法都是可行的，都可排除环路等待条件▲优点：资源利用率和系统吞吐量都有很大提高▼缺点：①资源请求受限，合理编号困难，增加系统开销。②暂不使用的资源也需提前申请，增加资源占用时间。3.4死锁的避免●排除死锁的动态策略。关键是确定资源分配的安全性3.4.1安全状态在当前分配状态下，进程的安全序列{P1,P2,…,Pn}是：若对于每一个进程Pi（1≤i≤n），它需要的附加资源可被系统中当前可用资源与所有进程Pj（j＜i）当前占有资源之和所满足，则{P1,P2,…,Pn}为一个安全序列。这时系统处于安全状态。●存在安全序列时一定不会有死锁发生死锁是不安全状态中的特例安全状态安全状态示意设系统中共有10台磁带机，有三个进程p1,p2和p3，分别拥有3台、2台和2台磁带机，而它们各自的最大需求分别是9台、4台和7台磁带机。此时，系统已分配了7台磁带机，还有3台空闲。下表给出三个进程在不同时刻占有资源及向前推进的情况。时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T03229473T13429471T23029—75T33079—70T43009——7T5900———1T6000———10不安全状态示意时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T0′3229473T1′4229472T2′4429470T3′4029—74若不按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态死锁的避免①死锁状态是不安全状态。②如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。③如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。3.4.2资源分配图算法资源类单体资源类多体资源类单体资源类的资源分配图除申请边和赋给边之外，还要有一种称为“要求边”的新边。要求边pirj表示进程pi能够申请资源rj，有时用虚线表示。资源分配图示例处于不安全状态的资源分配图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类资源才能完成其任务。▲记号：令X和Y表示长度为n的向量可以把矩阵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个单位。进程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420T0时刻资源分配表（安全）资源情况（1）T0时刻是安全的存在一个安全序列{B,A,C,D}资源情况WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true进程T0时刻的安全序列（2）进程A请求资源进程A发出请求Request（1,0,1）资源情况进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系统进入不安全的状态不能为进程A分配所申请的资源为进程A分配资源后的有关数据银行家算法优点：限制条件少资源利用程度提高缺点：①难以保证进程数固定不变②未考虑实时进程快速响应③增加了系统开销3.5死锁的检测和恢复死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。3.5.1对单体资源类的死锁检测■等待图——资源分配图的变形从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的资源分配图和对应的等待图3.5.2对多体资源类的死锁检测■采用若干随时间变化的数据结构，与银行家算法相似①Available是一个长度为m的向量②Allocation是一个n×m的矩阵③Request是一个n×m的矩阵，Request[i,j]=k，表示进程pi正申请k个rj类资源仍把矩阵Allocation和Request的行作为向量对待，并分别表示为Allocationi和Requesti对多体资源类的死锁检测■检测算法简单地调查尚待完成的各个进程所有可能的分配序列①令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处于死锁环中。对多体资源类的死锁检测设系统中有5个进程p1,p2,p3,p4和p5，有3类资源R1,R2和R3，每类资源的个数分别为7,2,6。AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002死锁检测示例资源分配情况▲可以找到序列{p1,p3,p4,p2,p5}，对于所有的i都有Finish[i]=true，系统在T0时刻没有死锁。资源情况进程假定，进程p3现在申请一个单位的R3资源AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p220