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

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

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

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

4、交互的并發(fā)進程來說，并發(fā)會破壞對于有交互的并發(fā)進程來說，并發(fā)會破壞“封封閉性閉性”和和“可再現(xiàn)性可再現(xiàn)性”例例1 ：車輛自動計數(shù)系統(tǒng)：車輛自動計數(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)計每小時的卡車流量統(tǒng)計每小時的卡車流量觀察者進程觀察者進程(Observer)：觀察到一輛卡車，計數(shù)器：觀察到一輛卡車，計數(shù)器+1報告者進程報告者進程(Reporter)

5、：每隔：每隔1小時，將計數(shù)值輸出，計數(shù)器清零小時，將計數(shù)值輸出，計數(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代表售票處理進程；代表售票處理進程；Ri是每個售票進程的私是每個售票進程的私有變量；有變量；各個售票處進程的工作各個售票處進程的工作如左邊代碼所示：如左邊代碼所示： 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為

10、5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為5，A、B兩個人同時在2號3號窗口買票 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è)某時刻Ak為1，兩個窗口同時賣票，可能出現(xiàn)什么情況？與時間有關(guān)的錯誤與時間有關(guān)的錯誤n由于進程交替修改了由于進程交替修改了共享變量共享變量造成結(jié)果可能不造成結(jié)果可能不正確。正確。n造成不正確的因素與進程占據(jù)處理器的時間、造成不正確的因素與進程占據(jù)處理器的時間、執(zhí)行速度以及外界的影響（卡車），這些因素執(zhí)行速度以及外界的影響（卡車），這些因素都與時間有關(guān)，所以稱為與時間有關(guān)的錯誤。都與時間有關(guān)，所以稱為與時間有關(guān)的錯誤。臨界區(qū)臨界區(qū)n有交互的并發(fā)進

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

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;如果能保證一個進程在臨界區(qū)執(zhí)行時，不讓另一個進程進入相關(guān)的臨界區(qū)執(zhí)行，即各進程對共享變量的訪問是互斥的，就不會造成與時間有關(guān)的錯誤。臨界區(qū)臨界區(qū)(1)當無進程在臨界區(qū)時，若有進程要進入，則當無進程在臨界區(qū)時，若有進程要進入，則允許一個進程進入臨界區(qū)

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

17、的概念n信號量信號量S是一個整數(shù)是一個整數(shù)S0 可供并發(fā)進程使用的資源實體數(shù)0 絕對值表示等待使用資源的進程數(shù)PV操作操作n對信號量的操作只能由對信號量的操作只能由P、V操作來進行，即：操作來進行，即： 信號量數(shù)值的改變只能由信號量數(shù)值的改變只能由P、V操作完成操作完成nPV操作由操作由P操作操作和和V操作操作組成，也稱組成，也稱P操作原語操作原語和和V操操作原語作原語。P操作操作nP(S) : 將信號量將信號量S減減1，若結(jié)果小于，若結(jié)果小于0，則把調(diào)用，則把調(diào)用P(S)的進程設(shè)置成等待信號量的進程設(shè)置成等待信號量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)的進程設(shè)置成等待信號量的進程設(shè)置成等待信號量S的狀態(tài)的狀態(tài)nV(S) : 將信號量將信號量S加加1，若不大于，若不大于0(小于等于小于等于0)，則釋放一個等待信號量則釋放一個等待信號量S的進程。的進程。 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計算機中，把可供多個進程使用的文件稱為計算機中，把可供多個進程使用的文件稱為共共享文件享文件。n想讀文件的進程稱為想讀文件的進程稱為讀進程讀進程，寫文件的進程稱，寫文件的進程稱為為寫進程寫進程。不允許多個進程同時使用共享文件不允許多個進程同時使用共享文件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個并發(fā)執(zhí)行的進程個并發(fā)執(zhí)行的進程A，B，C，D,它們在執(zhí)它們在執(zhí)行時都要讀共享文件行時都要讀共享文件F。限定：。限定：不允許不允許進程進程A和進程和進程B同時讀文件同時讀文件F，不允許不允許進程進程C和進程和進程D同時讀文件同時讀文件F。寫出用。寫出用PV操作管理時四個進程操作管理時四個進程的程序。的程序。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個個進程同時讀文件進程同時讀文件F，當同時，當同時讀文件讀文件F的進程不滿的進程不滿10個時，欲讀該文件的其他個時，欲讀該文件的其他進程可立即讀，當已有進程可立即讀，當已有10個進程在讀文件個進程在讀文件F時其時其他欲讀文件他欲讀文件F的進程必須等待，直至有進程讀完的進程必須等待

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

23、許任何進程去寫時，不允許任何進程去寫PV操作的實現(xiàn)思路：操作的實現(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 是第一個讀進程是第一個讀進程 then P(S); read file F; if 是最后一個完成的讀進程是最后一個完成的讀進程 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;進程的同步進程的同步記錄記錄進程進程B B進程進程A A緩沖區(qū)緩沖區(qū)存存取取加工加工假設(shè)緩沖區(qū)容量為假設(shè)緩沖區(qū)容量為1一個生產(chǎn)者進程，將數(shù)據(jù)存在緩沖區(qū)中；一個消費一個生產(chǎn)者進程，將數(shù)據(jù)存在緩沖區(qū)中；一個消費者進程，從緩沖區(qū)中取數(shù)據(jù)，要求兩者同步（即緩者進程，從緩沖區(qū)中取數(shù)據(jù)，要求兩者同步（即緩沖區(qū)空才

26、可以存，緩沖區(qū)滿才可以?。_區(qū)空才可以存，緩沖區(qū)滿才可以?。┯糜肞V操作實現(xiàn)進程的同步操作實現(xià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桌上只有一個盤子，一個盤子一次只能放一個桌上只有一個盤子，一個盤子一次只能放一個蘋果，爸爸向盤子里放蘋果，兒子從盤子里拿蘋果，爸爸向盤子里放蘋果，兒子從盤子里拿蘋果，用蘋果，用PV操作實現(xiàn)同步。操作實現(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操作實現(xiàn)售票員和司機的同步

28、操作實現(xiàn)售票員和司機的同步,假設(shè)初始狀假設(shè)初始狀態(tài)為車在始發(fā)站，要求態(tài)為車在始發(fā)站，要求售票員進程先開始執(zhí)行售票員進程先開始執(zhí)行process 售票員售票員開車門開車門關(guān)車門關(guān)車門售票售票process 司機司機啟動車輛啟動車輛 正常行車正常行車 到站停車到站停車begin S1，S2 : semaphore; /S1能否開門，能否開門，S2能否開車能否開車 S1 := 1; S2 := 0; cobegin: process 司機司機 begin L1: P(S2); 啟動車輛啟動車輛 正常行駛正常行駛 到站停車到站停車 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有三個并發(fā)進程有三個并發(fā)進程R、M、P，它們共享一個只能，它們共享一個只能存放一個記錄的緩沖區(qū)。存放一個記錄的緩沖區(qū)。R負責從輸入設(shè)備讀負責從輸入設(shè)備讀信息，每次讀一個記錄，存在緩沖區(qū)中。信息，每次讀一個記錄，存在緩沖區(qū)中。M對對緩沖區(qū)中的記錄加工，緩沖區(qū)中的記錄加工，P把加工后的記錄打印把加工后的記錄打印輸出。輸出。記錄經(jīng)加工并輸出后記錄經(jīng)加工并輸出后，緩沖區(qū)才能存放，緩沖區(qū)才能存放下一個記錄。寫出它們并發(fā)執(zhí)行時的程序。下一個記錄。寫出它們并發(fā)執(zhí)行時的程序。n

30、假設(shè)有三個進程假設(shè)有三個進程R，W1，W2共享一個緩沖區(qū)共享一個緩沖區(qū)B，又設(shè)，又設(shè)B中每次只能放一個數(shù)。中每次只能放一個數(shù)。n要求：要求：q緩沖區(qū)中無數(shù)時，緩沖區(qū)中無數(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: 讀入一個數(shù)讀入一個數(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ū)的進程同步多緩沖區(qū)的進程同步記錄記錄BA緩沖區(qū)緩沖區(qū)進程進程存存進程進程取取加工加工假設(shè)緩沖區(qū)容量為假設(shè)緩沖區(qū)容量為n，或者假設(shè)有，或者假設(shè)有n個緩沖區(qū)。個緩沖區(qū)。一個生產(chǎn)者進程，一個消費者進程，要求消費者一個生產(chǎn)者進程，一個消費者進程，要求消費者進程的處理順序與生產(chǎn)者進程的輸入的完全一樣進程的處理順序與生產(chǎ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某工廠有一個可以存放設(shè)備的倉庫，總共可以某工廠有一個可以存放設(shè)備的倉庫，總共可以存放存放8臺設(shè)備。臺設(shè)備。n生產(chǎn)部門生產(chǎn)的每一臺設(shè)備都必須入庫。生產(chǎn)部門生

34、產(chǎn)的每一臺設(shè)備都必須入庫。n銷售部門可以從倉庫中提出設(shè)備供應(yīng)客戶。銷售部門可以從倉庫中提出設(shè)備供應(yīng)客戶。n設(shè)備出設(shè)備出/入庫需要借助運輸工具，現(xiàn)入庫需要借助運輸工具，現(xiàn)只有一套只有一套運輸工具，每次只能運一臺設(shè)備運輸工具，每次只能運一臺設(shè)備n請設(shè)計一套能夠協(xié)調(diào)工作的自動調(diào)度系統(tǒng)。請設(shè)計一套能夠協(xié)調(diào)工作的自動調(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)一臺設(shè)備生產(chǎn)一臺設(shè)備 P(SP); P(S); 運送到倉庫；運送到倉庫； V(S) V(SG); goto L1

35、; end; coend:end;process 銷售銷售begin L1: P(SG); P(S); 從倉庫運出；從倉庫運出； V(S) V(SP); goto L1;end;nm個生產(chǎn)者和個生產(chǎn)者和r個消費者怎樣共享容量為個消費者怎樣共享容量為n的緩的緩沖區(qū)，每個生產(chǎn)者都要把生產(chǎn)的物品存入緩沖沖區(qū)，每個生產(chǎn)者都要把生產(chǎn)的物品存入緩沖區(qū)，每個消費者要從緩沖區(qū)中取物品區(qū)，每個消費者要從緩沖區(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桌上放一個盤子，每次只能放一個水果，爸爸桌上放一個盤子，每次只能放一個水果，爸爸像盤子里放蘋果，媽媽向盤子里放橘子，女兒像盤子里放蘋果，媽媽向盤子里放橘子，女兒專吃蘋果專吃蘋果,兒子專吃橘子。盤子空的時候爸爸兒子專吃橘子。盤子空的時候爸爸或媽媽才能向盤子里面放一個水果，僅當盤子或媽媽才能向盤子里面放一個水果，僅當盤子里有自己需要的水果時才可取一個水果。把爸里有自己需要的水果時才可取一個水果。把爸爸、媽媽、兒子、女兒看做四個進程，用爸、媽媽、兒子、女兒看做四個進程，用PV操作進行管理，使這四個進程能正確地并發(fā)執(zhí)操作進行管理，

38、使這四個進程能正確地并發(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，且任何時刻只允許爸，且任何時刻只允許爸爸、媽媽、女兒、兒子中的一個進程去訪問盤爸、媽媽、女兒、兒子中的一個進程去訪問盤子（放或者?。?。子（放或者?。?。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、個進程有三個進程A1、A2、A3，它們共享兩個緩沖區(qū)，它們共享兩個緩沖區(qū)B1和和B2。緩沖區(qū)緩沖區(qū)B1中可以存放中可以存放n件產(chǎn)品，緩沖區(qū)件產(chǎn)品，緩沖區(qū)B2中可以存放中可以存放m件件產(chǎn)品。進程產(chǎn)品。進程A1每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)B1。進程。進程A2每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)每次生產(chǎn)一件產(chǎn)品，并把產(chǎn)品存入緩沖區(qū)B2。進程進程A3每次從緩沖區(qū)每次從緩沖區(qū)B2中取一件產(chǎn)品區(qū)消費。為了防止中取一件產(chǎn)品區(qū)消費。為了防止把產(chǎn)品存入已滿的緩沖，或者從空緩沖中取產(chǎn)品，或重復把產(chǎn)品存入已滿的緩沖，或者從空緩沖中取產(chǎn)品，或重復取一產(chǎn)品，用取一產(chǎn)品，用PV

42、操作實現(xiàn)它們的相互制約關(guān)系。操作實現(xiàn)它們的相互制約關(guān)系。進程進程A1緩沖區(qū)緩沖區(qū)B1n緩沖區(qū)緩沖區(qū)B2m進程進程A2進程進程A3消費消費生產(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;進程通信進程通信n并發(fā)進程間可以通過并發(fā)進程間可以通過PV操作交換信息實現(xiàn)進程的操作交換信息實現(xiàn)進程的互斥和同步，因此可以把互斥和同步，因此可以把PV操作看做進程間的一操作看做進程間的一種通信方式，但這種通信只交換了少量的信息。種通信方式，但這種通信只交換了少量的信息。n如果進程間要交換大量信息，這種大量信息的傳如果進程間要交換大量信息，這種大量信息的傳遞要有專門的通信機制來實現(xiàn)，通過專門的通信遞要有專門的通信機制來實現(xiàn)，通過專門的通信機制實現(xiàn)進程間機制實現(xiàn)進程間大量信息大量信息的通信方式稱為的通信方式稱為進程通進程通信信。通信機制通信機制n采用高級通信方式時，進程

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

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

46、n通信時要遵循的規(guī)則：通信時要遵循的規(guī)則：q信箱滿時，把發(fā)送信件的進程信箱滿時，把發(fā)送信件的進程 置成置成”等信箱等信箱“，直到信箱有空，直到信箱有空 才被釋放才被釋放q若信箱無信，則把接收信件的若信箱無信，則把接收信件的 進程置成進程置成”等信件等信件“，直到信箱，直到信箱 有信件才釋放。有信件才釋放?？纱嫘偶?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); 釋放一個等信箱的進程釋放一個等信

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

50、 組織回信組織回信M ; sendname,M; goto L1；end;用進程通信實現(xiàn)進程同步用進程通信實現(xiàn)進程同步n用直接通信方式解決生產(chǎn)者用直接通信方式解決生產(chǎn)者/消費者問題消費者問題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中的進程同步中的進程同步nUNIX的進程在的進程在用戶態(tài)用戶態(tài)執(zhí)行

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

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

53、個字個字 節(jié)到管道文件節(jié)到管道文件read(fds0,buffer,6);/從管道文件中讀從管道文件中讀6個個 字節(jié)到字節(jié)到bufferUNIX中的進程通信中的進程通信管道機制管道機制n命名管道命名管道FIFOqFIFO適用于適用于不同用戶的進程不同用戶的進程間通信。間通信。q命名管道是一個命名管道是一個有文件名有文件名的管道文件。的管道文件。q用戶可以用用戶可以用shell命令命令mknod來創(chuàng)建一個管道文件，來創(chuàng)建一個管道文件，也可以在程序中使用也可以在程序中使用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個字節(jié)到管道文件個字節(jié)到管道文件fd = open(“fifo”,”O(jiān)_RDONLY”);/已只讀方式打開已只讀方式打開read(fd,buffer,6);/從管道里讀從管道里讀6個字節(jié)到個字節(jié)到bufferUNIX中的進程通信中的進程通信消息緩沖機制消息緩沖機制n利用緩沖區(qū)來傳輸消息，