1、一、進程的并發(fā)性 二、進程的互斥三、進程的同步四、同步與互斥的混合問題一、進程的并發(fā)性一、進程的并發(fā)性 程序并行性的表示：程序并行性的表示：Cobegin S1；S2；SnCoend 在多道系統(tǒng)中，假如有兩個進程在多道系統(tǒng)中，假如有兩個進程A A和和B B，它們要求順序執(zhí)行的操，它們要求順序執(zhí)行的操作如下：作如下： 進程進程A A：a a1 1,a,a2 2,a,a3 3,a,a4 4, ,a,an n 進程進程B B：b b1 1,b,b2 2,b,b3 3,b,b4 4, ,b,bm m這兩個進程是在處理器上交替執(zhí)行的，可能出現(xiàn)的執(zhí)行序列有：這兩個進程是在處理器上交替執(zhí)行的，可能出現(xiàn)的執(zhí)行

2、序列有：a a1 1,b,b1 1,a,a2 2,b,b2 2, ,和和a a1 1,a,a2 2,b,b1 1,b,b2 2, , ,等等，它們的執(zhí)行在時間上是重疊等等，它們的執(zhí)行在時間上是重疊的，這被稱為的，這被稱為“可同時執(zhí)行的可同時執(zhí)行的”。 在多道程序環(huán)境下，進程之間存在以下關系在多道程序環(huán)境下，進程之間存在以下關系q 資源共享關系資源共享關系q 相互合作關系相互合作關系 觀察者觀察者begin L：observe a lorry； count := count +1； goto Lend；報告者報告者begin print count； count := 0；end；樣例樣例1 1

3、：假定某一時刻，觀察者已記錄了：假定某一時刻，觀察者已記錄了N N輛車，又輛車，又在記錄下一輛車，此時，報告者也開始工作。在記錄下一輛車，此時，報告者也開始工作。 與時間有關的錯誤與時間有關的錯誤執(zhí)行順序執(zhí)行順序1 1：（觀察者）（觀察者）count := count + 1;count := count + 1;（報告者）（報告者）report;report;（報告者）（報告者）count := 0;count := 0;這是正確的結果。這是正確的結果。 執(zhí)行順序執(zhí)行順序2 2：（報告者）（報告者）report count;report count;（觀察者）（觀察者）count := co

4、unt +1;count := count +1;（報告者）（報告者）count := 0;count := 0;觀察者剛剛記錄的一輛車的信息丟失了觀察者剛剛記錄的一輛車的信息丟失了 造成不正確的因素是與進程占用處理器的時間、造成不正確的因素是與進程占用處理器的時間、執(zhí)行的速度以及外界的影響有關。這些因素都與時間執(zhí)行的速度以及外界的影響有關。這些因素都與時間有關，所以，稱它們?yōu)橛嘘P，所以，稱它們?yōu)椤芭c時間有關的錯誤與時間有關的錯誤”樣例樣例2 2：飛機航班有：飛機航班有N N個售票處，每個售票個售票處，每個售票處通過終端訪問系統(tǒng)的公共數(shù)據(jù)區(qū)。處通過終端訪問系統(tǒng)的公共數(shù)據(jù)區(qū)。 售票處售票處1be

5、gin 從數(shù)據(jù)單元中取出現(xiàn)從數(shù)據(jù)單元中取出現(xiàn) 有余票；有余票； 做減做減1操作；操作； 把結果送回到數(shù)據(jù)單元把結果送回到數(shù)據(jù)單元end;售票處售票處2begin 從數(shù)據(jù)單元中取出現(xiàn)從數(shù)據(jù)單元中取出現(xiàn) 有余票；有余票； 做減做減1操作；操作； 把結果送回到數(shù)據(jù)單元把結果送回到數(shù)據(jù)單元end;假定現(xiàn)有余票為假定現(xiàn)有余票為1 1執(zhí)行順序：執(zhí)行順序：（售票處（售票處1 1）從數(shù)據(jù)單元中取出現(xiàn)有余票；）從數(shù)據(jù)單元中取出現(xiàn)有余票；（售票處（售票處2 2）從數(shù)據(jù)單元中取出現(xiàn)有余票；）從數(shù)據(jù)單元中取出現(xiàn)有余票；（售票處（售票處1 1）做減）做減1 1操作；操作；（售票處（售票處1 1）把結果送回到數(shù)據(jù)單元；）

6、把結果送回到數(shù)據(jù)單元；（售票處（售票處2 2）做減）做減1 1操作；操作；（售票處（售票處2 2）把結果送回到數(shù)據(jù)單元；）把結果送回到數(shù)據(jù)單元；結果是把一張票賣給了兩個顧客。結果是把一張票賣給了兩個顧客。 與時間有關的錯誤產(chǎn)生的原因：多個進程與時間有關的錯誤產(chǎn)生的原因：多個進程不受限制的對同一數(shù)據(jù)對象進行存取操作。不受限制的對同一數(shù)據(jù)對象進行存取操作。 二、進程的互斥二、進程的互斥 有共享資源的進程執(zhí)行時出現(xiàn)與時間有關的錯誤，有共享資源的進程執(zhí)行時出現(xiàn)與時間有關的錯誤，其根本原因是對共享資源的使用不受限制。進程交叉其根本原因是對共享資源的使用不受限制。進程交叉使用了共享資源從而造成了錯誤。使用

7、了共享資源從而造成了錯誤。 幾個基本概念幾個基本概念 1 1、臨界資源臨界資源 一次僅允許一個進程訪問的資源被稱為一次僅允許一個進程訪問的資源被稱為 臨界資源臨界資源 2 2、臨界區(qū)臨界區(qū) 臨界區(qū)的定義：把在進程中那段訪問臨臨界區(qū)的定義：把在進程中那段訪問臨 界區(qū)的代碼稱為臨界區(qū)。界區(qū)的代碼稱為臨界區(qū)。 對臨界區(qū)管理的要求：對臨界區(qū)管理的要求： 一次最多讓一個進程進入臨界區(qū)一次最多讓一個進程進入臨界區(qū) 任何一個進入臨界區(qū)的進程必須在一個有限的時間任何一個進入臨界區(qū)的進程必須在一個有限的時間 內(nèi)退出臨界區(qū)。內(nèi)退出臨界區(qū)。 若有多個進程同時要求進入它們的臨界區(qū)，則應在若有多個進程同時要求進入它們的

8、臨界區(qū)，則應在 有限的時間內(nèi)讓其中之一進入。有限的時間內(nèi)讓其中之一進入。處理臨界區(qū)的原則：處理臨界區(qū)的原則：1、當無進程處于臨界區(qū)時，允許一進程立即進入臨界區(qū)、當無進程處于臨界區(qū)時，允許一進程立即進入臨界區(qū)2、當某一進程已進入臨界區(qū)時，其它試圖進入臨界區(qū)進、當某一進程已進入臨界區(qū)時，其它試圖進入臨界區(qū)進 程必須等待程必須等待3、當某已進程離開臨界區(qū)時，若有進程等待，則允許其、當某已進程離開臨界區(qū)時，若有進程等待，則允許其 中之一進入臨界區(qū)中之一進入臨界區(qū)4、當進程不能進入臨界區(qū)時，應立即釋放處理機，避免、當進程不能進入臨界區(qū)時，應立即釋放處理機，避免 忙等。忙等。 對臨界資源同時提出訪問請求的

9、諸進程的執(zhí)行要加對臨界資源同時提出訪問請求的諸進程的執(zhí)行要加以限制，以防止上述以限制，以防止上述“與時間有關的錯誤與時間有關的錯誤”。這種對臨。這種對臨界資源的排它訪問稱為互斥。界資源的排它訪問稱為互斥。 早期的研究結果表明，互斥問題的解決并不是一件早期的研究結果表明，互斥問題的解決并不是一件很簡單的事情。很簡單的事情。解決互斥問題的軟件方法解決互斥問題的軟件方法假設有兩個進程假設有兩個進程P Pi i和和P Pj j，共享一個臨界資源，共享一個臨界資源R R。方法一：方法一： 設置一公用整型變量設置一公用整型變量turnturn，用于指示被允許進入，用于指示被允許進入臨界區(qū)的進程的編號。臨界

10、區(qū)的進程的編號。repeat while tern i do no op; 進入臨界區(qū)進入臨界區(qū) turn = j;until false;repeat while tern j do no op; 進入臨界區(qū)進入臨界區(qū) turn = i;until false; 該方法可以確保每次只允許一個進程進入臨界該方法可以確保每次只允許一個進程進入臨界區(qū)，但不符合處理臨界區(qū)的原則區(qū)，但不符合處理臨界區(qū)的原則1 1，易造成資源利用，易造成資源利用不充分。不充分。方法二：方法二： 基本思想：在每一個進程訪問臨界資源之前，先基本思想：在每一個進程訪問臨界資源之前，先查看一下臨界資源是否正被訪問。若正被訪問，

11、則進查看一下臨界資源是否正被訪問。若正被訪問，則進程等待；否則進入自己的臨界區(qū)。為此，設置一個數(shù)程等待；否則進入自己的臨界區(qū)。為此，設置一個數(shù)組組flagflag，每個元素的初值為，每個元素的初值為falsefalse，表示進程未進入臨，表示進程未進入臨界區(qū)，進程進入臨界區(qū)后，相應標志位置為界區(qū)，進程進入臨界區(qū)后，相應標志位置為truetrue。repeat while flagj do no op; flagi = true； 進入臨界區(qū)進入臨界區(qū) flagi = false;until false;repeat while flagi do no op; flagj = true； 進入臨

12、界區(qū)進入臨界區(qū) flagj = false;until false; 方法二可以滿足原則方法二可以滿足原則1 1，但又出現(xiàn)了新的問題。，但又出現(xiàn)了新的問題。比如，當比如，當P Pi i和和P Pj j幾乎在同時都要求進入臨界區(qū)，因幾乎在同時都要求進入臨界區(qū)，因而都發(fā)現(xiàn)對方的訪問標志為而都發(fā)現(xiàn)對方的訪問標志為falsefalse，于是兩進程都先，于是兩進程都先后進入臨界區(qū)，顯然，這不符合臨界區(qū)處理的原則后進入臨界區(qū)，顯然，這不符合臨界區(qū)處理的原則2 2。 為了解決這個問題，把標志位的含義改變?yōu)椋簽榱私鉀Q這個問題，把標志位的含義改變?yōu)椋簍ruetrue表示進程希望進入臨界區(qū)，即當進程要進入臨表示進

13、程希望進入臨界區(qū)，即當進程要進入臨界區(qū)前，先將標志位界區(qū)前，先將標志位flagflag置為置為truetrue，表示進程已要，表示進程已要求進入臨界區(qū)，然后再去查看另一進程的標志，若求進入臨界區(qū)，然后再去查看另一進程的標志，若另一進程的另一進程的flagflag標志也為標志也為truetrue，則本進程等待，否，則本進程等待，否則，本進程進入臨界區(qū)。則，本進程進入臨界區(qū)。 換句話說，進程要進入臨界區(qū)，首先設置其要換句話說，進程要進入臨界區(qū)，首先設置其要求進入的標志，然后，再去查看其他進程的標志。求進入的標志，然后，再去查看其他進程的標志。方法三：方法三：repeat flagi = true；

14、 while flagj do no op; 進入臨界區(qū)進入臨界區(qū) flagi = false;until false;repeat flagj = true； while flagi do no op; 進入臨界區(qū)進入臨界區(qū) flagj = false;until false; 該方法可以有效地防止兩個進程同時進入臨界該方法可以有效地防止兩個進程同時進入臨界區(qū)，但仔細分析又可看出，該方法可能會造成兩個區(qū)，但仔細分析又可看出，該方法可能會造成兩個進程都不能進入臨界區(qū)的后果。例如，當兩個進程進程都不能進入臨界區(qū)的后果。例如，當兩個進程同時要求進入臨界區(qū)，分別將自己的標志位置為同時要求進入臨界區(qū)，

15、分別將自己的標志位置為truetrue，再去查看另一進程的標志，發(fā)現(xiàn)也為，再去查看另一進程的標志，發(fā)現(xiàn)也為truetrue，于是都等待，誰也無法進入臨界區(qū)。于是都等待，誰也無法進入臨界區(qū)。方法四：方法四：repeat flagi = true；turn = j; while flagj and turn = j do no op; 進入臨界區(qū)進入臨界區(qū) flagi = false;until false; 假如進程假如進程P Pi i和和P Pj j幾乎同時要求進入臨界區(qū)，它幾乎同時要求進入臨界區(qū)，它們分別將們分別將flagiflagi和和flagjflagj置為置為truetrue。PiPi

16、先將先將turnturn置為置為j j，當它執(zhí)行，當它執(zhí)行whilewhile語句時，條件成立，故等待。語句時，條件成立，故等待。但但P Pj j會立即將會立即將turnturn置為置為i i，這樣，這樣P Pi i就可以進入臨界區(qū)。就可以進入臨界區(qū)。P Pi i退出臨界區(qū)時會將退出臨界區(qū)時會將flagiflagi置為置為falsefalse，從而可以，從而可以使使P Pj j進入臨界區(qū)。進入臨界區(qū)。 利用軟件方法解決互斥問題有一定難度，利用軟件方法解決互斥問題有一定難度，在使用同一資源的進程數(shù)量較大時，有很大的在使用同一資源的進程數(shù)量較大時，有很大的局限性。局限性。 另外一種解決互斥問題的方

17、法是鎖機制。另外一種解決互斥問題的方法是鎖機制。為臨界資源設置一個鎖為臨界資源設置一個鎖w w，當進程在進入臨界區(qū)，當進程在進入臨界區(qū)之前，首先測試之前，首先測試w w的狀態(tài)。的狀態(tài)。w w等于等于1 1表示上鎖，該表示上鎖，該資源已被占用；資源已被占用；w w等于等于0 0表示開鎖，該資源已空表示開鎖，該資源已空閑，未被占用。閑，未被占用。Lock w: L: if w = 1 then goto L else w := 1Unlock w: w := 0; 軟件的解決方法四和鎖機制雖然可以在一軟件的解決方法四和鎖機制雖然可以在一定程度上解決互斥問題，但進程在等待時都需定程度上解決互斥問題，

18、但進程在等待時都需要不停地進行測試。這不滿足處理臨界區(qū)的原要不停地進行測試。這不滿足處理臨界區(qū)的原則則4 4，降低了系統(tǒng)工作效率。，降低了系統(tǒng)工作效率。信號量同步機制信號量同步機制 一個信號量可以看成由兩個部分組成：一一個信號量可以看成由兩個部分組成：一個是整型變量，另一個是隊列。個是整型變量，另一個是隊列。整型整型變量變量隊列隊列Procedure P (Var S: Semaphore) begin S := S 1; if S 0 then W(S) end;Procedure V (Var S: Semaphore) begin S := S + 1; if S = 1 then if

19、 r = 1 then begin begin r := r 1; r := r 1; A := r; A := r; V(S); V(S); 售出一張票售出一張票; endend else else 售出票已售完售出票已售完;endend；PROCESS PiPROCESS Pir : integer;r : integer;beginbegin P(S); P(S); r := A; r := A; if r = 1 then if r = 1 then begin begin r := r 1; r := r 1; A := r; A := r; V(S); V(S); 售出一張票售出一

20、張票; endend else else begin begin V(S); V(S); 售出票已售完售出票已售完 endendendend；無法退出無法退出臨界區(qū)臨界區(qū)讀者寫者問題：讀者寫者問題：規(guī)定：允許多個進程同時讀；只允許一個進程寫；規(guī)定：允許多個進程同時讀；只允許一個進程寫；當有進程讀時不允許其它進程寫。當有進程讀時不允許其它進程寫。第一種方案：定義信號量：第一種方案：定義信號量：S: semaphoreS: semaphore；初值；初值1 1；定義一個整數(shù)：定義一個整數(shù)：rsrs ，初值，初值0 0； 讀者：讀者：PROCESS Readeribegin rs := rs + 1

21、; if rs = 1 then P(S); read file F; rs := rs 1; if rs = 0 then V(S);end;寫者：寫者：PROCESS Writerjbegin P(S); write file F; V(S);end;問題：對共享變量問題：對共享變量rsrs訪問的程序段也是臨界區(qū)。訪問的程序段也是臨界區(qū)。 改進的方案：改進的方案：定義信號量：定義信號量：S, SrS, Sr: semaphore: semaphore；分別為互斥訪問；分別為互斥訪問文件和計數(shù)變量的信號量，初值均為文件和計數(shù)變量的信號量，初值均為1 1；定義一個；定義一個整數(shù)：整數(shù)：rsrs

22、 ，初值，初值0 0； 讀者：讀者：PROCESS Readerbegin P(Sr); rs := rs + 1; if rs = 1 then P(S); V(Sr); read file F; P(Sr); rs := rs 1; if rs = 0 then V(S); V(Sr);end;寫者：寫者：PROCESS Writerbegin P(S); write file F; V(S);end;例題：試用例題：試用P P、V V操作寫出讀者優(yōu)先的同步算法。操作寫出讀者優(yōu)先的同步算法。解答：解答： 定義兩個變量定義兩個變量RCRC和和WCWC，分別用于對進入臨界區(qū)的，分別用于對進入臨

23、界區(qū)的讀者和寫者進程計數(shù)。為了互斥的操作這兩個變量，讀者和寫者進程計數(shù)。為了互斥的操作這兩個變量，需設置兩個相應的信號量需設置兩個相應的信號量RCSRCS和和WCSWCS。 為了使讀者為了使讀者- -寫者之間和寫者寫者之間和寫者- -寫者之間互斥的訪寫者之間互斥的訪問緩沖區(qū)，設置信號量問緩沖區(qū)，設置信號量S S。 為了阻止讀者進程和鏈接等待的寫者進程，設置為了阻止讀者進程和鏈接等待的寫者進程，設置信號量信號量W W。 為了鏈接等待的讀者進程，設置信號量為了鏈接等待的讀者進程，設置信號量R R。 這樣，當有第一個寫者進程進入臨界區(qū)后，所有這樣，當有第一個寫者進程進入臨界區(qū)后，所有的試圖進入臨界區(qū)

24、的讀者進程將被阻塞在信號量的試圖進入臨界區(qū)的讀者進程將被阻塞在信號量R R上，上，而寫者進程將優(yōu)先進入臨界區(qū)。而寫者進程將優(yōu)先進入臨界區(qū)。讀者：讀者：PROCESS Readerbegin P(R); P(W); P(RCS); if RC = 0 then P(S); RC := RC + 1; V(RCS); V(W); V(R); read file F; P(RCS); RC := RC 1; if RC = 0 then V(S); V(RCS);end;寫者：寫者：PROCESS Writerbegin P(WCS); if WC:= 0 then P(W); WC := WC +

25、 1; V(WCS); P(S); write file F; V(S); P(WCS); WC := WC 1; if WC = 0 then V(W); V(WCS);end;R := W := RCS := WCS := S := 1;RC := WC := 0;例題：舉例說明例題：舉例說明P P、V V操作為什么要被設計成原語（即對同一信操作為什么要被設計成原語（即對同一信號量上的操作必須互斥）。號量上的操作必須互斥）。解答：解答：對于對于P P操作，過程為：操作，過程為： Procedure P (Var S: Semaphore) begin S := S 1; if S 0 th

26、en W(S) end;假如有兩個進程假如有兩個進程P1P1、P2P2幾乎在同時作幾乎在同時作P P操作，信號量操作，信號量S S的初值為的初值為1 1。如果進程如果進程P1P1先作先作P P操作，則操作，則S S的值為的值為0 0，P1P1進程不應被阻塞（或掛進程不應被阻塞（或掛起）。但是，如果起）。但是，如果P P操作不是原語操作，則可能有如下執(zhí)行順序：操作不是原語操作，則可能有如下執(zhí)行順序：P1P1：S := S - 1S := S - 1P2P2：S := S - 1S := S - 1P1P1：if S 0 then W(S)if S 0 then W(S)由于此時由于此時S S為為

27、 1 1，P1P1將被阻塞，這樣，將被阻塞，這樣，P P操作就不符合原來的語操作就不符合原來的語義了。義了。 同樣，對于同樣，對于V V操作，過程為：操作，過程為： Procedure V (VarProcedure V (Var S: Semaphore) S: Semaphore) begin S := S + 1; begin S := S + 1; if S = 0 then R(S) if S = 0 then R(S) end; end;假如有兩個進程假如有兩個進程P1P1、P2P2幾乎在同時作幾乎在同時作V V操作，信號量操作，信號量S S的初值的初值為為-1-1。如果進程。如果

28、進程P1P1先作先作V V操作，則操作，則S S的值為的值為0 0，該，該V V操作應該喚操作應該喚醒一個被醒一個被P P操作阻塞的進程。但是，如果操作阻塞的進程。但是，如果V V操作不是原語操作，操作不是原語操作，則可能有如下執(zhí)行順序：則可能有如下執(zhí)行順序： P1P1：S := S + 1S := S + 1 P2 P2：S := S + 1S := S + 1 P1 P1：if S = 0 then R(S)if S = 0 then R(S)由于此時由于此時S S為為1 1，P1P1所作的所作的V V操作將不再去喚醒被阻塞的進程，操作將不再去喚醒被阻塞的進程，這樣，這樣，V V操作就不符

29、合原來的語義了。操作就不符合原來的語義了。 另外，如果在另外，如果在P P操作過程中插入了操作過程中插入了V V操作，也會操作，也會出現(xiàn)不符合語義的情況。例如，假定出現(xiàn)不符合語義的情況。例如，假定S S的值為的值為0 0，按，按照照P P操作的語義，作操作的語義，作P P操作的進程應該被阻塞，但是，操作的進程應該被阻塞，但是，如果有如下執(zhí)行順序：如果有如下執(zhí)行順序： A A進程的進程的P P操作語句：操作語句：S := S - 1S := S - 1 B B進程的進程的V V操作語句：操作語句：S := S + 1S := S + 1 A A進程的進程的P P操作語句：操作語句：if S 0

30、then W(S)if S 0 then W(S) 則作則作P P操作的進程將不會被阻塞，這不符合語義。操作的進程將不會被阻塞，這不符合語義。 三、進程的同步三、進程的同步 協(xié)作協(xié)作 buffer1buffer2輸入設備輸入設備打印設備打印設備輸入進程輸入進程計算進程計算進程打印進程打印進程P1P2P3這里，計算進程這里，計算進程C C和打印進程和打印進程P P的工作必須相互的工作必須相互協(xié)作：計算進程只有在緩沖區(qū)中無數(shù)據(jù)時才能協(xié)作：計算進程只有在緩沖區(qū)中無數(shù)據(jù)時才能向其寫入數(shù)據(jù)；打印進程只有在緩沖區(qū)中已有向其寫入數(shù)據(jù)；打印進程只有在緩沖區(qū)中已有數(shù)據(jù)時才能將從中取出并打印。數(shù)據(jù)時才能將從中取出

31、并打印。兩個進程應做如下協(xié)作兩個進程應做如下協(xié)作1 1、進程、進程C C把一個記錄存入緩沖區(qū)后，應向進程把一個記錄存入緩沖區(qū)后，應向進程P P發(fā)發(fā) 送送“緩沖區(qū)中有等待處理的記錄緩沖區(qū)中有等待處理的記錄”的消息；的消息；2 2、進程、進程P P從緩沖區(qū)取出記錄后，應向進程從緩沖區(qū)取出記錄后，應向進程C C發(fā)送發(fā)送 “ “緩沖區(qū)中的記錄已取走緩沖區(qū)中的記錄已取走”的消息；的消息；3 3、進程、進程C C只有在得到進程只有在得到進程P P發(fā)送來的發(fā)送來的“緩沖區(qū)中的緩沖區(qū)中的 記錄已取走記錄已取走”的消息后，才能把下一個記錄存的消息后，才能把下一個記錄存 入緩沖區(qū)，否則，進程入緩沖區(qū)，否則，進程C

32、 C等待，直到消息到達；等待，直到消息到達；4 4、進程、進程P P只有在得到進程只有在得到進程C C發(fā)送來的發(fā)送來的“緩沖區(qū)中有緩沖區(qū)中有 等待處理的記錄等待處理的記錄”的消息后，才能從緩沖區(qū)取的消息后，才能從緩沖區(qū)取 出記錄，否則，進程出記錄，否則，進程P P等待，直到消息到達。等待，直到消息到達。buffer1buffer2輸入設備輸入設備打印設備打印設備輸入進程輸入進程計算進程計算進程打印進程打印進程P1P2P3PROCESS calculatorbeginL1: P(SB); 計算下一個數(shù)據(jù)計算下一個數(shù)據(jù) 并送入緩沖區(qū)并送入緩沖區(qū); V(SA); goto L1;end;PROCES

33、S printerbeginL2: P(SA); 從緩沖區(qū)中取出從緩沖區(qū)中取出 數(shù)據(jù)并打印數(shù)據(jù)并打印; V(SB); goto L2;end;同步機制同步機制 調用調用P P操作測試消息是否到達操作測試消息是否到達 調用調用V V操作發(fā)送消息操作發(fā)送消息 生產(chǎn)者生產(chǎn)者- -消費者問題消費者問題簡單的生產(chǎn)者、消費者問題（單緩沖區(qū)）簡單的生產(chǎn)者、消費者問題（單緩沖區(qū)）定義：整型變量：定義：整型變量：BufferBuffer，信號量：，信號量：SP=1, SG=0SP=1, SG=0 PROCESS Producerbegin L1: produce a product; P(SP); Buffer

34、 := product; V(SG); goto L1endPROCESS Consumerbegin L2: P(SG); Take a product form Buffer; V(SP); goto L2end多緩沖區(qū)生產(chǎn)者、消費者問題多緩沖區(qū)生產(chǎn)者、消費者問題 PROCESS Producerbegin L1: produce a product; P(SP); Bk := product; k := (k + 1) mod n; V(SG); goto L1endPROCESS Consumerbegin L2: P(SG); Take a product form Bt; t :=

35、 (t + 1) mod n V(SP); consumer; goto L2end定義：整型變量：定義：整型變量：k = 0, t = 0k = 0, t = 0 整型數(shù)組：整型數(shù)組：B0B0n-1n-1 信號量：信號量：SP = n, SG = 0 SP = n, SG = 0 例子：三個進程例子：三個進程R R、W1W1、W2W2，共享一個緩沖區(qū)，共享一個緩沖區(qū)B B，B B中最多只能中最多只能存放一個數(shù)。進程存放一個數(shù)。進程R R負責不斷地向負責不斷地向B B中存入整數(shù)，進程中存入整數(shù)，進程W1W1、W2W2分分別負責取出別負責取出B B中的奇數(shù)和偶數(shù)并進行打印。中的奇數(shù)和偶數(shù)并進行打

36、印。PROCESS Rx: integer;beginL1: 從輸入設備中讀入從輸入設備中讀入 一個數(shù)一個數(shù); x := 讀入的數(shù)；讀入的數(shù)；P(S);B := x; if B=奇數(shù)奇數(shù) then V(SO) else V(SE) goto L1;endPROCESS W1y: integer;beginL2: P(SO); y := B； V(S); 打印打印y中數(shù)中數(shù)； goto L2;endPROCESS W2z: integer;beginL3: P(SE); z := B； V(S); 打印打印z中數(shù)中數(shù)； goto L3;end定義信號量：定義信號量：S S 初值為初值為1 1 表

37、示初始時緩沖區(qū)可用表示初始時緩沖區(qū)可用 SO SO 初值為初值為0 0 用于向打印奇數(shù)的進程發(fā)消息用于向打印奇數(shù)的進程發(fā)消息 SE SE 初值為初值為0 0 用于向打印偶數(shù)的進程發(fā)消息用于向打印偶數(shù)的進程發(fā)消息四、同步與互斥的混合問題四、同步與互斥的混合問題 例子：有例子：有m m個生產(chǎn)者和個生產(chǎn)者和r r個消費者共享容量為個消費者共享容量為n n的緩沖的緩沖器（器（m m、r r、n n均大于均大于1 1）。每個生產(chǎn)者把自己生產(chǎn)的物）。每個生產(chǎn)者把自己生產(chǎn)的物品存入緩沖區(qū)，每個消費者從緩沖區(qū)中取出物品去消品存入緩沖區(qū)，每個消費者從緩沖區(qū)中取出物品去消費。要求用費。要求用P P、V V操作對這

38、些生產(chǎn)者和消費者進行正確操作對這些生產(chǎn)者和消費者進行正確管理。管理。定義：整型數(shù)組：定義：整型數(shù)組：B0B0n-1n-1 整型變量：整型變量：k k，t t 初值均為初值均為0 0 信號量：信號量：S1S1：初值：初值1 1 用于生產(chǎn)者放入物品用于生產(chǎn)者放入物品 S2S2：初值：初值1 1 用于消費者取出物品用于消費者取出物品 SPSP：初值：初值n n 緩沖區(qū)是否可用緩沖區(qū)是否可用 SGSG：初值：初值0 0 緩沖區(qū)里是否有物品緩沖區(qū)里是否有物品PROCESS PibeginL1: produce a product; P(SP); P(S1); Bk := product; k := (k

39、 + 1) mod n; V(S1); V(SG); goto L1endPROCESS CjbeginL2: P(SG); P(S2); take a product from Bt; t := (t + 1) mod n; V(S2); V(SP); consume; goto L1end生產(chǎn)者分別向緩沖區(qū)送產(chǎn)品，由生產(chǎn)者分別向緩沖區(qū)送產(chǎn)品，由S1S1控制互斥訪問?？刂苹コ庠L問。消費者分別從緩沖區(qū)中取出產(chǎn)品，由消費者分別從緩沖區(qū)中取出產(chǎn)品，由S2S2控制互斥訪問?？刂苹コ庠L問。例子：例子：現(xiàn)有四個進程現(xiàn)有四個進程R1R1、R2R2、W1W1、W2W2，它們共享一個，它們共享一個可以存放一個

40、數(shù)的緩沖器可以存放一個數(shù)的緩沖器B B，R1R1、R2R2從鍵盤和從鍵盤和磁盤上讀入數(shù)據(jù)，放到緩沖器磁盤上讀入數(shù)據(jù)，放到緩沖器B B中，中，W1W1、W2W2從從緩沖器中分別讀取緩沖器中分別讀取R1R1，R2R2寫入的數(shù)據(jù)并輸出打寫入的數(shù)據(jù)并輸出打印。怎樣用印。怎樣用P P、V V操作來協(xié)調四個進程的并發(fā)執(zhí)操作來協(xié)調四個進程的并發(fā)執(zhí)行行？定義：信號量定義：信號量 S S 初值為初值為1 1 用于寫入進程的互斥用于寫入進程的互斥 S1 S1 初值為初值為0 R10 R1向向W1W1發(fā)送消息發(fā)送消息 S2 S2 初值為初值為0 R20 R2向向W2W2發(fā)送消息發(fā)送消息 整型變量整型變量 B BPR

41、OCESS R1x: integerbeginL1: 接受來自鍵盤的數(shù)接受來自鍵盤的數(shù)； x := 接受的數(shù)接受的數(shù); P(S); B := x; V(S1); goto L1endPROCESS R2y: integerbeginL2: 從磁盤上讀一個數(shù)從磁盤上讀一個數(shù)； y := 讀入的數(shù)讀入的數(shù); P(S); B := y; V(S2); goto L2endPROCESS W1k: integerbeginL4: P(S1); k := B; V(S); 打印打印k中的數(shù)中的數(shù)； goto L3endPROCESS W2j: integerbeginL4: P(S2); j := B;

42、 V(S); 打印打印k中的數(shù)中的數(shù)； goto L3end例題：假定一個閱覽室最多可以同時容納例題：假定一個閱覽室最多可以同時容納100100個人閱讀，讀者進入和離開閱覽室時，個人閱讀，讀者進入和離開閱覽室時，都必須在閱覽室門口的一個登記表上登記都必須在閱覽室門口的一個登記表上登記或去掉登記。試用或去掉登記。試用P P、V V操作編寫讀者進程操作編寫讀者進程的同步算法。的同步算法。分析：設讀者有任意多個，但能同時閱覽分析：設讀者有任意多個，但能同時閱覽的只能的只能100100人，所以，設一個信號量人，所以，設一個信號量S S代表代表空座位數(shù)目，初值為空座位數(shù)目，初值為100100，用它來控制

43、進入，用它來控制進入閱覽室的讀者進程不超過閱覽室的讀者進程不超過100100。另設信號量。另設信號量m m，用于控制對登記表這一共享資源的互斥，用于控制對登記表這一共享資源的互斥使用，其初值為使用，其初值為1 1。Process 第第i個讀者進程個讀者進程 begin P(S); P(m); 填寫登記表；填寫登記表； V(m); 坐下閱覽坐下閱覽; P(m); 在登記表上去掉登記；在登記表上去掉登記； V(m); V(S); goto L1; end例題：有一個倉庫存放兩種零件例題：有一個倉庫存放兩種零件A A和和B B，最大庫容量各為，最大庫容量各為M M個。有一車間不斷的取個。有一車間不斷

44、的取A A和和B B進行裝配，每次各取一個。進行裝配，每次各取一個。有兩組供應商分別不斷的供應有兩組供應商分別不斷的供應A A和和B B（每次供應一個）。（每次供應一個）。為保證配套和合理庫存，當某種零件的數(shù)量比另一種的為保證配套和合理庫存，當某種零件的數(shù)量比另一種的數(shù)量超過數(shù)量超過n n（n Mn = 1 and . and S = 1 and . and Sn n = 1) = 1) for i:=1 to n do for i:=1 to n do S Si i := S := Si i 1; 1; else else 將當前執(zhí)行進程插入到將當前執(zhí)行進程插入到S Si i的等待隊列，的等

45、待隊列， S Si i是第一個滿足是第一個滿足S Si i 1 = t = t1 1 and . and S and . and Sn n = t = tn n) ) for i:=1 to n do for i:=1 to n do S Si i := S := Si i d di i; ; else else 將當前執(zhí)行進程插入到將當前執(zhí)行進程插入到S Si i的等待隊列，的等待隊列， S Si i是第一個滿足是第一個滿足S Si i t 1）或互斥信號量）或互斥信號量（S=1）;(3) P(S,1,0)，這是一種很特殊且很有用的，這是一種很特殊且很有用的 信號量。當信號量。當S=1時，允

46、許多個進程進入時，允許多個進程進入 某特定區(qū)，當某特定區(qū)，當S變?yōu)樽優(yōu)?后，將阻止任何進后，將阻止任何進 程進入特定區(qū)。換言之，它相當于一個程進入特定區(qū)。換言之，它相當于一個 可控開關?？煽亻_關。2、管程、管程 信號量機制的一個特點是：在每個并發(fā)進程信號量機制的一個特點是：在每個并發(fā)進程中都要設置大量的同步操作原語，同步控制部分中都要設置大量的同步操作原語，同步控制部分分散在各個進程中。這不僅給編程帶來了麻煩，分散在各個進程中。這不僅給編程帶來了麻煩，而且如果而且如果P、V操作不當還可能會導致數(shù)據(jù)的不操作不當還可能會導致數(shù)據(jù)的不確定性和系統(tǒng)的死鎖。確定性和系統(tǒng)的死鎖。 Dijkstra認為應把

47、各進程中與同一共享數(shù)據(jù)認為應把各進程中與同一共享數(shù)據(jù)有關的同步控制和同步處理集中起來，構成獨立有關的同步控制和同步處理集中起來，構成獨立于進程的實體。系統(tǒng)中的各種硬件資源和軟件資于進程的實體。系統(tǒng)中的各種硬件資源和軟件資源均可用數(shù)據(jù)結構抽象地描述，既用少量信息和源均可用數(shù)據(jù)結構抽象地描述，既用少量信息和對該資源所執(zhí)行的操作來表征該資源，而忽略它對該資源所執(zhí)行的操作來表征該資源，而忽略它們的內(nèi)部結構和實現(xiàn)細節(jié)。當共享資源用共享數(shù)們的內(nèi)部結構和實現(xiàn)細節(jié)。當共享資源用共享數(shù)據(jù)來表示時，資源管理程序可以用對該數(shù)據(jù)結構據(jù)來表示時，資源管理程序可以用對該數(shù)據(jù)結構進行操作的一組過程來表示。我們把這樣一組相進

48、行操作的一組過程來表示。我們把這樣一組相關的數(shù)據(jù)結構和過程稱為管程。關的數(shù)據(jù)結構和過程稱為管程。 Hansen為管程下的定義是：一個管程定義了為管程下的定義是：一個管程定義了一個數(shù)據(jù)結構和能為并發(fā)進程所執(zhí)行的（在該數(shù)一個數(shù)據(jù)結構和能為并發(fā)進程所執(zhí)行的（在該數(shù)據(jù)結構上的）一組操作，這種操作能同步進程和據(jù)結構上的）一組操作，這種操作能同步進程和改變管程中的數(shù)據(jù)。改變管程中的數(shù)據(jù)。 管程的組成：管程的組成： 局部于管程的共享數(shù)據(jù)說明局部于管程的共享數(shù)據(jù)說明 對該數(shù)據(jù)結構進行操作的一組過程對該數(shù)據(jù)結構進行操作的一組過程 對局部于管程的數(shù)據(jù)的初始化語句對局部于管程的數(shù)據(jù)的初始化語句 在管程的實現(xiàn)中必須考

49、慮：在管程的實現(xiàn)中必須考慮：互斥互斥：當幾個進程調用管程時，僅允許一個進程：當幾個進程調用管程時，僅允許一個進程進入管程，其它調用者必須等待。進入管程，其它調用者必須等待。同步同步：在管程中必須設置兩個同步操作原語：在管程中必須設置兩個同步操作原語wait和和signal。當進程通過管程請求訪問某。當進程通過管程請求訪問某共享數(shù)據(jù)而未能滿足時，管程便調用共享數(shù)據(jù)而未能滿足時，管程便調用wait 原原語使該進程等待，并將它排在等待隊列上。語使該進程等待，并將它排在等待隊列上。僅當另一進程訪問完該共享資源且釋放后，僅當另一進程訪問完該共享資源且釋放后，管程又調用管程又調用signal原語，喚醒等待隊列中的原語，喚醒等待隊列中的隊首進程。隊首進程。條件變量條件變量：條件變量是用來區(qū)別不同的等待：條件變量是用來區(qū)別不同的等待原因，該條件變量應置于原因，該條件變量應置于wait和和signal之前。之前。操作操作共享數(shù)據(jù)共享數(shù)據(jù)初始化代碼初始化代碼XY入口隊列入口隊列.type