分布式系统-时钟同步ppt课件.pptx

《分布式系统-时钟同步ppt课件.pptx》由会员分享，可在线阅读，更多相关《分布式系统-时钟同步ppt课件.pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、同 步寇迦南1.时钟同步 时钟同步例子：UNIX中make程序的调用问题。 时钟同步例子：UNIX中make程序的调用问题Make程序的作用是什么？ 可以自动完成对源文件的编译。 时钟同步UNIX系统会把较大的程序分成多个源程序，当一个源文件发生变化时（比如被修改后），只需编译一个文件即可，不需要对所有的文件进行编译。 时钟同步这个过程如何进行？ 时钟同步这个过程如何进行？当调用make程序时， make程序根据所有源文件和对应目标文件的修改时间来决定是否对某个源文件重新编译。 时钟同步例如：如果源文件input.c.c的修改时间为5155且对应目标文件input.o.o的修改时间为5151，

2、那么，make程序知道input.c.c已被修改。input.c必须被重新编译。input.oinput.oinput.cinput.c51515155t 时钟同步例如：如果源文件output.c.c的修改时间为5144且对应目标文件output.o.o的修改时间为5145，那么，不需要对output.c.c进行重新编译。output.coutput.coutput.ooutput.o51445145t 时钟同步make程序在考察完所有源文件和其对应目标文件的修改时间后决定哪些文件需要重新编译并调用编译器对其进行编译。时钟同步在分布式环境中，由于时间不同步会造成的程序不能正常运行。时钟同步在分

3、布式环境中，由于时间不同步会造成的程序不能正常运行。时钟同步假定output.o的修改时间为5144，output.c被修改并赋予的时间为5143，原因是output.c所在机器上的时钟要比output.o所在机器上的时钟慢。创建创建 output.ooutput.o51445145t进行编译的进行编译的计算机计算机51465147根据本地时根据本地时钟的时间钟的时间创建创建 output.coutput.c51425143t进行编译的进行编译的计算机计算机51445145根据本地时根据本地时钟的时间钟的时间时钟同步因此，make程序不调用编译器进行编译。结果，最终的可执行的二进制程序将包含由

4、旧的源文件和新的源文件所产生的混合目标文件，导致该可执行程序无法运行而程序员却不知道原因而一直寻找代码的错误。时钟同步结论：在分布式系统中，时钟同步是非常重要的，也是必不可少的。p 物理时间概念 UTC（统一协调时间），它是所有现代人使用的时间。时钟同步算法如果一台机器上有一个WWV接收器接收标准时间，那么，时间同步算法的就是让所有机器的时钟与该机器的时钟进行同步。如果没有一台机器具有WWV接收器且每一台机器都有自己的时钟，那么时钟同步算法的就是使得所有机器的时钟尽可能地一致。系统基础模型系统基础模型1. 2. 3. 时钟同步算法：p 基本思想一台机器设为时间服务器（带有卫星接收器）其他的每一

5、台机器周期性地向时间服务器发送请求消息已获得当前标准时间。时间服务器在短时间内将包含当前时间的消息发送给请求时间机器。发送机器收到此消息后，将机器时钟调到与时间服务器一致的标准状态。时钟同步算法：时钟同步算法：p 存在问题 发送者如何根据时间服务器的返回值调整时间？ 由于时间不能倒退，因此一种方法是根据时钟快慢，中断服务程序调整（增大或减小）每次中断所加的时间。时钟同步算法：p 存在问题 如何处理从时间服务器发送的应答到发送者存在的延迟？ 精确记录从向时间服务器发送请求的起始时间T0和接受到的应答的结束时间T1 。 当前服务器时间估计值 = CUTC+(T0- T1)/2 如果考虑服务器中断处

6、理的时间I，那么传输的时间间隔为TI- T0=I ,单向传输时间为它的一半。时钟同步算法：p 基本思想 主动式服务-与中的被动式时间服务器相反 适合于没有WWV接收器的系统 时钟同步算法：p 过程 服务器主动定期询问每台机器的时间 服务器基于客户的回答，告知它们拨快或者拨慢时间时钟同步算法：p 实现方法a)a)时间守卫程序向所有时间守卫程序向所有其他机器询问时钟值其他机器询问时钟值b)b)其他其他机器做出应答机器做出应答c)c)时间守卫时间守卫程序通知每程序通知每台机器如何调整他们台机器如何调整他们的时钟的时钟时间守卫程序时间守卫程序a)b)c)时钟同步算法：p 实现方法a) a) 在在3:0

7、03:00中时，中时，时间守卫程序时间守卫程序把它的时间告诉其他机器把它的时间告诉其他机器，并并询问他们各自的时间询问他们各自的时间。b)b) 各台机器将它们各台机器将它们各自的时间各自的时间与与时间守护程序时间的差值时间守护程序时间的差值告诉告诉时间守护进程时间守护进程。c) c) 有了这些值，有了这些值，时间守护程序时间守护程序计算出它们的平均值计算出它们的平均值，并通，并通知知各台机器如何调整各自的各台机器如何调整各自的时钟时钟。时间守卫程序时间守卫程序a)b)c)时钟同步算法：和时钟同步算法：p 基本思想 将时间分成固定长度的再同步间隔R 第i次同步开始于T0+iR，结束于T0+(i+

8、1)R 每次同步间隔开始，每台机器广播自己的时间 对于某一具体的机器，当所有的同步广播都到达后，它根据所有的时间执行某一平均算法得到一新值，再根据新值调整时钟2.逻辑时钟p 基本概念 许多应用中，并不严格要求所有的机器都与UTC时间保持一致，而只需要所有机器时间相同就够了，即系统保持一个内部一致的时钟。这种时钟称为逻辑时钟。更进一步，很多问题中根本就不需要时间严格一致，而只是需要多个事件的发生顺序一致就可以。如果两个进程不进行交互，那么它们的时钟也无须同步。这是因为即使没有同步也察觉不出来，并且也不会产生问题。通常重要的不是所有的进程在时间上完全一致，而是它们在事件的发生顺序上要达成一致。p

9、Lamport 时间戳 为了同步逻辑时钟，Lamport定义了一个称作“先发生”的关系。事件a先发生，然后b才发生 如果a和b是同一个进程的两个事件，如果a在b之前发生，则ab为真 如果a是一个进程发生消息的事件， b是另一个进程的接收消息事件，则ab也为真先发生关系是一个传递关系，若ab且bc ，则ac 。先发生关系 ab 如果x和y事件发生在两个互不交换消息的进程中， xy不真， yx也不真。 这两个事件称为并发的，意味着无法说这两个事件什么时候发生，哪个事件先发生。并发事件p Lamport 时间戳 我们需要一种，使得对于每个时间a，我们都能为它分配一个所有进程都认可的时间值C(a)。

10、这些时间值必须具有如下性质：如果ab，那么C(a) C(b)。 若在同一进程中a在b之前发生，则C(a) C(b) 。 若a和b分别表示发送一个消息和接收该消息的事件，则C(a) C(b) 。p Lamport 时间戳 时间值C是一直向前走的（即增加），不会向后退（即减少）。 校正时间的操作总是给时间加上一个正值，而不能是减掉一个正值，时间的修改只能增加而不能减少。在a)中有三个进程。每一个进程都运行 在不同的机器上。每一个机器都有一个自己的时钟。并且以各自的速度向前走。Step 1当进程0中的时钟滴答6次时；进程1滴答了8次；进程3滴答10次。Step 2在时间为6时，进程0发送了一个消息A

11、给进程1，进程1在时间为16时收到了消息。如果消息中含有消息开始发送的时间值6，则进程1认为该消息的传输花费了10次滴答。Step 316-6=10同理，消息B从进程1传输到进程2花费了16次滴答Step 440-24=16但是，由进程2发送给进程1的消息C在发送时的时间值为60而在接收时时间值为56。这样，消息C的传输时间为负值。Step 5Lamport解决这个问题的算法：每一个消息都含有一个发送者时钟的发送时间，当消息到达时，接受者将自己时钟的接收时间与发送时间相比较。如果接收时间小于等于发送时间，则接收者的时钟被修改成发送时间加1。如果接收时间大于发送时间，则不改变接受者的时钟。因此消息C到达进程1的时间改为61消息D到达进程0的时间改为70。Step 6p Lamport算法还需满足一个要求：任意两个事件的时间之差至少为1。如果一个进程连续发送或接受两个消息，则这两个消息的时间之差也至少为1。p 我们对不同进程内两个同时发生的事件是这样赋时间值的： 事件发生的时间值与该事件所属进程的进程号连接起来，中间用“.”加以分隔。 例如，进程1和进程2中两个事件恰好同时在时间为40时发生。进程1中的事件发生时间为40.1，而进程2中的事件发生时间为40.2Thanks!