时间和全局状态.pptVIP

第3章 时间和全局状态 第3章 时间和全局状态 简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结 简介 如何计时？ 如何同步时钟？ 没有物理时钟能否确定事件的顺序？ 简介 时间的重要性 需要精确度量——审计电子商务 某些算法依赖于时钟同步——数据一致性维护、make 计算全局状态——事件排序 时间的复杂性 节点具有独立的物理时钟 精确同步物理时钟非常困难 全局状态的捕获 依赖于逻辑时钟 逻辑时钟与物理时钟无必然联系 第3章 时间和全局状态 简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结 时钟、事件和进程状态 假设 每个进程在单处理器上执行 处理器之间不共享内存 进程之间通过消息进行通信 进程状态 所有变量的值 相关的本地操作系统环境中的对象的值 事件 定义：一个通信动作或进程状态转换动作 进程历史： 时钟、事件和进程状态 计算机时钟 晶体具有固定震荡频率 硬件时钟： 软件时钟： 时钟漂移 频率不同 时钟频率随温度变化而有所差别 时钟偏移不可避免 时钟、事件和进程状态 时间分类 天文学时间 -太阳日：两次连续的太阳中天之间的时间间隔 -太阳秒：1/86400个太阳日 国际原子时间(TAI) -基于铯原子跳跃周期 -秒：9 192 631 770次跳跃周期 通用协调时间(UTC) -基于原子时间 -采用润秒，与天文时间保持一致 第3章 时间和全局状态 简介 时钟、事件和进程状态 同步物理时钟 逻辑时间和逻辑时钟 全局状态 分布式调试 小结 同步物理时钟 外部同步 采用权威的外部时间源 时钟Ci在范围D内是准确的 内部同步 无外部权威时间源,系统内时钟同步 时钟Ci在范围D内是准确的 关系 若P在范围D内外部同步,则P在范围2D内内部同步 同步物理时钟 时钟正确性 基于漂移率 基于单调性 基于混合条件 单调性+漂移率有界+同步点跳跃前进 时钟故障 崩溃故障: 时钟完全停止滴答 随机故障: 其它故障，如“千年虫”问题 同步物理时钟 同步系统中的同步 假设条件 -已知时钟漂移率范围 -存在最大的消息传输延迟 -进程每一步的执行时间已知 方法 若一个进程将时间t发送至另一个进程，且消息传输时间的不确定性为u=max－min，则 　接收进程：t+min，则时钟偏移至多为u t+max，则时钟偏移可能为u t+(max+min)/2，则时钟偏移至多为u/2 同步物理时钟 Cristian方法 应用条件 　-存在时间服务器，可与外部时间源同步 -消息往返时间与系统所要求的精度相比足够短 协议 　-进程p根据消息mr，mt计算消息往返时间Tround -根据服务器在mt中放置的时间t设置时钟为：t+Tround/2 同步物理时钟 精度分析 　若消息的最小传输时间为min，则精度为： 　　　?(Tround/2 – min) 同步物理时钟 Berkeley算法 主机周期轮询从属机时间 主机通过消息往返时间估算从属机的时间 　　与Cristian方法类似 主机计算容错平均值 主机发送每个从属机的调整量 同步物理时钟 网络时间协议(NTP) 设计目标 -可外部同步 使得跨Internet的用户能精确地与UTC同步 -高可靠性 可处理连接丢失，采用冗余服务器、路径等 -扩展性好 大量用户可经常同步，以抵消漂移率的影响 -安全性强 防止恶意或偶然的干扰 同步物理时钟 协议结构 -层次结构 -主服务器直接与外部UTC同步 -同步子网可重新配置 同步物理时钟 同步模式 -组播 　　 适用于高速LAN 　 准确度较低，但效率高 -过程调用 　　 与Cristian算法类似 准确度较低 -对称模式 保留时序信息 准确度最高 同步物理时钟 消息交换 若消息m、m’的实际传输时间分别为t、t’；o为B时钟相对于A时钟的真正偏移， o’为偏移估计，则 Ti-2 = Ti-3 + t + o , Ti = Ti-1 + t’ – o 定义 oi=(Ti-2 – Ti-3 + Ti-1 – Ti)/2 同步物理时钟 NTP采用过滤离中趋势算法，保留8个最近的oi,di，用以估算偏移o NTP采用对等方选择算法，可改变用于同步的对等方 -优先选择层次较低的对等方 -优先选择过滤