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

1、第四章 互斥、同步與通信4.1 并發(fā)進程 ( Concurrent Processes )4.2 進程互斥 ( Mutual Exclusion )4.3 進程同步 ( Synchronization )4.4 進程高級通信 ( Communication )4.5 系統(tǒng)舉例4.1 并發(fā)進程4.1.1 前驅(qū)圖的定義定義：前驅(qū)圖是一個有向無環(huán)圖。 圖中每個結(jié)點表示一條語句、一個計算步驟或一個進程。 結(jié)點間的有向邊表示偏序或前驅(qū)關(guān)系“”，關(guān)系 =(Pi,Pj)|Pi必須在Pj啟動之前已經(jīng)完成 (Pi,Pj) 記作PiPj，稱Pi是Pj的前驅(qū)，Pj是Pi的后繼。 前驅(qū)圖中，沒有前驅(qū)的結(jié)點稱為初始節(jié)點

2、； 沒有后繼的結(jié)點稱為終止節(jié)點。 每個結(jié)點可以有權(quán)重，表示該結(jié)點的程序量或計算時間。偏序關(guān)系：具有反身性、反對稱性、傳遞性。4.1.1 前驅(qū)圖的定義例. 對如下前驅(qū)關(guān)系： P1P2 , P1P3 , P1P4 , P2P5 , P3P5 , P4P5 , P4P6 , P5P7 , P6P7 , P6P8 前驅(qū)圖如下：P1P4P3P2P5P6P7P8無前驅(qū)關(guān)系的程序段可以并發(fā)執(zhí)行程序的順序性內(nèi)部順序性: 對一個進程來說，所有指令順序執(zhí)行； 如有程序:S1: a:= x+y ;S2: b:= a-z ;S3: c:= a+b ;S4: d:=c+5 ;外部順序性: 多個進程依次執(zhí)行（P82：圖4

3、-3 ）。4.1.2 順序程序及其特性該程序的內(nèi)部順序性的前驅(qū)圖為： 順序程序設(shè)計的特性連續(xù)性: 一個程序的指令連續(xù)執(zhí)行，不會夾雜其它程序的指令；封閉行: 程序執(zhí)行過程中獨占系統(tǒng)資源，不受其它程序影響；可再現(xiàn)性: 給定初始條件，程序任意次執(zhí)行得到相同結(jié)果。S1S2S3S4程序的并發(fā)執(zhí)行 內(nèi)部并發(fā)性: 指一個程序內(nèi)部的并發(fā)性； 如下程序段： S1: a := x+2; S2: b := y+4; S3: c := a+b; S4: d := c-6; S5: e := c+6; S6: f := c-e; 外部并發(fā)性: 多個程序的并發(fā)性。（P83：圖4-5）4.1.3 并發(fā)程序及其特性S1S2S

4、3S6S4S5內(nèi)部并發(fā)性的前驅(qū)圖：4.1.3 并發(fā)程序及其特性(Cont.)并發(fā)程序的特性 考慮P、Q兩個進程的并發(fā)執(zhí)行 進程 P 進程 Q A1：N = 0; B1: print(N); A2: N:= N+1; B2: N:= 0; A3: goto A2; B3: goto B1; 顯然：進程P、Q的不同并發(fā)執(zhí)行，可得到不同結(jié)果。并發(fā)程序的特性：交 叉 性: 并發(fā)執(zhí)行可能會有多種交叉，會產(chǎn)生不同結(jié)果；非封閉性: 進程運行環(huán)境會相互影響；不可再現(xiàn)性: 交叉運行的隨機性，會導致不同的運行結(jié)果。4.1.4 程序并發(fā)執(zhí)行的條件讀 集：R(Pi)=a1,a2,am 為Pi在執(zhí)行期間所引用的所有變量

5、的集合；寫 集：W(Pi)=b1,b2,bn 為Pi在執(zhí)行期間所修改的所有變量的集合。Bernstein條件：若程序（段）P1和P2滿足如下條件： R(P1) W(P2) R(P2) W(P1) W(P1) W(P2)= 則程序（段）P1和P2能夠保持可再現(xiàn)性，因而可以并發(fā)執(zhí)行。例：S1: a:=x-y; /* R(S1)=x,y,W(S1)=a */ S2: b:=z+1; /* R(S2)=z, W(S2)=b */ S3: v:=a+b; /* R(S3)=a,b,W(S3)=v */ S4: w:=v+1; /* R(S4)=v, W(S4)=w */P1和p2無前驅(qū)關(guān)系。Bernst

6、ein條件為可并發(fā)必要條件，不是充分條件。4.1.5 并發(fā)程序的表示設(shè) S1、S2、Sn 為 n 個程序段，則用如下形式的并發(fā)語句： cobegin S1; S2; ; Sn coend; 或 parbegin S1; S2; ; Sn parend;表示S1、S2、Sn 的并發(fā)執(zhí)行。遇到并發(fā)語句，系統(tǒng)會同時創(chuàng)建n個進程（線程）分別執(zhí)行S1、S2、Sn 。4.1.6 與時間有關(guān)的錯誤終端2: 進程P2do 等待借書者； if x = 1 x := x 1 ; 借書 else 無書 while(1);終端1: 進程P1do 等待借書者 ； if x = 1 x := x 1 ; 借書 else

7、無書 while(1);例：圖書借閱系統(tǒng) (x: 某種書冊數(shù), 設(shè)當前 x = 1) 錯誤原因： 進程執(zhí)行交叉(interleave) ; 涉及公共變量(x)。 Remarks: 某些交叉結(jié)果不正確 ; 必須去掉導致不正確結(jié)果的交叉。4.1.6 與時間有關(guān)的錯誤(Cont.)4.2 進程互斥4.2.1 共享變量與臨界區(qū)4.2.2 臨界區(qū)域與進程互斥4.2.3 進程互斥的實現(xiàn)4.2.4 多處理機環(huán)境下的互斥mutual exclusion 共享變量 (shared variable) 兩個或兩個以上的進程都需要訪問的變量。 臨界區(qū)域 (Critical Region)訪問共享變量的程序段。4.2

8、.1 共享變量與臨界區(qū)一組共享變量CR1CR2CRn 臨界資源(Critical resource)一次只允許一個進程使用的資源。 共享變量與臨界區(qū)的表示共享變量: shared 臨界區(qū)域: region do 也叫臨界語句。4.2.1 共享變量與臨界區(qū)(Cont.)例子：shared x1,x2；shared y1,y2; region x1,x2 do region y1,y2 do 4.2.2 臨界區(qū)域與進程互斥進程互斥: 兩個或兩個以上進程不能同時進入 關(guān)于同一組共享變量的臨界區(qū)域， 否則可能發(fā)生與時間有關(guān)的錯誤， 這種現(xiàn)象稱為進程互斥。含 義: 任何時刻最多只能有一個進程 處于同一組

9、共享變量的相同的臨界區(qū)域； 任何時刻最多只能有一個進程 處于同一組共享變量的不同的臨界區(qū)域。 Remarks: 互斥是相對于公共變量而言的。P1進程：shared x1 , x2 ;region x1 , x2 do region y1 , y2 do . . ; 4.2.2 臨界區(qū)域與進程互斥(Cont.)嵌套臨界區(qū)域(可能導致死鎖)P2進程：shared y1 , y2 ;region y1 , y2 do region x1 , x2 do . ;P1, P2在此處等待,出現(xiàn)死鎖臨界區(qū)框架(Framework)Do critical section remainder code whil

10、e(1);entry sectionexit section4.2.3 進程互斥的實現(xiàn)實現(xiàn)互斥就是要編寫entry section和exit section兩部分。4.2.3 進程互斥的實現(xiàn)(Cont.) 臨界區(qū)管理原則 互斥性 (mutual exclusion) 任一時刻至多只能有一個進程 處于關(guān)于同一組共享變量的臨界區(qū)中。 進展性 (progress) 臨界區(qū)空閑時，保證執(zhí)行entry section和exit section 的進程參與下一個進入臨界區(qū)進程的決策，該決策應(yīng)該 在有限時間完成。 有限等待性 (bounded waiting) 一個想要進入臨界區(qū)的進程 應(yīng)當在有限等待時間內(nèi)

11、獲得進入臨界區(qū)的機會。4.2.3 進程互斥的實現(xiàn)(Cont.) 臨界區(qū)調(diào)度原則： 當關(guān)于某組共享變量的所有臨界區(qū)空閑時， 一個要求進入該臨界區(qū)的進程應(yīng)當能立即進入; 當關(guān)于某組共享變量的某一臨界區(qū)被占用, 所有要求進入關(guān)于該組共享變量的臨界區(qū)的 進程應(yīng)當?shù)却? 當一個進程離開某臨界區(qū)時， 應(yīng)當允許某等待進入相關(guān)臨界區(qū)的進程進入。進程互斥的可以軟件方法實現(xiàn)，也可以硬件方法實現(xiàn)。4.2.3.1 進程互斥的軟件實現(xiàn) 完全用程序?qū)崿F(xiàn), 不需特殊硬件指令支持 ; 可用于單 CPU 和多 CPU 環(huán)境中 ; 有忙式等待問題。Busy waiting“運行”或“就緒”4.2.3.1 進程互斥的軟件實現(xiàn)(1)

12、 Dekker互斥算法int flag 2 ; /*初值=0；flagi1表示進程 P i 想進入或已進入臨界區(qū)*/int turn; /*初值為0或1; 表示進程進入臨界區(qū)輪流次序*/P0進程：do flag0=1; whlie (flag1) do if(turn=1) flag0=0; whlie(turn=1) do continue; flag0=1; 臨界區(qū)； turn=1;flag0=0; 其余代碼； while(1)P1進程：do flag1=1; whlie (flag0) do if(turn=0) flag1=0; whlie(turn=0) do continue; f

13、lag1=1; 臨界區(qū)； turn=0;flag1=0; 其余代碼； while(1)實現(xiàn)兩個進程互斥的軟件解法。4.2.3.1 進程互斥的軟件實現(xiàn)(2) Peterson互斥算法int flag 2 ; /*初值=0；表示進程是否在臨界區(qū)*/int turn; /*初值為0或1; 表示進程進入臨界區(qū)輪流次序*/P0進程：do flag0=1; turn=1; whlie (flag1&turn=1) do continue; 臨界區(qū)； flag0=0; 其余代碼； while(1)實現(xiàn)兩個進程互斥的軟件解法。P1進程：do flag1=1; turn=0; whlie (flag0&turn

14、=0) do continue; 臨界區(qū)； flag1=0; 其余代碼； while(1) 4.2.3.1 進程互斥的軟件實現(xiàn) (3) Lamport 面包店算法 問題描述： 顧客進面包店先抓號(號可能重復(fù)) ; 按號碼從小到大次序進店買面包 ; 如號重復(fù)，按顧客名字的字典順序進入。 (假定名字不重復(fù)) 算法思想： 進程進入臨界區(qū)前先選號 ; 選號后按號從小到大的次序依次進入臨界區(qū) ; 若不同進程選到相同的號，按進程編號依次進入。Definition: (a,b)(c,d) if (ac)or(a=c and bd) 4.2.3.1 進程互斥的軟件實現(xiàn)(3) Lamport 面包店算法(Con

15、t.)int choosing n = 0, 0, 0, , 0 ; /* n 個進程 */int number n = 0, 0, 0, , 0 ;算法4.1 Pi 進入：choosing i = 1 ;number i = max number0, , numbern-1 +1;choosing i = 0 ;for ( j = 0 ; j n ; j+ ) while ( choosing j ) do continue; while ( number j != 0 ) & (number j , j ) ( number i , i ) do continue; numberi = 0

16、; /Pi 退出臨界區(qū) C R例: P1選到1 ; P2選到 1 ; P3選到2 ; 正確次序：P1, P2, P3 變量choosing的作用 ; for 循環(huán)中的兩個while 語句有忙式等待的情況 ; 不進入等待狀態(tài)的等待稱為忙式等待(busy waiting). 處于忙式等待狀態(tài)的進程, 其實際狀態(tài)為運行或就緒。 4.2.3.1 進程互斥的軟件實現(xiàn)(3) Lamport 面包店算法(Cont.) 4.2.3.1 進程互斥的軟件實現(xiàn)(4) Eisenberg-Mcguire 算法數(shù)據(jù)結(jié)構(gòu)：enum state idle, want_in, in_cs ;enum state flag n

17、 ; /* n 個進程*/int turn ; /* 取值 0 n-1 , 初值任意 */flagi = idle: 進程 Pi 空閑，不想進入臨界區(qū)；flagi = want_in: 進程 Pi 想進入臨界區(qū);flagi = in_cs: 進程 Pi 想進入或已進入臨界區(qū);進程 Pi 進入臨界區(qū)算法思想（entry section）：Step1: 檢查編號為 turn, , n-1, 0, 1, , i-1的優(yōu)先于Pi 的進程是否空閑(idle), 如不空閑則轉(zhuǎn) Step1；Step2: 依次檢查編號從 0 i-1, i+1, , n-1 的進程是否 在臨界區(qū), 如有任何一個進程在臨界區(qū),

18、則轉(zhuǎn) Step1;Step3: 進入臨界區(qū) turn i .先于 i先于 i0 i turnn-1 4.2.3.1 進程互斥的軟件實現(xiàn)(4) Eisenberg/Mcguire 算法(Cont.)進程 Pi 退出臨界區(qū)算法思想（exit section）：Step1找下一個競爭進程 從turn+1 (即i+1)開始 找到一個非空閑 ( idle ) 的進程 Pj ;Step2指定下一個競爭進程 j turn = j ;Step3進程 Pi 退出臨界區(qū) flag i = idle .注意：Step1中, 可能找到的 j = i, 即除進程 Pi 之外, 其它進程都空閑。但由于 Step3 中將

19、Pi 的進程 狀態(tài)置為空閑 idle , 能保證其它進程進入臨界區(qū)。 4.2.3.1 進程互斥的軟件實現(xiàn)(4) Eisenberg/Mcguire 算法(Cont.)Pi 進入:do flag i = want_in ; j = turn ; while ( j != i ) do if (flag j != idle ) j = turn ; else j = (j+1)%n ; flag i = in_cs ; j = 0 ; while (jn)&(j = i|flagj!=in_cs ) do j+; while ( j ! = n ) ;turn = i ;C RPi 離開：j =

20、( turn + 1 ) % n ;while ( flag j = idle ) do j = ( j + 1 ) % n;turn =j ; flag i = idle ; 4.2.3.1 進程互斥的軟件實現(xiàn)(4) Eisenberg/Mcguire 算法(Cont.)Pi進入的Step1.Pi進入的Step2.4.2.3.2 進程互斥的硬件實現(xiàn)(1) 硬件提供“測試并設(shè)置”指令 int test_and_set ( int *target ) int temp; temp = *target ; *target = 1; return ( temp ) ; 4.2.3.2 進程互斥的硬件

21、實現(xiàn)(Cont.) 進程Pi : while ( test_and_set ( &lock ) do continue ; C Rlock = 0 ; TS指令互斥的實現(xiàn)對一組公共變量，定義全局變量 int lock = 0 ; 不滿足有限等待性4.2.3.2 進程互斥的硬件實現(xiàn)(Cont.)int waitingn=0,0,0, lock=0; /*全局變量 */ 進程Pi : int key; /*局部變量*/waitingi=1; key=1;while(waitingi&key) key=test_and_set(&lock);waitingi=0;C Rj=(i+1)%n;while

22、 (j!=i)&(!waitingj) do j=(j+1)%n;if (j=i) lock=0; else waitingj=0; 滿足有限等待性的TS互斥實現(xiàn)(2) 硬件提供“交換”指令 void swap( int *a,*b) int temp; temp = *a ; *a = *b ; *b = temp ; 4.2.3.2 進程互斥的硬件實現(xiàn)(Cont.)4.2.3.2 進程互斥的硬件實現(xiàn)(Cont.) SWAP指令互斥的實現(xiàn) 對每一組公共變量，定義全局變量 int lock=0; 對要進入臨界區(qū)的進程，定義局部變量 int key;lock = 0 ; 進 程 Pi : key

23、 = 1 ; do swap ( &lock, &key ) ; while ( key = 1 ) ;C R不滿足有限等待性4.2.3.2 進程互斥的硬件實現(xiàn)(Cont.) 滿足有限等待性的SWAP互斥實現(xiàn)int waitingn=0,0,0, lock=0; /*全局變量 */ 進程Pi : int key; /*局部變量*/waitingi=1; key=1;while(waitingi&key) swap(&lock,&key);waitingi=0;C Rj=(i+1)%n;while (j!=i)&(!waitingj) do j=(j+1)%n;if (j=i) lock=0;

24、else waitingj=0; Remarks：test_and_set 指令和 swap 指令是原子的， 不可中斷的 (在單 CPU 情況下) ;test_and_set 和 swap 實現(xiàn)互斥的方法 都存在忙式等待 ;4.2.3.2 進程互斥的硬件實現(xiàn)(Cont.)(3) 硬件提供“關(guān)中斷”和“開中斷”指令 關(guān)中斷 ( CLI ) Critical Region 開中斷 ( STI )Remarks: 開/關(guān)中斷只在單 CPU 系統(tǒng)中有效; 影響并發(fā)性; 效率高，無忙式等待，簡單易行。4.2.3.2 進程互斥的硬件實現(xiàn)(Cont.)4.2.4 多處理機環(huán)境下互斥 問題多CPU系統(tǒng)中, 關(guān)

25、中斷對解決互斥無效;單CPU系統(tǒng)中 指令間交叉，TS, swap 指令是原子的； 多CPU系統(tǒng)中 指令周期間交叉， TS、swap 指令占多個指令周期， 不能保證其原子性， 不同 CPU 上運行的進程 可能同時訪問一個單元。4.2.4 多處理機環(huán)境下互斥(Cont.)問題例 多CPU下，test_and_set 不能解決互斥。內(nèi)存CPU2initial: 0Bus4. Write 13. Write 1 2. Read 01. Read 0lockCPU1 First lock the bus： 在執(zhí)行 TS 指令和 Swap 指令前, 首先鎖總線(Bus-locking), 以保證指令的原子

26、性; 執(zhí)行完指令后再總線解鎖(Bus-unlocking). bus request protocol: modern buses have these facilities. earlier ones didnt. 4.2.4 多處理機環(huán)境下互斥(Cont.)2. 多CPU互斥的解決2. 多CPU互斥的解決(Cont.) 多CPU互斥算法： b = 1 ; while ( b ) lock ( bus ) ; b = test_and_set ( &lock ) ; unlock ( bus ) ; lock=0;CR4.2.4 多處理機環(huán)境下互斥(Cont.)自旋鎖(spin-lock):

27、 忙式等待鎖稱為自旋鎖。Assignment #1進程切換時,下降進程的現(xiàn)場信息 為何不能保存在系統(tǒng)棧中, 而必須傳送到 PCB 中？3.Consider the following program:int blocked 2 ;int turn ; /* 取值 0 和 1 */void P ( int id ) do blocked id = 1 ; while ( turn != id ) do while ( blocked 1- id ) do continue; turn = id ; blocked id = 0 ; whlie ( 1 ) ; void main ( ) bloc

28、ked 0 = 0 ; blocked 1 = 0 ; turn = 0 ; parbegin P(0); P(1) parend ; Assignment #1(Cont.)This is a software solution to the mutual exclusion problem proposed by Hyman. It is interesting to note that even the Communication of the ACM was fooled on this one.Find a counter example to demonstrate that th

29、is solution is incorrect.3.Consider the following program:int blocked 1 ;int turn ; /* 取值 0 和 1 */void P ( int id ) do blocked id = 1 ; while ( turn != id ) do while ( blocked 1- id ) do continue; turn = id ; blocked id = 0 ; whlie ( 1 ) ;Assignment #1(Cont.)當 P(1) 執(zhí)行完第二個 while, 還未執(zhí)行turn = id ; P(0)

30、 執(zhí)行到第一個 while。此時：turn=0，P(0) 能進入CS；而 P(1) 執(zhí)行完turn = id 后，外層while條件為假， P(1)也 能進入 CS . P(1)執(zhí)行完第二個 while,還未執(zhí)行 turn = id ;P(0)執(zhí)行到第一個 while4.3.1 進程同步的概念例：司機售票員問題 關(guān)門后才能啟動汽車 ; 到站停車后方能開車門。4.3 進程同步司機活動：do 啟動車輛； 正常行駛； 到站停車； while (1)售票員活動：do 關(guān)車門； 售 票； 開車門； while (1)4.3.1 進程同步的概念(Cont.)定義：一組進程，為協(xié)調(diào)其推進速度，在某些關(guān)鍵點處

31、需要相互等待與相互喚醒，進程之間這種相互制約的關(guān)系稱為進程同步，簡稱同步(Synchronization)。定義：一組進程，如果它們單獨不能正常運行，但并發(fā)可以正常運行，稱這種現(xiàn)象為進程合作(Cooperation)。參與合作的進程稱作合作進程(Cooperating Process)。P1:synchronize先P2:后4.3.2 進程同步機制 synchronization mechanism定義: 用于實現(xiàn)進程同步的工具稱為同步機制 , 亦稱為同步設(shè)施。同步機制要求: 描述能力夠用 ; 可實現(xiàn) ; 高效 ; 使用方便。典型同步機制信號量與P/V操作 Semaphore and P/V

32、operations條件臨界區(qū) conditional critical region 管程 (monitor)會合 (rendezvous)路徑表達式 (path expression)事 件 (traditional UNIX)4.3.2 進程同步機制(Cont.)4.3.3 信號量與P/V操作 E.W.Dijkstra, 1965. 最成功、最早的進程同步機制 ; 信號量是一種類型定義，其變量可以描述進程隊列、 資源以及進程互斥、同步等狀況； P/V 操作是針對信號量變量定義的兩種操作原語 (類似于Atomic指令) ; 一段不可間斷執(zhí)行的程序稱為原語 (Primitive) ; 信號量

33、變量可以看作共享變量，P/V 操作是該共享 變量的臨界區(qū)； 對 P/V 操作的互斥通常采用開/關(guān)中斷的方法來實現(xiàn)。4.3.3.1 信號量與P/V操作的定義 信號量類型的定義： typedef struct int value ; pointer_to_PCB queue ; semaphore ; semaphore s ; Remarks: semaphore is pre-defined data type; Variable s can be declared as needed . 信號量變量及進程隊列例：semaphore S ;4.3.3.1 信號量與P/V操作的定義(Cont.)

34、S.valueS.queueS.valueS.queuePCBPCBPCBFIFOP 操作原語: void P ( semaphore *s ) s - value - ; if (s - value queue) ; asleep( s- queue): 執(zhí)行此操作進程的 PCB 入 s - queue 的隊尾 (狀態(tài)改為等待) ; 轉(zhuǎn)處理機調(diào)度程序。 Primitive: a piece of code un-interruptible4.3.3.1 信號量與P/V操作的定義(Cont.)V 操作原語： void V ( semaphore *s ) s - value + ; if (s

35、 - value queue) ; wakeup(s - queue) : s - queue 鏈頭 PCB 出等待隊列， 進入就緒隊列(狀態(tài)改為就緒)。4.3.3.1 信號量與P/V操作的定義(Cont.)注意：P / V 操作的參數(shù) S 是指針型信號量，在調(diào)用 P / V 操作時其參數(shù)應(yīng)該用 &S 取地址的形式，為簡便起見，后面只用 S 的形式直接調(diào)用。原 語：一段不可間斷執(zhí)行的程序稱為原語。規(guī)定和結(jié)論對于信號燈變量的規(guī)定: 必須置一次初值, 只能置一次初值, 初值0 ; 只能執(zhí)行P操作和V操作, 所有其它操作非法。幾個有用的結(jié)論: 當 s.value 0 時, s.queue 為空 ;

36、當 s.value 0 時 , s.value為隊列 s.queue 的長度 ; 當 s.value初1 時, 實現(xiàn)進程互斥 ; 當 s.value初0 時, 可以實現(xiàn)進程同步; 當 s.value初非1 的正整數(shù)時, 用于管理同種組合資源;4.3.3.1 信號量與P/V操作的定義(Cont.)用“開關(guān)中斷”實現(xiàn)的PV操作4.3.3.2 信號量與P/V操作的實現(xiàn)void P(semaphore *s) disable interrupt; /* 關(guān)中斷 */ s-value-; if (s-valuequeue; enable interrupt; /* 開中斷 */ goto CPU dis

37、patcher; else enable interrupt; /* 開中斷 */asleep( )4.3.3.2 信號量與P/V操作的實現(xiàn)void V(semaphore *s) disable interrupt; /* 關(guān)中斷 */ s-value+; if (s-valuequeue; place this process on ready list; enable interrupt; /* 開中斷 */用“開關(guān)中斷”實現(xiàn)的PV操作用“測試并設(shè)置”實現(xiàn)的PV操作4.3.3.2 信號量與P/V操作的實現(xiàn)void P(semaphore *s) while(TS(&(s-flag); /

38、* 如果有s的P操作則等待 */ s-value-; if (s-valuequeue; s-flag=0; /* s的P操作結(jié)束 */ goto CPU dispatcher; else s-flag=0; /* s的P操作結(jié)束 */4.3.3.2 信號量與P/V操作的實現(xiàn)void V(semaphore *s) while(TS(&(s-flag); /* 如果有s的V操作則等待 */ s-value+; if (s-valuequeue; place this process on ready list; s-flag=0; /* s的V操作結(jié)束 */用“測試并設(shè)置”實現(xiàn)的PV操作1.

39、用信號量實現(xiàn)進程互斥 問題描述：4.3.3.3 信號量與PV操作的應(yīng)用shared int x, y, z ;CR1 CR2 CRn 4.3.3.3 信號量與PV操作的應(yīng)用(Cont.)用信號量實現(xiàn)進程互斥(Cont.) 實現(xiàn)原理：semaphore mutex; ( 初值 mutex.value = 1 )P(mutex)CR1V(mutex)P(mutex)CR2V(mutex)P(mutex)CRnV(mutex)shared int x , y , z ;2. 用信號燈實現(xiàn)進程同步 問題描述：4.3.3.3 信號量與PV操作的應(yīng)用(Cont.) 后動作P1:P2: 先動作semapho

40、re S ; ( initial s.value = 0 ) 用信號量實現(xiàn)進程同步(Cont.) 實現(xiàn)原理：4.3.3.3 信號量與PV操作的應(yīng)用(Cont.) 后動作P1:P2: 先動作P ( S ) ;V ( S ) ;借書系統(tǒng)互斥的實現(xiàn):Semaphore mutex ; ( initial mutex.value = 1 )終端1：do 等待借書者; P (mutex) ; if (x = 1) x = x 1 ; V(mutex); 借書; else V(mutex);無書; while ( 1 )4.3.3.3 信號量與PV操作的應(yīng)用(Cont.)終端2：do 等待借書者； P (

41、mutex) ; if (x = 1) x = x 1 ; V(mutex) ; 借書 ; else V(mutex);無書; while ( 1 )4.3.3.3 信號量與PV操作的應(yīng)用(Cont.)例4-1: (同步例子)司機-售票員問題 司機活動： 售票員活動： do do 啟動車輛； 關(guān)車門； 正常行駛； 售 票； 到站停車； 開車門； while (1) while(1) 要求：（1）關(guān)門后才能啟動汽車； （2）到站停車后方能開車門；4.3.3.3 信號量與PV操作的應(yīng)用(Cont.)司機-售票員問題的同步實現(xiàn)： semaphore s1 , s2 ; ( initial value

42、 0 ) 司機活動： 售票員活動： do do P ( S1 ) ； 關(guān)車門； 啟動車輛； V ( S1 ) ； 正常行駛； 售 票； 到站停車； P ( S2 ) ； V ( S2 ) ； 開車門； while (1) while(1)Classical synchronization problems 例4-2. Producers and consumers problem 例4-3. Readers and writers problem 例4-4. 同種組合資源(3臺打印機)的管理 例4-5. Cigarette smokers problem例. Sleepy barbers pr

43、oblem4.3.3.3 信號量與P/V操作的應(yīng)用(Cont.)例4-2. 生產(chǎn)者/消費者問題預(yù)備知識：組合資源：若干相對獨立的資源構(gòu)成的資源集合, 其中每個相對獨立的資源稱為子資源。同種組合資源：相同類型子資源構(gòu)成的組合資源。同種組合資源的管理：semaphore S; ( 初值 = 子資源個數(shù))例子：2 臺打印機 semaphore S; 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.valu

44、e|=等待進程數(shù) 空閑資源數(shù)=0.P(S): 申請一臺打印機, 分配, 空閑打印機減1;P(S): 申請一臺打印機, 等待, 等待進程數(shù)加1。 例4-2. 生產(chǎn)者/消費者問題(Cont.)V(S): 釋放一臺打印機, 喚醒一個等待者, 打印機分給被喚醒進程, 等待進程數(shù)減1;V(S): 釋放一臺打印機, 空閑打印機數(shù)量增1 。自動機描述例4-2. 生產(chǎn)者/消費者問題(Cont.)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.箱子B，容量k it

45、em B k ;生產(chǎn)者生產(chǎn)物品放入B中B中取物品消費例4-2. 生產(chǎn)者/消費者問題 問題描述012k-1消費者 Producers and consumers problem，or bounded bufferproblem.環(huán)形緩沖區(qū)10K-1in(in+1)mod kout(out+1)mod k例4-2. 生產(chǎn)者/消費者問題(Cont.) 問題描述生產(chǎn)者活動： 消費者活動： do do 加工一件物品; 箱中取一物品; 物品放入箱中; 消耗這件物品; while ( 1 ) while ( 1 )例4-2. 生產(chǎn)者/消費者問題(Cont.)問題分析資源：箱子(同種組合) 資源：物品(同種組

46、合) semaphore S1 ; semaphore S2 ; 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 )例4-2. 生產(chǎn)者/消費者問題(Cont.)同步的實現(xiàn)對 B 和 in，out 的互斥：semaphore mutex ; ( mut

47、ex.value = 1 )例4-2. 生產(chǎn)者/消費者問題(Cont.)互斥的實現(xiàn)生產(chǎn)者活動： 消費者活動：do do 加工一件物品; P ( S2 ) ; P ( S1 ) ; P ( mutex ) ; P ( mutex ) ; 箱中取一物品; 物品放入箱中; V ( mutex ) ; V ( mutex ) ; V ( S1 ) ; V ( S2 ) ; 消耗這件物品; while ( 1 ) while ( 1 )例4-2. 生產(chǎn)者/消費者問題(Cont.)程 序itemType buffer k ;semaphore S1, S2, mutex;int in, out;void

48、producer ( ) while(1) produceItem(&item); P ( S1 ) ; P ( mutex ) ; buffer in = item ; in = ( in + 1 ) % k; V ( mutex ) ; V ( S2 ) ; void consumer ( ) while(1) P ( S2 ) ; P ( mutex ) ; x = buffer out ; out = ( out + 1 ) % k; V ( mutex ) ; V ( S1 ) ; ; while ( 1 ) ;void producer_consumer ( ) S1.value

49、= k ; S2.value = 0 ; mutex . value = 1 ; in = out = 0 ; fork ( producer, 0 ) ; , fork ( producer, m - 1 ) ; fork ( consumer, 0 ) ; , fork ( consumer, n - 1 ) ;例4-2. 生產(chǎn)者/消費者問題(Cont.)程 序例4-2. 生產(chǎn)者/消費者問題(Cont.)并發(fā)性提高策略生產(chǎn)者和消費者: 不操作buffer的相同分量生產(chǎn)者的共享變量: buffer in , in消費者的共享變量: buffer out , out并且 in = out :

50、滿或空,semaphore mutex1 , mutex2 ; ( init 1 )生產(chǎn)者活動： 消費者活動： do do 加工一件物品 P ( S2 ) ; P ( S1 ) ; P ( mutex2 ) ; P ( mutex1 ) ; 箱中取一物品 物品放入箱中; V ( mutex2 ) ; V ( mutex1 ) ; V ( S1 ) ; V ( S2 ) ; 消耗這件物品 while ( 1 ) while ( 1 )例4-2. 生產(chǎn)者/消費者問題(Cont.)并發(fā)性提高策略例4-3. 讀者/寫者問題P. T. Courtois 1971. Communication of th

51、e ACM, Vol.14, 667-669. ACM: Association for Computing Machinery要求: R R 可以同時; R W 不可同時; W W不可同時。Problem Statement: accessingReaders and writers problemR1RmW1Wn共享數(shù)據(jù)semaphore r_w_w ; ( init value: 1 )void reader ( ) void writer ( ) P ( r_w_w ) ; P ( r_w_w ) ; V ( r_w_w ) ; V ( r_w_w ) ; 例4-3. 讀者/寫者問題(

52、Cont.)Solution1: 不考慮R-R不互斥分 析: 不滿足要求 , 即 R R 不能同時。改 進: 最先進入的 R 執(zhí)行 P ; 最后離開的 R 執(zhí)行 V ;int readCount = 0 ; ( initial value is 0 )void reader ( ) readCount + ; if ( readCount = 1 ) P ( r_w_w ) ; read_count - ; if ( readCount = 0 ) V ( r_w_w ) ;問題：對 readCount 操作的互斥問題。例4-3. 讀者/寫者問題(Cont.)Solution2: 考慮 R-R

53、 不互斥semaphore mutex = 1 ; /* initial value is 1 */int readCount = 0 ; /* initial value is 0 */void reader ( ) P ( mutex ) ; readCount + ; if ( readCount = 1 ) P ( r_w_w ) ; V ( mutex ) ; P ( mutex ) ; readCount - ; if ( readCount = 0 ) V ( r_w_w ) ; V ( mutex ) ;例4-3. 讀者/寫者問題(Cont.)Solution2: 考慮 R-R

54、 不互斥void writer ( ) while (1) P ( r_w_w ) ; V ( r_w_w ) ; 例4-3. 讀者/寫者問題(Cont.) 程 序void reader ( ) while (1) P ( mutex ) ; readCount + ; if ( readCount = 1 ) P ( r_w_w ) ; V ( mutex ) ; P ( mutex ) ; readCount - ; if ( readCount = 0 ) V ( r_w_w ) ; V ( mutex ) ; 例4-3. 讀者/寫者問題(Cont.) 程 序int readCount

55、= 0 ;semaphore r_w_w . value = 1 ; semaphore mutex . value = 1 ;void reader_writer ( ) cobegin fork ( reader, 0 ) ; fork ( reader, m - 1 ) ; fork ( writer, 0 ) ; fork ( writer, n 1 ) ; coend例4-3. 讀者/寫者問題(Cont.) 程 序問 題: 讀者源源不斷， readCount 不歸 0 , 寫者會被餓死，即饑餓(starvation)。策 略: 一旦有寫者等待, 新到達讀者等待 , 正在讀的讀者都結(jié)束

56、后, 寫者進入 , 即寫者優(yōu)先。例4-3. 讀者/寫者問題(Cont.) 程序分析semaphore r_w_w=1, mutex=1, mutex1=1, read_q=1 ;int readCount=0, writeCount=0 ;void writer ( ) P ( mutex1 ) ; writeCount + ; if ( writeCount = 1 ) P ( read_q ) ; V ( mutex1 ) ; P ( r_w_w ) ; V ( r_w_w ) ; P ( mutex1 ) ; writeCount -; if ( writeCount = 0 ) V (

57、 read_q ) ; V ( mutex1 ) ;例4-3. 讀者/寫者問題(Cont.)Solution3: 寫者優(yōu)先void reader ( ) P ( read_q ); P ( mutex ) ; readCount + ; if ( readCount = 1 ) P ( r_w_w ) ; V ( mutex ) ; V ( read_q ) P ( mutex ) ; readCount - ; if ( readCount = 0 ) V ( r_w_w ) ; V ( mutex ) ;例4-3. 讀者/寫者問題(Cont.)Solution3: 寫者優(yōu)先enum sta

58、te free , used ;enum state lp 3 ; /* initial value is free */semaphore S ; /* initial value is 3 */semaphore mutex ; /* initial value is 1 */例4-4. 三臺打印機管理int require ( ) P (S) ; P (mutex) ; for (i = 0; i3; i+) if (lpi=free) break; lpi = used ; V (mutex) ; return (i) ; void release ( int i ) P (mutex

59、); lp i = free ; V (mutex); V (S) ; 注意：執(zhí)行 for 循環(huán)時 P (S) 已經(jīng)通過，一定存在空閑（free）的打印機 i 。例4-5. 吸煙者問題Cigarette Smokers ProblemPatil S. S. Limitations and Capabilities of Dijkstras semaphore primitives for coordination among processes. MIT project MAC Computation Structure Group Memo 57, MIT, Cambridge, Mass,

60、 1977.例4-5. 吸煙者問題(Cont.)材 料：煙草、卷煙紙和火柴供應(yīng)者： 不吸煙； 有足夠多的煙草、卷煙紙和火柴； 每次隨機地將三種材料的兩種各一樣放 到桌子上，供有另一種材料的吸煙者吸煙。吸煙者： 每位吸煙者只有一種吸煙材料， 且彼此擁有材料各不相同； 每位吸煙者需要三種材料齊全才能吸煙。問 題：實現(xiàn)供應(yīng)者和吸煙者之間的同步。房間內(nèi)有一位材料供應(yīng)者和 3 位吸煙者。 3 supplier processes: X: supplies tobacco and match; Y: supplies match and wrapper; Z: supplies wrapper and t