-时间和全局状态.pptx

《-时间和全局状态.pptx》由会员分享，可在线阅读，更多相关《-时间和全局状态.pptx（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 时间和全局状态第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结简介简介n如何计时？n如何同步时钟？n没有物理时钟能否确定事件的顺序？简介简介n时间的重要性时间的重要性n需要精确度量审计电子商务n某些算法依赖于时钟同步数据一致性维护、maken计算全局状态事件排序n时间的复杂性时间的复杂性n节点具有独立的物理时钟n精确同步物理时钟非常困难n全局状态的捕获全局状态的捕获n依赖于逻辑时钟n逻辑时钟与物理时钟无必然联系时钟、事件和进

2、程状态时钟、事件和进程状态n时间分类时间分类n天文学时间天文学时间 -太阳日：两次连续的太阳中天之间的时间间隔 -太阳秒：1/86400个太阳日n国际原子时间国际原子时间(TAI)-基于铯原子跳跃周期 -秒：9 192 631 770次跳跃周期n通用协调时间通用协调时间(UTC)-基于原子时间 -采用润秒，与天文时间保持一致第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结时钟、事件和进程状态时钟、事件和进程状态n假设假设n每个进程在

3、单处理器上执行n处理器之间不共享内存n进程之间通过消息进行通信n进程状态进程状态n所有变量的值n相关的本地操作系统环境中的对象的值n事件事件n定义：一个通信动作或进程状态转换动作n进程历史：时钟、事件和进程状态时钟、事件和进程状态n计算机时钟计算机时钟n晶体具有固定震荡频率n硬件时钟：n软件时钟：n时钟漂移时钟漂移n频率不同n时钟频率随温度变化而有所差别n时钟偏移不可避免时钟偏移不可避免nIn fact,the effect of clock skew is the main reason why clock offsets keep drifting away.Novel clock pha

4、se offsetIEEE Transactions on Commnunications,Vol55,No.4,2007.4第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结同步物理时钟同步物理时钟n外部同步外部同步n采用权威的外部时间源n时钟Ci在范围D内是准确的n内部同步内部同步n无外部权威时间源,系统内时钟同步n时钟Ci在范围D内是准确的n关系关系 若P在范围D内外部同步,则P在范围2D内内部同步同步物理时钟同步物理时钟nCr

5、istian方法方法(适用于只有一台机器有适用于只有一台机器有WWV接收器接收器)n应用条件应用条件-存在时间服务器，可与外部时间源同步 -消息往返时间与系统所要求的精度相比足够短n协议协议-进程p根据消息mr，mt计算消息往返时间Tround -根据服务器在mt中放置的时间t设置时钟为：t+Tround/2mtp时间服务器Smr同步物理时钟同步物理时钟nBerkeley算法（没有算法（没有WWV接收器）接收器）n主机主机周期轮询周期轮询从属机时间从属机时间n主机通过消息往返时间估算从属机的时间主机通过消息往返时间估算从属机的时间与Cristian方法类似n主机计算主机计算容错平均值容错平均值

6、n主机发送每个从属机的主机发送每个从属机的调整量调整量同步物理时钟同步物理时钟n网络时间协议网络时间协议(NTP)n设计目标设计目标 -可外部同步 使得跨Internet的用户能精确地与UTC同步 -高可靠性 可处理连接丢失，采用冗余服务器、路径等 -扩展性好 大量用户可经常同步，以抵消漂移率的影响 -安全性强 防止恶意或偶然的干扰同步物理时钟同步物理时钟n协议结构协议结构 -层次结构 -主服务器直接与外部UTC同步 -同步子网可重新配置123233 同步子网结构示例第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻

7、辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结逻辑时间和逻辑时钟逻辑时间和逻辑时钟n逻辑时间的引入逻辑时间的引入n分布式系统中的物理时钟无法完美同步分布式系统中的物理时钟无法完美同步 -消息传输延时的不确定性n事件排序是众多分布式算法的基石事件排序是众多分布式算法的基石 -互斥算法 -死锁检测算法n缺乏全局时钟缺乏全局时钟 -后发生的事件有可能赋予较早的时间标记逻辑时间和逻辑时钟逻辑时间和逻辑时钟n逻辑时钟逻辑时钟n众多应用只要求所有节点具有众多应用只要求所有节点具有相同时间相同时间，该时间，该时间不一不一定与实际时间相同定与实际时间相同nLamport(

8、1978)指出：不进行交互的两个进程之间不需指出：不进行交互的两个进程之间不需要时钟同步要时钟同步对于不需要交互的两个进程而言，即使没有时钟同步，也无法察觉，更不会产生问题。n所有的进程需要在时间的所有的进程需要在时间的发生顺序发生顺序上上达成一致达成一致 如make程序逻辑时间和逻辑时钟逻辑时间和逻辑时钟n事件排序事件排序n“系统系统i中的事件中的事件a发生在系统发生在系统j中的事件中的事件b之前之前”是不是不准确的准确的 -事件发生和观察之间存在时延 -不同系统中的时钟存在偏差n时间戳时间戳(Lamport 1978)-用于分布式系统中的事件排序 -与物理时钟无关 -实用高效，应用广泛逻辑

9、时间和逻辑时钟逻辑时间和逻辑时钟n两个基本事实两个基本事实 -同一进程中的两个事件存在关系“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|ep1p2p3abcdefm1m2物理物理

10、时间时间逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟时钟n机制机制 -进程维护一个单调递增的软件计数器，充当逻辑时钟 -用逻辑时钟为事件添加时间戳 -按事件的时间戳大小为时间排序n逻辑时钟修改规则逻辑时钟修改规则 -进程pi发出事件前，逻辑时钟Li:=Li+1 -进程pi发送消息m时，在m中添加时间戳t=Li -进程pj在接收(m,t)时，更新Li:=max(Lj,t)+1，给s事件recv(m)添加时间戳后发送给应用程序abcdefm1m2213451p1p2p3物理时间逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟示例时钟示例(一一)ab L(a)L(b)L(e)L(

11、b)b e逻辑时间和逻辑时钟逻辑时间和逻辑时钟 (a)三个不同速率的时钟三个不同速率的时钟 (b)Lamport算法校正时钟算法校正时钟n Lamport时钟示例时钟示例(二二)逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟练习时钟练习假设系统中只存在消息发送和接收事件，如下图所示，请给出事件a-g的逻辑时钟。逻辑时钟 0逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟练习时钟练习答案答案逻辑时钟：0144328657579逻辑时间和逻辑时钟逻辑时间和逻辑时钟n不同不同进程产生的消息可能具有进程产生的消息可能具有相同数值相同数值的的Lamport时间戳时间戳物理物理时间时间逻

12、辑时间和逻辑时钟逻辑时间和逻辑时钟n基于基于Lamport时间戳的事件排序时间戳的事件排序-总结总结n算法不依赖于事件发生的真实时间算法不依赖于事件发生的真实时间n与真实物理时间中事件的发生顺序可能不一致与真实物理时间中事件的发生顺序可能不一致基于基于Lamport时间戳的排序中，在时刻时间戳的排序中，在时刻(2,1)发生的事件发生比在时发生的事件发生比在时刻刻（2，2）发生的事件要早，然而在真实物理时间中可能恰好相反。发生的事件要早，然而在真实物理时间中可能恰好相反。逻辑时间和逻辑时钟逻辑时间和逻辑时钟nLamport时钟不具备性质：若时钟不具备性质：若L(A)L(B)则则ABn没有捕获事件

13、的因果关系没有捕获事件的因果关系节点B发布一篇文章并传送给节点A和C。节点A就此发表评论并传送给节点B和C。araarr我们无法准确确定我们无法准确确定r的先后关系：的先后关系：C(a)C(r)a ra 是节点是节点A发布的文章发布的文章r 是节点是节点B对文章对文章a的评论的评论 全序逻辑时钟全序逻辑时钟n引入进程标示符创建事件的全序关系引入进程标示符创建事件的全序关系n若若e、e分别为进程分别为进程pi、pj中发生的事件，则其全局中发生的事件，则其全局逻辑时间戳分别为逻辑时间戳分别为(Ti,i)、(Tj,j)。nee TiTj|Ti=Tj&ijn系统中各个事件系统中各个事件Lamport时

14、间戳均不相同时间戳均不相同向量时钟向量时钟n克服Lamport时钟的缺点：若L(e)L(e)不能推出则ee。n每个进程维护它自己的向量时钟VinVC1:初始情况下，Vij=0,i,j=1,2,.N.nVC2:在pi给事件加时间戳之前，设置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

15、,0,0,00,0,0,00,0,0,0(1,0,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向量时钟向量时钟第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n同步物理时钟同步物理时钟n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结

16、小结全局状态全局状态n观察全局状态的必要性观察全局状态的必要性n分布式无用单元的收集分布式无用单元的收集 -基于对象的引用计数 -必须考虑信道和进程的状态n分布式死锁检测分布式死锁检测 观察系统中的“等待”关系图中是否存在循环p1消息无用对象对象引用p2等待等待p1p2n分布式终止检测分布式终止检测 与进程的状态有关“主动”或“被动”n分布式调试分布式调试 需要收集同一时刻系统中分布式变量的数值全局状态全局状态激活被动的p1p2被动的全局状态全局状态n全局状态和一致割集全局状态和一致割集n观察进程集的状态观察进程集的状态全局状态非常困难全局状态非常困难根源：缺乏全局时间n进程的历史进程的历史h

17、i=n进程历史的有限前缀进程历史的有限前缀hi k=n全局历史全局历史单个进程历史的并集单个进程历史的并集H=h1 h2 hN全局状态全局状态n进程状态进程状态 sik:进程pi在第k个事件发生之前的状态n全局状态全局状态单个进程状态的集合单个进程状态的集合S=(s1,s2,sN)n割集割集系统全局历史的子集系统全局历史的子集C=n割集的一致性割集的一致性割集C是一致的:对于所有事件eC,f e f C全局状态全局状态n割集示例割集示例m1m2p1p2物理时间物理时间e10一致的割集不一致的割集e11e12e13e20e21e22全局状态全局状态n一致的全局状态一致的全局状态对应于一致割集的状

18、态对应于一致割集的状态S0 S1 S2 n走向走向(run)-全局历史中所有事件的全序 -与每个本地历史顺序一致 -不是所有的走向都经历一致的全局状态不是所有的走向都经历一致的全局状态n线性化走向线性化走向 -所有的线性化走向只经历一致的全局状态所有的线性化走向只经历一致的全局状态 -若存在一个经过S和S的线性化走向，则状态S是从S可达全局状态全局状态nChandy和和Lamport的的“快照快照”算法算法n目的目的捕获一致的全局状态n假设假设 -进程和通道均不会出现故障 -单向通道，提供FIFO顺序的消息传递 -进程之间存在全连通关系 -任一进程可在任一时间开始全局拍照 -拍照时，进程可继续

19、执行，并发送和接收消息全局状态全局状态n算法基本思想算法基本思想 -接入通道+外出通道 -进程状态+通道状态 -标记消息 标记接收规则：强制进程在记录下自己的状态之后但在它们发送其他消息前发送一个标记。标记发送规则：强制没有记录状态的进程去记录状态全局状态全局状态n算法伪码算法伪码(一一)进程pi的标记接收规则 pi接收通道c上的标记消息：if(pi还没有记录它的状态)pi记录它的进程状态；将c的状态记成空集；开始记录从其他接入通道上到达的消息 else pi把c的状态记录到从保留它的状态以来它 在c上接收到的消息集合中 end if全局状态全局状态n算法伪码算法伪码(二二)进程pi的标记发送

20、规则 在pi记录了它的状态之后，对每个外出通道c:(在pi从c上发送任何其他消息前)pi在c上发送一个消息标记全局状态全局状态n算法示例算法示例 -两个进程p1、p2进行交易，每件10$-初始状态 进程p2已经收到5件商品的定单，它将马上分发给p1 p1p2c2c1帐户窗口部件$1000(none)帐户窗口部件$502000全局状态全局状态最后状态：最后状态：P1:;p2:;c1:;c2:p1(空)1.全局状态 S0p1p1p1c2c1(空)2.全局状态 S13.全局状态 S24.全局状态 S3p2p2p2p2c2c2c2c1c1c1(定单10，$100)，M(空)(空)(定单10，$100)

21、，M(五个窗口部件)M=标记信息)(定单10，$100)全局状态全局状态n算法终止算法终止 -假设：一个进程已经收到了一个标记信息，在有限的时间内记录了它的状态，并在有限的时间里通过每个外出通道发送了标记信息-若存在一条从进程pi到进程pj的信道和进程的路径，那么pi记录它的状态之后的有限时间内pj将记录它的状态-进程和通道图是强连接的，因此在一些进程记录它的状态之后的有限时间内，所有进程将记录它们的状态和节入通道的状态。全局状态全局状态n算法一致性算法一致性 ei、ej分别为进程pi、pj中的事件，且ei ej则我们有:若ej C ei C，其中C为一个割集。即如果ej在pj记录它的状态之前

22、发生，那么ei必须在pi记录它的状态之前发生.证明思路如下：-i=j时，显然成立 -ij时，反证法第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结分布式调试分布式调试n目的目的对系统实际执行中的暂态作出判断n例子例子n安全条件检查 xi为进程pi的变量(i=1,2,)，安全条件为|xi-xj|n控制系统所有阀门在某些时间是否全部处于开启状态分布式调试分布式调试n方法方法n监控器进程收集进程状态信息n全局状态谓词的判断 -可能的：存在

23、一个一致的全局状态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=1,2,N)即若一个进程的状态依赖于另一个进程的状态，则全局状态也包含了它所以来的状态。分布式调试

24、分布式调试n全局状态示例m1m2p1p2物理时间 Cut C1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1=1x1=100 x1=105x2=100 x2=95x2=90 x1=90Cut C2Sij=在进程发生事件i以及在进程发生事件j之后的全局状态S00S10S20S21S30S31S32S22S23S33S43层次 01234567分布式调试分布式调试n一致全局状态网格分布式调试分布式调试n判定可能的判定可能的 从初始状态考试，遍历可达状态的网格。L:=0;States:=(s01,s02,s0N);while(对所有可能的SStates，(s)=False

25、)L:=L+1;Reachable:=S:H中从一些SStates可到达的状态level(S)=L;States:=Reachable;end while输出“可能的”;?层次 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

26、)i，且si和sj能在同一时间发生第第3 3章章 时间和全局状态时间和全局状态n简介简介 n时钟、事件和进程状态时钟、事件和进程状态n物理时钟同步物理时钟同步n逻辑时间和逻辑时钟逻辑时间和逻辑时钟n全局状态全局状态n分布式调试分布式调试n小结小结小结小结n时钟偏移和时钟漂移时钟偏移和时钟漂移n物理时钟同步物理时钟同步nCristian方法nBerkeley方法n网络时间协议n逻辑时间逻辑时间n发生在先关系nLamport时间戳n向量时钟小结小结n全局状态全局状态n一致割集，一致全局状态n“快照”算法n分布式调试分布式调试n状态收集n判定可能的和明确的作业1.11.42.11.143.Datab

27、ases-R-Us runs a cluster of three servers A,B,and C,which communicate with one another.You are told that the current 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

28、apart.If each of the servers has an absolute clock drift of 2 ms per minute,how many minimum(i.e.,worst-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-e

29、xample)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.n9、静夜四无邻，荒居旧业贫。12月-2312月-23Monday,December 4,2023n10、雨中黄叶树，灯下白头人。21:32:0221:32:0221:3212/4/2023 9:32:02 PMn11、以我独沈久，愧君相

30、见频。12月-2321:32:0221:32Dec-2304-Dec-23n12、故人江海别，几度隔山川。21:32:0221:32:0221:32Monday,December 4,2023n13、乍见翻疑梦，相悲各问年。12月-2312月-2321:32:0221:32:02December 4,2023n14、他乡生白发，旧国见青山。04 十二月 20239:32:02 下午21:32:0212月-23n15、比不了得就不比，得不到的就不要。十二月 239:32 下午12月-2321:32December 4,2023n16、行动出成果，工作出财富。2023/12/4 21:32:022

31、1:32:0204 December 2023n17、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。9:32:02 下午9:32 下午21:32:0212月-23n9、没有失败，只有暂时停止成功！。12月-2312月-23Monday,December 4,2023n10、很多事情努力了未必有结果，但是不努力却什么改变也没有。21:32:0221:32:0221:3212/4/2023 9:32:02 PMn11、成功就是日复一日那一点点小小努力的积累。12月-2321:32:0221:32Dec-2304-Dec-23n12、世间成事，不求其绝对圆满，留一份不足，可得无限

32、完美。21:32:0221:32:0221:32Monday,December 4,2023n13、不知香积寺，数里入云峰。12月-2312月-2321:32:0221:32:02December 4,2023n14、意志坚强的人能把世界放在手中像泥块一样任意揉捏。04 十二月 20239:32:02 下午21:32:0212月-23n15、楚塞三湘接，荆门九派通。十二月 239:32 下午12月-2321:32December 4,2023n16、少年十五二十时，步行夺得胡马骑。2023/12/4 21:32:0221:32:0204 December 2023n17、空山新雨后，天气晚来秋

33、。9:32:02 下午9:32 下午21:32:0212月-23n9、杨柳散和风，青山澹吾虑。12月-2312月-23Monday,December 4,2023n10、阅读一切好书如同和过去最杰出的人谈话。21:32:0221:32:0221:3212/4/2023 9:32:02 PMn11、越是没有本领的就越加自命不凡。12月-2321:32:0221:32Dec-2304-Dec-23n12、越是无能的人，越喜欢挑剔别人的错儿。21:32:0221:32:0221:32Monday,December 4,2023n13、知人者智，自知者明。胜人者有力，自胜者强。12月-2312月-23

34、21:32:0221:32:02December 4,2023n14、意志坚强的人能把世界放在手中像泥块一样任意揉捏。04 十二月 20239:32:02 下午21:32:0212月-23n15、最具挑战性的挑战莫过于提升自我。十二月 239:32 下午12月-2321:32December 4,2023n16、业余生活要有意义，不要越轨。2023/12/4 21:32:0221:32:0204 December 2023n17、一个人即使已登上顶峰，也仍要自强不息。9:32:02 下午9:32 下午21:32:0212月-23MOMODA POWERPOINTLorem ipsum dolor sit amet,consectetur adipiscing elit.Fusce id urna blandit,eleifend nulla ac,fringilla purus.Nulla iaculis tempor felis ut cursus.感感 谢谢 您您 的的 下下 载载 观观 看看专家告诉