《时间和全局状态讲义》由会员分享，可在线阅读，更多相关《时间和全局状态讲义（61页珍藏版）》请在金锄头文库上搜索。
1、第3第第3章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进程状程状态n同步物理同步物理时钟n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试n小小结简介介n如何计时？n如何同步时钟？n没有物理时钟能否确定事件的顺序？简介介n时间的重要性的重要性n需要精确度量审计电子商务n某些算法依赖于时钟同步数据一致性维护、maken计算全局状态事件排序n时间的复的复杂性性n节点具有独立的物理时钟n精确同步物理时钟非常困难n全局状全局状态的捕的捕获n依赖于逻辑时钟n逻辑时钟与物理时钟无必然联系时钟、事件和、事件和进程状程状态n时间分分类n天文学天文学时间 -太阳日：两次连续的太阳中天之间的
2、时间间隔 -太阳秒：1/86400个太阳日n国国际原子原子时间(TAI) -基于铯原子跳跃周期 -秒：9 192 631 770次跳跃周期n通用通用协调时间(UTC) -基于原子时间 -采用润秒，与天文时间保持一致第第3章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进程状程状态n同步物理同步物理时钟n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试n小小结时钟、事件和、事件和进程状程状态n假假设n每个进程在单处理器上执行n处理器之间不共享内存n进程之间通过消息进行通信n进程状程状态n所有变量的值n相关的本地操作系统环境中的对象的值n事件事件n定义：一个通信动作或进程状态转换
3、动作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 phase offsetIEEE Transactions on Commnunications,Vol55,No.4,2007.4第第3章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进
4、程状程状态n同步物理同步物理时钟n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试n小小结同步物理同步物理时钟n外部同步外部同步n采用权威的外部时间源n时钟Ci在范围D内是准确的n内部同步内部同步n无外部权威时间源,系统内时钟同步n时钟Ci在范围D内是准确的n关系关系 若P在范围D内外部同步,则P在范围2D内内部同步同步物理同步物理时钟nCristian方法方法(适用于只有一台机器有适用于只有一台机器有WWV接收器接收器)n应用条件用条件-存在时间服务器，可与外部时间源同步 -消息往返时间与系统所要求的精度相比足够短n协议-进程p根据消息mr，mt计算消息往返时间Tround -根据服务
5、器在mt中放置的时间t设置时钟为：t+Tround/2mtp时间服务器Smr同步物理同步物理时钟nBerkeley算法（没有算法（没有WWV接收器）接收器）n主机主机周期周期轮询从属机从属机时间n主机通主机通过消息往返消息往返时间估算从属机的估算从属机的时间与Cristian方法类似n主机主机计算算容容错平均平均值n主机主机发送每个从属机的送每个从属机的调整量整量同步物理同步物理时钟n网网络时间协议(NTP)n设计目目标 -可外部同步 使得跨Internet的用户能精确地与UTC同步 -高可靠性 可处理连接丢失，采用冗余服务器、路径等 -扩展性好 大量用户可经常同步，以抵消漂移率的影响 -安全
6、性强 防止恶意或偶然的干扰同步物理同步物理时钟n协议结构构 -层次结构 -主服务器直接与外部UTC同步 -同步子网可重新配置123233 同步子网结构示例第第3章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进程状程状态n物理物理时钟同步同步n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试n小小结逻辑时间和和逻辑时钟n逻辑时间的引入的引入n分布式系分布式系统中的物理中的物理时钟无法完美同步无法完美同步 -消息传输延时的不确定性n事件排序是众多分布式算法的基石事件排序是众多分布式算法的基石 -互斥算法 -死锁检测算法n缺乏全局缺乏全局时钟 -后发生的事件有可能赋予较早的时间标
7、记逻辑时间和和逻辑时钟n逻辑时钟n众多众多应用只要求所有用只要求所有节点具有点具有相同相同时间，该时间不一不一定与定与实际时间相同相同nLamport(1978)指出：不指出：不进行交互的两个行交互的两个进程之程之间不需不需要要时钟同步同步对于不需要交互的两个进程而言，即使没有时钟同步，也无法察觉，更不会产生问题。n所有的所有的进程需要在程需要在时间的的发生生顺序序上上达成一致达成一致 如make程序逻辑时间和和逻辑时钟n事件排序事件排序n“系系统i中的事件中的事件a发生在系生在系统j中的事件中的事件b之前之前”是不是不准确的准确的 -事件发生和观察之间存在时延 -不同系统中的时钟存在偏差n时
8、间戳戳(Lamport 1978) -用于分布式系统中的事件排序 -与物理时钟无关 -实用高效，应用广泛逻辑时间和和逻辑时钟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与
9、ef均成立 -事件b和e无法比较，即b|ep1p2p3abcdefm1m2物理物理时间时间逻辑时间和和逻辑时钟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时钟示例示例(一一) a
10、b L(a)L(b) L(e)L(b) b e逻辑时间和和逻辑时钟 (a) 三个不同速率的时钟三个不同速率的时钟 (b) Lamport算法校正时钟算法校正时钟n Lamport时钟示例时钟示例(二二)逻辑时间和和逻辑时钟nLamport时钟练习假设系统中只存在消息发送和接收事件，如下图所示，请给出事件a-g的逻辑时钟。逻辑时钟 0逻辑时间和和逻辑时钟nLamport时钟练习答案答案逻辑时钟：0144328657579逻辑时间和和逻辑时钟n不同不同进程程产生的消息可能具有生的消息可能具有相同数相同数值的的Lamport时间戳戳物理物理时间时间逻辑时间和和逻辑时钟n基于基于Lamport时间戳的
11、事件排序戳的事件排序-总结n算法不依算法不依赖于事件于事件发生的真生的真实时间n与真与真实物理物理时间中事件的中事件的发生生顺序可能不一致序可能不一致基于基于Lamport时间戳的排序中，在戳的排序中，在时刻刻(2,1)发生的事件生的事件发生比在生比在时刻刻（2，2）发生的事件要早，然而在真生的事件要早，然而在真实物理物理时间中可能恰好相反。中可能恰好相反。逻辑时间和和逻辑时钟nLamport时钟不具不具备性性质：若：若L(A) L(B)则ABn没有捕没有捕获事件的因果关系事件的因果关系节点B发布一篇文章并传送给节点A和C。节点A就此发表评论并传送给节点B和C。araarr我我们无法准确确定无
12、法准确确定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时间戳均不相同戳均不相同向量向量时钟n克服Lamport时钟的缺点：若L(e) L(e)不能推出则ee。n每个进程维护它自己的向量时钟VinVC1:初始情况下，Vij=
13、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,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,
14、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章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进程状程状态n同步物理同步物理时钟n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试n小小结全局状全局状态n观察全局状察全局状态的必要性的必要性n分布式无用分布式无用单元的收集元的收集 -基于对象的引用计数 -必须考虑信道和进程的状态n分布式死分布式死锁检测 观察系统中的“等待”关系图中是否存在循环p1消息无用对
15、象对象引用p2等待等待p1p2n分布式分布式终止止检测 与进程的状态有关“主动”或“被动”n分布式分布式调试 需要收集同一时刻系统中分布式变量的数值全局状全局状态激活被动的p1p2被动的全局状全局状态n全局状全局状态和一致割集和一致割集n观察察进程集的状程集的状态全局状全局状态非常困非常困难根源：缺乏全局时间n进程的程的历史史hi = n进程程历史的有限前史的有限前缀hi k= n全局全局历史史单个个进程程历史的并集史的并集H = h1 h2 hN全局状全局状态n进程状程状态 sik : 进程pi在第k个事件发生之前的状态n全局状全局状态单个个进程状程状态的集合的集合S = (s1, s2,
16、sN)n割集割集系系统全局全局历史的子集史的子集C = n割集的一致性割集的一致性割集C是一致的: 对于所有事件eC, f e f C全局状全局状态n割集示例割集示例m1m2p1p2物理时间物理时间e10一致的割集不一致的割集e11e12e13e20e21e22全局状全局状态n一致的全局状一致的全局状态对应于一致割集的状于一致割集的状态S0 S1 S2 n走向走向(run) -全局历史中所有事件的全序 -与每个本地历史顺序一致 -不是所有的走向都不是所有的走向都经历一致的全局状一致的全局状态n线性化走向性化走向 -所有的所有的线性化走向只性化走向只经历一致的全局状一致的全局状态 -若存在一个经
17、过S和S的线性化走向，则状态S是从S可达全局状全局状态nChandy和和Lamport的的“快照快照”算法算法n目的目的捕获一致的全局状态n假假设 - 进程和通道均不会出现故障 - 单向通道，提供FIFO顺序的消息传递 - 进程之间存在全连通关系 - 任一进程可在任一时间开始全局拍照 - 拍照时，进程可继续执行，并发送和接收消息全局状全局状态n算法基本思想算法基本思想 - 接入通道+外出通道 - 进程状态+通道状态 - 标记消息 标记接收规则：强制进程在记录下自己的状态之后但在它们发送其他消息前发送一个标记。 标记发送规则：强制没有记录状态的进程去记录状态全局状全局状态n算法算法伪码(一一)
18、进程pi的标记接收规则 pi接收通道c上的标记消息： if (pi还没有记录它的状态) pi记录它的进程状态； 将c的状态记成空集； 开始记录从其他接入通道上到达的消息 else pi把c的状态记录到从保留它的状态以来它 在c上接收到的消息集合中 end if全局状全局状态n算法算法伪码(二二) 进程pi的标记发送规则 在pi记录了它的状态之后，对每个外出通道c: (在pi从c上发送任何其他消息前) pi在c上发送一个消息标记全局状全局状态n算法示例算法示例 - 两个进程p1、p2进行交易，每件10$ - 初始状态 进程p2已经收到5件商品的定单，它将马上分发给p1 p1p2c2c1帐户窗口部
19、件$1000(none)帐户窗口部件$502000全局状全局状态最后状最后状态： P1:; p2:; c1:; c2:p1(空)1. 全局状态 S0p1p1p1c2c1(空)2. 全局状态 S13. 全局状态 S24. 全局状态 S3p2p2p2p2c2c2c2c1c1c1(定单10，$100)，M(空)(空)(定单10，$100)，M(五个窗口部件)M=标记信息)(定单10，$100)全局状全局状态n算法算法终止止 - 假设：一个进程已经收到了一个标记信息，在有限的时间内记录了它的状态，并在有限的时间里通过每个外出通道发送了标记信息 - 若存在一条从进程pi到进程pj的信道和进程的路径，那么
20、pi记录它的状态之后的有限时间内pj将记录它的状态 - 进程和通道图是强连接的，因此在一些进程记录它的状态之后的有限时间内，所有进程将记录它们的状态和节入通道的状态。全局状全局状态n算法一致性算法一致性 ei、ej分别为进程pi、pj中的事件，且ei ej则我们有: 若ej C ei C，其中C为一个割集。即如果ej在pj记录它的状态之前发生，那么ei必须在pi记录它的状态之前发生.证明思路如下： - i=j时，显然成立 - ij时，反证法第第3章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进程状程状态n物理物理时钟同步同步n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试
21、n小小结分布式分布式调试n目的目的对系统实际执行中的暂态作出判断n例子例子n安全条件检查 xi为进程pi的变量(i=1,2,)，安全条件为|xi-xj| n控制系统所有阀门在某些时间是否全部处于开启状态分布式分布式调试n方法方法n监控器进程收集进程状态信息n全局状态谓词的判断 -可能的：存在一个一致的全局状态S，H的一个线性化走向经历了这个全局状态S，而且该S使得(s) 为True。 -明确的：对于H的所有线性化走向L，存在L经历的一个一致的全局状态S，而且该S使得(s) 为True。分布式分布式调试n观察一致的全局状察一致的全局状态n进程的状态信息附有向量时钟值n全局状态的一致性判断CGS条
22、件 设S=(s1,s2,sN)是从监控器进程接收到的状态信息中得出的全局状态，V(si)是从pi接收到的状态si的向量时间戳，则S是一致的全局状态当且仅当： V(si)i=V(sj)i (i,j = 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 C2Sij=在进程发生事件i以及在进程发生事件j之后的全局状态S00S10
23、S20S21S30S31S32S22S23S33S43层次 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输出“可能的”; ? 层次 012345FFFFTFF= (s)=False); T=(s)=True)分布式分布式调试n值判定示
24、例 在第层的状态为True明确的在第层的状态为False可能的分布式分布式调试n异步系异步系统开销很大，需要作O(k)次比较。n同步系同步系统物理时钟：|Ci(t) Cj(t) |D，即在范围D内同步。n同步系同步系统中的算法改中的算法改进n消息中同时携带物理时间戳和向量时间戳n测试条件 V(si)i V(si)i ，且si和sj能在同一时间发生第第3章章 时间和全局状和全局状态n简介介 n时钟、事件和、事件和进程状程状态n物理物理时钟同步同步n逻辑时间和和逻辑时钟n全局状全局状态n分布式分布式调试n小小结小小结n时钟偏移和偏移和时钟漂移漂移n物理物理时钟同步同步nCristian方法nBer
25、keley方法n网络时间协议n逻辑时间n发生在先关系nLamport时间戳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 current clock skews between server pairs are as follows: A-B: 3 ms; B
26、-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., worst-case) minutes can the cluster go without running a synchroniza
27、tion 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.
