04-协调和协定

《04-协调和协定》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章协调和协定第4章协调和协定简介分布式互斥选举组播通信共识和相关问题小结简介构造分布式系统的主要动力:资源共享和协作分布式系统中的进程需要协调动作和对共享资源达成协定分布式中的协作互斥选举组播可靠性和排序语义进程间的协定共识和拜占庭协定简介故障模型良性故障随机故障Internet现状网络分区非对称路由连接的非传递性崩溃的路由器简介通道假设进程通过可靠的通道连接进程假设进程仅在崩溃时出现故障故障检测器不可靠的故障检测器产生值:Unsuspected和Suspected可靠的故障检测器产生值:Unsuspected和Failed简介不可靠故障检测器的实现示例每个

2、进程以周期T通告自己正常消息检测器以时间D作为最大消息传输延迟若检测器在时间T+D内没有收到进程的通告消息，则设定此进程的状态为“Suspected”时间参数T、D可动态设置第4章协调和协定简介分布式互斥选举组播通信共识和相关问题小结分布式互斥目的仅基于消息传递，实现对资源的互斥访问。假设异步系统无故障进程可靠的消息传递执行临界区的应用层协议enter()//进入临界区——若必要，可以阻塞进入resourceAccesses()//在临界区访问共享资源exit()//离开临界区——其它进程现在可以进入分布式互斥基本要求安全性在临界区内一次最多有一个进程可以执行活

3、性进入和离开临界区的请求最终成功执行→顺序如果一个进入临界区的请求发生在先，则进入临界区时仍按此顺序。分布式互斥算法的性能评价带宽消耗在每个enter和exit操作中发送的消息数客户延迟-进程进入、退出临界区的等待时间由enter和exit操作引起的延迟同步延迟-进程切换所消耗的时间一个进程离开临界区和下一个进程进入临界区之间的延迟。分布式互斥中央服务器算法构架服务器1.请求令牌请求队列2.释放令牌3.授予令牌42p4p3p2p1分布式互斥满足安全性和活性要求，但不满足顺序要求。性能-带宽消耗enter():２个消息，即请求消息和授权消息exit():1个消息，

4、即释放消息-客户延迟消息往返时间导致请求进程的延迟时间-同步延迟1个消息的往返时间-性能瓶颈服务器分布式互斥基于环的算法构架pnp2p3p4令牌p1分布式互斥满足安全性和活性要求，但不满足顺序要求。性能-带宽消耗由于令牌的传递，会持续消耗带宽-客户延迟Min:0个消息，正好收到令牌Max:N个消息，刚刚传递了令牌-同步延迟Min:1个消息，进程依次进入临界区Max:N个消息，一个进程连续进入临界区，期间无其他进程进入临界区分布式互斥使用组播和逻辑时钟的算法基本思想-进程进入临界区需要所有其它进程的同意组播+应答-并发控制采用Lamport时间戳避免死锁分布式互斥

5、算法伪码初始化:state:=RELEASED;为了进入临界区state:=WAITED;组播请求给所有进程;T:=请求的时间戳;Waituntil(接收到的应答数=(N－1));state:=HELD;在pj(i≠j)接收一个请求if(state=HELDor(state=WANTEDand(T,pj)<(Ti,pi)))then将请求放入pi队列,不给出应答;else马上给pi应答;endif为了退出临界区;state:=RELEASED;对已进入队列的请求给出应答;分布式互斥示例p1、p2并发请求进入临界区p334应答3441414134p1

6、p2应答应答分布式互斥满足安全性、活性和顺序要求。性能-带宽消耗enter():2(N－1)，即(N－1)个请求、(N－1)个应答-客户延迟1个消息往返时间-同步延迟1个消息的传输时间分布式互斥Maekawa投票算法基本思想-进程进入临界区需要部分其它进程的同意-选举集Vi{p1,p2,…,pn}piViViVj

7、Vi

8、=K,Tobefair,K每个进程pj包括在选举集Vi中的M个集合中，M=K分布式互斥算法伪码初始化:state:=RELEASED;voted:=FALSE;pi为了进入临界区state:=WAITED;将请求组播给vi中的所有进程

9、;Waituntil(接收到的应答数=K);state:=HELD;在pj(i≠j)接收来自pi的请求：if(state=HELDorvoted=TRUE)将来自pi的请求放入队列,不予应答;else将应答发送给pi;voted:=TRUEendif分布式互斥Maekawa算法会产生死锁三个进程p1、p2和p3，且V1={p1,p2}，V2={p2,p3}，V3={p3,p1}。若三个进程并发请求进入临界区，考虑下列情况：1.p1应答了自己，但延缓p2；2.p2应答了自己，但延缓p3；3.p3应答了自己，但延缓p1。p1p2p3Voted=TRUEVoted=T

10、RUEVoted=TRU