1、4.3.6 會(huì)合(Rendezvous),背景 80年代, Ada, Initiated by DOD; Ada 95, (Object-oriented) 會(huì)合：兩個(gè)并發(fā)執(zhí)行流匯集到一處 并發(fā)執(zhí)行流 調(diào)用 接受 均發(fā)生，握手，同步。,P1:,會(huì)合引入背景分布系統(tǒng),共享變量 （被動(dòng)） Semaphore s;,P(S) CR2 V(S),P2:,共享變量與訪問進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。,PV操作問題:,P(S) CR1 V(S),P1:,會(huì)合引入背景分布系統(tǒng),共享變量 （被動(dòng)） Semaphore s;,P(S) CR2 V(S),P2:,共享變量與訪問進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境

2、。,PV操作問題:,P(S) CR1 V(S),站點(diǎn)1,站點(diǎn)2,會(huì)合引入背景分布系統(tǒng),管程（被動(dòng)）,管程與調(diào)用進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。,管程問題:,會(huì)合引入背景分布系統(tǒng),管程（被動(dòng)）,管程與調(diào)用進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。,管程問題:,站點(diǎn)1,站點(diǎn)2,會(huì)合圖示,被調(diào)用者代調(diào)用者執(zhí)行調(diào)用代碼,會(huì)合圖示,被調(diào)用任務(wù),入口1：accept,入口2：accept,select,.,.,.,PCB,PCB,.,.,.,調(diào)用語句,調(diào)用語句,調(diào)用任務(wù),入口FIFO隊(duì)列,Ada同步語句,1. 調(diào)用語句 . 2. 接受語句 accept doend,Accept語句,有調(diào)用者,等待,選取第一個(gè),

3、會(huì)合開始 調(diào)用者等待,有in參數(shù),取in參數(shù),有語句序列,執(zhí)行之,有out參數(shù),送out參數(shù),會(huì)合結(jié)束 調(diào)用者繼續(xù),會(huì)合期,例子-單一資源管理,task single_resource is entry acquire; entry return; end single_resource;,task body single_resource is begin loop accept acquire; accept return; end loop end single_resource;,single_resource.acquire; 使用 single_resource.return;,A

4、da同步語句（cont.）,3. 選擇語句 select when = or when = else end select,Select語句語義,計(jì)算所有布爾表達(dá)式，為真者對(duì)應(yīng)入口標(biāo)記開放； If 無開放的 Then If 有ELSE部分 Then 執(zhí)行之 Else 異常; break; If 無被調(diào)用的開放的 Then If 有ELSE部分 Then 執(zhí)行之; break; Else 等待; 任取一開放的被調(diào)用的接受語句 會(huì)合開始，調(diào)用者等待； If 有in參數(shù) Then 取in參數(shù)； If 有 Then 執(zhí)行之； 會(huì)合期 If 有out參數(shù) Then 送out參數(shù)； 會(huì)合結(jié)束，調(diào)用者繼續(xù)；

5、 If select語句有語句序列 Then 執(zhí)行之。,4.3.6.1 會(huì)合的描述(Cont.),select 語句流程,有開放的,有else部分,F,有被調(diào)用的開放的,T,有else部分,F,會(huì)合開始，調(diào)用者等待,有 in 參數(shù),有語句序列,F,有 out 參數(shù),F,F,會(huì)合結(jié)束，調(diào)用者繼續(xù),任取一開放且被調(diào)用的,T,4.3.6.2 會(huì)合例子-客棧問題,.,explorers,bakery,hunter,活動(dòng)： (1)接受獵物 (2)接受面包 (3)做三明治 (4)給探險(xiǎn)家,限制： 一份獵物 一份面包 一份三明治 一位客人,master,客棧,客棧問題,explorer： loop 探 險(xiǎn)

6、進(jìn)客棧 取三明治 出客棧 吃三明治 end loop,hunter： loop 狩 獵 進(jìn)客棧 送獵物 出客棧 end loop,bakery： loop 做面包 進(jìn)客棧 送面包 出客棧 end loop,入口,入口,入口,客棧問題,procedure Adalodge is task type explorer; task hunter; task bakery; task master is entry deliverbread; /面包師送面包 entry delivermeat; /狩獵者送獵物 entry lodge; /探險(xiǎn)家取三明治 end master;,客棧問題,task b

7、ody explorer is victuals:food; begin loop explore; master.lodge(victuals); /入客棧取三明治 eat(victuals) end loop end explorer;,客棧問題,task body hunter is walrus:food; begin loop hunt(walrus); master.delivermeat(walrus) end loop end hunter;,task body bakery is rolls:food; begin loop bake(rolls); master.deliv

8、erbread(rolls) end loop end bakery;,客棧問題,客棧問題,task body master is bread, meat, sandwich: food; procedure makesandwich is begin cook(meat); sandwich:=bread+meat; bread:=0; meat:=0; end makesandwich;,客棧問題,begin bread:=0; meat:=0; sandwich:=0; loop select when bread=0 = accept deliverbread(br: in food)

9、 do bread:=br; end deliverbread; or when meat=0 = accept delivermeat(mt: in food) do meat:=mt; end delivermeat;,客棧問題,or when (sandwich0)or(bread0 and meat0)= accept lodge(snack: out food) do /入店取三明治 if sandwich=0 then makesandwich end if; snack:=sandwich; end lodge; sandwich:=0 /會(huì)合期之外 else if (bread

10、0)and(meat0)and(sandwich=0) then makesandwich end if /棧主人活動(dòng) end select end loop end master,客棧問題,explorers: array(1.numberofexploers)of explorer; begin null; end Adalodge;,Bounded buffer problem,task boundedbuffer is entry putin; entry getout; end boundedbuffer; task body boundedbuffer is b: array(0.

11、k-1)of integer; ip, op: 0.k-1; count: integer; begin ip:=0; op:=0; count:=0;,Bounded buffer problem,loop select when (count accept putin(item:in integer) do b(ip):=item end putin; ip:=(ip+1)mod k; count:=count+1;,Bounded buffer problem,or when (count0) = accept getout(item:out integer) do item:=b(op

12、); end getout; op:=(op+1)mod k; count:=count-1; end select end loop end boundedbuffer;,作業(yè) #4,1. 用Ada語言中的會(huì)合解決讀者/寫者問題，要求寫者優(yōu)先。即編寫一個(gè)任務(wù)，其中有如下四個(gè)入口： start_read; finish_read, start_write, finish_write. 提示：可以使用嵌套的accept語句。,讀者-寫者問題,Task readers_writers is entry start_read; entry finish_read; entry start_write

13、; entry finish_write; End readers_writes; Task body readers_writers is; Var read_count, write_count: integer; begin read_count:=0; write_count:=0;,讀者-寫者問題,Loop select when write_count=0 = accept start_read do read_count := read_count+1; end start_read or when read_count0 = accept finish_read do read

14、_count := read_count-1; end finish_read; or,讀者-寫者問題,when write_count=0 = accept start_write do while read_count 0 do accept finish_read do read_count:= read_count -1; end finish_read end while end start_write; write_count:=write_count+1; or when write_count0 = accept finish_write do write_count:=wri

15、te_count-1; end finish_write; end select End loop; End readers_writers,讀者-寫者問題,讀者活動(dòng): Readers_writes.start_read; 讀操作 Readers_writers.finish_read; 寫者活動(dòng): Readers_writers.start_write; 寫操作 Readers_writers.finish_write;,4.4 進(jìn)程高級(jí)通訊,進(jìn)程通訊：進(jìn)程之間的相互作用。 低級(jí)通訊（簡單信號(hào)） 進(jìn)程互斥 進(jìn)程同步 高級(jí)通訊（大宗信息） 高級(jí)通訊 memory sharing vs. mes

16、sage passing direct vs. indirect symmetric vs. non-symmetric buffering vs. non-buffering,4.4.1 進(jìn)程通訊概念,4.4.2 進(jìn)程通訊模式,1. 共享內(nèi)存模式(shared memory)：,2. 消息傳遞模式(message passing)：,OS提供： （1）公共內(nèi)存 （2）互斥同步機(jī)制,P1,P2,M,send,receive,直接：進(jìn)程-進(jìn)程 間接：進(jìn)程-信箱-進(jìn)程,P1,P2,公共內(nèi)存,4.4.3 直接方式,對(duì)稱形式(sender and receiver name each other) s

17、end(R,message) receive(S,message),S:,R:,4.4.3 直接方式, receive(pid,N) ., send(R,M1) ., send(R,M2) .,非對(duì)稱形式(only sender names receiver) send(R,message) receive(pid,message),C/S model,R:,S1:,S2:,4.4.3.1 有緩沖途徑(消息傳遞模式,直接方式,非對(duì)稱形式),PCB, send(R,M) size text ,PCB, receive(pid,N) ,M:,N:,msg,msg,msg,.,發(fā)送者S:,接收者R:

18、,Message passing, direct,non-symmetric, buffering,Size text sender link,載有消息的緩沖：,進(jìn)程消息隊(duì)列管理： Var Sm:semaphore; (0) 收取消息前：P（Sm）; 消息入隊(duì)后：V（Sm); 消息隊(duì)列互斥： Var m_mutex:semaphore;(1) P(m_mutex); 入列(出列)動(dòng)作; V(m_mutex);,Buffer pool management,Var Sb, b_mutex:semaphore; (k,1),申請(qǐng)：P(Sb); P(b_mutex); 頭緩沖出鏈; V(b_mute

19、x);,釋放：P(b_mutex); 緩沖入鏈頭; V(b_mutex); V(Sb);,Head：,緩沖池,發(fā)送-接收原語,Send(R,M) 根據(jù)R找接收者； P(Sb); P(b_mutex); 取一空buf; V(b_mutex); size,text,sender = buf P(m_mutex); 消息入鏈尾； V(m_mutex); V(Sm);,Receive(pid,N) P(Sm); P(m_mutex); 頭消息出鏈; V(m_mutex); size,text= N sender = pid P(b_mutex); 空buf入鏈； V(b_mutex); V(Sb);,

20、Remarks：,Send/receive 為高級(jí)通訊原語，可用低級(jí)原語實(shí)現(xiàn)； Send/receive不是真正意義的原語，可以被中斷。,4.4.3.2 無緩沖途徑(消息傳遞模式,直接方式,非對(duì)稱形式),發(fā)送-接收都發(fā)生,信息由發(fā)送者復(fù)制到接收者. PCB中兩個(gè)信號(hào)燈, S_m, S_w, 初值0. 發(fā)送過程:send(R,M) 根據(jù)R找到消息接收者 發(fā)送消息進(jìn)程增1, 如接收進(jìn)程等待將其喚醒, 即執(zhí)行V(S_m) 等待消息傳送完畢, 即執(zhí)行P(S_w),4.4.3.2 無緩沖途徑,接收過程:receive(pid,N) 等待消息到達(dá), 即執(zhí)行P(S_m) 消息由發(fā)送進(jìn)程空間復(fù)制到接收進(jìn)程空間

21、; 喚醒發(fā)送消息進(jìn)程, 即執(zhí)行V(S_w),4.4.3.2 無緩沖途徑,Send(R,M),Receive(pid, N),M:,N:,reg,send,receive, S_m S_w ,PCB,硬件,OS,4.4.3.2 無緩沖途徑,優(yōu)點(diǎn): 節(jié)省空間(不需要buffer) 缺點(diǎn): 并發(fā)性差: 發(fā)送進(jìn)程需要等待接收進(jìn)程執(zhí)行receive把信息復(fù)制到接收進(jìn)程空間后才能繼續(xù).,4.4.4 間接方式,Mailbox,Send_mb(mb,m),Receive_mb(mb,n),multi-sender - multi-receiver; multi-sender - one receiver,4.

22、4.4.1 信箱屬于操作系統(tǒng)空間,Type mailbox=record in,out:0.k; s1,s2:semaphore; (k,0) mutex:semaphore; (1) letter:array0.k-1of message; end; Var mb:mailbox; create_mb(mb); 系統(tǒng)調(diào)用 delete_mb(mb); 系統(tǒng)調(diào)用,信箱通訊,Procedure send_mb(var mb:mailbox; m:massage); begin with mb do begin P(s1); /申請(qǐng)空位 P(mutex); letterin:=m; in:=(in

23、+1)mod k; V(mutex); V(s2) /消息增加一個(gè) end; end;,信箱通訊,Procedure receive_mb(var mb:mailbox; var n:massage); begin with mb do begin P(s2); /申請(qǐng)消息 P(mutex); n:=letterout; out:=(out+1)mod k; V(mutex); V(s1) /空位增加一個(gè) end; end;,屬于操作系統(tǒng)空間的信箱,Var mb: mailbox,create_MB,delete_MB,send_MB,receive_MB, create_MB(mb) receive_MB(mb,N) delete_MB(mb) N:, send_MB(mb,M) M:,UNIX進(jìn)程高級(jí)通訊機(jī)制,UNIX進(jìn)程高級(jí)通訊機(jī)制,速度： pipe作為文件，需要兩次IO，但一般不會(huì)真正執(zhí)行IO操作: 緩沖與延遲寫(delayed write), 寫到內(nèi)存緩沖區(qū), 只要內(nèi)存資源不緊張, 緩沖區(qū)不另作它用, 不會(huì)寫到外存, 讀時(shí)可在內(nèi)存緩沖區(qū)中得到. Pipe文件大