自考操作系統(tǒng)原理 第七章 進(jìn)程同步與進(jìn)程通信.

1、進(jìn)程同步與進(jìn)程通信進(jìn)程同步與進(jìn)程通信進(jìn)程的順序性進(jìn)程的順序性n進(jìn)程的進(jìn)程的順序性順序性是指進(jìn)程在順序處理器上的執(zhí)行是是指進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的，即按照程序規(guī)定的操作順序，只有嚴(yán)格按序的，即按照程序規(guī)定的操作順序，只有在前一個(gè)操作結(jié)束后才能開始后繼操作。在前一個(gè)操作結(jié)束后才能開始后繼操作。n當(dāng)一個(gè)進(jìn)程當(dāng)一個(gè)進(jìn)程獨(dú)占獨(dú)占處理器時(shí)，它具有兩個(gè)特性：處理器時(shí)，它具有兩個(gè)特性：q封閉性封閉性q可再現(xiàn)性可再現(xiàn)性進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性n每一個(gè)進(jìn)程具有順序性，但是在多道程序設(shè)計(jì)系每一個(gè)進(jìn)程具有順序性，但是在多道程序設(shè)計(jì)系統(tǒng)中，多個(gè)進(jìn)程要統(tǒng)中，多個(gè)進(jìn)程要競爭競爭，輪流占用輪流占用處理器。處理器。

2、n有兩個(gè)進(jìn)程有兩個(gè)進(jìn)程A和和B，它們各自順序執(zhí)行時(shí)的操作序，它們各自順序執(zhí)行時(shí)的操作序列如下：列如下：q進(jìn)程進(jìn)程A ： a1，a2，a3，amq進(jìn)程進(jìn)程B ： b1，b2，b3，bmn在多道程序設(shè)計(jì)系統(tǒng)中，處理器可能執(zhí)行的操作在多道程序設(shè)計(jì)系統(tǒng)中，處理器可能執(zhí)行的操作序列序列qa1， b1 ，a2， b2 ，a3， b3 qa1， a2， b1 ，a3 ，b2 ，b3 進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性n在一個(gè)進(jìn)程的工作沒有完成之前，另一個(gè)進(jìn)程在一個(gè)進(jìn)程的工作沒有完成之前，另一個(gè)進(jìn)程就可以開始工作，這些進(jìn)程就稱為就可以開始工作，這些進(jìn)程就稱為可同時(shí)執(zhí)行可同時(shí)執(zhí)行的的?；蛘叻Q它們?；蛘叻Q它們具有并發(fā)性具有

3、并發(fā)性，并且把可同時(shí)執(zhí)，并且把可同時(shí)執(zhí)行的進(jìn)程稱為行的進(jìn)程稱為并發(fā)進(jìn)程并發(fā)進(jìn)程。進(jìn)程的并發(fā)性進(jìn)程的并發(fā)性n如果一個(gè)進(jìn)程的執(zhí)行不影響另一個(gè)進(jìn)程的執(zhí)行結(jié)如果一個(gè)進(jìn)程的執(zhí)行不影響另一個(gè)進(jìn)程的執(zhí)行結(jié)果，也不依賴一個(gè)進(jìn)程的進(jìn)展情況，即它們是各果，也不依賴一個(gè)進(jìn)程的進(jìn)展情況，即它們是各自獨(dú)立的，則稱這些進(jìn)程相互之間是自獨(dú)立的，則稱這些進(jìn)程相互之間是無關(guān)無關(guān)的。的。n如果一個(gè)進(jìn)程的執(zhí)行要依賴其他進(jìn)程的進(jìn)展?fàn)顩r，如果一個(gè)進(jìn)程的執(zhí)行要依賴其他進(jìn)程的進(jìn)展?fàn)顩r，或者可能會(huì)影響其他進(jìn)程的執(zhí)行結(jié)果，則說這些或者可能會(huì)影響其他進(jìn)程的執(zhí)行結(jié)果，則說這些進(jìn)程是進(jìn)程是有交互有交互的。的。與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤n對(duì)于有

4、交互的并發(fā)進(jìn)程來說，并發(fā)會(huì)破壞對(duì)于有交互的并發(fā)進(jìn)程來說，并發(fā)會(huì)破壞“封封閉性閉性”和和“可再現(xiàn)性可再現(xiàn)性”例例1 ：車輛自動(dòng)計(jì)數(shù)系統(tǒng)：車輛自動(dòng)計(jì)數(shù)系統(tǒng) process Observer begin L1:observe a lorry; count: = count + 1; goto L1;end; process Reporter begin print count; count := 0;end;系統(tǒng)功能：系統(tǒng)功能： 統(tǒng)計(jì)每小時(shí)的卡車流量統(tǒng)計(jì)每小時(shí)的卡車流量觀察者進(jìn)程觀察者進(jìn)程(Observer)：觀察到一輛卡車，計(jì)數(shù)器：觀察到一輛卡車，計(jì)數(shù)器+1報(bào)告者進(jìn)程報(bào)告者進(jìn)程(Reporter)

5、：每隔：每隔1小時(shí)，將計(jì)數(shù)值輸出，計(jì)數(shù)器清零小時(shí)，將計(jì)數(shù)值輸出，計(jì)數(shù)器清零例例2：航班售票系統(tǒng)：航班售票系統(tǒng) process Pi (i=1,2,) begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ak代表某天某次航班的代表某天某次航班的剩余票數(shù)；剩余票數(shù)；Pi代表售票處理進(jìn)程；代表售票處理進(jìn)程；Ri是每個(gè)售票進(jìn)程的私是每個(gè)售票進(jìn)程的私有變量；有變量；各個(gè)售票處進(jìn)程的工作各個(gè)售票處進(jìn)程的工作如左邊代碼所示：如左邊代碼所示： process P2 begi

6、n Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ri = 5假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P2 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張

7、票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ri = 5假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P2 beg

8、in Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ri = 5假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P2 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一

9、張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ri = 5假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P2 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ri = 4假設(shè)某時(shí)刻Ak為

10、5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P2 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ak = 4假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P2 begin Ri:=Ak; if Ri=1

11、then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ri = 4假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else

12、 輸出輸出”票已售完票已售完“ end; process P2 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;Ak = 4假設(shè)某時(shí)刻Ak為5，A、B兩個(gè)人同時(shí)在2號(hào)3號(hào)窗口買票 process P3 begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end; process P2 begin Ri:=Ak; if Ri=1

13、 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;假設(shè)某時(shí)刻Ak為1，兩個(gè)窗口同時(shí)賣票，可能出現(xiàn)什么情況？與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤n由于進(jìn)程交替修改了由于進(jìn)程交替修改了共享變量共享變量造成結(jié)果可能不造成結(jié)果可能不正確。正確。n造成不正確的因素與進(jìn)程占據(jù)處理器的時(shí)間、造成不正確的因素與進(jìn)程占據(jù)處理器的時(shí)間、執(zhí)行速度以及外界的影響（卡車），這些因素執(zhí)行速度以及外界的影響（卡車），這些因素都與時(shí)間有關(guān)，所以稱為與時(shí)間有關(guān)的錯(cuò)誤。都與時(shí)間有關(guān)，所以稱為與時(shí)間有關(guān)的錯(cuò)誤。臨界區(qū)臨界區(qū)n有交互的并發(fā)進(jìn)

14、程執(zhí)行時(shí)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)有交互的并發(fā)進(jìn)程執(zhí)行時(shí)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤，誤，其根本原因是對(duì)共享資源（變量）的使用其根本原因是對(duì)共享資源（變量）的使用不受限不受限，為了使并發(fā)進(jìn)程能正確地執(zhí)行，必須，為了使并發(fā)進(jìn)程能正確地執(zhí)行，必須對(duì)對(duì)共享變量的使用加以限制共享變量的使用加以限制。 process Observer begin L1:observe a lorry; count: = count + 1; goto L1;end;臨界區(qū)臨界區(qū) process Reporter begin print count; count := 0;end;把并發(fā)進(jìn)程中與共享變量有關(guān)的程序段稱為把并發(fā)進(jìn)程中與共享

15、變量有關(guān)的程序段稱為臨界區(qū)臨界區(qū)。涉及相同共享變量的臨界區(qū)稱為涉及相同共享變量的臨界區(qū)稱為相關(guān)臨界區(qū)相關(guān)臨界區(qū)。臨界區(qū)臨界區(qū) process Pi(i=1,2) begin Ri:=Ak; if Ri=1 then begin Ri:= Ri -1; Ak = Ri 輸出一張票；輸出一張票； end; else 輸出輸出”票已售完票已售完“ end;如果能保證一個(gè)進(jìn)程在臨界區(qū)執(zhí)行時(shí)，不讓另一個(gè)進(jìn)程進(jìn)入相關(guān)的臨界區(qū)執(zhí)行，即各進(jìn)程對(duì)共享變量的訪問是互斥的，就不會(huì)造成與時(shí)間有關(guān)的錯(cuò)誤。臨界區(qū)臨界區(qū)(1)當(dāng)無進(jìn)程在臨界區(qū)時(shí)，若有進(jìn)程要進(jìn)入，則當(dāng)無進(jìn)程在臨界區(qū)時(shí)，若有進(jìn)程要進(jìn)入，則允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)

16、允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)(2)當(dāng)有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，其他試圖進(jìn)入臨當(dāng)有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待界區(qū)的進(jìn)程必須等待(3)當(dāng)有一個(gè)進(jìn)程離開臨界區(qū)，若有等待進(jìn)入臨當(dāng)有一個(gè)進(jìn)程離開臨界區(qū)，若有等待進(jìn)入臨界區(qū)的進(jìn)程，則允許一個(gè)進(jìn)程進(jìn)入它的臨界界區(qū)的進(jìn)程，則允許一個(gè)進(jìn)程進(jìn)入它的臨界區(qū)區(qū)信號(hào)量機(jī)制（信號(hào)量機(jī)制（Semaphores）n1965年，荷蘭的年，荷蘭的 E.W.Dijkstra (狄克斯特拉狄克斯特拉)提出了信號(hào)量同步機(jī)制。提出了信號(hào)量同步機(jī)制。n用于進(jìn)程同步用于進(jìn)程同步n廣泛應(yīng)用于存在臨界資源和臨界區(qū)控制的場合廣泛應(yīng)用于存在臨界資源和臨界區(qū)控制的場合信號(hào)量的概念信號(hào)量

17、的概念n信號(hào)量信號(hào)量S是一個(gè)整數(shù)是一個(gè)整數(shù)S0 可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)0 絕對(duì)值表示等待使用資源的進(jìn)程數(shù)PV操作操作n對(duì)信號(hào)量的操作只能由對(duì)信號(hào)量的操作只能由P、V操作來進(jìn)行，即：操作來進(jìn)行，即： 信號(hào)量數(shù)值的改變只能由信號(hào)量數(shù)值的改變只能由P、V操作完成操作完成nPV操作由操作由P操作操作和和V操作操作組成，也稱組成，也稱P操作原語操作原語和和V操操作原語作原語。P操作操作nP(S) : 將信號(hào)量將信號(hào)量S減減1，若結(jié)果小于，若結(jié)果小于0，則把調(diào)用，則把調(diào)用P(S)的進(jìn)程設(shè)置成等待信號(hào)量的進(jìn)程設(shè)置成等待信號(hào)量S的狀態(tài)的狀態(tài) Procedure P (Var S : Semaphore)

18、; begin S := S-1; if S0 then W(s) end; P W(s)表示把調(diào)用表示把調(diào)用P(S)的進(jìn)程設(shè)置成等待信號(hào)量的進(jìn)程設(shè)置成等待信號(hào)量S的狀態(tài)的狀態(tài)nV(S) : 將信號(hào)量將信號(hào)量S加加1，若不大于，若不大于0(小于等于小于等于0)，則釋放一個(gè)等待信號(hào)量則釋放一個(gè)等待信號(hào)量S的進(jìn)程。的進(jìn)程。 Procedure V (Var S : Semaphore); begin S := S+1; if S=1 then begin Ri:= Ri -1; Ak = Ri V(S); 輸出一張票；輸出一張票； end; else begin V(S); 輸出輸出”票已售完票已

19、售完“ end; coend:end;讀者讀者/寫者問題寫者問題n計(jì)算機(jī)中，把可供多個(gè)進(jìn)程使用的文件稱為計(jì)算機(jī)中，把可供多個(gè)進(jìn)程使用的文件稱為共共享文件享文件。n想讀文件的進(jìn)程稱為想讀文件的進(jìn)程稱為讀進(jìn)程讀進(jìn)程，寫文件的進(jìn)程稱，寫文件的進(jìn)程稱為為寫進(jìn)程寫進(jìn)程。不允許多個(gè)進(jìn)程同時(shí)使用共享文件不允許多個(gè)進(jìn)程同時(shí)使用共享文件begin S : semaphore; S := 1; cobegin process Readeri(i=1,2,3) begin P(S); read file F; V(S); end; process Writerj(j=1,2,3) begin P(S); write

20、 file F; V(S); end; coend:end;P226 12n有有4個(gè)并發(fā)執(zhí)行的進(jìn)程個(gè)并發(fā)執(zhí)行的進(jìn)程A，B，C，D,它們?cè)趫?zhí)它們?cè)趫?zhí)行時(shí)都要讀共享文件行時(shí)都要讀共享文件F。限定：。限定：不允許不允許進(jìn)程進(jìn)程A和進(jìn)程和進(jìn)程B同時(shí)讀文件同時(shí)讀文件F，不允許不允許進(jìn)程進(jìn)程C和進(jìn)程和進(jìn)程D同時(shí)讀文件同時(shí)讀文件F。寫出用。寫出用PV操作管理時(shí)四個(gè)進(jìn)程操作管理時(shí)四個(gè)進(jìn)程的程序。的程序。begin S1,S2 : semaphore; S1 := 1; S2 :=1; cobegin process A begin P(S1); read file F; V(S1); end; process

21、 B begin P(S1); read file F; V(S1); end; coend:end;process Dbegin P(S2); read file F; V(S2);end; process C begin P(S2); read file F; V(S2); end;某系統(tǒng)允許某系統(tǒng)允許最多最多10個(gè)個(gè)進(jìn)程同時(shí)讀文件進(jìn)程同時(shí)讀文件F，當(dāng)同時(shí)，當(dāng)同時(shí)讀文件讀文件F的進(jìn)程不滿的進(jìn)程不滿10個(gè)時(shí)，欲讀該文件的其他個(gè)時(shí)，欲讀該文件的其他進(jìn)程可立即讀，當(dāng)已有進(jìn)程可立即讀，當(dāng)已有10個(gè)進(jìn)程在讀文件個(gè)進(jìn)程在讀文件F時(shí)其時(shí)其他欲讀文件他欲讀文件F的進(jìn)程必須等待，直至有進(jìn)程讀完的進(jìn)程必須等待

22、，直至有進(jìn)程讀完后退出方可去讀后退出方可去讀, 寫出進(jìn)程并發(fā)執(zhí)行時(shí)的程序。寫出進(jìn)程并發(fā)執(zhí)行時(shí)的程序。begin S ：semaphore; S := 10; cobegin process Readeri(i=1,2,3) begin P(S); read file F; V(s); end; coend:end;允許多個(gè)進(jìn)程同時(shí)使用共享文件允許多個(gè)進(jìn)程同時(shí)使用共享文件要求：要求： (1) 多個(gè)進(jìn)程可以同時(shí)讀文件多個(gè)進(jìn)程可以同時(shí)讀文件F (2) 任何一個(gè)進(jìn)程在對(duì)文件任何一個(gè)進(jìn)程在對(duì)文件F進(jìn)行寫時(shí)，不允許其他進(jìn)程讀或?qū)戇M(jìn)行寫時(shí)，不允許其他進(jìn)程讀或?qū)?(3) 有進(jìn)程在讀文件有進(jìn)程在讀文件F時(shí)，不允

23、許任何進(jìn)程去寫時(shí)，不允許任何進(jìn)程去寫PV操作的實(shí)現(xiàn)思路：操作的實(shí)現(xiàn)思路：process Writeri(i=1,2,3)begin P(S); write file F; V(S);end; process Readeri(i=1,2,3.)begin if 是第一個(gè)讀進(jìn)程是第一個(gè)讀進(jìn)程 then P(S); read file F; if 是最后一個(gè)完成的讀進(jìn)程是最后一個(gè)完成的讀進(jìn)程 then V(S);end; begin S : semaphore; S = 1; rc : integer; rc = 0; cobegin: process Readeri(i=1,2,3) begin

24、rc := rc + 1; if rc=1 then P(S); read file F; rc := rc-1; if rc=0 then V(S) end; coend:end; process writerj(j=1,2) begin P(S); write file F; V(S);end;begin S，mutex : semaphore; S := 1; mutex :=1; rc : integer; rc := 0; cobegin: process Readeri(i=1,2,3) begin P(mutex); rc := rc + 1; if rc=1 then P(S)

25、; V(mutex); read file F; P(mutex); rc := rc-1; if rc=0 then V(S) V(mutex); end; coend:End;process writerj(j=1,2,3)begin P(S); write file F; V(S);end;進(jìn)程的同步進(jìn)程的同步記錄記錄進(jìn)程進(jìn)程B B進(jìn)程進(jìn)程A A緩沖區(qū)緩沖區(qū)存存取取加工加工假設(shè)緩沖區(qū)容量為假設(shè)緩沖區(qū)容量為1一個(gè)生產(chǎn)者進(jìn)程，將數(shù)據(jù)存在緩沖區(qū)中；一個(gè)消費(fèi)一個(gè)生產(chǎn)者進(jìn)程，將數(shù)據(jù)存在緩沖區(qū)中；一個(gè)消費(fèi)者進(jìn)程，從緩沖區(qū)中取數(shù)據(jù)，要求兩者同步（即緩者進(jìn)程，從緩沖區(qū)中取數(shù)據(jù)，要求兩者同步（即緩沖區(qū)空才

26、可以存，緩沖區(qū)滿才可以?。_區(qū)空才可以存，緩沖區(qū)滿才可以?。┯糜肞V操作實(shí)現(xiàn)進(jìn)程的同步操作實(shí)現(xiàn)進(jìn)程的同步begin SP，SG : semaphore; SP := 1; SG :=0; Buffer： integer; cobegin: process producer begin L1: produce a product P(SP); buffer : = product; V(SG); goto L1; end; coend:End;process consumerbegin L2: P(SG); take a product; V(SP); Consume; goto L2;end;

27、n桌上只有一個(gè)盤子，一個(gè)盤子一次只能放一個(gè)桌上只有一個(gè)盤子，一個(gè)盤子一次只能放一個(gè)蘋果，爸爸向盤子里放蘋果，兒子從盤子里拿蘋果，爸爸向盤子里放蘋果，兒子從盤子里拿蘋果，用蘋果，用PV操作實(shí)現(xiàn)同步。操作實(shí)現(xiàn)同步。begin S1，S2 : semaphore; S1 := 1; S2 :=0; cobegin: process 爸爸爸爸 begin L1: P(S1); 放蘋果放蘋果 V(S2); goto L1; end; process 兒子兒子 begin L2: P(S2); 拿蘋果拿蘋果 V(S1); goto L2; end; coend:end;n用用PV操作實(shí)現(xiàn)售票員和司機(jī)的同步

28、操作實(shí)現(xiàn)售票員和司機(jī)的同步,假設(shè)初始狀假設(shè)初始狀態(tài)為車在始發(fā)站，要求態(tài)為車在始發(fā)站，要求售票員進(jìn)程先開始執(zhí)行售票員進(jìn)程先開始執(zhí)行process 售票員售票員開車門開車門關(guān)車門關(guān)車門售票售票process 司機(jī)司機(jī)啟動(dòng)車輛啟動(dòng)車輛 正常行車正常行車 到站停車到站停車begin S1，S2 : semaphore; /S1能否開門，能否開門，S2能否開車能否開車 S1 := 1; S2 := 0; cobegin: process 司機(jī)司機(jī) begin L1: P(S2); 啟動(dòng)車輛啟動(dòng)車輛 正常行駛正常行駛 到站停車到站停車 V(S1); goto L1; end; coend:End;proc

29、ess 售票員售票員begin L2:P(S1); 開門開門 關(guān)門關(guān)門 V(S2); 售票售票 goto L2;end;P225 7n有三個(gè)并發(fā)進(jìn)程有三個(gè)并發(fā)進(jìn)程R、M、P，它們共享一個(gè)只能，它們共享一個(gè)只能存放一個(gè)記錄的緩沖區(qū)。存放一個(gè)記錄的緩沖區(qū)。R負(fù)責(zé)從輸入設(shè)備讀負(fù)責(zé)從輸入設(shè)備讀信息，每次讀一個(gè)記錄，存在緩沖區(qū)中。信息，每次讀一個(gè)記錄，存在緩沖區(qū)中。M對(duì)對(duì)緩沖區(qū)中的記錄加工，緩沖區(qū)中的記錄加工，P把加工后的記錄打印把加工后的記錄打印輸出。輸出。記錄經(jīng)加工并輸出后記錄經(jīng)加工并輸出后，緩沖區(qū)才能存放，緩沖區(qū)才能存放下一個(gè)記錄。寫出它們并發(fā)執(zhí)行時(shí)的程序。下一個(gè)記錄。寫出它們并發(fā)執(zhí)行時(shí)的程序。n

30、假設(shè)有三個(gè)進(jìn)程假設(shè)有三個(gè)進(jìn)程R，W1，W2共享一個(gè)緩沖區(qū)共享一個(gè)緩沖區(qū)B，又設(shè)，又設(shè)B中每次只能放一個(gè)數(shù)。中每次只能放一個(gè)數(shù)。n要求：要求：q緩沖區(qū)中無數(shù)時(shí)，緩沖區(qū)中無數(shù)時(shí)，R可以從設(shè)備讀數(shù)存到緩沖可以從設(shè)備讀數(shù)存到緩沖q若存到緩沖中的數(shù)是奇數(shù)，允許若存到緩沖中的數(shù)是奇數(shù)，允許W1將其取出打印將其取出打印q若存到緩沖中的數(shù)是偶數(shù)，允許若存到緩沖中的數(shù)是偶數(shù)，允許W2將其取出打印將其取出打印qR必須等緩沖區(qū)空才能放，必須等緩沖區(qū)空才能放，W1，W2不能從空緩沖不能從空緩沖區(qū)中取數(shù)。區(qū)中取數(shù)。begin SP，SG1,SG2 : semaphore; SP := 1; SG1 :=0; SG2:=

31、0; Buffer： integer; cobegin: process R begin L1: 讀入一個(gè)數(shù)讀入一個(gè)數(shù)number P(SP); buffer : = number; if buffer mod 2 0 then V(SG1) else then V(SG2) goto L1; end; coend:end;process W1begin L2: P(SG1); y:=buffer; V(SP); print y; goto L2;end;process W2begin L3: P(SG2); z:=buffer; V(SP); print z; goto L3;end;多緩沖

32、區(qū)的進(jìn)程同步多緩沖區(qū)的進(jìn)程同步記錄記錄BA緩沖區(qū)緩沖區(qū)進(jìn)程進(jìn)程存存進(jìn)程進(jìn)程取取加工加工假設(shè)緩沖區(qū)容量為假設(shè)緩沖區(qū)容量為n，或者假設(shè)有，或者假設(shè)有n個(gè)緩沖區(qū)。個(gè)緩沖區(qū)。一個(gè)生產(chǎn)者進(jìn)程，一個(gè)消費(fèi)者進(jìn)程，要求消費(fèi)者一個(gè)生產(chǎn)者進(jìn)程，一個(gè)消費(fèi)者進(jìn)程，要求消費(fèi)者進(jìn)程的處理順序與生產(chǎn)者進(jìn)程的輸入的完全一樣進(jìn)程的處理順序與生產(chǎn)者進(jìn)程的輸入的完全一樣begin buffer: array0,n-1 of integer k,t: integer; k:=0;t:=0; SP，SG : semaphore; SP := n; SG :=0; cobegin: process producer begin L1:

33、produce a product P(SP); bufferk : = product; k = (k+1) mod n; V(SG); goto L1; end; coend:end;process consumerbegin L2: P(SG); take a product from buffert; t:= (t+1) mod n; V(SP); Consume; goto L2; end;同步與互斥的混合問題同步與互斥的混合問題n某工廠有一個(gè)可以存放設(shè)備的倉庫，總共可以某工廠有一個(gè)可以存放設(shè)備的倉庫，總共可以存放存放8臺(tái)設(shè)備。臺(tái)設(shè)備。n生產(chǎn)部門生產(chǎn)的每一臺(tái)設(shè)備都必須入庫。生產(chǎn)部門生

34、產(chǎn)的每一臺(tái)設(shè)備都必須入庫。n銷售部門可以從倉庫中提出設(shè)備供應(yīng)客戶。銷售部門可以從倉庫中提出設(shè)備供應(yīng)客戶。n設(shè)備出設(shè)備出/入庫需要借助運(yùn)輸工具，現(xiàn)入庫需要借助運(yùn)輸工具，現(xiàn)只有一套只有一套運(yùn)輸工具，每次只能運(yùn)一臺(tái)設(shè)備運(yùn)輸工具，每次只能運(yùn)一臺(tái)設(shè)備n請(qǐng)?jiān)O(shè)計(jì)一套能夠協(xié)調(diào)工作的自動(dòng)調(diào)度系統(tǒng)。請(qǐng)?jiān)O(shè)計(jì)一套能夠協(xié)調(diào)工作的自動(dòng)調(diào)度系統(tǒng)。begin S，SP,SG : semaphore; S := 1; SP := 8; SG :=0 cobegin: process 生產(chǎn)生產(chǎn) begin L1: 生產(chǎn)一臺(tái)設(shè)備生產(chǎn)一臺(tái)設(shè)備 P(SP); P(S); 運(yùn)送到倉庫；運(yùn)送到倉庫； V(S) V(SG); goto L1

35、; end; coend:end;process 銷售銷售begin L1: P(SG); P(S); 從倉庫運(yùn)出；從倉庫運(yùn)出； V(S) V(SP); goto L1;end;nm個(gè)生產(chǎn)者和個(gè)生產(chǎn)者和r個(gè)消費(fèi)者怎樣共享容量為個(gè)消費(fèi)者怎樣共享容量為n的緩的緩沖區(qū)，每個(gè)生產(chǎn)者都要把生產(chǎn)的物品存入緩沖沖區(qū)，每個(gè)生產(chǎn)者都要把生產(chǎn)的物品存入緩沖區(qū)，每個(gè)消費(fèi)者要從緩沖區(qū)中取物品區(qū)，每個(gè)消費(fèi)者要從緩沖區(qū)中取物品begin buffer: array0,n-1 of integer k,t: integer; k:=0;t:=0; SP，SG ,mutex1，mutex2: semaphore; SP :=

36、 n; SG :=0; mutex1 := 1 ，mutex2 := 1； cobegin: process produceri(i=1,2.) begin L1: produce a product P(SP); P(mutex1) bufferk : = product; k = (k+1) mod n; V(mutex1) V(SG); goto L1; end; coend:end;process consumeri（i=1,2.）begin L2: P(SG); P(mutex2); take a product from buffert; t:= (t+1) mod n; V(mu

37、tex2) V(SP); Consume; goto L2; end;n桌上放一個(gè)盤子，每次只能放一個(gè)水果，爸爸桌上放一個(gè)盤子，每次只能放一個(gè)水果，爸爸像盤子里放蘋果，媽媽向盤子里放橘子，女兒像盤子里放蘋果，媽媽向盤子里放橘子，女兒專吃蘋果專吃蘋果,兒子專吃橘子。盤子空的時(shí)候爸爸兒子專吃橘子。盤子空的時(shí)候爸爸或媽媽才能向盤子里面放一個(gè)水果，僅當(dāng)盤子或媽媽才能向盤子里面放一個(gè)水果，僅當(dāng)盤子里有自己需要的水果時(shí)才可取一個(gè)水果。把爸里有自己需要的水果時(shí)才可取一個(gè)水果。把爸爸、媽媽、兒子、女兒看做四個(gè)進(jìn)程，用爸、媽媽、兒子、女兒看做四個(gè)進(jìn)程，用PV操作進(jìn)行管理，使這四個(gè)進(jìn)程能正確地并發(fā)執(zhí)操作進(jìn)行管理，

38、使這四個(gè)進(jìn)程能正確地并發(fā)執(zhí)行。行。begin mutex ,SA，SO : semaphore; mutex := 1; SA :=0; SO := 0; cobegin: process 爸爸爸爸 begin L1: P(mutex); 放蘋果放蘋果 V(SA); goto L1; end; process 媽媽媽媽 begin L2: P(mutex); 放橘子放橘子 V(SO); goto L2; end; coend:end;process 兒子兒子begin L4: P(SO); 拿橘子拿橘子 V(mutex); goto L4;end;process 女兒女兒begin L3: P

39、(SA); 拿蘋果拿蘋果 V(mutex); goto L3;end;P225 8n如果盤子的容量改為如果盤子的容量改為2，且任何時(shí)刻只允許爸，且任何時(shí)刻只允許爸爸、媽媽、女兒、兒子中的一個(gè)進(jìn)程去訪問盤爸、媽媽、女兒、兒子中的一個(gè)進(jìn)程去訪問盤子（放或者?。?。子（放或者?。?。begin mutex1, mutex2,SA，SO : semaphore; mutex1 := 2; mutex2 := 1; SA :=0; SO := 0; cobegin: process 爸爸爸爸 begin L1: P(mutex1);/盤子盤子 P(mutex2);/伸手伸手 放蘋果放蘋果 V(mutex2)

40、; V(SA); goto L1; end; process 媽媽媽媽 begin L2: P(mutex1);/盤子盤子 P(mutex2);/伸手伸手 放橘子放橘子 V(mutex2); V(SO); goto L2; end; coend:end;process 女兒女兒begin L3: P(SA); P(mutex2);/伸手伸手 拿蘋果拿蘋果 V(mutex2) V(mutex1); goto L3;end;process 兒子兒子begin L4: P(SO); P(mutex2);/伸手伸手 拿橘子拿橘子 V(mutex2) V(mutex1); goto L4;end;n有三

41、個(gè)進(jìn)程有三個(gè)進(jìn)程A1、A2、A3，它們共享兩個(gè)緩沖區(qū)，它們共享兩個(gè)緩沖區(qū)B1和和B2。緩沖區(qū)緩沖區(qū)B1中可以存放中可以存放n件產(chǎn)品，緩沖區(qū)件產(chǎn)品，緩沖區(qū)B2中可以存放中可以存放m件件產(chǎn)品。進(jìn)程產(chǎn)品。進(jìn)程A1每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)B1。進(jìn)程。進(jìn)程A2每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)B2。進(jìn)程進(jìn)程A3每次從緩沖區(qū)每次從緩沖區(qū)B2中取一件產(chǎn)品區(qū)消費(fèi)。為了防止中取一件產(chǎn)品區(qū)消費(fèi)。為了防止把產(chǎn)品存入已滿的緩沖，或者從空緩沖中取產(chǎn)品，或重復(fù)把產(chǎn)品存入已滿的緩沖，或者從空緩沖中取產(chǎn)品，或重復(fù)取一產(chǎn)品，用取一產(chǎn)品，用PV

42、操作實(shí)現(xiàn)它們的相互制約關(guān)系。操作實(shí)現(xiàn)它們的相互制約關(guān)系。進(jìn)程進(jìn)程A1緩沖區(qū)緩沖區(qū)B1n緩沖區(qū)緩沖區(qū)B2m進(jìn)程進(jìn)程A2進(jìn)程進(jìn)程A3消費(fèi)消費(fèi)生產(chǎn)生產(chǎn)Begin B1，B2: array0,n-1 of integer k1,k2，t1，t2: integer; k1:=0; k1:=0; t1:=0; SP，SG : semaphore; SP = n; SG =0; cobegin: process producer begin L1: produce a product P(SP); bufferk : = product; k = (k+1) mod n; V(SG); goto L1; e

43、nd; coend:End;進(jìn)程通信進(jìn)程通信n并發(fā)進(jìn)程間可以通過并發(fā)進(jìn)程間可以通過PV操作交換信息實(shí)現(xiàn)進(jìn)程的操作交換信息實(shí)現(xiàn)進(jìn)程的互斥和同步，因此可以把互斥和同步，因此可以把PV操作看做進(jìn)程間的一操作看做進(jìn)程間的一種通信方式，但這種通信只交換了少量的信息。種通信方式，但這種通信只交換了少量的信息。n如果進(jìn)程間要交換大量信息，這種大量信息的傳如果進(jìn)程間要交換大量信息，這種大量信息的傳遞要有專門的通信機(jī)制來實(shí)現(xiàn)，通過專門的通信遞要有專門的通信機(jī)制來實(shí)現(xiàn)，通過專門的通信機(jī)制實(shí)現(xiàn)進(jìn)程間機(jī)制實(shí)現(xiàn)進(jìn)程間大量信息大量信息的通信方式稱為的通信方式稱為進(jìn)程通進(jìn)程通信信。通信機(jī)制通信機(jī)制n采用高級(jí)通信方式時(shí)，進(jìn)程

44、間用采用高級(jí)通信方式時(shí)，進(jìn)程間用信件信件來交換信來交換信息。息。n信件：信件： 信件內(nèi)容包括發(fā)送者名、信息信件內(nèi)容包括發(fā)送者名、信息(信息存信息存放的地址和長度放的地址和長度)、等、等/不等回信，回信存放地不等回信，回信存放地址。址。n通信方式：信件的傳遞是由通信原語完成的，通信方式：信件的傳遞是由通信原語完成的，最基本的原語是兩條：最基本的原語是兩條：發(fā)送發(fā)送(send)原語原語和和接收接收(receive)原語原語。通信方式通信方式n直接通信方式直接通信方式q這種通信方式總是固定在一對(duì)進(jìn)程之間進(jìn)行這種通信方式總是固定在一對(duì)進(jìn)程之間進(jìn)行 send(B,M) 把信件把信件M發(fā)送給發(fā)送給BABr

45、eceive(A,X)接受來自進(jìn)程接受來自進(jìn)程A的信件存入的信件存入X中中通信方式通信方式n間接通信間接通信q這種通信方式總是這種通信方式總是信箱信箱為媒體來實(shí)現(xiàn)通信的，接受為媒體來實(shí)現(xiàn)通信的，接受進(jìn)程設(shè)立一個(gè)信箱，任何要向該進(jìn)程發(fā)信的進(jìn)程總進(jìn)程設(shè)立一個(gè)信箱，任何要向該進(jìn)程發(fā)信的進(jìn)程總是把信件發(fā)送到該進(jìn)程的信箱里是把信件發(fā)送到該進(jìn)程的信箱里AB信箱Nsend(N,M) 把信件把信件M送入信箱送入信箱N中中receive(N,X) 從信箱從信箱N中取出一封信存入中取出一封信存入X取發(fā)間接通信的實(shí)現(xiàn)間接通信的實(shí)現(xiàn)n間接通信指的是進(jìn)程之間間接通信指的是進(jìn)程之間利用信箱利用信箱來交換信息。來交換信息。

46、n通信時(shí)要遵循的規(guī)則：通信時(shí)要遵循的規(guī)則：q信箱滿時(shí)，把發(fā)送信件的進(jìn)程信箱滿時(shí)，把發(fā)送信件的進(jìn)程 置成置成”等信箱等信箱“，直到信箱有空，直到信箱有空 才被釋放才被釋放q若信箱無信，則把接收信件的若信箱無信，則把接收信件的 進(jìn)程置成進(jìn)程置成”等信件等信件“，直到信箱，直到信箱 有信件才釋放。有信件才釋放。可存信件數(shù)已有信件數(shù)可存信件的指針信件1信件2取信件信箱說明信箱的數(shù)據(jù)結(jié)構(gòu)定義信箱的數(shù)據(jù)結(jié)構(gòu)定義nTYPE box = record size : 0.n; 信箱大小信箱大小 count : 0.n ; 現(xiàn)有信件數(shù)現(xiàn)有信件數(shù) letter : array1.n of message; 信件信件

47、 S1,S2 : semaphore; end;send原語過程原語過程procedure send(var B:box; M:message)var i : integer;begin if B.count = B.size then W(B.S1) 如果信箱滿，等信箱如果信箱滿，等信箱 else begin i:= B.count + 1; 確定可存放信件的位置確定可存放信件的位置 B.letteri = M; 信件存放到信箱指定位置信件存放到信箱指定位置 B.count := i; 信箱的信件數(shù)信箱的信件數(shù)+1 R(B.S2); 釋放等信件者釋放等信件者 end;end;sendrece

48、ive原語過程原語過程procedure receive(var B:box; M:message)var i : integer;begin if B.count = 0 then W(B.S2) 如果信箱無信，等信件如果信箱無信，等信件 else begin X := B.letter1; 總是取第一封信總是取第一封信 B.count := B.count - 1; 信件數(shù)信件數(shù)-1 if B.count 0 then for i=1 to B.count do B.letteri := B.letteri+1; 所有信件上移所有信件上移 R(B.S1); 釋放一個(gè)等信箱的進(jìn)程釋放一個(gè)等信

49、箱的進(jìn)程 end;end;receive進(jìn)程通信示意進(jìn)程通信示意組織信件組織信件Msend(B,M).receive(A,Y)receive(B,X)處理信件處理信件M組織回信組織回信Nsend(A,N)信件信件M信件信件NB進(jìn)程信箱進(jìn)程信箱A進(jìn)程信箱進(jìn)程信箱A進(jìn)程進(jìn)程B進(jìn)程進(jìn)程磁盤管理磁盤管理欲訪問磁盤的進(jìn)程欲訪問磁盤的進(jìn)程begin 組織信件組織信件M ; sendB,M; end;磁盤管理進(jìn)程磁盤管理進(jìn)程L1: receive(B,X) 按信件要求組織通道程序按信件要求組織通道程序 ; 通道程序首址存入通道程序首址存入CAW ; 啟動(dòng)磁盤啟動(dòng)磁盤 ; 等待磁盤傳輸結(jié)束等待磁盤傳輸結(jié)束 ;

50、 組織回信組織回信M ; sendname,M; goto L1；end;用進(jìn)程通信實(shí)現(xiàn)進(jìn)程同步用進(jìn)程通信實(shí)現(xiàn)進(jìn)程同步n用直接通信方式解決生產(chǎn)者用直接通信方式解決生產(chǎn)者/消費(fèi)者問題消費(fèi)者問題cobegin: process producer begin L1: 生產(chǎn)物品生產(chǎn)物品 組織信件組織信件M send（consumer,M） goto L1; end;cobegin: process consumer begin L2: receive(producer,X) 處理處理X中的信件中的信件 goto L2; end;UNIX中的進(jìn)程同步中的進(jìn)程同步nUNIX的進(jìn)程在的進(jìn)程在用戶態(tài)用戶態(tài)執(zhí)行

51、時(shí)，使用執(zhí)行時(shí)，使用wait系統(tǒng)系統(tǒng)調(diào)用讓自己等待，子進(jìn)程執(zhí)行完畢，用系統(tǒng)調(diào)調(diào)用讓自己等待，子進(jìn)程執(zhí)行完畢，用系統(tǒng)調(diào)用用exit來終止自己。來終止自己。nUNIX的進(jìn)程在的進(jìn)程在核心態(tài)核心態(tài)執(zhí)行時(shí)，使用執(zhí)行時(shí)，使用sleep系系統(tǒng)調(diào)用讓進(jìn)程進(jìn)入睡眠態(tài)，使用統(tǒng)調(diào)用讓進(jìn)程進(jìn)入睡眠態(tài)，使用wakeup來喚來喚醒進(jìn)程。醒進(jìn)程。UNIX中的進(jìn)程通信中的進(jìn)程通信管道機(jī)制管道機(jī)制nUNIX中的管道通信機(jī)制允許進(jìn)程按中的管道通信機(jī)制允許進(jìn)程按先進(jìn)先出先進(jìn)先出的方法傳送的方法傳送信息。信息。n無名管道無名管道pipeq無名管道無名管道pipe適用于一個(gè)用戶有適用于一個(gè)用戶有同一祖先的父子進(jìn)程同一祖先的父子進(jìn)程間

52、的通信。間的通信。q無名管道就是一個(gè)進(jìn)程間的共享文件，稱為無名管道就是一個(gè)進(jìn)程間的共享文件，稱為pipe文件文件q一個(gè)進(jìn)程調(diào)用一個(gè)進(jìn)程調(diào)用pipe系統(tǒng)調(diào)用來建立一個(gè)無名管道（系統(tǒng)調(diào)用來建立一個(gè)無名管道（pipe文件），其文件），其子進(jìn)程可以與該進(jìn)程共享該管道，對(duì)子進(jìn)程可以與該進(jìn)程共享該管道，對(duì)pipe文件進(jìn)行讀寫。文件進(jìn)行讀寫。進(jìn)程P1進(jìn)程P2P1 | P2無名管道無名管道int fds2;char buffer1024 = ;pipe(fds); /fds0用于讀管道文件，用于讀管道文件， fds1用于寫管道文件用于寫管道文件write(fds1,buffer,6);/從從buffer寫寫6

53、個(gè)字個(gè)字 節(jié)到管道文件節(jié)到管道文件read(fds0,buffer,6);/從管道文件中讀從管道文件中讀6個(gè)個(gè) 字節(jié)到字節(jié)到bufferUNIX中的進(jìn)程通信中的進(jìn)程通信管道機(jī)制管道機(jī)制n命名管道命名管道FIFOqFIFO適用于適用于不同用戶的進(jìn)程不同用戶的進(jìn)程間通信。間通信。q命名管道是一個(gè)命名管道是一個(gè)有文件名有文件名的管道文件。的管道文件。q用戶可以用用戶可以用shell命令命令mknod來創(chuàng)建一個(gè)管道文件，來創(chuàng)建一個(gè)管道文件，也可以在程序中使用也可以在程序中使用mknod調(diào)用來創(chuàng)建。調(diào)用來創(chuàng)建。q使用方式同普通文件使用方式同普通文件命名管道命名管道FIFOchar string = “hello”;char buffer256;mknod(“fifo”,010777,0);/已可讀可寫方式創(chuàng)建管道文件已可讀可寫方式創(chuàng)建管道文件fifoint fd = open(“fifo”,”O(jiān)_WRONLY”);/已只寫方式打開已只寫方式打開write(fd,string,6);/從從string寫寫6個(gè)字節(jié)到管道文件個(gè)字節(jié)到管道文件fd = open(“fifo”,”O(jiān)_RDONLY”);/已只讀方式打開已只讀方式打開read(fd,buffer,6);/從管道里讀從管道里讀6個(gè)字節(jié)到個(gè)字節(jié)到bufferUNIX中的進(jìn)程通信中的進(jìn)程通信消息緩沖機(jī)制消息緩沖機(jī)制n利用緩沖區(qū)來傳輸消息，