分布式程序設(shè)計(jì)語(yǔ)言

分布式程序設(shè)計(jì)語(yǔ)言第1頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.1分布式程序設(shè)計(jì)語(yǔ)言概述

分布式程序設(shè)計(jì)與順序程序設(shè)計(jì)的區(qū)別

使用多個(gè)處理機(jī)。對(duì)分布式程序設(shè)計(jì)支持的第一個(gè)要求就是系統(tǒng)應(yīng)該具有把一個(gè)程序的不同部分分配到不同處理機(jī)上執(zhí)行的能力。處理機(jī)合作。各個(gè)進(jìn)程必須能相互通信和同步，這是對(duì)分布式程序設(shè)計(jì)支持的第二個(gè)要求。

處理部分失效。在分布計(jì)算系統(tǒng)中一些CPU失效時(shí)，其他CPU照樣工作。所以對(duì)分布式程序設(shè)計(jì)支持的第三個(gè)要求是能對(duì)系統(tǒng)的部分失效進(jìn)行檢測(cè)并恢復(fù)。第2頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.1分布式程序設(shè)計(jì)語(yǔ)言概述

分布式程序設(shè)計(jì)語(yǔ)言的分類

按并行模型來(lái)分

順序進(jìn)程并行語(yǔ)言。這類語(yǔ)言使用的最基本模型是一組順序進(jìn)程，它們并行運(yùn)行，并且通過(guò)報(bào)文傳遞進(jìn)行通信。大部分是流行的C(或C++)和FORTRAN的擴(kuò)展。具有內(nèi)在并行性的語(yǔ)言。一些研究者認(rèn)為算法語(yǔ)言不是處理并行性的最好語(yǔ)言，因?yàn)樗惴ㄕZ(yǔ)言是內(nèi)在順序式的，許多研究者研究具有內(nèi)在并行性的語(yǔ)言，如函數(shù)式語(yǔ)言、邏輯語(yǔ)言和面向?qū)ο笳Z(yǔ)言。第3頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.1分布式程序設(shè)計(jì)語(yǔ)言概述

分布式程序設(shè)計(jì)語(yǔ)言的分類

按通信模型來(lái)分

在物理分布的硬件上運(yùn)行邏輯上分布的軟件。相互使用SEND和RECEIVE原語(yǔ)通信，在網(wǎng)絡(luò)上發(fā)送報(bào)文。在物理非分布的硬件上運(yùn)行邏輯上分布的軟件。用共享主存方法實(shí)現(xiàn)報(bào)文傳遞來(lái)模擬物理報(bào)文傳遞通信。在物理分布的硬件上運(yùn)行邏輯上非分布的軟件。使用分布式共享存儲(chǔ)器通信。在物理非分布的硬件上運(yùn)行邏輯上非分布的軟件。使用物理共享存儲(chǔ)器通信。第4頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.1分布式程序設(shè)計(jì)語(yǔ)言概述

分布式程序設(shè)計(jì)語(yǔ)言的分類

容錯(cuò)模型和技術(shù)故障的處理模型：系統(tǒng)對(duì)程序員隱匿全部處理機(jī)故障。給程序員提供高層機(jī)制，使得程序員能夠描述哪些進(jìn)程和數(shù)據(jù)是重要的，以及發(fā)生崩潰后怎樣恢復(fù)。實(shí)現(xiàn)可靠性的方法有兩種：程序設(shè)計(jì)容錯(cuò)和通信容錯(cuò)。程序設(shè)計(jì)容錯(cuò)技術(shù)有三類：向前恢復(fù)試圖確定錯(cuò)誤所在并基于這個(gè)知識(shí)改正包含錯(cuò)誤的系統(tǒng)狀態(tài)；向后恢復(fù)通過(guò)把系統(tǒng)恢復(fù)到錯(cuò)誤發(fā)生前的狀態(tài)來(lái)改正系統(tǒng)狀態(tài)；錯(cuò)誤屏蔽，利用同一個(gè)算法獨(dú)立開(kāi)發(fā)幾個(gè)版本，一個(gè)最后投票系統(tǒng)用于對(duì)這n個(gè)版本產(chǎn)生的結(jié)果進(jìn)行投票并確定一個(gè)正確的結(jié)果。通信容錯(cuò)處理進(jìn)程通信中發(fā)生的故障，通信容錯(cuò)依賴于使用的通信方式和故障的類型。第5頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.2并行性的支持

并行性的概念

并行性。因?yàn)榉植加?jì)算系統(tǒng)有多個(gè)處理機(jī)，所以可把程序分成若干部放到多個(gè)處理機(jī)上同時(shí)運(yùn)行，這就是所謂的并行性。偽并行性(pseudoparallelism)，即把程序表示為一組并行運(yùn)行的進(jìn)程但不管它們是否在不同的處理機(jī)上同時(shí)運(yùn)行。并行粒度。并行單位可以是進(jìn)程(如并發(fā)C)，也可以是表達(dá)式(如ParAlfl)。一般說(shuō)來(lái)，通信代價(jià)越大，則并行的粒度就應(yīng)該越大。第6頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.2并行性的支持

并行性的表示

進(jìn)程并行。一般說(shuō)來(lái)，一個(gè)進(jìn)程是一個(gè)邏輯處理機(jī)，順序地執(zhí)行代碼，具有自己的狀態(tài)和數(shù)據(jù)。在語(yǔ)言中，進(jìn)程或進(jìn)程類型是要被說(shuō)明的，就像過(guò)程或過(guò)程類型一樣。進(jìn)程的創(chuàng)建可以由說(shuō)明隱式地完成，也可以通過(guò)創(chuàng)建某種結(jié)構(gòu)顯式地完成。對(duì)象并行。用下述方法擴(kuò)充順序?qū)ο竽Ｐ涂色@得并行性：(1)允許對(duì)象不必在收到報(bào)文時(shí)才活動(dòng)；(2)允許接收對(duì)象在返回結(jié)果后繼續(xù)執(zhí)行；第(3)一次向幾個(gè)對(duì)象發(fā)送報(bào)文；(4)允許報(bào)文發(fā)送者繼續(xù)和接收者并行工作。第7頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.2并行性的支持

并行性的表示

語(yǔ)句并行PARj=0FORn A[j]：=A[j]+1

PAR S1 S2第8頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.2并行性的支持

并行性的表示

函數(shù)并行例如表達(dá)式h(f(3,4),g(8))，先計(jì)算f或g是沒(méi)有關(guān)系的，從而可以并行計(jì)算f和g。子句的并行下面的程序給出謂詞A的兩個(gè)子句：(1)A:-B,C,D(2)A:-E,F存在兩個(gè)并行性的機(jī)會(huì)：(1)A的兩個(gè)子句可并行工作只到有一個(gè)成功或兩個(gè)都失敗。(2)每個(gè)子句中的子定理可并行工作直到它們?nèi)汲晒Γ蚱渲幸粋€(gè)失敗。前一種并行性叫做OR并行性，后一種叫做AND并行性。第9頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

報(bào)文傳遞進(jìn)程通信的表示方法：報(bào)文傳遞和共享數(shù)據(jù)設(shè)計(jì)報(bào)文傳遞的通信方式應(yīng)考慮的問(wèn)題：可靠的報(bào)文傳遞和非可靠的報(bào)文傳遞：可靠的報(bào)文傳遞需要承認(rèn)報(bào)文。顯式接收和隱式接收：顯式接收時(shí)，接收者執(zhí)行某一類accept語(yǔ)句指明接收哪些報(bào)文，以及當(dāng)報(bào)文到達(dá)時(shí)采取什么行動(dòng)。使用隱式接收時(shí)，在接收者內(nèi)自動(dòng)調(diào)用程序，通常在接收進(jìn)程中創(chuàng)建一個(gè)新的線程。

直接命名和間接命名：直接命名用于指示一個(gè)指定的進(jìn)程，名字可以是該進(jìn)程的靜態(tài)名字或是一個(gè)表達(dá)式。間接命名包括一個(gè)中間對(duì)象，通常叫做郵箱，發(fā)送者把報(bào)文送給它，接收者從它那接收。第10頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

報(bào)文傳遞進(jìn)程通信的表示方法：報(bào)文傳遞和共享數(shù)據(jù)設(shè)計(jì)報(bào)文傳遞的通信方式應(yīng)考慮的問(wèn)題：對(duì)稱命名和非對(duì)稱命名。如果發(fā)送者和接收者相互命名，則基于直接命名的方案是對(duì)稱的。在非對(duì)稱方案中，僅發(fā)送者找接收者，在此情況下，接收者要與任何發(fā)送者相互作用。注意，使用隱式接收?qǐng)?bào)文的相互作用在命名方面總是非對(duì)稱的。第11頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

報(bào)文傳遞報(bào)文傳遞通信模式有：同步和異步點(diǎn)到點(diǎn)報(bào)文。在同步報(bào)文傳送方式中，發(fā)送者在接收者接收?qǐng)?bào)文前一直阻塞。這樣，雙方不僅交換了數(shù)據(jù)而且還達(dá)到同步。在異步報(bào)文傳送方式中，發(fā)送者并不等待接收者準(zhǔn)備好接收其報(bào)文，發(fā)送者在送出報(bào)文后立即繼續(xù)工作。會(huì)合。在Ada中會(huì)合模型基于三個(gè)概念：項(xiàng)說(shuō)明、項(xiàng)調(diào)用和接受語(yǔ)句。項(xiàng)說(shuō)明和接受語(yǔ)句是服務(wù)員程序的一部分，項(xiàng)調(diào)用在顧客端。當(dāng)進(jìn)程S調(diào)用進(jìn)程R的一項(xiàng)，R為此項(xiàng)執(zhí)行accept語(yǔ)句時(shí)，在S和R之間發(fā)生了相互作用，叫做會(huì)合。

acceptincr(X:int;Y:outint) doY:=X+1; end第12頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

報(bào)文傳遞報(bào)文傳遞通信模式有：遠(yuǎn)程過(guò)程調(diào)用(RPC)。它是雙向通信的另一個(gè)原語(yǔ)。當(dāng)進(jìn)程S調(diào)用進(jìn)程R的過(guò)程P時(shí)，由S提供的P的輸入?yún)?shù)被送給R。當(dāng)R收到調(diào)用請(qǐng)求時(shí)，執(zhí)行過(guò)程P，然后把輸出參數(shù)送回給S。執(zhí)行P期間S阻塞，直到輸出參數(shù)返回。這和會(huì)合機(jī)構(gòu)不同，在會(huì)合機(jī)構(gòu)中，一旦accept語(yǔ)句已執(zhí)行，則調(diào)用者就不阻塞。一到多報(bào)文傳送。很多用于分布計(jì)算系統(tǒng)的網(wǎng)絡(luò)支持快速的廣播或組通信設(shè)施。第13頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

共享數(shù)據(jù)如果兩個(gè)進(jìn)程訪問(wèn)同一個(gè)變量，可以實(shí)現(xiàn)另一種通信方式：一個(gè)進(jìn)程對(duì)此變量進(jìn)行設(shè)置，另一個(gè)進(jìn)程對(duì)它進(jìn)行讀。如果兩個(gè)進(jìn)程在同一個(gè)機(jī)器上運(yùn)行，變量在此機(jī)器上存儲(chǔ)，則可直接通信。分布進(jìn)程的共享數(shù)據(jù)方法有：分布式數(shù)據(jù)結(jié)構(gòu)和共享的邏輯變量。分布式數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)可由若干進(jìn)程同時(shí)處理。Linda語(yǔ)言使用元組空間(tuplespace)的概念實(shí)現(xiàn)分布式數(shù)據(jù)結(jié)構(gòu)。例如[“jones”,31,true]是一個(gè)有三個(gè)段的元組：一個(gè)字符串、一個(gè)整數(shù)和一個(gè)布爾值。對(duì)TS定義了三個(gè)原子操作：out操作向TS加入一個(gè)元組，read讀TS中的一個(gè)元組，in讀TS中的一個(gè)元組并刪除它。第14頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

共享數(shù)據(jù)共享的邏輯變量。邏輯變量具有“單賦值”性質(zhì)，最初，它們是未賦值的，但一旦它們接收一個(gè)值就不能改變它們。這些變量被用于進(jìn)程之間的通信通道。如下三個(gè)目標(biāo)：goal_1(X,Y),goal_2(X,Y),goal_3(X)

進(jìn)行邏輯乘，用進(jìn)程P1、P2、P3并行求解。變量X是這三個(gè)進(jìn)程的通信通道，最初是未賦值的。如果三個(gè)進(jìn)程中的某個(gè)給X賦值，則其它兩個(gè)進(jìn)程可使用此值。類似地，Y是P1和P2的通信通道。第15頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

非確定性的表示和控制進(jìn)程之間的相互作用模式并不總是確定性的，有時(shí)還決定于運(yùn)行時(shí)條件。因此，表示和控制非確定性模型被提出。選擇語(yǔ)句和保護(hù)的(guarded)Horn子句是兩種表示和控制非確定性的模型。選擇語(yǔ)句。它是由如下形式的一組保護(hù)命令組成的： 保護(hù)→語(yǔ)句 其中保護(hù)(guard)由一個(gè)布爾表達(dá)式和某一類“通信請(qǐng)求”組成。布爾表達(dá)式必須無(wú)副作用，因?yàn)樗赡茉趫?zhí)行該選擇語(yǔ)句過(guò)程中被計(jì)算多次。第16頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.3進(jìn)程通信與同步的支持

非確定性的表示和控制保護(hù)的Horn子句。邏輯程序本質(zhì)上就不是確定性的。 并行邏輯語(yǔ)言不是對(duì)一給定的謂詞一個(gè)又一個(gè)地試驗(yàn)子句，失敗時(shí)回溯，而是并行地搜索所有那些子句，并且在這些并行執(zhí)行期間直到有一個(gè)并行執(zhí)行提交前不允許任何賦值對(duì)外部是可見(jiàn)的，這叫做OR并行性。但是，這不能無(wú)限地進(jìn)行，因?yàn)椴⑿泄ぷ鞯乃阉髀窂诫S證明的長(zhǎng)度而指數(shù)地增長(zhǎng)。 很普遍的控制OR并行性技術(shù)是提交選擇非確定性，它非確定地選擇一個(gè)可選擇的子句，取消其他子句。它是基于保護(hù)的Horn子句，形式如下：

A:-G1,…,Gn|B1,…,Bm n≥0,m≥0

目標(biāo)Gi的合取(與操作)叫做保護(hù)，目標(biāo)Bi的合取叫做體(body)。提交操作符“|”也是一個(gè)合取操作符。第17頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

分布式程序設(shè)計(jì)語(yǔ)言的分類：分布式程序設(shè)計(jì)語(yǔ)言分布地址空間

共享地址空間同步報(bào)文傳送異步報(bào)文傳送會(huì)合遠(yuǎn)程過(guò)程調(diào)用多重原語(yǔ)對(duì)象原子事務(wù)處理函數(shù)式語(yǔ)言邏輯語(yǔ)言分布數(shù)據(jù)結(jié)構(gòu)第18頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

同步式報(bào)文傳遞語(yǔ)言：創(chuàng)建并行進(jìn)程： 如CSP提供簡(jiǎn)單的并行命令創(chuàng)建固定數(shù)目的并行進(jìn)程。進(jìn)程包含名字、邏輯變量和一系列語(yǔ)句(進(jìn)程體)。CSP可以創(chuàng)建一組相似的進(jìn)程，但其數(shù)目必須在編譯時(shí)是個(gè)常數(shù)。例如并行語(yǔ)句

[writer::X:real;…||reader(i:1..2)::…]

創(chuàng)建三個(gè)進(jìn)程，叫作“writer”、“reader(1)”和“reader(2)”。Writer有一個(gè)局部變量X。下標(biāo)量i可在reader進(jìn)程的體中使用。通信：

CSP進(jìn)程不能使用全局變量相互通信，只能使用同步的receive和send。執(zhí)行send或receive的進(jìn)程受阻一直到其對(duì)方執(zhí)行完互補(bǔ)的語(yǔ)句為止。例如

[X::Y!3||Y::n:integer;X?n]

在進(jìn)程X的語(yǔ)句中，把值3發(fā)送給Y。在進(jìn)程Y的語(yǔ)句中，從進(jìn)程X讀取輸入，并存放到局部變量n中。第19頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

同步式報(bào)文傳遞語(yǔ)言：可傳遞的數(shù)據(jù)類型： 簡(jiǎn)單數(shù)據(jù)和有結(jié)構(gòu)的數(shù)據(jù)均可傳送與賦值，只要發(fā)送的值與接收它的變量類型相同。可給有結(jié)構(gòu)的數(shù)據(jù)一個(gè)名字(構(gòu)造符)，如下例中的pair：

[X::Y!pair(35,60)||Y::n,m:integer;X?pair(n,m)]

可使用空構(gòu)造符對(duì)兩個(gè)進(jìn)程進(jìn)行同步但不傳送任何實(shí)際數(shù)據(jù)。非確定性的表示：

CSP中使用alternative結(jié)構(gòu)表示非確定性，它由一組保護(hù)(后面跟著待執(zhí)行的動(dòng)作)組成。保護(hù)可包含布爾表達(dá)式和一個(gè)輸入語(yǔ)句。CSP允許進(jìn)程根據(jù)當(dāng)前通信的輸入和名字段的信息有選擇地接收。第20頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

異步式報(bào)文傳遞語(yǔ)言：并行性單位：NIL中的并行性是基于所謂進(jìn)程模型。進(jìn)程不僅是并行性的單位，也是模塊化的單位。進(jìn)程到處理機(jī)變換是實(shí)現(xiàn)上的問(wèn)題，由編譯和運(yùn)行時(shí)系統(tǒng)處理。

NIL可動(dòng)態(tài)地進(jìn)行進(jìn)程間通信路徑的配置：NIL中的信口是一個(gè)排隊(duì)的通信通道。在給定時(shí)間，一個(gè)信口有一個(gè)指定的所有者。所有者關(guān)系可以轉(zhuǎn)讓給其他進(jìn)程，可以把信口作為報(bào)文的一部分傳送，或把信口作為一個(gè)新創(chuàng)建進(jìn)程的初始化參數(shù)傳送。進(jìn)程可以連接其擁有的輸入口和輸出口。第21頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

異步式報(bào)文傳遞語(yǔ)言：通信類型：NIL既支持同步通信也支持異步通信，可把單個(gè)輸入口連接到幾個(gè)輸出口，所以在輸入口可以有多個(gè)掛起的報(bào)文，因而必須排隊(duì)。非確定表示：NIL提供一個(gè)保護(hù)命令風(fēng)格的語(yǔ)句用于在任何輸入口上等待報(bào)文。第22頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

基于會(huì)合的語(yǔ)言：Ada:并行性表示：其并行性是基于順序進(jìn)程，叫作任務(wù)(task)，每個(gè)任務(wù)具有一定的類型。任務(wù)由說(shuō)明部分(說(shuō)明其他任務(wù)如何與其通信)和一個(gè)體(包含它的可以執(zhí)行的語(yǔ)句)組成。通信：任務(wù)通常通過(guò)會(huì)合機(jī)制通信，也通過(guò)共享變量通信，會(huì)合機(jī)制基于項(xiàng)說(shuō)明、項(xiàng)調(diào)用和接受語(yǔ)句。非確定性表示：Ada使用select語(yǔ)句表示非確定性。這個(gè)語(yǔ)句用于三個(gè)目的：從一組未處理的請(qǐng)求中非確定地選擇一個(gè)項(xiàng)調(diào)用；有條件地調(diào)用一項(xiàng)(即僅當(dāng)被調(diào)用的任務(wù)準(zhǔn)備好立即接受它)和為一個(gè)項(xiàng)調(diào)用設(shè)置時(shí)限。容錯(cuò)：Ada有一個(gè)異常處理機(jī)制處理軟件故障，但語(yǔ)言定義未說(shuō)明硬件故障問(wèn)題。第23頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

基于會(huì)合的語(yǔ)言：并發(fā)C:進(jìn)程創(chuàng)建：它使用create原語(yǔ)顯式地創(chuàng)建進(jìn)程，并可向創(chuàng)建的進(jìn)程傳送參數(shù)。可賦給新進(jìn)程一個(gè)優(yōu)先權(quán)，以后新進(jìn)程或其他進(jìn)程還可以改變此優(yōu)先權(quán)。通信：進(jìn)程通過(guò)會(huì)合機(jī)構(gòu)相互通信。并發(fā)C中的事務(wù)處理與Ada中的項(xiàng)不同，可以返回一個(gè)值，并支持異步事務(wù)處理(但并不返回值)。并發(fā)C支持一個(gè)比Ada中的功能更強(qiáng)的accept語(yǔ)句，它根據(jù)事務(wù)處理參數(shù)的值，可以有條件地接受一些事務(wù)處理。非確定性表示：使用select語(yǔ)句表示非確定性。容錯(cuò)：基于進(jìn)程復(fù)制。第24頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

基于遠(yuǎn)程過(guò)程調(diào)用的語(yǔ)言：DP的進(jìn)程：每個(gè)處理機(jī)專用于執(zhí)行一個(gè)進(jìn)程，但每個(gè)進(jìn)程可包含幾個(gè)處理線程，這些線程以偽并行方式運(yùn)行。通信：DP進(jìn)程相互調(diào)用對(duì)方的公用過(guò)程進(jìn)行通信，用如下形式調(diào)用：

CallP.f(exps,vars)

這里P是被調(diào)用進(jìn)程的名字，f是由P說(shuō)明的過(guò)程名字，表達(dá)式是輸入?yún)?shù)，返回值賦予變量vars。第25頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

多重通信原語(yǔ)：SR是由一個(gè)或多個(gè)資源(resource)組成。資源是運(yùn)行在一個(gè)物理節(jié)點(diǎn)(單處理機(jī)或共享存儲(chǔ)器多處理機(jī))的一個(gè)程序模塊，可動(dòng)態(tài)創(chuàng)建，并可選擇地分配到指定機(jī)器上運(yùn)行。資源可包含多個(gè)進(jìn)程，它們共享數(shù)據(jù)。資源可包含一個(gè)初始進(jìn)程和終結(jié)進(jìn)程，它們隱式地被創(chuàng)建和運(yùn)行。SR使用類似于select語(yǔ)句的結(jié)構(gòu)處理非確定性。SR操作的定義類似過(guò)程的定義，可看成一個(gè)過(guò)程或入口點(diǎn)(entrypoint)。第26頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

多重通信原語(yǔ)：把操作的兩種服務(wù)方式和兩種調(diào)用方式結(jié)合起來(lái)就有四種進(jìn)程通信方法。

call(同步)send(異步)entry(同步)會(huì)合報(bào)文傳送process(異步)RPCFork第27頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

基于對(duì)象的語(yǔ)言：對(duì)象：Emerald把所有實(shí)體都看成對(duì)象。對(duì)象可以是主動(dòng)的或被動(dòng)的。并行性：Emerald中的并行性表現(xiàn)在主動(dòng)對(duì)象的同時(shí)執(zhí)行上。一些對(duì)象可從一個(gè)處理機(jī)上遷移到另一個(gè)上。分布式系統(tǒng)中，很多對(duì)象可以并行運(yùn)行，Emerald為本地和遠(yuǎn)程調(diào)用提供相同的語(yǔ)義。對(duì)象的遷移可由編譯程序或程序員使用幾個(gè)簡(jiǎn)單原語(yǔ)發(fā)動(dòng)。對(duì)象可作為遠(yuǎn)程操作中的參數(shù)傳送。對(duì)該參數(shù)對(duì)象的每次訪問(wèn)都會(huì)產(chǎn)生另一個(gè)遠(yuǎn)程調(diào)用。為了使這類調(diào)用最佳化，先把參數(shù)對(duì)象傳送到目的處理機(jī)，后把該對(duì)象傳送回來(lái)。因?yàn)檫@種情況經(jīng)常發(fā)生，所以引入一個(gè)新的參數(shù)傳送類型，叫做傳送調(diào)用(call_by_move)以便有效地完成這種操作。

第28頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.4邏輯上分布地址空間的語(yǔ)言

基于原子事務(wù)處理的語(yǔ)言：Argus:主要特點(diǎn):guardian(保護(hù)者)和action(活動(dòng))。保護(hù)者是能從崩潰中幸存下來(lái)的模塊，而活動(dòng)是一組原子執(zhí)行。為了在保持原子語(yǔ)義下允許活動(dòng)的并行，使用原子對(duì)象，它是一種原子數(shù)據(jù)類型。Argus提供一些原子類型，用戶也可自己定義一些。Argus提供兩級(jí)同步機(jī)制：用于偽并行進(jìn)程的和用于并行活動(dòng)的。mutex類型提供對(duì)保護(hù)者內(nèi)各進(jìn)程所共享的對(duì)象的互斥訪問(wèn)。在容錯(cuò)方面，可把某些保護(hù)者對(duì)象說(shuō)明成stable，存放到堅(jiān)固存儲(chǔ)器中，如果某個(gè)節(jié)點(diǎn)崩潰了，則可在堅(jiān)固存儲(chǔ)器中檢索并得到恢復(fù)。

第29頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.5邏輯上共享地址空間的語(yǔ)言

并行函數(shù)式語(yǔ)言：ParAlfl利用隱式函數(shù)并行性。函數(shù)并行性通常是細(xì)粒度的。由于可能有比處理機(jī)數(shù)多得多的任務(wù)要并行執(zhí)行，所以使用變換方法指定哪個(gè)表達(dá)式在哪臺(tái)處理機(jī)上計(jì)算。如：(f(x)$on($self-1))+(g(y)$on($self+1))通信和同步是隱式的，所以不需要顯式語(yǔ)言結(jié)構(gòu)。某個(gè)計(jì)算需要另一個(gè)計(jì)算的結(jié)果但還未出來(lái)時(shí)則受阻。語(yǔ)義是基于遲緩計(jì)算(lazyevaluation)，即一個(gè)表達(dá)式僅當(dāng)其結(jié)果被要求時(shí)才進(jìn)行計(jì)算。一般說(shuō)來(lái)，程序員不需關(guān)心計(jì)算次序，但為了有效性要對(duì)計(jì)算次序進(jìn)行控制。第30頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.5邏輯上共享地址空間的語(yǔ)言

并行邏輯語(yǔ)言：并發(fā)PROLOG：并行性來(lái)自合取的各目標(biāo)的AND并行計(jì)算和保護(hù)Horn子句的各保護(hù)的OR并行計(jì)算。并發(fā)PROLOG中的并行進(jìn)程使用共享邏輯變量通信。同步是基于在只讀變量上暫停的辦法。并發(fā)PROLOG使用保護(hù)Horn子句處理非確定性。第31頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.5邏輯上共享地址空間的語(yǔ)言

并行邏輯語(yǔ)言：PARLOG：AND/OR并行性由程序員控制。有兩種不同的合取操作符：“.”并行計(jì)算各合??；“&”串行計(jì)算各合取(自左至右)。進(jìn)程通過(guò)共享變量進(jìn)行通信，而同步方法是在無(wú)界共享變量上掛起。PARLOG有個(gè)機(jī)構(gòu)用來(lái)指定哪些進(jìn)程可以為某變量產(chǎn)生賦值。如果輸入自變量未被賦值，則相應(yīng)的合一將掛起，當(dāng)某其他進(jìn)程為該變量賦值時(shí)此合一將繼續(xù)。PARLOG使用保護(hù)的Horn子句用于非確定性。PARLOG中的保護(hù)可測(cè)試任何輸入變量并為子句的局部變量賦值，但不能給在輸入自變量中傳送的變量賦值。第32頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.5邏輯上共享地址空間的語(yǔ)言

基于分布數(shù)據(jù)結(jié)構(gòu)語(yǔ)言：Linda：Linda的目標(biāo)是將程序員從并行計(jì)算和并發(fā)事件的思考中解脫出來(lái)，從而使并行程序設(shè)計(jì)在概念上類似于順序程序設(shè)計(jì)。Linda使用簡(jiǎn)單原語(yǔ)eval創(chuàng)建順序進(jìn)程，但不為程序設(shè)計(jì)人員提供方法把進(jìn)程變換到處理機(jī)上，實(shí)際上并不需要，因?yàn)槊總€(gè)處理機(jī)執(zhí)行一個(gè)進(jìn)程。Linda使用元組空間通信模型。進(jìn)程通信要向TS插入新元組、讀和移去現(xiàn)存的元組。進(jìn)程同步方法是使用阻塞read和in操作等待元組可用。Linda的容錯(cuò)網(wǎng)絡(luò)內(nèi)核是基于TS的復(fù)制上的。

第33頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.5邏輯上共享地址空間的語(yǔ)言

基于分布數(shù)據(jù)結(jié)構(gòu)語(yǔ)言：Orca：這種語(yǔ)言的并行性是基于順序進(jìn)程。使用顯式的fork原語(yǔ)派生新的子進(jìn)程并把參數(shù)傳送給它。參數(shù)可以是數(shù)值，也可以是由該子進(jìn)程的說(shuō)明部分指出共享的抽象數(shù)據(jù)類型。進(jìn)程之間通信通過(guò)共享數(shù)據(jù)對(duì)象間接地進(jìn)行。每個(gè)對(duì)象都屬于抽象數(shù)據(jù)類型，每個(gè)抽象數(shù)據(jù)類型的定義由說(shuō)明部分和實(shí)現(xiàn)部分組成。說(shuō)明部分列出可對(duì)該給定類型的對(duì)象進(jìn)行的各種操作。一個(gè)操作的實(shí)現(xiàn)可由一個(gè)或多個(gè)保護(hù)語(yǔ)句組成。如果是這樣，一個(gè)操作的調(diào)用受阻直到至少有一個(gè)保護(hù)成功，接著非確定性地選擇一個(gè)為真的保護(hù)，執(zhí)行其語(yǔ)句不再受阻。共享數(shù)據(jù)對(duì)象模型在分布式系統(tǒng)中有效的實(shí)現(xiàn)方法是復(fù)制對(duì)象。如果共享對(duì)象不經(jīng)常改變，可在經(jīng)常讀它的處理機(jī)上維持副本，對(duì)本地副本進(jìn)行讀操作，就可減少通信開(kāi)銷。第34頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第35頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

DCDL中的通用符號(hào)：第36頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第37頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

DCDL中并行性表示：DCDL中的并行單元是語(yǔ)句。一組并行語(yǔ)句表示為：

S1||S2||…||Sn而一組順序語(yǔ)句表示為：

S1；S2；…；Sn

一組語(yǔ)句可以用語(yǔ)句優(yōu)先圖表示

S1；[S2；[S3||S4]；S5；S6]||S7

S1S2S3S4S7S5S6S1S2S3S4S7S5S6第38頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

選擇語(yǔ)句：一個(gè)選擇語(yǔ)句表示為：

[G1→C1□G2→C2□…□Gn→Cn]選擇語(yǔ)句選擇其組成的被保護(hù)的命令之一執(zhí)行。如果多余一個(gè)命令可被選擇，選擇將是不確定的。如下的選擇語(yǔ)句

[x≥y→m:=x□y≥x→m:=y]表示如果x≥y，將x賦予m；如果y≥x，將y賦予m；如果x≥y并且y≥x，則將x或y之一賦予m。第39頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

重復(fù)語(yǔ)句：一個(gè)重復(fù)語(yǔ)句指定其組成選擇語(yǔ)句的交互次數(shù)，這些語(yǔ)句帶保護(hù)或不帶保護(hù)，它的形式有如下三種：1．*[帶保護(hù)的選擇語(yǔ)句]2．*[不帶保護(hù)的選擇語(yǔ)句]3．(n)[選擇語(yǔ)句]在第一種情況下，當(dāng)所有的保護(hù)都經(jīng)過(guò)時(shí)，重復(fù)語(yǔ)句終止。在第二種情況下，執(zhí)行不終止。第三種是一個(gè)特別的重復(fù)語(yǔ)句，其重復(fù)的次數(shù)最多為n。第40頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

重復(fù)語(yǔ)句：例1：給出一個(gè)確定的數(shù)組b[1:m][1:n]，其中1<m，1<n，找出數(shù)組b中的一個(gè)確定值x。

i:=1; j:=1; *[i≤m∧x≠b[i,j]→ [j:=j+1; [j≤n→skip□j>n→i:=i+1;j:=1] ] ]第41頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

重復(fù)語(yǔ)句：例2：確定一個(gè)m×n的矩陣a[1:m][1:n]中某一行的所有元素是否全部為0i:=1;p:=m+1;*[i≠p→ [j:=1; q:=n+1; *[j≠q→ [a[i,j]=0→j:=j+1□a[i,j]≠0→q:=j] ]; [j=n→p:=i□j≠n→i:=i+1] ]]found:=(i≠m+1)第42頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

語(yǔ)句并發(fā)(或并行)的條件當(dāng)兩個(gè)語(yǔ)句并發(fā)執(zhí)行時(shí)，可能產(chǎn)生與順序執(zhí)行不同的結(jié)果。讓我們先定義兩個(gè)符號(hào)：

(1)R(Si)，Si的讀集，即在Si中被引用的所有變量的集合。

(2)W(Si)，Si的寫集，即在Si中被修改的所有變量的集合。Bernstein提出了以下三個(gè)條件，對(duì)于兩個(gè)并發(fā)執(zhí)行的語(yǔ)句S1和S2，必須滿足這三個(gè)條件才能使它們并發(fā)執(zhí)行的結(jié)果與它們以任意次序順序執(zhí)行的結(jié)果相同。

(1)R(S1)∩W(S2)=Ф (2)R(S2)∩W(S1)=Ф (3)W(S1)∩W(S2)=Ф第43頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

語(yǔ)句并發(fā)(或并行)的條件我們可以用Bernstein條件來(lái)尋找語(yǔ)句中可以并行執(zhí)行的最大子集。為此我們定義了一個(gè)無(wú)向圖，節(jié)點(diǎn)集由給定語(yǔ)句集組成，如果Si||Sj，則節(jié)點(diǎn)Si和Sj相連，可以并行執(zhí)行的最大的語(yǔ)句子集對(duì)應(yīng)于最大的完全子圖。例如：S1:a:=x＋y,S2:b:=x×z,S3:x:=y＋z,S4:c:=y-1。顯然，S1，S2，S4形成最大的完全子圖，也就是說(shuō)，S1||S2||S4。S1S2S3S4S1S2S3S4第44頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

DCDL中的通信輸出命令的形式為：

sendmessage_listtodestination

其中destination是一個(gè)進(jìn)程名(一對(duì)一通信)或代表所有其他進(jìn)程(一對(duì)所有通信)的關(guān)鍵字all。輸入命令的形式為：

receivemessage_listfromsource

其中source是一個(gè)進(jìn)程名，這個(gè)輸入命令支持顯式和隱式的報(bào)文接收。 隱式的報(bào)文接收表示為：

receivemessage_list第45頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

DCDL中的通信例1：用如下遞歸的方法計(jì)算f(n)=f(n-1)×n2，n＞1并且f(1)=1。

p(i:1..n)::=*[receivemfromp(i-1)→ [[m=0→send1top(i-1)□m>0→sendm-1top(i+1)]; receiverfromp(i+1); sendm×m×rtop(i-1) ] ] p(0)::=sendntop(1); receiveresultfromp(1)

第46頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月第三章分布式程序設(shè)計(jì)語(yǔ)言

3.6分布式控制描述語(yǔ)言DCDL

DCDL中的通信例2：Fibonacci數(shù)列是由遞推公式F(i)=F(i-1)+F(i-2)(i>1)定義的一個(gè)整數(shù)數(shù)列，其初始