分布式系统的同步

《分布式系统的同步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章分布式系统的同步中国科技大学软件学院丁箐主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁2主要内容3.1时钟同步3.2互斥3.3选举算法3.4原子性事务3.5分布式系统中的死锁33.1时钟同步分布式算法的特点相关信息散布在多个场地上每个进程只能基于本地信息做决定应避免因单点故障造成整个系统的失败不存在公共时钟或精确的全局时间4时钟同步问题例：makefile误差时间output.o：cc–Coutput.c5逻辑时钟计时器：石英晶体+计数器时钟偏差（clo

2、ckskew）逻辑时钟：相对时间物理时钟：真实时间“之前”关系:事件a在b之前出现，则aba为发送消息m，b为接收m，则ab具有传递性：ab,bc,则ac并发事件（concurrent）6Lamport算法对每一事件a，在所有进程中都认可给它分配一个时间值C(a）ifab;则C(a)

3、2）如何使各时钟之间保持同步。太阳日：连续的两次日中天的时间太阳秒：solar-day/86400平均太阳秒：如，格林威治时间9现实时钟铯原子钟：9192631770次跃迁=1秒TAI秒：国际原子时间UTC秒：世界时间（在TAI秒中加入闰秒）时间服务：WWV电台、GEOS卫星102010时钟同步算法如何与现实时钟同步如何使不同机器之间相互同步设机器时钟值Cp(t),t为UTC时间最大偏移率精确时钟：dC/dt=1快时钟：dC/dt〉1慢时钟：dC/dt<111Christian’s算法--逐步调整法

4、时间服务器，可接受WWV的UTC时间每隔δ/2ρ校准时间（允许误差δ，存在误差ρ）两个问题：时间决不能倒退,延迟假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。传播时间12Berkeley算法–主动式方法时间监控器定期查询其他机器时间计算出平均值通知其他机器调整时间13平均值算法–非集中式方法将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于T0+(i+1)R所有机器广播自己的时钟时间启动本地计时器收集在S时间

5、间隔中到达的其他机器广播的时间执行平均时间计算算法，得到新的时间值（取平均值，去掉两端值）14多个外部时间源法例：OSFDCE方法接受所有时间源的当前UTC区间去掉与其他区间不相交的区间将相交部分的中点作为校准时间时间15使用同步时钟最多一次消息提交每个消息携带一个ID和一个时间印ts（timestamp）服务器的表T中，记录每个连接C最近的时间印t如果到达的消息m，ts(m)

6、G的时间印从表T中清除对于具有新的ID的到达消息m,如果ts(m)

7、.5分布式系统中的死锁183.2互斥基本概念当一个进程使用某个共享资源，其他进程不允许对这个资源操作临界区（CriticalSection）：对共享资源进行操作的程序段基本方法：信号量、管程问题：死锁活锁饥饿19集中式算法（仿照单处理机系统的方法）协调者：确定那个进程可进入临界区通信量：3个消息：请求-许可-释放缺点：单点失败单协调者会成为执行的瓶颈CCC20WinThread临界区CreateMutex()WaitForSingleObject()ReleaseMutex()InitializeC

8、riticalSection()EnterCriticalSection()LeaveCriticalSection()21分布式算法（Ricart-Agrawala算法）要求系统中所有事件都是全序的1.在一个进程P打算进入临界区R之前，向所有其他进程广播消息<临界区R名、进程号、时间印>2.当一个进程P’收到消息后，做如下决定：若P’不在临界区R中，也不想进入R，它就向P发送OK消息；若P’已经在临界区R中，则不回答，并将P放入请求队列；若P’也同时要进入临界区R，