分布式系统与WEB服务(2).ppt

第三章分布式系统的同步和进程3．1时钟同步1．逻辑时钟先看一个例子:Lamport的算法以”先于”关系为基础每个消息都携带它的发送时间当它到达目的地时如果目的地的时间早于它的发送时间那么就把目的地的时间向前拔至少要比发送时间大1个单位.该算法解决了全局时钟问题它的条件就是两个相关事件之间必须至少相差一个时间2．时钟同步算法逻辑时钟只给出事物的相对时间与真实时间并不对应故要引入外部物理时钟常用的时钟同步算法:①克里司帝安(CRISTIAN)算法具有国家标致时间接收器的机器注意:调整的方法通过调节单位时间内的中断的时间来逐步完成时钟的调整.②伯克利算法计算平均时间它是一个集中式算法不能在大规模的分布式系统中使用原理:定期轮询每台机器的时间由结果计算平均时间各机器依此调整时间.3．同步时钟的具体使用①至多一次消息传送消息的时间戳比存储的时间戳的值早就拒绝接受该消息②基于时钟的缓冲存储器（CACHE）的一致性使用CACHE会出现一致性问题原解决的方法:区分读写缓存现在可用同步时钟来解决。即通过提供有效期（利用有效的租约）来控制CACHE一致性问题。3.2互斥操作②分布式算法算法的条件:系统中的事件必须有全局的顺序算法的工作过程如下:当一个进程要进入临界区时它构造一条包括临界区名、进程号和当前时间的请求消息然后把该消息广播给其他的所有进程。这里假设消息的发送是可靠的。当一个进程收到请求后根据它的状态采取相应的动作：(1)当接收者不在临界区并且也不想进入临界区就应答发送者OK消息。(2)如果接收者已经在临界区中它不回答．仅仅把请求加入队列。(3)如果接收者不在临界区但它也想进入临界区就要将收到消息的时间戳和它广播消息的时间戳比较.如果到来的消息时间戳早接收者回答发送者OK消息；反之接收者把到来的请求加入队列不回答.在发完进入临界区请求后进程将等待所有的允许消息一旦得到许可就可进入临界区当退出时向队列中的所有进程发OK消息并将它从队列中删除。所有进程都要参与决定是否进入临界区若有进程不能做算法将出错。由于所有进程都要参加算法所以比集中式算法慢复杂开销大。改进算法：不需所有进程同意部分回答OK即可③令牌环算法进程只有拥有令牌时才能进入临界区一个进程从相邻的进程收到令牌时先检查自己是非要进入临界区;如果要就进入否则就将令牌传递给下一个进程.缺点:令牌可能丢失且检测困难一个要进入临界区的进程最差情况下要等待其他进程进入和退出临界区所用时间总和④三种算法的特点比较集中式算法简单、高效每次进入和离开临界区只需3次消息传递：请求、许可；释放分布式算法中n个进程需要(n-1)个请求和(n-1)个许可总共要2(n—1)个消息。在令牌环算法中所需的消息数是不固定的。如果每个进程都要进入临界区那么每个令牌都有一次进人和退出平均每次进入有—个消息传递；如果令牌被一个进程占有很长时间那么进入临界区需要的消息就不确定。进程从它发出进入临界区的请求到它进入临界区的时间延迟在三个算法中是不同的当临界区很短并且使用频率很低时进入临界区时间延迟的决定因素是进人临界区的控制机制．当临界区很长并且使用的频率很高时决定因素在于等待时间消息数就能说明这一点。这三种算法出现故障时都会有很大影响要避免系统的崩溃须注意:在容错系统中次三种算法都不适用.3.3选举算法1.霸道算法该算法提出。当一个进程P注意到管理员不再对请求作出反应时它就开始选举．进程P执行下列步骤：(1)向所有进程号比它大的进程发送ELECTION消息；(2)如果没有进程响应进程P成为管理员；(3)如果有进程响应该响应进程成为管理员P结束选举。注意：一个进程只能从号码比它小的进程处得到一个选择消息2.环形算法这个算法使用环但不是令牌环。这里假定所有的进程都是有序号的即每个进程都知道它的后继进程。当一个进程发现管理员不能工作时它把包含其进程号的ELECTION消息发给它的后继进程；接收消息的进程再向后继进程发送ELECTION消息。如果接收进程没有反应发送消息的进程便向下一个进程发消息。每一次发送ELECTION进程都要将自己的进程号加入消息。最后第一个发出该选举（ELECTION）消息进程收到该消息再将其转换为协调（COORDINATOR）消息后再循环一周