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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26、們說它在語義上保證了條件同步。 鎖就是條件, 協(xié)調(diào)就是同步 請注意, 此時(shí)未設(shè)同步原語。 程度員也無法阻塞停止某個(gè)進(jìn)程。如果有多個(gè)進(jìn)程競爭進(jìn)入臨界段, 則每個(gè)進(jìn)程都要輪流測試鎖。這就是著名的自旋鎖 (spin lock), 其算法如下:,基于共享變量的通訊機(jī)制,,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;,,,,,,上述算法如果在多處理器的條件下, 進(jìn)程嚴(yán)格同時(shí)到達(dá), 對(duì)資源的競爭變成對(duì)指示變量查詢和更改的競爭，要取決于操作系統(tǒng)對(duì)公用主存儲(chǔ)器的存取訪問的排序。如果某進(jìn)程進(jìn)入循環(huán)且正在更新lock為true期間, 第二個(gè)進(jìn)程又訪問了lock(為false), 那么它也進(jìn)入臨界段?；コ獾貌坏奖ＷC。為此, 尋找以忙等待實(shí)現(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;,,,,,二、 信號(hào)燈 Dijkstra 首先理解到忙等待的低級(jí)和設(shè)計(jì)麻煩, 提出了完整的信號(hào)燈(semaphores)理論(1968)。 信號(hào)燈是一個(gè)非負(fù)整值變量 s。在其上定義了兩個(gè)操作P, V(取自荷蘭語字頭, 即wait（等待）和signal（示信）。V操作發(fā)信號(hào)指示一個(gè)事件可以出現(xiàn), P操作延遲所在進(jìn)程直至某個(gè)事件已經(jīng)出現(xiàn): P(s) : await s>0 do s

34、:= s-1; ∥ ‘a(chǎn)wait’ 表達(dá)延遲的原語 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.,,例以信號(hào)燈實(shí)現(xiàn)的兩進(jìn)程互斥,信號(hào)燈變量s, 當(dāng)只有一個(gè)資源時(shí)取值{0,1}就夠了, 此時(shí)稱為二值信號(hào)燈。P, V操作很容易擴(kuò)大到n個(gè)進(jìn)程競爭一個(gè)臨界段。也可以將二值信號(hào)燈劈開分別實(shí)施同步警衛(wèi)功能。以下是生產(chǎn)者/消費(fèi)者著名問題的同步解。,program PRODUCER＿CONSUMER var buf : TYPE; ∥任意類型TYPE var empt

37、y : sem := 1, full : sem := 0; ∥兩信號(hào)變量初始化 process PRODUCER [i:1.. J]:: loop PRODUCER[i] 產(chǎn)生一條消息m; deposit : P(empty); ∥存入消息m的三個(gè)操作 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;,,,,,,將信號(hào)變量s一分為二(empty, full)簡化了傳遞方向。稱劈分二值信號(hào)燈(split binary semaphore).這個(gè)算法保證了互斥,無死鎖 。 將P,V操作擴(kuò)充到多進(jìn)程, 多資源(多個(gè)臨界段)也是很容易的。例如, 我們可實(shí)現(xiàn)q個(gè)緩沖區(qū)的多生產(chǎn)、消費(fèi)者問題。其算法如下:,program PROD＿CONS var buf [1...q], mi,

40、 mj: TYPE; var front :=0, rear :=0; ∥buf 的下標(biāo)變量 var empty : sem :=q , full: sem :=0, ∥劈分二值信號(hào) 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]消費(fèi)消息mi; end loop;end;,,,,,,

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

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

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

48、一臨界區(qū)可出現(xiàn)在不同進(jìn)程之中(誰進(jì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實(shí)現(xiàn)的生產(chǎn)者與

49、消費(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 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] 消費(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) 易于程序正確

52、性證明 體現(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 () is

53、end; ... proc opn () is end; end; process Pname [i:1..N]:: 局部數(shù)據(jù)聲明并初始化 begin : call Mname.opi (實(shí)參表); : end begin 初始化，激活進(jìn)程 end monitor.,例: 有界緩沖區(qū)的監(jiān)控器實(shí)現(xiàn)算法monitor

54、BOUNDED_BUFFER:: var buf[1..q]：TYPE; var frout :=1，rear :=1，count := 0; var not_full:cond； //當(dāng)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)控器實(shí)現(xiàn)條件同步的技術(shù)(1) 復(fù)蓋條件變量(2) 傳遞條件(3) 有無占先對(duì)競爭的并發(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)程交互是客戶

57、/服務(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)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)控器實(shí)現(xiàn)的FIFO信號(hào)燈monitor SEMAPHORE:: var s=0; var pos :cond； //當(dāng)V中pos隊(duì)列非空示真 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. 注:本例中“?”號(hào)表示和前一個(gè)語句并行執(zhí)行的語句,以下同.,例*** 貪睡的理發(fā)師的模擬解monitor BARBER_SHOP:: var barbe

60、r := 0,chair :=0,open =0; var barber_available :cond //當(dāng)barber>0 示真 var chair_occupied :cond //當(dāng)chair>0示真 var door_open:cond //當(dāng)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;,各種語言實(shí)現(xiàn)監(jiān)控器時(shí)的原語語義差異監(jiān)控器有三個(gè)特征：第一，監(jiān)控器

64、封裝了共享變量，共享變量僅能由監(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í)行的開銷,程序員也不必

65、操心是否用錯(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)和急等

66、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)程首先要爭取進(jìn)入磁盤去尋址，找到地址后

67、讀/寫，這樣就要設(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)程順序的建議--

68、監(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:(d