第五章同步与互斥.ppt

第五章 同步和互斥 5.4互斥算法 选举算法 从进程集中选出一个进程执行特别的任务。大部分选举算法是基于全局优先级的，就是说给每个进程预先分配一个优先级，选举算法选择一个具有最高优先级的进程作为协调者。 Bully选举算法 P发送选举报文到所有优先级比它高的进程。 如果在一定时间内收不到任何响应报文，P赢得选举成为协调者。它向所有比它的优先级低的进程发送通知报文，宣布自己是协调者。 如果收到一个优先级比它高的进程的回答，P的选举工作结束。同时启动一个计时器，等待接收谁是协调者的通知报文，如果在规定时间内得不到通知报文，则它重新启动选举算法。 任何时候，一个进程可能从比它的优先级低的进程那儿接收到一个选举报文，它就给发送者回答一个响应报文，同时启动如上所述的相同的选举算法，如果选举算法已经启动，就不必重新启动。 第五章 同步和互斥 5.4互斥算法 选举算法 Bully选举算法实例： 第五章 同步和互斥 5.4互斥算法 选举算法 Bully选举算法实例： 第五章 同步和互斥 5.4互斥算法 选举算法 环选举算法： 在环选举算法中，所有进程以任意的顺序排列在一个单向环上，每个进程知道环上的排列情况，任何进程在环上有一个后继进程。 任何一个进程发现协调者失效时，它创建一个选举报文，将自己的进程号加入该报文中作为一个候选协调者，并把该选举报文传递到它的后继进程。 收到该选举报文的后继进程，也将自己的进程号加入到该选举报文中作为一个候选协调者。如果发送者发现其后继者失效，它会将选举报文传送给后继者在环中的下一个进程，或沿环的方向可以寻找到的下一个运行的进程。 第五章 同步和互斥 5.4互斥算法 选举算法 环选举算法： 如果一个进程接收到自己所创建的选举报文，它将该报文的类型由选举报文改为协调者报文。 这个协调者报文再绕环一周，这个报文用于通知每个进程协调者是谁，组成新环的成员有那些。如果进程号大的进程具有高的优先级，那么具有最大进程号的进程就是协调者； 第五章 同步和互斥 5.4互斥算法 自稳定算法 自稳定系统：一个系统，如果无论它的初始状态是什么，总是能在有限的步骤内达到一个合法的状态，那么它是自稳定的。 一个系统S，如果它满足以下两个性质，那么它关于谓词P是自稳定的。 终止性(closure)。P在S的执行下是终止的(closed)，也就是说，一旦P在S中被建立，它就不能被再被证明为假。 收敛性(convergence)。从任意全局状态开始，S能保证在有限次状态转换内达到一个满足P的全局状态。 第五章 同步和互斥 5.4互斥算法 自稳定算法 Dijkstra自稳定系统：有一个特别的进程，它对于状态转换使用独特的特权，其他进程使用另一个特权。给定n个k状态进程，k﹥n，标号分别为P0到Pn-1。P0是特别的进程，其他进程Pi(0＜i≤n-1）是一样的。 Pi的状态转换如下： Pi≠Pi-1 ? Pi:=Pi-1, 0＜i≤n-1 P0的状态转换如下： P0=Pn-1 ? P0:=(P0+1) mod k Dijkstra自稳定系统实例：n=3，k=4 第五章 同步和互斥 5.2 同步机构 分布式系统中同步机构的作用 同步点：为了达到合作，各个进程在执行的过程中必须存在若干点，超过这些点时，一个进程在另一个进程执行完某一活动前不能继续执行，这些点称为这两个进程之间的同步点。 分布计算系统中共享资源的两类：一类是各进程可以同时访问的，如中央处理机(允许多个进程交叠使用一个处理机)、只读文件和不允许修改的存放子程序和数据的主存区域等；另一类是不允许多个进程同时访问的，每次只允许一个进程使用，如大多数外部设备(如打印机)、可写的文件以及主存中可修改的区域等。同步机构在互斥控制中的作用是对活动的执行进行排序。 第五章 同步和互斥 5.2 同步机构 分布式系统中同步机构的作用 一致状态：一个计算系统应该在所有时间内满足一定的外部规定或约束，如果一个计算系统确实在所有时间内满足了一定的外部规定或约束，这时我们称系统状态是一致的。同步机构的目的就是给进程提供某种手段，使系统保持一致状态。 分布计算系统的计算方式分成三种 ： 完全复制的计算。任何操作所激发的每个活动必须由所有的消费者共同处理，要求所有的活动均应完成。这时同步机构的目的是保证消费者处理活动的次序必须相同。 第五章 同步和互斥 5.2 同步机构 分布计算系统的计算方式分成三种 ： 完全分割的计算。一个操作所激发的不同活动由不同的消费者分别独自处理。在这种情况下，同步机构的目的是保证所有相互干扰的活动成为有序的，使得该操作保持原子性(要么完成操作，要么干脆不发生)。 分割和部分复制