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

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