分布式系统 时钟同步ppt课件.pptx
同 步,寇迦南,1.时钟同步,引入 时钟同步,例子：UNIX中make程序的调用问题。,引入 时钟同步,例子：UNIX中make程序的调用问题Make程序的作用是什么？可以自动完成对源文件的编译。,引入 时钟同步,UNIX系统会把较大的程序分成多个源程序，当一个源文件发生变化时（比如被修改后），只需编译一个文件即可，不需要对所有的文件进行编译。,引入 时钟同步,这个过程如何进行？,引入 时钟同步,这个过程如何进行？当调用make程序时，make程序根据所有源文件和对应目标文件的修改时间来决定是否对某个源文件重新编译。,引入 时钟同步,例如：如果源文件input.c的修改时间为5155且对应目标文件input.o的修改时间为5151，那么，make程序知道input.c已被修改。input.c必须被重新编译。,input.o,input.c,5151,5155,t,引入 时钟同步,例如：如果源文件output.c的修改时间为5144且对应目标文件output.o的修改时间为5145，那么，不需要对output.c进行重新编译。,output.c,output.o,5144,5145,t,引入 时钟同步,make程序在考察完所有源文件和其对应目标文件的修改时间后决定哪些文件需要重新编译并调用编译器对其进行编译。,分布式系统 时钟同步,在分布式环境中，由于时间不同步会造成的程序不能正常运行。,分布式系统 时钟同步,在分布式环境中，由于时间不同步会造成的程序不能正常运行。为什么？,分布式系统 时钟同步,假定output.o的修改时间为5144，output.c被修改并赋予的时间为5143，原因是output.c所在机器上的时钟要比output.o所在机器上的时钟慢。,创建 output.o,5144,5145,t,进行编译的计算机,5146,5147,根据本地时钟的时间,创建 output.c,5142,5143,t,进行编译的计算机,5144,5145,根据本地时钟的时间,分布式系统 时钟同步,因此，make程序不调用编译器进行编译。结果，最终的可执行的二进制程序将包含由旧的源文件和新的源文件所产生的混合目标文件，导致该可执行程序无法运行而程序员却不知道原因而一直寻找代码的错误。,分布式系统 时钟同步,结论：在分布式系统中，时钟同步是非常重要的，也是必不可少的。,物理时钟,物理时间概念 UTC（统一协调时间），它是所有现代人使用的时间。,引入 时钟同步算法,如果一台机器上有一个WWV接收器接收标准时间，那么，时间同步算法的目的就是让所有机器的时钟与该机器的时钟进行同步。如果没有一台机器具有WWV接收器且每一台机器都有自己的时钟，那么时钟同步算法的目的就是使得所有机器的时钟尽可能地一致。,时钟同步算法,时钟精确度 设UTC时间为t，机器的的时间为C，则机器时钟的精确度可以用一个常数来表达：1-1+一般来说，由生产商规定，称为最大偏移率。,系统基础模型,时钟同步算法,同步间隔最坏的情况下，两个计算机的时钟以相反的方向偏离UTC时间，则要保证两个时钟误差不超过，就必须至少/2秒钟重新同步一次。,系统基础模型,时钟同步算法,时钟同步算法,1.Cristian算法2.Berkeley算法3.平均值算法,时钟同步算法：Cristian 算法,基本思想一台机器设为时间服务器（带有卫星接收器）其他的每一台机器周期性地向时间服务器发送请求消息已获得当前标准时间。时间服务器在短时间内将包含当前时间的消息发送给请求时间机器。发送机器收到此消息后，将机器时钟调到与时间服务器一致的标准状态。,时钟同步算法：Cristian 算法,时钟同步算法：Cristian 算法,存在问题 发送者如何根据时间服务器的返回值调整时间？由于时间不能倒退，因此一种方法是根据时钟快慢，中断服务程序调整（增大或减小）每次中断所加的时间。,时钟同步算法：Cristian 算法,存在问题 如何处理从时间服务器发送的应答到发送者存在的延迟？精确记录从向时间服务器发送请求的起始时间T0和接受到的应答的结束时间T1。当前服务器时间估计值=CUTC+(T0-T1)/2如果考虑服务器中断处理的时间I，那么传输的时间间隔为TI-T0=I,单向传输时间为它的一半。,时钟同步算法：Berkeley算法,基本思想 主动式服务-与Cristian算法中的被动式时间服务器相反 适合于没有WWV接收器的系统,时钟同步算法：Berkeley算法,过程 服务器主动定期询问每台机器的时间 服务器基于客户的回答，告知它们拨快或者拨慢时间,时钟同步算法：Berkeley算法,实现方法,时间守卫程序向所有其他机器询问时钟值其他机器做出应答时间守卫程序通知每台机器如何调整他们的时钟,时间守卫程序,a),b),c),时钟同步算法：Berkeley算法,实现方法,在3:00中时，时间守卫程序把它的时间告诉其他机器，并询问他们各自的时间。各台机器将它们各自的时间与时间守护程序时间的差值告诉时间守护进程。有了这些值，时间守护程序计算出它们的平均值，并通知各台机器如何调整各自的时钟。,时间守卫程序,a),b),c),时钟同步算法：平均值算法,Cristian算法和Berkeley算法-集中式算法 平均值算法-非集中式算法,时钟同步算法：平均值算法,基本思想 将时间分成固定长度的再同步间隔R 第i次同步开始于T0+iR，结束于T0+(i+1)R 每次同步间隔开始，每台机器广播自己的时间 对于某一具体的机器，当所有的同步广播都到达后，它根据所有的时间执行某一平均算法得到一新值，再根据新值调整时钟,2.逻辑时钟,逻辑时钟,基本概念 许多应用中，并不严格要求所有的机器都与UTC时间保持一致，而只需要所有机器时间相同就够了，即系统保持一个内部一致的时钟。这种时钟称为逻辑时钟。更进一步，很多问题中根本就不需要时间严格一致，而只是需要多个事件的发生顺序一致就可以。,逻辑时钟同步,如果两个进程不进行交互，那么它们的时钟也无须同步。这是因为即使没有同步也察觉不出来，并且也不会产生问题。通常重要的不是所有的进程在时间上完全一致，而是它们在事件的发生顺序上要达成一致。,Lamport 时间戳 为了同步逻辑时钟，Lamport定义了一个称作“先发生”的关系。,Lamport 算法(逻辑时钟同步算法),事件a先发生，然后b才发生 如果a和b是同一个进程的两个事件，如果a在b之前发生，则ab为真 如果a是一个进程发生消息的事件，b是另一个进程的接收消息事件，则ab也为真先发生关系是一个传递关系，若ab且bc，则ac。,先发生关系 ab,如果x和y事件发生在两个互不交换消息的进程中，xy不真，yx也不真。这两个事件称为并发的，意味着无法说这两个事件什么时候发生，哪个事件先发生。,并发事件,Lamport 时间戳 我们需要一种测量时间的方法，使得对于每个时间a，我们都能为它分配一个所有进程都认可的时间值C(a)。这些时间值必须具有如下性质：如果ab，那么C(a)C(b)。若在同一进程中a在b之前发生，则C(a)C(b)。若a和b分别表示发送一个消息和接收该消息的事件，则C(a)C(b)。,Lamport 算法(逻辑时钟同步算法),Lamport 时间戳 时间值C是一直向前走的（即增加），不会向后退（即减少）。校正时间的操作总是给时间加上一个正值，而不能是减掉一个正值，时间的修改只能增加而不能减少。,Lamport 算法(逻辑时钟同步算法),在a)中有三个进程。每一个进程都运行 在不同的机器上。每一个机器都有一个自己的时钟。并且以各自的速度向前走。,Lamport 算法 算法基本思想,Step 1,当进程0中的时钟滴答6次时；进程1滴答了8次；进程3滴答10次。,Lamport 算法 算法基本思想,Step 2,在时间为6时，进程0发送了一个消息A给进程1，进程1在时间为16时收到了消息。如果消息中含有消息开始发送的时间值6，则进程1认为该消息的传输花费了10次滴答。,Lamport 算法 算法基本思想,Step 3,16-6=10,同理，消息B从进程1传输到进程2花费了16次滴答,Lamport 算法 算法基本思想,Step 4,40-24=16,但是，由进程2发送给进程1的消息C在发送时的时间值为60而在接收时时间值为56。这样，消息C的传输时间为负值。,Lamport 算法 算法基本思想,Step 5,Lamport 算法 算法基本思想,Lamport解决这个问题的算法：每一个消息都含有一个发送者时钟的发送时间，当消息到达时，接受者将自己时钟的接收时间与发送时间相比较。如果接收时间小于等于发送时间，则接收者的时钟被修改成发送时间加1。如果接收时间大于发送时间，则不改变接受者的时钟。,因此消息C到达进程1的时间改为61消息D到达进程0的时间改为70。,Lamport 算法 算法基本思想,Step 6,Lamport算法还需满足一个要求：任意两个事件的时间之差至少为1。如果一个进程连续发送或接受两个消息，则这两个消息的时间之差也至少为1。,Lamport 算法(逻辑时钟同步算法),我们对不同进程内两个同时发生的事件是这样赋时间值的：事件发生的时间值与该事件所属进程的进程号连接起来，中间用“.”加以分隔。例如，进程1和进程2中两个事件恰好同时在时间为40时发生。进程1中的事件发生时间为40.1，而进程2中的事件发生时间为40.2,Lamport 算法(逻辑时钟同步算法),由此，我们现在有一个为分布式系统中的所有事件分配时间的方法，它遵守下面的规则：若在同一进程中a在b之前发生，则C(a)C(b)。若a和b分别表示发送一个消息和接收该消息的事件，则C(a)C(b)。对于所有不同的事件a和b，C(a)C(b)。,Lamport 算法(逻辑时钟同步算法),Thanks!,
