【文章內(nèi)容簡介】 tion Critical Region簡稱 CCR)將共享變量顯式地置于叫做資源的區(qū)域內(nèi) 每個(gè)進(jìn)程在自己的進(jìn)程體內(nèi)指明要訪問的條件臨界區(qū)，而同一臨界區(qū)可出現(xiàn)在不同進(jìn)程之中 (誰進(jìn)誰用 ) 首先在資源中聲明共享變量 : resource r(共享變量聲明 )，例： resource sema( s:int :=n ) 使用共享變量： region r when B do S end region sema when s0 do s:= s1 end // P操作 region sema do s:= s+1 end // V操作 例 : 用 CCR實(shí)現(xiàn)的生產(chǎn)者與消費(fèi)者 pragram PRODUCER_CONSUMER_CCR var buf:TYPE。 var empty:sema,full:sema。 resource sema:(empty := 1,full := 0)。 process PRODUCER [i:1..M]:: loop PRODUCER[i] 產(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 end。 m=buf； region sema do empty := empty + 1 end。 CONSUMER[j] 消費(fèi)者取出的這條消息 m。 end loop。 end。 end PRODUCER_CONSUMER_CCR. 條件臨界區(qū)評(píng)價(jià) 條件臨界區(qū)最主要的優(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)控器 Dijkstra建議是把分散在整個(gè)程序中的 region語句進(jìn)一步集中成為一個(gè)模塊叫做監(jiān)控器 (monitor)。 program monitor monitor Mname:: 共享數(shù)據(jù)聲明并初始化 。 proc op1 (形參表 1) is op1 體 end。 ... proc opn (形參表 n) is opn體 end。 end。 process Pname [i:1..N]:: 局部數(shù)據(jù)聲明并初始化 begin : call (實(shí)參表 )。 : end begin 初始化，激活進(jìn)程 end monitor. 例 : 有界緩沖區(qū)的監(jiān)控器實(shí)現(xiàn)算法 monitor BOUNDED_BUFFER:: var buf[1..q]： TYPE。 var frout :=1， rear :=1， count := 0。 var not_full:cond； //當(dāng) count q示信為真 var not_empty:cond。 //當(dāng) count0 示信為真 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 wait (not_empty) end。 result := buf [front]。 front := (front mod q) +1。 count := count 1。 signal (not_full)。 end。 end BOUNDED_BUFFER. 以監(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)程。 (見下例 **) (5) 會(huì)合同步 進(jìn)程交互是客戶 /服務(wù)器 (C/S)關(guān)系時(shí) ,為此兩交互進(jìn)程必須會(huì)合 (rendezvou)才能得到服務(wù)。如不能到達(dá)會(huì)合的同步點(diǎn)則要相互等待。 （ 見下例 ***） 例 * 以監(jiān)控器作信號(hào)燈 monitor SEMAPHORE:: var s:= 0。 var pos:cond。 //當(dāng) s0， pos示信為真 proc P( ) is while s=0 do wait (pos) end。 s:= s1。 end。 proc V( ) is s := s+1； signal (pos)。 end。 end SEMAPHORE. 例 **： 以監(jiān)控器實(shí)現(xiàn)的 FIFO信號(hào)燈 monitor SEMAPHORE:: var s=0。 var pos :cond； //當(dāng) V中 pos隊(duì)列非空示真 proc P( ) is if s0 then s:= s1 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. 注 :本例中 “ ?” 號(hào)表示和前一個(gè)語句并行執(zhí)行的語句 ,以下同 . 例 *** 貪睡的理發(fā)師的模擬解 monitor BARBER_SHOP:: var barber := 0,chair :=0,open =0。 var barber_available :cond //當(dāng) barber0 示真 var chair_occupied :cond //當(dāng) chair0示真 var door_open:cond //當(dāng) open=0示真 proc get_haircut( ) is //顧客調(diào)用 while barber=0 do wait (barber_available) end。 barber := barber1。 chair := chair+1； signal (chair_occupied)。 while open=0 do wait (door_open) end。 open := open1； 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 := chair1。 end。 proc finished_cut ( ) is //理發(fā)師調(diào)用 open := open+1； signal (door_open)。 while open0 do wait (customer_left) end。 end。 各種語言實(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ī)制 ? 自動(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)控器的。 modula3即采用此種機(jī)制。 ? 信號(hào)和出口 SX:既然被占了先 ,發(fā)信號(hào)的進(jìn)程也就不等了 .立即從監(jiān)控器出口或從過程返回。并發(fā) Pascal即采用此種機(jī)制。 ? 信號(hào)和等待 SW:發(fā)信號(hào)的進(jìn)程被人占先之后處于監(jiān)控器內(nèi)等待，直到它能再次獲得互斥訪問，恢復(fù)執(zhí)行。 Modula和并發(fā) Euclid采用這種機(jī)制。 ? 信號(hào)和急等 SU:發(fā)信號(hào)進(jìn)程被人占先之后也要等待，但保證在監(jiān)控器有新的進(jìn)程進(jìn)入之前先使它得到恢復(fù)。 Pascal_plus即采用這樣的機(jī)制。 各種語言實(shí)現(xiàn)監(jiān)控器時(shí)的原語語義差異 以上五種信號(hào)機(jī)制語義略有不同，但可從理論上證明它們是等價(jià)的。即以一種機(jī)制可模擬另一 種機(jī)制。實(shí)現(xiàn)費(fèi)用不同，對(duì)某些類型問題表達(dá)的方便性不同。也正是不同語言各自鐘愛它們的原因。 (2) 嵌套監(jiān)控器中的互斥 在磁盤調(diào)度器之類的應(yīng)用中，一個(gè)進(jìn)程首先要爭(zhēng)取進(jìn)入磁盤去尋址，找到地址后讀 /寫，這樣就要設(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á)式 1974年 Campbell和 Habermann提出以路徑表達(dá)式直接控制進(jìn)程順序的建議 監(jiān)控器中派生出來的一個(gè)重要分枝。 路徑表達(dá)式是就每一資源在其開始聲明時(shí) ,就在其上定義操作的約束。 path deposit,fetch end //deposit和 fetch并發(fā)執(zhí)行 path deposit。fetch end //deposit必須先于 fetch執(zhí)行 path1:（ deposit； fetch) end //只能有一條路徑 (但可多次執(zhí)行此路徑 ),兩操作交替互斥執(zhí)行 . path N:(1:(deposit)； 1:(fetch)) end //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á)能力差 。 消息是信息傳遞的單元 ,按 shannon的模型 ,信息源借助信道 (channel)向信息目標(biāo)發(fā)送消息 .信道成了并發(fā)進(jìn)程共享的資源 .信道是通信網(wǎng)的抽象 , 泛指進(jìn)程間通信的路徑 .信道由兩個(gè)原語訪問 : send, 程向信道發(fā)送一消息 ,通信就開始了 .需要該消息的進(jìn)程 , 從信道上接受 (獲取 )這條消息 .數(shù)據(jù)流也隨發(fā)送者傳遞到接受者 . 基于消息傳遞的通訊機(jī)制 基于消息傳遞的通訊機(jī)制 由于信道本身不能存儲(chǔ) , 變量只能存放在各個(gè)進(jìn)程中 , 因而不能共享地訪問 ,所以也用不著互斥機(jī)制 .由于只有所在進(jìn)程能考察變量情況 , 條件同步編程與基于共享變量的大不相同 .程序也不一定非要在一個(gè)處理器上執(zhí)行 ,可以分布在多個(gè)處理器上 , 分布式程序因而得名 .反過來 , 分布式程序卻可在單主機(jī)或多路處理器的 (分時(shí) )系統(tǒng)上執(zhí)行 .此時(shí)把信道改成共享存儲(chǔ)就可以了 . 兩類通信模式 基于消息傳遞的進(jìn)程 , 通信雖然不靠共享存儲(chǔ)間接實(shí)現(xiàn)， 然而通信時(shí)也有同步異步之分 ? 同步消息傳