第六章分布式系统中的死锁.ppt
《第六章分布式系统中的死锁.ppt》由会员分享,可在线阅读,更多相关《第六章分布式系统中的死锁.ppt(29页珍藏版)》请在三一文库上搜索。
1、第六章 分布式系统中的死锁 6.1 死锁问题,死锁发生的条件,(1) 互斥。正如我们第五章所讨论的,互斥是一种资源分配方式,保证同一个资源在同一时刻最多只能被一个进程占用,它用于防止多个进程同时共享访问不可同时共享访问的资源。 (2) 不可剥夺的资源分配。系统将一个资源的访问权分配给某一个进程后,系统不能强迫该进程放弃对该资源的控制权。 (3) 占有并等待。必然有一个进程占用了至少一个资源,同时在等待获取被其他进程占用的资源。 (4) 循环等待。在等待图中有一个循环路径。,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的图论模型,可以用图模型来表示死锁,表示死锁的图模型有两种,一种是等待图
2、,另一种是资源分配图。,在等待图中,节点代表进程,当且仅当进程Pi等待一个被进程Pj所占用的资源时,边(Pi,Pj)存在于等待图中,图中的边是有向的。 资源分配图中的节点有两种:一种是进程节点,另一种是资源节点。每个边是一个有序对(Pi,Rj)或(Rj,Pi),其中P代表进程,R代表一个资源类型。边(Pi,Rj)表示进程Pi请求类型为Rj的一个资源,并且正在等待这个资源,一个资源类型中可能有多个资源。边(Rj,Pi)表示类型为Rj的一个资源已经分配给进程Pi。由于等待图假定一个资源类型中只有一个资源,所以资源分配图是一个比等待图更加有力的工具。,第六章 分布式系统中的死锁 6.1 死锁问题,死
3、锁的图论模型,资源分配图实例:,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的图论模型,资源分配图到等待图的转化: (1)在资源分配图中找到一个未被处理的资源R。如果所有的资源都已经处理,转向步骤3。 (2)从这个资源R的每个输入进程节点到每个输出进程节点之间加一条有向边。一个资源的输入进程节点是等待这个资源的进程节点,一个资源的输出进程节点是占有这个资源的进程节点。转向步骤1。 (3)删除所有的资源节点以及相应的边。,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的图论模型,资源分配图到等待图的转化实例:,第六章 分布式系统中的死锁 6.1 死锁问题,处理死锁的策略死锁,可以使用P
4、AID来概括死锁处理的各种方法:预防(Prevent)、避免(Avoid)、忽略(Ignore)和检测(Detect) 。 预防死锁。通过限制请求,保证四个死锁条件中至少有一个不能发生,从而预防死锁。 避免死锁。如果资源分配会导致一个安全的结果状态,就将资源动态地分配给进程。如果至少有一个执行序列使所有的进程都能完成运行,那么这个状态就是安全的。 忽略死锁。忽略死锁是UNIX常采用的一种方法,这种方法只是简单地忽略死锁问题。 检测死锁和从死锁中恢复。允许死锁发生,然后发现并解除死锁。,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的AND条件和OR条件,资源死锁和通信死锁:在通信死锁中,进
5、程等待的资源就是报文。资源死锁和通信死锁的真正区别在于资源死锁通常使用AND条件,而通信死锁通常使用OR条件。 所谓AND条件就是当进程取得所有所需资源时,它才能继续执行;所谓OR条件就是当进程得到至少一个所需资源,它就能继续执行。 在使用AND条件的系统中,死锁条件是在等待图中存在回路。但是在使用OR条件的系统中,等待图中的回路未必会引发死锁。在使用OR条件的系统中,死锁条件是存在结(knot)。一个结K是一个节点集合,对于K中的任何节点a,a能到达K中的所有节点,并且只能到达K中的节点。,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的AND条件和OR条件,OR条件死锁图例:,第六章
6、分布式系统中的死锁 6.2 死锁的预防,预防死锁的一般方法,死锁预防算法是通过限制进程的资源请求来达到预防死锁的目的,都是通过打破四个死锁条件中的一个条件来实现的。,进程在开始执行之前同时获得所有所需资源。这种方法打破了占有并等待的条件。 所有的资源都要被赋予一个唯一的数字编号。一个进程可以请求一个有唯一编号i的资源,条件是该进程没有占用编号小于或等于i的资源。这样,就打破了循环等待的条件。 每个进程被赋予一个唯一的优先级标识。优先级标识决定了进程Pi是否应该等待进程Pj,从而打破了不可剥夺的条件。,第六章 分布式系统中的死锁 6.2 死锁的预防,基于时间戳的预防死锁方法,包括两种死锁预防方案
7、。这两种方案相互补充,这种方法常用于分布式数据库系统中。,等待死亡方案(wait-die scheme)。该方案是基于非剥夺方法。当进程Pi请求的资源正被进程Pj占有时,只有当Pi的时间戳比进程Pj的时间戳小时,即Pi比Pj老时,Pi才能等待。否则Pi被卷回(roll-back),即死亡。 伤害等待方案(wound-wait scheme)。它是一种基于剥夺的方法。当进程Pi请求的资源正被进程Pj占有时,只有当进程Pi的时间戳比进程Pj的时间戳大时,即Pi比Pj年轻时,Pi才能等待。否则Pj被卷回(roll-back),即死亡。,第六章 分布式系统中的死锁 6.2 死锁的预防,基于时间戳的预防
8、死锁方法,图例说明:,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,在集中式死锁检测方法中,利用所有的局部资源分配图(或等待图)建立一个全局资源分配图(或等待图)。任何一个机器为它自己的进程和资源维持一个局部的资源分配图。整个系统只有一个协调者,它维持全局的资源分配图,全局的资源分配图是由局部资源分配图组合而成的。,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,全局资源分配图(或等待图)的获得方法: 当在局部图中有边被加入或删除时,向协调者发送一个报文,协调者根据报文信息对全局图进行更新。 定期地更新,每个机器定期地向协调者发送自上次更新以来所有添加的边和删
9、除的边,协调者根据报文信息对全局图进行更新。 当协调者认为需要运行回路检测算法时,它要求所有的机器向它发送局部图的更新信息,协调者对全局图进行更新。 当开始死锁检测时,协调者便查找全局等待图。如果发现回路,一个进程就会被卷回,从而打破循环等待。 缺点:容易产生假死锁的情况 。,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,产生假死锁的图例说明:,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,产生假死锁的图例说明:,第六章 分布式系统中的死锁 6.3 死锁的检测,分布式死锁检测,Knapp将分布式死锁检测算法分为以下四类: 路径推动算法(path-pushin
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 分布式 系统 中的 死锁
链接地址:https://www.31doc.com/p-2095755.html