分布式系统的同步.pptx

第3章分布式系统的同步中国科技大学软件学院丁箐

2主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁

3主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁

相关信息散布在多个场地上每个进程只能基于本地信息做决定应避免因单点故障造成整个系统的失败不存在公共时钟或精确的全局时间分布式算法的特点3.1时钟同步

时间output.o：cc–Coutput.c例：makefile误差时钟同步问题

逻辑时钟计时器：石英晶体+计数器时钟偏差（clockskew）逻辑时钟：相对时间物理时钟：真实时间“之前”关系:?事件a在b之前出现，则a?ba为发送消息m，b为接收m，则a?b具有传递性：a?b,b?c,则a?c并发事件（concurrent）

对每一事件a，在所有进程中都认可给它分配一个时间值C(a）ifa?b;则C(a)C(b)?a,bC(a)?C(b)C是递增的校正算法a?b，ifC(b)C(a),则C(b)=C(a)+1Lamport算法

时间慢快慢快020103050604Lamport算法

物理时钟与现实时钟如何用现实世界的时钟将它们同步起来；如何使各时钟之间保持同步。太阳日：连续的两次日中天的时间太阳秒：solar-day/86400平均太阳秒：如，格林威治时间

现实时钟铯原子钟：9192631770次跃迁=1秒TAI秒：国际原子时间UTC秒：世界时间（在TAI秒中加入闰秒）时间服务：WWV电台、GEOS卫星1020

时钟同步算法11如何与现实时钟同步如何使不同机器之间相互同步设机器时钟值Cp(t),t为UTC时间最大偏移率精确时钟：dC/dt=1快时钟：dC/dt〉1慢时钟：dC/dt1

Christian’s算法--逐步调整法时间服务器，可接受WWV的UTC时间每隔δ/2ρ校准时间（允许误差δ，存在误差ρ）两个问题：时间决不能倒退,延迟假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。传播时间

Berkeley算法–主动式方法01时间监控器定期查询其他机器时间计算出平均值通知其他机器调整时间02

平均值算法–非集中式方法14将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于T0+(i+1)R所有机器广播自己的时钟时间启动本地计时器收集在S时间间隔中到达的其他机器广播的时间执行平均时间计算算法，得到新的时间值（取平均值，去掉两端值）

多个外部时间源法15例：OSFDCE方法接受所有时间源的当前UTC区间去掉与其他区间不相交的区间将相交部分的中点作为校准时间时间

使用同步时钟最多一次消息提交每个消息携带一个ID和一个时间印ts（timestamp）服务器的表T中，记录每个连接C最近的时间印t如果到达的消息m，ts(m)t,则拒绝m服务器要一直保存一个全局变量G=CurrentTime–MaxLifetime–MaxClockSkew所有G的时间印从表T中清除对于具有新的ID的到达消息m,如果ts(m)G则拒绝m,否则，接受m按照一定时间间隔?T，定期地将G写入磁盘。当系统重启后，G’=G+?T

17当客户读取一个副本到缓存时，设置一个租期（lease）在租期过期之前，客户可更新副本，重续租期如果已经过期，缓存中的副本失效基于时钟的缓存一致性当客户修改文件时，只需将所有没有到期的缓存副本设为无效如果某个客户崩溃，则等待直到该客户的租期过期改进的一致性协议使用同步时钟

01时钟同步互斥选举算法原子性事务分布式系统中的死锁02主要内容

19当一个进程使用某个共享资源，其他进程不允许对这个资源操作基本概念对共享资源进行操作的程序段临界区（CriticalSection）：信号量、管程基本方法：死锁活锁饥饿问题：3.2互斥

集中式算法（仿照单处理机系统的方法）协调者：确定那个进程可进入临界区通信量：3个消息：请求-许可-释放缺点：单点失败单协调者会成为执行的瓶颈CCC

CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeCriticalSection()EnterCriticalSection()LeaveCriticalSection()0102WinThread临界区

分布式算法（Ricart-Agrawala算法）要求系统中所有事件都是全序的1.在一个进程P打算进入临界区R之前，向所有其他进程广播消息临界区R名、进程