第三章分布式程序设计语言培训资料

《第三章分布式程序设计语言培训资料》由会员分享，可在线阅读，更多相关《第三章分布式程序设计语言培训资料（50页珍藏版）》请在金锄头文库上搜索。

1、第三章 分布式程序设计语言 3.1 分布式程序设计语言概述,分布式应用程序的分类,并行、高性能应用程序。通过并行性达到加速是在分布计算系统上运行应用程序的最主要的原因。,容错应用程序。而分布计算系统具有允许部分失效的特性，即由于各处理机具有自治性，一个处理机的故障不影响其他处理机的正常工作，所以可靠性高。程序和数据也可在若干处理机上复制而进一步增加可靠性。,具有专用功能的应用程序。一些应用程序可以被构造成一组专用的服务程序。例如文件服务、打印服务、进程服务、终端服务、时间服务等。,固有的分布式应用程序。有些应用程序本身就是分布的，在这种情况下，可以把工作站的集合看成一个分布计算系统，这种应用程

2、序必须在分布式硬件上运行。,第三章 分布式程序设计语言 3.1 分布式程序设计语言概述,分布式程序设计与顺序程序设计的区别,使用多个处理机。对分布式程序设计支持的第一个要求就是系统应该具有把一个程序的不同部分分配到不同处理机上执行的能力。,处理机合作。各个进程必须能相互通信和同步，这是对分布式程序设计支持的第二个要求。,处理部分失效。在分布计算系统中一些CPU失效时，其他CPU照样工作。所以对分布式程序设计支持的第三个要求是能对系统的部分失效进行检测并恢复。,第三章 分布式程序设计语言 3.1 分布式程序设计语言概述,分布式程序设计语言的分类,按并行模型来分 顺序进程并行语言。这类语言使用的最

3、基本模型是一组顺序进程，它们并行运行，并且通过报文传递进行通信。大部分是流行的C(或C+)和FORTRAN的扩展。 具有内在并行性的语言。一些研究者认为算法语言不是处理并行性的最好语言，因为算法语言是内在顺序式的，许多研究者研究具有内在并行性的语言，如函数式语言、逻辑语言和面向对象语言。,第三章 分布式程序设计语言 3.1 分布式程序设计语言概述,分布式程序设计语言的分类,容错模型和技术 故障的处理模型： 系统对程序员隐匿全部处理机故障。 给程序员提供高层机制，使得程序员能够描述哪些进程和数据是重要的，以及发生崩溃后怎样恢复。 实现可靠性的方法有两种：程序设计容错和通信容错。 程序设计容错技术

4、有三类：向前恢复试图确定错误所在并基于这个知识改正包含错误的系统状态；向后恢复通过把系统恢复到错误发生前的状态来改正系统状态；错误屏蔽，利用同一个算法独立开发几个版本，一个最后投票系统用于对这n个版本产生的结果进行投票并确定一个正确的结果。 通信容错处理进程通信中发生的故障，通信容错依赖于使用的通信方式和故障的类型。,第三章 分布式程序设计语言 3.2 并行性的支持,并行性的概念,并行性。因为分布计算系统有多个处理机，所以可把程序分成若干部放到多个处理机上同时运行，这就是所谓的并行性。,伪并行性(pseudo parallelism)，即把程序表示为一组并行运 行的进程但不管它们是否在不同的处

5、理机上同时运行。,并行粒度。并行单位可以是进程(如并发C)，也可以是表达式(如Par Alfl)。一般说来，通信代价越大，则并行的粒度就应该越大。,第三章 分布式程序设计语言 3.2 并行性的支持,并行性的表示,进程并行。一般说来，一个进程是一个逻辑处理机，顺序地执行代码，具有自己的状态和数据。在语言中，进程或进程类型是要被说明的，就像过程或过程类型一样。进程的创建可以由说明隐式地完成，也可以通过创建某种结构显式地完成。,对象并行。用下述方法扩充顺序对象模型可获得并行性：(1)允许对象不必在收到报文时才活动；(2)允许接收对象在返回结果后继续执行；第(3)一次向几个对象发送报文；(4)允许报文

6、发送者继续和接收者并行工作。,第三章 分布式程序设计语言 3.2 并行性的支持,并行性的表示,语句并行,PAR j=0 FOR n Aj：=Aj+1,PAR S1 S2,第三章 分布式程序设计语言 3.2 并行性的支持,并行性的表示,函数并行 例如表达式h(f(3,4),g(8)，先计算f或g是没有关系的，从而可以并行计算f和g。,子句的并行 下面的程序给出谓词A的两个子句： (1) A:-B,C,D (2) A:-E,F 存在两个并行性的机会： (1) A的两个子句可并行工作只到有一个成功或两个都失败。 (2) 每个子句中的子定理可并行工作直到它们全都成功，或其中一个失败。 前一种并行性叫做

7、OR并行性，后一种叫做AND并行性。,第三章 分布式程序设计语言 3.3 进程通信与同步的支持,报文传递 进程通信的表示方法：报文传递和共享数据,设计报文传递的通信方式应考虑的问题：,可靠的报文传递和非可靠的报文传递：可靠的报文传递需要承认报文。,显式接收和隐式接收：显式接收时，接收者执行某一类accept语句指明接收哪些报文，以及当报文到达时采取什么行动。使用隐式接收时，在接收者内自动调用程序，通常在接收进程中创建一个新的线程。,直接命名和间接命名：直接命名用于指示一个指定的进程，名字可以是该进程的静态名字或是一个表达式。间接命名包括一个中间对象，通常叫做邮箱，发送者把报文送给它，接收者从它

8、那接收。,第三章 分布式程序设计语言 3.3 进程通信与同步的支持,报文传递 进程通信的表示方法：报文传递和共享数据,设计报文传递的通信方式应考虑的问题：,对称命名和非对称命名。如果发送者和接收者相互命名，则基于直接命名的方案是对称的。在非对称方案中，仅发送者找接收者，在此情况下，接收者要与任何发送者相互作用。注意，使用隐式接收报文的相互作用在命名方面总是非对称的。,第三章 分布式程序设计语言 3.3 进程通信与同步的支持,报文传递,报文传递通信模式有 ：,同步和异步点到点报文。在同步报文传送方式中，发送者在接收者接收报文前一直阻塞。这样，双方不仅交换了数据而且还达到同步。在异步报文传送方式中

9、，发送者并不等待接收者准备好接收其报文，发送者在送出报文后立即继续工作。,会合。在Ada中会合模型基于三个概念：项说明、项调用和接受语句。项说明和接受语句是服务员程序的一部分，项调用在顾客端。当进程S调用进程R的一项，R为此项执行accept语句时，在S和R之间发生了相互作用，叫做会合。 accept incr(X: int; Y: out int) do Y:=X+1; end,第三章 分布式程序设计语言 3.3 进程通信与同步的支持,报文传递,报文传递通信模式有 ：,远程过程调用(RPC)。它是双向通信的另一个原语。当进程S调用进程R的过程P时，由S提供的P的输入参数被送给R。当R收到调用

10、请求时，执行过程P，然后把输出参数送回给S。执行P期间S阻塞，直到输出参数返回。这和会合机构不同，在会合机构中，一旦accept语句已执行，则调用者就不阻塞。,一到多报文传送。很多用于分布计算系统的网络支持快速的广播或组通信设施。,第三章 分布式程序设计语言 3.3 进程通信与同步的支持,共享数据,如果两个进程访问同一个变量，可以实现另一种通信方式：一个进程对此变量进行设置，另一个进程对它进行读。如果两个进程在同一个机器上运行，变量在此机器上存储，则可直接通信。分布进程的共享数据方法有：分布式数据结构和共享的逻辑变量 。,分布式数据结构。这种数据结构可由若干进程同时处理。Linda语言使用元组

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

12、。变量X是这三个进程的通信通道，最初是未赋值的。如果三个进程中的某个给X赋值，则其它两个进程可使用此值。类似地，Y是P1和P2的通信通道。,第三章 分布式程序设计语言 3.3 进程通信与同步的支持,非确定性的表示和控制 进程之间的相互作用模式并不总是确定性的，有时还决定于运行时条件。因此，表示和控制非确定性模型被提出。选择语句和保护的(guarded)Horn子句 是两种表示和控制非确定性的模型。,选择语句。它是由如下形式的一组保护命令组成的： 保护语句 其中保护(guard)由一个布尔表达式和某一类“通信请求”组成。布尔表达式必须无副作用，因为它可能在执行该选择语句过程中被计算多次。,第三章

13、 分布式程序设计语言 3.3 进程通信与同步的支持,非确定性的表示和控制,保护的Horn子句。逻辑程序本质上就不是确定性的。 并行逻辑语言不是对一给定的谓词一个又一个地试验子句，失败时回溯，而是并行地搜索所有那些子句，并且在这些并行执行期间直到有一个并行执行提交前不允许任何赋值对外部是可见的，这叫做OR并行性。但是，这不能无限地进行，因为并行工作的搜索路径随证明的长度而指数地增长。 很普遍的控制OR并行性技术是提交选择非确定性，它非确定地选择一个可选择的子句，取消其他子句。它是基于保护的Horn子句，形式如下： A:-G1,Gn|B1,Bmn0,m0 目标Gi的合取(与操作)叫做保护，目标Bi

14、的合取叫做体(body)。提交操作符“|”也是一个合取操作符。,第三章 分布式程序设计语言 3.4 逻辑上分布地址空间的语言,分布式程序设计语言的分类：,第三章 分布式程序设计语言 3.4 逻辑上分布地址空间的语言,同步式报文传递语言 ：,创建并行进程： 如CSP提供简单的并行命令创建固定数目的并行进程。进程包含名字、逻辑变量和一系列语句(进程体)。 CSP可以创建一组相似的进程，但其数目必须在编译时是个常数。例如并行语句 writer:X:real;|reader(i:1.2): 创建三个进程，叫作“writer”、“reader(1)”和“reader(2)”。Writer有一个局部变量X

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

16、ir(35,60)|Y:n,m:integer;X? pair(n,m) 可使用空构造符对两个进程进行同步但不传送任何实际数据。 非确定性的表示： CSP中使用alternative结构表示非确定性，它由一组保护(后面跟着待执行的动作)组成。保护可包含布尔表达式和一个输入语句。CSP允许进程根据当前通信的输入和名字段的信息有选择地接收。,第三章 分布式程序设计语言 3.4 逻辑上分布地址空间的语言,异步式报文传递语言 ：,并行性单位：NIL中的并行性是基于所谓进程模型。进程不仅是并行性的单位，也是模块化的单位。进程到处理机变换是实现上的问题，由编译和运行时系统处理。,NIL可动态地进行进程间通信路径的配置：NIL中的信口是一个排队的通信通道。在给定时间，一个信口有一个指定的所有者。所有者关系可以转让给其他进程，可以把信口作为报文的一部分传送，或把信口作为一个新创建进程的初始化参数传送。进程可以连接其拥有的输入口和输出口。,第三章 分布式程序设计语言 3.4 逻辑上分布地址空间的语言,异步式报文传递语言 ：,通信类型：NIL既支持同步通信也支持异步通信，可把单