Chapter3分布式程序设计语言.ppt

《Chapter3分布式程序设计语言.ppt》由会员分享，可在线阅读，更多相关《Chapter3分布式程序设计语言.ppt（55页珍藏版）》请在课桌文档上搜索。

1、第三章 分布式程序设计语言,2,2023/3/10,3.1 分布式程序设计语言概述,对应用程序进行程序设计的理由：减少单个计算的周转时间；增加可靠性和可用性；使系统的某些部分提供某些特殊功能以及固有的分布式应用。,3,2023/3/10,分布式应用程序的分类,并行、高性能应用程序。通过并行性达到加速是在分布计算系统上运行应用程序的最主要的原因。容错应用程序。分布计算系统具有允许部分失效的特性，即由于各处理机具有自治性，一个处理机的故障不影响其他处理机的正常工作。程序和数据也可在若干处理机上复制而进一步增加可靠性。具有专用功能的应用程序。一些应用程序可以被构造成一组专用的服务程序。例如文件服务、

2、打印服务、进程服务、终端服务、时间服务等。固有的分布式应用程序。有些应用程序本身就是分布的，在这种情况下，可以把工作站的集合看成一个分布计算系统，这种应用程序必须在分布式硬件上运行。,4,2023/3/10,分布式程序设计与顺序程序设计的区别,使用多个处理机：分布式程序在不同处理机上并行执行其代码的不同部分，这是对分布式程序设计的第一个要求处理机合作：分布式计算系统的各个进程在执行分布式应用程序时需要合作，能相互通信和同步，这是对分布式程序设计支持的第二个要求。处理部分失效：在分布计算系统中一些CPU失效时，其他CPU照样工作。能对系统的部分失效进行检测并恢复是分布式程序设计的第三个要求。,5

3、,2023/3/10,分布式程序设计语言的分类,按并行模型来分 顺序进程并行语言：这类语言使用的最基本模型是一组顺序进程，它们并行运行，并且通过报文传递进行通信。大部分是流行的C(或C+)和FORTRAN的扩展。具有内在并行性的语言：一些研究者认为算法语言不是处理并行性的最好语言，因为算法语言是内在顺序式的，许多研究者研究具有内在并行性的语言，如函数式语言、逻辑语言和面向对象语言。,6,2023/3/10,按通信模型来分 分布式程序语言分为逻辑上分布的语言和逻辑上非分布的语言。分布式系统逻辑上和物理上的分布有四种组合：在物理分布的硬件上运行逻辑上分布的软件。一组进程，每个进程在分开的处理机上运

4、行，相互使用SEND和RECEIVE原语通信，在网络上发送报文。在物理非分布的硬件上运行逻辑上分布的软件。具有相同逻辑的多进程结构，用共享主存方法实现报文传递来模拟物理报文传递通信。在物理分布的硬件上运行逻辑上非分布的软件。试图隐匿物理分布，使分布式系统相对于程序员来说好像有共享存储器。在物理非分布的硬件上运行逻辑上非分布的软件。使用共享数据通信，物理共享存储器的存在使得实现起来比较容易。,7,2023/3/10,容错模型和技术故障的处理模型：系统对程序员隐匿全部处理机故障。给程序员提供高层机制，使得程序员能够描述哪些进程和数据是重要的，以及发生崩溃后怎样恢复。实现可靠性的方法：程序设计容错技

5、术有三类：向前恢复、向后恢复、错误屏蔽。通信容错，依赖于使用的通信方式和故障的类型。,8,2023/3/10,3.2 并行性的支持,并行性的概念 并行性：因为分布计算系统有多个处理机，所以可把程序分成若干部放到多个处理机上同时运行，这就是所谓的并行性。伪并行性:即把程序表示为一组并行运行的进程，但不管它们是否在不同的处理机上同时运行。并行粒度:并行单位可以是进程(如并发C)，也可以是表达式(如Par Alfl)。一般说来，通信代价越大，则并行的粒度就应该越大。,9,2023/3/10,并行性的表示进程并行：一般说来，一个进程是一个逻辑处理机，顺序地执行代码，具有自己的状态和数据。在语言中，如同

6、过程或过程类型一样，进程或进程类型是要被说明的。对象并行：面向对象语言中的并行性可以用两种方法获得。Smalltalk-80包含传统的进程概念，让程序员处理两种模块：进程和对象。另一种方法是对象本身作为并行单位。用下述方法扩充顺序对象模型可获得并行性：(1)允许对象不必在收到报文时才活动；(2)允许接收对象在返回结果后继续执行；(3)允许一次向几个对象发送报文；(4)允许报文发送者继续和接收者并行工作。,10,2023/3/10,语句并行：语句被分成组且并行执行 SEQ S1 S2 或 PAR S1 S2 并行循环语句 PAR j=0 FOR n Aj：=Aj+1,11,2023/3/10,函

7、数并行如果函数没有任何副作用，则出了“结束”这一点外，在那种次序执行方面是没有差别的，例如表达h(f(3,4),g(8)，先计算f或g是没有关系的，因此可以并行计算f和g。原则上，所有函数调用均可以并行执行，唯一的限制是使用另一个函数的结果的函数要等待该结果的产生。对于分布式计算系统，函数方法需要解决以下几个问题：确立并行度，即粒度大小；如何分配计算问题；编译程序，确立处理机的分配。,12,2023/3/10,子句的并行 AND/OR并行性适合于分布式程序设计，且已并入很多并行逻辑程序设计语言中，下面的程序给出谓词A的两个子句：A:-B,C,D A:-E,F用过程的观点，存在两个并行性的机会：

8、A的两个子句可并行工作只到有一个成功或两个都失败。每个子句中的子定理可并行工作直到它们全都成功，或其中一个失败。前一种并行性叫做OR并行性，后一种叫做AND并行性。,13,2023/3/10,并行计算到物理处理机的变换 可编程的变换，即用户控制的变换通常由两步组成：把并行单元变换到物理的处理机上，几个并行单元可以变换到同一个处理机上；使用局部变换对同一处理机上的单元进行调度，通常使用分配给并行单元的优先权。无论是由程序员还是由系统把并行单元分配给处理机，有如下三种分配方法：编译时确定处理机；运行时确定处理机；完全不确定。,14,2023/3/10,3.3 进程通信与同步的支持,进程通信的表示方

9、法：报文传递和共享数据报文传递设计报文传递的通信方式应考虑的问题：可靠的报文传递和非可靠的报文传递：语言通常只提供可靠的报文传递，语言的运行时系统自动产生承认报文，这在语言级上是透明的。显式接收和隐式接收：发送者通过发送报文或调用远程过程显式地发动相互作用，接收者接收报文可以是显式的也可以是隐式的。显式接收时，接收者执行某一类accept语句指明接收哪些报文，以及当报文到达时采取什么行动。使用隐式接收时，在接收者内自动调用程序，通常在接收进程中创建一个新的线程。,15,2023/3/10,直接命名和间接命名：发送者要把报文送给谁，接收者从谁那里接收报文？双方的命名可以是直接的或间接的。直接命名

10、用于指示一个指定的进程，名字可以是该进程的静态名字或是一个表达式。间接命名包括一个中间对象，通常叫做邮箱，发送者把报文送给它，接收者从它那接收。对称命名和非对称命名：如果发送者和接收者相互命名，则基于直接命名的方案是对称的。在非对称方案中，仅发送者找接收者，在此情况下，接收者要与任何发送者相互作用。注意，使用隐式接收报文的相互作用在命名方面总是非对称的。,16,2023/3/10,报文传递通信模式同步和异步点到点报文：在同步报文传送方式中，发送者在接收者接收报文前一直阻塞。这样，双方不仅交换了数据而且还达到同步。在异步报文传送方式中，发送者并不等待接收者准备好接收其报文，发送者在送出报文后立即

11、继续工作。会合：点到点报文在两个进程间建立单向通信，但是进程之间的相互作用本知识是双向的。在Ada中会合模型基于三个概念：项说明、项调用和接受语句。项说明和接受语句是服务员程序的一部分，项调用在顾客端。当进程S调用进程R的一项，R为此项执行accept语句时，在S和R之间发生了相互作用，叫做会合。,17,2023/3/10,远程过程调用(RPC)：双向通信的另一个原语。当进程S调用进程R的过程P时，由S提供的P的输入参数被送给R。当R收到调用请求时，执行过程P，然后把输出参数送回给S。执行P期间S阻塞，直到输出参数返回。这和会合机构不同，在会合机构中，一旦accept语句已执行，则调用者就不阻

12、塞，但RPC和会合机构是一样的，也是完全同步相互作用。一到多报文传送：很多用于分布计算系统的网络支持快速的广播或组通信设施，但不能保证所有的目的地收到报文。由于通信差错或某些接受处理机未准备好，报文可能会丢失。,18,2023/3/10,共享数据 分布进程的共享数据方法：分布式数据结构和共享的逻辑变量 分布式数据结构：这种数据结构可由若干进程同时处理。Linda语言使用元组空间(Tuple Space)的概念实现分布式数据结构。元组空间TS在概念上是一个共享存储器，TS是为程序的所有进程共享的全局存储器，TS的基本存储单元是元组，是有序的数据序列，类似PASCAL中的记录，例如“jones”,

13、31,true是一个有三个段的元组：一个字符串、一个整数和一个布尔值。对TS定义了三个原子操作：out操作向TS加入一个元组，read读TS中的一个元组，in读TS中的一个元组并删除它。,19,2023/3/10,共享的逻辑变量：逻辑变量具有“单赋值”性质，最初它们是未赋值的，但一旦它们接收一个值就不能再被改变，这一性质可能在共享逻辑变量的并行进程之间引起冲突。下面的例子出示了这些变量如何被用于进程之间的通信通道。假设三个目标：goal_1(X,Y),goal_2(X,Y),goal_3(X)进行逻辑乘，用进程P1、P2、P3并行求解。变量X是这三个进程的通信通道，最初是未赋值的。如果三个进程

14、中的某个给X赋值，则其它两个进程可使用此值。类似地，Y是P1和P2的通信通道，进程同步通过在无约束变量上挂起达到。,20,2023/3/10,非确定性的表示和控制 进程之间的相互作用模式并不总是确定性的，有时还决定于运行时条件，因此需要研究表示和控制非确定性模型。选择语句和保护的(guarded)Horn子句是两种分开的控制非确定性结构。选择语句：它是由如下形式的一组保护命令组成的：保护语句 其中保护(guard)由一个布尔表达式和某一类“通信请求”组成。布尔表达式必须无副作用，因为它可能在执行该选择语句过程中被计算多次。,21,2023/3/10,保护的Horn子句：逻辑程序本质上就不是确定

15、性的。并行逻辑语言并行地搜索所有子句，并且在这些并行执行期间直到有一个并行执行提交前不允许任何赋值对外部是可见的，这叫做OR并行性。但是，这不能无限地进行，因为并行工作的搜索路径随证明的长度而指数地增长。很普遍的控制OR并行性技术是提交选择非确定性，它非确定地选择一个可选择的子句，并取消其他子句，它是基于保护的Horn子句，形式如下：A:-G1,Gn|B1,Bmn0,m0目标Gi的合取(与操作)叫做保护，目标Bi的合取叫做体(body)。提交操作符“|”也是一个合取操作符。,22,2023/3/10,3.4 逻辑上分布地址空间的语言,23,2023/3/10,同步式报文传递语言1978年，Ho

16、are提出CSP语言。CSP提供简单的并行命令创建固定数目的并行进程。进程包含名字、逻辑变量和一系列语句(进程体)。CSP不使用参数，也不能变换到制定的处理机上。CSP可以创建一组相似的进程，但其数目必须在编译时是个常数。CSP进程不能使用全局变量相互通信，只能使用同步的receive和send。发送进程指出接收进程的名字，提供一个待发送的值。接收进程指出发送进程的名字并提供一个变量。执行send或receive的进程受阻，一直到其对方执行完互补的语句为止。,24,2023/3/10,简单数据和有结构的数据均可传送与赋值，只要发送的值与接收它的变量类型相同。可给有结构的数据一个名字(构造符)。

17、CSP中使用alternative结构表示非确定性，它由一组保护(后面跟着待执行的动作)组成。保护可包含布尔表达式和一个输入语句。CSP允许进程根据当前通信的输入和名字段的信息有选择地接收。,25,2023/3/10,异步式报文传递语言NIL（Network Implementation Language）是一种高级语言，用于构造大型、可靠的分布式软件系统。它是一种安全的语言，即一个程序模块不影响其他模块的正确性。该语言的原理是基于“类型状态”的，这是一个编译时特性，它能获得变量的类型和其初始状态。NIL中的并行性是基于所谓进程模型。进程不仅是并行性的单位，也是模块化的单位。把NIL程序分解为

18、进程是根据软件工程的原理，而不是基于性能的考虑。进程到处理机变换是实现上的问题，由编译和运行时系统处理。,26,2023/3/10,NIL可动态地进行进程间通信路径的配置。NIL中的信口是一个排队的通信通道。在给定时间，一个信口有一个指定的所有者。所有者关系可以转让给其他进程，可以把信口作为报文的一部分传送，或把信口作为一个新创建进程的初始化参数传送。进程可以连接其拥有的输入口和输出口。NIL既支持同步通信也支持异步通信，可把单个输入口连接到几个输出口，所以在输入口可以有多个挂起的报文，因而必须排队。NIL提供一个保护命令风格的语句用于在任何输入口上等待报文。,27,2023/3/10,基于会

19、合的语言Ada并行性是基于顺序进程，叫作任务(task)，每个任务具有一定的类型。任务由说明部分(说明其他任务如何与其通信)和一个体(包含它的可以执行的语句)组成。任务通常通过会合机制通信，也通过共享变量通信，会合机制基于项说明、项调用和接受语句。Ada使用select语句表示非确定性。这个语句用于三个目的：从一组未处理的请求中非确定地选择一个项调用；有条件地调用一项(即仅当被调用的任务准备好立即接受它)和为一个项调用设置时限。Ada有一个异常处理机制处理软件故障，但语言定义未说明硬件故障问题。,28,2023/3/10,并发C并发C中的进程有一个说名部分和一个体，说名部分由进程名、一组形参和

20、一组事务处理组成，它使用create原语显式地创建进程，并可向创建的进程传送参数。可赋给新进程一个优先权，以后新进程或其他进程还可以改变此优先权。它还可把新进程分配给指定的处理机。进程通过会合机构相互通信。并发C中的事务处理与Ada中的项不同，可以返回一个值，并支持异步事务处理(但并不返回值)。并发C支持一个比Ada中的功能更强的accept语句，它根据事务处理参数的值，可以有条件地接受一些事务处理。事务处理调用类似于函数调用，可用作表达式的一部分。非确定性使用select语句表示。基于进程复制的容错机制。,29,2023/3/10,基于远程过程调用的语言DP是面向实时系统的程序设计语言，其进

21、程通信使用RPC。DP程序中的进程数是在编译时固定下来的，每个处理机专用于执行一个进程，但每个进程可包含几个处理线程，这些线程以伪并行方式运行。DP进程相互调用对方的公用过程进行通信，用如下形式调用：Call P.f(exps,vars)这里P是被调用进程的名字，f是由P说明的过程名字，表达式是输入参数，返回值赋予变量vars。调用进程及其所有线程在调用期间受阻，在P中创建新控制线程。,30,2023/3/10,多重通信原语SR（Synchronizing Resources）是用于对分布式操作系统和应用程序进行程序设计的语言，它提供了若干进程通信模块。SR由一个或多个资源(resource)

22、组成。资源是运行在一个物理节点(单处理机或共享存储器多处理机)的一个程序模块。SR使用类似于select语句的结构处理非确定性。SR操作的定义类似过程的定义，可看成一个过程或入口点(entry point)。调用者可以使用send异步地调用一个操作，也可以使用call同步地调用一个操作。把操作的两种服务方式和两种调用方式结合起来就有四种进程通信方法。,31,2023/3/10,SR中的四种通信类型,32,2023/3/10,基于对象的语言Emerald把所有实体都看成对象。对象可以是主动的或被动的。Emerald是一种强制类型语言，没有类或继承。Emerald中的并行性表现在主动对象的同时执行

23、上。一些对象可从一个处理机上迁移到另一个上。对象由名字、表示、一组操作和一个可选进程四个部分组成。分布式系统中，很多对象可以并行运行，Emerald为本地和远程调用提供相同的语义。对象的迁移可由编译程序或程序员使用几个简单原语发动。对象可作为远程操作中的参数传送。,33,2023/3/10,基于原子事务处理的语言Argus:支持容错的分布式程序设计，特别是需要高度可靠性和可用性的应用程序。其主要特点是guardian(保护者)和action(活动)。保护者是能从崩溃中幸存下来的模块，而活动是一组原子执行。Argus的模块保护着由数据对象及其操作的过程组成。Argus提供两级同步机制：用于伪并行

24、进程的和用于并行活动的。为了在保持原子语义下允许活动的并行，使用原子对象，它是一种原子数据类型。在容错方面，可把某些保护者对象说明成stable，存放到坚固存储器中，如果某个节点崩溃了，则可在坚固存储器中检索并得到恢复。,34,2023/3/10,Aeolus：Aeolus是一个系统程序设计语言，用于clouds分布式操作系统实现容错服务员，它为clouds提供的抽象有对象、活动和进程，并提供对可恢复性和同步设施的访问。Aeolus是基于对象的，支持数据抽象。Aeolus通过对象的操作调用进行通信和同步。Clouds支持对象的原子事务处理，活动可以是嵌套的。Clouds支持对象的可恢复性和同步

25、。自动恢复的方法是对对象的整个状态使用检查点设备。,35,2023/3/10,3.5 逻辑上共享地址空间的语言并行函数式语言ParAlfl利用隐式函数并行性，函数并行性通常是细粒度的。通信和同步是隐式的，所以不需要显式语言结构。某个计算需要另一个计算的结果但还未出来时则受阻。语义是基于迟缓计算(lazy evaluation)，即一个表达式仅当其结果被要求时才进行计算。一般说来，程序员不需关心计算次序，但为了有效性要对计算次序进行控制。ParAlfl程序完全是有确定性的，即这些程序的结果不依赖于这些计算在处理机上是如何分布的。,36,2023/3/10,并行逻辑语言并发PROLOG：并行性来自

26、合取的各目标的AND并行计算和保护Horn子句的各保护的OR并行计算。并发PROLOG中的并行进程使用共享逻辑变量通信。同步是基于在只读变量上暂停的办法。并发PROLOG使用保护Horn子句处理非确定性，保护可创建其它AND并行进程，由于这些进程可能调用新的保护，所以可能导致系统有任意嵌套的保护。,37,2023/3/10,PARLOG：AND/OR并行性由程序员控制。有两种不同的合取操作符：“.”并行计算各合取；“&”串行计算各合取(自左至右)。顺序AND/OR操作符的出现要求实现时确定一组并行进程何时结束。进程通过共享变量进行通信，而同步方法是在无界共享变量上挂起。PARLOG使用保护的H

27、orn子句用于非确定性。PARLOG中的保护可测试任何输入变量并为子句的局部变量赋值，但不能给在输入自变量中传送的变量赋值。PARLOG已用于离散事件模拟、通信协议说明和验证、医学诊断专家系统和自然语言语法分析。,38,2023/3/10,基于分布数据结构语言Linda：Linda的目标是将程序员从并行计算和并发事件的思考中解脱出来，从而使并行程序设计在概念上类似于顺序程序设计。Linda使用简单原语eval创建顺序进程，但不为程序设计人员提供方法把进程变换到处理机上。Linda使用元组空间通信模型。进程通信要向TS插入新元组、读和移去现存的元组。进程同步方法是使用阻塞read和in操作等待元

28、组可用。Linda的容错网络内核是基于TS的复制上的。其目标是达到实际应用问题的高加速比。,39,2023/3/10,Orca：并行性是基于顺序进程，使用显式的fork原语派生新的子进程并把参数传送给它。进程之间通信通过共享数据对象间接地进行。每个对象都属于抽象数据类型，每个抽象数据类型的定义由说明部分和实现部分组成。抽象数据类型的实现部分指定该抽象数据类型的每个变量所包含的数据，并且含有实现该操作的程序。一个操作的实现可由一个或多个保护语句组成。操作在执行中途不会受阻。共享数据对象模型在分布式系统中有效的实现方法是复制对象。,40,2023/3/10,原语,语言的例子,各种分布式程序设计语言

29、原语,41,2023/3/10,3.6 分布式控制描述语言DCDLDCDL中的通用符号,42,2023/3/10,DCDL中并行性表示 DCDL中的并行单元是语句。并行语句可以用优先图表示，节点代表语句，有向边代表优先关系。优先图是有向无环图。一组并行语句表示为：S1|S2|Sn一组顺序语句表示为：S1；S2；Sn 如图所示的优先图表示为:S1；S2；S3|S4；S5；S6|S7,43,2023/3/10,选择语句 一个选择语句表示为：G1C1G2C2GnCn 选择语句选择其组成的被保护的命令之一执行。如果多余一个命令可被选择，选择将是不确定的。如下的选择语句xym:=xyxm:=y表示如果x

30、y，将x赋予m；如果yx，将y赋予m；如果xy并且yx，则将x或y之一赋予m。,44,2023/3/10,重复语句 一个重复语句指定其组成选择语句的交互次数，这些语句带保护或不带保护，它的形式有如下三种：*带保护的选择语句*不带保护的选择语句(n)选择语句 第一种情况，当所有的保护都经过时，重复语句终止。第二种情况，执行不终止。第三种是一个特别的重复语句，其重复的次数最多为n。,45,2023/3/10,例3.6.1 给出一个确定的数组b1:m1:n，其中1ni:i+1;j:=1 在计算表达式xy时，如果x为假，则不用计算y而节省时间，因为不论y为何值，表达式总是为假，这种优化称之为短路。,4

31、6,2023/3/10,例3.6.2 Rubin问题：确定一个mn的矩阵a1:m1:n中某一行的所有元素是否全部为0，这是一个二维的查找问题。i:=1;p:=m+1;*ipj:=1;q:=n+1;*jqai,j=0j:=j+1ai,j0q:=j;j=np:=ijni:=i+1found:=(im+1)布尔变量foundT，则存在这样的全0行，否则，不存在。,47,2023/3/10,语句并发(或并行)的条件 当两个语句并发执行时，可能产生与顺序执行不同的结果。让我们先定义两个符号：R(Si)：Si的读集，即在Si中被引用的所有变量的集合。W(Si)：Si的写集，即在Si中被修改的所有变量的集合

32、。Bernstein提出了以下三个条件，对于两个并发执行的语句S1和S2，必须满足这三个条件才能使它们并发执行的结果与它们以任意次序顺序执行的结果相同。R(S1)W(S2)=R(S2)W(S1)=W(S1)W(S2)=使用S1|S2表示语句S1和S2满足这三个条件，可以并行或并发执行。,48,2023/3/10,例3.6.3 假设S1为a:=x+y，S2为b:=x+z，则这两个语句可以并发执行，因为R(S1)=x，y，R(S2)=x，z，W(S1)=a，W(S2)=b它们满足上述三个条件，以上条件也称为Bernstein条件。一般地，一个语句集Si，1i n，如果两两满足Bernstein条件

33、，那么可以并行执行，即 S1|S2|Sn i j Si|Sj 可以用Bernstein条件寻找语句中可以并行执行的最大子集。为此可定义一个无向图，节点集由给定语句集组成，如果Si|Sj，则节点Si和Sj相连，可以并行执行的最大的语句子集对应于最大的完全子图。,49,2023/3/10,例3.6.4 假设S1:a:=xy,S2:b:=xz,S3:x:=yz,S4:c:=y-1。利用Bernstein条件，有S1|S2，S1|S4，S2|S4，S3|S4，相应的表示在下图中，显然，S1，S2，S4形成最大的完全子图，也就是说S1|S2|S4。,50,2023/3/10,DCDL中的通信 采用异步点

34、对点报文传递，报文通过异步静态通道传递给指定的接收方进程。输出命令的形式为：send message_list to destination其中destination是一个进程名(一对一通信)或代表所有其他进程(一对所有通信)的关键字all。输入命令的形式为：receive message_list from source其中source是一个进程名，这个输入命令支持显式和隐式的报文接收。隐式的报文接收表示为：receive message_list,51,2023/3/10,例3.6.5 用如下递归的方法计算f(n)=f(n-1)n2，n1并且f(1)=1。p(i:1.n):=*receiv

35、e m from p(i-1)m=0send 1 to p(i-1)m0send m-1 to p(i+1);receive r from p(i+1);send mmr to p(i-1)p(0):=send n to p(1);receive result from p(1),52,2023/3/10,例3.6.6 Fibonacci数列是由递推公式F(i)=F(i-1)+F(i-2)(i1)定义的一个整数数列，其初始值F(0)=0，F(1)=2，有如下两种算法：定义一系列进程：f(i)用于计算F(n-i+1)，如果(n-i+1)大于1，f(i)从f(i-1)接收(n-i+1)并把(n-i

36、)传递给f(i+1)。然后f(i)等待f(i+1)和f(i+2)的结果，把它们相加，并把相加的结果传递给f(i-1)和f(i-2)。f(0)是用户进程，f(-1)是虚进程。,53,2023/3/10,f(0):=send n to f(1)；receive p from f(2)；receive q from f(1)；ans:=qf(i):=receive n from f(i-1)；n1send n-1 to f(i-1)；receive p from f(i+2)；receive q from f(i+1)；send p+q to f(i-1)；send p+q to f(i-2)；n=

37、1send 1 to f(i-1)；send 1 to f(i-2)；n=0send 0 to f(i-1)；send 0 to f(i-2)；f(-1):=receive p from f(1)；,54,2023/3/10,这个算法使通信只限于邻居之间，即f(i)只能和f(i-1)和f(i+1)通信。f(0):=n1send n to f(1);receive p from f(1);receive q from f(1);ans:=p n=1ans:=1 n=0ans:=0 f(i):=receive n from f(i-1);n1send n-1 to f(i+1);receive p

38、 from f(i+1);receive q from f(i+1);send p+q to f(i-1);send p to f(i-1)n=1send 1 to f(i-1);send 0 to f(i-1),55,2023/3/10,DCDL中的通信容错 容错是通过检测故障并随之对系统进行重新配置而实现的。以下是用DCDL描述的故障检测过程。sender:=setup time(t);send diagnostic_signal to receiver;receive ack from receiverstatus:=normal timeout(t)status:=abnormal 通过上述高层DCDL算法，一个有故障的处理机将被发送方节点通过检查状态变量的值发现。,