第3章分布式同步控制 东北大学信息学院 于戈 2002年6月
第3章 分布式同步控制 东北大学信息学院 于 戈 2002年6月
主要内容 3.1时钟同步控制 ≥3.2互斥控制 °3.3选举算法 3.4原子性事务管理 3.5分布式死锁处理 36习题 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 2 主要内容 3.1 时钟同步控制 3.2 互斥控制 3.3 选举算法 3.4 原子性事务管理 3.5 分布式死锁处理 3.6 习题
3.1时钟同步 口分布式算法的特点 相关信息散布在多个场地上 每个进程只能基于本地信息做决定 应避免因单点失败造成整个系统的失败 ■不存在公共时钟或精确的全局时间 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 3 3.1 时钟同步 ❑分布式算法的特点 ▪ 相关信息散布在多个场地上 ▪ 每个进程只能基于本地信息做决定 ▪ 应避免因单点失败造成整个系统的失败 ▪ 不存在公共时钟或精确的全局时间
时钟同步问题 口例: makefile误差 outputo: C-C output.c 21442145214621474本地时 钟时间 创建 outputo 计算机1 21422143214421454本地时 钟时间 计算机2 修改oupu时间 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 4 时钟同步问题 ❑例：makefile误差 时间 output.o ： cc –C output.c
逻辑时钟 口计时器:石英晶体+计数器 口时钟偏差( clock skew) 口逻辑时钟:相对时间 口物理时钟:真实时间 口“之前”关系:→ 事件a在b之前出现,则a->b a为发送消息m,b为接收m,则a->b 具有传递性:a→>b,b→>c,则a->c 口并发事件( concurrent) 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 5 逻辑时钟 ❑计时器：石英晶体+计数器 ❑时钟偏差（clock skew） ❑逻辑时钟：相对时间 ❑物理时钟：真实时间 ❑“之前”关系: → – 事件a在b之前出现，则a→b – a为发送消息m，b为接收m，则a→b – 具有传递性：a→b, b→c,则a→c ❑并发事件（concurrent）
Lamport算法 口C(a)表示事件a的时钟值。性质 ifa>b;,则C(a)C(b) vabC(a)≠C(b) C是递增的 口校正算法 a>b, if c(bk<C(a), JC(b)=C(a)+1 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 6 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
Lamport算法 0 0 0 0 6 6 16 32 50 时 48D64 D69 54 70 间 慢 快 快 2002-6-14 第三章分布式同步控制 7 东北大学软件所于戈
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 7 Lamport算法 时 间 慢 快 慢 快
物理时钟与现实时钟 口太阳日:连续的两次日中天的时间 口太阳秒: solar-day/86400 日平均太阳秒:如,格林威治时间 地球轨道 中天点太阳到达 一天的最高点 在n天以后的中天 太阳 点,地球已经旋转 了将近360度 地球第0天 到银河系的距离 到达中天 到银河系的距离 地球第n天 到达中天 大 -6-14 大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 8 物理时钟与现实时钟 ❑ 太阳日：连续的两次日中天的时间 ❑ 太阳秒：solar-day/86400 ❑ 平均太阳秒：如，格林威治时间
现实时钟 口铯原子钟:9192631770次跃迁=1秒 口TA秒:国际原子时间 日UTC秒:世界时间(在TA秒中加入闰秒) 口时间服务:WWV电台、GEOS卫星 012345678910111213141516171819202122232425 TAI卜 +++++++++++ 太阳秒01234567891112131415161718192122232425 10 20 在UTC引入闰秒以A同步 2002-6-14 第三章分布式同步控制 9 东北大学软件所于戈
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 9 现实时钟 ❑ 铯原子钟：9192631770次跃迁=1秒 ❑ TAI秒：国际原子时间 ❑ UTC秒：世界时间（在TAI秒中加入闰秒） ❑ 时间服务：WWV电台、GEOS卫星 10 20
时钟同步算法 √如何与现实时钟同步 √如何使不同机器之间相互同步 口设机器时钟值Cp(t),t为UTC时间卖> 最大偏移率 精确时钟:dC/dt=1 快时钟:dC/dt〉 慢时钟:dC/dt<1 2002-6-14 第三章分布式同步控制 10 东北大学软件所于戈
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 10 时钟同步算法 ✓ 如何与现实时钟同步 ✓ 如何使不同机器之间相互同步 ❑设机器时钟值Cp(t), t 为UTC时间 – 最大偏移率 – 精确时钟： dC/dt =1 – 快时钟： dC/dt 〉1 – 慢时钟： dC/dt < 1