分布式系统之7、同步1.ppt

同步(1)物理时钟同步逻辑时钟同步选举算法互斥内容一、物理时钟同步1、基本概念一致的系统时间是分布式同步的基础事件的顺序关系问题的解决基础两个层面的时钟同步绝对同步（物理同步）物理时钟相对同步（逻辑同步）逻辑时钟物理时钟计算机系统的绝对时间UTC：一种国际统一的科学物理时间，称为统一协调时间。基本概念时钟精确度设UTC时间为t，机器的时间为C，则机器时钟的精确度可以用一个常数来表达：1-dC/dt 1+一般来说，由生产厂商规定，称为最大偏移率。同步间隔最坏的情况下，两个计算机的时钟以相反的方向偏离UTC时间，则要保证两个时钟误差不超过，就必须至少/(2)秒钟重新同步一次。时钟速率不正确时，机器时间与UTC之间的关系基本思想系统中有唯一一台时间服务器接收UTC时间，其他机器则必须与时间服务器同步。每台机器以不大于/(2)秒的周期定期向时间服务器发送消息询问当前时间时间服务器收到后发送消息告知当前时间CUTC发送者收到服务器消息后将时钟调整为CUTC2、Cristian时钟同步算法Cristian算法：从服务器得到当前时间问题时间回调将导致严重后果逐步调整时钟：即正常一个时钟中断将时钟加10毫秒，而需要慢下来时则一个中断加9毫秒，需要快时加11。传输延迟的问题测量估算法Cristian时钟同步算法思想主动式服务与Cristian算法中的被动式时间服务器相反过程服务器主动定期询问每台机器的时间服务器基于客户的回答，告知它们拨快或者拨慢3、Berkeley时钟同步算法Berkeley时钟同步算法Cristian算法和Berkeley算法集中式的算法。平均值算法非集中式算法将时间划分为固定长度的再同步间隔R第i次同步开始于T0+iR，结束于T0+(i+1)R每次同步间隔开始，每台机器广播自己的时间对于某一具体的机器，当所有的同步广播都到达后，它根据所有的时间执行某一平均算法得一新值，再根据新值调整时钟。思考：各机器计算的新值一样吗？4、平均值算法二、逻辑时钟同步1、基本概念许多应用中，并不严格需要所有机器都与UTC时间保持一致，而只需要所有机器时间相同就够了，即系统保持一个内部一致的时钟。这种时钟称为逻辑时钟。更进一步，很多问题中根本就不需要时间严格一致，而只是需要多个事件的发生顺序一致就可以。基本概念两个概念：先发生关系ab事件a先发生，然后b才发生如果a和b是同一个进程的两个事件，如果a在b之前发生，则ab为真如果a是一个进程发送消息的事件，b是另一个进程的接收消息事件，则ab为真并发事件如果x和y事件发生在两个互不交换消息的进程中，xy不真，yx也不真逻辑同步问题若干分布式进程协同工作对于任一事件a，为它分配一个所有进程都认可的时间值C(a)如果ab，则C(a)C(b)时钟值C必须保证始终前进，不能倒退，所以校正时间的操作是加上一个正值，而不是减去一个正值2、Lamport时间戳Lamport时间戳Lamport算法直接遵循先发生关系所有消息都必须携带发送者时钟的时间当接受者发现自己时钟比发送者的时钟早时，接受者将它的时钟调到一个比发送时间大1的值同一进程的每两个事件之间，必须至少滴答（即一个时钟中断）一次Lamport时间戳提供了一种对系统中所有事件完全排序的方法000612182430364248546000081624324048566472800010203040506070809010000612182430364248707600081624324048616977850010203040506070809010Lamport算法校正三个进程的不同时钟三、选举算法1、基本概念为什么要进行选举？许多分布式算法中需要一个进程来充当协调者、发起者或者其他特殊角色两种基本选举算法欺负算法环算法2、欺负算法基本思想比大小最大者获胜当选欺负算法过程当任何一个进程发现协调者不再响应请求时，它就发起一次选举P向所有编号比它大的进程发送一个ELECTION消息。如果无人响应，P获胜，成为协调者。如果有编号比它大的进程响应，则由响应者接管选举工作。P的工作完成。最后选举获胜者向所有进程发送选举获胜的消息，声明它成为协调者。欺负选举算法3、环算法基本过程所有进程按照物理或者逻辑的顺序组成一个逻辑的环当任何一个进程注意到协调者不工作时，它就自己构造一个带有它自己进程号的ELECTION消息，发给它的后继者如果后继者崩溃了，则跳过发给下一个接收者将自己的进程号加入消息中，继续传递消息。最后消息返回到选举发起者，它计算出协调者之后发送COORDINATOR消息宣布协调者消息环系统环一周后被删除环选举算法四、互斥基本概念分布式互斥解决分布式共享资源并发访问问题比单机系统互斥复杂算法集中式互斥算法分布式互斥算法令牌环算法1、集中式算法最简单的一种互斥算法基本过程：选举一个协调者任何一个进程要进入临界区，向协调者发送申请消息协调者根据临界区的使用情况同意或者拒绝申请者的请求协调者拒绝申请者的方式可以发送拒绝消息或者不应答，但都将请求放入队列中集中式互斥算法优点：保证了互斥的实现公平先来先服务没有进程会处于永远等待状态，不会出现饿死易于实现缺点：协调者是一个单故障点，如果协调者崩溃，则整个系统瘫痪协调者可能成为性能的瓶颈集中式算法2、分布式互斥算法基本过程：当一个进程想进入临界区时，它构造一个含有目标临界区名字、本进程号和当前时间的消息，发给所有进程。一个进程收到另一个进程的请求消息时，根据自己与目标临界区的状态关系反应：若接受者不在也不想进入临界区，发送OK消息接受者已经在临界区则不应答，只是把请求放入队列接受者亦欲进入临界区，则将收到的请求时间戳与它发送的请求时间戳比较，早的获胜进入。发送者一直等待至其他所有进程返回OK消息，之后进入临界区，使用完毕向队列中的进程发送OK消息，删除自己的任务。分布式互斥算法优点：实现了分布式互斥不会发生死锁或饿死不存在单个故障点缺点：反而有n个故障点，实际上比集中式算法差了n倍需要自己维护组成员清单，处理进入、离开组和崩溃进程的能力比较差总之，实际上比集中式算法更慢，更复杂，花费更高，而且更脆弱。意义：说明分布式算法至少可以实现。分布式互斥算法3、令牌环算法算法基本思想：构造一个逻辑环初始化时，进程0得到一个令牌，令牌绕环运行收到令牌的进程如果要使用临界区，则使用完临界区后再传递令牌不允许用同一个令牌进入另一个临界区。令牌环算法令牌环算法优点：不会发生饿死进程崩溃比较容易处理缺点：令牌丢失的情况，检测令牌丢失非常困难