分布式系统与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）消息后，再循环一周,通知谁是管理员，谁是组成员，这时消息包中进程号最高的进程将成为管理员。当这个消息循环一周后，由发送进程把它从网上清除。
图中2和5都发现7失效，分别建立选举消息，两条消息都沿环运行，结果是一样的，只是浪费了带宽。3．4线程1)分配器／工作者模型
有一个