操作系统原理方敏死锁课件

单击此处编辑母版标题样式,第一级,第二级,第三级,第四级,第五级,第,*,页,第四章 死 锁,操作系统课程组,内容回顾,UNIX,进程模型,进程结构：,proc,结构，数据段，正文段。,进程状态,调度算法：动态优先级调度算法。,进程创建与终止：,fork(),exit(),。,进程通信：,pipe;sleep,wakeup;wait,exit,。,死锁,2,一、什么是死锁？,死锁,(deadlock),定义：,在,多道程序,中，由于,多个并发进程共享系统的资源,，如果,使用不当,可能会造成一种僵局，即当某个进程提出资源的使用请求后，使得系统中一些进程处于无休止的阻塞状态，在,无外力的作用,下，这些进程将无法继续进行下去，这就是死锁。,3,二、为什么会产生死锁？,产生死锁的环境,多道程序设计技术,多个并发进程,资源共享,(,独占,),没有外力可以借助,使用不当造成的死锁示例,P,、,V,操作不当,进程,T1:,while(true,),启动读卡机,;,送卡片到缓冲区,;,P(S2);,V(S1);,进程,T2:,while(true,),P(S1);,从缓冲区取卡片,;,V(S2);,semaphore s1,s2;,s1=0;s2=0;,4,二、为什么会产生死锁？,进程申请顺序不当,同类资源分配不当,1,2,3,4,5,6,进程,1,进程,2,进程,3,1,2,3,4,5,6,7,5,二、为什么会产生死锁？,进程通信不当,资源的类型,独占资源,VS,非独占资源,永久性资源,VS,临时性资源,独占资源分类,可剥夺式资源,不可剥夺式资源,T1,T3,T2,S3,S1,S2,6,二、为什么会产生死锁？,必要条件,(Coffman 1971,年指出,),资源互斥使用,(,资源独占,),非剥夺控制,(,不可强占,),零散请求,循环等待,破坏其中任何一个条件，就可一防止死锁的发生。,7,三、如何解决死锁问题？,死锁的危害,轻则系统资源利用率严重下降，重则系统崩溃。,解决死锁的策略,置之不理法,鸵鸟政策,优点：简单，简化系统设计，节约成本。,缺点：安全性欠佳。,8,三、如何解决死锁问题？,积极防御法,不让死锁发生,思想：以积极的遏制为出发点。,手段：,破坏产生死锁的必要条件。,分类：,静态策略：进程创建时就由系统分配了所有需要的资源，然后才执行，并且以后没有资源申请要求。缺点：系统效率低，并发性下降，资源浪费严重。,动态策略：执行时动态改变资源分配策略。缺点：实现复杂。优点：灵活，资源利用率高。,9,三、如何解决死锁问题？,事后处理法,让死锁发生，事后处理,提出原因：预防策略虽然可以杜绝死锁发生，但是它提出的策略可能会或多或少影响到系统效率。,思想：可以容忍死锁的发生，事后处理。,优点：灵活，效率高。,10,四、死锁的预防,破坏死锁产生的必要条件,破坏互斥条件,SPOOLing,P1,P2,P3,执行上无先后顺序,剩余票数,n=3,P1,P2,P3,执行上有先后顺序,局限：,破坏“互斥”比较困难，而且对很多资源行不通。,11,四、死锁的预防,破坏不可剥夺条件,思想：允许进程还未执行完成时释放已经占有的资源。,方法,:,已经占有部分资源，还需要资源，如果得不到满足，则释放自己所占有的所有资源，以后再申请。,正在使用资源，有高优先级的进程请求相同资源，则低优先级进程放弃资源。,局限：实现困难，为了恢复现场需要耗费很多时间和空间。因此只适合类似,CPU,、存储器这样的资源。,12,四、死锁的预防,破坏零散请求条件,常常采用静态策略：进程创建时就由系统分配了所有需要的资源，然后才执行，并且以后没有资源申请要求，进程执行完后，释放资源。,缺点：系统效率低，并发性下降，资源浪费严重。,破坏循环等待条件,方法：给资源编号，进程必须按序申请资源。,P1,P5,1,2,4,7,1,2,3,4,5,6,7,3,3,3,4,5,6,7,P1,P5,P2,P3,P4,13,四、死锁的预防,局限：,资源编号困难：尽管资源的按序分配方法消除了死锁的问题，但给资源编号很困难，很难满足每一个进程的要求。,资源的编号很难和进程申请资源的顺序一致：资源顺序分配法是按资源编号申请资源，可能与实际使用资源的顺序不一致，使得一些先申请的资源因暂时不用，而长时间闲置，降低了系统资源利用率。,结论,死锁的预防是以破坏死锁产生的必要条件为基本方法，从而防止死锁发生的。其中由于对资源的申请加上了诸多的限制，因此这种策略虽有一定的效果，但其资源的利用率和效率比较低，很难令人满意。,14,五、死锁的避免,思想,允许死锁产生的条件存在，但通过动态的、明智的选择,在分配资源之前，系统判断假若满足进程的要求是否会发生死锁，如果会，资源就不予分配，从而确保永远不会到达死锁点，避免死锁的发生。,优点：比预防策略更为灵活实用，允许更多的并发，其资源利用率和效率也更高。,15,五、死锁的避免,系统的状态,安全状态,不安全状态,死锁,安全状态：指在某个时刻，当多个进程动态的申请资源时，如果存在一种顺序，使得系统按照这种顺序逐次地为每个进程分配所需资源后每个进程都可以在最终得到最大需求量后，依次顺利地完成。,避免死锁的,关键,就是：让系统在动态分配资源的过程中，不要进入不安全状态。,16,五、死锁的避免,单银行家算法（,Bankers Algorithm,）,1965,年由,Dijkstra,为,T.H.E,系统设计,基本思想：借用了银行借贷系统的分配策略。基于这样一些规则：,客户,银行,1,、第一次申请需要声明最大资金需求量,2,、满足最大需求后要及时归还资金,3,、客户申请的贷款数量不超过它自己拥有的,最大值时，银行要尽量满足客户需求,进程,资源,操作系统,17,客户,a,b,c,d,举例：假设一个银行拥有资金数量为,10,（单位省略），现在有,4,个客户,a,b,c,d,要来贷款，所需最大资金需求量为,8,，,5,，,6,，,7,，为方便期间我们用图形表示如下。,已用资金,最大需求,仍需资金,五、死锁的避免,0,8,8,0,5,5,0,6,6,0,7,7,银行剩余资金,10,初始状态,客户,已用资金,最大需求,仍需资金,a,b,c,d,1,8,7,2,5,3,1,6,5,2,7,5,银行剩余资金,4,状态,1,Q,：,如何分配才能保证银行资金能够顺利周转？,18,五、死锁的避免,客户,已用资金,最大需求,仍需资金,a,b,c,d,1,8,7,5,5,0,1,6,5,2,7,5,银行剩余资金,1,状态,2,客户,已用资金,最大需求,仍需资金,a,b,c,d,1,8,7,1,6,5,2,7,5,银行剩余资金,6,状态,3,客户,已用资金,最大需求,仍需资金,a,b,c,d,1,8,7,6,6,0,2,7,5,银行剩余资金,1,状态,4,客户,已用资金,最大需求,仍需资金,a,b,c,d,1,8,7,2,7,5,银行剩余资金,7,状态,5,19,五、死锁的避免,客户,已用资金,最大需求,仍需资金,a,b,c,d,8,8,0,2,7,5,银行剩余资金,0,状态,6,客户,已用资金,最大需求,仍需资金,a,b,c,d,2,7,5,银行剩余资金,8,状态,7,客户,已用资金,最大需求,仍需资金,a,b,c,d,7,7,0,银行剩余资金,3,状态,8,分配策略：,b,c,a,d,20,五、死锁的避免,算法流程,21,五、死锁的避免,以上讨论的是单银行家算法,只涉及到了一种资源，实际中资源的种类是多样的，一个进程往往需要申请多个资源才能完成工作。解决这一问题需要使用多银行家算法。,22,五、死锁的避免,多项资源银行家算法,举例：系统中有以下资源：,5,台打印机，,7,个手写板，,8,台扫描仪，,9,个读卡器，共有,5,个进程,T1,、,T2,、,T3,、,T4,、,T5,共享这些资源。各进程所需最大资源量和当前各进程请求资源情况如下：,各进程所需最大资源量,当前各进程请求资源,23,1,、,sum,向量：表示系统资源总量,sum=,（,5,，,7,，,8,，,9,）,2,、,allocation,向量：表示当前系统已分配资源,allocation=,（,3,，,5,，,7,，,7,）,3,、,available,向量：表示系统剩余资源,available=sum allocation,=,（,2,，,2,，,1,，,2,）,4,、,claim(i),向量：表示第,i,个进程还需申请资源数,claim(i)=,sum(i),allocation(i),五、死锁的避免,为方面讨论，我们用向量来表示资源分配及占用情况：,sum,allocation,claim(i),24,五、死锁的避免,步骤：,比较,claim(i),和,available,向量，寻找满足下列关系的进程,claim(i)available,available=,（,2,，,2,，,1,，,2,）,allocation,available=,（,2,，,5,，,5,，,2,）,25,五、死锁的避免,available=,（,2,，,6,，,7,，,3,）,allocation,available=,（,3,，,7,，,7,，,5,）,allocation,26,五、死锁的避免,available=,（,5,，,7,，,7,，,6,）,allocation,allocation,available=,（,5,，,7,，,8,，,9,）,27,五、死锁的避免,28,六、死锁的检测和解除,死锁的检测,检测工具,资源分配图,定义：是描述进程申请资源和资源分配情况的关系模型图。表示系统中某个时刻进程对资源的申请和占有情况。,示例：,规则：,（,1,）圆表示一个进程；,（,2,）方块表示一个资源类，其中的圆点表示该类型资源中的单个资源；,（,3,）从资源指向进程的箭头表示资源被分配给了这个进程；,（,4,）从进程指向资源的箭头表示进程申请一个这类资源；,29,六、死锁的检测和解除,一张合理的资源分配图应当满足如下条件,设资源类,Rj,有资源,Wj,个，用,|(Rj,Pi)|,表示,Rj,分配给进程,Pi,的资源个数；用,|(Pi,Rj)|,表示进程,Pi,申请,Rj,资源的资源个数。,1,、资源,Rj,分配给各进程的资源数目不能大于,Wj,，即：,2,、任何一个进程,Pi,对某类资源,Rj,的申请量和已分配数量之和，不应大于该类资源的总数,Wj,，即,：,30,六、死锁的检测和解除,检测方法,化简算法,资源分配图中的所有进程如果都能化简成孤立结点，则这个资源图就是可完全化简的（,completely reducible,）；反之，就是不可完全化简的（,irrreducible,）。,死锁定理：,如果一个系统状态为死锁状态，当且仅当资源分配图是不可完全化简的。也即，如果资源图中所有的进程都成为孤立结点，则系统不会死锁；否则系统状态为死锁状态。,31,六、死锁的检测和解除,举例,结论：系统不会发生死锁。,32,六、死锁的检测和解除,临时资源的死锁检测,临时性资源：即可消耗的资源。如信号、消息、邮件等。,特点：,没有固定数目；,不需要释放。,一般的资源分配图,无法清楚的描述,33,六、死锁的检测和解除,临时性资源分配的表述方式,重定义的资源分配图,定义：,圆表示一个进程；,方块表示一个资源类，其中的圆点表示该类型资源中的单个资源；,由资源类指向进程的箭头表示该进程产生这种资源，一个箭头可表示产生一到多个资源，每个资源类至少有一个生产者进程；,由进程指向资源的箭头表示该进程申请这种资源，一个箭头只表示申请一个资源。,34,六、死锁的检测和解除,死锁判断标准,分析：,一个进程死锁意味着永久被阻塞。,对于临时性资源来讲，它有生产者，生产者会源源不断的生产资源，因此只要生产者进程不被阻塞，可以认为资源最终一定是充分的，可以满足各消费进程的需要。,需要的资源可以满足则进程一定不会死锁。,结论：,判断系统是否死锁的关键在于判断生产者进程的状态，若生产者进程不被阻塞，则可以