北航研究生課程程序語言設(shè)計(jì)原理教程

1、第14章 進(jìn)程交互機(jī)制和并發(fā)程序設(shè)計(jì)語言 如果說忙等待是人們?cè)O(shè)計(jì)、實(shí)現(xiàn)并發(fā)程序的最初嘗試。信號(hào)燈理論則為進(jìn)程交互的同步與互斥的研究打下了基礎(chǔ)。 70年代結(jié)構(gòu)化程序設(shè)計(jì)已經(jīng)比較成熟，人們利用結(jié)構(gòu)程序的概念為并發(fā)機(jī)制提供較高層的機(jī)制，并設(shè)計(jì)了一系列并發(fā)程序設(shè)計(jì)語言。 基于變量共享的并發(fā)機(jī)制提出了條件臨界區(qū)、監(jiān)控器、路徑表達(dá)式等技術(shù)。 70年代末把結(jié)構(gòu)化與通信相結(jié)合提出了遠(yuǎn)程過程調(diào)用和會(huì)合機(jī)制。 80年代又有多原語范型的機(jī)制出現(xiàn)。14.1 14.1 基于變量共享的高層并發(fā)機(jī)制基于變量共享的高層并發(fā)機(jī)制條件臨界區(qū)條件臨界區(qū)條件臨界區(qū)(Condition Critieal Region簡稱CCR)將共享

2、變量顯式地置于叫做資源的區(qū)域內(nèi)每個(gè)進(jìn)程在自己的進(jìn)程體內(nèi)指明要訪問的條件臨界區(qū)，而同一臨界區(qū)可出現(xiàn)在不同進(jìn)程之中(誰進(jìn)誰用)首先在資源中聲明共享變量: resourceresource r(共享變量聲明) 例：resourceresource sema( s:int :=n )regionregion r whenwhen B dodo S endendregionregion sema when when s0 do do s:= s-1 endend / P操作regionregion sema dodo s:= s+1 end end / V操作例: 用CCR實(shí)現(xiàn)例12-4的生產(chǎn)者與消費(fèi)者

3、pragrampragram PRODUCER_CONSUMER_CCR varvar buf:TYPE; varvar empty:sema,full:sema; resourceresource sema:(empty := 1,full := 0); processprocess PRODUCER i:1.M: looploop PRODUCERi 產(chǎn)生一條消息m; deposit: regionregion sema whenwhen empty0 dodo empty := empty - 1 endend； buf := m; regionregion sema dodo full

4、 := full + 1 end; end loopend loop; endend; processprocess CONSUMER j:1.N: looploop fetch: regionregion sema whenwhen full0 dodo full:= full - 1 end; m=buf； regionregion sema dodo empty := empty + 1 endend; CONSUMERj 消費(fèi)者取出的這條消息m; end loopend loop; endend;endend PRODUCER_CONSUMER_CCR.條件臨界區(qū)評(píng)價(jià)條件臨界區(qū)最主要的

5、優(yōu)點(diǎn)是概念清晰。此外: 無需輔助標(biāo)志和變量即可描述共享變量的任何進(jìn)程交互 程序編譯時(shí)即可保證互斥 一個(gè)進(jìn)程創(chuàng)建一個(gè)條件不需顧及其它條件是否與此條件有關(guān) 易于程序正確性證明 體現(xiàn)了共享數(shù)據(jù)傳遞的方便它的致命缺點(diǎn)是低效(和信號(hào)燈相比)。此外： 進(jìn)程和共享變量耦合太緊 臨界區(qū)利寫不利讀，一多了就太散，因而也難修改監(jiān)控器監(jiān)控器Dijkstra建議是把分散在整個(gè)程序中的regionregion語句進(jìn)一步集中成為一個(gè)模塊叫做監(jiān)控器(monitormonitor)。program monitorprogram monitor monitormonitor Mname: 共享數(shù)據(jù)聲明并初始化; procpro

6、c op1 () isis endend; . proc proc opn () isis endend; endend; process process Pname i:1.N: 局部數(shù)據(jù)聲明并初始化 beginbegin : callcall Mname.opi (實(shí)參表); : endend beginbegin 初始化，激活進(jìn)程 end monitorend monitor.例: 有界緩沖區(qū)的監(jiān)控器實(shí)現(xiàn)算法monitor monitor BOUNDED_BUFFER: var var buf1.q：TYPE; var var frout :=1，rear :=1，count := 0;

7、 var var not_fall:cond； /當(dāng)count 0 示信為真 procproc deposit (data :TYPE) isis while while count = q do wait do wait (not_full) endend; buf rear := data; rear := (rear modmod q) +1; count := count+1; signal signal (not_empty); end end; proc proc fetch (varvar result :TYPE) isis while while count=0 do wai

8、tdo wait (not_empty) end end; result := buf front; front := (front modmod q) +1; count := count -1; signal signal (not_full); end end;endend BOUNDED_BUFFER.以監(jiān)控器實(shí)現(xiàn)條件同步的技術(shù)以監(jiān)控器實(shí)現(xiàn)條件同步的技術(shù)(1) 復(fù)蓋條件變量(2) 傳遞條件(3) 有無占先對(duì)競(jìng)爭(zhēng)的并發(fā)進(jìn)程影響是很大的,由于不占先在被喚醒進(jìn)程執(zhí)行之前,監(jiān)控器不能拒絕另一進(jìn)程進(jìn)入它.(見下例*)(4) 為了防止條件信號(hào)被偷，發(fā)信號(hào)的進(jìn)程直接將條件傳入被喚醒的進(jìn)程。(見下例*

9、)(5) 會(huì)合同步 進(jìn)程交互是客戶/服務(wù)器(C/S)關(guān)系時(shí),為此兩交互進(jìn)程必須會(huì)合(rendezvou)才能得到服務(wù)。如不能到達(dá)會(huì)合的同步點(diǎn)則要相互等待。（見下例*）例* 以監(jiān)控器作信號(hào)燈monitormonitor SEMAPHORE: var var s:= 0; var var pos:cond; /當(dāng)s0，pos示信為真 proc proc P( ) isis while while s=0 dodo waitwait (pos) endend; s:= s-1; end end; proc proc V( ) isis s := s+1； signalsignal (pos); en

10、d end;endend SEMAPHORE.例*： 以監(jiān)控器實(shí)現(xiàn)的FIFO信號(hào)燈monitormonitor SEMAPHORE: var s=0; var var pos :cond； /當(dāng)V中pos隊(duì)列非空示真 proc proc P( ) isis if if s0 thenthen s:= s-1 endifendif; ifif s=0 thenthen waitwait(pos) endifendif; endend; procproc V( ) isis if if empty(pos) then then s:= s+1 endifendif; if if not empty

11、(pos) then then signalsignal(pos) endifendif; endend;endend SEMAPHORE. 注:本例中“”號(hào)表示和前一個(gè)語句并行執(zhí)行的語句,以下同.例* 貪睡的理發(fā)師的模擬解monitor monitor BARBER_SHOP: varvar barber := 0,chair :=0,open =0; var var barber_available :cond /當(dāng)barber0 示真 varvar chair_occupied :cond /當(dāng)chair0示真 varvar choor_open:cond /當(dāng)open=0示真 proc

12、proc get_haircut( ) is is /顧客調(diào)用 whilewhile barber=0 do waitdo wait (barber_available) end end; barber := barber-1; chair := chair+1； signalsignal (chair_occupied); while while open=0 do waitdo wait (door_open) endend; open := open-1； signalsignal (customer_left); end end; proc get_next_customer( ) i

13、sis proc proc finished_cut ( ) isisendend BARBER_SHOP.見下一頁見下一頁 procproc get_next_customer( ) is is /理發(fā)師調(diào)用 barber := barber+1； signal signal (barber_available); whilewhile chair=0 do waitdo wait (chair_occupied) endend; chair := chair-1; end end; proc proc finished_cut ( ) is is /理發(fā)師調(diào)用 open := open+1

14、； signal signal (door_open); while while open0 do waitdo wait (customer_left) endend; end end;各種語言實(shí)現(xiàn)監(jiān)控器時(shí)的原語語義差異各種語言實(shí)現(xiàn)監(jiān)控器時(shí)的原語語義差異監(jiān)控器有三個(gè)特征：第一，監(jiān)控器封裝了共享變量，共享變量僅能由監(jiān)控器內(nèi)的過程訪問。第二，監(jiān)控器內(nèi)的過程都是互斥地執(zhí)行的。因而共享變量不能并發(fā)訪問。第三，條件同步由wait和signal操作實(shí)現(xiàn)程序設(shè)計(jì)語言Mesa包括以上三個(gè)特征。UNIX采用上述條件同步。監(jiān)控器有時(shí)不一定必須互斥。也可以采用其它辦法實(shí)現(xiàn)條件同步(1) 實(shí)現(xiàn)條件同步的各種信號(hào)機(jī)制

15、 自動(dòng)信號(hào)AS:只要wait加上條件就可以不用signal原語了.即省去檢查signal是否執(zhí)行的開銷,程序員也不必操心是否用錯(cuò) 信號(hào)和繼續(xù)SC:當(dāng)無占先時(shí)發(fā)信號(hào)的進(jìn)程繼續(xù)執(zhí)行.直至它進(jìn)入等待或返回之前,其它進(jìn)程是不許進(jìn)入監(jiān)控器的 信號(hào)和出口SX:既然被占了先,發(fā)信號(hào)的進(jìn)程也就不等了.立即從監(jiān)控器出口或從過程返回 信號(hào)和等待SW:發(fā)信號(hào)的進(jìn)程被人占先之后處于監(jiān)控器內(nèi)等待，直到它能再次獲得互斥訪問，恢復(fù)執(zhí)行 信號(hào)和急等SU:發(fā)信號(hào)進(jìn)程被人占先之后也要等待，但保證在監(jiān)控器有新的進(jìn)程進(jìn)入之前先使它得到恢復(fù)(2) 嵌套監(jiān)控器中的互斥 在磁盤調(diào)度器之類的應(yīng)用中，一個(gè)進(jìn)程首先要爭(zhēng)取進(jìn)入磁盤去尋址，找到地址

16、后讀/寫，這樣就要設(shè)計(jì)兩個(gè)監(jiān)控器一個(gè)管理粗的磁盤資源，進(jìn)程進(jìn)入或釋放。另一個(gè)管理讀/寫區(qū)，進(jìn)程互斥地讀寫。這兩個(gè)監(jiān)控器是嵌套的 每一時(shí)刻只有一個(gè)進(jìn)程進(jìn)入監(jiān)控器，調(diào)用某個(gè)過程，我們稱它是閉式調(diào)用.在嵌套監(jiān)控器之中，這種方式容易引起死鎖。 開式調(diào)用是若有嵌套調(diào)用發(fā)生時(shí)上層互斥自動(dòng)解開，待調(diào)用返回后上層監(jiān)控器又重新閉合(獲得)互斥路徑表達(dá)式路徑表達(dá)式 1974年Campbell和Habermann提出以路徑表達(dá)式直接控制進(jìn)程順序的建議 路徑表達(dá)式是就每一資源在其開始聲明時(shí),就在其上定義操作的約束。 pathpath deposit,fetch end end /deposit和fetch并發(fā)執(zhí)行 p

17、ath path deposit;fetch endend /deposit必須先于fetch執(zhí)行 pathpath1:（deposit；fetch) endend /只能有一條路徑(但可多次執(zhí)行此路徑),兩操作交替互斥執(zhí)行. pathpath N:(1:(deposit)；1:(fetch) endend /deposit和fetch是一一對(duì)應(yīng)地互斥激活,先執(zhí)行deposit,完成的deposit個(gè)數(shù)不超過N次,且可多于fetch完成的個(gè)數(shù).由路徑表達(dá)式指明的同步約束,編譯時(shí)即可保證. 優(yōu)點(diǎn)是程序員可直接控制過程的執(zhí)行,正文清晰。但當(dāng)同步化依賴過程參數(shù)或監(jiān)控器的狀態(tài)時(shí)，表達(dá)能力差。14.2

18、14.2 基于消息傳遞的高層并發(fā)機(jī)制基于消息傳遞的高層并發(fā)機(jī)制14.2.1 14.2.1 異步消息傳遞異步消息傳遞 chanchan (:，,：)其中:為傳到信道上的數(shù)據(jù)域名(可缺省)和類型。例如: chanchan input (char); chan chan disk_access(cylinder，block，count ：int, buffer：char*); char output 1.N(1.M：char);異步通信的過濾器異步通信的過濾器chan chan input (char)，output (1.MAXLINE:char); char_to_Line: var var l

19、ine 1.MAXLINE:char，i:int :=1; loop loop receive receive input (line i); while while line i =CR andand i if if avail 0 then then /正常分配 avail := avail-1; unitid := remove (units); send send reply index (unitid)； endifendif; ifif avail = 0 then then /記住index號(hào)客戶未分 insert (pending，index) /插入阻塞隊(duì)pending en

20、dif endif; 接下一張 case case kind = RELEASE = ifif empty (pending) thenthen avail := avail+1; insert (units，unitid); endif endif; ifif not empty(pending) then then /分配unitid號(hào)資源 index := remove (pending); send send reply index (unitid); endif endif; end caseend case; end loop end loop; client i:1.N: var

21、 var unitid :int; send send request (i，ACQUIRE，0); receive receive reply i (unitid); /使用unitid號(hào)資源然后釋放它，發(fā)以下消息: send release (i，RELEASE，unitid);客戶/服務(wù)器進(jìn)程的特點(diǎn)是sendsend，receivereceive是對(duì)等的，服務(wù)器要應(yīng)答消息。本算法有N個(gè)客戶一個(gè)服務(wù)器。用其它主控程序創(chuàng)建clienti，當(dāng)它發(fā)送request后，接著執(zhí)行replyi，如發(fā)現(xiàn)未分配(未應(yīng)答)則在本處等待，直至確已分配unitid/=0再使用它。14.2.2 14.2.2 同步

22、消息傳遞同步消息傳遞通信著的順序進(jìn)程通信著的順序進(jìn)程CSPCSP(1) 通信語句 A:.B!e. /B!e 是輸出語句，目標(biāo)是B B:.A?x. /A?x 是輸入語句，源自A進(jìn)程 ! 信道名 () ? 信道名 ()我們把求最大公約數(shù)做成一服務(wù)器進(jìn)程GCD。客戶進(jìn)程client每向它發(fā)送一對(duì)整數(shù)，它求出結(jié)果發(fā)回客戶。 GCD :varvar x，y:int; looploop client ? args( x，y) while while x/=y do ifif xy thenthen x:= x-y endifendif ifif yx thenthen y:=y-x endif endif

23、; end end; client ! result (x); end loopend loop;client進(jìn)程在準(zhǔn)備好數(shù)據(jù)v1,v2和結(jié)果存儲(chǔ)空間r之后，應(yīng)有以下語句: .GCD! args(v1，v2); GCD ? result (r).其中args，result是信道端口名。(2) 選擇通信 Dijkstra 1975年提出的(警)衛(wèi)式命令。即設(shè)一布爾條件B，僅當(dāng)B為 真才執(zhí)行消息傳遞語句。所以，也叫衛(wèi)式通信。衛(wèi)式通信語句的一般形式是: B；CS; 選擇通信語句一般形式是: if if G1S1 G2S2 . GnSn endif endif GCD:varvar x，y：int;

24、while while (i:1.N) client i? args(x，y) do do whilewhile x /= y dodo ifif xy then then x:= x-y endifendif if if xy thenthen y:= y-x end ifif; end end; client ! result(x); end end; 過濾器的同步實(shí)現(xiàn)過濾器的同步實(shí)現(xiàn)sreve 1 :varvar p:= 2，i:int; print (p)；sieve 2! p; for for i := 3 toto N byby 2 dodo /發(fā)送候選奇數(shù) sieve 2 !i

25、endend.sreve j：2.L:varvar p:int，next:int; sieve j-1? p；print (p) ； /只打印“第一個(gè)”收到的 looploop sievej-1 ? next; if if next modmod p /=0 thenthen sieve i+1 ! next endifendif; end loopend loop; 客戶客戶/ /服務(wù)器的同步通信實(shí)現(xiàn)服務(wù)器的同步通信實(shí)現(xiàn)文件服務(wù)器的同步實(shí)現(xiàn)算法 File_Server i:1.N: var var fname:string，args:TYPE; var var more :bool; var

26、 var 局部緩沖區(qū)，快速緩存，磁盤地址等; whilewhile (c:1.M) client c? open (fname) do do /如名為fname的文件已打開: client ! open_reply( ); more := true; while while more = true do do if if client c? read(args) thenthen 調(diào)處理讀入數(shù)據(jù)的過程; client c! read_reply(results); if if client c? write(args) thenthen 調(diào)處理寫的過程; client c ! write_re

27、ply(results); ifif client c? close() thenthen 調(diào)關(guān)閉文件操作; more := false endif endif; end end; endend.client j:1.M : varvar serverid ：int; while while (i:1.N) File_Serveri! open(“foo”) dodo serverid := i; File_serveri ? open_reply(serverid); end end. /以下寫使用該進(jìn)程的代碼。例如，讀可寫: File_Serverserverid ! read(訪問參數(shù))

28、; File_Serverserverid ? read_reply(results); . /最后要有關(guān)閉文件的消息 14.2.2.4 14.2.2.4 同步通信的底層實(shí)現(xiàn)同步通信的底層實(shí)現(xiàn) 應(yīng)用程序分布式并發(fā)核示意圖應(yīng)用程序原語例程描述子緩沖區(qū)網(wǎng)絡(luò)接口本地核描述子緩沖區(qū)原語例程網(wǎng)絡(luò)接口本地核同步通信在最基本的操作上和異步是一樣的。當(dāng)前實(shí)現(xiàn)同步有兩種策略:(1) 集中式的同步實(shí)現(xiàn)CHPiPj集中管理，它易于檢查進(jìn)程匹配情況。然而，在分布式系統(tǒng)中，這樣多次來回通信增加了系統(tǒng)通信開銷，往往成為并行核的瓶頸。 分散式同步實(shí)現(xiàn)用異步通信原語實(shí)現(xiàn)分散式同步通信，為每個(gè)要求通信的進(jìn)程設(shè)立一個(gè)匹配信道(輸

29、出語句為一端，輸入語句為另一端)和一個(gè)應(yīng)答信道。并于有輸入語句的進(jìn)程設(shè)阻塞等候隊(duì)列.如果輸出/入語句不出現(xiàn)在警衛(wèi)子句內(nèi)處理程序要簡單得多，輸出語句出現(xiàn)在警衛(wèi)子句中情況會(huì)變得更復(fù)雜。因此CSP和Occam的最初版本均不允許在警衛(wèi)子句中有輸出語句14.3 14.3 遠(yuǎn)程過程調(diào)用和會(huì)合遠(yuǎn)程過程調(diào)用和會(huì)合調(diào)用進(jìn)調(diào)服服務(wù)進(jìn)程從創(chuàng)建到完成 call RPC 調(diào)用進(jìn)程調(diào)用進(jìn)調(diào)進(jìn)入同步點(diǎn) in等待數(shù)據(jù)通信完成call會(huì)合(等待）RPC會(huì)合14.3.1 14.3.1 遠(yuǎn)程過程調(diào)用遠(yuǎn)程過程調(diào)用RPCRPCcall Mname.opname(AP_list); 每個(gè)模塊在各自的地址空間。每當(dāng)有遠(yuǎn)程調(diào)用時(shí)，服務(wù)模塊創(chuàng)

30、建一服務(wù)進(jìn)程，調(diào)用進(jìn)程一直延遲到整個(gè)服務(wù)完成。如果同一時(shí)間只允許一個(gè)遠(yuǎn)程調(diào)用進(jìn)入本模塊，就實(shí)現(xiàn)了對(duì)共享數(shù)據(jù)的互斥訪問。多個(gè)調(diào)用者們就要排隊(duì)等待?，F(xiàn)在的問題是塊內(nèi)各操作進(jìn)程在有了遠(yuǎn)程調(diào)用之后如何同步與互斥。一個(gè)辦法最簡單；塊內(nèi)同一時(shí)間只能有一個(gè)進(jìn)程執(zhí)行(不管是局部調(diào)用還是遠(yuǎn)程的一起排隊(duì))。這樣最安全，隱含地實(shí)現(xiàn)了互斥，共享變量無需保護(hù)。但不可取，喪失了大量潛在的并發(fā)性。 現(xiàn)在多數(shù)RPC實(shí)現(xiàn)是支持模塊內(nèi)并發(fā)執(zhí)行的。其實(shí)現(xiàn)模塊可以如前所述的異步、同步、衛(wèi)式同步模式。遠(yuǎn)程調(diào)用只是其并發(fā)成分之一。我們舉例說明。14.3.2 14.3.2 會(huì)合會(huì)合call call Mname.Pname.Opi(ARG

31、_list)RPC是進(jìn)程級(jí)的(一個(gè)過程一個(gè)進(jìn)程)，且允許有多個(gè)并發(fā)進(jìn)程進(jìn)入封裝這些操作的模塊。會(huì)合是操作級(jí)的(一個(gè)進(jìn)程有若干個(gè)操作)，調(diào)用的是進(jìn)程輸出的操作，因而，操作不能是并行的，只能同時(shí)有一個(gè)操作在執(zhí)行。而每個(gè)操作都有自己的等候隊(duì)列。正是由于定義輸出操作，帶來了衛(wèi)式通信的方便性。會(huì)合的一般形式是: inin Op1 andand B1 by by e1s1 . Opn andand Bn byby ensn end inend in callcall Op1 andand B1 byby e1 . Opn andand Bn byby en end callend call會(huì)合實(shí)現(xiàn)過濾器

32、Baffer : op op deposit(data:TYPE)，fetch(varvar result:TYPE); varvar buf1.q:TYPE varvar front :=1，rear := 1，count !=0; looploop in in deposit (data) andand count 0 dodo result := buffront; front := front modmod n+1; count := count -1 endend; end loopend loop.有界緩沖區(qū)buf1.q是本地機(jī)上的共享變量。front，rear，count為控制和

33、警衛(wèi)變量14.3.3 14.3.3 AdaAda的任務(wù)的任務(wù)AdaAda的任務(wù)結(jié)構(gòu)的任務(wù)結(jié)構(gòu)tasktask TNAME isis entry ENAME (FP_list)； /可以多個(gè)endend TNAME； tasktask body TNAME isis 局部聲明；beginbegin accept accept ENAME (FP_list) is is /對(duì)應(yīng)多個(gè) 語句序列; endend ENAME;end end TNAME;任務(wù)激活后就是一個(gè)進(jìn)程。其它進(jìn)程通過 callcall TNAME.ENAME (AP_list);AdaAda的的通信與同步通信與同步（1）簡單選擇 (2) 否則選擇 (3) 衛(wèi)式選擇 （4） 延時(shí)選擇14.4 14.4 多原語的并發(fā)機(jī)制多原語的并發(fā)機(jī)制進(jìn)程交互主要技術(shù)的回顧進(jìn)程交互主要技術(shù)的回顧忙等待信號(hào)燈條件臨界區(qū)監(jiān)控器同步消息傳遞異步消息傳遞遠(yuǎn)程過程調(diào)用/會(huì)合路徑表達(dá)式多原語交