《北航研究生課程程序語言設計原理教程第14章.ppt》由會員分享，可在線閱讀，更多相關(guān)《北航研究生課程程序語言設計原理教程第14章.ppt（40頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、在自己的進程體內(nèi)指明要訪問的條件臨界區(qū)，而同一臨界區(qū)可出現(xiàn)在不同進程之中(誰進誰用) 首先在資源中聲明共享變量: resource r(共享變量聲明) 例：resource sema( s:int :=n ) region r when B do S end region sema when s0 do s:= s-1 end // P操作 region sema do s:= s+1 end // V操作,例: 用CCR實現(xiàn)例12-4的生產(chǎn)者與消費者 pragram PRODUCER_CONSUMER_CCR var buf:TYPE; var empty:sema,full:sem

3、a; resource sema:(empty := 1,full := 0); process PRODUCER i:1..M:: loop PRODUCERi 產(chǎn)生一條消息m; deposit: region sema when empty0 do empty := empty - 1 end； buf := m; region sema do full := full + 1 end; end loop; end; process CONSUMER j:1..N:: loop fetch: region sema when full0 do full:= full - 1

4、end; m=buf； region sema do empty := empty + 1 end; CONSUMERj 消費者取出的這條消息m; end loop; end; end PRODUCER_CONSUMER_CCR.,條件臨界區(qū)評價 條件臨界區(qū)最主要的優(yōu)點是概念清晰。此外: 無需輔助標志和變量即可描述共享變量的任何進程交互 程序編譯時即可保證互斥 一個進程創(chuàng)建一個條件不需顧及其它條件是否與此條件有關(guān) 易于程序正確性證明 體現(xiàn)了共享數(shù)據(jù)傳遞的方便 它的致命缺點是低效(和信號燈相比)。此外： 進程和共享變量耦合太緊 臨界區(qū)利寫不利讀，一多了就太散，因而也難修改,監(jiān)控器 Dijk

5、stra建議是把分散在整個程序中的region語句進一步集中成為一個模塊叫做監(jiān)控器(monitor)。 program monitor monitor Mname:: 共享數(shù)據(jù)聲明并初始化; proc op1 () is end; ... proc opn () is end; end; process Pname i:1..N:: 局部數(shù)據(jù)聲明并初始化 begin : call Mname.opi (實參表); : end begin 初始化，激活進程 end monitor.,例: 有界緩沖區(qū)的監(jiān)控器實現(xiàn)算法 monitor BOUNDED_BUFFER::

6、var buf1..q：TYPE; var frout :=1，rear :=1，count := 0; var not_fall:cond； //當count 0 示信為真 proc deposit (data :TYPE) is while count = q do wait (not_full) end; buf rear := data; rear := (rear mod q) +1; count := count+1; signal (not_empty); end; proc fetch (var result :TYPE) is while count=0 do

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

8、)關(guān)系時,為此兩交互進程必須會合(rendezvou)才能得到服務。如不能到達會合的同步點則要相互等待。（見下例***）,例* 以監(jiān)控器作信號燈 monitor SEMAPHORE:: var s:= 0; var pos:cond; //當s0，pos示信為真 proc P( ) is while s=0 do wait (pos) end; s:= s-1; end; proc V( ) is s := s+1； signal (pos); end; end SEMAPHORE.,例*： 以監(jiān)控器實現(xiàn)的FIFO信號燈 monitor SEMAPHORE:: var s=0; var

9、 pos :cond； //當V中pos隊列非空示真 proc P( ) is if s0 then s:= s-1 endif; if s=0 then wait(pos) endif; end; proc V( ) is if empty(pos) then s:= s+1 endif; if not empty(pos) then signal(pos) endif; end; end SEMAPHORE. 注:本例中“”號表示和前一個語句并行執(zhí)行的語句,以下同.,例*** 貪睡的理發(fā)師的模擬解 monitor BARBER_SHOP:: var barber := 0,chair

10、 :=0,open =0; var barber_available :cond //當barber0 示真 var chair_occupied :cond //當chair0示真 var choor_open:cond //當open=0示真 proc get_haircut( ) is //顧客調(diào)用 while barber=0 do wait (barber_available) end; barber := barber-1; chair := chair+1； signal (chair_occupied); while open=0 do wai

11、t (door_open) end; open := open-1； signal (customer_left); end; proc get_next_customer( ) is proc finished_cut ( ) is end BARBER_SHOP.,,見下一頁,proc get_next_customer( ) is //理發(fā)師調(diào)用 barber := barber+1； signal (barber_available); while chair=0 do wait (chair_occupied) end; chair := chair-1; end; p

12、roc finished_cut ( ) is //理發(fā)師調(diào)用 open := open+1； signal (door_open); while open0 do wait (customer_left) end; end;,各種語言實現(xiàn)監(jiān)控器時的原語語義差異 監(jiān)控器有三個特征：第一，監(jiān)控器封裝了共享變量，共享變量僅能由監(jiān)控器內(nèi)的過程訪問。第二，監(jiān)控器內(nèi)的過程都是互斥地執(zhí)行的。因而共享變量不能并發(fā)訪問。第三，條件同步由wait和signal操作實現(xiàn) 程序設計語言Mesa包括以上三個特征。UNIX采用上述條件同步。監(jiān)控器有時不一定必須互斥。也可以采用其它辦法實現(xiàn)條件同步,(1) 實現(xiàn)條

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

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

15、path deposit;fetch end //deposit必須先于fetch執(zhí)行 path1:（deposit；fetch) end //只能有一條路徑(但可多次執(zhí)行此路徑),兩操作交替互斥執(zhí)行. path N:(1:(deposit)；1:(fetch)) end //deposit和fetch是一一對應地互斥激活,先執(zhí)行deposit,完成的deposit個數(shù)不超過N次,且可多于fetch完成的個數(shù).由路徑表達式指明的同步約束,編譯時即可保證. 優(yōu)點是程序員可直接控制過程的執(zhí)行,正文清晰。但當同步化依賴過程參數(shù)或監(jiān)控器的狀態(tài)時，表達能力差。,14.2 基于消息傳遞的高層并發(fā)機制,14

16、.2.1 異步消息傳遞 chan (:，,：) 其中:為傳到信道上的數(shù)據(jù)域名(可缺省)和類型。例如: chan input (char); chan disk_access(cylinder，block，count ：int, buffer：char*); char output 1...N(1...M：char);,異步通信的過濾器 chan input (char)，output (1..MAXLINE:char); char_to_Line:: var line 1..MAXLINE:char，i:int :=1; loop receive input (li

17、ne i); while line i =CR and i

18、et of int; var pending :queue of int; var index:int，kind :op_kind，unitid :int; //units可用資源以整數(shù)代號初始化，reply初始化為零 loop receive request(index，kind，unitid); case kind = ACQUIRE = if avail 0 then //正常分配 avail := avail-1; unitid := remove (units); send reply index (unitid)； endif;

19、if avail = 0 then //記住index號客戶未分 insert (pending，index) //插入阻塞隊pending endif; 接下一張,case kind = RELEASE = if empty (pending) then avail := avail+1; insert (units，unitid); endif; if not empty(pending) then //分配unitid號資源 index := remove (pending); send reply index (uniti

20、d); endif; end case; end loop; client i:1..N: var unitid :int; send request (i，ACQUIRE，0); receive reply i (unitid); //使用unitid號資源然后釋放它，發(fā)以下消息: send release (i，RELEASE，unitid); 客戶/服務器進程的特點是send，receive是對等的，服務器要應答消息。本算法有N個客戶一個服務器。用其它主控程序創(chuàng)建clienti，當它發(fā)送request后，接著執(zhí)行replyi，如發(fā)現(xiàn)未分配(未應答)則在本處等待，直至

21、確已分配unitid/=0再使用它。,14.2.2 同步消息傳遞 通信著的順序進程CSP (1) 通信語句,A::...B!e... //B!e 是輸出語句，目標是B B::...A?x... //A?x 是輸入語句，源自A進程 ! 信道名 () ? 信道名 (),我們把求最大公約數(shù)做成一服務器進程GCD?？蛻暨M程client每向它發(fā)送一對整數(shù)，它求出結(jié)果發(fā)回客戶。 GCD ::var x，y:int; loop client ? args( x，y) while x/=y do if xy then x:= x-y endif if yx then y:=y-

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

23、y：int; while (i:1..N) client i? args(x，y) do while x /= y do if xy then x:= x-y endif if x

24、:int; sieve j-1? p；print (p) ； //只打印“第一個”收到的 loop sievej-1 ? next; if next mod p /=0 then sieve i+1 ! next endif; end loop;,客戶/服務器的同步通信實現(xiàn) 文件服務器的同步實現(xiàn)算法 File_Server i:1..N:: var fname:string，args:TYPE; var more :bool; var 局部緩沖區(qū)，快速緩存，磁盤地址等; while (c:1..M) client c? open (fname) do //

25、如名為fname的文件已打開: client ! open_reply( ); more := true; while more = true do if client c? read(args) then 調(diào)處理讀入數(shù)據(jù)的過程; client c! read_reply(results); if client c? write(args) then 調(diào)處理寫的過程; client c ! write_reply(results); if client c? close() then 調(diào)關(guān)閉文件操作; more := false

26、 endif; end; end.,client j:1..M :: var serverid ：int; while (i:1..N) File_Serveri! open(“foo”) do serverid := i; File_serveri ? open_reply(serverid); end. //以下寫使用該進程的代碼。例如，讀可寫: File_Serverserverid ! read(訪問參數(shù)); File_Serverserverid ? read_reply(results); ... //最后要有關(guān)閉文件的消息,14.2.2.4 同

27、步通信的底層實現(xiàn),,,,,應用程序,分布式并發(fā)核示意圖,應用程序,原語 例程,,描述子 緩沖區(qū),,網(wǎng)絡接口,,本地核,描述子 緩沖區(qū),,原語 例程,網(wǎng)絡接口,,,本地核,同步通信在最基本的操作上和異步是一樣的。當前實現(xiàn)同步有兩種策略: (1) 集中式的同步實現(xiàn),,,,,,,,,CH,Pi,Pj,,,,,,集中管理，它易于檢查進程匹配情況。然而，在分布式系統(tǒng)中，這樣多次來回通信增加了系統(tǒng)通信開銷，往往成為并行核的瓶頸。,分散式同步實現(xiàn),用異步通信原語實現(xiàn)分散式同步通信，為每個要求通信的進程設立一個匹配信道(輸出語句為一端，輸入語句為另一端)和一個應答信道。并于有輸入語句的進程設阻塞等候隊列.如果

28、輸出/入語句不出現(xiàn)在警衛(wèi)子句內(nèi)處理程序要簡單得多，輸出語句出現(xiàn)在警衛(wèi)子句中情況會變得更復雜。因此CSP和Occam的最初版本均不允許在警衛(wèi)子句中有輸出語句,14.3 遠程過程調(diào)用和會合,調(diào)用進調(diào),服服務進程 從創(chuàng)建到完成,,call RPC,,,,,調(diào)用進程,,調(diào)用進調(diào),進入同步點 in,等待,數(shù)據(jù)通信 完成,call,,,,,,,會合,(等待）,RPC,會合,14.3.1 遠程過程調(diào)用RPC,call Mname.opname(AP_list);,每個模塊在各自的地址空間。每當有遠程調(diào)用時，服務模塊創(chuàng)建一服務進程，調(diào)用進程一直延遲到整個服務完成。如果同一時間只允許一個遠程調(diào)用進入本模塊，就實

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

30、一個進程有若干個操作)，調(diào)用的是進程輸出的操作，因而，操作不能是并行的，只能同時有一個操作在執(zhí)行。而每個操作都有自己的等候隊列。正是由于定義輸出操作，帶來了衛(wèi)式通信的方便性。會合的一般形式是:,in Op1 and B1 by e1s1 .... Opn and Bn by ensn end in,call Op1 and B1 by e1 .... Opn and Bn by en end call,,會合實現(xiàn)過濾器,Baffer :: op deposit(data:TYPE)，fetch(var result:TYPE); var buf1..q:TYPE var front

31、 :=1，rear := 1，count !=0; loop in deposit (data) and count 0 do result := buffront; front := front mod n+1; count := count -1 end; end loop.,有界緩沖區(qū)buf1..q是本地機上的共享變量。front，rear，count為控制和警衛(wèi)變量,14.3.3 Ada的任務,Ada的任務結(jié)構(gòu),task TNAME is entry ENAME (FP_list)； //可以多個 end TNAME； task body TNAME is

32、局部聲明； begin accept ENAME (FP_list) is //對應多個 語句序列; end ENAME; end TNAME; 任務激活后就是一個進程。其它進程通過 call TNAME.ENAME (AP_list);,Ada的通信與同步,（1）簡單選擇 (2) 否則選擇 (3) 衛(wèi)式選擇 （4） 延時選擇,14.4 多原語的并發(fā)機制,進程交互主要技術(shù)的回顧,,忙等待,,信號燈,條件臨界區(qū),監(jiān)控器,同步消息傳遞,異步消息傳遞,遠程過程調(diào)用/會合,路徑表達式,多原語交互,面向 過程,面向 消息,面向操作,,,多原語并發(fā)程序表示法 module Mname 可見Op(操作)

33、聲明; //輸出操作 body 局部變量聲明; 初始化代碼; 過程聲明(包括輸出的和局部的); //proc或in 進程聲明(Mname 內(nèi)的進程); end. 同步和異步調(diào)用Op: call Mname.Op(ARG_List) //同步用call send Mname.Op(ARG_List) //異步用send,調(diào)用者 被調(diào)用者 效果 call proc (遠程)過程調(diào)用 call in 會合 send proc 動態(tài)過程創(chuàng)建 send in 簡單異步消息傳遞,14.4.3 SR語言 14.5 并發(fā)程序設計語言,高級程序設

34、計語言擴充并發(fā)機制，最早可溯源至PL/1和Algal-68。20多年以來，隨著各種并發(fā)機制的研究推出了數(shù)十種具有并發(fā)機制的高級程序設計語言。直到目前，還沒有一種并發(fā)程序設計語言能統(tǒng)治并發(fā)程序設計整個領域。其原因是硬件背景、應用領域和程序設計模型的多樣性。,主要的并發(fā)程序設計語言 語言 年代 并發(fā)機制 備注 DP 1978 CCR+RPC Edison 1978 CCR Argus 1982 CCR+RPC+原子事務 Lynx 1991 RPC+會合+CCR Concurrent Euclid 監(jiān)控器(SW) Concurrent Pascal

35、1975 監(jiān)控器(SW) Modula-3 1985 監(jiān)控器(SC)+協(xié)例程和鎖的包 Path Pascal 1979 監(jiān)控器+路徑表達式 Pascal Plus 1979 監(jiān)控器(SU) Turing Plus 1983 監(jiān)控器(SC+SW) Mesa 1979 監(jiān)控器(SC)+RPC Emerald 監(jiān)控器+RPC(面向?qū)ο?,,,語言 年代 并發(fā)機制 備注 Actor 異步消息傳遞(基于對象) PLITS 1979 異步消息傳遞 NIL 1982 異步消息傳遞+會合 Gypsy 1979 異步消息傳遞 CONIC 異步消息傳遞 CSP 1980 同步消息傳遞 Joyce 同步消息傳遞 Occam 1987 同步消息傳遞 Concurrent C 1985 會合+異步發(fā)送 Concurrent C++ 1987 會合 Ada 1983 會合 SR 1982 多共享+消息原語 92年SR2.0 Star Mod 1980 多消息原語 Linda 1986 帶共享元組空間的消息原語 Java 1996 類庫支持多原語,,