第 10章 分布式系统中的同步问题
10.1 时钟同步分布式系统特点：
相关的信息分布在多台机器上
没有共享内存进程只根据本地可用的信息做出决策
系统中不存在公共时钟或其它精确的全局时间源
在集中式系统中,时间是很明确的时钟同步 例子
UNIX的 Make,检查文件最后修改时间
创建 input.o后,源 input.C修改了,要重新编译 input.C
设 ouput.o 的 修 改 时 间 是 2000 。 创建
output.o后即修改了源 output.c
但编辑 output.c的机器时钟慢,修改后
output.c时间被 1999
make不会重新编译 output.c,程序的运行会出现问题
10.2 逻辑时钟 (1)
只关心时钟内部一致性,不关心时钟是否与实际时间一致
1978年 Lamport指出,系统中的时钟并不需要绝对的同步
重要的不是进程有完全一致的时间,而是事件发生的先后次序要一致
10.2 逻辑时钟 (2)
发生之前 （ happens-before） 关系定义
表达式 a b读作,a发生在 b前,
即所有进程都认为事件 a先发生,然后才发生事件 b
事件 a,有一个时间值 C（ a）
如果 a和 b是同一进程中的事件,而且 a发生在 b前
那么 a b为 true,C（ a） <C（ b）
10.2 逻辑时钟 (3)
传递性
Happens-before关系具有传递性如果 a b和 b c都成立,a c也成立并发事件：
如果事件 x和 y发生在不同的进程中,且这两进程间不交换信息那么 x y和 y x都不成立 。 这两个事件就称为并发事件
并发意味着两个事件发生时,无法确定哪个事件先发生,或者说不需要考虑此事
时钟时间 C必须向前 （ 不断增加 ）,不能后退 （ 减小 ）
对时间的更新,只能是在时钟上加一个正数,
不能减正数
Lamport算法 (1)：
例子说明 (1)
三个进程运行在不同的有自己时钟的机器上,
每个时钟按自己的速度运行
可以看到,进程 0中时钟有 6次嘀嗒时,进程 1已经有了 8次,而进程 2已经有了 10次
Lamport算法 (2)：
设,计时器每秒生成 60次中断,每次中断称为一个时钟嘀嗒
从进程 2发送该进程 1的消息 C,其发送时刻为 60,到达时刻为 56
同样,从进程 1到进程 0的消息 D,其发送时刻为 64,到达时刻为 54
这显然是不可能的,也是必须避免出现的情况例子说明 (2)
Lamport算法 (3)：
消息 c的发送时间为 60,它的到达时间一定在时刻 61或 61之后
让每条消息都携带发送者时钟的发送时刻
当消息到达接收时,如果接收者的时钟指示值先于发送消息的时间
接受者的时钟值就应快于消息发送时刻加 1
之后时间值例子说明 (3)
Lamport算法 (4)：
Lamport算法 (5)：
两个事件之间,时钟至少应间隔一个嘀嗒
如果一个进程依次快速发送或接收两条消息,
就必须调整时钟
使两个事件之间 （ 至少 ） 间隔一个时钟嘀嗒
附加条件,没有两个事件是精确地在同一时刻发生的：
1.在同一进程中,如果 a在 b前面发生,
那么 C(a)<C(b)
2.如果 a与 b分别代表诮息的发送和接收,
那么 C(a)<C(b)
3.对于所有的事件 a与 b而言,C(a)≠C(b)
Lamport算法 (6)：
算法给出系统中所有事件的整体定序方法
该算法在学术界中得到广泛认同
Lamport算法 (7)：
10.3 物理时钟 (1)
在某些系统中,实际的时钟时间非常重要,
需要物理时钟
如何使物理时钟与世界的时钟同步？
物理时间之间如何保持同步？
原子钟可以准确度量时间
世界时 （ Universal Coordinated Time）
简称 UTC
UTC是现代计时的基础
National Institute of Standard Time
NIXT,国家标准时间组织短波电台,WWV
每个 UTC秒的起始时刻,WWV就发送一个短脉冲
WWV本身的误差大约为 +-1毫秒物理时钟 (2)
10.4 时钟同步算法
如果某台机器有 WWV接收器
时钟同步的目的是使其它机器与这台机器同步时钟同步算法的基本模型 (1)
设每台机器都有个计时器,该计时器每秒中断 H次
计时器溢出时,中断处理程序就将软件时钟加 1
软件时钟是从过去某一已知时间开始所经历的 tick数
这个时钟的值称为 C。 当 UTC时间为 t时,
机器 p的时钟值为 Cp(t)
理想情况下 dC/dt应为 1
理论上,当 H = 60时,计时器应每小时生成
216,000次 ticks
实际上,计时器芯片的相对误差大约为 10-5，
即 每 小 时 的 tick数 的 范 围 为 215,998到
216,002
准确地说,如果存在一个常数 p
1 - ρ≤ dC/dt ≤ 1 + ρ
成立,就可以认为计时器是正常工作的时钟同步算法的基本模型 (2)
如果两个时钟偏离 UTC的方向相反那么在同步之后的 △ t时刻时它们的时差为 2ρ△ t
要保证两个时钟间时间差不超过 δ
必须至少每隔 δ/2ρ秒重新同步
Cristian算法 (1)
某台机器拥有 WWV接收器的系统的算法
时钟同步的目的就是使其它机器与有 WWV
接收器的机器保持同步
有 WWV 接收器的机器称为时间服务器
（ timeserver）
Cristian算法 (2)
系统中每台机器至少每隔 δ/2ρ秒就向时间服务器发送一条消息查询当前时间
服务器尽快将携带当前时间 CUTC的消息返回给请求者
一种近似方法发送者得到时间服务器的响应后,直接将其时钟值设置为 CUTC
Cristian算法 (3)
笫一个问题：时间决不能倒退如果这个请求发送者的时钟比实际时间快这时仅将 CUTC设置为时钟的当前值会引起严重问题
Cristian算法 (4)
对时钟的调整必须逐步进行
一种方法：假设计时器每秒中断 100次正常情况下,每次中断将时钟时间增加 10毫秒如果要使时钟慢下来,中断程序就每次只将时间增加 9
直到将时间矫正过来为止
Cristian算法 (5)
同样,每次中断时将时间加 11毫秒,
就会逐渐将时钟调快,
而不应直接将时钟值设快
Cristian算法 (6)
第二个问题时间服务器将当前时间发送给查询时间的机器需要时间这个延迟时间可能会很长,而且它也在变化
Cristian的处理方法就是计算出准确的延迟时间为了提高估计值的准确性,建议要进行一系列的测量
Berkeley UNIX算法 (1)
时间服务器是活动的,它定期向其他机器查询这些机器的时间
根据得到的响应,时间服务器计算出一个平均值
并通知其它机器调整其时钟
Berkeley UNIX算法 (2)
重复这个过程,直到达到一定的缩减量为止
这种方法适用于那些没有 WWV接收器的系统
在这样的系统中,操作员必须阶段性地手工设置时间的时间
10.5 互斥问题
在分布式系统中,临界区和互斥如何实现
10.5.1 集中式算法
在分布式系统中,实现互斥的最简单算法是模拟单处理机的情形集中式算法基本思路
一个进程作为协调者
其他进程要进入临界区须先发出请求消息说明要进入哪一个临界区
如果在那个临界区中,当前没有其他进程那么协调者就发出批准
当批准到达请求的机器后发出请求的进程就进入临界区集中式算法评价
显然本算法中由协调者保证互斥
算法是公平的
因为按收到请求的先后顺序,考虑是否发出回答
不会出现有某个进程永远等待的现象
算法的缺点,协调者是一个单点失效的机制如果协调者垮台了,是,不允许,呢,还是它自身垮台了呢？
10.5.2 分布式算法 (1)
Richart与 Agrawala(R&A)算法
要求在系统中,对所有事件安排一个次序
进程在进入临界区之前,先构造一条消息
消息中包含有要进入的临界区的名称,进程编号以及当前时间
把该诮息发给所有其他的进程分布式算法 (2)
为简单起见,假定消息的发送是可靠的,每一进程都认可收到了此消息
各个进程依据情况,发回消息
如果接受方不在临界区中并且也不想进入,
那么发出 OK
如果接受方已在临界区内,那么不应答,并把该消息放到队列中
如果接受方也想进临界区,但还没有进入比较收到的消息和自己发出消息的时间戳分布式算法 (3)
如果收到消息中的时间戳早,则发出 OK
如果自己的消息较早,那么不发消息,并把请求送入队列
请求的进程要等到所有其他进程回送允许消息为止
当所有的允许消息都到达后,该进程就可以进入申请的临界区
退出临界区后,该进程向在其队列中的所有其他进程发出 OK
分布式算法 (4)
算法关键当发生有冲突的申请时所有进程均同意有小时间戳一方取胜分布式算法评价
算法中不存在单点失效却出来了多点失效
一个进程垮台后,它不响应外来的请求还阻塞了后续试图进入临界区的进程
该算法仅使出错概率增大了,而且还要占用大量网络资源分布式算法评价 (2)
补救方法,在发送方设置有超时的反应机制
该机制不断询问直到有一个回答收到
或者在经过一段设定的时间段后,得出结论,
接收方有故障
这个算法,速度慢,复杂,开销也大
但至少表明了,分布式算法是可行的
10.5.3 令牌环网算法 (1)
一个分布式系统,内部的进程构成了一个逻辑上的环形网
所有的进程都知道它的后续者是谁
设令牌从进程 k传到进程 k+1沿环传递
当进程得到令牌后,首先看是否需要进入临界区
如果需要,进程进入临界区,进行所需的操作
在撤出临界区后,该进程让令牌沿环传递令牌环网算法 (2)
本算法规定,进程不允许用同一张令牌进入第二个临界区
如果一个进程得到了令牌,但不打算进入临界区那么它就继续传递令牌
如果没有进程想进入临界区,令牌则沿着环路高速循环令牌环网算法评价 (1)
算法的正确性是明显的
因为任何时刻,只有一个进程持有令牌
在临界区中只可能有一个进程
由于巳经规定好令牌传递次序,所以不可能发生死锁
最坏情况是,排在最后的进程要等到其他进程都进入临界区,完成操作,并离开之后,
才轮到它令牌环网算法评价 (2)
算法的问题如果令牌因为某种原因丢失了,就必须重新生成一个
但是如何探测令牌是否丢失,却是一件难事
令牌在一小时之内没有传递,不意味着丢失了,可能某个进程还在使用它令牌环网算法评价 (3)
另一个问题,如果某个进程垮台了,算法也会碰到麻烦
补救方法,进程收到令牌后,给予认可
在进程试图把令牌递交给邻居后如果在规定时限内没有认可回答,就判定该邻居是死进程
于是令牌越过死进程,传到下一个进程中
10.6 典型选举算法：威力 (Bully)算法
分布式系统需要有一个进程担当协调者
完成一些特别的工作任务
如何选择进程来担当协调者威力 (Bully)算法 (1)
假定每台机器只有一个进程每一进程都有一个单独的编号
还假定每一进程都了解其他进程的编号
选举算法的目的试图挑出一个具有最高进程编号的进程,委任它为协调者
确认如下规则,当选举开始以后,它会得出结论威力 (Bully)算法 (2)
所有的进程都同意某个进程将担任新的协调者
当某一个进程 P,发现协调者不再响应请求后它积极发起一场竞选活动
P,掌握着一场选举威力 (Bully)算法 (3)
规则：
首先,P发出选举消息给所有比它更高级别编号的进程
其次,如果没有响应者,那么 P就赢得这场选举,成为新的协调者
最后,如果更高编号中有一个进程响应那么这个更高编号的进程就赢得选举
P也就完成了使命威力 (Bully)算法 (4)
一个进程可能从小编号的进程中收到选举消息
这时,这个接收进程回送 OK消息给发送方
从而表明它将接管选举工作
接收方大员然后掌管这场选举活动,向其它进程发出消息
宣布取得了选举胜利,并开始其协调者的工作威力 (Bully)算法 (5)
如果有一个最高级编号进程在运行
它肯定会赢得选举并接管协调者的工作
最有势力的大亨总是取得胜利
小伙计可能是白忙一场
这就是称之为,威力 (Bully)算法,的原因
10.1 时钟同步分布式系统特点：
相关的信息分布在多台机器上
没有共享内存进程只根据本地可用的信息做出决策
系统中不存在公共时钟或其它精确的全局时间源
在集中式系统中,时间是很明确的时钟同步 例子
UNIX的 Make,检查文件最后修改时间
创建 input.o后,源 input.C修改了,要重新编译 input.C
设 ouput.o 的 修 改 时 间 是 2000 。 创建
output.o后即修改了源 output.c
但编辑 output.c的机器时钟慢,修改后
output.c时间被 1999
make不会重新编译 output.c,程序的运行会出现问题
10.2 逻辑时钟 (1)
只关心时钟内部一致性,不关心时钟是否与实际时间一致
1978年 Lamport指出,系统中的时钟并不需要绝对的同步
重要的不是进程有完全一致的时间,而是事件发生的先后次序要一致
10.2 逻辑时钟 (2)
发生之前 （ happens-before） 关系定义
表达式 a b读作,a发生在 b前,
即所有进程都认为事件 a先发生,然后才发生事件 b
事件 a,有一个时间值 C（ a）
如果 a和 b是同一进程中的事件,而且 a发生在 b前
那么 a b为 true,C（ a） <C（ b）
10.2 逻辑时钟 (3)
传递性
Happens-before关系具有传递性如果 a b和 b c都成立,a c也成立并发事件：
如果事件 x和 y发生在不同的进程中,且这两进程间不交换信息那么 x y和 y x都不成立 。 这两个事件就称为并发事件
并发意味着两个事件发生时,无法确定哪个事件先发生,或者说不需要考虑此事
时钟时间 C必须向前 （ 不断增加 ）,不能后退 （ 减小 ）
对时间的更新,只能是在时钟上加一个正数,
不能减正数
Lamport算法 (1)：
例子说明 (1)
三个进程运行在不同的有自己时钟的机器上,
每个时钟按自己的速度运行
可以看到,进程 0中时钟有 6次嘀嗒时,进程 1已经有了 8次,而进程 2已经有了 10次
Lamport算法 (2)：
设,计时器每秒生成 60次中断,每次中断称为一个时钟嘀嗒
从进程 2发送该进程 1的消息 C,其发送时刻为 60,到达时刻为 56
同样,从进程 1到进程 0的消息 D,其发送时刻为 64,到达时刻为 54
这显然是不可能的,也是必须避免出现的情况例子说明 (2)
Lamport算法 (3)：
消息 c的发送时间为 60,它的到达时间一定在时刻 61或 61之后
让每条消息都携带发送者时钟的发送时刻
当消息到达接收时,如果接收者的时钟指示值先于发送消息的时间
接受者的时钟值就应快于消息发送时刻加 1
之后时间值例子说明 (3)
Lamport算法 (4)：
Lamport算法 (5)：
两个事件之间,时钟至少应间隔一个嘀嗒
如果一个进程依次快速发送或接收两条消息,
就必须调整时钟
使两个事件之间 （ 至少 ） 间隔一个时钟嘀嗒
附加条件,没有两个事件是精确地在同一时刻发生的：
1.在同一进程中,如果 a在 b前面发生,
那么 C(a)<C(b)
2.如果 a与 b分别代表诮息的发送和接收,
那么 C(a)<C(b)
3.对于所有的事件 a与 b而言,C(a)≠C(b)
Lamport算法 (6)：
算法给出系统中所有事件的整体定序方法
该算法在学术界中得到广泛认同
Lamport算法 (7)：
10.3 物理时钟 (1)
在某些系统中,实际的时钟时间非常重要,
需要物理时钟
如何使物理时钟与世界的时钟同步？
物理时间之间如何保持同步？
原子钟可以准确度量时间
世界时 （ Universal Coordinated Time）
简称 UTC
UTC是现代计时的基础
National Institute of Standard Time
NIXT,国家标准时间组织短波电台,WWV
每个 UTC秒的起始时刻,WWV就发送一个短脉冲
WWV本身的误差大约为 +-1毫秒物理时钟 (2)
10.4 时钟同步算法
如果某台机器有 WWV接收器
时钟同步的目的是使其它机器与这台机器同步时钟同步算法的基本模型 (1)
设每台机器都有个计时器,该计时器每秒中断 H次
计时器溢出时,中断处理程序就将软件时钟加 1
软件时钟是从过去某一已知时间开始所经历的 tick数
这个时钟的值称为 C。 当 UTC时间为 t时,
机器 p的时钟值为 Cp(t)
理想情况下 dC/dt应为 1
理论上,当 H = 60时,计时器应每小时生成
216,000次 ticks
实际上,计时器芯片的相对误差大约为 10-5，
即 每 小 时 的 tick数 的 范 围 为 215,998到
216,002
准确地说,如果存在一个常数 p
1 - ρ≤ dC/dt ≤ 1 + ρ
成立,就可以认为计时器是正常工作的时钟同步算法的基本模型 (2)
如果两个时钟偏离 UTC的方向相反那么在同步之后的 △ t时刻时它们的时差为 2ρ△ t
要保证两个时钟间时间差不超过 δ
必须至少每隔 δ/2ρ秒重新同步
Cristian算法 (1)
某台机器拥有 WWV接收器的系统的算法
时钟同步的目的就是使其它机器与有 WWV
接收器的机器保持同步
有 WWV 接收器的机器称为时间服务器
（ timeserver）
Cristian算法 (2)
系统中每台机器至少每隔 δ/2ρ秒就向时间服务器发送一条消息查询当前时间
服务器尽快将携带当前时间 CUTC的消息返回给请求者
一种近似方法发送者得到时间服务器的响应后,直接将其时钟值设置为 CUTC
Cristian算法 (3)
笫一个问题：时间决不能倒退如果这个请求发送者的时钟比实际时间快这时仅将 CUTC设置为时钟的当前值会引起严重问题
Cristian算法 (4)
对时钟的调整必须逐步进行
一种方法：假设计时器每秒中断 100次正常情况下,每次中断将时钟时间增加 10毫秒如果要使时钟慢下来,中断程序就每次只将时间增加 9
直到将时间矫正过来为止
Cristian算法 (5)
同样,每次中断时将时间加 11毫秒,
就会逐渐将时钟调快,
而不应直接将时钟值设快
Cristian算法 (6)
第二个问题时间服务器将当前时间发送给查询时间的机器需要时间这个延迟时间可能会很长,而且它也在变化
Cristian的处理方法就是计算出准确的延迟时间为了提高估计值的准确性,建议要进行一系列的测量
Berkeley UNIX算法 (1)
时间服务器是活动的,它定期向其他机器查询这些机器的时间
根据得到的响应,时间服务器计算出一个平均值
并通知其它机器调整其时钟
Berkeley UNIX算法 (2)
重复这个过程,直到达到一定的缩减量为止
这种方法适用于那些没有 WWV接收器的系统
在这样的系统中,操作员必须阶段性地手工设置时间的时间
10.5 互斥问题
在分布式系统中,临界区和互斥如何实现
10.5.1 集中式算法
在分布式系统中,实现互斥的最简单算法是模拟单处理机的情形集中式算法基本思路
一个进程作为协调者
其他进程要进入临界区须先发出请求消息说明要进入哪一个临界区
如果在那个临界区中,当前没有其他进程那么协调者就发出批准
当批准到达请求的机器后发出请求的进程就进入临界区集中式算法评价
显然本算法中由协调者保证互斥
算法是公平的
因为按收到请求的先后顺序,考虑是否发出回答
不会出现有某个进程永远等待的现象
算法的缺点,协调者是一个单点失效的机制如果协调者垮台了,是,不允许,呢,还是它自身垮台了呢？
10.5.2 分布式算法 (1)
Richart与 Agrawala(R&A)算法
要求在系统中,对所有事件安排一个次序
进程在进入临界区之前,先构造一条消息
消息中包含有要进入的临界区的名称,进程编号以及当前时间
把该诮息发给所有其他的进程分布式算法 (2)
为简单起见,假定消息的发送是可靠的,每一进程都认可收到了此消息
各个进程依据情况,发回消息
如果接受方不在临界区中并且也不想进入,
那么发出 OK
如果接受方已在临界区内,那么不应答,并把该消息放到队列中
如果接受方也想进临界区,但还没有进入比较收到的消息和自己发出消息的时间戳分布式算法 (3)
如果收到消息中的时间戳早,则发出 OK
如果自己的消息较早,那么不发消息,并把请求送入队列
请求的进程要等到所有其他进程回送允许消息为止
当所有的允许消息都到达后,该进程就可以进入申请的临界区
退出临界区后,该进程向在其队列中的所有其他进程发出 OK
分布式算法 (4)
算法关键当发生有冲突的申请时所有进程均同意有小时间戳一方取胜分布式算法评价
算法中不存在单点失效却出来了多点失效
一个进程垮台后,它不响应外来的请求还阻塞了后续试图进入临界区的进程
该算法仅使出错概率增大了,而且还要占用大量网络资源分布式算法评价 (2)
补救方法,在发送方设置有超时的反应机制
该机制不断询问直到有一个回答收到
或者在经过一段设定的时间段后,得出结论,
接收方有故障
这个算法,速度慢,复杂,开销也大
但至少表明了,分布式算法是可行的
10.5.3 令牌环网算法 (1)
一个分布式系统,内部的进程构成了一个逻辑上的环形网
所有的进程都知道它的后续者是谁
设令牌从进程 k传到进程 k+1沿环传递
当进程得到令牌后,首先看是否需要进入临界区
如果需要,进程进入临界区,进行所需的操作
在撤出临界区后,该进程让令牌沿环传递令牌环网算法 (2)
本算法规定,进程不允许用同一张令牌进入第二个临界区
如果一个进程得到了令牌,但不打算进入临界区那么它就继续传递令牌
如果没有进程想进入临界区,令牌则沿着环路高速循环令牌环网算法评价 (1)
算法的正确性是明显的
因为任何时刻,只有一个进程持有令牌
在临界区中只可能有一个进程
由于巳经规定好令牌传递次序,所以不可能发生死锁
最坏情况是,排在最后的进程要等到其他进程都进入临界区,完成操作,并离开之后,
才轮到它令牌环网算法评价 (2)
算法的问题如果令牌因为某种原因丢失了,就必须重新生成一个
但是如何探测令牌是否丢失,却是一件难事
令牌在一小时之内没有传递,不意味着丢失了,可能某个进程还在使用它令牌环网算法评价 (3)
另一个问题,如果某个进程垮台了,算法也会碰到麻烦
补救方法,进程收到令牌后,给予认可
在进程试图把令牌递交给邻居后如果在规定时限内没有认可回答,就判定该邻居是死进程
于是令牌越过死进程,传到下一个进程中
10.6 典型选举算法：威力 (Bully)算法
分布式系统需要有一个进程担当协调者
完成一些特别的工作任务
如何选择进程来担当协调者威力 (Bully)算法 (1)
假定每台机器只有一个进程每一进程都有一个单独的编号
还假定每一进程都了解其他进程的编号
选举算法的目的试图挑出一个具有最高进程编号的进程,委任它为协调者
确认如下规则,当选举开始以后,它会得出结论威力 (Bully)算法 (2)
所有的进程都同意某个进程将担任新的协调者
当某一个进程 P,发现协调者不再响应请求后它积极发起一场竞选活动
P,掌握着一场选举威力 (Bully)算法 (3)
规则：
首先,P发出选举消息给所有比它更高级别编号的进程
其次,如果没有响应者,那么 P就赢得这场选举,成为新的协调者
最后,如果更高编号中有一个进程响应那么这个更高编号的进程就赢得选举
P也就完成了使命威力 (Bully)算法 (4)
一个进程可能从小编号的进程中收到选举消息
这时,这个接收进程回送 OK消息给发送方
从而表明它将接管选举工作
接收方大员然后掌管这场选举活动,向其它进程发出消息
宣布取得了选举胜利,并开始其协调者的工作威力 (Bully)算法 (5)
如果有一个最高级编号进程在运行
它肯定会赢得选举并接管协调者的工作
最有势力的大亨总是取得胜利
小伙计可能是白忙一场
这就是称之为,威力 (Bully)算法,的原因
