中国科学技术大学：《高级操作系统 Advanced Operating System》课程教学资源（PPT课件讲稿）分布式系统的同步（3.3-3.5）

●●● ●●●● ●●●●● ●●●● 33选举算法 ●●●0● ●●●0 ●许多分布式算法需要一个进程充当协调者、发 起者、排序者或者其他特定的角色 ●例如:集中式互斥算法中的协调者进程 ●通常,选择哪个进程充当协调者并不重要,重 要的是要有进程负责,并且需要所有进程的 致认可。 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 2 3.3 选举算法 ⚫ 许多分布式算法需要一个进程充当协调者、发 起者、排序者或者其他特定的角色 ⚫ 例如：集中式互斥算法中的协调者进程 ⚫ 通常，选择哪个进程充当协调者并不重要，重 要的是要有进程负责,并且需要所有进程的一 致认可

●●● ●●●● ●●●●● ●●●● 最大进程号 ●●●0● ●●●0 ●如果所有进程的地位都相同,没有特性上的区 别,就无法选择其中一个为特殊进程; ●假设每个进程都有一个特殊的号,通常选举算 法总是找拥有最大号的进程,将它指定为协调 者,不同的选举算法在选举时采用不同的方法 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 3 最大进程号 ⚫ 如果所有进程的地位都相同，没有特性上的区 别，就无法选择其中一个为特殊进程； ⚫ 假设每个进程都有一个特殊的号，通常选举算 法总是找拥有最大号的进程，将它指定为协调 者，不同的选举算法在选举时采用不同的方法

●●● ●●●● ●●●●● ●●● 选举的目的 ●●●0● ●●●0 ●我们假设每个进程都知道所有其他进程的进程 号,但不知道目前哪些进程在工作,哪些进程 不在工作; ●选举算法的目的是在选举开始后,确保在所有 进程都同意的基础上选出协调者 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 4 选举的目的 ⚫ 我们假设每个进程都知道所有其他进程的进程 号，但不知道目前哪些进程在工作，哪些进程 不在工作； ⚫ 选举算法的目的是在选举开始后，确保在所有 进程都同意的基础上选出协调者

●●● ●●●● ●●●●● ●●●● 两个选举算法 ●●●0● ●●●0 欺负(Buy)算法 环算法 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 5 两个选举算法 ⚫ 欺负（Bully）算法 ⚫ 环算法

●●● ●●●● ●●●●● ●●●● 331欺负(Buly)算法 ●●●0● ●●●0 Buy算法由 Garcia-Mona在1982年提出 当一个进程P发现协调者不再响应请求时, 它就发起选举。进程P负责选举如下 1.P向所有进程号比它大的进程发送选举 ( ELECT|ON)消息; 2.若无人响应,P获胜成为协调者; 3.若有进程号比它大的进程响应,响应者接管,P 的工作完成。 由于总是进程号最大的进程获胜,故该算法 命名为欺负算法 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 6 3.3.1 欺负（Bully）算法 ⚫ Bully算法由Garcia-Molina在1982年提出 ⚫ 当一个进程P发现协调者不再响应请求时， 它就发起选举。进程P负责选举如下： 1. P向所有进程号比它大的进程发送选举 （ELECTION）消息； 2. 若无人响应，P获胜成为协调者； 3. 若有进程号比它大的进程响应，响应者接管，P 的工作完成。 ⚫ 由于总是进程号最大的进程获胜，故该算法 命名为欺负算法

●●● ●●●● ●●●●● ●●●● 欺负(Buly)算法 ●●●0● ●●●0 ●在某一时刻,一个进程只能从进程号比它小的进程那 里得到一个选举( ELECTION)消息,当它到达时, 接收者就发送回OK消息,表明它的存在并接管,然 后接收者主持选举(除非它正在主持别的选举)。 ●除了一个进程外即进程号最大的进程,其余进程都会 放弃选举,这个进程就是新的协调者,它将选举获胜 的消息发送给所有进程,告之自己是新的协调者。 若一个进程刚刚崩溃过,但又很快恢复,它主持选举, 若它刚好是当前运行进程中号最大的,它就会获得选 举的胜利,从而接管协调者的工作。 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 7 欺负（Bully）算法 ⚫ 在某一时刻，一个进程只能从进程号比它小的进程那 里得到一个选举（ELECTION）消息，当它到达时， 接收者就发送回OK消息，表明它的存在并接管，然 后接收者主持选举（除非它正在主持别的选举）。 ⚫ 除了一个进程外即进程号最大的进程，其余进程都会 放弃选举，这个进程就是新的协调者，它将选举获胜 的消息发送给所有进程，告之自己是新的协调者。 ⚫ 若一个进程刚刚崩溃过，但又很快恢复，它主持选举， 若它刚好是当前运行进程中号最大的，它就会获得选 举的胜利，从而接管协调者的工作

●●● ●●●● ●●●●● ●●● 欺负(Buly)算法举例 ●●●0● ●●●0 ●一组由0~7号共8个进程组成,开始7号进程是 协调者,但是它突然发生了故障,进程4第 个注意到这一点,所以它向所有比它进程号大 的进程,即进程5、6、7发送选举消息 选举 选举 选举 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 8 欺负（Bully）算法举例 ⚫ 一组由0~7号共8个进程组成，开始7号进程是 协调者，但是它突然发生了故障，进程4第一 个注意到这一点，所以它向所有比它进程号大 的进程，即进程5、6、7发送选举消息

●●● ●●●● ●●●●● ●●●● ●●●0● ●●●0 ●进程5和6接收消息后发送回OK。进程4接收到 第一个应答时就知道自己已经结束了,因为已 经有比它进程号大的进程即将接管它的工作成 为新的协调者,它就等待着看谁将在选举中获 胜。 A-( ok 以前的协调(b) 陈香兰@2007.3 者崩溃

陈香兰@2007.3.21 分布式系统同步（续） 9 ⚫ 进程5和6接收消息后发送回OK。进程4接收到 第一个应答时就知道自己已经结束了，因为已 经有比它进程号大的进程即将接管它的工作成 为新的协调者，它就等待着看谁将在选举中获 胜

●●● ●●●● ●●●●● ●●●● ●●●0● ●●●0 ●进程5和6都主持选举,每个进程仅把消息发送 给比自己进程号大的进程 选举 选举 选举 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 10 ⚫ 进程5和6都主持选举，每个进程仅把消息发送 给比自己进程号大的进程

●●● ●●●● ●●●●● ●●●● ●●●0● ●●●0 ●进程6向进程5发OK消息,进程5收到OK消息 后停止选举,而这个时候进程6知道进程7已经 死了,所以,它将是获胜者 ok 陈香兰@2007.3 分布式系统同步

陈香兰@2007.3.21 分布式系统同步（续） 11 ⚫ 进程6向进程5发OK消息，进程5收到OK消息 后停止选举，而这个时候进程6知道进程7已经 死了，所以，它将是获胜者