第3章分布式序設計語言

1、第三章第三章 分布式程序設計語言分布式程序設計語言 3.1 3.1 分布式程序設計語言概述分布式程序設計語言概述 v分布式應用程序的分類分布式應用程序的分類 并行、高性能應用程序。通過并行性達到加速是在分布計算系統(tǒng)上運行應用程序的最主要的原因。 容錯應用程序。而分布計算系統(tǒng)具有允許部分失效的特性，即由于各處理機具有自治性，一個處理機的故障不影響其他處理機的正常工作，所以可靠性高。程序和數(shù)據(jù)也可在若干處理機上復制而進一步增加可靠性。 具有專用功能的應用程序。一些應用程序可以被構造成一組專用的服務程序。例如文件服務、打印服務、進程服務、終端服務、時間服務等。 固有的分布式應用程序。有些應用程序本身

2、就是分布的，在這種情況下，可以把工作站的集合看成一個分布計算系統(tǒng)，這種應用程序必須在分布式硬件上運行。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.1 3.1 分布式程序設計語言概述分布式程序設計語言概述 v分布式程序設計與順序程序設計的區(qū)別分布式程序設計與順序程序設計的區(qū)別 使用多個處理機。對分布式程序設計支持的第一個要求就是系統(tǒng)應該具有把一個程序的不同部分分配到不同處理機上執(zhí)行的能力。 處理機合作。各個進程必須能相互通信和同步，這是對分布式程序設計支持的第二個要求。 處理部分失效。在分布計算系統(tǒng)中一些cpu失效時，其他cpu照樣工作。所以對分布式程序設計支持的第三個要求是能對系

3、統(tǒng)的部分失效進行檢測并恢復。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.1 3.1 分布式程序設計語言概述分布式程序設計語言概述 v分布式程序設計語言的分類分布式程序設計語言的分類 按并行模型來分按并行模型來分 1) 順序進程并行語言。這類語言使用的最基本模型是一組順序進程，它們并行運行，并且通過報文傳遞進行通信。大部分是流行的c(或c+)和fortran的擴展。2) 具有內(nèi)在并行性的語言。一些研究者認為算法語言不是處理并行性的最好語言，因為算法語言是內(nèi)在順序式的，許多研究者研究具有內(nèi)在并行性的語言，如函數(shù)式語言、邏輯語言和面向對象語言。 第三章第三章 分布式程序設計語言分布式程

4、序設計語言 3.1 3.1 分布式程序設計語言概述分布式程序設計語言概述 v分布式程序設計語言的分類分布式程序設計語言的分類 按通信模型來分按通信模型來分 1) 在物理分布的硬件上運行邏輯上分布的軟件。相互使用send和receive原語通信，在網(wǎng)絡上發(fā)送報文。 2) 在物理非分布的硬件上運行邏輯上分布的軟件。用共享主存方法實現(xiàn)報文傳遞來模擬物理報文傳遞通信。 3) 在物理分布的硬件上運行邏輯上非分布的軟件。使用分布式共享存儲器通信。4) 在物理非分布的硬件上運行邏輯上非分布的軟件。使用物理共享存儲器通信。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.1 3.1 分布式程序設計語言

5、概述分布式程序設計語言概述 v分布式程序設計語言的分類分布式程序設計語言的分類 容錯模型和技術容錯模型和技術故障的處理模型： 1)系統(tǒng)對程序員隱匿全部處理機故障。2)給程序員提供高層機制，使得程序員能夠描述哪些進程和數(shù)據(jù)是重要的，以及發(fā)生崩潰后怎樣恢復。實現(xiàn)可靠性的方法有兩種：程序設計容錯和通信容錯。1)程序設計容錯技術有三類：向前恢復試圖確定錯誤所在并基于這個知識改正包含錯誤的系統(tǒng)狀態(tài)；向后恢復通過把系統(tǒng)恢復到錯誤發(fā)生前的狀態(tài)來改正系統(tǒng)狀態(tài)；錯誤屏蔽，利用同一個算法獨立開發(fā)幾個版本，一個最后投票系統(tǒng)用于對這n個版本產(chǎn)生的結果進行投票并確定一個正確的結果。2)通信容錯處理進程通信中發(fā)生的故障，

6、通信容錯依賴于使用的通信方式和故障的類型。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.2 3.2 并行性的支持并行性的支持 v并行性的概念并行性的概念 并行性。因為分布計算系統(tǒng)有多個處理機，所以可把程序分成若干部放到多個處理機上同時運行，這就是所謂的并行性。 偽并行性(pseudo parallelism)，即把程序表示為一組并行運 行的進程但不管它們是否在不同的處理機上同時運行。 并行粒度。并行單位可以是進程(如并發(fā)c)，也可以是表達式(如par alfl)。一般說來，通信代價越大，則并行的粒度就應該越大。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.2 3.2 并

7、行性的支持并行性的支持 v并行性的表示并行性的表示 進程并行。一般說來，一個進程是一個邏輯處理機，順序地執(zhí)行代碼，具有自己的狀態(tài)和數(shù)據(jù)。在語言中，進程或進程類型是要被說明的，就像過程或過程類型一樣。進程的創(chuàng)建可以由說明隱式地完成，也可以通過創(chuàng)建某種結構顯式地完成。 對象并行。用下述方法擴充順序對象模型可獲得并行性：(1)允許對象不必在收到報文時才活動；(2)允許接收對象在返回結果后繼續(xù)執(zhí)行；第(3)一次向幾個對象發(fā)送報文；(4)允許報文發(fā)送者繼續(xù)和接收者并行工作。第三章第三章 分布式程序設計語言分布式程序設計語言 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 語句并行語

8、句并行par j=0 for n aj：=aj+1 par s1s2第三章第三章 分布式程序設計語言分布式程序設計語言 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 函數(shù)并行函數(shù)并行 例如表達式例如表達式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) 每個子句中的子定理可并行

9、工作直到它們?nèi)汲晒Γ蚱渲幸粋€失敗。前一種并行性叫做or并行性，后一種叫做and并行性。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v報文傳遞報文傳遞進程通信的表示方法：報文傳遞和共享數(shù)據(jù)進程通信的表示方法：報文傳遞和共享數(shù)據(jù) 設計報文傳遞的通信方式應考慮的問題：1) 可靠的報文傳遞和非可靠的報文傳遞：可靠的報文傳遞需要承認報文。2) 顯式接收和隱式接收：顯式接收時，接收者執(zhí)行某一類accept語句指明接收哪些報文，以及當報文到達時采取什么行動。使用隱式接收時，在接收者內(nèi)自動調(diào)用程序，通常在接收進程中創(chuàng)建一個新的線程。 3)

10、 直接命名和間接命名：直接命名用于指示一個指定的進程，名字可以是該進程的靜態(tài)名字或是一個表達式。間接命名包括一個中間對象，通常叫做郵箱，發(fā)送者把報文送給它，接收者從它那接收。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v報文傳遞報文傳遞進程通信的表示方法：報文傳遞和共享數(shù)據(jù)進程通信的表示方法：報文傳遞和共享數(shù)據(jù) 設計報文傳遞的通信方式應考慮的問題：4) 對稱命名和非對稱命名。如果發(fā)送者和接收者相互命名，則基于直接命名的方案是對稱的。在非對稱方案中，僅發(fā)送者找接收者，在此情況下，接收者要與任何發(fā)送者相互作用。注意，使用隱式接收報

11、文的相互作用在命名方面總是非對稱的。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v報文傳遞報文傳遞報文傳遞通信模式有 ：1) 同步和異步點到點報文。在同步報文傳送方式中，發(fā)送者在接收者接收報文前一直阻塞。這樣，雙方不僅交換了數(shù)據(jù)而且還達到同步。在異步報文傳送方式中，發(fā)送者并不等待接收者準備好接收其報文，發(fā)送者在送出報文后立即繼續(xù)工作。2) 會合。在ada中會合模型基于三個概念：項說明、項調(diào)用和接受語句。項說明和接受語句是服務員程序的一部分，項調(diào)用在顧客端。當進程s調(diào)用進程r的一項，r為此項執(zhí)行accept語句時，在s和r之間發(fā)

12、生了相互作用，叫做會合。 accept incr(x: int; y: out int)do y:=x+1;end第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v報文傳遞報文傳遞報文傳遞通信模式有 ：3) 遠程過程調(diào)用(rpc)。它是雙向通信的另一個原語。當進程s調(diào)用進程r的過程p時，由s提供的p的輸入?yún)?shù)被送給r。當r收到調(diào)用請求時，執(zhí)行過程p，然后把輸出參數(shù)送回給s。執(zhí)行p期間s阻塞，直到輸出參數(shù)返回。這和會合機構不同，在會合機構中，一旦accept語句已執(zhí)行，則調(diào)用者就不阻塞。 4) 一到多報文傳送。很多用于分布計算系統(tǒng)的網(wǎng)

13、絡支持快速的廣播或組通信設施。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v共享數(shù)據(jù)共享數(shù)據(jù)如果兩個進程訪問同一個變量，可以實現(xiàn)另一種通信方式：一個進程對此變量進行設置，另一個進程對它進行讀。如果兩個進程在同一個機器上運行，變量在此機器上存儲，則可直接通信。分布進程的共享數(shù)據(jù)方法有：分布式數(shù)據(jù)結構和共享的邏輯變量 。1) 分布式數(shù)據(jù)結構。這種數(shù)據(jù)結構可由若干進程同時處理。linda語言使用元組空間(tuple space)的概念實現(xiàn)分布式數(shù)據(jù)結構。例如“jones”,31,true是一個有三個段的元組：一個字符串、一個整數(shù)和一

14、個布爾值。對ts定義了三個原子操作：out操作向ts加入一個元組，read讀ts中的一個元組，in讀ts中的一個元組并刪除它。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v共享數(shù)據(jù)共享數(shù)據(jù)2) 共享的邏輯變量。邏輯變量具有“單賦值”性質，最初，它們是未賦值的，但一旦它們接收一個值就不能改變它們。這些變量被用于進程之間的通信通道。如下三個目標：goal_1(x,y), goal_2(x,y), goal_3(x)進行邏輯乘，用進程p1、p2、p3并行求解。變量x是這三個進程的通信通道，最初是未賦值的。如果三個進程中的某個給x賦值

15、，則其它兩個進程可使用此值。類似地，y是p1和p2的通信通道。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v非確定性的表示和控制非確定性的表示和控制 進程之間的相互作用模式并不總是確定性的，有時還決定于運行進程之間的相互作用模式并不總是確定性的，有時還決定于運行時條件。因此，表示和控制非確定性模型被提出。選擇語句和保時條件。因此，表示和控制非確定性模型被提出。選擇語句和保護的護的(guarded)horn(guarded)horn子句子句 是兩種表示和控制非確定性的模型。是兩種表示和控制非確定性的模型。1) 選擇語句。它是由如

16、下形式的一組保護命令組成的： 保護語句 其中保護(guard)由一個布爾表達式和某一類“通信請求”組成。布爾表達式必須無副作用，因為它可能在執(zhí)行該選擇語句過程中被計算多次。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.3 3.3 進程通信與同步的支持進程通信與同步的支持 v非確定性的表示和控制非確定性的表示和控制 2) 保護的horn子句。邏輯程序本質上就不是確定性的。并行邏輯語言不是對一給定的謂詞一個又一個地試驗子句，失敗時回溯，而是并行地搜索所有那些子句，并且在這些并行執(zhí)行期間直到有一個并行執(zhí)行提交前不允許任何賦值對外部是可見的，這叫做or并行性。但是，這不能無限地進行，因為并

17、行工作的搜索路徑隨證明的長度而指數(shù)地增長。 很普遍的控制or并行性技術是提交選擇非確定性，它非確定地選擇一個可選擇的子句，取消其他子句。它是基于保護的horn子句，形式如下：a:-g1,gn|b1,bmn0,m0目標gi的合取(與操作)叫做保護，目標bi的合取叫做體(body)。提交操作符“|”也是一個合取操作符。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v分布式程序設計語言的分類：分布式程序設計語言的分類： 分布式程序設計語言分布地址空間共享地址空間同步報文傳送異步報文傳送會合遠程過程調(diào)用多重原語對象原子事務處理函

18、數(shù)式語言邏輯語言分布數(shù)據(jù)結構第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v同步式報文傳遞語言同步式報文傳遞語言 ： 1)創(chuàng)建并行進程：如csp提供簡單的并行命令創(chuàng)建固定數(shù)目的并行進程。進程包含名字、邏輯變量和一系列語句(進程體)。 csp可以創(chuàng)建一組相似的進程，但其數(shù)目必須在編譯時是個常數(shù)。例如并行語句writer:x:real;|reader(i:1.2): 創(chuàng)建三個進程，叫作“writer”、“reader(1)”和“reader(2)”。writer有一個局部變量x。下標量i可在reader進程的體中使用。 2)通

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

20、pair：x:y! pair(35,60)|y:n,m:integer;x? pair(n,m)可使用空構造符對兩個進程進行同步但不傳送任何實際數(shù)據(jù)。4)非確定性的表示：csp中使用alternative結構表示非確定性，它由一組保護(后面跟著待執(zhí)行的動作)組成。保護可包含布爾表達式和一個輸入語句。csp允許進程根據(jù)當前通信的輸入和名字段的信息有選擇地接收。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v異步式報文傳遞語言異步式報文傳遞語言 ： 1) 并行性單位：nil中的并行性是基于所謂進程模型。進程不僅是并行性的單位

21、，也是模塊化的單位。進程到處理機變換是實現(xiàn)上的問題，由編譯和運行時系統(tǒng)處理。 2) nil可動態(tài)地進行進程間通信路徑的配置：nil中的信口是一個排隊的通信通道。在給定時間，一個信口有一個指定的所有者。所有者關系可以轉讓給其他進程，可以把信口作為報文的一部分傳送，或把信口作為一個新創(chuàng)建進程的初始化參數(shù)傳送。進程可以連接其擁有的輸入口和輸出口。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v異步式報文傳遞語言異步式報文傳遞語言 ： 3) 通信類型：nil既支持同步通信也支持異步通信，可把單個輸入口連接到幾個輸出口，所以在輸入

22、口可以有多個掛起的報文，因而必須排隊。4) 非確定表示：nil提供一個保護命令風格的語句用于在任何輸入口上等待報文。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v基于會合的語言基于會合的語言 ： ada:1) 并行性表示：其并行性是基于順序進程，叫作任務(task)，每個任務具有一定的類型。任務由說明部分(說明其他任務如何與其通信)和一個體(包含它的可以執(zhí)行的語句)組成。2) 通信：任務通常通過會合機制通信，也通過共享變量通信，會合機制基于項說明、項調(diào)用和接受語句。 3) 非確定性表示：ada使用select語句表示非

23、確定性。這個語句用于三個目的：從一組未處理的請求中非確定地選擇一個項調(diào)用；有條件地調(diào)用一項(即僅當被調(diào)用的任務準備好立即接受它)和為一個項調(diào)用設置時限。 4) 容錯：ada有一個異常處理機制處理軟件故障，但語言定義未說明硬件故障問題。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v基于會合的語言基于會合的語言 ： 并發(fā)c:1) 進程創(chuàng)建：它使用create原語顯式地創(chuàng)建進程，并可向創(chuàng)建的進程傳送參數(shù)?？少x給新進程一個優(yōu)先權，以后新進程或其他進程還可以改變此優(yōu)先權。2) 通信：進程通過會合機構相互通信。并發(fā)c中的事務處理與

24、ada中的項不同，可以返回一個值，并支持異步事務處理(但并不返回值)。并發(fā)c支持一個比ada中的功能更強的accept語句，它根據(jù)事務處理參數(shù)的值，可以有條件地接受一些事務處理 。3) 非確定性表示：使用select語句表示非確定性。4) 容錯：基于進程復制。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v基于遠程過程調(diào)用的語言基于遠程過程調(diào)用的語言 ： 1) dp的進程：每個處理機專用于執(zhí)行一個進程，但每個進程可包含幾個處理線程，這些線程以偽并行方式運行。2) 通信：dp進程相互調(diào)用對方的公用過程進行通信，用如下形式調(diào)

25、用： call p.f(exps,vars)這里p是被調(diào)用進程的名字，f是由p說明的過程名字，表達式是輸入?yún)?shù)，返回值賦予變量vars。第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v多重通信原語多重通信原語 ： 1) sr是由一個或多個資源(resource)組成。資源是運行在一個物理節(jié)點(單處理機或共享存儲器多處理機)的一個程序模塊，可動態(tài)創(chuàng)建，并可選擇地分配到指定機器上運行。 2) 資源可包含多個進程，它們共享數(shù)據(jù)。資源可包含一個初始進程和終結進程，它們隱式地被創(chuàng)建和運行。 3) sr使用類似于select語句的結構

26、處理非確定性。 4) sr操作的定義類似過程的定義，可看成一個過程或入口點(entry point)。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v多重通信原語多重通信原語 ： 5) 把操作的兩種服務方式和兩種調(diào)用方式結合起來就有四種進程通信方法 。 call(同步)send(異步)entry(同步)會合報文傳送process(異步)rpcfork第三章第三章 分布式程序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v基于對象的語言基于對象的語言 ： 1) 對象：emer

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

28、序設計語言分布式程序設計語言 3.4 3.4 邏輯上分布地址空間的語言邏輯上分布地址空間的語言 v基于原子事務處理的語言基于原子事務處理的語言 ： argus:1) 主要特點:guardian(保護者)和action(活動)。保護者是能從崩潰中幸存下來的模塊，而活動是一組原子執(zhí)行。2) 為了在保持原子語義下允許活動的并行，使用原子對象，它是一種原子數(shù)據(jù)類型。argus提供一些原子類型，用戶也可自己定義一些。3) argus提供兩級同步機制：用于偽并行進程的和用于并行活動的。 4) mutex類型提供對保護者內(nèi)各進程所共享的對象的互斥訪問。5) 在容錯方面，可把某些保護者對象說明成stable，

29、存放到堅固存儲器中，如果某個節(jié)點崩潰了，則可在堅固存儲器中檢索并得到恢復。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.5 3.5 邏輯上共享地址空間的語言邏輯上共享地址空間的語言 v并行函數(shù)式語言并行函數(shù)式語言 ： 1) paralfl利用隱式函數(shù)并行性。函數(shù)并行性通常是細粒度的。由于可能有比處理機數(shù)多得多的任務要并行執(zhí)行，所以使用變換方法指定哪個表達式在哪臺處理機上計算。 如：(f(x) $on ($self-1)+(g(y) $on ($self+1) 2) 通信和同步是隱式的，所以不需要顯式語言結構。某個計算需要另一個計算的結果但還未出來時則受阻。 3) 語義是基于遲緩計算

30、(lazy evaluation)，即一個表達式僅當其結果被要求時才進行計算。一般說來，程序員不需關心計算次序，但為了有效性要對計算次序進行控制。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.5 3.5 邏輯上共享地址空間的語言邏輯上共享地址空間的語言 v并行邏輯語言并行邏輯語言 ： 并發(fā)prolog ：1) 并行性來自合取的各目標的and并行計算和保護horn子句的各保護的or并行計算。 2) 并發(fā)prolog中的并行進程使用共享邏輯變量通信。同步是基于在只讀變量上暫停的辦法。3) 并發(fā)prolog使用保護horn子句處理非確定性。第三章第三章 分布式程序設計語言分布式程序設計語

31、言 3.5 3.5 邏輯上共享地址空間的語言邏輯上共享地址空間的語言 v并行邏輯語言并行邏輯語言 ： parlog：1) and/or并行性由程序員控制。有兩種不同的合取操作符：“.”并行計算各合??；“&”串行計算各合取(自左至右)。2) 進程通過共享變量進行通信，而同步方法是在無界共享變量上掛起。parlog有個機構用來指定哪些進程可以為某變量產(chǎn)生賦值。如果輸入自變量未被賦值，則相應的合一將掛起，當某其他進程為該變量賦值時此合一將繼續(xù)。 3) parlog使用保護的horn子句用于非確定性。parlog中的保護可測試任何輸入變量并為子句的局部變量賦值，但不能給在輸入自變量中傳送的變量

32、賦值。第三章第三章 分布式程序設計語言分布式程序設計語言 3.5 3.5 邏輯上共享地址空間的語言邏輯上共享地址空間的語言 v基于分布數(shù)據(jù)結構語言基于分布數(shù)據(jù)結構語言 ： linda：1) linda的目標是將程序員從并行計算和并發(fā)事件的思考中解脫出來，從而使并行程序設計在概念上類似于順序程序設計。2) linda使用簡單原語eval創(chuàng)建順序進程，但不為程序設計人員提供方法把進程變換到處理機上，實際上并不需要，因為每個處理機執(zhí)行一個進程。3) linda使用元組空間通信模型。進程通信要向ts插入新元組、讀和移去現(xiàn)存的元組。進程同步方法是使用阻塞read和in操作等待元組可用。4) linda的

33、容錯網(wǎng)絡內(nèi)核是基于ts的復制上的。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.5 3.5 邏輯上共享地址空間的語言邏輯上共享地址空間的語言 v基于分布數(shù)據(jù)結構語言基于分布數(shù)據(jù)結構語言 ： orca ：1)這種語言的并行性是基于順序進程。使用顯式的fork原語派生新的子進程并把參數(shù)傳送給它。參數(shù)可以是數(shù)值，也可以是由該子進程的說明部分指出共享的抽象數(shù)據(jù)類型。2) 進程之間通信通過共享數(shù)據(jù)對象間接地進行。每個對象都屬于抽象數(shù)據(jù)類型，每個抽象數(shù)據(jù)類型的定義由說明部分和實現(xiàn)部分組成。說明部分列出可對該給定類型的對象進行的各種操作。3) 一個操作的實現(xiàn)可由一個或多個保護語句組成。如果是這樣

34、，一個操作的調(diào)用受阻直到至少有一個保護成功，接著非確定性地選擇一個為真的保護，執(zhí)行其語句不再受阻。 4) 共享數(shù)據(jù)對象模型在分布式系統(tǒng)中有效的實現(xiàn)方法是復制對象。如果共享對象不經(jīng)常改變，可在經(jīng)常讀它的處理機上維持副本，對本地副本進行讀操作，就可減少通信開銷。原語 語言的例子并行性表示并行性 進程 ada、并發(fā) c、linda、nil 對象 emerald、并發(fā) smalltalk 語句 occam 表達式 paralfl、fx-87 子句 并發(fā) prolog、parlog變換 靜態(tài) occam、starmod 動態(tài) 并發(fā) prolog、paralfl 遷移 emerald通信報文傳遞 點到點報

35、文 csp、occam、nil 會合 ada、并發(fā) c 遠程過程調(diào)用 dp、并發(fā) clu、lynx 一對多報文 bsp、starmod數(shù)據(jù)共享 分布式數(shù)據(jù)結構 linda、orca 共享邏輯變量 并發(fā) prolog、parlog非確定性 選擇語句 csp、occam、ada、并發(fā) c、sr 保護 horn 子句 并發(fā) prolog、parlog部分失效故障檢測 ada、sr原子事務處理 argus、aeolus、avalon透明容錯 nil第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl vdcdl中的通用符號中的通用符號

36、 ： 選擇*重復|并行條件；順序send輸出：=賦值receive輸入： ：定義開始結束任意(全稱量詞)存在(存在量詞)=相等不等或且反第三章第三章 分布式程序設計語言分布式程序設計語言 3.63.6分布式控制描述語言分布式控制描述語言dcdldcdl vdcdl中并行性表示中并行性表示 ：dcdldcdl中的并行單元是語句。中的并行單元是語句。一組并行語句表示為：一組并行語句表示為：s s1 1|s|s2 2|s|sn n而一組順序語句表示為：而一組順序語句表示為： s s1 1；s s2 2；s sn n 一組語句可以用語句優(yōu)先圖表示一組語句可以用語句優(yōu)先圖表示 s s1 1；s s2 2

37、；s s3 3|s|s4 4 ；s s5 5；s s6 6|s|s7 7 s1s2s3s4s7s5s6s1s2s3s4s7s5s6第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v選擇語句選擇語句 ：一個選擇語句表示為：一個選擇語句表示為：gg1 1cc1 1g g2 2cc2 2g gn nccn n 選擇語句選擇其組成的被保護的命令之一執(zhí)行。如果多余一個命選擇語句選擇其組成的被保護的命令之一執(zhí)行。如果多余一個命令可被選擇，選擇將是不確定的。如下的選擇語句令可被選擇，選擇將是不確定的。如下的選擇語句xym:=xxym:

38、=xyxm:=yyxm:=y表示如果表示如果xyxy，將，將x x賦予賦予mm；如果；如果yxyx，將，將y y賦予賦予mm；如果；如果xyxy并并且且yxyx，則將，則將x x或或y y之一賦予之一賦予mm。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v重復語句重復語句 ：一個重復語句指定其組成選擇語句的交互次數(shù)，這些語句帶保護一個重復語句指定其組成選擇語句的交互次數(shù)，這些語句帶保護或不帶保護，它的形式有如下三種：或不帶保護，它的形式有如下三種：1 1* * 帶保護的選擇語句帶保護的選擇語句 2 2* * 不帶保

39、護的選擇語句不帶保護的選擇語句 3 3(n)(n)選擇語句選擇語句 在第一種情況下，當所有的保護都經(jīng)過時，重復語句終止。在第在第一種情況下，當所有的保護都經(jīng)過時，重復語句終止。在第二種情況下，執(zhí)行不終止。第三種是一個特別的重復語句，其重二種情況下，執(zhí)行不終止。第三種是一個特別的重復語句，其重復的次數(shù)最多為復的次數(shù)最多為n n。 第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v重復語句重復語句 ：例例1 1：給出一個確定的數(shù)組：給出一個確定的數(shù)組b1:m1:nb1:m1:n，其中，其中1m1m，1n1ni:=i+1;j:

40、=1jni:=i+1;j:=1 第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v重復語句重復語句 ：例例2 2：確定一個：確定一個mmn n的矩陣的矩陣a1:m1:na1:m1:n中某一行的所有元素是否中某一行的所有元素是否全部為全部為0 0 i:=1; p:=m+1;i:=1; p:=m+1;* *ipipj:=1; j:=1; q:=n+1; q:=n+1; * *jqjqai,j=0j:=j+1ai,j=0j:=j+1ai,j0q:=jai,j0q:=j ; ; j=np:=i j=np:=ijni:=i+1jn

41、i:=i+1 found:=(im+1) found:=(im+1) 第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v語句并發(fā)語句并發(fā)( (或并行或并行) )的條件的條件當兩個語句并發(fā)執(zhí)行時，可能產(chǎn)生與順序執(zhí)行不同的結果。讓我當兩個語句并發(fā)執(zhí)行時，可能產(chǎn)生與順序執(zhí)行不同的結果。讓我們先定義兩個符號：們先定義兩個符號：(1) r(s(1) r(si i) )，s si i的讀集，即在的讀集，即在s si i中被引用的所有變量的集合。中被引用的所有變量的集合。(2) w(s(2) w(si i) )，s si i的寫集，即

42、在的寫集，即在s si i中被修改的所有變量的集合。中被修改的所有變量的集合。 bernsteinbernstein提出了以下三個條件，對于兩個并發(fā)執(zhí)行的語句提出了以下三個條件，對于兩個并發(fā)執(zhí)行的語句s s1 1和和s s2 2，必須滿足這三個條件才能使它們并發(fā)執(zhí)行的結果與它們以任意次必須滿足這三個條件才能使它們并發(fā)執(zhí)行的結果與它們以任意次序順序執(zhí)行的結果相同。序順序執(zhí)行的結果相同。(1) r(s(1) r(s1 1)w(s)w(s2 2)=)=(2) r(s(2) r(s2 2)w(s)w(s1 1)=)=(3) w(s(3) w(s1 1)w(s)w(s2 2)=)=第三章第三章 分布式程

43、序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v語句并發(fā)語句并發(fā)( (或并行或并行) )的條件的條件 我們可以用我們可以用bernsteinbernstein條件來尋找語句中可以并行執(zhí)行的最大條件來尋找語句中可以并行執(zhí)行的最大子集。為此我們定義了一個無向圖，節(jié)點集由給定語句集組成，子集。為此我們定義了一個無向圖，節(jié)點集由給定語句集組成，如果如果s si i|s|sj j，則節(jié)點，則節(jié)點s si i和和s sj j相連，可以并行執(zhí)行的最大的語句子集相連，可以并行執(zhí)行的最大的語句子集對應于最大的完全子圖。對應于最大的完全子圖。 例如：s1: a

44、:=xy, s2: b:=xz, s3: x:=yz, s4: c:=y-1。顯然，s1，s2，s4形成最大的完全子圖，也就是說，s1|s2|s4。 s1s2s3s4s1s2s3s4第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v dcdldcdl中的通信中的通信1) 1) 輸出命令的形式為：輸出命令的形式為：send message_list to destinationsend message_list to destination其中其中destinationdestination是一個進程名是一個進程名( (一

45、對一通信一對一通信) )或代表所有其他或代表所有其他進程進程( (一對所有通信一對所有通信) )的關鍵字的關鍵字allall。2)2) 輸入命令的形式為：輸入命令的形式為：receive message_list from sourcereceive message_list from source其中其中sourcesource是一個進程名，這個輸入命令支持顯式和隱式的是一個進程名，這個輸入命令支持顯式和隱式的報文接收。報文接收。隱式的報文接收表示為：隱式的報文接收表示為：receive message_listreceive message_list第三章第三章 分布式程序設計語言分布式程

46、序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v dcdldcdl中的通信中的通信例例1 1：用如下遞歸的方法計算：用如下遞歸的方法計算f(n)=f(n-1)f(n)=f(n-1)n n2 2，n n1 1并且并且f(1)=1f(1)=1。 p(i:1.n):=p(i:1.n):=* *receive m from p(i-1)receive m from p(i-1)m=0m=0send 1 to p(i-1)send 1 to p(i-1)m0m0send m-1 to p(i+1);send m-1 to p(i+1);receive r from p

47、(i+1);receive r from p(i+1);send msend mmmr to p(i-1)r to p(i-1) p(0):=send n to p(1);p(0):=send n to p(1);receive result from p(1)receive result from p(1) 第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v dcdldcdl中的通信中的通信例例2 2：fibonaccifibonacci數(shù)列是由遞推公式數(shù)列是由遞推公式f(i)=f(i-1)+f(i-2)(i1)f(i

48、)=f(i-1)+f(i-2)(i1)定義的定義的一個整數(shù)數(shù)列，其初始值一個整數(shù)數(shù)列，其初始值f(0)=0f(0)=0，f(1)=2f(1)=2。這里有兩種算法。這里有兩種算法。算法一：定義一系列進程：算法一：定義一系列進程：f(i)f(i)用于計算用于計算f(n-i+1)f(n-i+1)，如果，如果(n-i+1)(n-i+1)大于大于1 1，f(i)f(i)從從f(i-1)f(i-1)接收接收(n-i+1)(n-i+1)并把并把(n-i)(n-i)傳遞給傳遞給f(i+1)f(i+1)。然后。然后f(i)f(i)等待等待f(i+1)f(i+1)和和f(i+2)f(i+2)的結果，把它們相加，并

49、把相加的結果傳的結果，把它們相加，并把相加的結果傳遞給遞給f(i-1)f(i-1)和和f(i-2)f(i-2)。 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=1send 1 to f(i-1); send 1 to f(i-2) n=0

50、send 0 to f(i-1); send 0 to f(i-2) f(-1):=receive p from f(1) 在上述算法中，f(0)是用戶進程，f(-1)是虛進程。算法二。這個算法使通信只限于鄰居之間，即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 from f(i+1);

51、 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) 第三章第三章 分布式程序設計語言分布式程序設計語言 3.6 3.6 分布式控制描述語言分布式控制描述語言dcdldcdl v dcdldcdl中的通信容錯中的通信容錯容錯是通過檢測故障并隨之對系統(tǒng)進行重新配置而實現(xiàn)的。以下容錯是通過檢測故障并隨之對系統(tǒng)進行重新配置而實現(xiàn)的。以下是用是用dcdldcdl描述的故障檢測過程。描述的故障檢測過程。 sender:=setup time(t);sender:

52、=setup time(t);send diagnostic_signal to receiver;send diagnostic_signal to receiver;receive ack from receiverreceive ack from receiverstatus:=normalstatus:=normal timeout(t)timeout(t)status:=abnormalstatus:=abnormal 個有故障的處理機將被發(fā)送方節(jié)點通過檢查狀態(tài)變量的值發(fā)現(xiàn)。個有故障的處理機將被發(fā)送方節(jié)點通過檢查狀態(tài)變量的值發(fā)現(xiàn)。 3.7 公共網(wǎng)關接口（cgi）在internet上運

53、行程序，由于數(shù)據(jù)處于外地計算機上，可能分布在相距甚遠的多臺設備中，甚至于html程序本身也在外地計算機中，再加上html程序可能同一時刻有多個用戶運行，從而使得html程序的運行不同于 doswindows等平臺下應用程序的線性運行了。.公共關系接口cgi（common gateway interface）是客戶機與外部應用程序交互信息的基本方式?；趙ww的客戶機/服務器應用中，客戶機（通常即為瀏覽器）和服務器通過網(wǎng)絡采用http協(xié)議彼此通信。http等候來自web客戶機的請求，并對它們作出響應。html程序的上載 一個html程序設計完成后只有將它上載（upload）到某一個http服務器

54、（host）中，才可以被用戶執(zhí)行。http服務器中有固定的路徑用于存放html程序，使之能被internet上任何用戶檢索執(zhí)行。 例如： %cd %mkdir public_homepage %cd public_homepage %ftp get quit %chmod a+x 至此，html程序上載工作已完成。 2cgi程序的調(diào)用與結果回送form中的信息可以由cgi程序接收。cgi程序運行后回送結果給前端。html調(diào)用cgi程序的方法是：在form的action屬性中指定；cgi程序回送結果的方法是：產(chǎn)生或調(diào)用url，將html程序文本送給前端機。3前端數(shù)據(jù)的輸入 html允許前端用戶輸

55、入數(shù)據(jù)，其語句如下： 顯示信息 顯示信息 4cgi程序的調(diào)用 為了前后臺交換信息，必須調(diào)用cgi程序，調(diào)用方法為 注：所有cgi程序通過form方式調(diào)用。 5cgi中接收數(shù)據(jù) cgi程序中首先應判明前臺傳送數(shù)據(jù)的長度，然后一位一位地接收到自己的變量中，而進行所需的處理。 getenv（“content-length”）求得cgi數(shù)據(jù)長度 getchar（ ） 取得cgi中一個字節(jié)參數(shù)。 6、其它環(huán)境變量 除了傳送數(shù)據(jù)之外，還可通過預先確定環(huán)境變量變量，把一些附加信息傳送到外部程序。主要的環(huán)境變量：remoteaddr：產(chǎn)生執(zhí)行程序請求的客戶機的ip地址。用途：用于防止未經(jīng)許可的客戶機訪問你的應

56、用。remotehost：正在運行的客戶機名稱。remoteuser：serverport：已接收請求的服務器端口號，通常為80。querystring：當使用get方式時，存儲著傳送到服務器的數(shù)據(jù)。requestmethod：getpost？contentlength：客戶機傳送到服務器的數(shù)據(jù)的長度，程序用這個變量來了解將從標準輸入設備讀取多少數(shù)據(jù)httpreferer：與你的cgi建立聯(lián)系的url。 7、實例： thes is a simple example of cgi 姓名： 年齡： simplecgi.c如f：編譯成simplecgi.exe.print (“content-typ

57、e: text/html”); print (“connect cgi variables”) n = 0;if (getenv ( “content-length”) n = atoi(getchar (“content-length”)for (i = 0;in; i+) putchar(getcharl);fflush (stdout); 3.8 asp技術nasp是一種嵌入了用javascript和vb script書寫的程序代碼的html網(wǎng)頁。該程序并不必送至客戶端解釋執(zhí)行，而是由iis解釋在服務器中運行，并將運行結果生成html語句與asp中非腳本代碼合并生成完整網(wǎng)頁。 基于web的系統(tǒng)，往往需要瀏覽器（前端），web server （第二層應用服務器）、database server（后端第三層）等部分?；趙eb的程序往往有基于瀏覽器和基于服務部兩部分。1常用browser有ie與netscape。標準html適應于任何瀏覽器，而種種