操作系統(tǒng)課件：04第四章 互斥同步與通訊1

1、第四章 互斥、同步與通訊并發(fā)進程(concurrent processes)進程互斥(mutual exclusion)進程同步(synchronization)進程高級通訊(communication)4.1并發(fā)進程4.1.1前趨圖的定義前趨圖（precedence graph）有向無環(huán)圖，圖中每個結點表示一個語句、一個計算步驟、或一個進程。結點間的有向邊表示偏序或前趨（precedence relation)關系“” 。=（Pi，Pj）| Pj啟動之前Pi必須已經(jīng)完成。（Pi，Pj）可記作PiPj, 稱Pi是Pj的前趨，Pj是Pi的后繼。在前趨圖中，沒有前趨的結點稱為初始結點，沒有后繼的結

2、點稱為終止結點。每個結點可以有一個權重(weight)，它可以表示該結點所包含的程序量或計算時間。4.1并發(fā)進程前趨圖的例子P1P2，P1P3，P1P4，P2P5，P3P5，P4P5，P4P6，P5P7，P6P714326574.1.2順序程序及其特性4.1.2.1 程序的順序執(zhí)行(1)內部順序性：對于一個進程來說，它的所有指令是按序執(zhí)行的。S1：a:=x+yS2：b:=a-zS3：c:=a+bS4：d:=c+5S1S2S3S44.1.2順序程序及其特性(2)外部順序性：對于多個進程來說，所有進程的活動是依次執(zhí)行的。例: 輸入(I)、計算(C)、打印(P)三個活動構成的進程，每個進程的內部活動

3、是順序的，即IiCiPi，多個進程的活動也是順序的。I1C1P1I2C2P24.1.2順序程序及其特性4.1.2.2順序程序特性: (1)連續(xù)性: 指令逐條執(zhí)行 (2)封閉性: 不受其它程序及外界因素影響 (3)可再現(xiàn)性: 結果與推進速度無關4.1.3 并發(fā)程序及其特性4.1.3.1 程序的并發(fā)執(zhí)行(1)內部并發(fā)性: 指一個程序內部的并發(fā)性。例：S1：a:=x+2；S2：b:=y+4；S3：c:=a+b；S4：d:=c+6；S5：e:=c-d；214354.1.3 并發(fā)程序及其特性4.1.3.1 程序的并發(fā)執(zhí)行(2)外部并發(fā)性: 指多個程序之間的并發(fā)性。I1I2I3I4C1C2C3C4P1P2

4、P3P44.1.3 并發(fā)程序及其特性不可再現(xiàn)性的例子進程P： 進程Q：A1: N:=0； B1: PRINT（N）；A2: N:=N+1； B2: N:=0；A3: GOTO A2； B3: GOTO B1；此例中進程P累積計數(shù)，進程Q將累計的結果打印出來。希望打印出的數(shù)是累計數(shù)的和。兩個進程并發(fā)執(zhí)行時有許多可能的交叉:如進程P循環(huán)5次進程Q循環(huán)1次，然后進程P又循環(huán)3次進程Q循環(huán)1次，則輸出結果是5，3；如進程P循環(huán)2次進程Q循環(huán)1次，然后進程P又循環(huán)6次進程Q循環(huán)1次，則輸出結果是2，6。兩次執(zhí)行結果完全不同。進程Q執(zhí)行完B1后被中斷，進程P對N執(zhí)行加1操作，然后進程Q執(zhí)行B2，在這種情況

5、下進程P的累計數(shù)將被丟失。4.1.3 并發(fā)程序及其特性4.1.3.2 并發(fā)程序的特性（1）間斷性：程序交叉執(zhí)行。（2）非封閉性：一個進程的運行環(huán)境可能被其它進程所改變，從而相互影響。（3）不可再現(xiàn)性：由于交叉的隨機性，并發(fā)程序的多次執(zhí)行可能對應不同的交叉，因而不能期望重新運行的程序能夠再現(xiàn)上次運行的結果。4.1.4 程序并發(fā)執(zhí)行的條件 在失去封閉性的條件下，保持可再現(xiàn)性。R(pi)=a1,a2,am表示程序pi在執(zhí)行期間所需讀取的所有變量的集合，稱為“讀集”；W(pi)=b1,b2,bn表示程序pi在執(zhí)行期間所需改變的所有變量的集合，稱為“寫集”。若有兩條語句c=a+b和v=c-1，則它們的“

6、讀集”和“寫集”分別為：R(c:=a+b)=a,b，R(v:=c-1)=cW(c:=a+b)=c，W(v:=c-1)=v4.1.4 程序并發(fā)執(zhí)行的條件若兩個程序p1，p2滿足如下條件，則能夠保持可再現(xiàn)性，因而可以并發(fā)執(zhí)行。該條件是1966年首先由Bernstein提出的，稱為Bernstein條件。 R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=4.1.4 程序并發(fā)執(zhí)行的條件例如，有如下四條語句： S1: a:=x+y S2: b:=z+1 S3: c:=a-b S4: w:=c+1R(S1)=x,y，R(S2)=z，R(S3)=a,b，R(S4)=cW(S1)=a，W(S2)

7、=b，W(S3)=c，W(S4)=w可見，R(S1)W(S2)R(S2)W(S1)W(S1)W(S2)=，因而S1和S2可以并發(fā)執(zhí)行；而S1 和S3不能并發(fā)執(zhí)行，因為W(S1)R(S3)=a；S2和S3也不能并發(fā)執(zhí)行，因為W(S2) R(S3)=b；同樣，S3和S4不能并發(fā)執(zhí)行，因為W(S3)R(S4)=c。4.1.5 與時間有關的錯誤例：圖書借閱系統(tǒng) （x:某種書冊數(shù)，設當前x=1.）終端1： 終端2：CYCLE CYCLE 等待借書者； 等待借書者； IF x=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; 借書 借書 End End Else

8、 無書 Else 無書 End End 12344.1.5 與時間有關的錯誤(Cont.)錯誤原因之1： 進程執(zhí)行交叉(interleave);錯誤原因之2： 涉及公共變量(x)。Remarks: 某些交叉結果不正確; 必須去掉導致不正確結果的交叉。4.2 進程互斥(mutual exclusion)4.2.1 共享變量與臨界區(qū)4.2.2 臨界區(qū)域與進程互斥4.2.3 進程互斥的實現(xiàn)4.2.4 多處理機環(huán)境下的互斥4.2.1 共享變量與臨界區(qū)域共享變量（shared variable）多個進程都需要訪問的變量。臨界區(qū)域（critical region）訪問共享變量的程序段。 一組公共變量CR1

9、CR2CRn.表示共享變量: shared 臨界區(qū)域: region do 語句例子：shared B:array0,.,n-1of integer; region B do region B do begin begin (訪問B） .（訪問B）. end; end; 4.2.2 臨界區(qū)域與進程互斥定義：多個進程不能同時進入關于同一組共享變量的臨界區(qū)域，否則可能發(fā)生與時間有關的錯誤，這種現(xiàn)象稱為進程互斥。二層涵義： （1）任何時刻最多只能有一個進程處于同一組共享變量的相同的臨界區(qū)域； （2）任何時刻最多只能有一個進程處于同一組共享變量的不同的臨界區(qū)域。Remarks: 互斥是相對于公共變量而

10、言的。嵌套臨界區(qū)域 shared x1,x2; shared y1,y2;region x1,x2 do region y1,y2 do begin begin . region y1,y2 do region x1,x2 do begin begin . . end end end; end;P1P24.2.3 進程互斥的實現(xiàn)FrameworkRepeat critical section remainder sectionUntil falseentry sectionexit section4.2.3 進程互斥的實現(xiàn)Requirements:mutual exclusion(互斥進入):

11、 一次只允許一個進程進入關于同一組公共變量的臨界區(qū)；Progress(空閑讓進): 臨界區(qū)空閑時，放行一個進入者；bounded waiting(有限等待): 一個想要進入臨界區(qū)的進程在等待有限個進程進入并離開臨界區(qū)后獲得進入臨界區(qū)的機會。4.2.3.1 進程互斥的軟件實現(xiàn)完全用程序實現(xiàn)，不需特殊硬件指令支持?？捎糜趩蜟PU和多CPU環(huán)境中。有忙式等待問題。Busy waiting“運行”或“就緒”嘗試1int turn; P0: P1:do do while (turn=1) ; while(turn=0); 臨界區(qū)代碼 臨界區(qū)代碼 turn=1; turn=0; 其余代碼 其余代碼whil

12、e(1); while(1);不滿足進展性: P0和P1必須交替進入臨界區(qū).嘗試2int flag2;P0: P1:Do do while (flag1) ; while (flag0); flag0=1; flag1=1; 臨界區(qū) 臨界區(qū) flag0=0; flag1=0; 其余代碼 其余代碼while(1); while(1);不滿足互斥性: flag0=flag1=0.嘗試3int flag2; (0,0)do do flag0=1; flag1=1; while (flag1); while(flag0); 臨界區(qū)代碼 臨界區(qū) flag0=0; flag1=0; 其余代碼 其余代碼wh

13、ile(1); while(1);不滿足進展性: flag0=flag1=1, 進程P1和進程P2都不能進入臨界區(qū). 嘗試4:int flag2;Int turn;P0:Do flag0=1; turn=1; while (flag1 & turn=1); 臨界區(qū) flag0=0; 其余代碼while(1);P1:Do flag1=1; turn=0; while (flag0 & turn=0); 臨界區(qū) flag1=0; 其余代碼while(1);Peterson算法Dekkel算法int flag2; (init 0)int turn; (0 or 1)do flag0=1; while

14、(flag1) if(turn=1) flag0=0; while (turn=1) skip; flag0=1; 臨界區(qū) turn=1; flag0=0; 其余代碼while(1);P0：do flag1=1; while(flag0) if(turn=0) flag1=0; while (turn=0) skip; flag1=1; 臨界區(qū) turn=0; flag1=0; 其余代碼while(1);P1：Lamport面包店算法問題描述：一個面包店，較小，一次只能進入一位顧客。算法思想：設置一個發(fā)號者，按0,1,2, 發(fā)號。想進入臨界區(qū)的進程抓號，抓到號之后按由小到大的次序依次進入。Pr

15、oblem: 兩個進程可能抓到相同的號。Why? 為保證抓到不同的號，需要互斥機制。Resolution: 若抓到相同的號，按進程編號依次進入。Definition: (a,b)(c,d) iff (ac)or(a=c and bd)Lamport面包店算法Boolean choosing0,n-1;（false)int number0,n-1; (0)Pi 進入：1. choosingi=true;2. numberi=maxnumber0,numbern-1+1;3. choosingi=false;4. For(j=0;jn;j+)5. While (choosingj) skip;6.

16、 While (numberj!=0)and7. (numberj,j)(numberi,i) skip;8. Lamport面包店算法Boolean choosing0,n-1;（false)Int number0,n-1; (0)Pi 進入：1. 2. numberi=maxnumber0,numbern-1+1;3. 4. For(j=0;jn;j+)5. 6. While (numberj!=0)and7. (numberj,j)(numberi,i) skip;8. (1)P1抓到1未賦值(3)P2進入臨界區(qū) (2)P2抓到1賦值(4)P1進入臨界區(qū) Lamport面包店算法(Con

17、t.)Pi離開： numberi=0：變量choosing的作用：P1：抓到1; P2：抓到1;P2進入后離開前P1進入,不滿足互斥性.滿足臨界區(qū)管理原則互斥性(mutual exclusion)多個進程競爭進入臨界區(qū)時, 抓到號且二元組(numberi,i)最小的進程獲準進入臨界區(qū), 其它進程將在第一個while循環(huán)或第二個while循環(huán)處等待, 因而滿足互斥性.進展性(progress)當僅有一個進程想進入臨界區(qū)時, 該進程可以立即進入; 當有多個進程想進入臨界區(qū)時，抓到號且二元組(numberi,i)最小的進程獲準進入, 因而滿足進展性.有限等待性(bounded waiting)對任意

18、一個想要進入臨界區(qū)的進程Pi, 設其抓到號碼為numberi, 按二元組(numberi,i)次序排在Pi之前的競爭進程數(shù)量是有限的, 在最壞情況下Pi將等待n-1個排在其前面的進程進入并離開臨界區(qū)后獲準進入臨界區(qū), 因而滿足有限等待性.Eisenberg/Mcguire算法enum flag0,n-1 (idle, want_in, in_cs); int turn; /0.n-1; 初始任意0 i turnn-1先于i先于iflagi=idle: 進程Pi不想進入臨界區(qū)flagi=want_in: 進程Pi想進入臨界區(qū)flagi=in_cs: 進程Pi想進入或已進入臨界區(qū)Eisenberg

19、/Mcguire算法Pi進入:Do flagi=want_in; j=turn; While (j!=i) If (flagj != idle) j=turn Else j=(j+1)% n; flagi=in_cs; j=0; While (jn)and(j=i or flagj!=in_cs) do j+;while (j!=n);turn=i;Eisenberg/Mcguire算法Pi離開：j=(turn+1)% n;While (flagj=idle) j=(j+1)% n;turn=j;flagi=idle;CS滿足臨界區(qū)管理原則互斥性僅當flagi=in_cs, 且對所有j!=i,

20、 flagj!=in_cs時, 進程Pi才進入臨界區(qū)域, 因而滿足互斥性.進展性臨界區(qū)空閑時, 排在序列turn, turn+1, , n-1,0,1, 2,turn-1最前面的申請進入臨界區(qū)的進程獲準進入臨界區(qū), 因而滿足進展性.有限等待性進程離開臨界區(qū)時,按循環(huán)次序turn+1, , n-1,0,1, 2,turn-1確定唯一一個競爭進程為其后繼, 所以一個進程最多等待n-1個進程進入并離開臨界區(qū)后一定能進入臨界區(qū), 因而滿足有限等待性.4.2.3.2 進程互斥的硬件實現(xiàn)1. 硬件提供“測試并建立”指令 int test_and_set(int *target) test_and_set=

21、target; *target=1; . 對一組公共變量，int lock;（初始=0); Pi進入：While test_and_set(&lock); Pi離開：lock=0;滿足互斥性，進展性，不滿足有限等待性。4.2.3.2 進程互斥的硬件實現(xiàn)滿足有限等待性：全局變量： int waitingn; int lock;局部變量：int j; int key; waitingi=1; key=1;While(waitingi&key) key=test_and_set(&lock);waitingi=0;臨界區(qū)J=(i+1)%n;While(j!=i)&(!waitingj) j=(j+1

22、)%n;If(j=i) lock=0;Else waitingj=0;其余部分4.2.3.2 進程互斥的硬件實現(xiàn)2. 硬件提供“交換”指令 void swap(int *a,*b:boolean) int temp: boolean; temp:=*a; *a:=*b; *b:=temp; ; 對一組公共變量：int lock (初始=0); 對一個進程空間：int key; Pi進入：key=1; do swap(&lock,&key) while (key=1); Pi離開：lock=0;4.2.3.2進程互斥的硬件實現(xiàn)Remarks：(1) test_and_set指令和swap指令是原

23、子的，不可中斷的(在單CPU情況下)。(2) test_and_set實際上是：將內存中一個單元的內容取出，再送一個新值。(3) swap實際上是：交換內存兩個單元的內容。4.2.3.2進程互斥的硬件實現(xiàn)3. 硬件提供“關中斷”和“開中斷”指令 關中斷 Critical Region 開中斷Remarks: (1) 沒有忙式等待問題; (2) 影響并發(fā)性; (3) 只在單CPU系統(tǒng)中有效(why?)。4.2.4 多處理機環(huán)境下互斥單CPU, 指令間交叉, test_and_set, swap指令是原子的;多CPU, 指令周期間交叉, test_and_set, swap指令不是原子的;4.2.

24、4 多處理機環(huán)境下互斥內存Word 1000initial: 0CPU1CPU2Bus1. Read 03. Write 1 2. Read 04. Write 14.2.4 多處理機環(huán)境下互斥TS指令，Swap指令: first lock the busbus request protocol: modern buses have these facilities earlier ones didnt4.2.4 多處理機環(huán)境下互斥do lock(bus); b = test_and_set(&lock); unlock(bus);while(b)lock=0;CR作業(yè) #2Consider

25、the following program:var blocked: array0.1of boolean; turn:0.1;procedure P(id:integer);begin repeat blockedid:=true; while turnid do begin while blocked1-id do nothing turn:=id end; blockedid:=false; until falseend;begin blocked0:=false; blocked1:=false; turn:=0; parbegin P(0); P(1) parend;end.This

26、 is a software solution to the mutual exclusion problem proposed by Hyman. Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was fooled on this one.4.3 進程同步4.3.1 進程同步的概念例：司機-售票員問題 司機活動： 售票員活動： do do 啟動車輛 關車門 正常行駛 售

27、 票 到站停車 開車門 while(1) while(1)4.3.1 進程同步的概念定義：一組進程，為協(xié)調其推進速度，在某些關鍵點處需要相互等待與相互喚醒，進程之間這種相互制約的關系稱為進程同步。P1:P2:synchronize后先4.3.2 進程同步機制定義：用于實現(xiàn)進程同步的工具稱為同步機制（synchronization mechanism）同步機制要求：描述能力夠用;可實現(xiàn);高效;使用方便.典型同步機制 信號燈與PV操作(semaphore and PV operations)管程(monitor)會合(rendezvous)條件臨界區(qū)(conditional critical re

28、gion)路徑表達式(path expression)事件(event,traditional UNIX)4.3.3 信號燈與PV操作E.W.Dijkstra, 1965.4.3.3.1 信號燈與PV操作的定義 Typedef semaphore struct int value; PCBpointer queue; ; semaphore s;Remarks:(1) semaphore is pre-defined data type,(2) s can be declared as needed, eg. semaphore s1,s2; 信號燈變量S.valueS.queueS.valu

29、eS.queuePCBPCBPCBVar S:semaphore;FIFOP操作原語P操作原語：Procedure P(var s:semaphore) s.value:=s.value-1; If s.value0 Then asleep(s.queue)Endasleep(s.queue):(1) 執(zhí)行此操作進程的PCB入s.queue尾（狀態(tài)改為等待）；(2) 轉處理機調度程序。 Primitive: a piece of code un-interruptibleV操作原語V操作原語：Procedure V(var s:semaphore) s.value:=s.value+1; If

30、 s.value=0;只能執(zhí)行P操作和V操作，所有其它操作非法。幾個有用的結論：當s.value=0時，s.queue為空；當s.value=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; 借書 借書 End End Else 無書; Else 無書; End End互斥例子：借書系統(tǒng)(revisited)Var mutex:semaphore; (initial value is 1)終端1： 終端2：CYCLE CYCLE 等待借書者； 等待借書者； P(mutex) P(mutex) IF x=1 Then IF x=1 Then Begin

31、 Begin x:=x-1; x:=x-1; V(mutex) V(mutex) 借書 借書 End End Else V(mutex);無書; Else V(mutex);無書; End End用信號燈實現(xiàn)進程同步 后動作先動作 P1:P2:用信號燈實現(xiàn)進程同步General Case:VAR S:semaphore; (initial value 0) P(S)后動作先動作 V(S)P1:P2:用信號燈實現(xiàn)進程同步例子：司機-售票員問題：司機活動： 售票員活動： Do Do 關車門 啟動車輛 正常行駛 售 票 到站停車 開車門 While(1) While(1)用信號燈實現(xiàn)進程同步例子：司

32、機-售票員問題：VAR s1,s2: semaphore; (initial value 0)司機活動： 售票員活動： Do Do P(S1) 關車門 啟動車輛 V(S1) 正常行駛 售 票 到站停車 P(S2) V(S2) 開車門 While(1) While(1)Classical synchronization problems1. Producers and consumers problem2. Readers and writers problem3. Dining philosophers problem4. Cigarette smokers problem5. Sleepy

33、barbers problemetc. 例1. 生產(chǎn)者/消費者問題預備知識：組合資源：若干相對獨立的資源構成的資源集合，其中每個相對獨立的資源稱為子資源。同種組合資源：相同類型子資源構成的組合資源。管理：Var S:semaphore; (初值=子資源個數(shù)）例子：2臺打印機 Var S:semaphore; S.value=2; 申請：P（S）； 釋放：V（S）；自動機描述210-1-2P(S)P(S)P(S)P(S)P(S)V(S) V(S) V(S) V(S) V(S) S.value=空閑資源數(shù) S.queue=空|S.value|=等待進程數(shù) 空閑資源數(shù)=0.P(S): 申請一臺打印機

34、, 分配, 空閑打印機減1P(S): 申請一臺打印機, 等待, 等待進程數(shù)加1 2自動機描述10-1-2P(S)P(S)P(S)P(S)P(S)V(S) V(S) V(S) V(S) V(S) S.value=空閑資源數(shù) S.queue=空|S.value|=等待進程數(shù) 空閑資源數(shù)=0.V(S): 釋放一臺打印機, 喚醒一個等待者, 打印機分給被喚醒進程, 等待進程數(shù)減1V(S): 釋放一臺打印機, 空閑打印機數(shù)量增1 例1. 生產(chǎn)者/消費者問題 0 1 k-1箱子，容量k B:Array0.k-1Of item生產(chǎn)者消費者生產(chǎn)物品放入B中B中取物品消費之環(huán)形緩沖區(qū)K-101in(in+1)m

35、od kout(out+1)mod k問題分析生產(chǎn)者活動： 消費者活動： do do 加工一件物品 箱中取一物品 物品放入箱中 消耗這件物品 while(1) while(1)資源：空位（同種組合） 資源：物品（同種組合）Var S1:semaphore; Var S2:semaphore; S1.value=k; S2.value=0;放前：P（S1） 取前：P（S2）放后：V（S2） 取后：V（S1）同步生產(chǎn)者活動： 消費者活動： Do Do 加工一件物品 P(S2) P(S1) 箱中取一物品 物品放入箱中 V(S1) V(S2) 消耗這件物品 While(1) While(1)對B和in

36、,out的互斥：Var mutex:semaphore; (mutex.value=1)互斥生產(chǎn)者活動： 消費者活動： Do Do 加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品 物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗這件物品 While(1) While(1)程序Program producers_consumers;Var B:Array0,k-1Of item; S1,S2,mutex:semaphore; in,out:0.k-1;Procedure producer cycle produce a pro

37、duct P(S1); P(mutex); Bin:=product; in:=(in+1)mod k; V(mutex); V(S2) endProcedure consumer cycle P(s2); P(mutex); x:=Bout; out:=(out+1)mod k; V(mutex); V(S1); consume x; end;程序Begin S1.value:=k; S2.value:=0; mutex.value:=1; in:=0; out:=0; Cobegin P1: producer; , Pm: producer; C1: consumer; , Cn: con

38、sumer; Coend;End.并發(fā)性提高策略生產(chǎn)者的共享變量： B, in消費者的共享變量： B, outin=out: 滿或空；滿時, P(S1)等待；空時, P(S2)等待Var mutex1,mutex2:semaphore; (init 1)生產(chǎn)者和消費者：不同時操作B的相同元素并發(fā)性提高策略生產(chǎn)者活動： 消費者活動： Repeat Repeat 加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品 物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗這件物品 Until false Until false例2.

39、讀者/寫者問題P. T. Courtois 1971Communication of the ACM, Vol.14, 667-669.ACM: Association for Computing Machinery解法1：寫者可能餓死解法2：寫者優(yōu)先例2. 讀者/寫者問題Problem Statement: 一組公共數(shù)據(jù)DB R1 Rm W1 . Wn要求：（1）R-R可以同時 （2）R-W不可同時 （3）W-W不可同時accessingSolution1: 不考慮R-R不互斥Var r_w_w:semaphore; (init value: 1)Reader： Writer: P(r_w_

40、w); P(r_w_w) 讀操作 寫操作 V(r_w_w); V(r_w_w)分析：（1）寫者活動正確；（2）R-R不能同時。改進：最先進入的R執(zhí)行P；最后離開的R執(zhí)行V；Solution2: 考慮R-R不互斥Var read_count:integer; (initial value is 0)Reader: read_count:=read_count+1; If read_count=1 Then P(r_w_w); 讀操作 read_count:=read_count-1; If read_count=0 Then V(r_w_w);問題：對Read_count操作的互斥問題。Solu

41、tion3: 正確解法Var mutex:semaphore; (initial value is 1) Reader: P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); 讀操作 P(mutex); read_count:=read_count-1; If read_count=0 Then V(r_w_w); V(mutex); 讀者等待在何處？ 讀者如何被喚醒？程序Program readers_writers;Var r_w_w: semaphore; mutex:semaphore;

42、 read_count: integer;procedure writer;begin P(r_w_w); write ops V(r_w_w)end;程序（Cont.）Procedure reader;begin P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); read ops P(mutex); read_count:=read_count-1; If read_count=0 Then V(r_w_w); V(mutex);end;程序（Cont.）begin read_count:

43、=0; r_w_w.value:=1; mutex.value:=1; cobegin r1: reader; ; rm: reader; w1: writer; ,; wn: writer coendend.分析：問題：讀者源源不斷，read_count不歸0，寫者會被餓死。策略：一旦有寫者等待，新到達讀者等待，正在讀的讀者都結束后，寫者進入。 Further improvement is left to interested students.例3. 哲學家就餐問題Dining Philosophers ProblemProposed and solved byE.W. Dijkstra,

44、 in 1965例3. 哲學家就餐問題Roomph0ph4ph3ph2ph1f0f4f3f2f1例3. 哲學家就餐問題Roomph0ph4ph3ph2ph1f0f4f3f2f1例3. 哲學家就餐問題哲學家活動：Do 思考 進食While(1)進食：需要“叉子”叉子：不同種組合資源哲學家活動（包含資源活動）Do 思考 取左叉，取右叉 進食 放左叉，放右叉While(1)死鎖情況：每位哲學家拿到左叉，等待右叉。例3. 哲學家就餐問題Roomph0ph4ph3ph2ph1f0f4f3f2f1死鎖預防策略死鎖解決方法：同時申請左、右兩把叉子（預先分配）。哲學家狀態(tài)描述（增加了hungry狀態(tài)）：Sta

45、te: Array0.4Of (thinking,hungry,eating);等待隊列設置（每個哲學家一個隊列）：Self: Array0.4Of semaphore; (initial value is 0);就餐條件測試測試I號哲學家是否具備進食條件：Procedure test(I:0.4) If (stateI=hungry) and (state(I-1)mod 5eating) and (state(I+1)mod 5eating) Then Begin stateI:=eating; V(selfI) end;Remark: 自測試不需要stateI=hungry, 但測試左鄰

46、右舍需要此條件。未考慮互斥問題I號哲學家活動：1. Repeat2. 思考3. stateI:=hungry;4. test(I);5. P(selfI);6. 取左叉，取右叉；7. 進食8. 放左叉，放右叉；9. stateI:=thinking;10 test(I-1)mod 5);11. test(I+1)mod 5)12.Until false;共享變量：state;臨界區(qū)域：3-4, 9-11Var mutex:semaphore;(1)考慮互斥問題I號哲學家活動：1. Repeat2. 思考3. P(mutex);4. stateI:=hungry;5. test(I);6. V(

47、mutex); 7. P(selfI);8. 取左叉，取右叉；9. 進食10. 放左叉，放右叉；11. P(mutex);12. stateI:=thinking;13 test(I-1)mod 5);14. test(I+1)mod 5);15. V(mutex)16.Until false;問題餓死情況： 某哲學家左右鄰居至少有一個處于eating狀態(tài)。程序Program dining_philosophersvar state:array0.4of (thinking,hungry,eating); self:array0.4of semaphore; mutex:semaphore;p

48、rocedure test(I:0.4)begin if (stateI=hungry)and (state(I-1)mod 5eating)and (state(I+1)mod 5eating) then begin stateI:=eating; V(selfI) endend;程序(Cont.)Procedure philosopher(I:0.4)begin cycle thinking P(mutex); stateI:=hungry; test(I); V(mutex); P(selfI); pick_up_fork(I);pick_up_fork(I+1)mod 5); Eati

49、ng; put_down_fork(I);put_down_fork(I+1)mod 5); P(mutex); stateI:=thinking; test(I-1)mod 5); test(I+1)mod 5); V(mutex); endend 程序(Cont.)程序(Cont.)Procedure initVar i:integer;begin for i:=0 to 4 do begin stateI:=thinking; selfI.value:=0 end; mutex.value:=1;end;程序(Cont.)begin init; cobegin philosopher(0

50、); philosopher(4); coend;End.例3. 哲學家就餐問題Roomph0ph3ph3ph2ph1f0f4f3f2f1例3. 哲學家就餐問題Roomph0ph4ph3ph2ph1f0f4f3f2f1例4. 吸煙者問題Cigarette Smokers ProblemPatil S. S. Limitations and Capabilities of Dijkstras semaphore primitives for coordination among processes. MIT project MAC Computation Structure Group Memo

51、 57, MIT, Cambridge, Mass, 1977.吸煙者問題-problem statement3 supplier processes: X: supplies tobacco and match; Y: supplies match and wrapper; Z: supplies wrapper and tobacco.3 smoker processes: A: possess tobacco; B: possess match; C: possess wrapper.(1) only one of X,Y,Z can supply at a time;(2) X,Y,Z

52、 can proceed only after consumption.Traditional semaphore:Var t,m,w,s:semaphore; (0,0,0,1)Process X process Y process Z P(s); P(s); P(s); V(t); V(m); V(w); V(m); V(w); V(t);Process A Process B process C P(m); P(w); P(t); P(w); P(t); P(m); smoke; smoke; smoke; V(s); V(s); V(s);Simultaneous P-operatio

53、nSP(S1,t1,d1;Sn,tn,dn);if S1=t1 and and Sn=tn then for I:=1 to n do Si:=Si-di endforelse (1) place the executing process in the waiting queue for the first Si with Siti, (2)and set the program counter to the beginning of the SP operation so that all conditions will be reexamined when the process is

54、reactivated. Simultaneous V-operationSV(S1,d1;Sn,dn) for(i=1; i0) countb-; V(qb);else if(countc0) countc-; V(qc); else if(counta0) counta-; V(qa); else free=1;V(mutex) 例8. 系統(tǒng)與網(wǎng)絡打印機問題設有網(wǎng)絡打印機和系統(tǒng)打印機各一臺。網(wǎng)絡打印機由網(wǎng)絡用戶使用；系統(tǒng)打印機一般由系統(tǒng)用戶使用，但當其空閑時也可由網(wǎng)絡用戶使用。試用信號燈與PV 操作實現(xiàn)對兩臺打印機的管理。變量定義int sys_free, net_free; (1,1)i

55、nt sys_wait, net_wait; (0,0)semaphore sys_q, net_q; (0,0)semaphore mutex; (1)例8. 系統(tǒng)與網(wǎng)絡打印機問題sys_apply /系統(tǒng)用戶申請 P(mutex);L1: If(sys_free) sys_free=0; V(mutex); else sys_wait+; V(mutex); P(sys_q); goto L1; net_apply /網(wǎng)絡用戶申請 P(mutex);L2: if(net_free) net_free=0; V(mutex); return(net); else if(sys_free) s

56、ys_free=0; V(mutex); return(sys); else net_wait+; V(mutex); P(net_q); goto L2; 例8. 系統(tǒng)與網(wǎng)絡打印機問題sys_return /歸還系統(tǒng)打印機 P(mutex); sys_free=1; if(sys_wait0) sys_wait-; V(sys_q); else if(net_wait0) net_wait-; V(net_q); else V(mutex); net_return /歸還網(wǎng)絡打印機 P(mutex); net_free=1; if(net_wait0) net_wait-; V(net_q)

57、; else V(mutex); 例9. 2009研究生入學考試題三個進程P1、P2、P3互斥使用一個包含N(N0)個單元的緩沖區(qū)。P1每次用produce()生成一個正數(shù)并用put()送入緩沖區(qū)某一空閑單元中；P2每次用getodd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計奇數(shù)個數(shù)； P3每次用geteven()從該緩沖區(qū)中取出一個偶數(shù)并用counteven()統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)三個進程的同步與互斥活動，并說明所定義信號量的含義。例9. 2009研究生入學考試題變量定義semaphore empty; (init N)semaphore odd, even; (i

58、nit 0)semaphore mutex; (init 1)例9. 2009研究生入學考試題main() process P1 do n=produce(); P(empty); P(mutex); put(); V(mutex); if(n%2=0) V(even); else V(odd); while(true) process P2 do P(odd); P(mutex); getodd(); V(mutex); V(empty); countodd(); while(true) process P3 do P(even); P(mutex); geteven(); V(mutex)

59、; V(empty); counteven(); while(true) 例10. 寺廟問題某寺廟有老和尚、小和尚若干。廟內有一水缸，由小和尚提水入缸，供老和尚飲用。水缸可容納30桶水，每次入水、取水僅為一桶，不可同時進行。水取自同一井中，井口狹窄，每次只能容納一個水桶取水。設有5只水桶，老和尚與小和尚共用。試用信號燈與PV操作給出老和尚和小和尚的活動。例10. 寺廟問題變量定義semaphore empty; (30) /水缸容量semaphore full; (0) /當前水量semaphore bucket; (5) /水桶數(shù)semaphore mutex_bigjar;semaphor

60、e mutex_well; 例10. 寺廟問題Young_monk() do P(empty); P(bucket); 走到井邊; P(mutex_well); 井中取水; V(mutex_well); 走到寺廟; P(mutex_bigjar); 水入缸中; V(mutex_bigjar); V(bucket); V(full); while(1)old_monk() do P(full); P(bucket); P(mutex_bigjar); 缸中取水; V(mutex_bigjar); 喝水; V(bucket); V(empty); 4.3.4 條件臨界區(qū)Conditional Cr