高级操作系统课件-第六章同步.ppt

《高级操作系统课件-第六章同步.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章同步时钟同步逻辑时钟全局状态选举算法互斥分布式事务分布式系统中的死锁时钟同步分布式系统中，不存在公共时钟或精确的全局时间当每台机器都有自己的时钟时，一个发生较晚的时间可能被标上较早的时间例子：Unix中的make程序物理时钟平均太阳日的计算太阳日：连续的两次日中天的时间太阳秒：solar-day/86400平均太阳秒：格林威治时间现实时钟铯原子钟：9192631770次跃迁=1秒TAI秒：国际原子时间UTC秒：统一协调时间（在TAI秒中加入闰秒）时间服务：WWV电台、GEOS卫星时钟同步算法当时钟以不同的速率滴答时，时钟时间与UTC之间的关系：当UTC时间为t

2、时，机器上的时间为Cp(t)，理想情况是Cp(t)=t,即dC/dt=1.1-p<=dC/dt<=1+p为保证每两个时钟间的差值不超过a,则时钟必须至少每a/2p秒重新同步一次Cristian算法适合只有一台时间服务器的情况，可接收WWV的UTC时间Cristian算法不能简单接受CUTC时间不能倒退，须逐步修正假设：每秒产生100次中断，每次中断将时间加10毫秒若调慢时钟，中断服务程序每次只加9毫秒；若加快时钟，则加11毫秒。存在延迟Berkeley算法timedaemon向所有其他机器发送自己的时间，并询问其时钟值其他机器应答timedaemon计算出平均值，通

3、知其他机器如何调整时钟平均值算法非集中式算法时间间隔[T0+iR,T0+(i+1)R]在每次时间间隔开始，每台机器广播自己的当前时间之后启动本地计时器，搜集时间间隔S内到达的所有时间广播，计算时间值平均值去掉若干个最低值和最高值？给每个消息加上传输时间的估计值逻辑时钟LamportTimestamps时间戳（Time-Stamping）的算法：网络上的每个系统（站点）维护一个计数器，起时钟的作用每个站点有一个数字型标识,消息的格式为（m,Ti,i）,m为消息内容，Ti为时间戳，i为站点标识当系统发送消息时，将时钟加一当系统j接收消息时，将它的时钟设为当前值和到达的时

4、间戳这两者的最大者加一在每个站点，时间的排序遵循以下规则对来自站点i的消息x和站点j的消息y,如果Ti

5、态和正在传输中的消息选举算法选择一个进程作为协调者、发起者或其他特殊角色，一般选择进程号最大的进程（假设每个进程都知道其他进程的进程号，但不知道是否还在运行）目的：保证在选举之行后，所有进程都认可被选举的进程相关算法：Bully算法环算法无线环境下的选举算法大型系统中的选举算法Bully算法当进程P注意到需要选举一个进程作协调者时：向所有进程号比它高的进程发ELECTION消息如果得不到任何进程的响应，进程P获胜，成为协调者如果有进程号比它高的进程响应，该进程接管选举过程，进程P任务完成当其他进程都放弃，只剩一个进程时，该进程成为协调者一个以前被中止的进程恢复后也有

6、选举权Bully算法进程4启动选举进程5和进程6响应，接管选举，成为协调者Bully算法Process6tells5tostopProcess6winsandtellseveryone进程6响应进程5的消息，接管选举，进程6成为协调者，通知所有进程环算法不使用令牌按进程号排序，每个进程都知道自己的后继者当进程P注意到需要选举一个进程作协调者时：就创建一条包含该进程号的ELECTION消息，发给后继进程后继进程再将自己的进程号加入ELECTION消息，依次类推最后回到进程P，它再发送一条COORDINATOR消息到环上，包含新选出的协调者进程（进程号最大者）和所有在线

7、进程环算法无线环境下的选举算法不能保证其消息传送是可靠的以及网络拓扑结构不改变源节点向其相邻节点发送ELECTION消息开始一个选举当节点第一次收到ELECTION消息时，会将发送者作为其父节点，然后将ELECTION消息发给其相邻节点（父节点除外）。等到其他节点的确认消息都收到后，再向父节点确认（消息中包含资源容量）。而从某个节点再次收到ELECTION消息时，只是确认。无线环境下的选举算法无线环境下的选举算法大型系统中的选举算法可能需要选举多个节点（如超级节点）要求：一般节点访问超级节点的延时要低超级节点平均地分布在覆盖网络上相对于覆盖网络中的所有节点，应有