13 第九章 网络与分布式操作系统（2）.pptx

第1页：9.5 事件排序

• 9.5.1先发生关系(用符号“→”表示):
• 如果A和B是同一进程内部的事件,而且A在B前执行,则有A→B;
• 如果A是一个由某一进程发送消息的事件,B是由另一进程接收该消息的事件,则有A→B。
• 如果A→B且B→C,则有A→C。
• 先发生关系是非自反的偏序关系;
• 如果两个事件没有关系→，则两个事件可以并行；
• 如果A、B分别是进程P、Q中的两个事件,且有A→B,则P进程中A之前的事件与Q进程中B之后的事件不能并行。

第2页：9.5 事件排序（续）

9.5.1先发生关系进程时间与事件描述Pp1p0p2p3p4Qq1q0q2q3q4Rr1r0r2r3r4Ss1s0s2s3s4

第3页：9.5.2 全序关系

全序关系

基于时间戳(timestamp)的方法将每个系统事件都打上一个“时间戳”:对每一个事件A和B,如果A→B,则A的时间戳应小于B的时间戳。

时间戳定义在每个进程Pi内部定义一个相关联的逻辑时钟LCi,初值为0;

带有时间戳的消息定义

(m, Tj, j)含义:“进程Pj发送消息m”这一事件发生时,进程Pj的逻辑时钟LCj=Tj .

第4页：9.5.2 全序关系（续）

• 全序关系的实现：
  • 进程Pi某事件发生前, LCi=LCi+
• 1.该事件的时间戳＝LCi .
  • 进程Pi接收到一个消息(m, Tj, j),则: LCi=max{LCi, Tj}+1
  • 对于消息(x, Ti, i)和(y, Tj, j),如果Ti<Tj || ((Ti=Tj)&&i<j)则称x在y之前。

第5页：9.5.2 全序关系（续3）

Pp1p0p2p3p4Qq1q0q2q3q4Rr1r0r2r3r4Ss1s0s2s3s4事件与逻辑时间s4s3s2s1s0r4r3r2r1r0q4q3q2q1q0p4p3p2p1p0事件5432111109818732176541逻辑时间

第6页：9.6 进程互斥

• 假设(Distributed Management Environment :DME)
  • 系统包含n个处理机;
  • 每个处理机中仅有一个进程;
  • 每个进程有一个临界区需要互斥。
• 必要条件如果进程Pi正在它的临界区域内执行,则在这个临界区域内没有其它进程Pj执行。
• 三个算法确保执行进程在其临界区内互斥:
  • 集中算法
  • 分布算法
  • 标志传递算法

第7页：9.6 进程互斥（续）

• 9.6.1集中方式集中方式处理过程:
• 指派一个协调者进程(coordinator),负责控制对于临界区的进入;
• 每一个要求进入临界区的进程都必须发送一个请求给协调者进程;
• 协调者决定哪个进程可以进入临界区域,之后给它发送应答消息;
• 当进程收到协调者进程的应答消息后,才能进入自己的临界区。

第8页：9.6.1 集中方式

• 当一个进程退出临界区时,发送一个释放信号给协调者进程,然后再继续运行;
• 无死锁;若协调者进程公平(如FCFS),无饿死;
• 每次进入临界区需要三个消息：
  • 请求:进程;
  • 应答:协调者;
  • 释放:进程。

第9页：9.6.2 分布方式

• (Richard/Agrawala)全分布互斥算法:
• ①进程Pi想进入临界区,产生一个时间戳TSi,发消息request (Pi ,TSi,i)给所有其它进程;
• ②进程Pj接收到request消息后,可能立即,也可能延迟回复reply消息:
  • Pj在临界区,延迟回复;
  • Pj不想进入临界区,立即回复;
  • Pj想进入、但还未进入临界区,比较两者的时间戳:若(TSi,i)<(TSj,j),则立即回复;否则延迟回复。
• ③当进程Pi接收到所有进程回复的reply消息后,可以进入临界区;
• ④进程Pi离开临界区后,给所有延迟回复的进程发reply消息。

第10页：9.6.2分布方式DME例子

9.6.2分布方式DME例子:系统有p1,p2,p3, p1,p3想进入其临界区域。p1发送request (1, 15)给p2和p3 ,p3发送request (3, 6)给p1和p2 ;p1p3p2replyreplyP3接收到两个reply,进入临界区。延迟应答P1P2接收到P3的延迟reply后,进入临界区。request(1, 15)request(1, 15)request(3, 6)request(3, 6)(立即)reply(P3退出临界区后)reply

第11页：9.6.2 分布方式

• 分布方式优点
• 确保无死锁;
• 确保无饥饿:因为进入临界区域是依照时间戳顺序,时间戳顺序确保FCFS.
• 每个进程每次进入临界区需要的消息数量:2×(n－1)这是全分布算法最好的结果。

第12页：9.6.2 分布方式分布方式缺点

• 每个进程必须知道所有其它进程的存在,这使进程动态增减变的复杂;
• 若其中一个进程失效,则整个算法崩溃,为此需要动态监视所有进程状态;
• 不想进入临界区的进程也必须参与协调过程,因而算法比较适合稳定且数量较少的进程集合。

第13页：9.6.3 标志传递方式仅适合于逻辑拓扑

• 。
• 系统中有一个标志,它作为特殊类型的消息在系统中环行;
• 当一个进程接收到这个标志后,它就可以进入其临界区,并扣留这个标志;
• 当它退出临界区之后,标志才被释放,并沿环路继续绕行;
• 如果一个接收到标志的进程并不想进入其临界区,只需放行此标志token passing

第14页：9.6.3 标志传递方式

• 需要考虑两种失效情况
• 如果消息丢失,则应能发现并选择一个进程产生一个新的标志;
• 如果一个进程夭折了,则逻辑环就将断裂,此时系统应能重构一个新的逻辑环.

第15页：9.7 进程同步与进程通信

• 消息传递(Message Passing)
• 套接字(Socket)
• 远程过程调用Remote Procedure Call : RPC
• 远程方法启用Remote Method Invocation : RMI

第16页：9.7.1 消息传递

• (Message Passing)
• ⒈同步消息传递
• ①send (接收者,消息)将消息发送给指定的接收者,然后挂起,等待来自接收者的应答消息,之后继续。
• ②receive (发送者,消息)等待接收来自发送进程的消息。
• ③reply (发送者,应答)将应答信息发给发送进程,使之继续执行。

第17页：9.7.1 消息传递（续）

9.7.1消息传递进程Pi..……….send(接收者,消息);............阻塞…………继续…………站点A进程Pj..……….receive(发送者,消息);……………………reply(发送者,应答)…………站点B同步消息传递

第18页：9.7.1 消息传递（续3）

• ⒉异步消息传递
• ①send (接收者,消息/应答)将消息/回答发送给接收者,然后继续。
• ②receive(发送者,消息/应答)由发送者处接收消息/应答,然后继续。

第19页：9.7.1 消息传递（续4）

9.7.1消息传递进程Pi..……….send(接收者,消息);继续receive(发送者,应答);…………站点A进程Pj..……….receive(发送者,消息);……………………send(发送者,应答)…………站点B异步消息传递

第20页：9.7.2 套接字

• (Socket)
• 套接字是一种端—端的通信协议;
• 套接字定义为通信的一端,与一个地址相联系;
• 地址形式为(IP, port);
• 套接字是一种低级(low level),不完全可靠的通信方式;
• All Ports < 1024 are Considered “well-known”
  • TELNET uses port 23
  • FTP uses port 21
  • HTTP uses port 80

第21页：9.7.2 套接字（续）

(Socket)socket():建立流式套接字,返回套接字号sconnect():将套接字s与远端主机连接send()/recev():在s上传输数据,直到结束closesocket():关闭套接字s,结束TCP/IP通信客户端(146.86.5.20)服务器端(161.25.19.8)socket():建立流式套接字,返回套接字号sbind():绑定套接字s与本地地址listen():通知TCP/IP,服务器准备好接受连接accept():接受连接,并得到新的套接字nsrecev()/send():在ns上传输数据,直到结束closesocket():关闭套接字nsclosesocket():关闭套接字s建立连接请求服务服务响应套接字通信示图

第22页：9.7.3 远程过程调用

• (RPC)调用者和被调用者通常属于不同站点的进程。RPCs提供一种高级通信方式:
• Client makes procedure call to “remote”server using ordinary procedure callmechanisms.
• Widely accepted and standardizedmechanism in distributed environment
• RPC can be synchronized or asynchronous

第23页：9.7.3 远程过程调用（续）

9.7.3远程过程调用⒈RPC的形式……客户进程:……RPC_name(vec, MAX, 10);(挂起)……vec := v;(继续)…………站点A……服务进程:……RPC_name(v, n, k);v := vec;n := MAX;k := 10;for(i=1;i<=n;i++) dov[i] *=k;…………站点B调用消息Vec, MAX,10返回消息V

第24页：9.7.3 远程过程调用（续3）

• 9.7.3远程过程调用
• ⒉RPC的实现
• ①为每个远程过程调用创建一个代理进程
  • 调用时创建,结束时撤销,代理进程的生存期为调用过程;
  • 一个站点可以同时存在多个执行同一远程过程的进程,并发性好,空间开销小,时间开销大;

第25页：9.7.3 远程过程调用（续4）

• 9.7.3远程过程调用②对每位顾客创建一个代理进程
  • 顾客进程开始时创建代理进程,顾客进程结束时撤销代理进程;
  • 并发性好,空间开销大,时间开销小;
• ③为每项服务建立代理进程
  • 一个站点中仅存在一个执行远程过程的代理进程;
  • 读取控制请求,执行相应过程,然后返回应答消息;
  • 该服务进程可被多个顾客调用;
  • 时空开销小,响应速度慢。

第26页：9.7.3 远程过程调用客户端调用客户端

(stub)参数打包发送等待接收开包结果返回服务器端代理(stub)参数接收开包调用打包发送结果服务器端执行过程返回消息消息远程过程调用实现示图

第27页：9.7.4 远程方法启用

• (Remote Method Invocation, RMI)
• Java中的RPC版本被命名为RMI;
• 一个线程可以启用另外一个远程对象中的方法;
• “远程”指处于不同的Java虚拟机(JVM)中。

第28页：9.7.4 远程方法启用（续）

• RPC与RMI的比较
• RPC支持过程型程序设计风格;
• RMI支持面向对象程序风格;
• RPC的参数为普通数据类型;
• RMI的参数为对象。

第29页：9.8 死锁处理

死锁预防

全局资源排序

基于“优先权/回退”方式的时间戳

死锁避免

分布银行家算法

死锁检测

对每个资源类型的实例

集中方式

分布方式

第30页：9.8.1 死锁预防

• “全局资源排序+请求排序”死锁预防
  • 给每个资源赋予一个唯一的整数;
  • 如果一个进程没持有资源编号等于或大于i的资源,则可以申请编号为i的资源.
  • 优点和缺点
  • simple implementation
  • little overhead
  • difficulty in global resource ordering
  • inconvenient for distributed processesto abide by the protocol

第31页：9.8.1 死锁预防（续）

• 优先级死锁预防
  • 每个进程Pi被赋予一个唯一的优先数;
  • 优先数用来决定进程Pi是否应该等待进程Pj;如果pri (Pi) > pri (Pj), Pi等待;否则Pi回退.
  • The scheme is deadlock-free.For every edge Pi→Pjin thewait-for graph, Pihas a higher priority than Pj. Thus a cyclecannot exist.
  • Possibility ofstarvation--low priority process mayalways be rolled back.
  • Resolve: usetime-stampinstead of priority

第32页：9.8.1 死锁预防（续3）

• 1.等-死(wait-die)基于非剥夺策略;资源申请者等待或回退。
• 当一个进程Pi申请另外一个进程Pj占有的资源时,Pi被允许等待,仅当它具有比Pj更小的时间邮戳,即Pi是比Pj更老,否则Pi回退。例如:设进程P1, P2, P3分别具有时间邮戳5, 10, 15。
  • 如果P1要求P2占用的资源,则P1等待。
  • 如果P3要求P2占用的资源,则P3回退。等待边:(更老)Pi→Pj(更年轻)

第33页：9.8.1 死锁预防（续4）

• 2.伤-等(wound-wait)基于剥夺策略;资源申请者等待或占有者被抢占而回退。
• 当进程Pi申请进程Pj当前所占有的资源时,Pi获准等待的条件是它具有比Pj更大的时间邮戳,即Pi比Pj更年轻;否则Pj回退,即Pj被Pi所伤。例如:设进程P1, P2, P3分别具有邮戳时间5, 10, 15。
  • 如果P1要求P2所占用的资源,则将剥夺P2的资源给P1, P2回退;
  • 如果P3要求P2占用的资源，则P3等待。等待边:(更年轻)Pi→Pj(更老)

第34页：9.8.2 死锁避免

• 银行家算法
  • 指定系统中某个进程为银行家,由它保持执行银行家算法所必需的信息;
  • 银行家负责系统中资源的分配。
• 优点和缺点
  • easy implementation
  • may incur too much overhead
  • possibility of bottleneck
  • if banker fails, the algorithm fails

第35页：9.8.3 死锁检测

• 每个站点保持一个局部资源分配图
  • 资源结点:均为本站点的资源;
  • 进程结点:所有持有或者请求本站点资源的进程。p1p5p3p2r1r2r3p2p3p4r5r4站点A局部资源分配图站点B局部资源分配图
• 1.集中式死锁检测

第36页：9.8.3 死锁检测（续）

• 所有局部资源分配图合并成全局资源分配图站点A和站点B合并的全局资源分配图p1p5p3p2r1r2r3p4r5r4
• 集中式死锁检测方法存在假死锁问题;
• 通过消息时间戳可判断申请/释放资源的顺序,从而判定是否出现死锁。

第37页：9.8.3 死锁检测（续3）

• 利用”探测器”信令: (i, j, k)含义:由进程Pi发起、从进程Pj发往进程Pk的探测信令。
• 算法描述S1:若进程Pi申请资源被进程Pj占有,则发信令(i,i,j);S2:任意进程Pl接到信令(i,r,l),若i=l,则系统出现死锁环路,算法结束;若Pl无等待其它进程占有的资源,则系统无环路,算法结束;S3:假设进程Pl等待的资源分别被进程Pl1、Pl2、…、Plm所占有,则进程Pl分别向进程Pl1、Pl2、…、Plm发信令(i,l,l1)、(i,l,l2)…、(i,l,lm)S4: goto S2;
• 2.分布式死锁检测:Chandy-Misra-Haas算法

第38页：9.8.3死锁检测例

9.8.3死锁检测例:假设当前系统资源分配图如下p6p2p1p4p3p5站点A站点Bp7P2要申请资源且被P3占有;各进程所发信令如下p6p2p1p4p3p5站点A站点Bp7(2,2,3)(2,3,5)(2,5,7)(2,3,4)(2,4,1)

第39页：9.8.3死锁检测例（续）

9.8.3死锁检测p6p2p1p4p3p5站点A站点Bp7此时系统资源分配图如下P1要申请资源且被P2占有;各进程所发信令如下p6p2p1p4p3p5站点A站点Bp7(1,2,3)(1,3,5)(1,5,7)(1,3,4)(1,4,1)(1,1,2)该算法不能确定参与死锁的进程

第40页：9.9 资源管理

9.9.1集中式资源管理中央资源管理者负责系统中所有资源的分配.分配状态物理特性物理位置资源数量资源类型……………系统资源表资源管理：集中式、分布式、层次式

第41页：9.9.1集中式资源管理优点

• 9.9.1集中式资源管理优点:
• ①可以做出全局优化的资源分配策略;
• ②系统扩充和裁减容易这只需要在系统资源分配表中增加一个新项目或删除一个旧项目;
• ③减少了资源管理算法的开销除中央资源管理者外,其它站点不参与资源决策事务。

第42页：9.9.1 集中式资源管理

• 缺点:①可靠性低
  • 因为一旦资源管理者失效,则整个系统瘫痪;
  • 尽管引入多个资源管理者可以克服这一缺点,但保持多副本的一致性是困难的。
• ②中央资源管理者可能成为系统的瓶颈;
• ③由于中央资源管理者的存在,使整个系统失去了自治性。

第43页：9.9.2 分布式资源管理

• 每个站点都有一个局部资源表,用于记载属于该站点的局部资源;
• 当一个站点要申请局部资源时,它可由本地得到;
• 当一个站点要申请全局资源时,它向其它站点发送申请命令,其它站点根据情况做出分配决策。

第44页：9.9.2 分布式资源管理（续）

• 优点:
• 可靠性高因为任何一个站点、资源或服务的失效通常不会影响整个系统;
• 每个站点具有较高的自治性它可以将其所拥有的资源提供给整个系统使用,也可留为私用。

第45页：9.9.2 分布式资源管理（续3）

• 缺点:
• 通信量增加因为要获得有关资源的信息,每个站点都需要与其它站点交换信息;
• 每个站点都需要为资源分配策略的实施付出开销,即资源分配设施消耗局部资源。

第46页：9.9.3 层次式资源管理

• 集中式与分布式资源管理的结合,同时兼有二者的优点,并克服二者的缺点
  • 对于局部资源:采用分布式管理策略;
  • 对于全局资源:采用集中式管理策略。

第47页：9.10 分布式文件系统

• (Distributed File System, DFS)
• 一般结构
• 命名与透明性
• 远程文件存取Remote File Access
  • 远程文件服务
  • 副本复制缓存
• 有状态服务与无状态服务
• 缓存策略

第48页：9.10.1 一般结构

• 分布式文件系统(DFS)是集中式文件系统的分布式实现客户端服务器端一般文件系统客户端远程文件系统缓冲区驱动程序磁盘服务器远程文件系统缓冲区驱动程序磁盘通信子网分布式文件系统体系结构

第49页：9.10.2 命名与透明性

• 命名是逻辑实体(文件名)到物理实体(文件内容)的映射对于真正意义的DFS,整个系统具有统一的命名机制,用户以透明的视图共享所有文件和存储器。
• 三种命名形式
  • 网络命名方式:命名与物理位置完全相关,不透明;
  • 远程安装方式:远程安装是不透明的,一旦安装完毕,远程访问是透明的;
  • 完全分布方式:所有文件具有全局唯一的名字,文件名与物理位置无关。

第50页：9.10.2 命名与透明性（续）

• 0.3远程文件存取⒈远程文件服务:基于C/S工作模式,适合文件小量操作。
• 客户向服务器提出文件访问请求;
• 服务器执行相应操作;
• 服务器将结果返回给客户。
• 实现:RPC⒉副本复制缓存:适合文件整体存取。
• 将远程文件复制到本地,然后如同本地文件一样访问;
• 问题:多副本的一致性。

第51页：9.10.3 远程文件存取

• 副本复制缓存:文件仍然由一个位于服务器上的主拷贝标识,但其副本可能分散在多个站点上。
  • 当进程所需文件不在本地时,由服务器向本地缓存一个副本;
  • 存取操作在缓存副本上执行;
  • 缓存粒度:块为单位;整个文件为单位。
  • 缓存一致性问题:保证主文件和缓存副本的一致。

第52页：9.10.4 有状态服务与无状态服务

• 有状态服务(Stateful service)服务器端保持文件状态信息
  • 打开文件表,块缓冲
• 无状态服务(Stateless service)服务器端不保持文件状态信息
  • 无打开文件表,块缓冲

第53页：9.10.4 有状态服务与无状态…（续）

• ⒈有状态服务(stateful service)
• API界面中包含显式的打开和关闭命令;
• 对于打开命令,文件服务器端需要将文件控制信息读入内存打开文件表中,同时维持文件的读写指针;
• 关闭时若控制信息已变化则回写磁盘。

第54页：9.10.4 有状态服务与无状态服务

• 优点
  • 界面一致,远程文件API与本地文件API相同;
  • 状态信息在内存,响应快;
  • 可以通过预先读等手段提高访问速度;
  • 可以对文件加锁。
• 缺点
  • 对于小量偶然性访问使用麻烦,开销大;
  • 服务器端以open和close识别远程客户会话期,一旦用户不活动要及时撤销文件控制信息,若远程用户忘记close则给状态表维护带来困难。

第55页：9.10.4 有状态服务与无状态…（续）

• ⒉无状态服务(stateless service)
• API界面中不包含文件打开和关闭命令;
• 服务器端在内存文件控制表中不保持远程文件访问的控制信息;
• 每个文件读/写命令必须是自包含的(self contained)
• 远程文件读写命令中包括:文件名、位置(记录号)、内存地址

第56页：9.10.4 有状态服务与无状态服务

• 优点
  • 服务器不需在内存中保持文件状态信息,节省空间;
  • 没有打开文件数的限制;
  • 不需识别远程用户的会话期,实现简单,客户崩溃时不会造成服务器错误。
• 缺点
  • 大量访问速度慢;
  • 无法实现预先读。

第57页：9.10.5 缓存策略

• 1.缓存位置
• ①主存缓存
  • 速度快;
  • 支持无盘客户端工作站;
  • 可靠性差。
• ②磁盘缓存
  • 更可靠,本地机器故障后恢复容易;
  • 速度不如主存缓存。

第58页：9.10.5 缓存策略（续）

• 2.缓存更新策略
• ①通写(write through)
  • 每当缓存副本发生变化时就更新主本。
  • 可靠性高;一致性好;
  • 效率很低。
• ②延迟写(delayed write):
  • 副本数据经过若干次访问(更新)后才最终写回主本;
  • 实现效率较高;
  • 一致性差;
  • 可靠性低:一旦副本所在结点失效则更新数据可能丢失。

第59页：9.10.5 缓存策略（续3）

• ③增量刷新(incremental flush)
  • 定时扫描缓存数据,只将上次更新后发生变化的数据块回写到主本。
• ④关闭写(write on close)
  • 只在文件被关闭时才将缓存信息写回主本;
  • 适合于长时间对数据进行较多更新操作的应用环境。

第60页：9.10.5 缓存策略（续4）

1系统举例Windows 2000 Sever支持的通信模式1.命名管道

经典UNIX管道用于同祖先的进程家族之间;

命名管道可用于不同进程间、跨越网络结点的点对点可靠通信;

管道名的全局命名方式\\computer\\pipe\\name其中, computer为结点计算机名,pipe为固定的常量字符串;name为定义的管道名字。

涉及函数

①服务器端

CreateNamedPipe, ConnectNamedPipe;

②客户端

CallNemedPipe, ReadFile/WriteFile .

第61页：9.10.5 缓存策略（续5）

• 1系统举例Windows 2000 Sever支持的通信模式2.邮件槽控件
  • 基于用户数据报协议的不可靠通信机制;
  • 邮件槽命名方式\\sever\\mailslot\\name其中, sever为服务器名;mailslot为固定的常量字符串;name为创建的邮件槽控件的名字。
  • mailslot控件由服务器创建;
  • 服务器端通过ReadFile读邮件槽消息;
  • 客户端通过WriteFile向邮件槽写消息。

第62页：9.10.5 缓存策略（续6）

• 1系统举例Windows 2000 Sever支持的通信模式
• 3.套接字实现点对点通信,服务器端TransmitFile操作;
• 4.远程过程调用客户/服务器通信模式;
• 5.本地过程调用客户端进程与服务器端进程在同一机器时采用的通信模式。

第63页：选举算法

• 选举算法
• Bully算法Suppose that process Pisend a request that isnot answered by the coordinator within timeinterval T.In this situation, it is assumed that thecoordinator has failed, and Pitries to elect itselfas the new coordinator.This task is completedthrough the following algorithm:

第64页：Bully算法

• Bully算法
• Process Pisend an election message to every process with ahigher priority number. Process Pithen wait for a time intervalT for an answer from anyone of these processes.
• If no response is received within time T, Piassumes that allprocesses with numbers greater than i have failed, and electsitself the new coordinator.Process Pirestart a new copy of the coordinator and sends amessage to inform all active process with priority number lessthan i that Piis the coordinator.

第65页：Bully算法（续）

• Bully算法
• If an answer is received, Pibegins a time interval T’, waitingto receive a message informing it that a process with higherpriority number has been elected. (some other process iselecting itself coordinator, and should report the result withintime T’).If no message is sent within T’, then the process with a highernumber is assumed to have failed, and process Pishouldrestart the algorithm.

第66页：Bully算法（续3）

• Bully算法
• If Piis not the coordinator, then, at any time during execution,Pimay receive one of the following messages from process Pj:
  • Pjis the new coordinator (j>i), process Pirecords thisinformation.
  • Pjstarted a election (j<i). Process Pisend a response to Pjand begins its own election algorithm, provided thatprocess Pihas not already initiated such an election.

第67页：Bully算法例子

• Bully算法例子
• All processes are active, P4 is the coordinator process.
• P1 and P4 fail. P2 determines P4 has failed by sending arequest that is not answered within time T. P2 then beginits election algorithm by sending a request to P3.
• P3 receives the request, responds to P2, and begin itsown algorithm by sending an election request to P4.
• P2 receives P3’s response, and begin waiting for aninterval T’.

第68页：Bully算法例子（续）

• Bully算法例子
• P4 does not respond within an interval T, so P3 electsitself the new coordinator, and send number 3 to P2 andP1 (which P1 does not receive since it has failed)
• Later, when P1 recovers, it sends an election request toP2,P3,and P4.
• P2 and P3 respond to P1, and begin their own electionalgorithm. P3 will again be elected, using the same eventas before.
• Finally, P4 recovers and notice P1,P2,P3 that it is thecurrent coordinator. (P4 send no election request, since itis the process with highest number in the system)