第3章 進程的同步與通信

1、lChap.3 進程的同步與通信進程的同步與通信1 1、如何控制和協(xié)調(diào)并發(fā)進程異步執(zhí)行、如何控制和協(xié)調(diào)并發(fā)進程異步執(zhí)行 的時序？的時序？ 2 2、進程之間如何互相聯(lián)系，傳遞信息？、進程之間如何互相聯(lián)系，傳遞信息？ 本章討論的主要問題本章討論的主要問題3.1 3.1 進程間的相互作用進程間的相互作用n進程間的聯(lián)系進程間的聯(lián)系n進程的同步機制進程的同步機制信號量及信號量及P.VP.V操操作（解決進程同步互斥問題）作（解決進程同步互斥問題）1.1.進程間的聯(lián)系進程間的聯(lián)系相交進程與無關(guān)進程相交進程與無關(guān)進程相交進程：指多個并發(fā)進程在邏輯上有相交進程：指多個并發(fā)進程在邏輯上有某種聯(lián)系某種聯(lián)系無關(guān)進程（

2、不相交進程）：在邏輯上無無關(guān)進程（不相交進程）：在邏輯上無任何聯(lián)系的進程任何聯(lián)系的進程直接作用和間接作用直接作用和間接作用直接作用：直接作用：進程間的相互聯(lián)系是進程間的相互聯(lián)系是有意識的安排的有意識的安排的，直接作用只發(fā)生在相交進程間直接作用只發(fā)生在相交進程間間接作用：間接作用：進程間要通過進程間要通過某種中介某種中介發(fā)生聯(lián)系，是無發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相交進程之間，意識安排的，可發(fā)生在相交進程之間，也可發(fā)生在無關(guān)進程之間也可發(fā)生在無關(guān)進程之間進程的同步（直接作用）進程的同步（直接作用）進程的同步：進程的同步：synchronism指系統(tǒng)中多個進程中發(fā)生的事件存在某種指系統(tǒng)中多個進

3、程中發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項時序關(guān)系，需要相互合作，共同完成一項任務(wù)。任務(wù)。具體說，一個進程運行到某一點時具體說，一個進程運行到某一點時要求另一伙伴進程為它提供消息，在未獲要求另一伙伴進程為它提供消息，在未獲得消息之前，該進程處于等待狀態(tài)，獲得得消息之前，該進程處于等待狀態(tài)，獲得消息后被喚醒進入就緒態(tài)消息后被喚醒進入就緒態(tài)同步問題同步問題1nA race between two or more teams, in which each team member runs only a set part of the race and is then relieved

4、 by another member of the team.緩沖區(qū)鍵盤鍵盤計算計算緩沖區(qū)緩沖區(qū)緩沖區(qū)B進程A進程 A A進程只有當緩沖區(qū)為空時，才能將數(shù)據(jù)輸入緩沖區(qū)，進程只有當緩沖區(qū)為空時，才能將數(shù)據(jù)輸入緩沖區(qū)， B B進程只有當緩沖區(qū)有數(shù)據(jù)時，才能從緩沖區(qū)取數(shù)進行計算。進程只有當緩沖區(qū)有數(shù)據(jù)時，才能從緩沖區(qū)取數(shù)進行計算。 進程的同步與互斥雖然是兩個既有區(qū)別又有聯(lián)系的概念，進程的同步與互斥雖然是兩個既有區(qū)別又有聯(lián)系的概念，但從本質(zhì)上看并發(fā)進程的異步執(zhí)行都必須按一定的相互約束但從本質(zhì)上看并發(fā)進程的異步執(zhí)行都必須按一定的相互約束的時序進行，因此統(tǒng)稱為的時序進行，因此統(tǒng)稱為“進程同步進程同步”。

5、顯然，必須解決好進程的同步問題，才能保證并發(fā)進程顯然，必須解決好進程的同步問題，才能保證并發(fā)進程的正常執(zhí)行。的正常執(zhí)行。同步問題同步問題2進程的互斥（間接作用）進程的互斥（間接作用）由于各進程要求共享資源，而有些資源需由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這要互斥使用，因此各進程間競爭使用這些資源，進程的這種關(guān)系為進程的互斥些資源，進程的這種關(guān)系為進程的互斥臨界資源：臨界資源：critical resource 系統(tǒng)中某些資源一次只允許一個進程使系統(tǒng)中某些資源一次只允許一個進程使用，稱這樣的資源為臨界資源或互斥資用，稱這樣的資源為臨界資源或互斥資源或共享變量源或共

6、享變量臨界區(qū)（互斥區(qū)）：臨界區(qū)（互斥區(qū)）：critical section一個程序片段的集合，這些程序片段分散一個程序片段的集合，這些程序片段分散在不同的進程中，對某個共享的數(shù)據(jù)結(jié)在不同的進程中，對某個共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進行操作構(gòu)（共享資源）進行操作 在進程中涉及到臨界資源的程序段叫在進程中涉及到臨界資源的程序段叫臨臨界區(qū)界區(qū) 多個進程的臨界區(qū)稱為多個進程的臨界區(qū)稱為相關(guān)臨界區(qū)相關(guān)臨界區(qū) 每個進程每個進程 互斥訪問互斥訪問臨界資源臨界資源的那段代碼稱為的那段代碼稱為臨界區(qū)臨界區(qū)。代。代碼構(gòu)成如下碼構(gòu)成如下： repeatrepeat entry section entry sectio

7、n 進入?yún)^(qū)進入?yún)^(qū) 申請進入臨界區(qū)申請進入臨界區(qū) critical section critical section 臨界區(qū)臨界區(qū) 訪問臨界資源訪問臨界資源 exit section exit section 退出區(qū)退出區(qū) 退出對臨界資源的訪退出對臨界資源的訪問問 remainder section remainder section 剩留區(qū)剩留區(qū) 進程的其他代碼進程的其他代碼 until false until false 1 1。什么是臨界資源。什么是臨界資源 凡是以互斥方式使用的共享資源都稱為臨界資源。臨界凡是以互斥方式使用的共享資源都稱為臨界資源。臨界資源具有一次只允許一個進程使用的屬性

8、資源具有一次只允許一個進程使用的屬性。2 2。臨界區(qū)。臨界區(qū) （critical section）使用互斥區(qū)的原則使用互斥區(qū)的原則有空讓進：有空讓進：當無進程在互斥區(qū)時，任何有權(quán)使用當無進程在互斥區(qū)時，任何有權(quán)使用互斥區(qū)的進程可進入互斥區(qū)的進程可進入無空等待：無空等待：不允許兩個以上的進程同時進入互斥不允許兩個以上的進程同時進入互斥區(qū)區(qū)多中擇一：多中擇一：當沒有進程在臨界區(qū)，而同時有多個當沒有進程在臨界區(qū)，而同時有多個進程要求進入臨界區(qū)，只能讓其中之一進入臨進程要求進入臨界區(qū)，只能讓其中之一進入臨界區(qū)，其他進程必須等待界區(qū)，其他進程必須等待有限等待：有限等待：任何進入互斥區(qū)的要求應(yīng)在有限的時任

9、何進入互斥區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足間內(nèi)得到滿足讓權(quán)等待：讓權(quán)等待：處于等待狀態(tài)的進程應(yīng)放棄占用處于等待狀態(tài)的進程應(yīng)放棄占用CPUCPU，以使其他進程有機會得到以使其他進程有機會得到CPUCPU的使用權(quán)的使用權(quán)前提：任何進程無權(quán)停止其它進程的運行前提：任何進程無權(quán)停止其它進程的運行 進程之間相對運行速度無硬性規(guī)定進程之間相對運行速度無硬性規(guī)定進程互斥的解決有兩種做法進程互斥的解決有兩種做法: :n由競爭各方平等協(xié)商由競爭各方平等協(xié)商n引入進程管理者，由管理者來協(xié)調(diào)競爭引入進程管理者，由管理者來協(xié)調(diào)競爭各方對互斥資源的使用各方對互斥資源的使用具體方法：具體方法：n硬件硬件n軟件軟件使用互斥

10、區(qū)的原則（續(xù)）使用互斥區(qū)的原則（續(xù)）軟件解法軟件解法 (1)(1)free: free: 表示臨界區(qū)標志表示臨界區(qū)標志 true: true: 有進程在臨界區(qū)有進程在臨界區(qū) false:false:無進程在臨界區(qū)無進程在臨界區(qū)( (初值初值) ) . . while (free); while (free); free = true; free = true; 臨界區(qū)臨界區(qū) free = false;free = false;空循環(huán)空循環(huán)軟件解法軟件解法 (2)(2)turn: true turn: true P P進入臨界區(qū)進入臨界區(qū) false false Q Q進入臨界區(qū)進入臨界區(qū) .P

11、: while (not turn);P: while (not turn); 臨界區(qū)臨界區(qū) turn = true;turn = true;Q: while (turn);Q: while (turn); 臨界區(qū)臨界區(qū) turn = false;turn = false;軟件解法的缺點：軟件解法的缺點： 1. 1. 忙等待忙等待 2. 2. 實現(xiàn)過于復(fù)雜，需要高的編程技巧實現(xiàn)過于復(fù)雜，需要高的編程技巧硬件解法：提供專門的硬件指令，允許對一個字的硬件解法：提供專門的硬件指令，允許對一個字的內(nèi)容進行檢測和修正，或交換兩個字的內(nèi)容內(nèi)容進行檢測和修正，或交換兩個字的內(nèi)容目的：解決共享變量的目的：解決

12、共享變量的完整性和正確性完整性和正確性 簡單、有效，特別簡單、有效，特別適用于多處理機適用于多處理機缺點：忙等待缺點：忙等待硬件解法硬件解法 (1)(1) “測試并設(shè)置測試并設(shè)置”指令指令 TSTS指令執(zhí)行過程不可分割。指令執(zhí)行過程不可分割。 為臨界資源設(shè)置一個布爾量為臨界資源設(shè)置一個布爾量 LOCKLOCK：實現(xiàn)的基本思想是：對實現(xiàn)的基本思想是：對臨界資源臨界資源“加鎖加鎖” 進程的同步機制可以用軟件實現(xiàn)，也可以用硬件實現(xiàn)。進程的同步機制可以用軟件實現(xiàn)，也可以用硬件實現(xiàn)。（1 1）用）用T TestandestandS Set et 指令實現(xiàn)互斥指令實現(xiàn)互斥LOCK LOCK = false

13、 false 沒有進程在臨界區(qū)沒有進程在臨界區(qū)true true 有進程進入臨界區(qū)有進程進入臨界區(qū) TSTS指令的形式指令的形式： function function tsts（varvar lock lock：booleanboolean）：）：booleanboolean； begin begin tsts：=lock=lock； locklock：=true=true； endend；以兩進程以兩進程P1P1、P2P2并發(fā)執(zhí)行為例，如果并發(fā)執(zhí)行為例，如果P1P1先執(zhí)行：先執(zhí)行：若若P1P1先進入臨界區(qū)，則先進入臨界區(qū)，則P2P2循環(huán)執(zhí)行循環(huán)執(zhí)行TSTS指令，直到指令，直到P1P1退出臨界

14、區(qū)。退出臨界區(qū)。調(diào)用TS指令p1TS=true進入P1臨界區(qū)Lock：=false進入剩余區(qū)調(diào)用TS指令p2TS=true進入P2臨界區(qū)Lock：=false進入剩余區(qū)進入剩余區(qū)調(diào)用調(diào)用TS指令指令TS=trueNY進入進入P1臨界區(qū)臨界區(qū)調(diào)用TS指令TS=trueYN調(diào)用TS指令調(diào)用調(diào)用TS指令指令TS=trueTS=trueLock：=false進入進入P2臨界區(qū)臨界區(qū)進入剩余區(qū)進入剩余區(qū) 如果如果P2P2先執(zhí)行：若先執(zhí)行：若P2P2先進入臨界區(qū)，則先進入臨界區(qū)，則P1P1循環(huán)執(zhí)行循環(huán)執(zhí)行TSTS指令，直指令，直到到P2P2退出臨界區(qū)。退出臨界區(qū)。 結(jié)論：結(jié)論： TSTS指令有效實現(xiàn)互斥（

15、空閑讓進、忙則等待）指令有效實現(xiàn)互斥（空閑讓進、忙則等待） 循環(huán)測試，處于循環(huán)測試，處于“忙等待忙等待”（未讓權(quán)等待）（未讓權(quán)等待）調(diào)用TS指令p2TS=true進入P1臨界區(qū)Lock：=false進入剩余區(qū)調(diào)用調(diào)用TS指令指令TS=trueNY進入進入P2臨界區(qū)臨界區(qū)Lock：=false進入剩余區(qū)進入剩余區(qū)調(diào)用TS指令p1TS=true進入P2臨界區(qū)Lock：=false進入剩余區(qū)進入剩余區(qū)調(diào)用TS指令TS=trueYN調(diào)用TS指令調(diào)用調(diào)用TS指令指令TS=trueTS=true進入進入P1臨界區(qū)臨界區(qū)Lock：=false進入剩余區(qū)進入剩余區(qū)2.2.進程的同步機制進程的同步機制信號量及信

16、號量及P.VP.V操作操作 以上介紹的各種算法都存在問題，它們是以上介紹的各種算法都存在問題，它們是平平等進程等進程間的一種間的一種協(xié)商機制協(xié)商機制，需要一個地位高，需要一個地位高于進程的于進程的管理者管理者來解決公有資源的使用問題來解決公有資源的使用問題 操作系統(tǒng)操作系統(tǒng)可從進程管理者的角度來處理互斥可從進程管理者的角度來處理互斥的問題，的問題，信號量信號量就是操作系統(tǒng)提供的管理公就是操作系統(tǒng)提供的管理公有資源的有效手段有資源的有效手段進程的同步機制（續(xù)）進程的同步機制（續(xù)）同步機制：同步機制： 信號量信號量及及P P、V V操作；管程；操作；管程；條件臨條件臨界域；路徑表達式等（用于集中式

17、系界域；路徑表達式等（用于集中式系統(tǒng)中）統(tǒng)中）同步機制應(yīng)滿足的基本要求：同步機制應(yīng)滿足的基本要求：* * 描述能力描述能力* * 可以實現(xiàn)可以實現(xiàn)* * 效率高效率高* * 使用方便使用方便n1965年，由荷蘭學(xué)者年，由荷蘭學(xué)者Dijkstra提出（所以提出（所以P、V分別是荷蘭語的分別是荷蘭語的test(proberen)和和increment(verhogen)）n一種卓有成效的進程同步機制一種卓有成效的進程同步機制n最初提出的是二元信號量（互斥）最初提出的是二元信號量（互斥） 推廣到一般信號量（多值）（同步）推廣到一般信號量（多值）（同步）n廣泛應(yīng)用于存在臨界資源和臨界區(qū)控制廣泛應(yīng)用于存

18、在臨界資源和臨界區(qū)控制的場合的場合信號量及信號量及P、V操作操作Semaphores (proposed by Dijkstra in 1965)nWhat a Semaphore is?nAn integer variablenRepresent the number of resources available (when it is greater than or equals to 0)nRepresent the number of processes waiting for the resources( when it is less than 0)nOperations on a

19、 semaphorenInitializationnP operation - to testnV operation - to increment信號量：信號量：semaphoresemaphoren是一個數(shù)據(jù)結(jié)構(gòu)是一個數(shù)據(jù)結(jié)構(gòu)n定義如下：定義如下： strucstruc semaphore semaphore intint value; value;pointer_PCB queue;pointer_PCB queue; n信號量說明：信號量說明： semaphore s;semaphore s; S.value ：= S.Value + 1； 若 S.Value 0 進程繼續(xù)執(zhí)行。 若

20、S.Value 0 則釋放S等待隊列中的一個進程 ， 使之轉(zhuǎn)為就緒狀態(tài)。P P、V V操作原語操作原語 定義：定義：VARVAR S S：SemaphoreSemaphore； 1 1。P P操作（操作（wait wait 原語）原語） 每作一次每作一次P P操作，申請分配一個單位的資源。操作，申請分配一個單位的資源。 P P（S S） 對信號量對信號量S S 進行進行P P操作。操作。 2 2。V V操作（操作（SignalSignal原語）原語） V V（S S） 對信號量對信號量S S 進行進行V V操作，釋放一個單位的資源。操作，釋放一個單位的資源。 S.value ：= S.Valu

21、e - 1； 若若 S.Value 0 進程繼續(xù)執(zhí)行。進程繼續(xù)執(zhí)行。 若若 S.Value 0 0 時，其值表示某類資源可用數(shù)量。時，其值表示某類資源可用數(shù)量。 S.ValueS.Value 0 0 時，其絕對值表示在信號量隊列中等待時，其絕對值表示在信號量隊列中等待 該資源的進程數(shù)。該資源的進程數(shù)。 P P、V V操作有嚴格的不可分割性；執(zhí)行過程不允許中斷；操作有嚴格的不可分割性；執(zhí)行過程不允許中斷； P P、V V操作成對出現(xiàn)。操作成對出現(xiàn)。 （根據(jù)同步機制的原則，分析P、V操作的特點，）？問題？問題？如何使用如何使用P P、V V操作實現(xiàn)同步機制？操作實現(xiàn)同步機制？ 考慮：考慮： 如何控

22、制互斥地使用臨界資源？如何控制互斥地使用臨界資源？ 如何控制進程并發(fā)執(zhí)行的時序？如何控制進程并發(fā)執(zhí)行的時序？實現(xiàn)同步機制實現(xiàn)同步機制基本思想是：加基本思想是：加鎖、解鎖鎖、解鎖Another Meaning from SemaphorenP to request resourcesnV to release resources1、利用信號量實現(xiàn)進程互斥、利用信號量實現(xiàn)進程互斥n共享某個公有資源共享某個公有資源 定義一個互斥信號量，初定義一個互斥信號量，初值為值為1P(S)V(S)臨界區(qū)Mutual Exclusion Achieved by Using Semaphoreshared sema

23、phore S = 1;/P(S);/ Critical SectionV(S);The Bounded-Buffer Problem 1PAPAPBPBbuf設(shè) mutex 公共互斥信號量 初值：mutex.Value = 1利用P、V操作實現(xiàn)互斥的模型實現(xiàn)進程互斥實現(xiàn)進程互斥 以兩個進程并發(fā)執(zhí)行為例以兩個進程并發(fā)執(zhí)行為例進程進程P1P1.P P（mutexmutex）；）；進入進入P1P1臨界區(qū)；臨界區(qū)；V V（mutexmutex）；）；.值值0 0 進程進程P2P2.P P（mutexmutex）；）； 進入進入P2P2臨界區(qū)；臨界區(qū)； V（mutex）；）；.值值0 0 值值-1-1

24、 進程進程P1P1先執(zhí)行先執(zhí)行 P P（mutexmutex）；）；進程進程P1P1進入臨界區(qū)；進入臨界區(qū)； 進程進程P2P2開始執(zhí)行開始執(zhí)行 P P（mutexmutex）；）；進程進程P2P2阻塞，插入阻塞隊列。阻塞，插入阻塞隊列。 若進程若進程P1P1再次執(zhí)行再次執(zhí)行 V V（mutexmutex）；）；mutex.Valuemutex.Value=0 =0 釋放資源。釋放資源。 2、實現(xiàn)進程間的同步、實現(xiàn)進程間的同步nPA：需要空緩沖區(qū)資源，該資源由需要空緩沖區(qū)資源，該資源由PB取取數(shù)后產(chǎn)生，空緩沖區(qū)資源用信號量數(shù)后產(chǎn)生，空緩沖區(qū)資源用信號量Sempty表示表示nPB：需要滿緩沖區(qū)資源

25、，該資源由需要滿緩沖區(qū)資源，該資源由PA送送數(shù)后產(chǎn)生，滿緩沖區(qū)資源用信號量數(shù)后產(chǎn)生，滿緩沖區(qū)資源用信號量Sfull表表示示PAPAPBPBbuf實現(xiàn)進程間的同步實現(xiàn)進程間的同步PA:P(Sempty);V(Sfull);Goto PA;PB:P(Sfull);V(Sempty);Goto PB;Shared Semaphore Sempty := 1Shared Semaphore Sfull := 0 分析：打印進程與計算進程之間有兩個約束： 1）計算進程只有當緩沖區(qū)為空時，才能放入計算結(jié)果。 2）打印進程只有當緩沖區(qū)有結(jié)果時，才能從緩沖區(qū)取 計算結(jié)果打印。定義兩個信號量：Sempty、 S

26、full ，用于控制這兩個約束：Sfull 控制打印進程從緩沖區(qū)取計算結(jié)果打印。Sempty 控制計算進程向緩沖區(qū)送計算結(jié)果。2 2、實現(xiàn)進程同步、實現(xiàn)進程同步 實例：實例： 打印進程與計算進程的同步問題。打印進程與計算進程的同步問題。緩沖區(qū)計算計算打印機打印機緩沖區(qū)緩沖區(qū)緩沖區(qū)打印打印進程進程計算進程計算進程SfullSempty設(shè)：設(shè)： Sempty 初值為初值為1 1 Sfull初值為初值為0 0 表示緩沖區(qū)為空。表示緩沖區(qū)為空。 當當 Sfull 0 0 表示可以打印表示可以打印 當當 Sempty 0 0 表示可以表示可以放入計算結(jié)果。放入計算結(jié)果。信號量機制的基本原理信號量機制的基

27、本原理n兩個或兩個或多個進程可以通過簡單的信號進行合作，一多個進程可以通過簡單的信號進行合作，一個進程被迫在某個指定位置停止，直到它收到一個個進程被迫在某個指定位置停止，直到它收到一個特定的信號才繼續(xù)。特定的信號才繼續(xù)。n通過合適的信號結(jié)構(gòu)可以滿足任何復(fù)雜的協(xié)作要求。通過合適的信號結(jié)構(gòu)可以滿足任何復(fù)雜的協(xié)作要求。n為了發(fā)信號，使用特殊的變量為了發(fā)信號，使用特殊的變量信號量。信號量。n進程執(zhí)行原語進程執(zhí)行原語 signal(S) / V(S)發(fā)出信號，通過執(zhí)行發(fā)出信號，通過執(zhí)行 wait(S) / P(S)接收信號；如果沒有相應(yīng)的信號到達，接收信號；如果沒有相應(yīng)的信號到達，該進程將被掛起直到所需

28、信號到達。該進程將被掛起直到所需信號到達。Another Meaning from SemaphorenP wait nTo wait for a signalnV signal nTo give a signal to somebody.The Bounded-Buffer Problem 2PAPAPBPBbufbufbuf.bufThe buffer is finite and consists of a linear array of elementsQ: How to describe ? Mutual Exclusion Needed!Synchronization Between

29、 Producer and ConsumernProducer:repeatproduce P(Sempty); V(Sfull);forevernConsumer:repeat P(Sfull); V(Sempty);consumeforeverSempty, Sfull : Semaphore;Sempty := n;Sfull := 0;Classical Synchronization Problemsn生產(chǎn)者生產(chǎn)者消費者問題消費者問題( the Producer-Consumer Problem )n讀者與寫者問題讀者與寫者問題( the Readers and Writers Pr

30、oblem )經(jīng)典的生產(chǎn)者經(jīng)典的生產(chǎn)者消費者問題消費者問題消費者消費者生產(chǎn)者生產(chǎn)者生產(chǎn)者生產(chǎn)者消費者問題分析消費者問題分析n生產(chǎn)者與消費者間的同步關(guān)系生產(chǎn)者與消費者間的同步關(guān)系n生產(chǎn)者之間互斥訪問緩沖區(qū)生產(chǎn)者之間互斥訪問緩沖區(qū)n消費者之間互斥訪問緩沖區(qū)消費者之間互斥訪問緩沖區(qū)n生產(chǎn)者與消費者之間互斥訪問緩沖區(qū)生產(chǎn)者與消費者之間互斥訪問緩沖區(qū) P P進程不能往進程不能往“滿滿”的緩沖區(qū)中放產(chǎn)品，的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為設(shè)置信號量為Sempty Q Q進程不能從進程不能從“空空”的緩沖區(qū)中取產(chǎn)品，的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量設(shè)置信號量Sfull Synchronization Between

31、 Producer and ConsumernProducer:repeatproduce P(Sempty);V(Sfull);forevernConsumer:repeat P(Sfull);V(Sempty);consumeforeverSempty, Sfull : Semaphore;Sempty := n;Sfull := 0;.PQ放 消 息取 消 息nn個 緩 沖 區(qū)(Buffer)ijMutual Exclusion Among Producers/ConsumersnProducer:RepeatproduceP(mutex);V(mutex);forevernConsum

32、er:repeatP(mutex);V(mutex);consumeforevermutex: Semaphore;mutex := 1;A Solution to the Bounded-Buffer Producer/Consumer ProblemSemaphores:Sempty: Semaphore := n;Sfull: Semaphore := 0;Mutex: Semaphore := 1;A Solution to the Bounded-Buffer Producer/Consumer ProblemnProducer:RepeatproduceP(Sempty);P(mu

33、tex);V(Sfull);V(mutex);forevernConsumer:repeatP(Sfull);P(mutex);V(Sempty);V(mutex);consumeforeverV操作出現(xiàn)的次序能否顛倒？P操作出現(xiàn)的次序能否顛倒？得出結(jié)論：得出結(jié)論：生產(chǎn)一種產(chǎn)品P（S n）V（S 0)V(S)P（S ）產(chǎn)品送入緩沖區(qū)P(S0)P(S)V(S)消耗該產(chǎn)品從緩沖區(qū)取一產(chǎn)品V(Sn)生產(chǎn)者消費者ProducerConsumerProblem 1n桌上有一空盤，只允許放入一個水果。桌上有一空盤，只允許放入一個水果。爸爸專向盤中放蘋果，媽媽專向盤中入爸爸專向盤中放蘋果，媽媽專向盤中入桔子

34、，女兒專等吃盤中的蘋果，兒子專桔子，女兒專等吃盤中的蘋果，兒子專等吃盤中的桔子。試用等吃盤中的桔子。試用P、V原語實現(xiàn)爸原語實現(xiàn)爸爸、媽媽、兒子和女兒間能同步的程序。爸、媽媽、兒子和女兒間能同步的程序。 The Readers / Writers Problem There is a data area shared among a number of processes. The data area could be a file, a block of main memory, or even a bank of processor registers. There are a numbe

35、r of processes that only read the data area(readers) and a number that only write to the data area(writers).The Readers / Writers ProblemThe following conditions must be satisfied:1.Any number of reader may simultaneously read the file.2.Only one writer at a time may write to the file.3.If a writer

36、is writing to the file, no reader may read it.讀者與寫者問題讀者與寫者問題n讀者：只能讀取數(shù)據(jù)區(qū)中的數(shù)據(jù)讀者：只能讀取數(shù)據(jù)區(qū)中的數(shù)據(jù)n寫者：只能往數(shù)據(jù)區(qū)中寫入數(shù)據(jù)寫者：只能往數(shù)據(jù)區(qū)中寫入數(shù)據(jù)n滿足的要求：滿足的要求：1、同時可以有任意多個讀者讀取數(shù)據(jù)、同時可以有任意多個讀者讀取數(shù)據(jù)2、在某個時候只能有一個寫者往里寫數(shù)據(jù)、在某個時候只能有一個寫者往里寫數(shù)據(jù)3、在寫的時候不能讀，讀的時候不能寫、在寫的時候不能讀，讀的時候不能寫 與生產(chǎn)者與生產(chǎn)者/消費者問題的區(qū)別？消費者問題的區(qū)別？A Solution to Readers/Writers Proble

37、mnSemaphores:nreadcount: integer;/ number of readersnrmutex: semaphores := 1;/ mutual exclusionnwmutex: Semaphores := 1;/ mutual exclusion among writersA Solution to Readers/Writers ProblemnReader:repeatP(rmutex);readcount := readcount + 1;if readcount =1 then P(wmutex);V(rmutex);READUNIT;P(rmutex);

38、readcount := readcount - 1;if readcount = 0 then V(wmutex);V(rmutex);foreverlWriter:repeatP(wmutex);WRITEUNIT;V(wmutex);forever本講內(nèi)容本講內(nèi)容nP、V操作小結(jié)操作小結(jié)n信號量集信號量集n進程間通信進程間通信回顧回顧經(jīng)典的進程同步問題：經(jīng)典的進程同步問題：n生產(chǎn)者生產(chǎn)者消費者問題消費者問題n讀者讀者寫者問題寫者問題Problem 2n有一閱覽室，共有有一閱覽室，共有100個座位。讀者進入個座位。讀者進入前必須先在一張登記表上登記，該表為前必須先在一張登記表上登記，該表為

39、每一座位列一表目，包括座號和讀者姓每一座位列一表目，包括座號和讀者姓名。讀者離開時要消掉登記內(nèi)容。試用名。讀者離開時要消掉登記內(nèi)容。試用某一種語言（或類語言）和某一種語言（或類語言）和P、V操作描操作描述讀者進程的同步結(jié)構(gòu)。述讀者進程的同步結(jié)構(gòu)。 n【分析分析】n本例是考查操作系統(tǒng)中信號量的應(yīng)用本例是考查操作系統(tǒng)中信號量的應(yīng)用. 讀者要申請座讀者要申請座位，首先要獲得登記表以便在上面進行登記；該讀位，首先要獲得登記表以便在上面進行登記；該讀者在登記過程中是不允許其他讀者進行登記的；因者在登記過程中是不允許其他讀者進行登記的；因此，需要引入一個初值為此，需要引入一個初值為1的信號的信號量量mut

40、ex以實現(xiàn)讀以實現(xiàn)讀者間對登記表的互斥使用；者間對登記表的互斥使用；n讀者要在登記表上進行登記，前提是登記表要有空讀者要在登記表上進行登記，前提是登記表要有空表目；為此，需要引入一個信號表目；為此，需要引入一個信號量量S，其初值其初值為為100，表示有空表目表示有空表目100項；項；n讀者在完成登記后，放下登記表給其他讀者使用，讀者在完成登記后，放下登記表給其他讀者使用，然后在申請到的座位上進行閱讀活動；然后在申請到的座位上進行閱讀活動； n在完成閱讀后讀者需刪除登記表上的內(nèi)容，在他進在完成閱讀后讀者需刪除登記表上的內(nèi)容，在他進行刪除的同時是不允許其他讀者進行刪除的。行刪除的同時是不允許其他讀

41、者進行刪除的。n讀者進程：讀者進程：nmutex, S: Semaphore;mutex := 1;S := 100;Process Readeri begin P( S ); /查找空表目查找空表目 P( mutex ); /申請登記申請登記 ; V( mutex ); /允許其他讀者填寫登記表允許其他讀者填寫登記表 ; P( mutex );V( mutex );V( S );end;Problem 3n設(shè)有四個進程設(shè)有四個進程A、X、Y、Z共享一個緩共享一個緩沖區(qū)，進程沖區(qū)，進程A負責(zé)循環(huán)地從文件讀一個整負責(zé)循環(huán)地從文件讀一個整數(shù)并放入緩沖區(qū)，進程數(shù)并放入緩沖區(qū)，進程X從緩沖區(qū)中循環(huán)從緩

42、沖區(qū)中循環(huán)地讀入地讀入MOD 3為為0的整數(shù)并累計求和；的整數(shù)并累計求和；Y從緩沖區(qū)中循環(huán)地讀入從緩沖區(qū)中循環(huán)地讀入MOD 3為為1的整數(shù)的整數(shù)并累計求和；并累計求和；Z從緩沖區(qū)中循環(huán)地讀入從緩沖區(qū)中循環(huán)地讀入MOD 3為為2的整數(shù)并累計求和。請用的整數(shù)并累計求和。請用PV操作寫出能夠正確執(zhí)行的程序。操作寫出能夠正確執(zhí)行的程序。 緩沖區(qū)AZYXnum MOD 3 = 0numnum MOD 3 = 1num MOD 3 = 2Sempty, SX, SY, SZ: Semaphore = 1, 0, 0, 0;num: integer; Process PABeginP(Sempty);if(

43、 num MOD 3 = 0 )V( SX )Else if ( num MOD 3 = 1 )V( SY )Else V( SZ );End;Process PXBeginP( SX );V( Sempty );End;Process PYBeginP( SY );V( Sempty );End;Process PZBeginP( SZ );V( Sempty );End;1) 信號量的物理含義信號量的物理含義：S0表示有表示有S個資源可用個資源可用S=0表示無資源可用表示無資源可用S=1 & S2 = 1 & & Sn = 1)/滿足資源要求時的處理；滿足資源要求時

44、的處理； for (i = 1; i = n; +i) -Si; /注：注：與與P的處理不同，這里是在確信可滿足的處理不同，這里是在確信可滿足 / / 資源要求時，才進行減資源要求時，才進行減1操作；操作；break;else /某些資源不夠時的處理；某些資源不夠時的處理； 調(diào)用進程進入第一個小于調(diào)用進程進入第一個小于1信號量的等待隊列信號量的等待隊列Sj.queue; 阻塞調(diào)用進程阻塞調(diào)用進程; 信號量集信號量集AND型信號量集（續(xù)）型信號量集（續(xù)） Ssignal(S1, S2, , Sn)for (i = 1; i = ti；即當資源數(shù)量低于即當資源數(shù)量低于ti時，便不予時，便不予分配）

45、分配）占用占用值為值為di（表示資源的申請量，即表示資源的申請量，即Si = Si - di）對應(yīng)的對應(yīng)的P、V原語格式為：原語格式為：nSwait(S1, t1, d1; .; Sn, tn, dn);nSsignal(S1, d1; .; Sn, dn);一般一般“信號量集信號量集”（續(xù)）（續(xù)）一般一般“信號量集信號量集”可以用于各種情況可以用于各種情況的資源分配和釋放，幾種特殊情況的資源分配和釋放，幾種特殊情況：nSwait(S, d, d)表示每次申請表示每次申請d個資源，當少個資源，當少于于d個時，便不分配個時，便不分配nSwait(S, 1, 1)表示互斥信號量表示互斥信號量nSw

46、ait(S, 1, 0)可作為一個可控開關(guān)（當可作為一個可控開關(guān)（當S 1時，允許多個進程進入臨界區(qū)；時，允許多個進程進入臨界區(qū)；當當S=0時，時，禁止任何進程進入臨界區(qū)）禁止任何進程進入臨界區(qū)）管程的引入管程的引入n信號量機制中信號量機制中P、V操作使用不當會造成操作使用不當會造成與時間有關(guān)的錯誤與時間有關(guān)的錯誤P、V操作不當?shù)睦硬僮鞑划數(shù)睦?V(mutex)P(mutex)P(mutex)V(mutex)P、V操作不當?shù)睦硬僮鞑划數(shù)睦?V(mutex)V(mutex)P(mutex)V(mutex)P、V操作不當?shù)睦硬僮鞑划數(shù)睦?P(mutex)P(mutex)V(mutex)

47、管程管程n1971年年, Dijkstra：把所有進程對某一種把所有進程對某一種臨界資源的同步操作集成起來構(gòu)成臨界資源的同步操作集成起來構(gòu)成“秘秘書書”進程；凡要訪問該資源的進程都需進程；凡要訪問該資源的進程都需先報告先報告“秘書秘書”，由其實現(xiàn)諸進程的同，由其實現(xiàn)諸進程的同步步n1973年，年，Hansan和和Hoare：管程概念管程概念管程概念管程概念n一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)程中的數(shù)據(jù)Hansan M

48、onitors - high level synchronization constructsnSemaphores and event-counters are too primitive (low level) and are hard to programn Monitors are a special package of proceduresn Mutual exclusion constructs are generated by the compiler. Internal data structures are invisiblenOnly one process is act

49、ive in a monitor at the same time - high level mutual exclusionmonitor sharedData int *buffer;public:writeData(int byteNum) ;readData(int byteNum) ; ;type monitor-name = monitorvariable declarationsprocedure entry P1 ();begin end;procedure entry P2 ();begin end;.procedure entry Pn ();begin end; begi

50、ninitialization code endFigure 6.20 Monitor with Condition VariableShared dataxyQueues associated with x, y conditionsoperationsInitialization codeEntry queueMonitors - Condition variablesn Only one process is active in a monitor at the same time - high level mutual exclusionn To enable synchronizat

51、ion: Condition variables and operations on them: and n the monitor provides queuing for proceduresn When one procedure and another , the signaling procedure is inside the monitor ! n Operation signal must be either followed by or , so that only one procedure is active at one timeBounded-Buffer with

52、Monitorsmonitor ProducerConsumerconditionnotfull, notempty;integercount;procedure enter;beginif count = N then notfull.wait;enter_item;count := count + 1;if count = 1 then notempty.signal; endprocedure remove;beginif count = 0 then notempty.wait;remove_item;count := count - 1;if count = N - 1 then n

53、otfull.signal; endcount := 0;end monitorBounded-Buffer with Monitors (II)procedure producer;beginwhile true dobeginproduce_item;ProducerConsumer.enter;endend;procedure consumer;beginwhile true dobeginProducerConsumer.remove;consume_item;endend;Interprocess Communication (進程間通信進程間通信)n低級通信低級通信 交換的數(shù)據(jù)量較

54、小的情況，常常指的交換的數(shù)據(jù)量較小的情況，常常指的是控制信息的交換，往往用來控制進程是控制信息的交換，往往用來控制進程執(zhí)行的速度，如鎖或信號量執(zhí)行的速度，如鎖或信號量n高級通信高級通信 傳送的數(shù)據(jù)量大，只是為了交換信息，傳送的數(shù)據(jù)量大，只是為了交換信息，而不是為了控制進程的執(zhí)行速度而不是為了控制進程的執(zhí)行速度進程間高級通信進程間高級通信類型類型n共享存儲區(qū)方式共享存儲區(qū)方式n共享文件方式（管道方式）共享文件方式（管道方式）n郵箱通信郵箱通信n消息緩沖機制消息緩沖機制共享存儲區(qū)方式共享存儲區(qū)方式n在內(nèi)存中開辟一塊供多個進程共享使用在內(nèi)存中開辟一塊供多個進程共享使用的區(qū)域的區(qū)域n基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式n由程序員完成同步處理n基于共享存儲區(qū)的通信方式基于共享存儲區(qū)的通信方式共享文件方式（管道方式共享文件方式（管道方式, Pipe）WriteReadFI