




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.1 3.1 分布式程序設(shè)計(jì)言語(yǔ)概述分布式程序設(shè)計(jì)言語(yǔ)概述 v分布式運(yùn)用程序的分類分布式運(yùn)用程序的分類 并行、高性能運(yùn)用程序。經(jīng)過并行性到達(dá)加速是在分布計(jì)算系統(tǒng)上運(yùn)轉(zhuǎn)運(yùn)用程序的最主要的緣由。 容錯(cuò)運(yùn)用程序。而分布計(jì)算系統(tǒng)具有允許部分失效的特性,即由于各處置機(jī)具有自治性,一個(gè)處置機(jī)的缺點(diǎn)不影響其他處置機(jī)的正常任務(wù),所以可靠性高。程序和數(shù)據(jù)也可在假設(shè)干處置機(jī)上復(fù)制而進(jìn)一步添加可靠性。 具有公用功能的運(yùn)用程序。一些運(yùn)用程序可以被構(gòu)呵斥一組公用的效力程序。例如文件效力、打印效力、進(jìn)程效力、終端效力、時(shí)間效力等。 固有的分布式運(yùn)用程序。有些運(yùn)用程序本
2、身就是分布的,在這種情況下,可以把任務(wù)站的集合看成一個(gè)分布計(jì)算系統(tǒng),這種運(yùn)用程序必需在分布式硬件上運(yùn)轉(zhuǎn)。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.1 3.1 分布式程序設(shè)計(jì)言語(yǔ)概述分布式程序設(shè)計(jì)言語(yǔ)概述 v分布式程序設(shè)計(jì)與順序程序設(shè)計(jì)的區(qū)別分布式程序設(shè)計(jì)與順序程序設(shè)計(jì)的區(qū)別 運(yùn)用多個(gè)處置機(jī)。對(duì)分布式程序設(shè)計(jì)支持的第一個(gè)要求就是系統(tǒng)應(yīng)該具有把一個(gè)程序的不同部分分配到不同處置機(jī)上執(zhí)行的才干。 處置機(jī)協(xié)作。各個(gè)進(jìn)程必需能相互通訊和同步,這是對(duì)分布式程序設(shè)計(jì)支持的第二個(gè)要求。 處置部分失效。在分布計(jì)算系統(tǒng)中一些CPU失效時(shí),其他CPU照樣任務(wù)。所以對(duì)分布式程序設(shè)計(jì)支持的第三個(gè)要求是能對(duì)
3、系統(tǒng)的部分失效進(jìn)展檢測(cè)并恢復(fù)。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.1 3.1 分布式程序設(shè)計(jì)言語(yǔ)概述分布式程序設(shè)計(jì)言語(yǔ)概述 v分布式程序設(shè)計(jì)言語(yǔ)的分類分布式程序設(shè)計(jì)言語(yǔ)的分類 按并行模型來(lái)分按并行模型來(lái)分 順序進(jìn)程并行言語(yǔ)。這類言語(yǔ)運(yùn)用的最根本模型是一組順序順序進(jìn)程并行言語(yǔ)。這類言語(yǔ)運(yùn)用的最根本模型是一組順序進(jìn)程,它們并行運(yùn)轉(zhuǎn),并且經(jīng)過報(bào)文傳送進(jìn)展通訊。大部分進(jìn)程,它們并行運(yùn)轉(zhuǎn),并且經(jīng)過報(bào)文傳送進(jìn)展通訊。大部分是流行的是流行的C(或或C+)和和FORTRAN的擴(kuò)展。的擴(kuò)展。 具有內(nèi)在并行性的言語(yǔ)。一些研討者以為算法言語(yǔ)不是處置具有內(nèi)在并行性的言語(yǔ)。一些研討者以為算法言語(yǔ)不
4、是處置并行性的最好言語(yǔ),由于算法言語(yǔ)是內(nèi)在順序式的,許多研并行性的最好言語(yǔ),由于算法言語(yǔ)是內(nèi)在順序式的,許多研討者研討具有內(nèi)在并行性的言語(yǔ),如函數(shù)式言語(yǔ)、邏輯言語(yǔ)討者研討具有內(nèi)在并行性的言語(yǔ),如函數(shù)式言語(yǔ)、邏輯言語(yǔ)和面向?qū)ο笱哉Z(yǔ)。和面向?qū)ο笱哉Z(yǔ)。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.1 3.1 分布式程序設(shè)計(jì)言語(yǔ)概述分布式程序設(shè)計(jì)言語(yǔ)概述 v分布式程序設(shè)計(jì)言語(yǔ)的分類分布式程序設(shè)計(jì)言語(yǔ)的分類 按通訊模型來(lái)分按通訊模型來(lái)分 在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。相互運(yùn)用在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。相互運(yùn)用SEND和和RECEIVE原語(yǔ)通訊,在網(wǎng)絡(luò)上發(fā)送報(bào)文。原語(yǔ)通
5、訊,在網(wǎng)絡(luò)上發(fā)送報(bào)文。 在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。用共享主存在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上分布的軟件。用共享主存方法實(shí)現(xiàn)報(bào)文傳送來(lái)模擬物理報(bào)文傳送通訊。方法實(shí)現(xiàn)報(bào)文傳送來(lái)模擬物理報(bào)文傳送通訊。 在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用分布式在物理分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用分布式共享存儲(chǔ)器通訊。共享存儲(chǔ)器通訊。 在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用物理在物理非分布的硬件上運(yùn)轉(zhuǎn)邏輯上非分布的軟件。運(yùn)用物理共享存儲(chǔ)器通訊。共享存儲(chǔ)器通訊。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.1 3.1 分布式程序設(shè)計(jì)言語(yǔ)概述分布式程序設(shè)計(jì)言語(yǔ)概述
6、v分布式程序設(shè)計(jì)言語(yǔ)的分類分布式程序設(shè)計(jì)言語(yǔ)的分類 容錯(cuò)模型和技術(shù)容錯(cuò)模型和技術(shù) 缺點(diǎn)的處置模型:缺點(diǎn)的處置模型: 系統(tǒng)對(duì)程序員隱匿全部處置機(jī)缺點(diǎn)。系統(tǒng)對(duì)程序員隱匿全部處置機(jī)缺點(diǎn)。 給程序員提供高層機(jī)制,使得程序員可以描畫哪些進(jìn)程和數(shù)給程序員提供高層機(jī)制,使得程序員可以描畫哪些進(jìn)程和數(shù)據(jù)是重要的,以及發(fā)生解體后怎樣恢復(fù)。據(jù)是重要的,以及發(fā)生解體后怎樣恢復(fù)。 實(shí)現(xiàn)可靠性的方法有兩種:程序設(shè)計(jì)容錯(cuò)和通訊容錯(cuò)。實(shí)現(xiàn)可靠性的方法有兩種:程序設(shè)計(jì)容錯(cuò)和通訊容錯(cuò)。 程序設(shè)計(jì)容錯(cuò)技術(shù)有三類:向前恢復(fù)試圖確定錯(cuò)誤所在并基程序設(shè)計(jì)容錯(cuò)技術(shù)有三類:向前恢復(fù)試圖確定錯(cuò)誤所在并基于這個(gè)知識(shí)矯正包含錯(cuò)誤的系統(tǒng)形狀;向后
7、恢復(fù)經(jīng)過把系統(tǒng)于這個(gè)知識(shí)矯正包含錯(cuò)誤的系統(tǒng)形狀;向后恢復(fù)經(jīng)過把系統(tǒng)恢復(fù)到錯(cuò)誤發(fā)生前的形狀來(lái)矯正系統(tǒng)形狀;錯(cuò)誤屏蔽,利用恢復(fù)到錯(cuò)誤發(fā)生前的形狀來(lái)矯正系統(tǒng)形狀;錯(cuò)誤屏蔽,利用同一個(gè)算法獨(dú)立開發(fā)幾個(gè)版本,一個(gè)最后投票系統(tǒng)用于對(duì)這同一個(gè)算法獨(dú)立開發(fā)幾個(gè)版本,一個(gè)最后投票系統(tǒng)用于對(duì)這n個(gè)版本產(chǎn)生的結(jié)果進(jìn)展投票并確定一個(gè)正確的結(jié)果。個(gè)版本產(chǎn)生的結(jié)果進(jìn)展投票并確定一個(gè)正確的結(jié)果。 通訊容錯(cuò)處置進(jìn)程通訊中發(fā)生的缺點(diǎn),通訊容錯(cuò)依賴于運(yùn)用通訊容錯(cuò)處置進(jìn)程通訊中發(fā)生的缺點(diǎn),通訊容錯(cuò)依賴于運(yùn)用的通訊方式和缺點(diǎn)的類型。的通訊方式和缺點(diǎn)的類型。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.2 3.2 并行性的
8、支持并行性的支持 v并行性的概念并行性的概念 并行性。由于分布計(jì)算系統(tǒng)有多個(gè)處置機(jī),所以可把程序分成假設(shè)干部放到多個(gè)處置機(jī)上同時(shí)運(yùn)轉(zhuǎn),這就是所謂的并行性。 偽并行性(pseudo parallelism),即把程序表示為一組并行運(yùn) 行的進(jìn)程但不論它們能否在不同的處置機(jī)上同時(shí)運(yùn)轉(zhuǎn)。 并行粒度。并行單位可以是進(jìn)程(如并發(fā)C),也可以是表達(dá)式(如Par Alfl)。普通說(shuō)來(lái),通訊代價(jià)越大,那么并行的粒度就應(yīng)該越大。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 進(jìn)程并行。普通說(shuō)來(lái),一個(gè)進(jìn)程是一個(gè)邏輯處置機(jī),順序地執(zhí)行代碼,具
9、有本人的形狀和數(shù)據(jù)。在言語(yǔ)中,進(jìn)程或進(jìn)程類型是要被闡明的,就像過程或過程類型一樣。進(jìn)程的創(chuàng)建可以由闡明隱式地完成,也可以經(jīng)過創(chuàng)建某種構(gòu)造顯式地完成。 對(duì)象并行。用下述方法擴(kuò)展順序?qū)ο竽P涂色@得并行性:(1)允許對(duì)象不用在收到報(bào)文時(shí)才活動(dòng);(2)允許接納對(duì)象在前往結(jié)果后繼續(xù)執(zhí)行;第(3)一次向幾個(gè)對(duì)象發(fā)送報(bào)文;(4)允許報(bào)文發(fā)送者繼續(xù)和接納者并行任務(wù)。第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.2 3.2 并行性的支持并行性的支持 v并行性的表示并行性的表示 語(yǔ)句并行語(yǔ)句并行PAR j=0 FOR n Aj:=Aj+1 PAR S1S2第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言
10、語(yǔ) 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的兩個(gè)子句:的兩個(gè)子句:(1) A:-B,C,D(2) A:-E,F存在兩個(gè)并行性的時(shí)機(jī):存在兩個(gè)并行性的時(shí)機(jī):(1) A的兩個(gè)子句可并行任務(wù)只到有一個(gè)勝利或兩個(gè)都失敗。的兩個(gè)子句可并行任務(wù)只到有一個(gè)勝利或兩個(gè)都失敗。(2) 每個(gè)子句中的子定理可并行任務(wù)直到它們?nèi)?/p>
11、勝利,或其每個(gè)子句中的子定理可并行任務(wù)直到它們?nèi)紕倮?,或其中一個(gè)失敗。中一個(gè)失敗。前一種并行性叫做前一種并行性叫做OR并行性,后一種叫做并行性,后一種叫做AND并行性。并行性。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報(bào)文傳送報(bào)文傳送v進(jìn)程通訊的表示方法:報(bào)文傳送和共享數(shù)據(jù)進(jìn)程通訊的表示方法:報(bào)文傳送和共享數(shù)據(jù) 設(shè)計(jì)報(bào)文傳送的通訊方式應(yīng)思索的問題:可靠的報(bào)文傳送和非可靠的報(bào)文傳送:可靠的報(bào)文傳送需求成認(rèn)報(bào)文。顯式接納和隱式接納:顯式接納時(shí),接納者執(zhí)行某一類accept語(yǔ)句指明接納哪些報(bào)文,以及當(dāng)報(bào)文到達(dá)時(shí)采取什么行動(dòng)。運(yùn)
12、用隱式接納時(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)文送給它,接納者從它那接納。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報(bào)文傳送報(bào)文傳送v進(jìn)程通訊的表示方法:報(bào)文傳送和共享數(shù)據(jù)進(jìn)程通訊的表示方法:報(bào)文傳送和共享數(shù)據(jù) 設(shè)計(jì)報(bào)文傳送的通訊方式應(yīng)思索的問題:對(duì)稱命名和非對(duì)稱命名。假設(shè)發(fā)送者和接納者相互命名,那么基于直接命名的方案是對(duì)稱的。在非對(duì)稱方案中,僅發(fā)送者找
13、接納者,在此情況下,接納者要與任何發(fā)送者相互作用。留意,運(yùn)用隱式接納報(bào)文的相互作用在命名方面總是非對(duì)稱的。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報(bào)文傳送報(bào)文傳送報(bào)文傳送通訊方式有 :同步和異步點(diǎn)到點(diǎn)報(bào)文。在同步報(bào)文傳送方式中,發(fā)送者在接納者接納報(bào)文前不斷阻塞。這樣,雙方不僅交換了數(shù)據(jù)而且還到達(dá)同步。在異步報(bào)文傳送方式中,發(fā)送者并不等待接納者預(yù)備好接納其報(bào)文,發(fā)送者在送出報(bào)文后立刻繼續(xù)任務(wù)。 會(huì)合。在Ada中會(huì)合模型基于三個(gè)概念:項(xiàng)闡明、項(xiàng)調(diào)用和接受語(yǔ)句。項(xiàng)闡明和接受語(yǔ)句是效力員程序的一部分,項(xiàng)調(diào)用在顧客端。當(dāng)進(jìn)程S調(diào)用
14、進(jìn)程R的一項(xiàng),R為此項(xiàng)執(zhí)行accept語(yǔ)句時(shí),在S和R之間發(fā)生了相互作用,叫做會(huì)合。 accept incr(X: int; Y: out int)do Y:=X+1;end第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v報(bào)文傳送報(bào)文傳送報(bào)文傳送通訊方式有 :遠(yuǎn)程過程調(diào)用(RPC)。它是雙向通訊的另一個(gè)原語(yǔ)。當(dāng)進(jìn)程S調(diào)用進(jìn)程R的過程P時(shí),由S提供的P的輸入?yún)?shù)被送給R。當(dāng)R收到調(diào)用懇求時(shí),執(zhí)行過程P,然后把輸出參數(shù)送回給S。執(zhí)行P期間S阻塞,直到輸出參數(shù)前往。這和會(huì)合機(jī)構(gòu)不同,在會(huì)合機(jī)構(gòu)中,一旦accept語(yǔ)句已執(zhí)行,那么調(diào)用者就
15、不阻塞。 一到多報(bào)文傳送。很多用于分布計(jì)算系統(tǒng)的網(wǎng)絡(luò)支持快速的廣播或組通訊設(shè)備。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v共享數(shù)據(jù)共享數(shù)據(jù)假設(shè)兩個(gè)進(jìn)程訪問同一個(gè)變量,可以實(shí)現(xiàn)另一種通訊方式:一個(gè)進(jìn)程對(duì)此變量進(jìn)展設(shè)置,另一個(gè)進(jìn)程對(duì)它進(jìn)展讀。假設(shè)兩個(gè)進(jìn)程在同一個(gè)機(jī)器上運(yùn)轉(zhuǎn),變量在此機(jī)器上存儲(chǔ),那么可直接通訊。分布進(jìn)程的共享數(shù)據(jù)方法有:分布式數(shù)據(jù)構(gòu)造和共享的邏輯變量 。分布式數(shù)據(jù)構(gòu)造。這種數(shù)據(jù)構(gòu)造可由假設(shè)干進(jìn)程同時(shí)處置。Linda言語(yǔ)運(yùn)用元組空間(tuple space)的概念實(shí)現(xiàn)分布式數(shù)據(jù)構(gòu)造。例如“jones,31,true
16、是一個(gè)有三個(gè)段的元組:一個(gè)字符串、一個(gè)整數(shù)和一個(gè)布爾值。對(duì)TS定義了三個(gè)原子操作:out操作向TS參與一個(gè)元組,read讀TS中的一個(gè)元組,in讀TS中的一個(gè)元組并刪除它。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v共享數(shù)據(jù)共享數(shù)據(jù)共享的邏輯變量。邏輯變量具有“單賦值性質(zhì),最初,它們是未賦值的,但一旦它們接納一個(gè)值就不能改動(dòng)它們。這些變量被用于進(jìn)程之間的通訊通道。如下三個(gè)目的:goal_1(X,Y), goal_2(X,Y), goal_3(X)進(jìn)展邏輯乘,用進(jìn)程P1、P2、P3并行求解。變量X是這三個(gè)進(jìn)程的通訊通道,最初是
17、未賦值的。假設(shè)三個(gè)進(jìn)程中的某個(gè)給X賦值,那么其它兩個(gè)進(jìn)程可運(yùn)用此值。類似地,Y是P1和P2的通訊通道。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v非確定性的表示和控制非確定性的表示和控制 v進(jìn)程之間的相互作用方式并不總是確定性的,有時(shí)還進(jìn)程之間的相互作用方式并不總是確定性的,有時(shí)還決議于運(yùn)轉(zhuǎn)時(shí)條件。因此,表示和控制非確定性模型被決議于運(yùn)轉(zhuǎn)時(shí)條件。因此,表示和控制非確定性模型被提出。選擇語(yǔ)句和維護(hù)的提出。選擇語(yǔ)句和維護(hù)的(guarded)Horn子句子句 是兩種表是兩種表示和控制非確定性的模型。示和控制非確定性的模型。選擇語(yǔ)句
18、。它是由如下方式的一組維護(hù)命令組成的: 維護(hù)語(yǔ)句 其中維護(hù)(guard)由一個(gè)布爾表達(dá)式和某一類“通訊懇求組成。布爾表達(dá)式必需無(wú)副作用,由于它能夠在執(zhí)行該選擇語(yǔ)句過程中被計(jì)算多次。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.3 3.3 進(jìn)程通訊與同步的支持進(jìn)程通訊與同步的支持 v非確定性的表示和控制非確定性的表示和控制 維護(hù)的Horn子句。邏輯程序本質(zhì)上就不是確定性的。并行邏輯言語(yǔ)不是對(duì)一給定的謂詞一個(gè)又一個(gè)地實(shí)驗(yàn)子句,失敗時(shí)回溯,而是并行地搜索一切那些子句,并且在這些并行執(zhí)行期間直到有一個(gè)并行執(zhí)行提交前不允許任何賦值對(duì)外部是可見的,這叫做OR并行性。但是,這不能無(wú)限地進(jìn)展,由于
19、并行任務(wù)的搜索途徑隨證明的長(zhǎng)度而指數(shù)地增長(zhǎng)。 很普遍的控制OR并行性技術(shù)是提交選擇非確定性,它非確定地選擇一個(gè)可選擇的子句,取消其他子句。它是基于維護(hù)的Horn子句,方式如下:A:-G1,Gn|B1,Bmn0,m0目的Gi的合取(與操作)叫做維護(hù),目的Bi的合取叫做體(body)。提交操作符“|也是一個(gè)合取操作符。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v分布式程序設(shè)計(jì)言語(yǔ)的分類:分布式程序設(shè)計(jì)言語(yǔ)的分類: 分布式程序設(shè)計(jì)言語(yǔ)分布地址空間共享地址空間同步報(bào)文傳送異步報(bào)文傳送會(huì)合遠(yuǎn)程過程調(diào)用多重原語(yǔ)對(duì)象原子事務(wù)處置函
20、數(shù)式言語(yǔ)邏輯言語(yǔ)分布數(shù)據(jù)構(gòu)造第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v同步式報(bào)文傳送言語(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)程的體中運(yùn)用。 通訊:CSP進(jìn)程
21、不能運(yùn)用全局變量相互通訊,只能運(yù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中。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v同步式報(bào)文傳送言語(yǔ)同步式報(bào)文傳送言語(yǔ) : 可傳送的數(shù)據(jù)類型:簡(jiǎn)單數(shù)據(jù)和有構(gòu)造的數(shù)據(jù)均可傳送與賦值,只需發(fā)送的值與接納它的變量類型一樣??山o有構(gòu)造的數(shù)據(jù)一個(gè)名字(構(gòu)造符),如下例中的pair:X:Y!
22、 pair(35,60)|Y:n,m:integer;X? pair(n,m)可運(yùn)用空構(gòu)造符對(duì)兩個(gè)進(jìn)程進(jìn)展同步但不傳送任何實(shí)踐數(shù)據(jù)。非確定性的表示:CSP中運(yùn)用alternative構(gòu)造表示非確定性,它由一組維護(hù)(后面跟著待執(zhí)行的動(dòng)作)組成。維護(hù)可包含布爾表達(dá)式和一個(gè)輸入語(yǔ)句。CSP允許進(jìn)程根據(jù)當(dāng)前通訊的輸入和名字段的信息有選擇地接納。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v異步式報(bào)文傳送言語(yǔ)異步式報(bào)文傳送言語(yǔ) : 并行性單位:NIL中的并行性是基于所謂進(jìn)程模型。進(jìn)程不僅是并行性的單位,也是模塊化的單位。進(jìn)程四處
23、置機(jī)變換是實(shí)現(xiàn)上的問題,由編譯和運(yùn)轉(zhuǎ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)程可以銜接其擁有的輸入口和輸出口。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v異步式報(bào)文傳送言語(yǔ)異步式報(bào)文傳送言語(yǔ) : 通訊類型:NIL既支持同步通訊也支持異步通訊,可把單個(gè)輸入口銜接到幾個(gè)輸出口,所以在輸入口可以有多個(gè)掛起的報(bào)文,因此必需排隊(duì)。非
24、確定表示:NIL提供一個(gè)維護(hù)命令風(fēng)格的語(yǔ)句用于在任何輸入口上等待報(bào)文。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v基于會(huì)合的言語(yǔ)基于會(huì)合的言語(yǔ) : Ada:并行性表示:其并行性是基于順序進(jìn)程,叫作義務(wù)(task),每個(gè)義務(wù)具有一定的類型。義務(wù)由闡明部分(闡明其他義務(wù)如何與其通訊)和一個(gè)體(包含它的可以執(zhí)行的語(yǔ)句)組成。通訊:義務(wù)通常經(jīng)過會(huì)合機(jī)制通訊,也經(jīng)過共享變量通訊,會(huì)合機(jī)制基于項(xiàng)闡明、項(xiàng)調(diào)用和接受語(yǔ)句。 非確定性表示:Ada運(yùn)用select語(yǔ)句表示非確定性。這個(gè)語(yǔ)句用于三個(gè)目的:從一組未處置的懇求中非確定地選擇一
25、個(gè)項(xiàng)調(diào)用;有條件地調(diào)用一項(xiàng)(即僅當(dāng)被調(diào)用的義務(wù)預(yù)備好立刻接受它)和為一個(gè)項(xiàng)調(diào)用設(shè)置時(shí)限。 容錯(cuò):Ada有一個(gè)異常處置機(jī)制處置軟件缺點(diǎn),但言語(yǔ)定義未闡明硬件缺點(diǎn)問題。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v基于會(huì)合的言語(yǔ)基于會(huì)合的言語(yǔ) : 并發(fā)C:進(jìn)程創(chuàng)建:它運(yùn)用create原語(yǔ)顯式地創(chuàng)建進(jìn)程,并可向創(chuàng)建的進(jìn)程傳送參數(shù)。可賦給新進(jìn)程一個(gè)優(yōu)先權(quán),以后新進(jìn)程或其他進(jìn)程還可以改動(dòng)此優(yōu)先權(quán)。通訊:進(jìn)程經(jīng)過會(huì)合機(jī)構(gòu)相互通訊。并發(fā)C中的事務(wù)處置與Ada中的項(xiàng)不同,可以前往一個(gè)值,并支持異步事務(wù)處置(但并不前往值)。并發(fā)C支持一
26、個(gè)比Ada中的功能更強(qiáng)的accept語(yǔ)句,它根據(jù)事務(wù)處置參數(shù)的值,可以有條件地接受一些事務(wù)處置 。非確定性表示:運(yùn)用select語(yǔ)句表示非確定性。容錯(cuò):基于進(jìn)程復(fù)制。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v基于遠(yuǎn)程過程調(diào)用的言語(yǔ)基于遠(yuǎn)程過程調(diào)用的言語(yǔ) : DP的進(jìn)程:每個(gè)處置機(jī)公用于執(zhí)行一個(gè)進(jìn)程,但每個(gè)進(jìn)程可包含幾個(gè)處置線程,這些線程以偽并行方式運(yùn)轉(zhuǎn)。通訊:DP進(jìn)程相互調(diào)用對(duì)方的公用過程進(jìn)展通訊,用如下方式調(diào)用: Call P.f(exps,vars)這里P是被調(diào)用進(jìn)程的名字,f是由P闡明的過程名字,表達(dá)式是輸入
27、參數(shù),前往值賦予變量vars。第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v多重通訊原語(yǔ)多重通訊原語(yǔ) : SR是由一個(gè)或多個(gè)資源(resource)組成。資源是運(yùn)轉(zhuǎn)在一個(gè)物理節(jié)點(diǎn)(單處置機(jī)或共享存儲(chǔ)器多處置機(jī))的一個(gè)程序模塊,可動(dòng)態(tài)創(chuàng)建,并可選擇地分配到指定機(jī)器上運(yùn)轉(zhuǎn)。 資源可包含多個(gè)進(jìn)程,它們共享數(shù)據(jù)。資源可包含一個(gè)初始進(jìn)程和終結(jié)進(jìn)程,它們隱式地被創(chuàng)建和運(yùn)轉(zhuǎn)。 SR運(yùn)用類似于select語(yǔ)句的構(gòu)造處置非確定性。 SR操作的定義類似過程的定義,可看成一個(gè)過程或入口點(diǎn)(entry point)。 第三章第三章 分布式程序設(shè)
28、計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v多重通訊原語(yǔ)多重通訊原語(yǔ) : 把操作的兩種效力方式和兩種調(diào)用方式結(jié)合起來(lái)就有四種進(jìn)程通訊方法 。 call(同步)send(異步)entry(同步)會(huì)合報(bào)文傳送process(異步)RPCFork第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v基于對(duì)象的言語(yǔ)基于對(duì)象的言語(yǔ) : 對(duì)象:Emerald把一切實(shí)體都看成對(duì)象。對(duì)象可以是自動(dòng)的或被動(dòng)的。并行性:Emerald中的并行性表如今自動(dòng)對(duì)象的同時(shí)執(zhí)行上。一些對(duì)象可從一個(gè)處置機(jī)上遷移
29、到另一個(gè)上。 分布式系統(tǒng)中,很多對(duì)象可以并行運(yùn)轉(zhuǎn),Emerald為本地和遠(yuǎn)程調(diào)用提供一樣的語(yǔ)義。 對(duì)象的遷移可由編譯程序或程序員運(yùn)用幾個(gè)簡(jiǎn)單原語(yǔ)發(fā)動(dòng)。對(duì)象可作為遠(yuǎn)程操作中的參數(shù)傳送。對(duì)該參數(shù)對(duì)象的每次訪問都會(huì)產(chǎn)生另一個(gè)遠(yuǎn)程調(diào)用。為了使這類調(diào)用最正確化,先把參數(shù)對(duì)象傳送到目的處置機(jī),后把該對(duì)象傳送回來(lái)。由于這種情況經(jīng)常發(fā)生,所以引入一個(gè)新的參數(shù)傳送類型,叫做傳送調(diào)用(call_by_move)以便有效地完成這種操作。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.4 3.4 邏輯上分布地址空間的言語(yǔ)邏輯上分布地址空間的言語(yǔ) v基于原子事務(wù)處置的言語(yǔ)基于原子事務(wù)處置的言語(yǔ) : Argus
30、: 主要特點(diǎn):guardian(維護(hù)者)和action(活動(dòng))。維護(hù)者是能從解體中幸存下來(lái)的模塊,而活動(dòng)是一組原子執(zhí)行。 為了在堅(jiān)持原子語(yǔ)義下允許活動(dòng)的并行,運(yùn)用原子對(duì)象,它是一種原子數(shù)據(jù)類型。Argus提供一些原子類型,用戶也可本人定義一些。 Argus提供兩級(jí)同步機(jī)制:用于偽并行進(jìn)程的和用于并行活動(dòng)的。 mutex類型提供對(duì)維護(hù)者內(nèi)各進(jìn)程所共享的對(duì)象的互斥訪問。 在容錯(cuò)方面,可把某些維護(hù)者對(duì)象闡明成stable,存放到鞏固存儲(chǔ)器中,假設(shè)某個(gè)節(jié)點(diǎn)解體了,那么可在鞏固存儲(chǔ)器中檢索并得到恢復(fù)。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.5 3.5 邏輯上共享地址空間的言語(yǔ)邏輯上共享
31、地址空間的言語(yǔ) v并行函數(shù)式言語(yǔ)并行函數(shù)式言語(yǔ) : ParAlfl利用隱式函數(shù)并行性。函數(shù)并行性通常是細(xì)粒度的。由于能夠有比處置機(jī)數(shù)多得多的義務(wù)要并行執(zhí)行,所以運(yùn)用變換方法指定哪個(gè)表達(dá)式在哪臺(tái)處置機(jī)上計(jì)算。 如:(f(x) $on ($self-1)+(g(y) $on ($self+1) 通訊和同步是隱式的,所以不需求顯式言語(yǔ)構(gòu)造。某個(gè)計(jì)算需求另一個(gè)計(jì)算的結(jié)果但還未出來(lái)時(shí)那么受阻。 語(yǔ)義是基于緩慢計(jì)算(lazy evaluation),即一個(gè)表達(dá)式僅當(dāng)其結(jié)果被要求時(shí)才進(jìn)展計(jì)算。普通說(shuō)來(lái),程序員不需關(guān)懷計(jì)算次序,但為了有效性要對(duì)計(jì)算次序進(jìn)展控制。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)
32、言語(yǔ) 3.5 3.5 邏輯上共享地址空間的言語(yǔ)邏輯上共享地址空間的言語(yǔ) v并行邏輯言語(yǔ)并行邏輯言語(yǔ) : 并發(fā)PROLOG : 并行性來(lái)自合取的各目的的AND并行計(jì)算和維護(hù)Horn子句的各維護(hù)的OR并行計(jì)算。 并發(fā)PROLOG中的并行進(jìn)程運(yùn)用共享邏輯變量通訊。同步是基于在只讀變量上暫停的方法。 并發(fā)PROLOG運(yùn)用維護(hù)Horn子句處置非確定性。第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.5 3.5 邏輯上共享地址空間的言語(yǔ)邏輯上共享地址空間的言語(yǔ) v并行邏輯言語(yǔ)并行邏輯言語(yǔ) : PARLOG: AND/OR并行性由程序員控制。有兩種不同的合取操作符:“.并行計(jì)算各合取;“&串
33、行計(jì)算各合取(自左至右)。 進(jìn)程經(jīng)過共享變量進(jìn)展通訊,而同步方法是在無(wú)界共享變量上掛起。PARLOG有個(gè)機(jī)構(gòu)用來(lái)指定哪些進(jìn)程可以為某變量產(chǎn)生賦值。假設(shè)輸入自變量未被賦值,那么相應(yīng)的合一將掛起,當(dāng)某其他進(jìn)程為該變量賦值時(shí)此合一將繼續(xù)。 PARLOG運(yùn)用維護(hù)的Horn子句用于非確定性。PARLOG中的維護(hù)可測(cè)試任何輸入變量并為子句的部分變量賦值,但不能給在輸入自變量中傳送的變量賦值。第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.5 3.5 邏輯上共享地址空間的言語(yǔ)邏輯上共享地址空間的言語(yǔ) v基于分布數(shù)據(jù)構(gòu)造言語(yǔ)基于分布數(shù)據(jù)構(gòu)造言語(yǔ) : Linda: Linda的目的是將程序員從并行計(jì)算和
34、并發(fā)事件的思索中解脫出來(lái),從而使并行程序設(shè)計(jì)在概念上類似于順序程序設(shè)計(jì)。 Linda運(yùn)用簡(jiǎn)單原語(yǔ)eval創(chuàng)建順序進(jìn)程,但不為程序設(shè)計(jì)人員提供方法把進(jìn)程變換四處置機(jī)上,實(shí)踐上并不需求,由于每個(gè)處置機(jī)執(zhí)行一個(gè)進(jìn)程。 Linda運(yùn)用元組空間通訊模型。進(jìn)程通訊要向TS插入新元組、讀和移去現(xiàn)存的元組。進(jìn)程同步方法是運(yùn)用阻塞read和in操作等待元組可用。 Linda的容錯(cuò)網(wǎng)絡(luò)內(nèi)核是基于TS的復(fù)制上的。 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.5 3.5 邏輯上共享地址空間的言語(yǔ)邏輯上共享地址空間的言語(yǔ) v基于分布數(shù)據(jù)構(gòu)造言語(yǔ)基于分布數(shù)據(jù)構(gòu)造言語(yǔ) : Orca :這種言語(yǔ)的并行性是基于順序
35、進(jìn)程。運(yùn)用顯式的fork原語(yǔ)派生新的子進(jìn)程并把參數(shù)傳送給它。參數(shù)可以是數(shù)值,也可以是由該子進(jìn)程的闡明部分指出共享的籠統(tǒng)數(shù)據(jù)類型。進(jìn)程之間通訊經(jīng)過共享數(shù)據(jù)對(duì)象間接地進(jìn)展。每個(gè)對(duì)象都屬于籠統(tǒng)數(shù)據(jù)類型,每個(gè)籠統(tǒng)數(shù)據(jù)類型的定義由闡明部分和實(shí)現(xiàn)部分組成。闡明部分列出可對(duì)該給定類型的對(duì)象進(jìn)展的各種操作。一個(gè)操作的實(shí)現(xiàn)可由一個(gè)或多個(gè)維護(hù)語(yǔ)句組成。假設(shè)是這樣,一個(gè)操作的調(diào)用受阻直到至少有一個(gè)維護(hù)勝利,接著非確定性地選擇一個(gè)為真的維護(hù),執(zhí)行其語(yǔ)句不再受阻。 共享數(shù)據(jù)對(duì)象模型在分布式系統(tǒng)中有效的實(shí)現(xiàn)方法是復(fù)制對(duì)象。假設(shè)共享對(duì)象不經(jīng)常改動(dòng),可在經(jīng)常讀它的處置機(jī)上維持副本,對(duì)本地副本進(jìn)展讀操作,就可減少通訊開銷。原語(yǔ)
36、 語(yǔ)言的例子并行性表示并行性 進(jìn)程 Ada、并發(fā) C、Linda、NIL 對(duì)象 Emerald、并發(fā) Smalltalk 語(yǔ)句 Occam 表達(dá)式 ParAlfl、FX-87 子句 并發(fā) PROLOG、PARLOG變換 靜態(tài) Occam、StarMod 動(dòng)態(tài) 并發(fā) PROLOG、ParAlfl 遷移 Emerald通信報(bào)文傳遞 點(diǎn)到點(diǎn)報(bào)文 CSP、Occam、NIL 會(huì)合 Ada、并發(fā) C 遠(yuǎn)程過程調(diào)用 DP、并發(fā) CLU、LYNX 一對(duì)多報(bào)文 BSP、StarMod數(shù)據(jù)共享 分布式數(shù)據(jù)結(jié)構(gòu) Linda、Orca 共享邏輯變量 并發(fā) PROLOG、PARLOG非確定性 選擇語(yǔ)句 CSP、Occ
37、am、Ada、并發(fā) C、SR 保護(hù) Horn 子句 并發(fā) PROLOG、PARLOG部分失效故障檢測(cè) Ada、SR原子事務(wù)處理 Argus、Aeolus、Avalon透明容錯(cuò) NIL第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL vDCDL中的通用符號(hào)中的通用符號(hào) : 選擇*重復(fù)|并行條件;順序send輸出:=賦值receive輸入: :定義開始結(jié)束任意(全稱量詞)存在(存在量詞)=相等不等或且反第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.63.6分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL vD
38、CDL中并行性表示中并行性表示 :vDCDL中的并行單元是語(yǔ)句。中的并行單元是語(yǔ)句。v一組并行語(yǔ)句表示為:一組并行語(yǔ)句表示為:vS1|S2|Snv而一組順序語(yǔ)句表示為:而一組順序語(yǔ)句表示為:v S1;S2;Sn v一組語(yǔ)句可以用語(yǔ)句優(yōu)先圖一組語(yǔ)句可以用語(yǔ)句優(yōu)先圖表示表示v S1;S2;S3|S4;S5;S6|S7 S1S2S3S4S7S5S6S1S2S3S4S7S5S6第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v選擇語(yǔ)句選擇語(yǔ)句 :v一個(gè)選擇語(yǔ)句表示為:一個(gè)選擇語(yǔ)句表示為:vG1C1G1C1G2C2G2C2GnC
39、nGnCnv選擇語(yǔ)句選擇其組成的被維護(hù)的命令之一執(zhí)行。假設(shè)選擇語(yǔ)句選擇其組成的被維護(hù)的命令之一執(zhí)行。假設(shè)多余一個(gè)命令可被選擇,選擇將是不確定的。如下的選多余一個(gè)命令可被選擇,選擇將是不確定的。如下的選擇語(yǔ)句擇語(yǔ)句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ì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v反復(fù)語(yǔ)句反復(fù)語(yǔ)句 :v一
40、個(gè)反復(fù)語(yǔ)句指定其組成選擇語(yǔ)句的交互次數(shù),這些一個(gè)反復(fù)語(yǔ)句指定其組成選擇語(yǔ)句的交互次數(shù),這些語(yǔ)句帶維護(hù)或不帶維護(hù),它的方式有如下三種:語(yǔ)句帶維護(hù)或不帶維護(hù),它的方式有如下三種:v1 1* * 帶維護(hù)的選擇語(yǔ)句帶維護(hù)的選擇語(yǔ)句 v2 2* * 不帶維護(hù)的選擇語(yǔ)句不帶維護(hù)的選擇語(yǔ)句 v3 3(n)(n)選擇語(yǔ)句選擇語(yǔ)句 v在第一種情況下,當(dāng)一切的維護(hù)都經(jīng)過時(shí),反復(fù)語(yǔ)句在第一種情況下,當(dāng)一切的維護(hù)都經(jīng)過時(shí),反復(fù)語(yǔ)句終止。在第二種情況下,執(zhí)行不終止。第三種是一個(gè)特終止。在第二種情況下,執(zhí)行不終止。第三種是一個(gè)特別的反復(fù)語(yǔ)句,其反復(fù)的次數(shù)最多為別的反復(fù)語(yǔ)句,其反復(fù)的次數(shù)最多為n n。 第三章第三章 分布式
41、程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v反復(fù)語(yǔ)句反復(fù)語(yǔ)句 :v例例1 1:給出一個(gè)確定的數(shù)組:給出一個(gè)確定的數(shù)組b1:m1:nb1:m1:n,其中,其中1m1m,1n1ni:=i+1;j:=1jni:=i+1;j:=1v v 第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v反復(fù)語(yǔ)句反復(fù)語(yǔ)句 :v例例2 2:確定一個(gè):確定一個(gè)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ì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v語(yǔ)句并發(fā)語(yǔ)句并發(fā)( (或并行或并行) )的條件的條件v當(dāng)兩個(gè)語(yǔ)句并發(fā)執(zhí)行時(shí),能夠產(chǎn)生與順序執(zhí)行不同的當(dāng)兩個(gè)語(yǔ)句并發(fā)
43、執(zhí)行時(shí),能夠產(chǎn)生與順序執(zhí)行不同的結(jié)果。讓我們先定義兩個(gè)符號(hào):結(jié)果。讓我們先定義兩個(gè)符號(hào):v(1) R(Si)(1) R(Si),Si Si的讀集,即在的讀集,即在Si Si中被援用的一切變量中被援用的一切變量的集合。的集合。v(2) W(Si)(2) W(Si),Si Si的寫集,即在的寫集,即在Si Si中被修正的一切變量中被修正的一切變量的集合。的集合。 vBernsteinBernstein提出了以下三個(gè)條件,對(duì)于兩個(gè)并發(fā)執(zhí)行的提出了以下三個(gè)條件,對(duì)于兩個(gè)并發(fā)執(zhí)行的語(yǔ)句語(yǔ)句S1S1和和S2S2,必需滿足這三個(gè)條件才干使它們并發(fā)執(zhí)行,必需滿足這三個(gè)條件才干使它們并發(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ì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v語(yǔ)句并發(fā)語(yǔ)句并發(fā)( (或并行或并行) )的條件的條件v 我們可以用我們可以用BernsteinBernstein條件來(lái)尋覓語(yǔ)句中可以并行執(zhí)條件來(lái)尋覓語(yǔ)句中可以并行執(zhí)行的最大子集。為此我們定義了一個(gè)無(wú)向圖,節(jié)點(diǎn)集行的最大子集。
45、為此我們定義了一個(gè)無(wú)向圖,節(jié)點(diǎn)集由給定語(yǔ)句集組成,假設(shè)由給定語(yǔ)句集組成,假設(shè)Si|SjSi|Sj,那么節(jié)點(diǎn),那么節(jié)點(diǎn)Si Si和和Sj Sj相連,相連,可以并行執(zhí)行的最大的語(yǔ)句子集對(duì)應(yīng)于最大的完全子可以并行執(zhí)行的最大的語(yǔ)句子集對(duì)應(yīng)于最大的完全子圖。圖。 例如:S1: a:=xy, S2: b:=xz, S3: x:=yz, S4: c:=y-1。顯然,S1,S2,S4構(gòu)成最大的完全子圖,也就是說(shuō),S1|S2|S4。 S1S2S3S4S1S2S3S4第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)DCDL DCDL v DCDLDCDL中的
46、通訊中的通訊v 輸出命令的方式為:輸出命令的方式為:vsend message_list to destinationsend message_list to destinationv其中其中destinationdestination是一個(gè)進(jìn)程名是一個(gè)進(jìn)程名( (一對(duì)一通訊一對(duì)一通訊) )或代或代表一切其他進(jìn)程表一切其他進(jìn)程( (一對(duì)一切通訊一對(duì)一切通訊) )的關(guān)鍵字的關(guān)鍵字allall。v 輸入命令的方式為:輸入命令的方式為:vreceive message_list from sourcereceive message_list from sourcev其中其中sourcesource是
47、一個(gè)進(jìn)程名,這個(gè)輸入命令支持顯是一個(gè)進(jìn)程名,這個(gè)輸入命令支持顯式和隱式的報(bào)文接納。式和隱式的報(bào)文接納。v隱式的報(bào)文接納表示為:隱式的報(bào)文接納表示為:vreceive message_listreceive message_list第三章第三章 分布式程序設(shè)計(jì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)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ì)言語(yǔ)分布式程序設(shè)計(jì)言語(yǔ) 3.6 3.6 分布式控制描畫言語(yǔ)分布式控制描畫言語(yǔ)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 湖北省2023~2024學(xué)年高一數(shù)學(xué)下學(xué)期6月聯(lián)考試卷含答案
- 部編版三年級(jí)下冊(cè)語(yǔ)文看拼音寫詞語(yǔ)復(fù)習(xí)田字格
- 山西省重點(diǎn)名校2025年初三“一診”模擬考試物理試題含解析
- 山東省濟(jì)南市高新區(qū)2024-2025學(xué)年數(shù)學(xué)五下期末統(tǒng)考模擬試題含答案
- 南通科技職業(yè)學(xué)院《英語(yǔ)教學(xué)技能訓(xùn)練》2023-2024學(xué)年第二學(xué)期期末試卷
- 江蘇省江蘇省大豐市萬(wàn)盈初級(jí)中學(xué)2025屆學(xué)業(yè)水平考試物理試題含解析
- 遼寧省鐵嶺市銀州區(qū)2024-2025學(xué)年數(shù)學(xué)三下期末質(zhì)量檢測(cè)模擬試題含解析
- 江蘇省揚(yáng)州市江都區(qū)國(guó)際校2025屆初三最后一次模擬考試英語(yǔ)試題含答案
- 婺源縣2025屆四下數(shù)學(xué)期末學(xué)業(yè)質(zhì)量監(jiān)測(cè)模擬試題含解析
- 延安大學(xué)西安創(chuàng)新學(xué)院《古代詩(shī)人研究》2023-2024學(xué)年第二學(xué)期期末試卷
- 成都地鐵運(yùn)營(yíng)有限公司招聘筆試題庫(kù)2024
- 小小理財(cái)師教學(xué)課件
- 知識(shí)產(chǎn)權(quán)法(四川師范大學(xué))智慧樹知到答案2024年四川師范大學(xué)
- 2024-2030年中國(guó)3D IC和2.5D IC封裝行業(yè)市場(chǎng)發(fā)展趨勢(shì)與前景展望戰(zhàn)略分析報(bào)告
- 福州流動(dòng)人口登記表
- 北京市昌平區(qū)2023-2024學(xué)年高二下學(xué)期期末考試政治試題
- 2020-2021學(xué)年天津市河西區(qū)八年級(jí)(下)期中語(yǔ)文試卷(附答案詳解)
- 人教版初中化學(xué)實(shí)驗(yàn)?zāi)夸?總表)
- 監(jiān)控工程驗(yàn)收單-范本模板
- DLT 5175-2021 火力發(fā)電廠熱工開關(guān)量和模擬量控制系統(tǒng)設(shè)計(jì)規(guī)程-PDF解密
- 公路工程設(shè)計(jì)方案設(shè)計(jì)工作量及計(jì)劃安排
評(píng)論
0/150
提交評(píng)論