第三章分布式程序設(shè)計(jì)語言ppt課件

1、第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.1 3.1 分布式程序設(shè)計(jì)言語概述分布式程序設(shè)計(jì)言語概述 v分布式運(yùn)用程序的分類分布式運(yùn)用程序的分類 并行、高性能運(yùn)用程序。經(jīng)過并行性到達(dá)加速是在分布計(jì)算系統(tǒng)上運(yùn)轉(zhuǎn)運(yùn)用程序的最主要的緣由。 容錯運(yùn)用程序。而分布計(jì)算系統(tǒng)具有允許部分失效的特性，即由于各處置機(jī)具有自治性，一個處置機(jī)的缺點(diǎn)不影響其他處置機(jī)的正常任務(wù)，所以可靠性高。程序和數(shù)據(jù)也可在假設(shè)干處置機(jī)上復(fù)制而進(jìn)一步添加可靠性。 具有公用功能的運(yùn)用程序。一些運(yùn)用程序可以被構(gòu)呵斥一組公用的效力程序。例如文件效力、打印效力、進(jìn)程效力、終端效力、時間效力等。 固有的分布式運(yùn)用程序。有些運(yùn)用程序本

2、身就是分布的，在這種情況下，可以把任務(wù)站的集合看成一個分布計(jì)算系統(tǒng)，這種運(yùn)用程序必需在分布式硬件上運(yùn)轉(zhuǎn)。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.1 3.1 分布式程序設(shè)計(jì)言語概述分布式程序設(shè)計(jì)言語概述 v分布式程序設(shè)計(jì)與順序程序設(shè)計(jì)的區(qū)別分布式程序設(shè)計(jì)與順序程序設(shè)計(jì)的區(qū)別 運(yùn)用多個處置機(jī)。對分布式程序設(shè)計(jì)支持的第一個要求就是系統(tǒng)應(yīng)該具有把一個程序的不同部分分配到不同處置機(jī)上執(zhí)行的才干。 處置機(jī)協(xié)作。各個進(jìn)程必需能相互通訊和同步，這是對分布式程序設(shè)計(jì)支持的第二個要求。 處置部分失效。在分布計(jì)算系統(tǒng)中一些CPU失效時，其他CPU照樣任務(wù)。所以對分布式程序設(shè)計(jì)支持的第三個要求是能對

3、系統(tǒng)的部分失效進(jìn)展檢測并恢復(fù)。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.1 3.1 分布式程序設(shè)計(jì)言語概述分布式程序設(shè)計(jì)言語概述 v分布式程序設(shè)計(jì)言語的分類分布式程序設(shè)計(jì)言語的分類 按并行模型來分按并行模型來分 順序進(jìn)程并行言語。這類言語運(yùn)用的最根本模型是一組順序順序進(jìn)程并行言語。這類言語運(yùn)用的最根本模型是一組順序進(jìn)程，它們并行運(yùn)轉(zhuǎn)，并且經(jīng)過報文傳送進(jìn)展通訊。大部分進(jìn)程，它們并行運(yùn)轉(zhuǎn)，并且經(jīng)過報文傳送進(jìn)展通訊。大部分是流行的是流行的C(或或C+)和和FORTRAN的擴(kuò)展。的擴(kuò)展。 具有內(nèi)在并行性的言語。一些研討者以為算法言語不是處置具有內(nèi)在并行性的言語。一些研討者以為算法言語不

4、是處置并行性的最好言語，由于算法言語是內(nèi)在順序式的，許多研并行性的最好言語，由于算法言語是內(nèi)在順序式的，許多研討者研討具有內(nèi)在并行性的言語，如函數(shù)式言語、邏輯言語討者研討具有內(nèi)在并行性的言語，如函數(shù)式言語、邏輯言語和面向?qū)ο笱哉Z。和面向?qū)ο笱哉Z。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.1 3.1 分布式程序設(shè)計(jì)言語概述分布式程序設(shè)計(jì)言語概述 v分布式程序設(shè)計(jì)言語的分類分布式程序設(shè)計(jì)言語的分類 按通訊模型來分按通訊模型來分 在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。相互運(yùn)用在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。相互運(yùn)用SEND和和RECEIVE原語通訊，在網(wǎng)絡(luò)上發(fā)送報文。原語通

5、訊，在網(wǎng)絡(luò)上發(fā)送報文。 在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。用共享主存在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。用共享主存方法實(shí)現(xiàn)報文傳送來模擬物理報文傳送通訊。方法實(shí)現(xiàn)報文傳送來模擬物理報文傳送通訊。 在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用分布式在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用分布式共享存儲器通訊。共享存儲器通訊。 在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用物理在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用物理共享存儲器通訊。共享存儲器通訊。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.1 3.1 分布式程序設(shè)計(jì)言語概述分布式程序設(shè)計(jì)言語概述

6、v分布式程序設(shè)計(jì)言語的分類分布式程序設(shè)計(jì)言語的分類 容錯模型和技術(shù)容錯模型和技術(shù) 缺點(diǎn)的處置模型：缺點(diǎn)的處置模型： 系統(tǒng)對程序員隱匿全部處置機(jī)缺點(diǎn)。系統(tǒng)對程序員隱匿全部處置機(jī)缺點(diǎn)。 給程序員提供高層機(jī)制，使得程序員可以描畫哪些進(jìn)程和數(shù)給程序員提供高層機(jī)制，使得程序員可以描畫哪些進(jìn)程和數(shù)據(jù)是重要的，以及發(fā)生解體后怎樣恢復(fù)。據(jù)是重要的，以及發(fā)生解體后怎樣恢復(fù)。 實(shí)現(xiàn)可靠性的方法有兩種：程序設(shè)計(jì)容錯和通訊容錯。實(shí)現(xiàn)可靠性的方法有兩種：程序設(shè)計(jì)容錯和通訊容錯。 程序設(shè)計(jì)容錯技術(shù)有三類：向前恢復(fù)試圖確定錯誤所在并基程序設(shè)計(jì)容錯技術(shù)有三類：向前恢復(fù)試圖確定錯誤所在并基于這個知識矯正包含錯誤的系統(tǒng)形狀；向后

7、恢復(fù)經(jīng)過把系統(tǒng)于這個知識矯正包含錯誤的系統(tǒng)形狀；向后恢復(fù)經(jīng)過把系統(tǒng)恢復(fù)到錯誤發(fā)生前的形狀來矯正系統(tǒng)形狀；錯誤屏蔽，利用恢復(fù)到錯誤發(fā)生前的形狀來矯正系統(tǒng)形狀；錯誤屏蔽，利用同一個算法獨(dú)立開發(fā)幾個版本，一個最后投票系統(tǒng)用于對這同一個算法獨(dú)立開發(fā)幾個版本，一個最后投票系統(tǒng)用于對這n個版本產(chǎn)生的結(jié)果進(jìn)展投票并確定一個正確的結(jié)果。個版本產(chǎn)生的結(jié)果進(jìn)展投票并確定一個正確的結(jié)果。 通訊容錯處置進(jìn)程通訊中發(fā)生的缺點(diǎn)，通訊容錯依賴于運(yùn)用通訊容錯處置進(jìn)程通訊中發(fā)生的缺點(diǎn)，通訊容錯依賴于運(yùn)用的通訊方式和缺點(diǎn)的類型。的通訊方式和缺點(diǎn)的類型。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.2 3.2 并行性的

8、支持并行性的支持 v并行性的概念并行性的概念 并行性。由于分布計(jì)算系統(tǒng)有多個處置機(jī)，所以可把程序分成假設(shè)干部放到多個處置機(jī)上同時運(yùn)轉(zhuǎn)，這就是所謂的并行性。 偽并行性(pseudo parallelism)，即把程序表示為一組并行運(yùn) 行的進(jìn)程但不論它們能否在不同的處置機(jī)上同時運(yùn)轉(zhuǎn)。 并行粒度。并行單位可以是進(jìn)程(如并發(fā)C)，也可以是表達(dá)式(如Par Alfl)。普通說來，通訊代價越大，那么并行的粒度就應(yīng)該越大。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 進(jìn)程并行。普通說來，一個進(jìn)程是一個邏輯處置機(jī)，順序地執(zhí)行代碼，具

9、有本人的形狀和數(shù)據(jù)。在言語中，進(jìn)程或進(jìn)程類型是要被闡明的，就像過程或過程類型一樣。進(jìn)程的創(chuàng)建可以由闡明隱式地完成，也可以經(jīng)過創(chuàng)建某種構(gòu)造顯式地完成。 對象并行。用下述方法擴(kuò)展順序?qū)ο竽Ｐ涂色@得并行性：(1)允許對象不用在收到報文時才活動；(2)允許接納對象在前往結(jié)果后繼續(xù)執(zhí)行；第(3)一次向幾個對象發(fā)送報文；(4)允許報文發(fā)送者繼續(xù)和接納者并行任務(wù)。第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 語句并行語句并行PAR j=0 FOR n Aj：=Aj+1 PAR S1S2第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言

10、語 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 函數(shù)并行函數(shù)并行 例如表達(dá)式例如表達(dá)式h(f(3,4),g(8)h(f(3,4),g(8)，先計(jì)算，先計(jì)算f f或或g g是沒有關(guān)系的，從是沒有關(guān)系的，從而可以并行計(jì)算而可以并行計(jì)算f f和和g g。 子句的并行子句的并行下面的程序給出謂詞下面的程序給出謂詞A的兩個子句：的兩個子句：(1) A:-B,C,D(2) A:-E,F存在兩個并行性的時機(jī)：存在兩個并行性的時機(jī)：(1) A的兩個子句可并行任務(wù)只到有一個勝利或兩個都失敗。的兩個子句可并行任務(wù)只到有一個勝利或兩個都失敗。(2) 每個子句中的子定理可并行任務(wù)直到它們?nèi)?/p>

11、勝利，或其每個子句中的子定理可并行任務(wù)直到它們?nèi)紕倮?，或其中一個失敗。中一個失敗。前一種并行性叫做前一種并行性叫做OR并行性，后一種叫做并行性，后一種叫做AND并行性。并行性。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報文傳送報文傳送v進(jìn)程通訊的表示方法：報文傳送和共享數(shù)據(jù)進(jìn)程通訊的表示方法：報文傳送和共享數(shù)據(jù) 設(shè)計(jì)報文傳送的通訊方式應(yīng)思索的問題：可靠的報文傳送和非可靠的報文傳送：可靠的報文傳送需求成認(rèn)報文。顯式接納和隱式接納：顯式接納時，接納者執(zhí)行某一類accept語句指明接納哪些報文，以及當(dāng)報文到達(dá)時采取什么行動。運(yùn)

12、用隱式接納時，在接納者內(nèi)自動調(diào)用程序，通常在接納進(jìn)程中創(chuàng)建一個新的線程。 直接命名和間接命名：直接命名用于指示一個指定的進(jìn)程，名字可以是該進(jìn)程的靜態(tài)名字或是一個表達(dá)式。間接命名包括一個中間對象，通常叫做郵箱，發(fā)送者把報文送給它，接納者從它那接納。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報文傳送報文傳送v進(jìn)程通訊的表示方法：報文傳送和共享數(shù)據(jù)進(jìn)程通訊的表示方法：報文傳送和共享數(shù)據(jù) 設(shè)計(jì)報文傳送的通訊方式應(yīng)思索的問題：對稱命名和非對稱命名。假設(shè)發(fā)送者和接納者相互命名，那么基于直接命名的方案是對稱的。在非對稱方案中，僅發(fā)送者找

13、接納者，在此情況下，接納者要與任何發(fā)送者相互作用。留意，運(yùn)用隱式接納報文的相互作用在命名方面總是非對稱的。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報文傳送報文傳送報文傳送通訊方式有 ：同步和異步點(diǎn)到點(diǎn)報文。在同步報文傳送方式中，發(fā)送者在接納者接納報文前不斷阻塞。這樣，雙方不僅交換了數(shù)據(jù)而且還到達(dá)同步。在異步報文傳送方式中，發(fā)送者并不等待接納者預(yù)備好接納其報文，發(fā)送者在送出報文后立刻繼續(xù)任務(wù)。 會合。在Ada中會合模型基于三個概念：項(xiàng)闡明、項(xiàng)調(diào)用和接受語句。項(xiàng)闡明和接受語句是效力員程序的一部分，項(xiàng)調(diào)用在顧客端。當(dāng)進(jìn)程S調(diào)用

14、進(jìn)程R的一項(xiàng)，R為此項(xiàng)執(zhí)行accept語句時，在S和R之間發(fā)生了相互作用，叫做會合。 accept incr(X: int; Y: out int)do Y:=X+1;end第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報文傳送報文傳送報文傳送通訊方式有 ：遠(yuǎn)程過程調(diào)用(RPC)。它是雙向通訊的另一個原語。當(dāng)進(jìn)程S調(diào)用進(jìn)程R的過程P時，由S提供的P的輸入?yún)?shù)被送給R。當(dāng)R收到調(diào)用懇求時，執(zhí)行過程P，然后把輸出參數(shù)送回給S。執(zhí)行P期間S阻塞，直到輸出參數(shù)前往。這和會合機(jī)構(gòu)不同，在會合機(jī)構(gòu)中，一旦accept語句已執(zhí)行，那么調(diào)用者就

15、不阻塞。 一到多報文傳送。很多用于分布計(jì)算系統(tǒng)的網(wǎng)絡(luò)支持快速的廣播或組通訊設(shè)備。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v共享數(shù)據(jù)共享數(shù)據(jù)假設(shè)兩個進(jìn)程訪問同一個變量，可以實(shí)現(xiàn)另一種通訊方式：一個進(jìn)程對此變量進(jìn)展設(shè)置，另一個進(jìn)程對它進(jìn)展讀。假設(shè)兩個進(jìn)程在同一個機(jī)器上運(yùn)轉(zhuǎn)，變量在此機(jī)器上存儲，那么可直接通訊。分布進(jìn)程的共享數(shù)據(jù)方法有：分布式數(shù)據(jù)構(gòu)造和共享的邏輯變量 。分布式數(shù)據(jù)構(gòu)造。這種數(shù)據(jù)構(gòu)造可由假設(shè)干進(jìn)程同時處置。Linda言語運(yùn)用元組空間(tuple space)的概念實(shí)現(xiàn)分布式數(shù)據(jù)構(gòu)造。例如“jones,31,true

16、是一個有三個段的元組：一個字符串、一個整數(shù)和一個布爾值。對TS定義了三個原子操作：out操作向TS參與一個元組，read讀TS中的一個元組，in讀TS中的一個元組并刪除它。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v共享數(shù)據(jù)共享數(shù)據(jù)共享的邏輯變量。邏輯變量具有“單賦值性質(zhì)，最初，它們是未賦值的，但一旦它們接納一個值就不能改動它們。這些變量被用于進(jìn)程之間的通訊通道。如下三個目的：goal_1(X,Y), goal_2(X,Y), goal_3(X)進(jìn)展邏輯乘，用進(jìn)程P1、P2、P3并行求解。變量X是這三個進(jìn)程的通訊通道，最初是

17、未賦值的。假設(shè)三個進(jìn)程中的某個給X賦值，那么其它兩個進(jìn)程可運(yùn)用此值。類似地，Y是P1和P2的通訊通道。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v非確定性的表示和控制非確定性的表示和控制 v進(jìn)程之間的相互作用方式并不總是確定性的，有時還進(jìn)程之間的相互作用方式并不總是確定性的，有時還決議于運(yùn)轉(zhuǎn)時條件。因此，表示和控制非確定性模型被決議于運(yùn)轉(zhuǎn)時條件。因此，表示和控制非確定性模型被提出。選擇語句和維護(hù)的提出。選擇語句和維護(hù)的(guarded)Horn子句子句 是兩種表是兩種表示和控制非確定性的模型。示和控制非確定性的模型。選擇語句

18、。它是由如下方式的一組維護(hù)命令組成的： 維護(hù)語句 其中維護(hù)(guard)由一個布爾表達(dá)式和某一類“通訊懇求組成。布爾表達(dá)式必需無副作用，由于它能夠在執(zhí)行該選擇語句過程中被計(jì)算多次。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v非確定性的表示和控制非確定性的表示和控制 維護(hù)的Horn子句。邏輯程序本質(zhì)上就不是確定性的。并行邏輯言語不是對一給定的謂詞一個又一個地實(shí)驗(yàn)子句，失敗時回溯，而是并行地搜索一切那些子句，并且在這些并行執(zhí)行期間直到有一個并行執(zhí)行提交前不允許任何賦值對外部是可見的，這叫做OR并行性。但是，這不能無限地進(jìn)展，由于

19、并行任務(wù)的搜索途徑隨證明的長度而指數(shù)地增長。 很普遍的控制OR并行性技術(shù)是提交選擇非確定性，它非確定地選擇一個可選擇的子句，取消其他子句。它是基于維護(hù)的Horn子句，方式如下：A:-G1,Gn|B1,Bmn0,m0目的Gi的合取(與操作)叫做維護(hù)，目的Bi的合取叫做體(body)。提交操作符“|也是一個合取操作符。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v分布式程序設(shè)計(jì)言語的分類：分布式程序設(shè)計(jì)言語的分類： 分布式程序設(shè)計(jì)言語分布地址空間共享地址空間同步報文傳送異步報文傳送會合遠(yuǎn)程過程調(diào)用多重原語對象原子事務(wù)處置函

20、數(shù)式言語邏輯言語分布數(shù)據(jù)構(gòu)造第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v同步式報文傳送言語同步式報文傳送言語 ： 創(chuàng)建并行進(jìn)程：如CSP提供簡單的并行命令創(chuàng)建固定數(shù)目的并行進(jìn)程。進(jìn)程包含名字、邏輯變量和一系列語句(進(jìn)程體)。 CSP可以創(chuàng)建一組類似的進(jìn)程，但其數(shù)目必需在編譯時是個常數(shù)。例如并行語句writer:X:real;|reader(i:1.2): 創(chuàng)建三個進(jìn)程，叫作“writer、“reader(1)和“reader(2)。Writer有一個部分變量X。下標(biāo)量i可在reader進(jìn)程的體中運(yùn)用。 通訊：CSP進(jìn)程

21、不能運(yùn)用全局變量相互通訊，只能運(yùn)用同步的receive和send。執(zhí)行send或receive的進(jìn)程受阻不斷到其對方執(zhí)行完互補(bǔ)的語句為止。例如X:Y! 3|Y:n:integer;X? n在進(jìn)程X的語句中，把值3發(fā)送給Y。在進(jìn)程Y的語句中，從進(jìn)程X讀取輸入，并存放到部分變量n中。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v同步式報文傳送言語同步式報文傳送言語 ： 可傳送的數(shù)據(jù)類型：簡單數(shù)據(jù)和有構(gòu)造的數(shù)據(jù)均可傳送與賦值，只需發(fā)送的值與接納它的變量類型一樣?？山o有構(gòu)造的數(shù)據(jù)一個名字(構(gòu)造符)，如下例中的pair：X:Y!

22、 pair(35,60)|Y:n,m:integer;X? pair(n,m)可運(yùn)用空構(gòu)造符對兩個進(jìn)程進(jìn)展同步但不傳送任何實(shí)踐數(shù)據(jù)。非確定性的表示：CSP中運(yùn)用alternative構(gòu)造表示非確定性，它由一組維護(hù)(后面跟著待執(zhí)行的動作)組成。維護(hù)可包含布爾表達(dá)式和一個輸入語句。CSP允許進(jìn)程根據(jù)當(dāng)前通訊的輸入和名字段的信息有選擇地接納。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v異步式報文傳送言語異步式報文傳送言語 ： 并行性單位：NIL中的并行性是基于所謂進(jìn)程模型。進(jìn)程不僅是并行性的單位，也是模塊化的單位。進(jìn)程四處

23、置機(jī)變換是實(shí)現(xiàn)上的問題，由編譯和運(yùn)轉(zhuǎn)時系統(tǒng)處置。 NIL可動態(tài)地進(jìn)展進(jìn)程間通訊途徑的配置：NIL中的信口是一個排隊(duì)的通訊通道。在給定時間，一個信口有一個指定的一切者。一切者關(guān)系可以轉(zhuǎn)讓給其他進(jìn)程，可以把信口作為報文的一部分傳送，或把信口作為一個新創(chuàng)建進(jìn)程的初始化參數(shù)傳送。進(jìn)程可以銜接其擁有的輸入口和輸出口。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v異步式報文傳送言語異步式報文傳送言語 ： 通訊類型：NIL既支持同步通訊也支持異步通訊，可把單個輸入口銜接到幾個輸出口，所以在輸入口可以有多個掛起的報文，因此必需排隊(duì)。非

24、確定表示：NIL提供一個維護(hù)命令風(fēng)格的語句用于在任何輸入口上等待報文。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v基于會合的言語基于會合的言語 ： Ada:并行性表示：其并行性是基于順序進(jìn)程，叫作義務(wù)(task)，每個義務(wù)具有一定的類型。義務(wù)由闡明部分(闡明其他義務(wù)如何與其通訊)和一個體(包含它的可以執(zhí)行的語句)組成。通訊：義務(wù)通常經(jīng)過會合機(jī)制通訊，也經(jīng)過共享變量通訊，會合機(jī)制基于項(xiàng)闡明、項(xiàng)調(diào)用和接受語句。 非確定性表示：Ada運(yùn)用select語句表示非確定性。這個語句用于三個目的：從一組未處置的懇求中非確定地選擇一

25、個項(xiàng)調(diào)用；有條件地調(diào)用一項(xiàng)(即僅當(dāng)被調(diào)用的義務(wù)預(yù)備好立刻接受它)和為一個項(xiàng)調(diào)用設(shè)置時限。 容錯：Ada有一個異常處置機(jī)制處置軟件缺點(diǎn)，但言語定義未闡明硬件缺點(diǎn)問題。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v基于會合的言語基于會合的言語 ： 并發(fā)C:進(jìn)程創(chuàng)建：它運(yùn)用create原語顯式地創(chuàng)建進(jìn)程，并可向創(chuàng)建的進(jìn)程傳送參數(shù)?？少x給新進(jìn)程一個優(yōu)先權(quán)，以后新進(jìn)程或其他進(jìn)程還可以改動此優(yōu)先權(quán)。通訊：進(jìn)程經(jīng)過會合機(jī)構(gòu)相互通訊。并發(fā)C中的事務(wù)處置與Ada中的項(xiàng)不同，可以前往一個值，并支持異步事務(wù)處置(但并不前往值)。并發(fā)C支持一

26、個比Ada中的功能更強(qiáng)的accept語句，它根據(jù)事務(wù)處置參數(shù)的值，可以有條件地接受一些事務(wù)處置 。非確定性表示：運(yùn)用select語句表示非確定性。容錯：基于進(jìn)程復(fù)制。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v基于遠(yuǎn)程過程調(diào)用的言語基于遠(yuǎn)程過程調(diào)用的言語 ： DP的進(jìn)程：每個處置機(jī)公用于執(zhí)行一個進(jìn)程，但每個進(jìn)程可包含幾個處置線程，這些線程以偽并行方式運(yùn)轉(zhuǎn)。通訊：DP進(jìn)程相互調(diào)用對方的公用過程進(jìn)展通訊，用如下方式調(diào)用： Call P.f(exps,vars)這里P是被調(diào)用進(jìn)程的名字，f是由P闡明的過程名字，表達(dá)式是輸入

27、參數(shù)，前往值賦予變量vars。第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v多重通訊原語多重通訊原語 ： SR是由一個或多個資源(resource)組成。資源是運(yùn)轉(zhuǎn)在一個物理節(jié)點(diǎn)(單處置機(jī)或共享存儲器多處置機(jī))的一個程序模塊，可動態(tài)創(chuàng)建，并可選擇地分配到指定機(jī)器上運(yùn)轉(zhuǎn)。 資源可包含多個進(jìn)程，它們共享數(shù)據(jù)。資源可包含一個初始進(jìn)程和終結(jié)進(jìn)程，它們隱式地被創(chuàng)建和運(yùn)轉(zhuǎn)。 SR運(yùn)用類似于select語句的構(gòu)造處置非確定性。 SR操作的定義類似過程的定義，可看成一個過程或入口點(diǎn)(entry point)。 第三章第三章 分布式程序設(shè)

28、計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v多重通訊原語多重通訊原語 ： 把操作的兩種效力方式和兩種調(diào)用方式結(jié)合起來就有四種進(jìn)程通訊方法 。 call(同步)send(異步)entry(同步)會合報文傳送process(異步)RPCFork第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v基于對象的言語基于對象的言語 ： 對象：Emerald把一切實(shí)體都看成對象。對象可以是自動的或被動的。并行性：Emerald中的并行性表如今自動對象的同時執(zhí)行上。一些對象可從一個處置機(jī)上遷移

29、到另一個上。 分布式系統(tǒng)中，很多對象可以并行運(yùn)轉(zhuǎn)，Emerald為本地和遠(yuǎn)程調(diào)用提供一樣的語義。 對象的遷移可由編譯程序或程序員運(yùn)用幾個簡單原語發(fā)動。對象可作為遠(yuǎn)程操作中的參數(shù)傳送。對該參數(shù)對象的每次訪問都會產(chǎn)生另一個遠(yuǎn)程調(diào)用。為了使這類調(diào)用最正確化，先把參數(shù)對象傳送到目的處置機(jī)，后把該對象傳送回來。由于這種情況經(jīng)常發(fā)生，所以引入一個新的參數(shù)傳送類型，叫做傳送調(diào)用(call_by_move)以便有效地完成這種操作。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.4 3.4 邏輯上分布地址空間的言語邏輯上分布地址空間的言語 v基于原子事務(wù)處置的言語基于原子事務(wù)處置的言語 ： Argus

30、: 主要特點(diǎn):guardian(維護(hù)者)和action(活動)。維護(hù)者是能從解體中幸存下來的模塊，而活動是一組原子執(zhí)行。 為了在堅(jiān)持原子語義下允許活動的并行，運(yùn)用原子對象，它是一種原子數(shù)據(jù)類型。Argus提供一些原子類型，用戶也可本人定義一些。 Argus提供兩級同步機(jī)制：用于偽并行進(jìn)程的和用于并行活動的。 mutex類型提供對維護(hù)者內(nèi)各進(jìn)程所共享的對象的互斥訪問。 在容錯方面，可把某些維護(hù)者對象闡明成stable，存放到鞏固存儲器中，假設(shè)某個節(jié)點(diǎn)解體了，那么可在鞏固存儲器中檢索并得到恢復(fù)。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.5 3.5 邏輯上共享地址空間的言語邏輯上共享

31、地址空間的言語 v并行函數(shù)式言語并行函數(shù)式言語 ： ParAlfl利用隱式函數(shù)并行性。函數(shù)并行性通常是細(xì)粒度的。由于能夠有比處置機(jī)數(shù)多得多的義務(wù)要并行執(zhí)行，所以運(yùn)用變換方法指定哪個表達(dá)式在哪臺處置機(jī)上計(jì)算。 如：(f(x) $on ($self-1)+(g(y) $on ($self+1) 通訊和同步是隱式的，所以不需求顯式言語構(gòu)造。某個計(jì)算需求另一個計(jì)算的結(jié)果但還未出來時那么受阻。 語義是基于緩慢計(jì)算(lazy evaluation)，即一個表達(dá)式僅當(dāng)其結(jié)果被要求時才進(jìn)展計(jì)算。普通說來，程序員不需關(guān)懷計(jì)算次序，但為了有效性要對計(jì)算次序進(jìn)展控制。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)

32、言語 3.5 3.5 邏輯上共享地址空間的言語邏輯上共享地址空間的言語 v并行邏輯言語并行邏輯言語 ： 并發(fā)PROLOG ： 并行性來自合取的各目的的AND并行計(jì)算和維護(hù)Horn子句的各維護(hù)的OR并行計(jì)算。 并發(fā)PROLOG中的并行進(jìn)程運(yùn)用共享邏輯變量通訊。同步是基于在只讀變量上暫停的方法。 并發(fā)PROLOG運(yùn)用維護(hù)Horn子句處置非確定性。第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.5 3.5 邏輯上共享地址空間的言語邏輯上共享地址空間的言語 v并行邏輯言語并行邏輯言語 ： PARLOG： AND/OR并行性由程序員控制。有兩種不同的合取操作符：“.并行計(jì)算各合??；“&串

33、行計(jì)算各合取(自左至右)。 進(jìn)程經(jīng)過共享變量進(jìn)展通訊，而同步方法是在無界共享變量上掛起。PARLOG有個機(jī)構(gòu)用來指定哪些進(jìn)程可以為某變量產(chǎn)生賦值。假設(shè)輸入自變量未被賦值，那么相應(yīng)的合一將掛起，當(dāng)某其他進(jìn)程為該變量賦值時此合一將繼續(xù)。 PARLOG運(yùn)用維護(hù)的Horn子句用于非確定性。PARLOG中的維護(hù)可測試任何輸入變量并為子句的部分變量賦值，但不能給在輸入自變量中傳送的變量賦值。第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.5 3.5 邏輯上共享地址空間的言語邏輯上共享地址空間的言語 v基于分布數(shù)據(jù)構(gòu)造言語基于分布數(shù)據(jù)構(gòu)造言語 ： Linda： Linda的目的是將程序員從并行計(jì)算和

34、并發(fā)事件的思索中解脫出來，從而使并行程序設(shè)計(jì)在概念上類似于順序程序設(shè)計(jì)。 Linda運(yùn)用簡單原語eval創(chuàng)建順序進(jìn)程，但不為程序設(shè)計(jì)人員提供方法把進(jìn)程變換四處置機(jī)上，實(shí)踐上并不需求，由于每個處置機(jī)執(zhí)行一個進(jìn)程。 Linda運(yùn)用元組空間通訊模型。進(jìn)程通訊要向TS插入新元組、讀和移去現(xiàn)存的元組。進(jìn)程同步方法是運(yùn)用阻塞read和in操作等待元組可用。 Linda的容錯網(wǎng)絡(luò)內(nèi)核是基于TS的復(fù)制上的。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.5 3.5 邏輯上共享地址空間的言語邏輯上共享地址空間的言語 v基于分布數(shù)據(jù)構(gòu)造言語基于分布數(shù)據(jù)構(gòu)造言語 ： Orca ：這種言語的并行性是基于順序

35、進(jìn)程。運(yùn)用顯式的fork原語派生新的子進(jìn)程并把參數(shù)傳送給它。參數(shù)可以是數(shù)值，也可以是由該子進(jìn)程的闡明部分指出共享的籠統(tǒng)數(shù)據(jù)類型。進(jìn)程之間通訊經(jīng)過共享數(shù)據(jù)對象間接地進(jìn)展。每個對象都屬于籠統(tǒng)數(shù)據(jù)類型，每個籠統(tǒng)數(shù)據(jù)類型的定義由闡明部分和實(shí)現(xiàn)部分組成。闡明部分列出可對該給定類型的對象進(jìn)展的各種操作。一個操作的實(shí)現(xiàn)可由一個或多個維護(hù)語句組成。假設(shè)是這樣，一個操作的調(diào)用受阻直到至少有一個維護(hù)勝利，接著非確定性地選擇一個為真的維護(hù)，執(zhí)行其語句不再受阻。 共享數(shù)據(jù)對象模型在分布式系統(tǒng)中有效的實(shí)現(xiàn)方法是復(fù)制對象。假設(shè)共享對象不經(jīng)常改動，可在經(jīng)常讀它的處置機(jī)上維持副本，對本地副本進(jìn)展讀操作，就可減少通訊開銷。原語

36、 語言的例子并行性表示并行性 進(jìn)程 Ada、并發(fā) C、Linda、NIL 對象 Emerald、并發(fā) Smalltalk 語句 Occam 表達(dá)式 ParAlfl、FX-87 子句 并發(fā) PROLOG、PARLOG變換 靜態(tài) Occam、StarMod 動態(tài) 并發(fā) PROLOG、ParAlfl 遷移 Emerald通信報文傳遞 點(diǎn)到點(diǎn)報文 CSP、Occam、NIL 會合 Ada、并發(fā) C 遠(yuǎn)程過程調(diào)用 DP、并發(fā) CLU、LYNX 一對多報文 BSP、StarMod數(shù)據(jù)共享 分布式數(shù)據(jù)結(jié)構(gòu) Linda、Orca 共享邏輯變量 并發(fā) PROLOG、PARLOG非確定性 選擇語句 CSP、Occ

37、am、Ada、并發(fā) C、SR 保護(hù) Horn 子句 并發(fā) PROLOG、PARLOG部分失效故障檢測 Ada、SR原子事務(wù)處理 Argus、Aeolus、Avalon透明容錯 NIL第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL vDCDL中的通用符號中的通用符號 ： 選擇*重復(fù)|并行條件；順序send輸出：=賦值receive輸入： ：定義開始結(jié)束任意(全稱量詞)存在(存在量詞)=相等不等或且反第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.63.6分布式控制描畫言語分布式控制描畫言語DCDL DCDL vD

38、CDL中并行性表示中并行性表示 ：vDCDL中的并行單元是語句。中的并行單元是語句。v一組并行語句表示為：一組并行語句表示為：vS1|S2|Snv而一組順序語句表示為：而一組順序語句表示為：v S1；S2；Sn v一組語句可以用語句優(yōu)先圖一組語句可以用語句優(yōu)先圖表示表示v S1；S2；S3|S4；S5；S6|S7 S1S2S3S4S7S5S6S1S2S3S4S7S5S6第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v選擇語句選擇語句 ：v一個選擇語句表示為：一個選擇語句表示為：vG1C1G1C1G2C2G2C2GnC

39、nGnCnv選擇語句選擇其組成的被維護(hù)的命令之一執(zhí)行。假設(shè)選擇語句選擇其組成的被維護(hù)的命令之一執(zhí)行。假設(shè)多余一個命令可被選擇，選擇將是不確定的。如下的選多余一個命令可被選擇，選擇將是不確定的。如下的選擇語句擇語句vxym:=xxym:=xyxm:=yyxm:=yv表示假設(shè)表示假設(shè)xyxy，將，將x x賦予賦予mm；假設(shè)；假設(shè)yxyx，將，將y y賦予賦予mm；假設(shè)假設(shè)xyxy并且并且yxyx，那么將，那么將x x或或y y之一賦予之一賦予mm。 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v反復(fù)語句反復(fù)語句 ：v一

40、個反復(fù)語句指定其組成選擇語句的交互次數(shù)，這些一個反復(fù)語句指定其組成選擇語句的交互次數(shù)，這些語句帶維護(hù)或不帶維護(hù)，它的方式有如下三種：語句帶維護(hù)或不帶維護(hù)，它的方式有如下三種：v1 1* * 帶維護(hù)的選擇語句帶維護(hù)的選擇語句 v2 2* * 不帶維護(hù)的選擇語句不帶維護(hù)的選擇語句 v3 3(n)(n)選擇語句選擇語句 v在第一種情況下，當(dāng)一切的維護(hù)都經(jīng)過時，反復(fù)語句在第一種情況下，當(dāng)一切的維護(hù)都經(jīng)過時，反復(fù)語句終止。在第二種情況下，執(zhí)行不終止。第三種是一個特終止。在第二種情況下，執(zhí)行不終止。第三種是一個特別的反復(fù)語句，其反復(fù)的次數(shù)最多為別的反復(fù)語句，其反復(fù)的次數(shù)最多為n n。 第三章第三章 分布式

41、程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v反復(fù)語句反復(fù)語句 ：v例例1 1：給出一個確定的數(shù)組：給出一個確定的數(shù)組b1:m1:nb1:m1:n，其中，其中1m1m，1n1ni:=i+1;j:=1jni:=i+1;j:=1v v 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v反復(fù)語句反復(fù)語句 ：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) 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v語句并發(fā)語句并發(fā)( (或并行或并行) )的條件的條件v當(dāng)兩個語句并發(fā)執(zhí)行時，能夠產(chǎn)生與順序執(zhí)行不同的當(dāng)兩個語句并發(fā)

43、執(zhí)行時，能夠產(chǎn)生與順序執(zhí)行不同的結(jié)果。讓我們先定義兩個符號：結(jié)果。讓我們先定義兩個符號：v(1) R(Si)(1) R(Si)，Si Si的讀集，即在的讀集，即在Si Si中被援用的一切變量中被援用的一切變量的集合。的集合。v(2) W(Si)(2) W(Si)，Si Si的寫集，即在的寫集，即在Si Si中被修正的一切變量中被修正的一切變量的集合。的集合。 vBernsteinBernstein提出了以下三個條件，對于兩個并發(fā)執(zhí)行的提出了以下三個條件，對于兩個并發(fā)執(zhí)行的語句語句S1S1和和S2S2，必需滿足這三個條件才干使它們并發(fā)執(zhí)行，必需滿足這三個條件才干使它們并發(fā)執(zhí)行的結(jié)果與它們以恣意次

44、序順序執(zhí)行的結(jié)果一樣。的結(jié)果與它們以恣意次序順序執(zhí)行的結(jié)果一樣。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)=第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v語句并發(fā)語句并發(fā)( (或并行或并行) )的條件的條件v 我們可以用我們可以用BernsteinBernstein條件來尋覓語句中可以并行執(zhí)條件來尋覓語句中可以并行執(zhí)行的最大子集。為此我們定義了一個無向圖，節(jié)點(diǎn)集行的最大子集。

45、為此我們定義了一個無向圖，節(jié)點(diǎn)集由給定語句集組成，假設(shè)由給定語句集組成，假設(shè)Si|SjSi|Sj，那么節(jié)點(diǎn)，那么節(jié)點(diǎn)Si Si和和Sj Sj相連，相連，可以并行執(zhí)行的最大的語句子集對應(yīng)于最大的完全子可以并行執(zhí)行的最大的語句子集對應(yīng)于最大的完全子圖。圖。 例如：S1: a:=xy, S2: b:=xz, S3: x:=yz, S4: c:=y-1。顯然，S1，S2，S4構(gòu)成最大的完全子圖，也就是說，S1|S2|S4。 S1S2S3S4S1S2S3S4第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v DCDLDCDL中的

46、通訊中的通訊v 輸出命令的方式為：輸出命令的方式為：vsend message_list to destinationsend message_list to destinationv其中其中destinationdestination是一個進(jìn)程名是一個進(jìn)程名( (一對一通訊一對一通訊) )或代或代表一切其他進(jìn)程表一切其他進(jìn)程( (一對一切通訊一對一切通訊) )的關(guān)鍵字的關(guān)鍵字allall。v 輸入命令的方式為：輸入命令的方式為：vreceive message_list from sourcereceive message_list from sourcev其中其中sourcesource是

47、一個進(jìn)程名，這個輸入命令支持顯是一個進(jìn)程名，這個輸入命令支持顯式和隱式的報文接納。式和隱式的報文接納。v隱式的報文接納表示為：隱式的報文接納表示為：vreceive message_listreceive message_list第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語DCDL DCDL v DCDLDCDL中的通訊中的通訊v 例例1 1：用如下遞歸的方法計(jì)算：用如下遞歸的方法計(jì)算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) 第三章第三章 分布式程序設(shè)計(jì)言語分布式程序設(shè)計(jì)言語 3.6 3.6 分布式控制描畫言語分布式控制描畫言語