第3章并發控制-互斥與同步1第3章進程的并發控制——互斥與同步第3章并發控制-互斥與同步2進程的并發控制——互斥與同步3.1前趨圖(PrecedenceGraph)3.2進程的同步與互斥3.3信號量和管程3.4進程通信第3章并發控制-互斥與同步3互斥與同步概念在多道程序環境中，由于進程合作和資源共享，使得并發執行的多個進程之間存在兩種制約關系——同步與互斥第3章并發控制-互斥與同步4

互斥與同步概念（1）同步，也稱為直接相互制約，是指某些并發執行的進程為共同完成一個任務，需要相互合作、協同工作，這些合作的進程都是獨立地以不可預知的速度推進，這就需要在一些關鍵點上互相等待，互通消息。第3章并發控制-互斥與同步5

互斥與同步概念（2）互斥，也稱間接相互制約關系，是指多個進程同時競爭一個需要互斥使用的資源（如打印機等），當該資源已經分配給某個進程使用時，其它進程只能等待，直到該資源被釋放。第3章并發控制-互斥與同步6

互斥與同步概念可見，進程的同步是我們需要的，而互斥是被迫的。為了說明進程的同步，引入一個前趨圖的概念第3章并發控制-互斥與同步73.1前趨圖(PrecedenceGraph)前趨圖(PrecedenceGraph)是一個有向無循環圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執行的前后關系。圖中的每個結點可用于描述一個程序段或進程，乃至一條語句；結點間的有向邊則用于表示兩個結點之間存在的偏序(PartialOrder)或前趨關系第3章并發控制-互斥與同步8第3章并發控制-互斥與同步9圖3-3并發執行時的前趨圖第3章并發控制-互斥與同步10圖3-4四條語句的前趨關系第3章并發控制-互斥與同步11

3.2進程的同步與互斥

進程互斥定義:

所謂進程互斥是指當有若干進程都要使用某一共享資源時，最多允許一個進程使用，而其他要使用該資源的進程必須等待，直到占用該資源的進程釋放了該資源為止。進程互斥是進程之間發生的一種間接性作用，一般是程序不希望的。兩個進程不能同時進入臨界區，否則就會導致數據的不一致，產生與時間有關的錯誤。第3章并發控制-互斥與同步123.2進程的同步與互斥臨界資源定義:操作系統中將一次僅允許一個進程訪問的資源稱為臨界資源,如打印機、共享變量等。臨界區定義:操作系統中把每個進程中訪問臨界資源的那段代碼段稱為臨界區。第3章并發控制-互斥與同步133.2進程的同步與互斥如變量N是臨界資源，程序A中有訪問N的代碼：

…………….X=N;N++;

…………….

上面訪問N的兩句代碼就是程序A的臨界區。第3章并發控制-互斥與同步143.2進程的同步與互斥顯然，若能保證每個進程互斥地進入自己的臨界區，便可實現諸進程對臨界資源的互斥訪問第3章并發控制-互斥與同步153.2進程同步與互斥解決互斥問題應該滿足互斥和公平兩個原則，即任意時刻只能允許一個進程處于同一共享變量的臨界區，而且不能讓任一進程無限期地等待。第3章并發控制-互斥與同步16

進程同步機制的準則:

①空閑讓進：當無進程處于臨界區時，必須讓一個要求進入它的臨界區的進程立即進入，以提高臨界資源的利用率。

②忙則等待：當已有進程處于臨界區時，其他試圖進入自己臨界區的進程必須等待，以保證它們互斥地進入臨界區。

③讓權等待：對于等待進入臨界區的進程而言，它必須立即釋放處理機，以避免進程"忙等"而降低CPU的效率。

④有限等待：對要求進入臨界區的進程，應在有限時間內進入，以免陷入"死等"。第3章并發控制-互斥與同步173.2進程的同步與互斥（續）進程同步概念:一般來說，一個進程對于其它的進程運行速度是不確定的。但是相互合作的幾個進程需要在某些確定點上協調它們的工作。所謂進程同步，是指多個相互合作的進程，在一些關鍵點上可能需要互相等待或互相交換信息，這種相互制約的關系稱為進程同步。進程同步是進程之間直接的相互作用，是合作進程間有意識的行為。第3章并發控制-互斥與同步183.2進程同步與互斥進程同步實例1：典型的同步例子是公共汽車上司機與售票員的合作：

只有當售票員關門之后司機才能啟動車輛，只有司機停車之后售票員才能開車門。司機和售票員的行動需要一定的協調。同樣地，兩個進程之間有時也有這樣的依賴關系，因此我們也要有一定的同步機制保證它們的執行次序。

第3章并發控制-互斥與同步19

進程同步實例2：系統中有兩個合作的進程，他們共用一個單緩沖區。這兩個進程一個是計算進程，負責對數據進行計算；另一個為打印進程，負責對計算結果進行打印。當計算進程沒有計算完畢，計算結果沒有送到緩沖區的時候，打印進程就不能打印。一旦計算進程把計算結果送入緩沖區，就應該給打印進程發送一個信號，打印進程收到信號后就可以從緩沖區中取出計算結果進行打印。第3章并發控制-互斥與同步20

進程同步實例2（續）：在打印進程尚未把緩沖區中的計算結果取出打印之前，計算進程也不能把下一次的計算結果送入緩沖區。只有在打印進程取出緩沖區中的內容，給計算進程發一個信號后，計算進程才能將下一次的計算結果送入緩沖區。計算進程和打印進程就是通過這種互相發信號的方式實現同步的。第3章并發控制-互斥與同步213.3信號量和管程本章主要介紹以下兩種同步和互斥機制：信號量管程第3章并發控制-互斥與同步22

3.3信號量和管程互斥問題可以用硬件方法，也可以用軟件方法解決。“開關中斷”稱為硬件鎖，是最簡單的用硬件實現互斥的方法。第3章并發控制-互斥與同步23

3.3信號量和管程即在進程進入臨界區之前，先執行“關中斷”指令，即屏蔽所有中斷，在進程執行自己的臨界區期間，計算機系統不響應中斷，直到進程完成臨界區的執行，才執行“開中斷”指令。這樣，進程在執行臨界區時，會一直占用CPU，使其它進程不能再執行臨界區，從而有效地保證了臨界區的互斥使用，實現了進程的互斥。第3章并發控制-互斥與同步24

3.3信號量和管程用“開關中斷”指令實現互斥的模板如下：

P1：

..….

關中斷；臨界區；開中斷；

……

第3章并發控制-互斥與同步25

3.3信號量和管程這種方法雖然簡單，但如果關中斷的時間過長，會導致系統效率下降，甚至如果關中斷處理不當，還會引起系統無法正常調度，而且這種方法僅適用于單CPU系統。還有其它一些用硬件進行互斥方法，但都有許多缺陷。后來人們用軟件方法解決互斥，取得較好的效果，其中比較常用的有信號量機制和管程。第3章并發控制-互斥與同步263.3信號量和管程——3.3.1信號量1.信號量及P、V操作

2.利用信號量實現互斥

3.利用P、V操作描述前趨關系

4.生產者-消費者問題

5.哲學家就餐問題

6.讀者-寫者問題第3章并發控制-互斥與同步273.3信號量和管程——3.3.1信號量1.信號量及P、V操作信號量是一種有效的用來解決進程同步與互斥問題的機制。信號量最早是在1965年由荷蘭學者E.W.Dijkstra提出來的。這種方法是通過使用信號量及有關的P、V操作原語來實現進程的互斥與同步的。操作又叫Wait操作，V操作又叫Signal操作第3章并發控制-互斥與同步283.3信號量和管程

——3.3.1信號量

信號量是一個確定的兩元組（S，Q），其中S是一個具有非負初值的整型變量，Q是一個初始狀態為空的隊列。整型變量S表示系統中某類資源的數目，當其值大于或等于0時，表示系統中當前可用資源的數目；當其值小于0時，其絕對值表示系統中因請求該類資源而被阻塞的進程數目。第3章并發控制-互斥與同步293.3信號量和管程

——3.3.1信號量

除信號量的初值外，信號量的值僅能由P操作（又叫Wait操作）和V操作（又稱Signal操作）來改變。

第3章并發控制-互斥與同步303.3信號量和管程

——3.3.1信號量一個信號量的建立必須經過說明，即應該準確說明S的意義和初值（注意這個初值不是一個負值）。每個信號量都有一個相應的隊列，在建立信號量時，隊列為空。P、V操作以原語方式實現，信號量的值僅能由這兩條原語加以改變。P、V操作的定義為：第3章并發控制-互斥與同步31

3.3信號量和管程

——3.3.1信號量（1）P操作。

P操作記為P(S)，其中S為一個信號量，它執行時主要完成下述動作：

S=S-1；若S>=0則進程繼續運行；否則（即S<0)阻塞該進程，并將它插入該信號量的等待隊列中。第3章并發控制-互斥與同步323.3信號量和管程

——3.3.1信號量（2）V操作。

V操作記為V（S），S為一個信號量，它執行時主要完成下述動作：

S=S+1；若S大于0則進程繼續執行；否則（即S<=0)則從信號量等待隊列中移出第一個進程，使其變為就緒狀態并插入就緒隊列，然后再返回原進程繼續執行。第3章并發控制-互斥與同步33

3.3信號量和管程

——3.3.1信號量

2.利用信號量實現互斥利用信號量能方便地實現互斥。設S為兩個進程P1、P2實現互斥的信號量，由于每次只允許一個進程進入臨界區，所以S的初值應為1（即可用資源的數目為1）。只需要把臨界區置于P(S)和V(S)之間，即可以實現兩個進程的互斥。互斥訪問臨界區的描述如下：第3章并發控制-互斥與同步34

3.3信號量和管程

——3.3.1信號量

P1、P2互斥訪問臨界區：//注意格式！semaphoreS=1;main(){

cobeginP1();P2();coend}第3章并發控制-互斥與同步35

3.3信號量和管程

——3.3.1信號量

P1(){

……

/*剩余區*/P(S);

進程P1的臨界區；

V(S);……}

P2(){……

/*剩余區*/P(S);

進程P2的臨界區；

V(S);

……}第3章并發控制-互斥與同步36

一個慣例：當我們可使用的資源數量最多為1的時候，信號量一般用mutex表示如：semaphoremutex=1若信號量表達的不是臨界資源（即一段時間里可供多個進程訪問的資源），則信號量不用mutex表達第3章并發控制-互斥與同步37

3.3信號量和管程

——3.3.1信號量

3.利用P、V操作描述前趨關系若干進程為了完成一個共同的任務而并發執行。這些并發進程有些沒有時間上的先后次序，不管誰先做都是正確的；有些進程則必須有先后順序，也就是他們必須遵循一定的同步規則，只有這樣，并發執行的最終結果才是正確的。第3章并發控制-互斥與同步38例1：P1、P2、P3、P4、P5、P6為一組合作進程。試用P、V操作實現這六個進程的同步。P1P2P3P4P5P6第3章并發控制-互斥與同步39為了確保上述前趨圖圖中6個進程的執行順序，設置5個同步信號量f1、f2、f3、f4、f5，分別表示進程P1、P2、P3、P4、P5是否執行完成，其初值設為0，表示起始沒有完成。6個進程的同步描述如下：

semaphoref1=0;semaphoref2=0;semaphoref3=0;semaphoref4=0;semaphoref5=0;第3章并發控制-互斥與同步40main(){cobeginP1();P2();P3();P4();P5();P6();coend}第3章并發控制-互斥與同步41P1(){……V(f1);V(f1);}P2(){P(f1);……V(f2);V(f2);}

P3(){P(f1);……V(f3);}P4(){P(f2);……V(f4);}第3章并發控制-互斥與同步42P1P2P3P4P5P6第3章并發控制-互斥與同步43

P5(){P(f2);……V(f5);}

P6(){P(f3);P(f4)P(f5);……}第3章并發控制-互斥與同步44練習1：下圖是6個進程的前趨圖。用P、V操作實現進程的同步P1P2P3P4P5P6第3章并發控制-互斥與同步45參考解答：設5個同步信號量f1、f2、f3、f4、f5，分別表示進程P1、P2、P3、P4、P5是否執行完成，其初值設為0。6個進程的同步描述如下：

semaphoref1=0;semaphoref2=0;semaphoref3=0;semaphoref4=0;semaphoref5=0;第3章并發控制-互斥與同步46main(){

cobeginP1();P2();P3();P4();P5();P6();coend}第3章并發控制-互斥與同步47P1(){……V(f1);V(f1);V(f1);}P2(){……V(f2);V(f2);}第3章并發控制-互斥與同步48P3（）

{P(f1);……V(f1);}

P4(){P(f1);P(f2);……V(f4);}第3章并發控制-互斥與同步49P5(){P(f2);……V(f5);}P6(){P(f3);P(f4);P(f5);……}第3章并發控制-互斥與同步50練習2.某電話亭每一時刻最多只能容納一個人打電話。來打電話的人，如果看到電話亭空閑，則直接進入電話亭打電話；如果看到電話亭里正有人在打電話，則在外面排隊等候，直到輪到自己，再進入電話亭打電話。請用信號量來表達打電話的進程對電話亭的互斥使用。第3章并發控制-互斥與同步51

練習2參考解答（續）：該電話亭每次只能容納一個人打電話（進程）使用，所以是一個臨界資源，資源量為1，各進程要互斥使用。用信號量來表達資源的數量：

semphoremutex=1；（或empty=1）

main()

{

CobeginP（i）；//(i=1,2,3,4,……);

Coend}第3章并發控制-互斥與同步52

練習2參考解答（續）：P(i)

//i=1,2,3……{

P(mutex);

打電話；

………

走出電話亭

V(mutex);}第3章并發控制-互斥與同步53練習3.某電話亭共有3臺電話機，即能容納3個人（3個進程）同時打電話。來打電話的人，如果看到電話亭有空閑機子，則直接進入電話亭打電話；如果看到電話亭人滿，則在外面排隊等候，直到輪到自己，再進入電話亭打電話。請用信號量機制表達打電話的進程對電話機資源的使用限制。第3章并發控制-互斥與同步54

練習3參考解答：用信號量來表達空閑的電話機數：資源量的初值為3（表示開始時有3臺空機子可用）

semaphoreempty=3；

main（）

{CobeginP（i）;//i=1,2,3,……Coend}第3章并發控制-互斥與同步55

練習3參考解答：P（i）//i=1，2，3，…{

P(empty);

打電話；

V(empty);}第3章并發控制-互斥與同步56練習4：某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者的一次購票看作一個進程，請回答下列問題：

(1)用P、V操作管理這些并發進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。

第3章并發控制-互斥與同步57(2)根據所定義的信號量，把應執行的P、V操作填入下述方框中，以保證進程能夠正確地并發執行。COBEGIN

PROCESSPi(i=1，2，……)

begin

；

進入售票廳；購票；退出；

；

endCOEND第3章并發控制-互斥與同步58(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)

。第3章并發控制-互斥與同步59練習4參考解答：(1)定義一信號量empty，初始值為20。

意義：

empty>0empty的值表示可繼續進入售票廳的人數empty=0

表示售票廳中已有20名顧客(購票者)empty<0|empty|的值為等待進入售票廳的人數

第3章并發控制-互斥與同步60

練習4參考解答：(2)上框為P(empty)下框為V(empty)(3)empty的最大值為20empty的最小值為20－n

注：信號量的符號可不同(如寫成s、t等)，但使用時應上下一致(即上述的s全應改成t)。第3章并發控制-互斥與同步61練習5：在公共汽車上，司機和售票員周期性的活動分別是：

司機：啟動車輛；正常行駛；到站停車；售票員：關車門；售票；開車門；在汽車不斷地到站、行駛過程中，這兩個活動有什么同步關系？用信號量和P、V操作實現他們的同步。分析：司機啟動汽車要在售票員關上車門之后；售票員開車門要在司機停車之后

第3章并發控制-互斥與同步62練習5參考解答：在本題中設置兩個信號量：SDoorClosed表示有未關好車門，初值為0表示一開始未關車門；SBusstoped表示有沒有停下車，初值為1表示起始時刻車已停下。第3章并發控制-互斥與同步63練習5參考解答：SemaphoreSDoorClosed=0；SemaphoreSBusStoped=1；

main（）

{

Cobegindriver（）；

busman（）；

Coend}第3章并發控制-互斥與同步64Driver（）

{while(1){P(SDoorClosed);

啟動車輛；正常行駛；到站停車；

V（SBusStoped

）；

}}第3章并發控制-互斥與同步65

busman(){

while(1){關車門；

V（SDoorClosed

）；賣票；

P（SBusStoped

）；開車門；

}}

第3章并發控制-互斥與同步66有時為了完成某一任務，要等的資源（信號量）不止一種，這時要根據具體情況，建立多個信號量，使用多個P、V操作

第3章并發控制-互斥與同步67附加練習1：學校電子閱覽室共有30個計算機供讀者使用，同時為了掌握上機情況，每個要進入閱覽室的人必須先在一個紙質的登記本上登記以后才能使用電子閱覽室，每個時刻只有一個人能使用該登記本。每個讀者的閱覽步驟是（1）先看有無空機可用，若有則進入登記環節，若無則排隊等候空機；（2）進行登記時，若無人在登記，則在登記本上登記，若有人正在登記，則排隊等候登記本。第3章并發控制-互斥與同步68附加練習1參考解答：//第一步：說明并定義信號量，并賦初值設其中的一個信號量empty為閱覽室可使用的空機數，初值為30；另一個信號量notebook為登記本一次允許使用的進程數，初值為1；

Semaphoreempty=30;Semaphorenotebook=1;第3章并發控制-互斥與同步69附加練習1參考解答：//第二步：建立main函數，說明各個并發的進程

main(){

cobeginP(i);

//i=1,2,3,…或Read(i);

coend}

第3章并發控制-互斥與同步70

附加練習1參考解答：//第三步：對每一個參與并發的進程進行具體說明，并輔以P、V操作

P（i）

{

P（empty）；

P（notebook）；進行登記；登記完畢；放下登記本；

V（notebook）；進入閱覽室；使用計算機；離開閱覽室；

V（empty）；

}

第3章并發控制-互斥與同步71附加練習2：某理發店有2把理發椅供顧客坐著理發，同時還有一個能容納5個人的等待室供等待理發的顧客坐。用P、V操作來說明理發進程之間的互相制約情況第3章并發控制-互斥與同步72附加練習2參考解答：

分析：

想要理發的顧客，一共要等待兩種資源才能完成理發：（1）要先進入等待室等待理發。若等待室沒有空位，則在等待室外面等候，直到有空位；（2）坐上理發椅進行理發。在等待室等待理發的顧客進入理發椅理發之前，要看看有無空的理發椅，有空著的則坐上理發椅理發，無空的理發椅則在等待室等候。第3章并發控制-互斥與同步73附加練習2參考解答：//第一步：說明并定義信號量，賦以初值用一個信號量S1來表示等待室中可用的空椅子個數，用另一個信號量S2表示可用的空理發椅個數

SemaphoreS1=5；

SemaphoreS2=2；第3章并發控制-互斥與同步74附加練習2參考解答//第二步：在main函數中羅列各個并發的進程

main（）

{

cobegin

P（i）；i=1,2,3,……

coend}第3章并發控制-互斥與同步75附加練習2參考解答//第三步：對各個理發的進程具體說明，并輔以相應的P、V操作

P（i）

{P（S1）；

進入等待室；

P（S2

）；

坐上理發椅；

V（S1）；

開始理發；理發完畢；

V（S2

）；

}第3章并發控制-互斥與同步76

附加練習3：

到澡堂洗澡的一個進程要經歷兩個步驟：（1）先看有無可用的更衣箱，若有則進入澡堂，若沒有則等候更衣箱；（2）進入澡堂后并不一定能立刻洗澡，要先看有無空的水龍頭可用，有則洗澡，沒有則等候水龍頭。假定共有20個更衣箱，15個水龍頭，用P、V操作表達多個洗澡進程的互相制約關系。第3章并發控制-互斥與同步77

附加練習3參考解答：用信號量S1表示可用的更衣箱數，初值為20；用信號量S2表示可用的水龍頭數，初值為15；

semaphoreS1=20；

semaphoreS2=15；第3章并發控制-互斥與同步78

附加練習3參考解答：main（）

{

cobegin；

Pi（）；//i=1,2,3,……

coend}第3章并發控制-互斥與同步79

附加練習3參考解答：Pi（）

{

P（S1）；

獲取更衣箱；

P（S2）；

獲取水龍頭；

洗澡；洗澡完畢；

V（S2）；

V（S1）；

}

第3章并發控制-互斥與同步80問：在該問題中，S1=10，S1=0，S1=-30分別表示什么意義？

S2=10，S2=0，S2=-10各表示什么意義？若來洗澡的人數為n，那么S1、S2的最大值分別是多少？最小值呢？第3章并發控制-互斥與同步81

3.3信號量和管程

——3.3.1信號量

4.生產者-消費者問題把并發進程的同步和互斥問題一般化，可以得到一個抽象的一般模型——生產者-消費者模型。在計算機系統中每個進程都申請使用和釋放各種不同類型的資源，這些資源既可以是外設、內存及緩沖區等硬件資源，也包括臨界區、數據等軟件資源。把系統中使用某一類資源的進程稱為該資源的消費者，而把釋放同類資源的進程稱為該資源的生產者第3章并發控制-互斥與同步824.生產者-消費者問題

生產者-消費者問題是一個著名的進程同步問題。它描述了一組生產者向一組消費者提供產品，生產者與消費者共享一個有界緩沖區，生產者向其中投放產品，消費者從中取得產品。

生產者-消費者問題是許多相互合作進程的一種抽象，例如，在輸入時，輸入進程是生產者，計算進程是消費者；在輸出時，計算進程是生產者，打印進程是消費者。第3章并發控制-互斥與同步83

4.生產者-消費者問題我們把一個長度為n的有界緩沖區（n>0)與一群生產者進程P1、P2、……Pm和一群消費者進程C1、C2、……Ck聯系起來。假定這些消費者和生產者都是等效的。只要緩沖區未滿，生產者就可以把產品送入緩沖區，類似地，只要緩沖區未空，消費者就可以從緩沖區中取走產品并消費之。第3章并發控制-互斥與同步84生產者和消費者的同步關系，將禁止生產者向滿的緩沖區輸送產品，也禁止消費者從空的緩沖區中提取產品。第3章并發控制-互斥與同步85

4.生產者-消費者問題

為了解決生產者-消費者問題，應該設置兩個同步信號量.一個說明空緩沖單元的數目，用empty表示，其初值為有界緩沖區的大小n，另一個說明滿緩沖單元的數目，用full表示，其初值為0。第3章并發控制-互斥與同步86本例有P1、P2，…Pm個生產者和C1、C2、…Ck個消費者，它們在生產和消費活動中要對有界緩沖區進行操作，而有界緩沖區是一個臨界資源，必須互斥使用，因此還需要另外設置一個互斥信號量mutex，其初值為1。生產者-消費者問題的同步描述如下：第3章并發控制-互斥與同步87semaphorefull=0;//第一步：定義信號量，semaphoreempty=n;

//并為信號量賦初值semaphoremutex=1;main()//第二步：編寫主函數，{cobegin

//在其中調用各個進程

producer(i);//i=1,2,…mconsumer(j);//j=1,2,…kcoend}第3章并發控制-互斥與同步88//第三步：編寫各個具體的進程，其中加上P、V操作producer(i){while(1){生產一個產品；

p(empty);p(mutex);

將一個產品送入有界緩沖區；

V(mutex);V(full);}}consumer(j){while(1){p(full);p(mutex);

從緩沖區中取出一個產品；

V(mutex);V(empty);

消費一個產品

}}第3章并發控制-互斥與同步89

4.生產者-消費者問題注意：無論在生產者進程還是消費者進程中，P操作的次序都不能顛倒，否則將可能造成死鎖。練習：思考一下，在上面的例子中，在一個進程中顛倒一下兩個P操作，可能會產生什么樣的不利后果？第3章并發控制-互斥與同步90練習6.兄弟倆共同使用一個賬號，每次限存和取100元錢。如何用P、V操作來實現兩個并發操作的互斥，以避免賬號里的錢數發生錯誤分析：無論存錢還是取錢都要分為3個步驟：（1）把賬戶對應的金額讀到一個變量中；（2）讓該變量+100或-100

（3）把該變量的值寫回賬戶中第3章并發控制-互斥與同步91

練習6分析：先存錢和先取錢都不會發生錯誤，但若兩個進程交錯使用CPU時就會產生不同的值。用互斥信號量mutex來互斥存錢和取錢兩個進程對帳戶金額amount的修改第3章并發控制-互斥與同步92

練習6參考解答：Semaphoremutex=1;//表示每次只有一個進程（用戶）可以存取該帳戶，故可用資源總數為1intamount=0;//假定剛開始帳戶里的余額為0；

main(){cobeginsave();take();coend}第3章并發控制-互斥與同步93練習6參考解答：take(){P(mutex);m2=amount;m2=m2-100;amount=m2;V(mutex);}save(){P(mutex);m1=amount;m1=m1+100;amount=m1;V(mutex);}第3章并發控制-互斥與同步94練習7：（1）寫出P、V操作的定義（2）三個進程PA、PB、PC協作解決文件打印問題：

PA將文件記錄從磁盤讀入到內存緩沖區1，每執行一次讀一個記錄；

PB將緩沖區1中的內容復制到緩沖區2，每執行一次復制一個記錄；

PC將緩沖區2的內容打印出來，每執行一次打印一個記錄；假定緩沖區的大小和一個記錄一樣大。請用P、V操作來保證文件的正確打印第3章并發控制-互斥與同步95本題也是一個典型的生產者-消費者問題，其中的難點在于PB既是一個消費者，又是一個生產者緩沖區1緩沖區2PAPBPC從磁盤讀入復制打印第3章并發控制-互斥與同步96

練習7參考解答：設置4個信號量：

empty1

：表示緩沖區1空位數，初值為1；

full1

：表示緩沖區1滿記錄數，初值為0empty2：表示緩沖區2空位數，初值為1；

full2：表示緩沖區2滿記錄數，初值為0

第3章并發控制-互斥與同步97

練習7參考解答：main(){

cobeginPA();PB();PC();coend}第3章并發控制-互斥與同步98

練習7參考解答：PA(){while(1){從磁盤讀一個記錄；

P(empty1);

將記錄存入緩沖區1；

V(full1);}}PB(){while(1){P(full1);

從緩沖區1取出記錄；

V(empty1);P(empty2);

將記錄存入緩沖區2；

V(full2);}}第3章并發控制-互斥與同步99

練習7參考解答：PC(){

while(1){P(full2);

從緩沖區2取出記錄；

V(empty2);

打印記錄；

}}第3章并發控制-互斥與同步100練習8.

桌上有一個盤子，只能存放一個水果。父親總是放蘋果到盤子中，而母親總是放香蕉到盤子中；一個女兒專等吃盤中的蘋果，一個兒子專等吃盤中的香蕉。請用信號量機制解決該問題。分析：在本題中，爸爸、媽媽、兒子、女兒共用一個盤子，且盤子每次只能放一個水果；當盤子為空時，爸爸可以放入蘋果，或媽媽可以放入香蕉；若放入盤中的是蘋果，則允許女兒吃，若放入盤中的是香蕉，則允許兒子吃。第3章并發控制-互斥與同步101

練習題8分析：本題實際上是生產者——消費者問題的一種變形。這里生產者有兩類爸爸和媽媽；每類生產者只生產其中固定的一類產品：爸爸放蘋果，媽媽放香蕉；消費者也有兩類兒子和女兒；每類消費者只消費其中固定的一類產品:兒子消費香蕉，女兒消費蘋果。第3章并發控制-互斥與同步102

練習題8參考解答：爸爸、媽媽、兒子、女兒的四個進程都是隨機地并發執行自己的循環操作；但爸爸媽媽放水果前，要先看看盤子是否為空，若為空則放入自己的水果，若不空則等待（阻塞）；第3章并發控制-互斥與同步103兒子拿水果前，要先看看盤中有無香蕉，有則拿來吃，沒有則等待（阻塞）；女兒拿水果前要先看看盤中有無蘋果，有則拿來吃，沒有則等待（阻塞）。第3章并發控制-互斥與同步104練習題8參考解答：本題設置三個信號量：爸爸媽媽要用到的表示盤子是否有空位的信號量SEmpty，

因最多只有一個空位（可放一個水果），所以初值為1，表示開始時盤子有一個空位；第3章并發控制-互斥與同步105女兒吃水果前要看看盤中有沒有蘋果，用信號量SApple

表示盤中可用的蘋果個數，初值設為0，表示開始時沒有蘋果在盤中；兒子吃水果前要先看看盤中有無香蕉，用信號量SBanana表示盤中香蕉的個數。初值設為0，表示開始時沒有香蕉在盤中；第3章并發控制-互斥與同步106練習題8參考解答：SemaphoreSEmpty=1；SemaphoreSApple=0；SemaphoreSBanana=0；

main(){

Cobeginfather();mather();son();

doughterCoend}第3章并發控制-互斥與同步107Father(){

while(1){P(SEmpty);

把一只蘋果放入盤中；

V(SApple);}}Mather(){

while(1){P(Empty);

把一只桔子放入盤中；

V(Banana

);}}第3章并發控制-互斥與同步108Son（）{while(1){P(Banana）；從盤中拿桔子吃；

V(SEmpty);}}

Daughter（）{while(1){P(SApple)；從盤中拿蘋果吃；

V(SEmpty)

}}第3章并發控制-互斥與同步1095.哲學家就餐問題Dijkstra于1965年首先提出并解決了哲學家就餐問題。該問題是大量并發控制問題中的一個典型的同步例子。第3章并發控制-互斥與同步1105.哲學家就餐問題哲學家就餐問題描述如下：5個哲學家傾注畢生精力用于思考和吃飯。他們坐在一張放有5把椅子的圓桌旁，每人獨占一把椅子。圓桌中間放置食品，桌上放著5根筷子，每個哲學家的左右各有一只筷子。第3章并發控制-互斥與同步1115.哲學家就餐問題哲學家只做2件事：思考和吃飯哲學家思考時并不影響他人，只有當哲學家饑餓的時候，他才試圖拿起左右兩根筷子（一根一根拿起）。第3章并發控制-互斥與同步112如果筷子已在他人手中，則需要等待。饑餓的哲學家只有同時拿起了兩根筷子后才可以開始吃飯。吃完飯后才放下筷子，重新開始思考。第3章并發控制-互斥與同步113

分析：放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現對筷子的互斥使用，可以用一個信號量表示一只筷子，由這5個信號量構成信號量數組。第3章并發控制-互斥與同步114進行同步的解決方案如下：semaphorechopstick[5]；//假定數組從下標0開始：所有信號量都被初始化為1，即chopstick[0]=chopstick[1]=chopstick[2]=chopstick[3]=chopstick[4]=1；第3章并發控制-互斥與同步115為了同步，第i位哲學家的活動Pi可描述為：

while(1){P(chopstic[i]

);

P(chopstic[(i+1)mod5]);eatint;……

V(chopstic[i]);

V(chopstic[(i+1)

mod5]);thinking;……}第3章并發控制-互斥與同步1165.哲學家就餐問題雖然上述解法可保證不會有兩個相鄰的哲學家同時就餐，但有可能會引起死鎖。假如5位哲學家同時饑餓而拿起左邊的筷子時，就會使5個信號量chopstick均為0；當他們試圖拿右邊的筷子時，都將因無筷子可拿而無限期地等待。對于這樣的死鎖問題，可采用以下幾種解決方法：第3章并發控制-互斥與同步117

5.哲學家就餐問題（1）至多只允許有4位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能就餐，用畢后能釋放兩只筷子，從而使更多的哲學家就餐。（2）僅當哲學家的左右兩只筷子均可用時，才允許他拿起筷子就餐。第3章并發控制-互斥與同步118

5.哲學家就餐問題（3）規定奇數號哲學家先拿他左邊的筷子，然后再拿他右邊的筷子；偶數號哲學家則正相反。按此規定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即5位哲學家都先競爭奇數號筷子，獲得后，再去競爭偶數號筷子，最后總有一位哲學家能獲得兩只筷子而就餐。第3章并發控制-互斥與同步1196.讀者-寫者問題讀者-寫者問題是1971年由Courtois提出的一個經典的同步問題。該問題可描述為：兩組并發進程共享一個數據文件;其中，一組進程只要求讀該文件，稱為讀者進程（Reader），另一組進程只要求寫該文件，稱為寫者進程（Writer）。第3章并發控制-互斥與同步1206.讀者-寫者問題該問題還要求：（1）允許多個讀者進程同時對該文件執行讀操作；（2）不允許讀者進程和寫者進程同時對該文件進行操作，即讀者和寫者要互斥；（3）不允許多個寫者同時對文件進行“寫”操作，即寫者與寫者之間要互斥第3章并發控制-互斥與同步121

分析：為滿足要求(1)——幾個讀者可以同時讀同一個文件的要求，要設置一個信號量Rcount，表示正在讀文件的進程個數，初值設為0。當一個讀者進程要讀該文件的時候，要先對Rcount進行操作，讓Rcount的值加1；當一個進程讀完該文件的時候，也要對Rcount進行操作，讓Rcount減1；第3章并發控制-互斥與同步122但是注意：Rcount是可被多個讀者進程訪問的臨界資源，應為它設置一個互斥信號量Rmutex，初值設為1；第3章并發控制-互斥與同步123

分析：為滿足要求（2）：

“讀者與寫者保持互斥”以及滿足要求（3）：

“寫者與寫者保持互斥”，要再設一個互斥信號量Wmutex，這是一個和寫有關的信號量，初值設為1，Wmutex=1第3章并發控制-互斥與同步124

即：為了解決讀寫之間的同步，應設兩個信號量和一個共享變量：讀互斥信號量Rmutex，用于使讀進程互斥地訪問共享變量Rcount，初值為1；寫互斥信號量Wmutex，用于實現寫進程與寫進程、寫進程與讀進程之間的互斥，初值為1；共享變量Rcount，記錄當前正在讀文件的進程個數，初值為0第3章并發控制-互斥與同步125讀者-寫者工作過程描述如下：SemephoreRmutex=1;SemephoreWmutex=1;intRcount=0;main(){cobeginreaderi（）;i=1,2,3,……writeri（）;i=1,2,3,……coend}第3章并發控制-互斥與同步126Readeri（）{while(1){P(Rmutex）;if(Rcount==0)P(Wmutex);

Rcount++;v(Rmutex);

讀文件；

P(Rmutex);

Rcount--;if(Rcount==0)V(Wmutex);V(Rmutex);}}writeri（）

{while(1){P(Wmutex);

寫文件；

V(Wmutex);}}第3章并發控制-互斥與同步127

“讀者優先”與“寫者優先”：注意上面的讀者-寫者解決方案，它其實是一個對讀者有利的解決方案。只需設想一下：假設系統中順序出現四個進程：reader1，reader2，writer1，reader3Reader1、reader2均可順利進行讀操作，當它們還在讀的時候writer1來到，可憐的writer1將被阻塞；第3章并發控制-互斥與同步128

“讀者優先”與“寫者優先”（續）：接著reader4、reader5……一系列讀者相繼來到盡管writer1先來到，后來的reader們卻搶在writer1的前面進行了讀操作這樣的解決方案稱為“讀者優先”第3章并發控制-互斥與同步129

“讀者優先”與“寫者優先”（續）：將上面的偽程序稍加改造，便可形成“寫者優先”的讀者-寫者解決方案再增加一個信號量mutex，在讀者、寫者進程開始時獲得這個這個資源才能繼續進行；否則將會阻塞第3章并發控制-互斥與同步130“寫者優先”策略的讀者寫者問題：Semaphoremutex=1SemaphoreRmutex=1SemaphoreWmutex=1SemaphoreRcount=0第3章并發控制-互斥與同步131

main(){

Cobeginreaderi();//i=1,2,3,……writerj();//j=1,2,3,……Coend

}第3章并發控制-互斥與同步132

readeri(){while(1){

P(mutex);//新加的

P(Rmutex);if(Rcount==0)P(Wmutex);

Rcount=Rcount+1;V(Rmutex);

V(Mutex);//新加的

Reading……P(Rmutex);

Rcount=Rcount-1;if(Rcount==0)V(Mutex);V(Rmutex)}}第3章并發控制-互斥與同步133writeri（）

{while（1）

{P(Mutex);P(Wmutex);

Writing……V(Wmutex);V(mutex);}}

第3章并發控制-互斥與同步134“寫者優先”策略的讀者寫者問題：在這種情況下，若依然按reaer1,reader2,writer1,reader3,reader4……的順序來一些進程Reader3，reader4就不會在writer1之前進行讀操作了。第3章并發控制-互斥與同步1353.3.2管程機制雖然信號量機制是一種既方便又有效的進程同步機制，但每個要訪問臨界資源的進程都必須自備同步操作P(S)和V(S)。這使得大量的同步操作分散在各個進程中。這不僅給系統管理帶來麻煩，而且還會因為同步操作的使用不當造成系統死鎖。于是在解決上述問題的基礎上，產生了一種新的同步工具——管程第3章并發控制-互斥與同步136一.管程定義：Hasan為管程下的定義為：“一個管程定義了一個數據結構和能為并發進程所執行（在該數據結構上）的一組操作，這組操作能同步進程和改變管程中的數據”。管程機制提供了與信號量機制相同的表達能力，但它更容易控制。管程是一種軟件模塊，包括一個或多個過程、初始化語句和局部數據。第3章并發控制-互斥與同步137二.管程的特點：（1）只能通過管程中的過程，而不能通過其他外部過程訪問其局部數據變量；（2）進程通過調用管程的過程而進入管程；（3）為確保互斥，一個管程中一次只能有一個進程是活躍的，任何其它調用管程的過程都將被阻塞直至管程可用為止。因為管程是一個語言成分，所以管程的互斥訪問完全由編譯程序在編譯時自動添加，無須程序員關注，而且保證正確。第3章并發控制-互斥與同步138

三.建立管程的基本理由由于對臨界區的執行分散在各個進程之中，這樣不便于系統對臨界資源的控制和管理，也很難發現和糾正分散在用戶程序中的對同步原語的錯誤使用等問題。第3章并發控制-互斥與同步139為此應把分散的各同類臨界區集中起來，并為每個可共享資源設立一個專門的管程來統一管理各進程對資源的訪問。這樣，既便于系統管理共享資源，又能保證互斥訪問。第3章并發控制-互斥與同步140

四.操作條件變量的函數管程機制是一種自動提供適當同步方式的機制，它必須擁有同步手段。可使用條件變量支持同步。這些變量保存在管程中，并且只能在管程內部訪問。第3章并發控制-互斥與同步141

四.操作條件變量的函數cWait(c)//調用進程在條件c上掛起，管程可被其它進程使用

cSignal(c)//在條件c上被掛起的進程再次執行管程的cWait(c)/cSignal(c)操作與信號量中的不同。如果管程中的進程發出信號，并且沒有一個任務等待條件變量，那么這個信號就將丟失。第3章并發控制-互斥與同步142管程舉例：

用管程解決生產者消費者同步問題假定有一個多進程共用的緩沖區，里面最多能放n個單元的產品；生產者進程周而復始地生產產品；每次生產一個單元的產品（item）；只要緩沖區有空位存在——即只要緩沖區不滿（notfull）就將產品放入緩沖區；若緩沖區已滿，則阻塞，等待notfull條件出現；第3章并發控制-互斥與同步143管程舉例：

用管程解決生產者消費者同步問題消費者周而復始地消費產品；只要緩沖區不是空的（notnull），就從緩沖區拿出一個單元的產品，進行消費——注意：緩沖區是一個臨界資源，各個生產者進程和消費者進程必須互斥地使用緩沖區問題：請用管程實現一組生產者和消費者的同步與互斥操作

第3章并發控制-互斥與同步144

管程的實現步驟——1.定義一個管程：（1）聲明一個管程，給出名字：（2）聲明管程內的數據結構、變量、條件變量：（3）聲明管程從外部可調用的函數(里面就包含了CWait和CSignal操作）（4）對管程聲明的變量進行初始化第3章并發控制-互斥與同步145

管程的實現步驟——

2.在main函數中把并發的進程羅列出來：Main（）

{cobeginPi()//i=1,2,3,……coend}第3章并發控制-互斥與同步146

管程的實現步驟——

3.在各個進程pi中調用管程中的函數

。。。。。。第3章并發控制-互斥與同步147舉例：生產者消費者管程：

——1.聲明一個管程MonitorMonitor_1;//起名字IntCount,Mutex//變量ConditionNotFull,NotNull;

//等待條件Put(x)//外部將會調用的函數{if(Count==n)CWait(NotFull);P(Mutex);putxintorush_areaCount++;V(Mutex);if((Count-1)==0)CSignal(NotNull);}第3章并發控制-互斥與同步148Get(x)//外部將會調用的函數{if(count==0)CWait(NotNull);P(mutex);getxfromrush_area;count--;V(Mutex);if((count+1)==n)CSignal(NotFull);}第3章并發控制-互斥與同步149{Count=0;//對變量初始化

mutex=1；

}第3章并發控制-互斥與同步150生產者消費者管程：——

2.在main中羅列并發進程main(){

cobeginproduceri();Consumeri();

coend}

第3章并發控制-互斥與同步151生產者消費者管程：——

3.在各個并發的進程中調用管程的函數produceri(){while(1)produceanitem;

mon_1.put(item);}consumer(){while(1)mon_1.get(item);}第3章并發控制-互斥與同步152總之，用管程解決同步與互斥，要分三個步驟（比較信號量機制）進行：1.定義一個管程（包含了管程的名字、涉及的數據結構、在數據結構上定義的操作、數據結構的初始化）；2.在main（）函數中把并發的進程歸在一起；3.說明各個進程的實際操作過程，并在其中引用管程中定義的操作（或函數）。第3章并發控制-互斥與同步153在現代操作系統中，信號量、管程是用來進行同步互斥的重要機制。除此之外，還有臨界區等許多其它的機制也能達到同樣的效果。我們在程序設計中，可參考相應的操作系統API函數，來選擇使用哪種機制，只要能達到要求便可。第3章并發控制-互斥與同步154

3.4進程通信進程通信是指進程之間的信息交換，其所交換的信息量，少則只是一個狀態或一個數值，多則可能是成千上萬個字節。進程之間的互斥與同步也是一種通信，由于其所交換的信息量少而被叫做“低級通信”。在進程互斥中，進程通過只修改信號量來向其它進程表明臨界資源是否可用；在生產者-消費者問題中，生產者通過緩沖池將所生產的產品傳送給消費者。第3章并發控制-互斥與同步155

3.4進程通信本節所要介紹的是高級進程通信，是指用戶可直接利用操作系統所提供的一組通信命令，高效地傳送大量數據的一種通信方式。操作系統隱藏了通信的實現細節，或者說通信過程對用戶是透明的，這樣就大大減少了通信程序編制上的復雜性。第3章并發控制-互斥與同步156

3.4.1進程通信的類型隨著OS的發展，用于進程之間實現通信的機制也在不斷發展，已由早期的低級通信機制發展為能傳送大量數據的高級通信機制。目前的高級通信機制可以歸為三大類：共享存儲器系統消息傳遞系統管道通信系統第3章并發控制-互斥與同步157

1.共享存儲器系統在共享存儲器系統中，相互通信的進程共享某些數據結構或共享存儲區，進程之間能夠通過這些空間進行通信。于是又可再分為以下兩種通信方式：

基于共享數據結構的通信方式基于共享存儲區的通信方式第3章并發控制-互斥與同步158

（1）基于共享數據結構