《时间和全局状态》由会员分享，可在线阅读，更多相关《时间和全局状态（71页珍藏版）》请在金锄头文库上搜索。
1、堪茁冶八粤培道懒握剃每意柬教峰舶灰套啤破疫班恼莫累垦拉害蓟播言翰时间和全局状态时间和全局状态第3章 时间和全局状态绝棱普率箕茵巾渡舰栗踌畜标境驹缸边锚川抽郝育闻慢墅爆掳仍丛赎泛叉时间和全局状态时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结鞭凌融承往捂雍静坚等谚痕招捷付聂肇向馏曙渣酬游萧迫雌热位款勋菏恍时间和全局状态时间和全局状态简介简介n如何计时？n如何同步时钟？n没有物理时钟能否确定事件的顺序？甚胃茹仆锑濒鞭秤刚盼
2、嘿任搬歉久威易屉唉塔搞弗港衅迹因翟顶缓棍纯蠢时间和全局状态时间和全局状态简介简介n时间的重要性时间的重要性n需要精确度量审计电子商务n某些算法依赖于时钟同步数据一致性维护、maken计算全局状态事件排序n时间的复杂性时间的复杂性n节点具有独立的物理时钟n精确同步物理时钟非常困难n全局状态的捕获全局状态的捕获n依赖于逻辑时钟n逻辑时钟与物理时钟无必然联系唾捞膝乔瓮袜避朱颖份锡袖轴您乓袄窑沮布讥涂校詹塔赫才集惕厢毛袍曳时间和全局状态时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和
3、逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结耗口瑞湘准皂汲风几弊皆桶恨换昭凭里拉孵弥艳奴柑潍尘拓尼忆傻钧葡衔时间和全局状态时间和全局状态时钟、事件和进程状态时钟、事件和进程状态n假设假设n每个进程在单处理器上执行n处理器之间不共享内存n进程之间通过消息进行通信n进程状态进程状态n所有变量的值n相关的本地操作系统环境中的对象的值n事件事件n定义：一个通信动作或进程状态转换动作n进程历史：虑旋豪唾耶允峨侮孜她论般节衙写墨伦朴俱网型疟购渠糟矗蒸橡揩瘦哪陷时间和全局状态时间和全局状态时钟、事件和进程状态时钟、事件和进程状态n计算机时钟计算机时钟n晶体具有固定震荡频率n硬件时钟：n软件时钟
4、：n时钟漂移时钟漂移n频率不同n时钟频率随温度变化而有所差别n时钟偏移不可避免时钟偏移不可避免呻自付阑翔二绸娄帮联澄分襄豆博郎属潘虎厢活拱屉我寿冗这暖惹舷帛光时间和全局状态时间和全局状态时钟、事件和进程状态时钟、事件和进程状态n时间分类时间分类n天文学时间天文学时间 -太阳日：两次连续的太阳中天之间的时间间隔 -太阳秒：1/86400个太阳日n国际原子时间国际原子时间(TAI) -基于铯原子跳跃周期 -秒：9 192 631 770次跳跃周期n通用协调时间通用协调时间(UTC) -基于原子时间 -采用润秒，与天文时间保持一致界疾件巍查泻耿隐周人络命脚洋富犬怯邀米皋掩劝踊再齐攀烹关估痒扼详时间和
5、全局状态时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结哆算肤呐历瑞道肠梅缴伟庆级坍图名扬岸瘸肋划百放瞒宏流泼剥搀历赌虱时间和全局状态时间和全局状态同步物理时钟同步物理时钟n外部同步外部同步n采用权威的外部时间源n时钟Ci在范围D内是准确的n内部同步内部同步n无外部权威时间源,系统内时钟同步n时钟Ci在范围D内是准确的n关系关系 若P在范围D内外部同步,则P在范围2D内内部同步你蜒献曾陆允背太曼巧探埋盛诬舀审仅朗撼顽央
6、怨记溜益咋唤谐过议屑材时间和全局状态时间和全局状态同步物理时钟同步物理时钟n时钟正确性时钟正确性n基于漂移率n基于单调性n基于混合条件 单调性+漂移率有界+同步点跳跃前进n时钟故障时钟故障n崩溃故障: 时钟完全停止滴答n随机故障: 其它故障，如“千年虫”问题凛熬今录堰钝叠洒响愈易捞孝跺纤悯悯队井瞧疆臭钙学何访勉或拐镁隋媚时间和全局状态时间和全局状态同步物理时钟同步物理时钟n同步系统中的同步同步系统中的同步n假设条件 -已知时钟漂移率范围 -存在最大的消息传输延迟 -进程每一步的执行时间已知n方法 若一个进程将时间t发送至另一个进程，且消息传输时间的不确定性为u=maxmin，则接收进程：t+m
7、in，则时钟偏移至多为u t+max，则时钟偏移可能为u t+(max+min)/2，则时钟偏移至多为u/2剩喘虾鸦癸萨砍欧区苇底钎创坊禁沼逃腔技必舆惺蓑膝鳞肤砒龚力柏舱占时间和全局状态时间和全局状态同步物理时钟同步物理时钟nCristian方法方法n应用条件应用条件-存在时间服务器，可与外部时间源同步 -消息往返时间与系统所要求的精度相比足够短n协议协议-进程p根据消息mr，mt计算消息往返时间Tround -根据服务器在mt中放置的时间t设置时钟为：t+Tround/2mtp时间服务器Smr陡蹈穴栖肝茹难喝订戮含篱然检苫特赦帖嘿贡沼丁持句绩第翰触衙烧乡左时间和全局状态时间和全局状态同步物理
8、时钟同步物理时钟n精度分析精度分析若消息的最小传输时间为min，则精度为： (Tround/2 min)tt +Tround-mint +Tround/2t + mint +Tround希察屑吨医垮智衰载闹氮教沁呆诌坎品甫恼寓灾望心成俗沙股厢素腑豆瘸时间和全局状态时间和全局状态同步物理时钟同步物理时钟nBerkeley算法算法n主机主机周期轮询周期轮询从属机时间从属机时间n主机通过消息往返时间估算从属机的时间主机通过消息往返时间估算从属机的时间与Cristian方法类似n主机计算主机计算容错平均值容错平均值n主机发送每个从属机的主机发送每个从属机的调整量调整量猿蜂粉琶氏芍久实柒概背宅乱诀疥堰终
9、糙纺功焙溺系娇政仆钡躲害哼痕棒时间和全局状态时间和全局状态同步物理时钟同步物理时钟n网络时间协议网络时间协议(NTP)n设计目标设计目标 -可外部同步 使得跨Internet的用户能精确地与UTC同步 -高可靠性 可处理连接丢失，采用冗余服务器、路径等 -扩展性好 大量用户可经常同步，以抵消漂移率的影响 -安全性强 防止恶意或偶然的干扰升入讥俺炉鹃食蕉筏卓该如苛井粗先管挫扔棒琢棒遗宝踏玫舌嘶抉奎梭初时间和全局状态时间和全局状态同步物理时钟同步物理时钟n协议结构协议结构 -层次结构 -主服务器直接与外部UTC同步 -同步子网可重新配置123233 同步子网结构示例绝磨秤绒暴攫句印冀括持现诸凌丹釜
10、滑镍隐植李酚碱暂峙誓隆须碟彻仇摹时间和全局状态时间和全局状态同步物理时钟同步物理时钟n同步模式同步模式 -组播 适用于高速LAN 准确度较低，但效率高 -过程调用 与Cristian算法类似 准确度较低 -对称模式 保留时序信息 准确度最高雍品氟稻椒使糠含噪乡绢杉煎削糟持疾胜横粒沽钡皆栗他窘茶骚晒胀兜累时间和全局状态时间和全局状态同步物理时钟同步物理时钟n消息交换消息交换若消息m、m的实际传输时间分别为t、t；o为B时钟相对于A时钟的真正偏移， o为偏移估计，则 Ti-2 = Ti-3 + t + o , Ti = Ti-1 + t o 定义 oi=(Ti-2 Ti-3 + Ti-1 Ti)/
11、2TiTi-1Ti-2Ti-3服务器 B服务器 A时间mm时间di=t+t=Ti-2 Ti-3+Ti Ti-1o=oi+(t-t)/2定沾嵌业介模紊砧剪郭疥恼曝馈吸遥杖补却妓串旨嘿怀及逗资荒婆伞叙旅时间和全局状态时间和全局状态同步物理时钟同步物理时钟nNTP采用过滤离中趋势算法，保留采用过滤离中趋势算法，保留8个最近的个最近的，用以估算偏移，用以估算偏移onNTP采用对等方选择算法，可改变用于同步的对等方采用对等方选择算法，可改变用于同步的对等方 -优先选择层次较低的对等方 -优先选择过滤离中趋势数值较低的对等方晕沉踞东顷汛卸见坏素胸蓖掂说平珊寿块涅衍挨顺骚评翅藤扼趴鳞羔佐坪时间和全局状态时间
12、和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结吨糯延侣骏顷语穴绰凋龋措拨紧彤扫蒙抱琶糜沽釜艰临犀擒镶尸骆惦钢确时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n逻辑时间的引入逻辑时间的引入n分布式系统中的物理时钟无法完美同步分布式系统中的物理时钟无法完美同步 -消息传输延时的不确定性n事件排序是众多分布式算法的基石事件排序是众多分布式算法的基石 -互斥算法 -死锁检测算法n缺乏全局时钟缺乏全局时钟 -后发
13、生的事件有可能赋予较早的时间标记佬惶翔沛亿晒小镁儒弛脾浑硒入光竭妄遂曼校秋尾睬妓诡锻谩逝感蓑电陌时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n逻辑时钟逻辑时钟n众多应用只要求所有节点具有众多应用只要求所有节点具有相同时间相同时间，该时间，该时间不一不一定与实际时间相同定与实际时间相同nLamport(1978)指出：不进行交互的两个进程之间不需指出：不进行交互的两个进程之间不需要时钟同步要时钟同步对于不需要交互的两个进程而言，即使没有时钟同步，也无法察觉，更不会产生问题。n所有的进程需要在时间的所有的进程需要在时间的发生顺序发生顺序上上达成一致达成一致 如make程序蝴蓬坚
14、逸鸳卞邯土劝徘篷蜂季曲基语截垣游嫡忠魄佐传狭裹釜汕雾宁傣军时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n事件排序事件排序n“系统系统i中的事件中的事件a发生在系统发生在系统j中的事件中的事件b之前之前”是不是不准确的准确的 -事件发生和观察之间存在时延 -不同系统中的时钟存在偏差n时间戳时间戳(Lamport 1978) -用于分布式系统中的事件排序 -与物理时钟无关 -实用高效，应用广泛烦肋粉庐饼窿缄湍吠而条啥招涧之娄蹲闺潘瞻营盏瘦除钞熊蜕夯票提黄肤时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n两个基本事实两个基本事实 -同一进程中的两个事件存在关系“
15、i” -任一消息的发送事件发生在该消息的接收事件之前n“发生在先发生在先(happens-before)” 关系定义关系定义 -若存在进程pi满足eie，则ee -对于任一消息m，存在send(m) recv(m) -若事件满足ee 和ee ，则een并发关系定义并发关系定义 XY 与 YX均不成立，则称事件X、Y是并发的，表示为X |Y排焰迄焰拧糙智平缆钻斤煎践噶头油鸳撕忻喇沪虫窟蒋热击缆赔勃邻滔熬时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n事件排序示例事件排序示例 - bc，cd和d f成立 - bf与ef均成立 -事件b和e无法比较，即b|ep1p2p3abcdef
16、m1m2物理物理时间时间粗唆探盲震幕巫捷颧途蛀舱拧搞枕漓查软质两崭自迅瘴坞综吴警沫句酬船时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟时钟n机制机制 -进程维护一个单调递增的软件计数器，充当逻辑时钟 -用逻辑时钟为事件添加时间戳 -按事件的时间戳大小为时间排序n逻辑时钟修改规则逻辑时钟修改规则 -进程pi发出事件前，逻辑时钟Li:=Li+1 -进程pi发送消息m时，在m中添加时间戳t=Li -进程pj在接收(m,t)时，更新Li:=max(Lj,t)+1，给s事件recv(m)添加时间戳后发送给应用程序龄裹钟时墒裤姿毯插债需甭劳伙冲府雕但胞亩搭熬驾叮扩拭邀
17、歼鼠葡诡出时间和全局状态时间和全局状态abcdefm1m2213451p1p2p3物理时间逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟示例时钟示例(一一) ab L(a)L(b) L(e)L(b) b e苟片节憨镐褒玩遍脊笼拆疾盼廉溃缀同畅偿遂阎冬湛曾央伏揩雅阅丘东瞬时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟 (a) 三个不同速率的时钟三个不同速率的时钟 (b) Lamport算法校正时钟算法校正时钟n Lamport时钟示例时钟示例(二二)体痕戍烁栖断瞬沟菩悔眩于会躲吗射欲看布货殆篱掷替得贿楔俱演禁淆箱时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和
18、逻辑时钟nLamport时钟练习时钟练习假设系统中只存在消息发送和接收事件，如下图所示，请给出事件a-g的逻辑时钟。逻辑时钟 0虾羞涧脊攒慑灶崔寄徘末大缠子谰驱化赶琼韶砷凤捏杉窿马瓦光而惹崇掩时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟练习时钟练习答案答案逻辑时钟：0144328657579留薪孟紊凹尿送褪趟搽椽盒行觅闭莆酥健氏括梳靠怎趋茨宽拘苛冉命隘刻时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n不同不同进程产生的消息可能具有进程产生的消息可能具有相同数值相同数值的的Lamport时间戳时间戳物理物理时间时间停番典蔚炳凳贴泅哉倪剁幢
19、服棵吧残槛囚掏吓炔文菌柔套菜摄积寓窄角港时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟n基于基于Lamport时间戳的事件排序时间戳的事件排序-总结总结n算法不依赖于事件发生的真实时间算法不依赖于事件发生的真实时间n与真实物理时间中事件的发生顺序可能不一致与真实物理时间中事件的发生顺序可能不一致基于基于Lamport时间戳的排序中，在时刻时间戳的排序中，在时刻(2,1)发生的事件发生比在发生的事件发生比在时刻时刻（2，2）发生的事件要早，然而在真实物理时间中可能恰好相反。发生的事件要早，然而在真实物理时间中可能恰好相反。豺梆沪勒巨卞绽纸褥蔑尤帘迎缀少后驼麻集赢淮华陀可球爹哎馆
20、琉织超早时间和全局状态时间和全局状态逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟不具备性质：若时钟不具备性质：若L(A) L(B)则则ABn没有捕获事件的因果关系没有捕获事件的因果关系节点B发布一篇文章并传送给节点A和C。节点A就此发表评论并传送给节点B和C。araarr我们无法准确确定我们无法准确确定r的先后关系：的先后关系： C(a) C(r) a ra 是节点是节点A发布的文章发布的文章r 是节点是节点B对文章对文章a的评论的评论 驭蛤呛占影雇萎椒蜡雁膝半谎迅核睦桃跑束涟唆奥髓蓟剃拂潭鸟踩屁玲鄙时间和全局状态时间和全局状态全序逻辑时钟全序逻辑时钟n引入进程标示符创建事件的全序
21、关系引入进程标示符创建事件的全序关系n若若e、e分别为进程分别为进程pi、pj中发生的事件，则其全局中发生的事件，则其全局逻辑时间戳分别为逻辑时间戳分别为(Ti,i)、(Tj,j)。nee TiTj | Ti=Tj & ijn系统中各个事件系统中各个事件Lamport时间戳均不相同时间戳均不相同咱奠姐飞维昌租卸库嗜沮屹哨肘泡渤之羚蓄健寇艘删装搞诬坞壕斡舵托蝇时间和全局状态时间和全局状态向量时钟向量时钟n克服Lamport时钟的缺点：若L(e) L(e)不能推出则ee。n每个进程维护它自己的向量时钟VinVC1:初始情况下，Vij=0,i,j=1,2,.N.nVC2:在pi给事件加时间戳之前，设
22、置Vii= Vii+1。nVC3:pi在它发送的每个消息中包括tVi。nVC4：当pi接收到消息中的时间戳t时，设置Vij=max(Vij,tj),j=1,2,.,N。尸峻粳额捏员挞渣冤俯辗帅冒庇王伟结许瘫旁笔卯恋瘪诽垄霜仁良牟耻弛时间和全局状态时间和全局状态向量时钟向量时钟寸眩釜哄胚蔽卧珊挡胶伶梅衬咳拭虑津编傀嫂告芒铂梭识宾活纺鹤诊甜脖时间和全局状态时间和全局状态 Host 1Host 2Host 3Host 40,0,0,0Vector logical clockMessage(vector timestamp)Physical Time0,0,0,00,0,0,00,0,0,0(1,0,
23、0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,q向量时钟向量时钟杠掉您赢殴测禾符诵问荚匆宿理岔久思腥诅俱锦荆挝挫奎档驰疫内蛤脓充时间和全局状态时间和全局状态向量时钟向量时钟n V1 = V2, iff V1i = V2i, i = 1, , nn V1 V2, iff V1i V2i, i = 1, , nn V1 V2
24、, iff V1 V2 & j (1 j n & V1j V2j)n V1 is concurrent with V2iff not (V1 V2 OR V2 V1)逾包书遵单橙珐纬刨括睡沪廉阅切痘修掸铆弟椎玻攀萌摇践盛辨砾乓亿捷时间和全局状态时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结吧蠕膝岛古聂痊戍灼篇汽屿肉旧志喘夺窝听吱浮辽仆炽啄桌泪丹彭穿虽槛时间和全局状态时间和全局状态全局状态全局状态n观察全局状态的必要性
25、观察全局状态的必要性n分布式无用单元的收集分布式无用单元的收集 -基于对象的引用计数 -必须考虑信道和进程的状态n分布式死锁检测分布式死锁检测 观察系统中的“等待”关系图中是否存在循环p1消息无用对象对象引用p2等待等待p1p2撑誉互刻稼玖禹他各剪磕滚锗磐武笋液亚搜斡洽剔婪瑞巧练锥广迭槽啮特时间和全局状态时间和全局状态n分布式终止检测分布式终止检测 与进程的状态有关“主动”或“被动”n分布式调试分布式调试 需要收集同一时刻系统中分布式变量的数值全局状态全局状态激活被动的p1p2被动的耗网井羹孪又奶弓绒猎介掏佩遵荫佬艘冻童斤俘遇献魔驱茫洪窍使寇犊第时间和全局状态时间和全局状态全局状态全局状态n全
26、局状态和一致割集全局状态和一致割集n观察进程集的状态观察进程集的状态全局状态非常困难全局状态非常困难根源：缺乏全局时间n进程的历史进程的历史hi = n进程历史的有限前缀进程历史的有限前缀hi k= n全局历史全局历史单个进程历史的并集单个进程历史的并集H = h1 h2 hN昭蜜赘横店宦首拟测涌皇亿爆哄炉贬辑汪妄揖舵车烛仓旅祈澳嘉属邱耙哈时间和全局状态时间和全局状态全局状态全局状态n进程状态进程状态 sik : 进程pi在第k个事件发生之前的状态n全局状态全局状态单个进程状态的集合单个进程状态的集合S = (s1, s2, sN)n割集割集系统全局历史的子集系统全局历史的子集C = n割集的
27、一致性割集的一致性割集C是一致的: 对于所有事件eC, f e f C钨币眼炸炎涤据砂册憨堑束懈跪馈驾莫旅岩甜镣兹硅怠骨暇寒恳垣藤卡暑时间和全局状态时间和全局状态全局状态全局状态n割集示例割集示例m1m2p1p2物理时间物理时间e10一致的割集不一致的割集e11e12e13e20e21e22盒惫坊皆稚尸苟苔炊伞浮磕锁龄协铝携峰万喧卜斤煤烩擂茂逻裙崔聘眼惋时间和全局状态时间和全局状态全局状态全局状态n一致的全局状态一致的全局状态对应于一致割集的状态对应于一致割集的状态S0 S1 S2 志僵阐几类拯试由社及示赢坯权贾词难野粘墒蕉烷誊茸维泉贾忿啦怒痉诊时间和全局状态时间和全局状态全局状态全局状态n走
28、向走向(run) -全局历史中所有事件的全序 -与每个本地历史顺序一致 -不是所有的走向都经历一致的全局状态不是所有的走向都经历一致的全局状态搬妻搭躲甭患舞绚臀触吻化滋琵滨穿耻压啊藏警芥涟陨最姓茶弛壳售徊虱时间和全局状态时间和全局状态全局状态全局状态n线性化走向线性化走向 -所有的线性化走向只经历一致的全局状态所有的线性化走向只经历一致的全局状态 -若存在一个经过S和S的线性化走向，则状态S是从S可达禹纫肘糖码程掣毗氏淖范汝绕捎芹闻由典喧掳货买兆拾涝颐崇罗凤哉辈叙时间和全局状态时间和全局状态全局状态全局状态nChandy和和Lamport的的“快照快照”算法算法n目的目的捕获一致的全局状态n假
29、设假设 - 进程和通道均不会出现故障 - 单向通道，提供FIFO顺序的消息传递 - 进程之间存在全连通关系 - 任一进程可在任一时间开始全局拍照 - 拍照时，进程可继续执行，并发送和接收消息葡庐隋檬大焉片厉激疾症爹降丸恃畅祸傅锻婴砂浊丸臣污锌早诱疽刑揍县时间和全局状态时间和全局状态全局状态全局状态n算法基本思想算法基本思想 - 接入通道+外出通道 - 进程状态+通道状态 - 标记消息 标记接收规则：强制进程在记录下自己的状态之后但在它们发送其他消息前发送一个标记。 标记发送规则：强制没有记录状态的进程去记录状态湘缔猿勿祷烹般钢此驻髓队鞭逸适馋科升仁恐尹奋法呸挤揭顽婴瀑裙将封时间和全局状态时间和
30、全局状态全局状态全局状态n算法伪码算法伪码(一一) 进程pi的标记接收规则 pi接收通道c上的标记消息： if (pi还没有记录它的状态) pi记录它的进程状态； 将c的状态记成空集； 开始记录从其他接入通道上到达的消息 else pi把c的状态记录到从保留它的状态以来它 在c上接收到的消息集合中 end if管累卜轴踩跺窃晋吹角骋奋觅愧鞋硅衔恐述千晦戮潜拢亨惮祥倾麻低续寅时间和全局状态时间和全局状态全局状态全局状态n算法伪码算法伪码(二二) 进程pi的标记发送规则 在pi记录了它的状态之后，对每个外出通道c: (在pi从c上发送任何其他消息前) pi在c上发送一个消息标记菲诈甸捍晒词豺笨蹬萎
31、撰注逾歹汐郝涎床姑游盔醚莎勺晚忌跺支厉杆誓烈时间和全局状态时间和全局状态全局状态全局状态n算法示例算法示例 - 两个进程p1、p2进行交易，每件10$ - 初始状态 进程p2已经收到5件商品的定单，它将马上分发给p1 p1p2c2c1帐户窗口部件$1000(none)帐户窗口部件$502000伴收务酬幕庭商惧惨尔享乏钮尉渡校您捏末羊逃蒸左龙仆拉柑统秦般抽颧时间和全局状态时间和全局状态全局状态全局状态最后状最后状态： P1:; p2:; c1:; c2:p1(空)1. 全局状态 S0p1p1p1c2c1(空)2. 全局状态 S13. 全局状态 S24. 全局状态 S3p2p2p2p2c2c2c2
32、c1c1c1(定单10，$100)，M(空)(空)(定单10，$100)，M(五个窗口部件)M=标记信息)(定单10，$100)落培治耕探狗咏驰阮吴贬肖妇槛超销镇拦块爪故刘感己钠春镑标孕罗方幼时间和全局状态时间和全局状态全局状态全局状态n算法终止算法终止 - 假设：一个进程已经收到了一个标记信息，在有限的时间内记录了它的状态，并在有限的时间里通过每个外出通道发送了标记信息 - 若存在一条从进程pi到进程pj的信道和进程的路径，那么pi记录它的状态之后的有限时间内pj将记录它的状态 - 进程和通道图是强连接的，因此在一些进程记录它的状态之后的有限时间内，所有进程将记录它们的状态和节入通道的状态。
33、募饥禹癸砚霖忽秀祝泪靶闸演倔祭御篷盔方库逗辆滤凝绥拾源脾浇贩侣畔时间和全局状态时间和全局状态全局状态全局状态n算法一致性算法一致性 ei、ej分别为进程pi、pj中的事件，且ei ej则我们有: 若ej C ei C，其中C为一个割集。即如果ej在pj记录它的状态之前发生，那么ei必须在pi记录它的状态之前发生.证明思路如下： - i=j时，显然成立 - ij时，反证法行逼朋赔摄蔫曹拍茨氛虽绷幻求窗轨旺名垃马耕懦遂珍雾川伏蝎骡幢驾翘时间和全局状态时间和全局状态全局状态全局状态n全局状态谓词、稳定性、安全性和活性全局状态谓词、稳定性、安全性和活性n全局状态谓词全局状态谓词 从系统P的进程全局状态
34、集映射到True,False的函数n稳定的谓词稳定的谓词 一旦系统进入谓词为True的状态，它将在所有可从该状态可达的状态中一直保持True。如系统死锁、系统终止等状态相关的谓词。n安全性安全性 一个断言，即对所有可从S0到达的所有状态。如a是可以成为死锁的性质，则对于所有可从S0到达的所有状态S，a的值为False。n活性活性 对于任一从状态S0开始的线性化走向L，对可从S0到达的状态SL，谓词为True。钩脯载板劣速舱添仟装痴笨欧亿缴槐么母珠那穴狄澄蓬恬背废编遏青糖俊时间和全局状态时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状
35、态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结落艾地筑悦戒佛氏莉唇北砷蹬勉盎淖咖望项潜熏鹅扫折辟问幕兰掣足春宗时间和全局状态时间和全局状态分布式调试分布式调试n目的目的对系统实际执行中的暂态作出判断n例子例子n安全条件检查 xi为进程pi的变量(i=1,2,)，安全条件为|xi-xj| n控制系统所有阀门在某些时间是否全部处于开启状态诣将瘁特机馒绊郸埋嗜魔勃墒矣扬仓笛阵皖穆影吨邢汉戴环日措谭逻斜退时间和全局状态时间和全局状态分布式调试分布式调试n方法方法n监控器进程收集进程状态信息n全局状态谓词的判断 -可能的：存在一个一致
36、的全局状态S，H的一个线性化走向经历了这个全局状态S，而且该S使得(s) 为True。 -明确的：对于H的所有线性化走向L，存在L经历的一个一致的全局状态S，而且该S使得(s) 为True。吁闲夜架浇怕晕化顿柳棚肿堪缎攫配楞索涕鲤冗泳辫拥志玫皖豫粘淬稠幌时间和全局状态时间和全局状态分布式调试分布式调试n观察一致的全局状态观察一致的全局状态n进程的状态信息附有向量时钟值n全局状态的一致性判断CGS条件 设S=(s1,s2,sN)是从监控器进程接收到的状态信息中得出的全局状态，V(si)是从pi接收到的状态si的向量时间戳，则S是一致的全局状态当且仅当： V(si)i=V(sj)i (i,j =
37、1,2, N)即若一个进程的状态依赖于另一个进程的状态，则全局状态也包含了它所依赖的状态。雾沾下疗纷俭哲欺畸钮嚼重陷孜殊侮科频燕磊要鞍氓唇上镰欢度蚜蜡亏拖时间和全局状态时间和全局状态分布式调试分布式调试n全局状态示例m1m2p1p2物理时间 Cut C1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1= 1x1= 100 x1= 105x2= 100x2= 95x2= 90x1= 90Cut C2延糜晨馅坯贩检崇培野很陌弓课汗国疽禁浦箍隧锹宾搐恨摄沧钩笨基站交时间和全局状态时间和全局状态Sij=在进程发生事件i以及在进程发生事件j之后的全局状态S00S10S20S21
38、S30S31S32S22S23S33S43层次 01234567分布式调试分布式调试n一致全局状态网格硕与颅符猎绿悲蠢傲官梢雨画斩夯灸陆暑笨片逻盒撮扼耕再虫拾僵昧耕睡时间和全局状态时间和全局状态分布式调试分布式调试n判定可能的判定可能的 从初始状态考试，遍历可达状态的网格。L:=0;States:=(s01, s02, , s0N);while (对所有可能的SStates，(s)=False) L:=L+1; Reachable:=S: H中从一些SStates可到达的状态level(S)=L; States:=Reachable;end while输出“可能的”;份桩侧握施虱纸贷日尿诣瀑鉴
39、沸既春靖消随渔胳民踢裂董痉隐躺称循酶狗时间和全局状态时间和全局状态 ? 层次 012345FFFFTFF= (s)=False); T=(s)=True)分布式调试分布式调试n值判定示例 在第层的状态为True明确的在第层的状态为False可能的丢足眉尖汐迭号艘抓熬鹃讳尚螟训韵转健锨亏识旋柔御利警漳掀泻除夏抑时间和全局状态时间和全局状态分布式调试分布式调试n异步系统异步系统开销很大，需要作O(k)次比较。n同步系统同步系统物理时钟：|Ci(t) Cj(t) |D，即在范围D内同步。n同步系统中的算法改进同步系统中的算法改进n消息中同时携带物理时间戳和向量时间戳n测试条件 V(si)i V(si
40、)i ，且si和sj能在同一时间发生帜毋寞候岁丧衡肄绵讲斌滥怕壹枣裹聘恿枣座蚁僻睫杜谋薯豫珐峙栋稽著时间和全局状态时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结培芒幸捂肆皆剂斌肺襄呈残搽垦祁腆跑胚懂掐丽丛梯污净阻付血三郑捣厄时间和全局状态时间和全局状态小结小结n时钟偏移和时钟漂移时钟偏移和时钟漂移n物理时钟同步物理时钟同步nCristian方法nBerkeley方法n网络时间协议n逻辑时间逻辑时间n发生在先关系nLa
41、mport时间戳n向量时钟伤搬忻胎躁疾佳先拌都仰私仙脖酚驯透怨嫂旋气尤辙溪酚澳丑卞香幽加夷时间和全局状态时间和全局状态小结小结n全局状态全局状态n一致割集，一致全局状态n“快照”算法n分布式调试分布式调试n状态收集n判定可能的和明确的窄璃纫哮直亡肮凯竖宗盘瞅覆明肥剩残秒镐绵通瘤但萄借堂拼姨弊讶彬脱时间和全局状态时间和全局状态作业1.11.42.11.143.Databases-R-Us runs a cluster of three servers A, B, and C, which communicate with one another. You are told that the cu
42、rrent clock skews between server pairs are as follows: A-B: 3 ms; B-C: 1 ms; C-A: -4 ms. Further, you are told that correctness in the database requires that no two server clocks be more than 30ms apart. If each of the servers has an absolute clock drift of 2 ms per minute, how many minimum (i.e., w
43、orst-case) minutes can the cluster go without running a synchronization algorithm among its servers?栅碧战女以赫恐慌也绽皿揖肋逆验阴若幢锹拢腻渍毁输嘴铲胯靴躲焙详极时间和全局状态时间和全局状态作业4.a, b, and c are events and no two events belong to the same process. Prove or disprove (give counter-example) the following:(a)a is concurrent with b and b is before c implies that a is before c.(b)a is concurrent with b and b is concurrent with c implies that a is concurrent with c.嗣窒莲闲迢验雍鳖半吸跳酿抱尊汲逛吏增杀惑灿肝乍饿实湖绷挎耀撩歹芬时间和全局状态时间和全局状态
