第5章分布式系统的同步

分布式系统同步算法分布式系统进程同步逻辑时钟Lamport算法物理时钟Cristian算法Berkeley算法同步基本含义同步是指两个或两个以上随时间变化的量在变化过程中保持一定的相对关系。当两个设备一起工作并对时间有精确要求的时候，就需要在它们之间进行同步。同步是基于在两个设备之间规定一个共同的时间参考。数据库同步的含义就是让两个或多个数据库内容保持一致，或者按需要部分保持一致。文件同步的含义就是让两个或多个文件夹里的文件保持一致，或者按需要部分保持一致。网络通信编程中常提到的“同步”，则主要指某函数的执行方式，即函数调用者需等待函数执行完成后才能进到下一步。“同步通信”的通信双方必须先建立同步，即双方的时钟要调整到同一个频率。收发双方不停地发送和接收连续的同步比特流。5.1分布式系统时钟同步在分布式系统中：进程之间的通信：采用消息传递(Message-passing)进行通信。与进程通信密切相关的问题：进程之间的协作和同步。

5.1分布式系统时钟同步分布式系统中的同步比单机系统中的同步要复杂的多,这是由分布式算法决定的:

1.相关的信息是分布在多个机器上的。

2.进程根据局部信息来作出决定。

3.对系统中任一个机器的失败应能容错。

4.不存在公共时钟或其它全局时间源。

5.1分布式系统时钟同步由一个机器收集所有的信息进行处理是不可能的。在分布式系统中必将造成某一个进程负担过重。分布式系统应该比单机系统更可靠。如果一个机器崩溃了,其余的机器应能继续工作,而不至于使系统瘫痪。在单机系统中,时间是确定的。如果一个进程想要知道时间,则它可以调用一个系统调用由内核告诉它当前的时间值。如果一个进程先得到时间值而另一个进程后得到时间值,那么,先得到的时间值一定比后得到的时间值小。在分布式系统中,所有机器要在时间上达到一致是非常困难的。5.1分布式系统时钟同步在分布式系统中缺乏全局时间产生不良影响的例子：Unix中make程序的调用问题。假设实现程序编辑功能的进程与实现程序编译功能的进程在不同的两台计算机上运行。Make程序的功能：自动完成对源文件的编译Make工具最主要也是最基本的功能就是通过makefile文件来描述源程序之间的相互关系并自动维护编译工作通常,一个大程序分成多个源文件。这样,对其中某一个文件的修改只需要对被修改的这个文件进行重编译,而无须对所有的源文件进行编译。当调用make程序时，Make程序根据所有源文件和对应目标文件的修改时间来决定是否对某个源文件重新编译。如果源文件input.c的修改时间为5155且对应目标文件input.o的修改时间为5151,那么,make程序知道input.c已被修改。input.c必须被重新编译。如果output.c的修改时间为5144且对应目标文件output.o的修改时间为5145,则不需要对output.c进行重新编译。Make程序在考察完所有源文件和其对应目标文件的修改时间后决定那些文件需要重新编译并调用编译器对其进行编译。5.1分布式系统时钟同步在分布式环境中,由于时间不同步造成程序不能正常运行：假定output.o的修改时间为5144,output.c被修改并被赋予的时间为5143,原因是output.c所在机器上的时钟要比output.o所在机器上的时钟慢。make程序不调用编译器进行编译。结果,最终可执行二进制程序将含有由新老源文件所生成的目标文件，导致该可执行程序无法运行而程序员却不知道原因而一直寻找程序代码的错误。结论：在分布式系统中，时钟同步是非常重要的，也是必不可少的。

时钟同步问题例：makefile误差时间output.o：cc–Coutput.c5.1分布式系统时钟同步5.1.1逻辑时钟同步算法

在分布式系统中，n台计算机上的时钟值都不相同。因此,需要一种方法将所有机器上的时钟进行同步。

Lamport在1978年指出时钟同步是可能的并提出了一个逻辑时钟同步算法。在1990年,Lamport扩展了他的工作。Lamport指出时钟的同步不是绝对的。如果两个进程并不交互,则它们的时钟就无须同步。

逻辑时钟同步算法系统中的进程不需要在事件发生的确切时间上达成一致而只需要在事件发生的先后顺序上达成一致即可。在make例子中,make只需要知道input.c是否比input.o生成的早即可,而无须知道input.c和input.o确切的生成时间。在许多应用中,只要所有机器都认可某一时间就足够了,而这个时间无须与收音机每小时广播的时间相同例如,尽管现在真正的时间是10:05,但只要所有机器都认为现在是10:00,我们说系统的时钟是同步的。我们把这种并不一定是真正时间但所有机器都一致认可的时钟称之为逻辑时钟。5.1分布式系统时钟同步5.1.1逻辑时钟同步算法如果我们增加一个条件:所有的时钟不仅一致而且与实际时间之间的误差不超过某个值。那么,这种时钟我们称之为物理时钟。为了将逻辑时钟进行同步,Lamport定义了一种称之为在之前发生的关系。表达式a→b读做”a在b之前发生”。它表示所有的进程都认为事件a先发生,而事件b后发生。a→b存在于下列两种情况:

1.如果a和b都是同一个进程中的两个事件且a在b之前发生,则a→b为真。

2.如果a是一个进程发送一个消息的事件且b是另一个进程接收该消息的事件,则a→b为真。

5.1分布式系统时钟同步5.1.1逻辑时钟同步算法在之前发送是一个传递关系,如果a→b且b→c,则a→c。如果两个事件x和y分别发生在两个不同的进程内且x和y不是同一个消息的发送和接收事件,则x→y不为真,y→x亦不为真。我们将这两个事件称之为是并发事件。度量时间的方法：对于每一个事件a,我们给a分配一个所有进程都认可的时间值C(a)。这种时间值必须具有一个特性:如果a→b,则C(a)<C(b)。时钟时间C是一直向前走的(即增加)，不会向后退(即减少)。时间的修改只能增加而不能减少。

Lamport逻辑时钟同步算法算法基本思想在图5-1（a）中有三个进程。每一个进程都运行在不同的机器上且每一个机器都有一个自己的时钟以各自的速度走时。当进程0中的时钟滴答6次时，进程1滴答8次，而进程3滴答10次。在时间为6时,进程0发送了一个消息A给进程1。进程1在时间为16时收到了消息。如果消息中含有消息开始发送的时间值6,则进程1认为该消息的传输花费了10次滴答。同理,消息B从进程1传输到进程2花费了16次滴答。但是,由进程2发给进程1的消息C在发送时的时间值为60而在接收时的时间值为56。这样,消息C的传输时间为负值。

Lamport算法时间慢快慢快5.1分布式系统时钟同步5.1.1逻辑时钟同步算法Lamport解决这个问题的算法：每一个消息都含有一个发送者时钟的发送时间,当消息到达时,接收者将自己时钟的接收时间与发送时间相比较。如果接收时间小于等于发送时间,则接收者的时钟被修改成发送时间加1。如果接收时间大于发送时间,则不改变接收者的时钟。因此,消息C到达进程1的时间改为61,消息D到达进程0的时间改为70(见图5-1(b))。Lamport算法还必须满足一个要求：任意两个事件的时间之差至少为1。如果一个进程连续发送或接收两个消息,则这两个消息的时间之差也至少为1。我们对不同进程内两个同时发生的事件是这样赋时间值的:5.1分布式系统时钟同步5.1.1逻辑时钟同步算法事件发生的时间值与该事件所属进程的进程号连接起来,中间用’.’加以分隔。例如,进程1和进程2中两个事件恰好同时在时间为40时发生。进程1中的事件发生时间为40.1而进程2中的事件发生时间为40.2。由此我们可以对系统中所有事件按如下方法赋时间值:1.在同一进程中,如果事件a在事件b之前发生,则

C(a)<C(b)。

2.如果a和b分别是一个消息的发送和接收事件,则

C(a)<C(b)。

3.对所有事件a和b,C(a)≠C(b)。

5.1分布式系统时钟同步5.1.2物理时钟同步算法如果某台机器有一个WWW接收器接收标准时间,那么,时钟同步算法的目的就是让所有机器的时钟与该机器的时钟进行同步。如果没有一台机器具有WWW接收器且每一台机器都有自己的时钟,那么,时钟同步算法的目的就是使得所有机器的时钟尽可能地一致。假定每一个机器都有一个每秒中断H次的定时器。定时器中断一次,中断处理程序就将软件时钟加1。该软件时钟保存滴答(即中断)次数。我们定义这个软件时钟的值为C。

5.1分布式系统时钟同步5.1.2物理时钟同步算法当UTC(一种标准的时间源)时间为t,则机器p上时钟值为Cp(t)。在理想情况下,对于所有的p和t,Cp(t)=t。换句话说,dC/dt=1。实际的定时器不可能每一秒精确地滴答H次。一个具有H=60的定时器应该每小时周期地滴答516,000次。但世界上最先进定时器芯片的相对误差是10-5。这就意味着一个机器时钟每小时的滴答值在515,998至516,005范围内。更确切地说,如果存在某个常数ρ使得：

1-ρ≤dC/dt≤1+ρ

则该定时器的误差在允许的范围之内。常数ρ由厂商设定。有时也称之为最大漂移率。当dC/dt>1时,时钟太快。当dC/dt<1时,时钟太慢。只有dC/dt=1时,时钟不快不慢。

Christian算法5.1.2基本思想一台机器设为时间服务器(带有卫星接收器)其他的每一台机器周期性地向时间服务器发送请求消息以获得当前标准时间。时间服务器在短时间内将包含当前时间的消息发送给请求时间机器。发送机器收到此消息后，将机器时钟调到与时间服务器一致的标准时间。Christian’s算法--逐步调整法时间服务器，可接受WWV的UTC时间(CoordinatedUniversalTime国际协调时间)每隔δ/5ρ校准时间（允许误差δ

，存在误差ρ

）两个问题：时间决不能倒退,延迟假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。传播时间Christian算法存在问题当发送消息机器时间比标准时间快时，发送消息的机器时间需往后调，应当避免。解决方法：改变定时器每秒中断次数服务器的回答消息具有一定的延迟。Berkeley算法–主动式方法时间监控器定期查询其他机器时间计算出平均值通知其他机器调整时间平均值算法–非集中式方法将时间划分成固定长度的再