第3章分布式系统的同步概要.ppt

第3章 分布式系统的同步 中国科技大学软件学院 丁箐 主要内容 3.1 时钟同步 3.2 互斥 3.3 选举算法 3.4 原子性事务 3.5 分布式系统中的死锁 主要内容 3.1 时钟同步 3.2 互斥 3.3 选举算法 3.4 原子性事务 3.5 分布式系统中的死锁 3.1 时钟同步 分布式算法的特点 相关信息散布在多个场地上 每个进程只能基于本地信息做决定 应避免因单点故障造成整个系统的失败 不存在公共时钟或精确的全局时间 时钟同步问题 例：makefile误差 逻辑时钟 计时器：石英晶体+计数器 时钟偏差（clock skew） 逻辑时钟：相对时间 物理时钟：真实时间 “之前”关系: ? 事件a在b之前出现，则a?b a为发送消息m，b为接收m，则a?b 具有传递性：a?b, b?c,则a?c 并发事件（concurrent） Lamport算法 对每一事件a，在所有进程中都认可给它分配一个时间值C(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算法 物理时钟与现实时钟 （1）如何用现实世界的时钟将它们同步起来； （2）如何使各时钟之间保持同步。 太阳日：连续的两次日中天的时间 太阳秒：solar-day/86400 平均太阳秒：如，格林威治时间 现实时钟 铯原子钟：9192631770次跃迁=1秒 TAI秒：国际原子时间 UTC秒：世界时间（在TAI秒中加入闰秒） 时间服务：WWV电台、GEOS卫星 时钟同步算法 如何与现实时钟同步 如何使不同机器之间相互同步 设机器时钟值Cp(t), t 为UTC时间 最大偏移率 精确时钟： dC/dt =1 快时钟： dC/dt 〉1 慢时钟： dC/dt 1 Christian’s 算法 -- 逐步调整法 时间服务器，可接受WWV的UTC时间 每隔δ/2ρ校准时间（ 允许误差δ ，存在误差ρ ） Berkeley 算法 – 主动式方法 时间监控器定期查询其他机器时间 计算出平均值 通知其他机器调整时间 平均值算法 – 非集中式方法 将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于 T0+(i+1)R 所有机器广播自己的时钟时间 启动本地计时器收集在S时间间隔中到达的其他机器广播的时间 执行平均时间计算算法，得到新的时间值 （取平均值，去掉两端值 ） 多个外部时间源法 使用同步时钟 最多一次消息提交 每个消息携带一个ID和一个时间印ts（timestamp） 服务器的表T中，记录每个连接C最近的时间印t 如果到达的消息m，ts(m)t, 则拒绝m 使用同步时钟 基于时钟的缓存一致性 当客户读取一个副本到缓存时，设置一个租期（lease） 在租期过期之前，客户可更新副本，重续租期 如果已经过期，缓存中的副本失效 主要内容 3.1 时钟同步 3.2 互斥 3.3 选举算法 3.4 原子性事务 3.5 分布式系统中的死锁 3.2 互 斥 基本概念 当一个进程使用某个共享资源，其他进程不允许对这个资源操作 临界区（Critical Section）： 对共享资源进行操作的程序段 基本方法： 信号量、管程 问题： 死锁 活锁 饥饿 集中式算法（仿照单处理机系统的方法 ） 协调者：确定那个进程可进入临界区 通信量：3个消息：请求-许可-释放 缺点：单点失败 单协调者会成为执行的瓶颈 Win Thread 临界区 CreateMutex() WaitForSingleObject() ReleaseMutex() InitializeCriticalSection() EnterCriticalSection() LeaveCriticalSection() 分布式算法（Ricart-Agrawala算法） 要求系统中所有事件都是全序的 1. 在一个进程P打算进入临界区R之前，向所有其他进程广播消息 临界区R名、进程号、时间印 2. 当一个进程P’收到消息后，做如下决定： 若P’不在临界区R中，也不想进入R，它就向P发送OK消息； 若P’已经在临界区R中，则不回答，并将P放入请求队列； 若P’也同时要进入临界区R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果P时间印小，则P发送OK消息;否则，不回答，并将P放入请求队列； 3. 当P收到所有的OK消息后，进入R。否则，等待。 4. 当P退出R时，如果存在等待队列，则取出请求者，向其发送OK消息。 分布式算法举例 举例： 共有0，1，2三个进程。 进程0，2申请进入临界区 分布式