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

第六章 同步 时钟同步 逻辑时钟 全局状态 选举算法 互斥 分布式事务 分布式系统中的死锁 时钟同步 分布式系统中，不存在公共时钟或精确的全局时间 当每台机器都有自己的时钟时，一个发生较晚的事件可能被标上较早的时间 例子：Unix中的make程序 物理时钟 平均太阳日的计算 现实时钟 铯原子钟：9192631770次跃迁=1秒 TAI秒：国际原子时间 UTC秒：统一协调时间（在TAI秒中加入闰秒） 时间服务：WWV电台、GEOS卫星 时钟同步算法 当时钟以不同的速率滴答时，时钟时间与UTC之间的关系：当UTC时间为t时，机器上的时间为Cp(t)，理想情况是Cp(t)=t,即dC/dt=1. 1-p=dC/dt=1+p（p为最大偏移率） 为保证每两个时钟间的差值不超过a,则时钟必须至少每a/2p秒重新同步一次 Cristian算法 适合只有一台时间服务器的情况，可接收WWV的UTC时间 Cristian算法 不能简单接受CUTC 时间不能倒退，须逐步修正 假设：每秒产生100次中断，每次中断将时间加10毫秒 若调慢时钟，中断服务程序每次只加9毫秒； 若加快时钟，则加11毫秒。 存在延迟 Berkeley 算法 time daemon 向所有其他机器发送自己的时间，并询问其时钟值 其他机器应答 time daemon计算出平均值，通知其他机器如何调整时钟 平均值算法 非集中式算法 时间间隔[ T0+iR, T0+(i+1)R ] 在每次时间间隔开始，每台机器广播自己的当前时间 之后启动本地计时器，搜集时间间隔S内到达的所有时间广播，计算时间值 平均值 去掉若干个最低值和最高值？ 给每个消息加上传输时间的估计值 逻辑时钟Lamport Timestamps 时间戳（ Time-Stamping）的算法： 网络上的每个系统（站点）维护一个计数器，起时钟的作用 每个站点有一个数字型标识,消息的格式为（m,Ti,i）,m为消息内容， Ti为时间戳， i为站点标识 当系统发送消息时，将时钟加一 当系统j接收消息时，将它的时钟设为当前值和到达的时间戳这两者的最大者加一 在每个站点，时间的排序遵循以下规则 对来自站点i的消息x和站点j的消息y,如果 TiTj或 Ti=Tj，且ij 则说消息x早于消息y 全局状态（Global State） (1) 操作系统或任何进程都不可能知道分布式系统中所有进程的当前状态 只能通过消息接收到状态信息，它只代表过去某时刻远程进程的状态 分布式系统的本质所造成的时间延迟使与并发有关的所有问题都复杂了 全局状态（Global State） (2) 一致的切口 不一致的切口 选举算法 选择一个进程作为协调者、发起者或其他特殊角色，一般选择进程号最大的进程（假设每个进程都知道其他进程的进程号，但不知道是否还在运行） 目的：保证在选举之行后，所有进程都认可被选举的进程 相关算法： Bully算法 环算法 无线环境下的选举算法 大型系统中的选举算法 Bully算法 当进程P注意到需要选举一个进程作协调者时： 向所有进程号比它高的进程发ELECTION消息 如果得不到任何进程的响应，进程P获胜，成为协调者 如果有进程号比它高的进程响应，该进程接管选举过程，进程P任务完成 当其他进程都放弃，只剩一个进程时，该进程成为协调者 一个以前被中止的进程恢复后也有选举权 Bully算法 进程 4 启动选举 进程 5 和进程 6 响应，接管选举，成为协调者 Bully算法 Process 6 tells 5 to stop Process 6 wins and tells everyone 环算法 不使用令牌 按进程号排序，每个进程都知道自己的后继者 当进程P注意到需要选举一个进程作协调者时： 就创建一条包含该进程号的ELECTION消息，发给后继进程 后继进程再将自己的进程号加入ELECTION消息，依次类推 最后回到进程P，它再发送一条COORDINATOR消息到环上，包含新选出的协调者进程（进程号最大者）和所有在线进程 环算法 无线环境下的选举算法 无线环境下的选举算法 无线环境下的选举算法 大型系统中的选举算法 可能需要选举多个节点（如超级节点） 要求： 一般节点访问超级节点的延时要低 超级节点平均地分布在覆盖网络上 相对于覆盖网络中的所有节点，应有一部分预定义的超级节点 每个超级节点不应为超过固定数目的一般节点服务 使用推动力在二维空间移动令牌 互 斥 基于令牌的解决方案 拥有令牌者获得使用资源的权限 可以避免饿死和死锁 令牌可能会丢失 基于许可的解决方案 获得其它进程的许可来使用资源 集中式算法 使用协调者 进程1请求协调者允许它进入临界区，得到同意 进程2也请求协调者允许它进入临界区，协调者不应答 当进程1退出临界区时