第2章信號量概念和互斥

1、mxh2.4.3 信號量機(jī)制信號量機(jī)制 1. 整型信號量整型信號量 最初由最初由Dijkstra把整型信號量定義為一個整型量，除初把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作原子操作(Atomic Operation) wait(S)和和signal(S)來訪問。這兩個操作一直被分別稱為來訪問。這兩個操作一直被分別稱為P、V操作操作。 wait和和signal操作可描述為：操作可描述為： wait(S): while (S0) ; S-; signal(S): while (S0) ; S+;mxh2.2.記錄型信號量記錄型信號量 記錄型信號量

2、結(jié)構(gòu)：記錄型信號量結(jié)構(gòu)：typedef struct int value; &信號量的值信號量的值 struct PCB: list; &在此信號量上的阻塞鏈表在此信號量上的阻塞鏈表 semaphore;mxh Wait(s)操作操作 描述：描述：wait(semaphore *s) s.value -; if (s.value0) block(s.list);原語操作的主要動作是：原語操作的主要動作是：(1) s.value減減 1；(2) 若若s.value減減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；(3) 若若s.value減減1后小于零后小于零，則該，則該

3、進(jìn)程被阻塞進(jìn)程被阻塞后進(jìn)入與后進(jìn)入與該信號相對應(yīng)的隊列中，然后轉(zhuǎn)進(jìn)程調(diào)度。該信號相對應(yīng)的隊列中，然后轉(zhuǎn)進(jìn)程調(diào)度。mxh signal(s)操作描述操作描述：signal(semaphore *s) s.value +; if (s.value=0) wakeup(s.list);signal原語的操作主要動作是：原語的操作主要動作是：(1) s.value加加1；(2) 若若s.value加加1后，結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；后，結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3) 若若s.value加加1，結(jié)果，結(jié)果小于或等于零小于或等于零，則從該信號的，則從該信號的等待隊列中等待隊列中喚醒一等待進(jìn)程喚醒一等待進(jìn)

4、程，然后再返回原進(jìn)程繼，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。mxhWait和和signal原語的物理意義原語的物理意義 每執(zhí)行一次每執(zhí)行一次wait操作，意味著請求操作，意味著請求分配一個單位的資源分配一個單位的資源，描述為，描述為s.value=s.value-1; 當(dāng)當(dāng)s.value0表示已無資源表示已無資源，請求該資源的進(jìn)程將被阻塞。，請求該資源的進(jìn)程將被阻塞。|s.value|表示等待該信表示等待該信號量的等待進(jìn)程數(shù)。號量的等待進(jìn)程數(shù)。 每執(zhí)行一次每執(zhí)行一次signal操作，意味著操作，意味著釋放一個單位的資源釋放一個單位的資源，描述為描述為s.value=s.v

5、alue+1;若若s.value2, 互斥信號量互斥信號量s.value僅僅能能取取 -(n-1) 到到 1。mxhWait和和signal原語的物理意義原語的物理意義 每執(zhí)行一次每執(zhí)行一次wait操作，意味著請求操作，意味著請求分配一個單位的資源分配一個單位的資源，描述為，描述為s.value=s.value-1; 當(dāng)當(dāng)s.value0表示已無資源表示已無資源，請求該資源的進(jìn)程將被阻塞。，請求該資源的進(jìn)程將被阻塞。|s.value|表示等待該信表示等待該信號量的等待進(jìn)程數(shù)。號量的等待進(jìn)程數(shù)。 每執(zhí)行一次每執(zhí)行一次signal操作，意味著操作，意味著釋放一個單位的資源釋放一個單位的資源，描述為

6、描述為s.value=s.value+1;若若s.value0時，時，S表示可使用資源數(shù)，表示可使用資源數(shù)， S=0時，表示已無資源可用，或表示不允許進(jìn)程再進(jìn)。時，表示已無資源可用，或表示不允許進(jìn)程再進(jìn)。 S0時，時，|s|表示等待使用資源的進(jìn)程個數(shù)。表示等待使用資源的進(jìn)程個數(shù)。mxh互斥應(yīng)用描述步驟如下互斥應(yīng)用描述步驟如下 1. 定義互斥信號量定義互斥信號量 2. 進(jìn)程過程描述進(jìn)程過程描述 臨界區(qū)前后用臨界區(qū)前后用wait、signal 3. 主程序描述主程序描述 并發(fā)進(jìn)程調(diào)用放在并發(fā)進(jìn)程調(diào)用放在cobegin和和coend之間之間mxhvoid processin() int R1 ; R

7、1:=count ; R1:=R1+1 ; count:=R1; void processout() int R2 ; R2:=count ; R2:=R2-1 ; count:=R2; main() cobegin processin() ; processout() ; coendWait(s) ;Wait(s) ;signal(s) ;signal(s) ;int count=n； semaphore s; s.value=1;例例1：游藝場例子：游藝場例子mxh 有一座東西方向的獨(dú)木橋有一座東西方向的獨(dú)木橋，用用wait, signal操作實操作實現(xiàn)：現(xiàn)：（1）每次只允許一個人過橋；）

8、每次只允許一個人過橋；（2）當(dāng)獨(dú)木橋上有行人時，同方向的行人可以同）當(dāng)獨(dú)木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。時過橋，相反方向的人必須等待。例例2：獨(dú)木橋：獨(dú)木橋mxh（1）每次只允許一個人過橋；）每次只允許一個人過橋；（1）解）解設(shè)信號量設(shè)信號量 MUTEX=1wait (MUTEX) 過橋過橋signal (MUTEX)mxh（2）當(dāng)獨(dú)木橋上有行人時，同方向的行人可）當(dāng)獨(dú)木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。以同時過橋，相反方向的人必須等待。同同向的向的第第1人申請人申請過橋權(quán)過橋權(quán)wait()，后面過去，不用，后面過去，不用申請申請同方

9、向同方向過橋過橋同向的同向的最后最后1人釋放人釋放過橋過橋權(quán)權(quán)signal()分析：分析：1. 東西方向互斥東西方向互斥的信的信號量，號量，MUTEX=12. 統(tǒng)計統(tǒng)計同方向的同方向的人數(shù)人數(shù)的變量，的變量，CountD=03. 對對計數(shù)變量的互斥計數(shù)變量的互斥訪問的信號量，訪問的信號量，MD=1mxh（2）當(dāng)獨(dú)木橋上有行人時，同方向的行人可）當(dāng)獨(dú)木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。以同時過橋，相反方向的人必須等待。同同向的向的第第1人申請人申請過橋權(quán)過橋權(quán)wait(MUTEX)，后面過去，后面過去，不用申請，不用申請同方向同方向過橋過橋同向的同向的最后最后1人釋放

10、人釋放過橋過橋權(quán)權(quán)signal(MUTEX)IF (CD=0)wait(MUTEX); CD=CD+1;CD=CD-1;IF (CD=0)signal(MUTEX); 同方向同方向過橋過橋wait(MD);wait(MD);signal(MD);signal(MD);mxh（2）當(dāng)獨(dú)木橋上有行人時，同方向的行人可）當(dāng)獨(dú)木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。以同時過橋，相反方向的人必須等待。(2)解解:設(shè)信號量：設(shè)信號量： MUTEX=1 (東西方互斥東西方互斥); MD=1 (東向西使用計數(shù)變量互斥東向西使用計數(shù)變量互斥) MX=1 (西向東使用計數(shù)變量互斥西向東使用

11、計數(shù)變量互斥)設(shè)整型變量：設(shè)整型變量： CD=0 (東向西的已上橋人數(shù)東向西的已上橋人數(shù)) CX=0 (西向東的已上橋人數(shù)西向東的已上橋人數(shù))mxh從東向西：從東向西：wait(MD)IF (CD=0)wait(MUTEX) CD=CD+1signal(MD)過橋過橋wait(MD)CD=CD-1IF (CD=0)signal(MUTEX) signal(MD)從西向東從西向東：wait(MX)IF (CX=0)wait(MUTEX) CX=CX+1signal(MX)過橋過橋wait(MX)CX=CX-1IF (CX=0)signal(MUTEX) signal(MX)mxh信號量分為：信號

12、量分為：互斥信號量互斥信號量和和資源信號量資源信號量。互斥信號量互斥信號量用于申請或歸還資源的用于申請或歸還資源的使用權(quán)使用權(quán)，常初常初始為始為1；資源信號量資源信號量用于申請或歸還資源，可以常用于申請或歸還資源，可以常初始為初始為大于大于1的正整數(shù)的正整數(shù)，表示系統(tǒng)中某類資源的可用個，表示系統(tǒng)中某類資源的可用個數(shù)。數(shù)。Wait操作用于申請資源（或使用權(quán)），操作用于申請資源（或使用權(quán)），進(jìn)程執(zhí)進(jìn)程執(zhí)行行wait原語時，可能會阻塞自己。原語時，可能會阻塞自己。signal操作用于釋放資源（或歸還使用權(quán)），操作用于釋放資源（或歸還使用權(quán)），進(jìn)進(jìn)程執(zhí)行程執(zhí)行signal原語時，會喚醒一個阻塞進(jìn)程。原

13、語時，會喚醒一個阻塞進(jìn)程。信號量的類型信號量的類型mxh用用P P、V V操作解決進(jìn)程間互斥問題操作解決進(jìn)程間互斥問題wait(s)signal(s)wait(s)wait(s)signal(s)signal(s)例如，系統(tǒng)中有例如，系統(tǒng)中有2 2臺臺打印機(jī)，三個進(jìn)程使用打印機(jī)。系統(tǒng)設(shè)置打印機(jī)，三個進(jìn)程使用打印機(jī)。系統(tǒng)設(shè)置一個一個資源信號量資源信號量s s，初值初值2 2。mxhP1 () .S1; /語句語句S1.2. 利用信號量實現(xiàn)前趨關(guān)系利用信號量實現(xiàn)前趨關(guān)系 P2 () .S2; /語句語句2.希望希望 S1 S2，只需使進(jìn)程，只需使進(jìn)程P1和和P2共享一個公用信號量共享一個公用信號量

14、S=0，將將signal(S)放在語句放在語句S1后，將后，將wait(S)放在語句放在語句S2前。前。P1 () .S1; /語句語句S1signal(S);.P2 () .wait(S);S2; /語句語句2.mxh 前驅(qū)關(guān)系：前驅(qū)關(guān)系：S1S2和和S1S3。有三個進(jìn)程。有三個進(jìn)程P1、P2、P3，P1中有程序段中有程序段S1，P2中有程序段中有程序段S2，P3中有程序段中有程序段S3，在它們并發(fā)執(zhí)行時，希望，在它們并發(fā)執(zhí)行時，希望S1先執(zhí)行先執(zhí)行，然后，然后S2、S3才執(zhí)行，才執(zhí)行，S1S2、S1S3。 解決辦法：設(shè)置兩個信號量解決辦法：設(shè)置兩個信號量mutex1、mutex2，分別用來

15、標(biāo)志前驅(qū)關(guān)系分別用來標(biāo)志前驅(qū)關(guān)系S1S2、S1S3。semaphore mutex1,mutex2；mutex1.value=mutex2.value=0;P1 () .S1; signal(mutex1) ;signal(mutex2);.P2 () .wait(mutex1);S2; .P3() .wait(mutex2);S3; .mxh前驅(qū)關(guān)系：前驅(qū)關(guān)系：S1S2S3，進(jìn)程，進(jìn)程P1、P2、P3。semaphore mutex1,mutex2；mutex1.value=mutex2.value=0;P1 () .S1; signal(mutex1) ;.P2 () .wait(mute

16、x1);S2; signal(mutex2);.P3() .wait(mutex2);S3; .mxh前驅(qū)關(guān)系：前驅(qū)關(guān)系：S1S3和和S2S3，進(jìn)程，進(jìn)程P1、P2、P3。semaphore mutex1,mutex2；mutex1.value=mutex2.value=0;P1 () .S1; signal(mutex1) ;.P2 () .S2; signal(mutex2);.P3() .wait(mutex1);wait(mutex2);S3; .mxhP1( ) S1; signal(a); signal(b); P2( ) wait(a); S2; signal(c); signa

17、l(d); P3( ) wait(b); S3; signal(e); P4( ) wait(c); S4; signal(f); P5( ) wait(d); S5; signal(g); P6( ) wait(e); wait(f); wait(g); S6; main( ) semaphore a,b,c,d,e,f,g; a.value:=0; b.value=0;.cobegin p1( ); p2( ); p3( ); p4( ); p5( ); p6( );coendS4S5S3S1S6S2進(jìn)程P1、P2如下所示，欲實現(xiàn)的前驅(qū)關(guān)系如圖中虛線所示。P1 () .S1; .S3;.P

18、2 () .S2; .S4;.semaphore a,b,c;a.value=b.value=c.value=0;P1 () .S1;signal(a); .wait(b);S3;signal(c);.P2 () .wait(a);S2;signal(b); .wait(c);S4;.進(jìn)程進(jìn)程P1P1、P2P2如下所示，欲實現(xiàn)的前驅(qū)關(guān)系如圖中虛線所如下所示，欲實現(xiàn)的前驅(qū)關(guān)系如圖中虛線所示，其中示，其中S1S1最初開始執(zhí)行。最初開始執(zhí)行。P1 () while(1) . S1; . semaphore a,b;a.value=0; b.value=1;P2() while(1) . S2; .

19、P1 () while(1) . wait(b); S1; signal(a); . P2() while(1) . wait(a); S2; signal(b); . mxh 解題步驟一解題步驟一分析題中各進(jìn)程間的制約關(guān)系；分析題中各進(jìn)程間的制約關(guān)系； 解題步驟二解題步驟二按上面的分析結(jié)果按上面的分析結(jié)果設(shè)置相應(yīng)的信號量設(shè)置相應(yīng)的信號量（包括信（包括信號量的名字、個數(shù)和初值及物理含義號量的名字、個數(shù)和初值及物理含義僅限同僅限同步問題步問題） 注意：對于互斥問題，一般只設(shè)注意：對于互斥問題，一般只設(shè)1 1個信個信號量，且設(shè)初值為號量，且設(shè)初值為1 1；而對于同步問題，合；而對于同步問題，合作進(jìn)

20、程間需要收發(fā)幾條消息就相應(yīng)設(shè)置幾作進(jìn)程間需要收發(fā)幾條消息就相應(yīng)設(shè)置幾個信號量，初值為個信號量，初值為0 0或一個整數(shù)。或一個整數(shù)。利用信號量解決進(jìn)程的同步和互斥利用信號量解決進(jìn)程的同步和互斥mxh 解題步驟三解題步驟三 把把waitwait、signalsignal操作加到進(jìn)程代碼的適當(dāng)處操作加到進(jìn)程代碼的適當(dāng)處 一般地，一般地，wait, signalwait, signal操作總是操作總是配對出現(xiàn)配對出現(xiàn)的，的， 但但具體描述互斥具體描述互斥時，時，wait, signalwait, signal操作出現(xiàn)在同操作出現(xiàn)在同一進(jìn)程中（且分別緊挨在臨界區(qū)前后）；一進(jìn)程中（且分別緊挨在臨界區(qū)前后）

21、； 而而具體描述進(jìn)程同步具體描述進(jìn)程同步時，時，wait,signalwait,signal操作常出操作常出現(xiàn)在不同的進(jìn)程中，且一進(jìn)程發(fā)送消息時用現(xiàn)在不同的進(jìn)程中，且一進(jìn)程發(fā)送消息時用signal(s)signal(s)，而它的合作進(jìn)程接收此消息時用，而它的合作進(jìn)程接收此消息時用wait(s)wait(s)利用信號量解決進(jìn)程的同步和互斥利用信號量解決進(jìn)程的同步和互斥mxh進(jìn)程簡單同步進(jìn)程簡單同步 共享緩沖區(qū)的進(jìn)程的同步共享緩沖區(qū)的進(jìn)程的同步計算進(jìn)程計算進(jìn)程cpcp，負(fù)責(zé)不斷地計算數(shù)據(jù)并送入，負(fù)責(zé)不斷地計算數(shù)據(jù)并送入緩緩沖區(qū)（一個）沖區(qū)（一個）中中打印進(jìn)程打印進(jìn)程pppp，負(fù)責(zé)不斷地從，負(fù)責(zé)不斷地從緩沖區(qū)（一個）緩沖區(qū)（一個）中取出數(shù)據(jù)去打印中取出數(shù)據(jù)去打印第三個例子第三個例子mxhcp進(jìn)程進(jìn)程計算計算pp進(jìn)程進(jìn)程打印打印4752cp進(jìn)程進(jìn)程計算計算pp進(jìn)程進(jìn)程打印打印取