第13章程序的并發(fā)性和進程交互原語

1、第 七 章 并發(fā)程序設(shè)計語言,多CPU/GPU網(wǎng)絡(luò),,Concurrent,,Declarative,Imperative,Concurrent,Deterministic,更關(guān)注如何描述問題本身，并且考慮問題如何分解成多個獨立執(zhí)行的小任務(wù)；,更關(guān)注描述馮諾依曼機如何執(zhí)行,馮諾依曼單機,網(wǎng)絡(luò)環(huán)境,,,小規(guī)模軟件,大規(guī)模軟件,不同的軟件開發(fā)方法,,主要內(nèi)容：,并發(fā)程序設(shè)計的基本概念并發(fā)程序帶來的問題需要解決的基本問題程序語言示例,

2、并行與并發(fā),并發(fā)（concurrency）和并行（parallelism）的概念并發(fā)性(concurrency)，又稱共行性，是指能處理多個同時性活動的能力，并發(fā)事件之間不一定要同一時刻發(fā)生。并行(parallelism)是指同時發(fā)生的兩個并發(fā)事件，具有并發(fā)的含義，而并發(fā)則不一定并行。另一種理解：并行強調(diào)的是多個執(zhí)行活動同時處于運行狀態(tài)之中，強調(diào)其相互獨立性。這里關(guān)心并行算法、并行系統(tǒng)、并行體系結(jié)構(gòu)等等并發(fā)強調(diào)的是多個執(zhí)行活

3、動之間的關(guān)系和相互作用，這里關(guān)心的是互斥、同步、通訊、資源的共享和競爭等等第三種解讀： 并發(fā)和并行的區(qū)別就是一個處理器同時處理多個任務(wù)和多個處理器或者是多核的處理器同時處理多個不同的任務(wù)。前者是邏輯上的同時發(fā)生（simultaneous），而后者是物理上的同時發(fā)生．,基本概念,并行程序設(shè)計模型并行計算的硬件環(huán)境程序與進程，線程與進程原子動作進程交互,基本概念,并行程序的基本計算單位是進程,它與有關(guān)代碼段執(zhí)行的操作

4、相對應(yīng)。進程的粒度在不同的程序設(shè)計模型和應(yīng)用程序中是不一樣的。,,,基本概念,并行程序設(shè)計的模型：1.共享變量模型 2.消息傳遞模型 3.數(shù)據(jù)并行模型 4.面向?qū)ο竽Ｐ?是目前最靈活，最常用的模型,新的并行模型,基本概念,1.共享變量模型共享變量模型用限定作用范圍和訪問權(quán)限的辦法,對進程尋址空間實行共享或限制,即利用共享變量實現(xiàn)并行進程間的通信。為了保證能有序地進行IPC(Inter-Process Communication

5、 ),可利用互斥特性保證數(shù)據(jù)一致性與同步。,基本概念,共享變量模型與傳統(tǒng)的順序程序設(shè)計有許多相似之處。程序員只需關(guān)心程序中的可并行進程,而無需關(guān)心進程間的數(shù)據(jù)交換問題。共享變量的數(shù)據(jù)一致性、臨界區(qū)的保護性訪問由編譯器與并行系統(tǒng)來維護。共享變量模型具有編程簡單、易于控制的特點,但若在多處理機、機群系統(tǒng)上實現(xiàn)時則會導致系統(tǒng)開銷增大,因此共享變量模型常常用于共享存儲多處理機,而不用于多處理機、機群系統(tǒng)。,基本概念,2.消息傳遞模型消息傳遞

6、模型是指程序中不同進程之間通過顯式方法(如函數(shù)調(diào)用、運算符等)傳遞消息來相互通信,實現(xiàn)進程之間的數(shù)據(jù)交換、同步控制等。消息包括指令、數(shù)據(jù)、同步信號等。,基本概念,程序員不僅要關(guān)心程序中可并行成分的劃分,而且還需關(guān)心進程間的數(shù)據(jù)交換。消息的發(fā)送、接收處理將增加并行程序開發(fā)的復(fù)雜度。但是它適用于多種并行系統(tǒng),如多處理機、可擴展機群系統(tǒng)等,且具有靈活、高效的特點。,基本概念,3.數(shù)據(jù)并行模型數(shù)據(jù)并行模型是指將數(shù)據(jù)分布于不同的處理單元,這些處

7、理單元對分布數(shù)據(jù)執(zhí)行相同的操作。數(shù)據(jù)并行程序使用預(yù)先分布好的數(shù)據(jù)集。運算操作之間進行數(shù)據(jù)交換操作。,基本概念,數(shù)據(jù)并行操作的同步是在編譯而不是在運行時完成的。數(shù)據(jù)并行模型中的SIMD模型可用于向量機、多處理機等并行計算機,而SPMD模型則可用于多處理機、機群系統(tǒng)。,基本概念,4.面向?qū)ο竽Ｐ兔嫦驅(qū)ο竽Ｐ褪墙鼛啄觌S著面向?qū)ο蠹夹g(shù)的發(fā)展而提出的。它基于消息傳遞,但并行處理單位卻是對象。在這種模型中,對象是動態(tài)建立和控制的。處理是通過對象間

8、發(fā)送和接收消息來完成。面向?qū)ο竽Ｐ途哂泻啙嶌`活的特點,適合多種平臺,但系統(tǒng)開銷較大。,基本概念,并行程序設(shè)計語言就是在這些并行程序設(shè)計模型的基礎(chǔ)上,提出對并行性的描述方法、并行單元間協(xié)同的描述方法,以及該語言適用的并行計算環(huán)境。,基本概念,無論是哪種模型，那個語言，都需要解決兩個問題：進程管理和通訊。事實上，模型之間的區(qū)別主要體現(xiàn)在對通訊實現(xiàn)方式的不一樣上。,,硬件環(huán)境單機/多機：并行/并發(fā)根據(jù)Flynn的分類法: SISD：一

9、組可執(zhí)行代碼裝入一個機器內(nèi)存后, 以一個CPU, 一組數(shù)據(jù)執(zhí)行一次。它屬于SISD執(zhí)行模式(即單指令流單數(shù)據(jù)流的簡寫)。物理上對應(yīng)為單處理器的順序程序。 SIMD：一組可執(zhí)行代碼裝入后, 可以依次執(zhí)行多個進程, 它屬于SIMD, 單指令流多數(shù)據(jù)流。對應(yīng)為單機多處理器的主機或單CPU的分時系統(tǒng)、陣列機組。 MISD：在多機或多處理器上各有自己的可執(zhí)行代碼。協(xié)同完成一組數(shù)據(jù)的計算, 是MISD多指令流單數(shù)據(jù)流系統(tǒng)。對應(yīng)為分布數(shù)據(jù)流機。

10、 MIMD：MIMD則為多指令流多數(shù)據(jù)流系統(tǒng), 對應(yīng)為一般分布式系統(tǒng)(有多個不同的處理機,運行各不相同的進程)。局域網(wǎng)和廣域網(wǎng)就屬于此列。如果網(wǎng)上協(xié)同運行一個程序作業(yè), 則為以MIMD系統(tǒng)實現(xiàn)的并發(fā)程序。,基本概念,并行處理器譜系,,,,,,,,,,并行處理器,SIMD,MIMD,共享存儲（緊耦合）,分布式存儲（松耦合）,共享存儲多用于同類多CPU的單機上，所有CPU處理的進程都共享公共的數(shù)據(jù).分布式存儲是松耦合的計算機群體,它對應(yīng)為

11、多計算機的簇（cluster）,和一組計算機的集合不同之處在于：它們各自的存儲是被大家共享的,它們互連,每個計算機只是”整個”計算機中的一個節(jié)點,是今后高性能、可伸縮、高可靠性計算機的發(fā)展方向.,基本概念,并行程序設(shè)計語言都要解決：并行進程的描述與管理進程間數(shù)據(jù)分布、傳遞的描述與管理以及進程間同步協(xié)同的描述與管理問題。,基本概念,一個程序的一次執(zhí)行叫做一個進程(process),基本概念,,進程執(zhí)行控制流,外部中斷,,,,,內(nèi)部中

12、斷,中斷處理器,原語例程,調(diào)度器,,,,,基本概念,線程是共享資源的輕量級進程（lightweight process）,它也有線程執(zhí)行狀態(tài)，也有其靜態(tài)存儲和局部變量。,基本概念,傳統(tǒng)的OS支持單線程的計算模式。單用戶的MS-DOS和多用戶的UNIX就是例子，即使UNIX是多線程交互，每一進程之中只有一線程。,,,,,,,,,,,,,,,,,,,,,,,,,,,MS-DOS,Java,UNIX,Windows NTSolarisMa

13、chOS/2,右側(cè)上圖，一個進程多個線程對應(yīng)為Java虛機的計算模式。而當今所有OS均發(fā)展為右下角的多進程和多線程的計算模式。,基本概念,原子動作是一次“立即”執(zhí)行完的“順序”動作。至于是否真正不再分就不一定了。原子動作一般定義在語句級的事件(event)上事件是本程序表示的狀態(tài)有了變化例： PL/1的多任務(wù) PL/1的并發(fā)進程是任務(wù)TASK, 它可以定義語句級的事件。P是一個進程, 它并行執(zhí)行Q進程, 則P進程的

14、正文可以寫: DECLARE X EVENT : CALL Q(APT) TASK (X) //激活Q,,,進程交互(1) 獨立進程 兩進程并行但不相關(guān) 設(shè)進程為事件序列, 若有C,K兩并行進程, 可表達為C‖K.其中: C={C1, C2…Cn} K={K1,K2,…Km} 獨立進程是兩進程內(nèi)任何事件Ci, Kj的執(zhí)行都不依賴對方(2

15、) 競爭進程 兩進程競爭同一資源 臨界段(Critical section)：據(jù)有并加工資源的代碼段 競爭進程一般形式是: C : loop K : loop 入口協(xié)議 入口協(xié)議 臨界段 臨界段 出口協(xié)議 出口協(xié)議

16、 非臨界段 非臨界段 end loop end loop 入口協(xié)議一般是按所設(shè)共享變量判斷能否進入,出口協(xié)議則改置 正確值.為確保進程的確定性,利用共享變量“通信”協(xié)調(diào),(3) 通信進程 兩進程有協(xié)議的信息交換設(shè)C,K定義如前, Ci必須先于Kj(Kj要用到Ci的結(jié)果)的執(zhí)行, 即其它事件先后無所謂, 一定要保證Ci, K

17、j的執(zhí)行順序. 同步(synchronous)通信 指兩進程進度各不相同, 但必須同步到達通信點.若一方未到,另一方等待,直至完成信息交換.交換后各自執(zhí)行各自進程則為單向同步通信.如果交換后,發(fā)送方一直等待接受方執(zhí)行的結(jié)果,拿回結(jié)果后再各自執(zhí)行自己的進程為雙向同步通信。 異步(asynchronous)通信 一般要借助相當大的郵箱.兩進程以各自速度執(zhí)行,發(fā)送方有了信息投入郵箱,并繼續(xù)執(zhí)行自己進程.接受方在認為合適時從郵箱獲取信息

18、.一般不競爭郵箱且為單向通信, 當然也可做成雙向的。 定向/廣播式通信 所謂定向是發(fā)送方指明接受方.而廣播式通信發(fā)送方只向公共信道發(fā)送信息,任何共享該信道的成員均可接受, 所以是異步通信、單向的.,,主要內(nèi)容,并發(fā)程序設(shè)計的基本概念并發(fā)程序帶來的問題需要解決的基本問題程序語言示例,帶來的問題,(1) 速度依賴(2) 輸入值依賴(3) 不確定性(4) 死鎖(5) 死等,帶來的問題,(1) 速度依賴 并發(fā)程序執(zhí)行結(jié)

19、果,取決于順序成分進程執(zhí)行的相對速度.對于并發(fā)且有實時(real time)要求的程序,執(zhí)行結(jié)果還取決于絕對速度. 并發(fā)程序調(diào)整相對速度的辦法是延遲快進程.把進程掛起來(進入懸置態(tài))待到指定條件滿足才喚醒該進程.其基本原語是: await do ,帶來的問題,(2) 輸入值依賴 同一并發(fā)程序兩組數(shù)據(jù)輸入可能會有很大差別,帶來的問題,(3) 不確定性 順序程序兩次同樣值的測試,一般情況下都是一致的.

20、即所說的再現(xiàn).并發(fā)程序因上述原因往往沒有確定的結(jié)果值.對于有副作用的函數(shù)或表達式這種先后次序的差異影響則更大,帶來的問題,(4) 死鎖（deadlock）是一種狀態(tài),由于進程對資源有互不相兼容的要求而使進程無法進展.表現(xiàn)為:受到排斥 進程永遠訪問不到所需資源循環(huán)等待 進程資源分配鏈形成一封閉回路無占先(no preemption) 進程無法放棄所占的、其它進程需要的資源.所謂占先,只要所據(jù)資源的進程未處于使用狀態(tài),另一

21、優(yōu)先級高的進程有了要求,則此資源被后者占去把持(wait and hold) 相互以占有對方資源為放棄已占資源的先決條件,帶來的問題,解決死鎖的方法:利用工具作靜態(tài)死鎖檢測,可以避免或減少死鎖出現(xiàn)的可能或事前,讓進程同時提出所有需要的資源, 消除把持條件, 或強行給資源排序, 按此順序滿足要求, 消除循環(huán)等待條件或事前,為調(diào)度程序聲明最大的資源需求一旦出現(xiàn), 最笨的 辦法是重新啟動, 試換數(shù)據(jù), 找出原因改正之。事后重試解決

22、一旦出現(xiàn), 找出死鎖地點, 夭折某些事件或進程或設(shè)置檢測點,帶來的問題,(5) 死等（starvation） 相互競爭的進程如果都滿足進入某一資源條件, 一般采用排隊的先來先服務(wù)原則。相對最公平, 但有的進程占用一種資源時間過長, 致使其它資源長期閑置。 適當?shù)刈屗却梢越夥藕芏嗾紩r少而重要的進程, 這樣更公平。于是, 除了先來先服務(wù)而外, 在調(diào)度例程中約定或在條件中加入優(yōu)先級表來達到此目的。調(diào)度程序則按此優(yōu)先級和先來后到統(tǒng)

23、一調(diào)度。如果優(yōu)先級不當就會造成某些進程永遠處于阻塞態(tài), 死等(但不是死鎖)。死等是不公平調(diào)度引起的。解決的辦法是在改變某些進程的優(yōu)先級, 在公平性和合理性上作某種折衷,,主要內(nèi)容：,并發(fā)程序設(shè)計的基本概念并發(fā)程序帶來的問題需要解決的基本問題程序語言示例,并發(fā)語言需要解決的基本問題,安全性(safety)是程序在執(zhí)行期間不會出現(xiàn)異常的結(jié)果.對于順序程序指其最終狀態(tài)是正確的.對于并發(fā)程序指保證共享變量的互斥訪問和無死鎖出現(xiàn)活性(li

24、veness)是程序能按預(yù)期完成它的工作.對于順序程序指程序能正常終止.對于并發(fā)程序指每個進程能得到它所要求的服務(wù); 或進程總能進入臨界段; 或送出的消息總能到達目的進程, 活性深深受到執(zhí)行機構(gòu)調(diào)度策略的影響公平性(fairness)指在有限進展的假設(shè)下沒有一個進程處于死等狀態(tài). 無條件公平性:調(diào)度策略如能保證每個無條件的原子功能均能執(zhí)行 弱公平性:在具有條件原子動作時, 若條件原子動作能執(zhí)行并依然保持無條件公平性,

25、則為弱公平性 強公平性:條件原子動作一定能執(zhí)行, 則為強公平性,,并發(fā)語言需要解決的基本問題,進程管理：創(chuàng)建；起動（或恢復(fù)）執(zhí)行；阻塞(或叫凍結(jié))；停止執(zhí)行；阻塞父進程創(chuàng)建子進程；撤銷進程等六種操作。通訊機制（信息交流和同步）：基于共享變量的；基于消息傳遞的,難點,一、 忙等待(busy wait) 設(shè)我們把指示變量叫做lock(鎖),每次測試臨界段是否鎖定。競爭進程以測定進入條件(鎖)保持協(xié)調(diào)地進入臨界段, 我

26、們說它在語義上保證了條件同步。 鎖就是條件, 協(xié)調(diào)就是同步 請注意, 此時未設(shè)同步原語。 程度員也無法阻塞停止某個進程。如果有多個進程競爭進入臨界段, 則每個進程都要輪流測試鎖。這就是著名的自旋鎖 (spin lock), 其算法如下:,基于共享變量的通訊機制,,program SPIN＿LOCK: var Lock := false; process P1:: loop

27、 when not lock do ∥條件同步 lock := true; ∥入口協(xié)議 臨界段; lock := false; ∥出口協(xié)議 P1的非臨界段; end do; end loop; end p1; process pn

28、 : end SPIN＿LOCK,process P2:: loop when not lock do lock := true; 臨界段; look := false; P2的非臨界段; end do; end loop; end

29、P2;,,,,,,上述算法如果在多處理器的條件下, 進程嚴格同時到達, 對資源的競爭變成對指示變量查詢和更改的競爭，要取決于操作系統(tǒng)對公用主存儲器的存取訪問的排序。如果某進程進入循環(huán)且正在更新lock為true期間, 第二個進程又訪問了lock(為false), 那么它也進入臨界段。互斥得不到保證。為此, 尋找以忙等待實現(xiàn)互斥同步的算法, 從65年到81年有許多名家寫了上百篇論文, 最后peterson的算法(1981)獲得滿意的解。

30、算法如下:,,program MUTUAL＿EXCLUSION Var enter1 : Boolean := false; enter2 : Boolean := false; turn : String := “P1”; ∥或賦初值“P2” process P1:: loop enter1 := true;

31、 ∥以下三行入口協(xié)議 turn := “P2”; while enter2 and turn = “P2” do skip; ∥ 跳至循環(huán)末端 臨界段; enter2 := false; ∥出口協(xié)議 P1的非臨界段;

32、 end loop; end;end.,process P2:: loop enter2 := true; turn := “P1”; while enter1 and turn = “P1” do skip; 臨界段; enter1 := false; p2的非臨界段;

33、 end loop;end;,,,,,二、 信號燈 Dijkstra 首先理解到忙等待的低級和設(shè)計麻煩, 提出了完整的信號燈(semaphores)理論(1968)。 信號燈是一個非負整值變量 s。在其上定義了兩個操作P, V(取自荷蘭語字頭, 即wait（等待）和signal（示信）。V操作發(fā)信號指示一個事件可以出現(xiàn), P操作延遲所在進程直至某個事件已經(jīng)出現(xiàn): P(s) : await s>0 do s

34、:= s-1; ∥ ‘a(chǎn)wait’ 表達延遲的原語 V(s) : s := s+1;,Program MUTEX＿EXAMPLE; var mutex : Semaphore := 1; process P1:: loop P(mutex); ∥入口協(xié)議 臨界段; V(mut

35、ex); ∥出口協(xié)議 P1的非臨界段; end loop; end p1; process p2:: loop P (mutex); 臨界段; V (mutex); P2的非臨界段;

36、 end loop; end; end.,,例以信號燈實現(xiàn)的兩進程互斥,信號燈變量s, 當只有一個資源時取值{0,1}就夠了, 此時稱為二值信號燈。P, V操作很容易擴大到n個進程競爭一個臨界段。也可以將二值信號燈劈開分別實施同步警衛(wèi)功能。以下是生產(chǎn)者/消費者著名問題的同步解。,program PRODUCER＿CONSUMER var buf : TYPE; ∥任意類型TYPE var empt

37、y : sem := 1, full : sem := 0; ∥兩信號變量初始化 process PRODUCER [i:1.. J]:: loop PRODUCER[i] 產(chǎn)生一條消息m; deposit : P(empty); ∥存入消息m的三個操作 buf := m;

38、 V(full); end loop; end; end PRODUCER＿CONSUMER.,process CONSUMER [j:1..N]:: loop fetch : P(full); ∥從buf取出消息m的三條操作 m := buf; V (empty)； CONSUME R[j]取出

39、這條消息m; end loop;end;,,,,,,將信號變量s一分為二(empty, full)簡化了傳遞方向。稱劈分二值信號燈(split binary semaphore).這個算法保證了互斥,無死鎖 。 將P,V操作擴充到多進程, 多資源(多個臨界段)也是很容易的。例如, 我們可實現(xiàn)q個緩沖區(qū)的多生產(chǎn)、消費者問題。其算法如下:,program PROD＿CONS var buf [1...q], mi,

40、 mj: TYPE; var front :=0, rear :=0; ∥buf 的下標變量 var empty : sem :=q , full: sem :=0, ∥劈分二值信號 var mutexD: sem := 1, mutexF: sem :=1; process PROD[i:1..M]: loop PROD[i]產(chǎn)生一條消息mi de

41、posit : P(empty); P(matexD); buf[rear] := mi; rear := rear mod q+1; V(mutexD); V(full); end loop; end; end PROD＿CONS.,process CO

42、NS [j:1..N]: loop fetch: P(full) ; P(mutexF); mj := buf(front); front := front mod q+1; V (matexF);V (empty); CONS[j]消費消息mi; end loop;end;,,,,,,

43、,選擇互斥是更為復(fù)雜的同步機制。用P, V操作也可以實現(xiàn)選擇互斥。經(jīng)典的例子是哲學家就餐問題。 一張圓桌坐了五位哲學家, 桌上放有一大盆通芯粉, 但只有五把叉子. 而吃通芯粉必須有兩把叉子. 一旦據(jù)有兩把叉子的哲學家就可以吃,否則它只好利用等待的時間思考。如果每人拿一把叉子等待其它人放下叉子, 就產(chǎn)生死鎖。 通芯粉是共享資源, 但叉子是只有兩個哲學家共享的資源。每個哲學家的行為過程即為一進程。第i個進程只和第i

44、和i+1個叉子有關(guān)。故算法如下:,program DINING＿PHILO: var forks [1..5]: sem:= (5*1); process PHILOSOPHER [i: 1..4]: loop P(forks [i]); P(forks[i+1]); 吃通芯粉; V(forks[i]); V (forks [i+1]);

45、 思考問題; end loop; end;end DINING-PHILO.,process PHILOSOPHER [5]: loop P(forks[1]); P(forks[5]); 吃通芯粉; V(forks[1]); V(forks[5]); 思考問題; end loo

46、p;end;,,,,,以上以信號燈實現(xiàn)互斥同步均隱含使用了await等待原語。事實上多數(shù)分時處理的機器, 單主機多處理器的機器是用系統(tǒng)調(diào)用并行核(或叫管理程序)實現(xiàn)的。進程創(chuàng)建就緒后將該進程的描述子(descriptor)入隊, 即就緒進程表, 等待P 操作的完成。這樣, 進程處于就緒或阻塞狀態(tài)且未運行。此時P, V操作的語義解釋是: P(s): if s =1 then s:= 0 el

47、se 置進程于queue中等候V(s): if queue != empty then 從queue中消除一進程,令運行程序執(zhí)行它 else s :=1,基于共享變量的通訊機制,三、條件臨界區(qū)條件臨界區(qū)(Condition Critical Region簡稱CCR)將共享變量顯式地置于叫做資源的區(qū)域內(nèi)每個進程在自己的進程體內(nèi)指明要訪問的條件臨界區(qū)，而同

48、一臨界區(qū)可出現(xiàn)在不同進程之中(誰進誰用)首先在資源中聲明共享變量: resource r(共享變量聲明)，例：resource sema( s:int :=n )使用共享變量：region r when B do S endregion sema when s>0 do s:= s-1 end // P操作region sema do s:= s+1 end // V操作,例: 用CCR實現(xiàn)的生產(chǎn)者與

49、消費者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 empty>0

50、 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 full>0 do full:= full - 1 end; m=buf； r

51、egion sema do empty := empty + 1 end; CONSUMER[j] 消費者取出的這條消息m; end loop; end;end PRODUCER_CONSUMER_CCR.,條件臨界區(qū)評價條件臨界區(qū)最主要的優(yōu)點是概念清晰。此外: 無需輔助標志和變量即可描述共享變量的任何進程交互 程序編譯時即可保證互斥 一個進程創(chuàng)建一個條件不需顧及其它條件是否與此條件有關(guān) 易于程序正確

52、性證明 體現(xiàn)了共享數(shù)據(jù)傳遞的方便它的致命缺點是低效(和信號燈相比)。此外： 進程和共享變量耦合太緊 臨界區(qū)利寫不利讀，一多了就太散，因而也難修改,四、監(jiān)控器Dijkstra建議是把分散在整個程序中的region語句進一步集中成為一個模塊叫做監(jiān)控器(monitor)。program monitor monitor Mname:: 共享數(shù)據(jù)聲明并初始化; proc op1 () is

53、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

54、BOUNDED_BUFFER:: var buf[1..q]：TYPE; var frout :=1，rear :=1，count := 0; var not_full:cond； //當count 0 示信為真 proc deposit (data :TYPE) is while count = q do wait (not_full) end; buf [rear] := data;

55、 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; cou

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

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

58、roc V( ) is s := s+1； signal (pos); end;end SEMAPHORE.,例**： 以監(jiān)控器實現(xiàn)的FIFO信號燈monitor SEMAPHORE:: var s=0; var pos :cond； //當V中pos隊列非空示真 proc P( ) is if s>0 then s:= s-1 endif; ? if s=0 then wait(

59、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 barbe

60、r := 0,chair :=0,open =0; var barber_available :cond //當barber>0 示真 var chair_occupied :cond //當chair>0示真 var door_open:cond //當open=0示真 proc get_haircut( ) is

61、 //顧客調(diào)用 while barber=0 do wait (barber_available) end; barber := barber-1; chair := chair+1； signal (chair_occupied); while open=0 do wait (door_open) end; open := open-1； signal (custom

62、er_left); end; proc get_next_customer( ) is proc finished_cut ( ) isend BARBER_SHOP.,,見下一頁,proc get_next_customer( ) is //理發(fā)師調(diào)用 barber := barber+1； signal (barber_available); while chair=0 do wait (ch

63、air_occupied) end; chair := chair-1; end; proc finished_cut ( ) is //理發(fā)師調(diào)用 open := open+1； signal (door_open); while open>0 do wait (customer_left) end; end;,各種語言實現(xiàn)監(jiān)控器時的原語語義差異監(jiān)控器有三個特征：第一，監(jiān)控器

64、封裝了共享變量，共享變量僅能由監(jiān)控器內(nèi)的過程訪問。第二，監(jiān)控器內(nèi)的過程都是互斥地執(zhí)行的。因而共享變量不能并發(fā)訪問。第三，條件同步由wait和signal操作實現(xiàn)程序設(shè)計語言Mesa包括以上三個特征。UNIX采用上述條件同步。監(jiān)控器有時不一定必須互斥。也可以采用其它辦法實現(xiàn)條件同步。,(1) 實現(xiàn)條件同步的各種信號機制 自動信號AS:只要wait加上條件就可以不用signal原語了.即省去檢查signal是否執(zhí)行的開銷,程序員也不必

65、操心是否用錯。 信號和繼續(xù)SC:當無占先時發(fā)信號的進程繼續(xù)執(zhí)行.直至它進入等待或返回之前,其它進程是不許進入監(jiān)控器的。modula3即采用此種機制。 信號和出口SX:既然被占了先,發(fā)信號的進程也就不等了.立即從監(jiān)控器出口或從過程返回。并發(fā)Pascal即采用此種機制。 信號和等待SW:發(fā)信號的進程被人占先之后處于監(jiān)控器內(nèi)等待，直到它能再次獲得互斥訪問，恢復(fù)執(zhí)行。Modula和并發(fā)Euclid采用這種機制。 信號和急等

66、SU:發(fā)信號進程被人占先之后也要等待，但保證在監(jiān)控器有新的進程進入之前先使它得到恢復(fù)。Pascal_plus即采用這樣的機制。,各種語言實現(xiàn)監(jiān)控器時的原語語義差異,以上五種信號機制語義略有不同，但可從理論上證明它們是等價的。即以一種機制可模擬另一 種機制。實現(xiàn)費用不同，對某些類型問題表達的方便性不同。也正是不同語言各自鐘愛它們的原因。,(2) 嵌套監(jiān)控器中的互斥 在磁盤調(diào)度器之類的應(yīng)用中，一個進程首先要爭取進入磁盤去尋址，找到地址后

67、讀/寫，這樣就要設(shè)計兩個監(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提出以路徑表達式直接控制進程順序的建議--

68、監(jiān)控器中派生出來的一個重要分枝。 路徑表達式是就每一資源在其開始聲明時,就在其上定義操作的約束。 path deposit,fetch end //deposit和fetch并發(fā)執(zhí)行 path deposit;fetch end //deposit必須先于fetch執(zhí)行 path1:（deposit；fetch) end //只能有一條路徑(但可多次執(zhí)行此路徑),兩操作交替互斥執(zhí)行. path N:(1:(d