DOS-CH3-Sync.ppt

文档介绍：第3章分布式同步控制
东北大学信息学院
于戈
2002年6月
1
主要内容
时钟同步控制
互斥控制
选举算法
原子性事务管理
分布式死锁处理
习题
2002-6-14
2
第三章分布式同步控制
时钟同步
分布式算法的特点
相关信息散布在多个场地上
每个进程只能基于本地信息做决定
应避免因单点失败造成整个系统的失败
不存在公共时钟或精确的全局时间
2002-6-14
3
第三章分布式同步控制
时钟同步问题
例:makefile误差
时间
:
cc –C
2002-6-14
4
第三章分布式同步控制
逻辑时钟
计时器:石英晶体+计数器
时钟偏差(clock skew)
逻辑时钟:相对时间
物理时钟:真实时间
“之前”关系: 
事件a在b之前出现,则ab
a为发送消息m,b为接收m,则ab
具有传递性:ab, bc,则ac
并发事件(concurrent)
2002-6-14
5
第三章分布式同步控制
Lamport算法
C(a)表示事件a的时钟值。性质:
if ab;则C(a)<C(b)
a,b C(a) C(b)
C是递增的
校正算法
ab,
if C(b)<C(a), 则C(b) = C(a) +1
2002-6-14
6
第三章分布式同步控制
Lamport算法
时间
慢
快
慢
快
2002-6-14
7
第三章分布式同步控制
物理时钟与现实时钟
太阳日:连续的两次日中天的时间
太阳秒:solar-day/86400
平均太阳秒:如,格林威治时间
2002-6-14
8
第三章分布式同步控制
现实时钟
铯原子钟:9192631770次跃迁=1秒
TAI秒:国际原子时间
UTC秒:世界时间(在TAI秒中加入闰秒)
时间服务:WWV电台、GEOS卫星
10
20
2002-6-14
9
第三章分布式同步控制
时钟同步算法
如何与现实时钟同步
如何使不同机器之间相互同步
设机器时钟值Cp(t), t 为UTC时间
最大偏移率
精确时钟: dC/dt =1
快时钟: dC/dt 〉1
慢时钟: dC/dt < 1
2002-6-14
10
第三章分布式同步控制