第三章分布式程序设计语言ppt课件

1、第三章第三章 分布式程序设计言语分布式程序设计言语 3.1 3.1 分布式程序设计言语概述分布式程序设计言语概述 v分布式运用程序的分类分布式运用程序的分类 并行、高性能运用程序。经过并行性到达加速是在分布计算系统上运转运用程序的最主要的缘由。 容错运用程序。而分布计算系统具有允许部分失效的特性，即由于各处置机具有自治性，一个处置机的缺点不影响其他处置机的正常任务，所以可靠性高。程序和数据也可在假设干处置机上复制而进一步添加可靠性。 具有公用功能的运用程序。一些运用程序可以被构呵斥一组公用的效力程序。例如文件效力、打印效力、进程效力、终端效力、时间效力等。 固有的分布式运用程序。有些运用程序本

2、身就是分布的，在这种情况下，可以把任务站的集合看成一个分布计算系统，这种运用程序必需在分布式硬件上运转。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.1 3.1 分布式程序设计言语概述分布式程序设计言语概述 v分布式程序设计与顺序程序设计的区别分布式程序设计与顺序程序设计的区别 运用多个处置机。对分布式程序设计支持的第一个要求就是系统应该具有把一个程序的不同部分分配到不同处置机上执行的才干。 处置机协作。各个进程必需能相互通讯和同步，这是对分布式程序设计支持的第二个要求。 处置部分失效。在分布计算系统中一些CPU失效时，其他CPU照样任务。所以对分布式程序设计支持的第三个要求是能对

3、系统的部分失效进展检测并恢复。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.1 3.1 分布式程序设计言语概述分布式程序设计言语概述 v分布式程序设计言语的分类分布式程序设计言语的分类 按并行模型来分按并行模型来分 顺序进程并行言语。这类言语运用的最根本模型是一组顺序顺序进程并行言语。这类言语运用的最根本模型是一组顺序进程，它们并行运转，并且经过报文传送进展通讯。大部分进程，它们并行运转，并且经过报文传送进展通讯。大部分是流行的是流行的C(或或C+)和和FORTRAN的扩展。的扩展。 具有内在并行性的言语。一些研讨者以为算法言语不是处置具有内在并行性的言语。一些研讨者以为算法言语不

4、是处置并行性的最好言语，由于算法言语是内在顺序式的，许多研并行性的最好言语，由于算法言语是内在顺序式的，许多研讨者研讨具有内在并行性的言语，如函数式言语、逻辑言语讨者研讨具有内在并行性的言语，如函数式言语、逻辑言语和面向对象言语。和面向对象言语。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.1 3.1 分布式程序设计言语概述分布式程序设计言语概述 v分布式程序设计言语的分类分布式程序设计言语的分类 按通讯模型来分按通讯模型来分 在物理分布的硬件上运转逻辑上分布的软件。相互运用在物理分布的硬件上运转逻辑上分布的软件。相互运用SEND和和RECEIVE原语通讯，在网络上发送报文。原语通

5、讯，在网络上发送报文。 在物理非分布的硬件上运转逻辑上分布的软件。用共享主存在物理非分布的硬件上运转逻辑上分布的软件。用共享主存方法实现报文传送来模拟物理报文传送通讯。方法实现报文传送来模拟物理报文传送通讯。 在物理分布的硬件上运转逻辑上非分布的软件。运用分布式在物理分布的硬件上运转逻辑上非分布的软件。运用分布式共享存储器通讯。共享存储器通讯。 在物理非分布的硬件上运转逻辑上非分布的软件。运用物理在物理非分布的硬件上运转逻辑上非分布的软件。运用物理共享存储器通讯。共享存储器通讯。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.1 3.1 分布式程序设计言语概述分布式程序设计言语概述

6、v分布式程序设计言语的分类分布式程序设计言语的分类 容错模型和技术容错模型和技术 缺点的处置模型：缺点的处置模型： 系统对程序员隐匿全部处置机缺点。系统对程序员隐匿全部处置机缺点。 给程序员提供高层机制，使得程序员可以描画哪些进程和数给程序员提供高层机制，使得程序员可以描画哪些进程和数据是重要的，以及发生解体后怎样恢复。据是重要的，以及发生解体后怎样恢复。 实现可靠性的方法有两种：程序设计容错和通讯容错。实现可靠性的方法有两种：程序设计容错和通讯容错。 程序设计容错技术有三类：向前恢复试图确定错误所在并基程序设计容错技术有三类：向前恢复试图确定错误所在并基于这个知识矫正包含错误的系统形状；向后

7、恢复经过把系统于这个知识矫正包含错误的系统形状；向后恢复经过把系统恢复到错误发生前的形状来矫正系统形状；错误屏蔽，利用恢复到错误发生前的形状来矫正系统形状；错误屏蔽，利用同一个算法独立开发几个版本，一个最后投票系统用于对这同一个算法独立开发几个版本，一个最后投票系统用于对这n个版本产生的结果进展投票并确定一个正确的结果。个版本产生的结果进展投票并确定一个正确的结果。 通讯容错处置进程通讯中发生的缺点，通讯容错依赖于运用通讯容错处置进程通讯中发生的缺点，通讯容错依赖于运用的通讯方式和缺点的类型。的通讯方式和缺点的类型。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.2 3.2 并行性的

8、支持并行性的支持 v并行性的概念并行性的概念 并行性。由于分布计算系统有多个处置机，所以可把程序分成假设干部放到多个处置机上同时运转，这就是所谓的并行性。 伪并行性(pseudo parallelism)，即把程序表示为一组并行运 行的进程但不论它们能否在不同的处置机上同时运转。 并行粒度。并行单位可以是进程(如并发C)，也可以是表达式(如Par Alfl)。普通说来，通讯代价越大，那么并行的粒度就应该越大。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 进程并行。普通说来，一个进程是一个逻辑处置机，顺序地执行代码，具

9、有本人的形状和数据。在言语中，进程或进程类型是要被阐明的，就像过程或过程类型一样。进程的创建可以由阐明隐式地完成，也可以经过创建某种构造显式地完成。 对象并行。用下述方法扩展顺序对象模型可获得并行性：(1)允许对象不用在收到报文时才活动；(2)允许接纳对象在前往结果后继续执行；第(3)一次向几个对象发送报文；(4)允许报文发送者继续和接纳者并行任务。第三章第三章 分布式程序设计言语分布式程序设计言语 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 语句并行语句并行PAR j=0 FOR n Aj：=Aj+1 PAR S1S2第三章第三章 分布式程序设计言语分布式程序设计言

10、语 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 函数并行函数并行 例如表达式例如表达式h(f(3,4),g(8)h(f(3,4),g(8)，先计算，先计算f f或或g g是没有关系的，从是没有关系的，从而可以并行计算而可以并行计算f f和和g g。 子句的并行子句的并行下面的程序给出谓词下面的程序给出谓词A的两个子句：的两个子句：(1) A:-B,C,D(2) A:-E,F存在两个并行性的时机：存在两个并行性的时机：(1) A的两个子句可并行任务只到有一个胜利或两个都失败。的两个子句可并行任务只到有一个胜利或两个都失败。(2) 每个子句中的子定理可并行任务直到它们全都

11、胜利，或其每个子句中的子定理可并行任务直到它们全都胜利，或其中一个失败。中一个失败。前一种并行性叫做前一种并行性叫做OR并行性，后一种叫做并行性，后一种叫做AND并行性。并行性。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v报文传送报文传送v进程通讯的表示方法：报文传送和共享数据进程通讯的表示方法：报文传送和共享数据 设计报文传送的通讯方式应思索的问题：可靠的报文传送和非可靠的报文传送：可靠的报文传送需求成认报文。显式接纳和隐式接纳：显式接纳时，接纳者执行某一类accept语句指明接纳哪些报文，以及当报文到达时采取什么行动。运

12、用隐式接纳时，在接纳者内自动调用程序，通常在接纳进程中创建一个新的线程。 直接命名和间接命名：直接命名用于指示一个指定的进程，名字可以是该进程的静态名字或是一个表达式。间接命名包括一个中间对象，通常叫做邮箱，发送者把报文送给它，接纳者从它那接纳。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v报文传送报文传送v进程通讯的表示方法：报文传送和共享数据进程通讯的表示方法：报文传送和共享数据 设计报文传送的通讯方式应思索的问题：对称命名和非对称命名。假设发送者和接纳者相互命名，那么基于直接命名的方案是对称的。在非对称方案中，仅发送者找

13、接纳者，在此情况下，接纳者要与任何发送者相互作用。留意，运用隐式接纳报文的相互作用在命名方面总是非对称的。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v报文传送报文传送报文传送通讯方式有 ：同步和异步点到点报文。在同步报文传送方式中，发送者在接纳者接纳报文前不断阻塞。这样，双方不仅交换了数据而且还到达同步。在异步报文传送方式中，发送者并不等待接纳者预备好接纳其报文，发送者在送出报文后立刻继续任务。 会合。在Ada中会合模型基于三个概念：项阐明、项调用和接受语句。项阐明和接受语句是效力员程序的一部分，项调用在顾客端。当进程S调用

14、进程R的一项，R为此项执行accept语句时，在S和R之间发生了相互作用，叫做会合。 accept incr(X: int; Y: out int)do Y:=X+1;end第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v报文传送报文传送报文传送通讯方式有 ：远程过程调用(RPC)。它是双向通讯的另一个原语。当进程S调用进程R的过程P时，由S提供的P的输入参数被送给R。当R收到调用恳求时，执行过程P，然后把输出参数送回给S。执行P期间S阻塞，直到输出参数前往。这和会合机构不同，在会合机构中，一旦accept语句已执行，那么调用者就

15、不阻塞。 一到多报文传送。很多用于分布计算系统的网络支持快速的广播或组通讯设备。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v共享数据共享数据假设两个进程访问同一个变量，可以实现另一种通讯方式：一个进程对此变量进展设置，另一个进程对它进展读。假设两个进程在同一个机器上运转，变量在此机器上存储，那么可直接通讯。分布进程的共享数据方法有：分布式数据构造和共享的逻辑变量 。分布式数据构造。这种数据构造可由假设干进程同时处置。Linda言语运用元组空间(tuple space)的概念实现分布式数据构造。例如“jones,31,true

16、是一个有三个段的元组：一个字符串、一个整数和一个布尔值。对TS定义了三个原子操作：out操作向TS参与一个元组，read读TS中的一个元组，in读TS中的一个元组并删除它。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v共享数据共享数据共享的逻辑变量。逻辑变量具有“单赋值性质，最初，它们是未赋值的，但一旦它们接纳一个值就不能改动它们。这些变量被用于进程之间的通讯通道。如下三个目的：goal_1(X,Y), goal_2(X,Y), goal_3(X)进展逻辑乘，用进程P1、P2、P3并行求解。变量X是这三个进程的通讯通道，最初是

17、未赋值的。假设三个进程中的某个给X赋值，那么其它两个进程可运用此值。类似地，Y是P1和P2的通讯通道。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v非确定性的表示和控制非确定性的表示和控制 v进程之间的相互作用方式并不总是确定性的，有时还进程之间的相互作用方式并不总是确定性的，有时还决议于运转时条件。因此，表示和控制非确定性模型被决议于运转时条件。因此，表示和控制非确定性模型被提出。选择语句和维护的提出。选择语句和维护的(guarded)Horn子句子句 是两种表是两种表示和控制非确定性的模型。示和控制非确定性的模型。选择语句

18、。它是由如下方式的一组维护命令组成的： 维护语句 其中维护(guard)由一个布尔表达式和某一类“通讯恳求组成。布尔表达式必需无副作用，由于它能够在执行该选择语句过程中被计算多次。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.3 3.3 进程通讯与同步的支持进程通讯与同步的支持 v非确定性的表示和控制非确定性的表示和控制 维护的Horn子句。逻辑程序本质上就不是确定性的。并行逻辑言语不是对一给定的谓词一个又一个地实验子句，失败时回溯，而是并行地搜索一切那些子句，并且在这些并行执行期间直到有一个并行执行提交前不允许任何赋值对外部是可见的，这叫做OR并行性。但是，这不能无限地进展，由于

19、并行任务的搜索途径随证明的长度而指数地增长。 很普遍的控制OR并行性技术是提交选择非确定性，它非确定地选择一个可选择的子句，取消其他子句。它是基于维护的Horn子句，方式如下：A:-G1,Gn|B1,Bmn0,m0目的Gi的合取(与操作)叫做维护，目的Bi的合取叫做体(body)。提交操作符“|也是一个合取操作符。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v分布式程序设计言语的分类：分布式程序设计言语的分类： 分布式程序设计言语分布地址空间共享地址空间同步报文传送异步报文传送会合远程过程调用多重原语对象原子事务处置函

20、数式言语逻辑言语分布数据构造第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v同步式报文传送言语同步式报文传送言语 ： 创建并行进程：如CSP提供简单的并行命令创建固定数目的并行进程。进程包含名字、逻辑变量和一系列语句(进程体)。 CSP可以创建一组类似的进程，但其数目必需在编译时是个常数。例如并行语句writer:X:real;|reader(i:1.2): 创建三个进程，叫作“writer、“reader(1)和“reader(2)。Writer有一个部分变量X。下标量i可在reader进程的体中运用。 通讯：CSP进程

21、不能运用全局变量相互通讯，只能运用同步的receive和send。执行send或receive的进程受阻不断到其对方执行完互补的语句为止。例如X:Y! 3|Y:n:integer;X? n在进程X的语句中，把值3发送给Y。在进程Y的语句中，从进程X读取输入，并存放到部分变量n中。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v同步式报文传送言语同步式报文传送言语 ： 可传送的数据类型：简单数据和有构造的数据均可传送与赋值，只需发送的值与接纳它的变量类型一样。可给有构造的数据一个名字(构造符)，如下例中的pair：X:Y!

22、 pair(35,60)|Y:n,m:integer;X? pair(n,m)可运用空构造符对两个进程进展同步但不传送任何实践数据。非确定性的表示：CSP中运用alternative构造表示非确定性，它由一组维护(后面跟着待执行的动作)组成。维护可包含布尔表达式和一个输入语句。CSP允许进程根据当前通讯的输入和名字段的信息有选择地接纳。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v异步式报文传送言语异步式报文传送言语 ： 并行性单位：NIL中的并行性是基于所谓进程模型。进程不仅是并行性的单位，也是模块化的单位。进程四处

23、置机变换是实现上的问题，由编译和运转时系统处置。 NIL可动态地进展进程间通讯途径的配置：NIL中的信口是一个排队的通讯通道。在给定时间，一个信口有一个指定的一切者。一切者关系可以转让给其他进程，可以把信口作为报文的一部分传送，或把信口作为一个新创建进程的初始化参数传送。进程可以衔接其拥有的输入口和输出口。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v异步式报文传送言语异步式报文传送言语 ： 通讯类型：NIL既支持同步通讯也支持异步通讯，可把单个输入口衔接到几个输出口，所以在输入口可以有多个挂起的报文，因此必需排队。非

24、确定表示：NIL提供一个维护命令风格的语句用于在任何输入口上等待报文。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v基于会合的言语基于会合的言语 ： Ada:并行性表示：其并行性是基于顺序进程，叫作义务(task)，每个义务具有一定的类型。义务由阐明部分(阐明其他义务如何与其通讯)和一个体(包含它的可以执行的语句)组成。通讯：义务通常经过会合机制通讯，也经过共享变量通讯，会合机制基于项阐明、项调用和接受语句。 非确定性表示：Ada运用select语句表示非确定性。这个语句用于三个目的：从一组未处置的恳求中非确定地选择一

25、个项调用；有条件地调用一项(即仅当被调用的义务预备好立刻接受它)和为一个项调用设置时限。 容错：Ada有一个异常处置机制处置软件缺点，但言语定义未阐明硬件缺点问题。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v基于会合的言语基于会合的言语 ： 并发C:进程创建：它运用create原语显式地创建进程，并可向创建的进程传送参数。可赋给新进程一个优先权，以后新进程或其他进程还可以改动此优先权。通讯：进程经过会合机构相互通讯。并发C中的事务处置与Ada中的项不同，可以前往一个值，并支持异步事务处置(但并不前往值)。并发C支持一

26、个比Ada中的功能更强的accept语句，它根据事务处置参数的值，可以有条件地接受一些事务处置 。非确定性表示：运用select语句表示非确定性。容错：基于进程复制。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v基于远程过程调用的言语基于远程过程调用的言语 ： DP的进程：每个处置机公用于执行一个进程，但每个进程可包含几个处置线程，这些线程以伪并行方式运转。通讯：DP进程相互调用对方的公用过程进展通讯，用如下方式调用： Call P.f(exps,vars)这里P是被调用进程的名字，f是由P阐明的过程名字，表达式是输入

27、参数，前往值赋予变量vars。第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v多重通讯原语多重通讯原语 ： SR是由一个或多个资源(resource)组成。资源是运转在一个物理节点(单处置机或共享存储器多处置机)的一个程序模块，可动态创建，并可选择地分配到指定机器上运转。 资源可包含多个进程，它们共享数据。资源可包含一个初始进程和终结进程，它们隐式地被创建和运转。 SR运用类似于select语句的构造处置非确定性。 SR操作的定义类似过程的定义，可看成一个过程或入口点(entry point)。 第三章第三章 分布式程序设

28、计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v多重通讯原语多重通讯原语 ： 把操作的两种效力方式和两种调用方式结合起来就有四种进程通讯方法 。 call(同步)send(异步)entry(同步)会合报文传送process(异步)RPCFork第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v基于对象的言语基于对象的言语 ： 对象：Emerald把一切实体都看成对象。对象可以是自动的或被动的。并行性：Emerald中的并行性表如今自动对象的同时执行上。一些对象可从一个处置机上迁移

29、到另一个上。 分布式系统中，很多对象可以并行运转，Emerald为本地和远程调用提供一样的语义。 对象的迁移可由编译程序或程序员运用几个简单原语发动。对象可作为远程操作中的参数传送。对该参数对象的每次访问都会产生另一个远程调用。为了使这类调用最正确化，先把参数对象传送到目的处置机，后把该对象传送回来。由于这种情况经常发生，所以引入一个新的参数传送类型，叫做传送调用(call_by_move)以便有效地完成这种操作。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.4 3.4 逻辑上分布地址空间的言语逻辑上分布地址空间的言语 v基于原子事务处置的言语基于原子事务处置的言语 ： Argus

30、: 主要特点:guardian(维护者)和action(活动)。维护者是能从解体中幸存下来的模块，而活动是一组原子执行。 为了在坚持原子语义下允许活动的并行，运用原子对象，它是一种原子数据类型。Argus提供一些原子类型，用户也可本人定义一些。 Argus提供两级同步机制：用于伪并行进程的和用于并行活动的。 mutex类型提供对维护者内各进程所共享的对象的互斥访问。 在容错方面，可把某些维护者对象阐明成stable，存放到巩固存储器中，假设某个节点解体了，那么可在巩固存储器中检索并得到恢复。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.5 3.5 逻辑上共享地址空间的言语逻辑上共享

31、地址空间的言语 v并行函数式言语并行函数式言语 ： ParAlfl利用隐式函数并行性。函数并行性通常是细粒度的。由于能够有比处置机数多得多的义务要并行执行，所以运用变换方法指定哪个表达式在哪台处置机上计算。 如：(f(x) $on ($self-1)+(g(y) $on ($self+1) 通讯和同步是隐式的，所以不需求显式言语构造。某个计算需求另一个计算的结果但还未出来时那么受阻。 语义是基于缓慢计算(lazy evaluation)，即一个表达式仅当其结果被要求时才进展计算。普通说来，程序员不需关怀计算次序，但为了有效性要对计算次序进展控制。 第三章第三章 分布式程序设计言语分布式程序设计

32、言语 3.5 3.5 逻辑上共享地址空间的言语逻辑上共享地址空间的言语 v并行逻辑言语并行逻辑言语 ： 并发PROLOG ： 并行性来自合取的各目的的AND并行计算和维护Horn子句的各维护的OR并行计算。 并发PROLOG中的并行进程运用共享逻辑变量通讯。同步是基于在只读变量上暂停的方法。 并发PROLOG运用维护Horn子句处置非确定性。第三章第三章 分布式程序设计言语分布式程序设计言语 3.5 3.5 逻辑上共享地址空间的言语逻辑上共享地址空间的言语 v并行逻辑言语并行逻辑言语 ： PARLOG： AND/OR并行性由程序员控制。有两种不同的合取操作符：“.并行计算各合取；“&串

33、行计算各合取(自左至右)。 进程经过共享变量进展通讯，而同步方法是在无界共享变量上挂起。PARLOG有个机构用来指定哪些进程可以为某变量产生赋值。假设输入自变量未被赋值，那么相应的合一将挂起，当某其他进程为该变量赋值时此合一将继续。 PARLOG运用维护的Horn子句用于非确定性。PARLOG中的维护可测试任何输入变量并为子句的部分变量赋值，但不能给在输入自变量中传送的变量赋值。第三章第三章 分布式程序设计言语分布式程序设计言语 3.5 3.5 逻辑上共享地址空间的言语逻辑上共享地址空间的言语 v基于分布数据构造言语基于分布数据构造言语 ： Linda： Linda的目的是将程序员从并行计算和

34、并发事件的思索中解脱出来，从而使并行程序设计在概念上类似于顺序程序设计。 Linda运用简单原语eval创建顺序进程，但不为程序设计人员提供方法把进程变换四处置机上，实践上并不需求，由于每个处置机执行一个进程。 Linda运用元组空间通讯模型。进程通讯要向TS插入新元组、读和移去现存的元组。进程同步方法是运用阻塞read和in操作等待元组可用。 Linda的容错网络内核是基于TS的复制上的。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.5 3.5 逻辑上共享地址空间的言语逻辑上共享地址空间的言语 v基于分布数据构造言语基于分布数据构造言语 ： Orca ：这种言语的并行性是基于顺序

35、进程。运用显式的fork原语派生新的子进程并把参数传送给它。参数可以是数值，也可以是由该子进程的阐明部分指出共享的笼统数据类型。进程之间通讯经过共享数据对象间接地进展。每个对象都属于笼统数据类型，每个笼统数据类型的定义由阐明部分和实现部分组成。阐明部分列出可对该给定类型的对象进展的各种操作。一个操作的实现可由一个或多个维护语句组成。假设是这样，一个操作的调用受阻直到至少有一个维护胜利，接着非确定性地选择一个为真的维护，执行其语句不再受阻。 共享数据对象模型在分布式系统中有效的实现方法是复制对象。假设共享对象不经常改动，可在经常读它的处置机上维持副本，对本地副本进展读操作，就可减少通讯开销。原语

36、 语言的例子并行性表示并行性 进程 Ada、并发 C、Linda、NIL 对象 Emerald、并发 Smalltalk 语句 Occam 表达式 ParAlfl、FX-87 子句 并发 PROLOG、PARLOG变换 静态 Occam、StarMod 动态 并发 PROLOG、ParAlfl 迁移 Emerald通信报文传递 点到点报文 CSP、Occam、NIL 会合 Ada、并发 C 远程过程调用 DP、并发 CLU、LYNX 一对多报文 BSP、StarMod数据共享 分布式数据结构 Linda、Orca 共享逻辑变量 并发 PROLOG、PARLOG非确定性 选择语句 CSP、Occ

37、am、Ada、并发 C、SR 保护 Horn 子句 并发 PROLOG、PARLOG部分失效故障检测 Ada、SR原子事务处理 Argus、Aeolus、Avalon透明容错 NIL第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL vDCDL中的通用符号中的通用符号 ： 选择*重复|并行条件；顺序send输出：=赋值receive输入： ：定义开始结束任意(全称量词)存在(存在量词)=相等不等或且反第三章第三章 分布式程序设计言语分布式程序设计言语 3.63.6分布式控制描画言语分布式控制描画言语DCDL DCDL vD

38、CDL中并行性表示中并行性表示 ：vDCDL中的并行单元是语句。中的并行单元是语句。v一组并行语句表示为：一组并行语句表示为：vS1|S2|Snv而一组顺序语句表示为：而一组顺序语句表示为：v S1；S2；Sn v一组语句可以用语句优先图一组语句可以用语句优先图表示表示v S1；S2；S3|S4；S5；S6|S7 S1S2S3S4S7S5S6S1S2S3S4S7S5S6第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v选择语句选择语句 ：v一个选择语句表示为：一个选择语句表示为：vG1C1G1C1G2C2G2C2GnC

39、nGnCnv选择语句选择其组成的被维护的命令之一执行。假设选择语句选择其组成的被维护的命令之一执行。假设多余一个命令可被选择，选择将是不确定的。如下的选多余一个命令可被选择，选择将是不确定的。如下的选择语句择语句vxym:=xxym:=xyxm:=yyxm:=yv表示假设表示假设xyxy，将，将x x赋予赋予mm；假设；假设yxyx，将，将y y赋予赋予mm；假设假设xyxy并且并且yxyx，那么将，那么将x x或或y y之一赋予之一赋予mm。 第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v反复语句反复语句 ：v一

40、个反复语句指定其组成选择语句的交互次数，这些一个反复语句指定其组成选择语句的交互次数，这些语句带维护或不带维护，它的方式有如下三种：语句带维护或不带维护，它的方式有如下三种：v1 1* * 带维护的选择语句带维护的选择语句 v2 2* * 不带维护的选择语句不带维护的选择语句 v3 3(n)(n)选择语句选择语句 v在第一种情况下，当一切的维护都经过时，反复语句在第一种情况下，当一切的维护都经过时，反复语句终止。在第二种情况下，执行不终止。第三种是一个特终止。在第二种情况下，执行不终止。第三种是一个特别的反复语句，其反复的次数最多为别的反复语句，其反复的次数最多为n n。 第三章第三章 分布式

41、程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v反复语句反复语句 ：v例例1 1：给出一个确定的数组：给出一个确定的数组b1:m1:nb1:m1:n，其中，其中1m1m，1n1ni:=i+1;j:=1jni:=i+1;j:=1v v 第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v反复语句反复语句 ：v例例2 2：确定一个：确定一个mmn n的矩阵的矩阵a1:m1:na1:m1:n中某一行的一中某一行的一切元素能否全部为切元素能否全部为0 0 vi:=1; p

42、:=m+1;i:=1; p:=m+1;v* *ipipvj:=1; j:=1; v q:=n+1; q:=n+1;v * *jqjqvai,j=0j:=j+1ai,j=0j:=j+1ai,j0q:=jai,j0q:=jv ; ;v j=np:=i j=np:=ijni:=i+1jni:=i+1v v vfound:=(im+1) found:=(im+1) 第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v语句并发语句并发( (或并行或并行) )的条件的条件v当两个语句并发执行时，能够产生与顺序执行不同的当两个语句并发

43、执行时，能够产生与顺序执行不同的结果。让我们先定义两个符号：结果。让我们先定义两个符号：v(1) R(Si)(1) R(Si)，Si Si的读集，即在的读集，即在Si Si中被援用的一切变量中被援用的一切变量的集合。的集合。v(2) W(Si)(2) W(Si)，Si Si的写集，即在的写集，即在Si Si中被修正的一切变量中被修正的一切变量的集合。的集合。 vBernsteinBernstein提出了以下三个条件，对于两个并发执行的提出了以下三个条件，对于两个并发执行的语句语句S1S1和和S2S2，必需满足这三个条件才干使它们并发执行，必需满足这三个条件才干使它们并发执行的结果与它们以恣意次

44、序顺序执行的结果一样。的结果与它们以恣意次序顺序执行的结果一样。v(1) R(S1)W(S2)=(1) R(S1)W(S2)=v(2) R(S2)W(S1)=(2) R(S2)W(S1)=v(3) W(S1)W(S2)=(3) W(S1)W(S2)=第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v语句并发语句并发( (或并行或并行) )的条件的条件v 我们可以用我们可以用BernsteinBernstein条件来寻觅语句中可以并行执条件来寻觅语句中可以并行执行的最大子集。为此我们定义了一个无向图，节点集行的最大子集。

45、为此我们定义了一个无向图，节点集由给定语句集组成，假设由给定语句集组成，假设Si|SjSi|Sj，那么节点，那么节点Si Si和和Sj Sj相连，相连，可以并行执行的最大的语句子集对应于最大的完全子可以并行执行的最大的语句子集对应于最大的完全子图。图。 例如：S1: a:=xy, S2: b:=xz, S3: x:=yz, S4: c:=y-1。显然，S1，S2，S4构成最大的完全子图，也就是说，S1|S2|S4。 S1S2S3S4S1S2S3S4第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v DCDLDCDL中的

46、通讯中的通讯v 输出命令的方式为：输出命令的方式为：vsend message_list to destinationsend message_list to destinationv其中其中destinationdestination是一个进程名是一个进程名( (一对一通讯一对一通讯) )或代或代表一切其他进程表一切其他进程( (一对一切通讯一对一切通讯) )的关键字的关键字allall。v 输入命令的方式为：输入命令的方式为：vreceive message_list from sourcereceive message_list from sourcev其中其中sourcesource是

47、一个进程名，这个输入命令支持显是一个进程名，这个输入命令支持显式和隐式的报文接纳。式和隐式的报文接纳。v隐式的报文接纳表示为：隐式的报文接纳表示为：vreceive message_listreceive message_list第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语DCDL DCDL v DCDLDCDL中的通讯中的通讯v 例例1 1：用如下递归的方法计算：用如下递归的方法计算f(n)=f(n-1)f(n)=f(n-1)n2n2，n n1 1并并且且f(1)=1f(1)=1。 vp(i:1.n):=p(i:1.n):=* *r

48、eceive m from p(i-1)receive m from p(i-1)vm=0send 1 to p(i-1)m=0send 1 to p(i-1)m0send m0send m-1 to p(i+1);m-1 to p(i+1);vreceive r from p(i+1);receive r from p(i+1);vsend msend mmmr to p(i-1)r to p(i-1)v v vp(0):=send n to p(1);p(0):=send n to p(1);vreceive result from p(1) receive result from p(1) 第三章第三章 分布式程序设计言语分布式程序设计言语 3.6 3.6 分布式控制描画言语分布式控制描画言语