Christian's算法-逐步调整法 口时间服务器,可接受WwV的UTC时间 口每隔82p校准时间(允许误差δ,存在误差p) o假设:每秒产生100次 发送机器 时间服务器 中断,每次中断将时间 时间 请求 加10毫秒 √若调慢时钟,中断服务 ,中断处理 程序每次只加9毫秒; 时间 √若加快时钟,则加11毫 秒 传播_T1-Tn-I C 时间 √传播时间 0和T都是由相同时钟测量的 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 11 Christian’s 算法 -- 逐步调整法 ❑时间服务器，可接受WWV的UTC时间 ❑每隔δ/2ρ校准时间（ 允许误差δ ，存在误差ρ ） o 假设：每秒产生100次 中断，每次中断将时间 加10毫秒 ✓ 若调慢时钟，中断服务 程序每次只加9毫秒； ✓ 若加快时钟，则加11毫 秒。 ✓ 传播时间
Berkeley算法一主动式方法 1.时间监控器定期查询其他机器时间 2.计算出平均值 3.通知其他机器调整时间 /时间守护进程 3:00 3:00 3:05 0 3:00 3:00+25 10-20 网络 325 2:50 3: 3:05 (a) (b) 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 12 Berkeley 算法 – 主动式方法 1. 时间监控器定期查询其他机器时间 2. 计算出平均值 3. 通知其他机器调整时间
平均值算法一非集中式方法 1.所有机器广播自己的时钟时间 2.启动本地计时器收集在S时间间隔中到 达的其他机器广播的时间 3.执行平均时间计算算法,得到新的时 间值 2002-6-14 第三章分布式同步控制 13 东北大学软件所于戈
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 13 平均值算法 – 非集中式方法 1. 所有机器广播自己的时钟时间 2. 启动本地计时器收集在S时间间隔中到 达的其他机器广播的时间 3. 执行平均时间计算算法，得到新的时 间值
多重外部时间源法 口例: OSF DCE方法 1.接受所有时间源的当前UC区间 2.去掉与其他区间不相交的区间 3.将相交部分的中点作为校准时间 按照源1,UCT落入此时间间隔 UTC源 UTC源2 拒绝 UTC源3 UTC源4 插入 时间 2002-6-14 东北大学软件所于戈 第三章分布式同步控制
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 14 多重外部时间源法 ❑ 例：OSF DCE方法 1. 接受所有时间源的当前UTC区间 2. 去掉与其他区间不相交的区间 3. 将相交部分的中点作为校准时间 时间
同步时钟的应用 口最多一次消息提交 2服务器的表工中,记录每个连接C最近的时线) 1.每个消息携带一个D和一个时间印ts( timesta 如果到达的消息m,ts(m)<t,则拒绝m 服务器设置的全局变量 G= Current Time- MaxLifetime-MaxClock Skew 所有<G的时间印从表T中清除 对于具有新的ID的到达消息m如果tm)<G则拒绝m, 否则,接受m ·按照ΔT,定期地将G写入磁盘。 当系统重启后,G=G+△T 2002-6-14 第三章分布式同步控制 15 东北大学软件所于戈
2002-6-14 东北大学软件所 于戈 第三章 分布式同步控制 15 同步时钟的应用 ❑ 最多一次消息提交 1. 每个消息携带一个ID和一个时间印ts（timestamp） 2. 服务器的表T中，记录每个连接C最近的时间印t 3. 如果到达的消息m，ts(m)<t, 则拒绝m 服务器设置的全局变量 G = CurrentTime – MaxLifetime – MaxClockSkew • 所有<G的时间印从表T中清除 • 对于具有新的ID的到达消息m,如果ts(m)<G则拒绝m, 否则，接受m • 按照T，定期地将G写入磁盘。 • 当系统重启后，G’=G+T