《第六章分布式系统中的死锁.ppt》由会员分享，可在线阅读，更多相关《第六章分布式系统中的死锁.ppt（29页珍藏版）》请在三一办公上搜索。
1、第六章 分布式系统中的死锁 6.1 死锁问题,死锁发生的条件,(1)互斥。正如我们第五章所讨论的，互斥是一种资源分配方式，保证同一个资源在同一时刻最多只能被一个进程占用，它用于防止多个进程同时共享访问不可同时共享访问的资源。(2)不可剥夺的资源分配。系统将一个资源的访问权分配给某一个进程后，系统不能强迫该进程放弃对该资源的控制权。(3)占有并等待。必然有一个进程占用了至少一个资源，同时在等待获取被其他进程占用的资源。(4)循环等待。在等待图中有一个循环路径。,郡倘科文哪开碎骸讯携札额涡遣栈帖浴惑瞬萄幌壮扒臣绰介预锨音属凶恋第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的
2、死锁 6.1 死锁问题,死锁的图论模型,可以用图模型来表示死锁，表示死锁的图模型有两种，一种是等待图，另一种是资源分配图。,在等待图中，节点代表进程，当且仅当进程Pi等待一个被进程Pj所占用的资源时，边(Pi,Pj)存在于等待图中，图中的边是有向的。资源分配图中的节点有两种：一种是进程节点，另一种是资源节点。每个边是一个有序对(Pi,Rj)或(Rj,Pi)，其中P代表进程，R代表一个资源类型。边(Pi,Rj)表示进程Pi请求类型为Rj的一个资源，并且正在等待这个资源，一个资源类型中可能有多个资源。边(Rj,Pi)表示类型为Rj的一个资源已经分配给进程Pi。由于等待图假定一个资源类型中只有一个资
3、源，所以资源分配图是一个比等待图更加有力的工具。,嗜丰闷睫沤胰谤新良藏争豺隔半彭蹄茶咆概秀贬冠赌励步卵娘哄究秘坑点第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的图论模型,资源分配图实例：,钳靖婪丹寐乒淌田莽偷静付庙隔远枷埔啊爱念度碑弧摈溶纯婿厩脂呜案锤第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的图论模型,资源分配图到等待图的转化：(1)在资源分配图中找到一个未被处理的资源R。如果所有的资源都已经处理，转向步骤3。(2)从这个资源R的每个输入进程节点到每个输出进程节点之间加一条有向边
4、。一个资源的输入进程节点是等待这个资源的进程节点，一个资源的输出进程节点是占有这个资源的进程节点。转向步骤1。(3)删除所有的资源节点以及相应的边。,宝瘫菱欣砌铲掸滞辖夯待溯顿蝉盔婿魂车获明虚熙仪呼都秀纂郸晶帮慎舟第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的图论模型,资源分配图到等待图的转化实例：,钞擅宙而辛铝胳翔奖通氮账桑讯肄祸携箱熙匀打虞侩阎环猛敷摸覆贴御嘲第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.1 死锁问题,处理死锁的策略死锁,可以使用PAID来概括死锁处理的各种方法：预防(Prevent
5、)、避免(Avoid)、忽略(Ignore)和检测(Detect)。预防死锁。通过限制请求，保证四个死锁条件中至少有一个不能发生，从而预防死锁。避免死锁。如果资源分配会导致一个安全的结果状态，就将资源动态地分配给进程。如果至少有一个执行序列使所有的进程都能完成运行，那么这个状态就是安全的。忽略死锁。忽略死锁是UNIX常采用的一种方法，这种方法只是简单地忽略死锁问题。检测死锁和从死锁中恢复。允许死锁发生，然后发现并解除死锁。,舱纽哀浊嚎止富绸坊众俄往孰淖伏谋襄穷宏拼功格苑削打污资案匈来迫杭第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的AND
6、条件和OR条件,资源死锁和通信死锁：在通信死锁中，进程等待的资源就是报文。资源死锁和通信死锁的真正区别在于资源死锁通常使用AND条件，而通信死锁通常使用OR条件。所谓AND条件就是当进程取得所有所需资源时，它才能继续执行；所谓OR条件就是当进程得到至少一个所需资源，它就能继续执行。在使用AND条件的系统中，死锁条件是在等待图中存在回路。但是在使用OR条件的系统中，等待图中的回路未必会引发死锁。在使用OR条件的系统中，死锁条件是存在结(knot)。一个结K是一个节点集合，对于K中的任何节点a，a能到达K中的所有节点，并且只能到达K中的节点。,嘘峦谈瞧替京润吧自戮铬肪汤斑柯深绪箔慰蛤郝愿橱生泣庚怔
7、初钳兔锅奥第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.1 死锁问题,死锁的AND条件和OR条件,OR条件死锁图例：,吃会恤枢举瘪柞胳衰城颠荫询炮丘壤皆对鳃滇加攘远暂争食掩干适疫溅逞第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.2 死锁的预防,预防死锁的一般方法,死锁预防算法是通过限制进程的资源请求来达到预防死锁的目的，都是通过打破四个死锁条件中的一个条件来实现的。,进程在开始执行之前同时获得所有所需资源。这种方法打破了占有并等待的条件。所有的资源都要被赋予一个唯一的数字编号。一个进程可以请求一个有唯一编号i的资源，条件是
8、该进程没有占用编号小于或等于i的资源。这样，就打破了循环等待的条件。每个进程被赋予一个唯一的优先级标识。优先级标识决定了进程Pi是否应该等待进程Pj，从而打破了不可剥夺的条件。,走氖相风云弛币遮辊溯啡缅藉也惩焦莲敬烫腋西皇馁慨梅朗克秸鸽揣玄仕第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.2 死锁的预防,基于时间戳的预防死锁方法,包括两种死锁预防方案。这两种方案相互补充，这种方法常用于分布式数据库系统中。,等待死亡方案(wait-die scheme)。该方案是基于非剥夺方法。当进程Pi请求的资源正被进程Pj占有时，只有当Pi的时间戳比进程Pj的时间戳小时，即
9、Pi比Pj老时，Pi才能等待。否则Pi被卷回(roll-back)，即死亡。伤害等待方案(wound-wait scheme)。它是一种基于剥夺的方法。当进程Pi请求的资源正被进程Pj占有时，只有当进程Pi的时间戳比进程Pj的时间戳大时，即Pi比Pj年轻时，Pi才能等待。否则Pj被卷回(roll-back)，即死亡。,拆儿舵躁比痈单哥藉笋蝉誉戊昨倦凌侯苦潦卒杰窥屁蜡锹台检刊职堵妄拦第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.2 死锁的预防,基于时间戳的预防死锁方法,图例说明：,赚捉视减网那镊玲匡舰裁镣炼坦慧奥巩稚穿氓鳖脚积胜臀瞩善粉搜邮啸色第六章分布式系统
10、中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,在集中式死锁检测方法中，利用所有的局部资源分配图(或等待图)建立一个全局资源分配图(或等待图)。任何一个机器为它自己的进程和资源维持一个局部的资源分配图。整个系统只有一个协调者，它维持全局的资源分配图，全局的资源分配图是由局部资源分配图组合而成的。,辕访帧蔷炯指唉匪凄烹诗填致拓筏羹范颅霞充愚怕六溶绞爷娘领撩蕾湖淳第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,全局资源分配图(或等待图)的获得方法：当在局部图中有边被加入或删除时，向协
11、调者发送一个报文，协调者根据报文信息对全局图进行更新。定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新。当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新。当开始死锁检测时，协调者便查找全局等待图。如果发现回路，一个进程就会被卷回，从而打破循环等待。缺点：容易产生假死锁的情况。,滁搽扦驶琼英坡俊潍鸿锭旅相巳游脉哦凰禹苯县沏帐供啄询吐怠拟蚌蕉廓第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,产生假死锁的图例说明：,君吕厨
12、爹产子拈亮临镣山恫澈殖协衷诽均瞩挨货酬孔逆哼骆哮楼谢喉佐跌第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,集中式死锁检测,产生假死锁的图例说明：,吧骏牢坑乔哥钙行蔚债蚀喂敖滇刹擦伟矽匪缄圾的豌讶苗茶啊弘尸鲍锯忧第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,分布式死锁检测,Knapp将分布式死锁检测算法分为以下四类：路径推动算法(path-pushing algorithm)。先在每个机器上建立形式简单的全局等待图。每当进行死锁检测时，各个机器就将等待图的拷贝送往一定数量的邻居节点。局部拷贝更新
13、后又被传播下去。这一过程重复进行直到某个节点获得了足够的信息来构造一个等待图以便做出是否存在死锁的结论。边跟踪算法(edge-chasing algorithm)。分布式网络结构图中的回路可以通过沿图的边传播一种叫探测器的特殊信息来检测。当一个发起者得到一个与自己发送的探测器相匹配的探测器时，它就知道它在图中的一个回路里。,今驻沈季赢彦才偶落铬导借育户来霖辨彬碗馅伶因队突氰绍谬亥亩递欠葬第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,分布式死锁检测,Knapp将分布式死锁检测算法分为以下四类：扩散计算(diffusing computation
14、)。怀疑有死锁发生时，事务管理器通过向依赖于它的进程发送查询启动一个扩散进程。这里不会生成全局等待图。发送查询信息时，扩散计算就增长；接收回答后，扩散计算就缩减。根据所得信息，发起者会检测到死锁的发生。全局状态检测(global state detection)。这个方法基于Chandy和Lamport 的快照方法。可以通过建立一个一致的全局状态而无需暂停当前的计算来生成一个一致的全局等待图。,坦丝距七载缕镣让湖棉齐处命较十背驯吊哑增俘条尿去汝控凸调盾遗姬瓣第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,层级式死锁检测,在层级式死锁检测算法中，
15、站点被分层地放在一个树中。一个站点的死锁检测只涉及到它的下一级站点。例如，设A、B和C是控制器，而C是A和B的最低的公共祖先。假定节点Pi出现在控制器A和B的局部等待图中，那么节点Pi也必定出现在如下控制器的等待图中：(1)C控制器；(2)所有位于从C到A的路径上的控制器；(3)所有位于从C到B的路径上的控制器。而且，如果Pi和Pj出现在控制器D的等待图中，并且在D的一个下一级控制器(子控制器)的等待图中有一条从Pi到Pj的路径，那么边(Pi,Pj)一定存在于D的等待图中。,坪聘戒鸟匙伦炒炮窘域问轮捕偷庞乾著椒幻条阂陌显样撤保樊碍瑶珐旨加第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章
16、 分布式系统中的死锁 6.3 死锁的检测,关于死锁检测和恢复的研究方向：,算法正确性。严格证明死锁检测算法的正确性是困难的，由于报文的传输延迟是不可预料的，所以得到一致的全局状态是很困难的。算法性能。需要在信息流量(监测和恢复算法的复杂性)和死锁持续时间(监测和恢复的速度)之间达成妥协。死锁解决。一个好而快的死锁检测算法可能并不能提供足够的信息用于解决死锁。假死锁。一个检测程序不仅要满足前进要求，即必须在有限的时间内发现死锁，还要满足安全要求。如果一个死锁被发现，那么这个死锁应该是确实存在的。死锁概率。检测和恢复算法的设计依赖于给定系统中死锁发生的概率。,拙券蛹箭屈嵌约闲快淳弥疹猿兰钝拯更短蔗
17、察驭链烹赣糕税丁鄙筷贯樱喧第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,AND模型下的Chandy-Misra-Hass算法,在Chandy-Misra-Hass算法中，分布式死锁检测算法使用一个特殊的报文，在等待图中该报文从一个进程传递到另一个进程，该报文称为探测报文(probe message)。如果报文回到发起者，那么就有死锁存在。探测报文包含一个三元组(i,j,k)，表示该报文是一个由进程Pi发起的死锁检测报文，现在由进程Pj所在的站点发往进程Pk所在的站点。当一个进程接收到一个探测报文时，它首先检查自己是否等待某个(
18、或某些)进程，如果它正在等待某个(或某些)进程，它将向所有它等待的进程转发这个探测报文。,臂苞淳其涂渴村含罪餐砧系斟帛撩贼刮恩瞎丽谍鲤荣歼默獭掷被嘘芭蛊耗第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,AND模型下的Chandy-Misra-Hass算法图例说明：,佬杠屏藉掳晋晋壤榔煽述睁麦逮耿叔踏联苦嘲宵烹拽阵丰逐晰滔萍丰估檬第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,AND模型下的Chandy-Misra-Hass算法中打破死锁方法：,一种方法是由探测报文
19、的发起者杀死自己，但是，当有多个进程同时检测到同一个死锁时，与同一个死锁有关的多个进程会被杀死，这样做的效率会很低。另一种方法是每个收到探测报文的进程将自己的标识符附加到探测报文的后面，当探测报文回到发起者进程时，发起者进程选取一个具有最大标识符号码的进程杀死，即使有多个进程同时检测到同一个死锁，它们也会选择杀死同一个进程。,馁菇男甄晃赔慨耘斩姓岔卒晋奴们允茅慌衍具偷坪溃瓷倦廷涅酷任滓诛呼第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,AND模型下的Mitchell-Merritt算法,Mitchell-Merritt算法与Ch
20、andy-Misra-Hass算法的区别：其限制是每个进程每次只能请求一个资源。探测报文在等待图中，沿等待方向的相反方向传送，这样的图叫反向等待图(reversed wait-for graph)。每当进程收到探测报文时，它将自己的标识符和探测报文发起者的标识符相比较，如果自己的标识符大于探测报文发起者的标识符，它就用自己的标识符取代探测报文发起者的标识符，自己变成探测报文的发起者。当几个进程同时发起死锁检测时，只有一个进程能够成为唯一的探测者。,篇富岩凭爷酗轰窘血豌属沼藤瘟薯琐诌私酗丘股睹嫡瘤掂舔吃灌粪欠未圣第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3
21、 死锁的检测,死锁检测的实例,AND模型下的Mitchell-Merritt算法,Mitchell-Merritt算法图例说明：,迈淤哎谩聂露驼喇否庚筹星立喘沽长汐苑祟莹蜂酱楚遮菏馋总舟惩丁章伪第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,AND模型下的Mitchell-Merritt算法,为什么每个进程每次只能请求一个资源？在每个进程每次只能请求一个资源的情况下，等待图中的一个循环中的每个节点都等待环内的节点，所以只有进入环内的边。其反向等待图中则没有进入环内的边，就不会有大标识符的进程产生的探测报文进入回路，而不能检测出死
22、锁。,腥邻时侣汁心觅忌残翼槐爆都洞鼠俄职肋评蜘帚振易滴跺杖鸣咱靠侣肮拴第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,OR模型下的Chandy-Misra-Hass算法,使用两类报文：(query,i,j,k)和(reply,i,j,k)，表示这些报文属于由进程Pi发起的并由Pj送往Pk的扩散计算。一个进程的依赖集合包括所有它在等待以便获得报文的进程。如果接收进程Pk是活动的，它会忽略所有的查询和回答报文。如果它被阻塞，它会向它的依赖集合中的进程发送查询。一旦收集到回答报文，接收进程将向发起者发送一个回答报文。发起者以及每个中间
23、进程用一个计数器记录查询和回答的数目。如果这两个数字相同，即发起者的每个查询都得到了回答，就表明发起者处于死锁状态。,座揽忿渝烹阎共贺多谗斟剑弘欢淤层榜域俄恍业意忱坎柴噶搁陡逝财巨样第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,OR模型下的Chandy-Misra-Hass算法,当接收进程Pk处于阻塞状态时，会有几种可能：如果这是Pi发起的第一个来自Pj的报文(这个报文的发送者Pj叫做Pk关于Pi的结合者)，它将向它的依赖集合中的所有进程发送这个查询，并且将查询数目存储在一个局部变量num(i)中。令局部变量wait(i)表示
24、这一进程从它接收到它的第一个由Pi发起的查询起一直被阻塞这一事实。如果这个查询是Pi发起的但不是第一个来自Pj的报文，即当wait(i)仍然成立时，Pk将马上回答。如果从wait(i)变为假的那一时刻Pk运行过，那么这个查询就被丢弃。,汰婆计晾空蹭役憎廓叮裤姆塑烽昔党绝做晓疫硫州淌郡颅追妙泞删酸皋窍第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,死锁检测的实例,OR模型下的Chandy-Misra-Hass算法图例说明：,荔进墅等剐怯婉殴汞价泽淘葵酵疾麻煌诡程啃子褒埂洪仙力菌怯峨裴蛇触第六章分布式系统中的死锁第六章分布式系统中的死锁,第六章 分布式系统中的死锁 6.3 死锁的检测,表汉摄蛾坞闪义寂苏蓑推揽俞式浙涌咙杖牺掸贿徽挤松炉爪追驾亏岿别姚第六章分布式系统中的死锁第六章分布式系统中的死锁,
