分布式操作系统3.ppt

分布式操作系统
第三章分布式系统的同步
时钟同步
分布式算法的特点:
相关信息分散在多台机器中;
远程决策仅仅依赖本地信息;
系统中单点故障应该避免;
没有公用时钟或其他精确的全局时间资源存在。
当每台机器都有自己的时钟,一个发生在另一事件之后的事件可能会被标记为比后者更早的时间。
逻辑时钟
时钟点(clock tick):一次时钟中断;
时钟偏移(clock skew):因计时器频率不同而导致多台机器之间的时间偏差;
Lamport提出时钟同步的可能
时钟不需要绝对同步;
若两进程间无相互作用,则不需要同步;
若需要同步,则需要解决进程间事件发生顺序的一致性。
相对时间——逻辑时钟
绝对时间——物理时钟
“先发生”(a→b)关系:
如果a和b是在同一进程内的两个事件,且a发生在b之前,则a→b为真;
如果a是一个进程发送消息,b是另一进程接收这一消息的事件,则a→b为真,即消息不能在发送之前接收,也不能在发送的同时接收,因为传送过程还需要一定时间;
先发生是一个传递关系,即若a→b且b→c则a→c。
为每一事件分配一时间值C,当a→b,则有C(a)<C(b)
0
6
12
18
24
30
36
42
48
54
60
0
0
8
16
24
32
40
48
56
64
72
80
1
0
10
20
30
40
50
60
70
80
90
100
2
“6”→“16”→“24”→“40”
“60”→“56”→“64”→“54”
0
6
12
18
24
30
36
42
48
70
76
0
0
8
16
24
32
40
48
61
69
77
85
1
0
10
20
30
40
50
60
70
80
90
100
2
“6”→“16”→“24”→“40”
“60”→“61”→“69”→“70”
Lamport的解决方案:
直接利用先发生关系;
每条消息都携带发送者的时刻值,当消息到达时,若接收者的时钟值比消息发送时钟小,就立刻将自己的时钟调整为比发送时间大1或更多的值;
在某些条件下,将进程号附加在时间值之后,并以小数点隔开。
分布式系统时间分配规则:
若在同一进程内a发生在b之前,则C(a)<C(b);
若a和b分别代表发送消息和接收消息,则C(a)<C(b);
对所有事件a和b,C(a)<>C(b)。
物理时钟
太阳日
铯133原子钟:以铯原子133所9192631770次跃迁所用的时间为一秒,简称TAI(International Atomic Time)
闰秒(leap second):因为原子钟时和太阳秒不同步,为减少误差,当原子钟时与太阳秒计时的误差增加到800微秒时,插入一秒。
统一协调时间(UTC)