2.4.3信號量機制1.整型信號量最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。wait和signal操作可描述為：

wait(S):{while(S≤0);S--;}signal(S):{while(S≤0);S++;}2.記錄型信號量記錄型信號量結構：typedefstruct{intvalue;&&信號量的值structPCB:list;&&在此信號量上的阻塞鏈表}semaphore;Wait(s)操作描述：wait(semaphore*s){s.value--;if(s.value<0)block(s.list);}原語操作的主要動作是：(1)s.value減1；(2)若s.value減1后仍大于或等于零，則進程繼續執行；(3)若s.value減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列中，然后轉進程調度。signal(s)操作描述：signal(semaphore*s){s.value++;if(s.value<=0)wakeup(s.list);}signal原語的操作主要動作是：(1)s.value加1；(2)若s.value加1后，結果大于零，進程繼續執行；(3)若s.value加1，結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續執行或轉進程調度。Wait和signal原語的物理意義每執行一次wait操作，意味著請求分配一個單位的資源，描述為s.value=s.value-1;當s.value<0表示已無資源，請求該資源的進程將被阻塞。|s.value|表示等待該信號量的等待進程數。每執行一次signal操作，意味著釋放一個單位的資源，描述為s.value=s.value+1;若s.value<=0表示仍有被阻塞進程。將被阻進程隊列中的第一個進程喚醒插入就緒隊列中。互斥問題中對信號量mutex必須設置一次初值，初值必須為1。wait、signal原語操作應該分別緊靠臨界區的頭部和尾部。wait、signal原語操作必須成對出現，而且它們同處于同一個進程中。wait、signal原語不能次序錯誤、重復或遺漏進程互斥模型n個進程共享一個信號量mutex,并初始化為1。每個進程Pi的組織結構如下：

while(1){……

}wait(mutex)臨界區(CS)

signal(mutex)剩余區進程互斥模型用信號量實現進程互斥

利用信號量能方便地解決臨界區問題。

設有n個進程，用數組P(i)表示，設與n個進程共享的臨界資源對應的互斥信號量為s。信號量初始化為1，表示初始狀態時共享資源是空閑的。只需把各個進程臨界區的程序段置于wait(s)和signal(s)之間即可實現n個進程的互斥。wait(s)signal(s)

臨界區1wait(s)wait(s)

臨界區i

臨界區nsignal(s)signal(s)進程P（1）…進程P（i）…進程P（n）使用信號量解決第一個例子

R1+1→R1

R1→count

count→R2

R2+2→R2

R1→countwait(s)Signal(s)

count→R1wait(s)Signal(s)

進程PIN

進程POUT

臨界區

臨界區用P、V操作解決進程間互斥問題wait(mutex)signal(mutex)P1P2P3臨界區wait(mutex)wait(mutex)signal(mutex)signal(mutex)1）Mutex－1＝02）Mutex－1＝－1P2阻塞3）Mutex－1＝－2P3阻塞4）Mutex＋1＝－1

喚醒P25）Mutex＋1＝0

喚醒P36）Mutex＋1＝1例如，系統中有一臺打印機，三個進程使用打印機。系統設置一個互斥信號量mutex，初值＝1。對于互斥當僅有兩個并發進程共享臨界資源時，即n=2時，互斥信號量s.value僅能取：-1，0，1三個值。其中：s.value=1，表示無進程進入臨界區s.value=0，表示已有一個進程進入臨界區s.value=-1，表示已有一個進程正在等待進入臨界區當用s來實現n個進程的互斥時，n>2,互斥信號量s.value僅能取-(n-1)到1。Wait和signal原語的物理意義每執行一次wait操作，意味著請求分配一個單位的資源，描述為s.value=s.value-1;當s.value<0表示已無資源，請求該資源的進程將被阻塞。|s.value|表示等待該信號量的等待進程數。每執行一次signal操作，意味著釋放一個單位的資源，描述為s.value=s.value+1;若s.value<=0表示仍有被阻塞進程。將被阻進程隊列中的第一個進程喚醒插入就緒隊列中。原語的物理意義S>0時，S表示可使用資源數，S=0時，表示已無資源可用，或表示不允許進程再進。S<0時，|s|表示等待使用資源的進程個數。互斥應用描述步驟如下1.定義互斥信號量2.進程過程描述臨界區前后用wait、signal3.主程序描述

并發進程調用放在cobegin和coend之間voidprocessin(){intR1;

R1:=count;R1:=R1+1;count:=R1;

}voidprocessout(){intR2;

R2:=count;R2:=R2-1;count:=R2;

}main(){

cobeginprocessin();processout();coend}Wait(s);Wait(s);signal(s);signal(s);intcount=n；

semaphores;s.value=1;例1：游藝場例子

有一座東西方向的獨木橋，用wait,signal操作實現：

（1）每次只允許一個人過橋；

（2）當獨木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。例2：獨木橋（1）每次只允許一個人過橋；（1）解

設信號量MUTEX=1

wait(MUTEX)

過橋

signal(MUTEX)（2）當獨木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。同向的第1人申請過橋權wait()，后面過去，不用申請同方向過橋

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

同向的最后1人釋放過橋權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);（2）當獨木橋上有行人時，同方向的行人可以同時過橋，相反方向的人必須等待。(2)解:

設信號量：MUTEX=1(東西方互斥);

MD=1

(東向西使用計數變量互斥)

MX=1

(西向東使用計數變量互斥)

設整型變量：CD=0

(東向西的已上橋人數)

CX=0

(西向東的已上橋人數)

從東向西：

wait(MD)

IF(CD=0)

{wait(MUTEX)

}

CD=CD+1

signal(MD)

過橋

wait(MD)

CD=CD-1

IF(CD=0)

{signal(MUTEX)

}

signal(MD)

從西向東：

wait(MX)

IF(CX=0)

{wait(MUTEX)

}

CX=CX+1

signal(MX)

過橋

wait(MX)

CX=CX-1

IF(CX=0)

{signal(MUTEX)

}

signal(MX)

信號量分為：互斥信號量和資源信號量。互斥信號量用于申請或歸還資源的使用權，常初始為1；資源信號量用于申請或歸還資源，可以常初始為大于1的正整數，表示系統中某類資源的可用個數。Wait操作用于申請資源（或使用權），進程執行wait原語時，可能會阻塞自己。signal操作用于釋放資源（或歸還使用權），進程執行signal原語時，會喚醒一個阻塞進程。信號量的類型用P、V操作解決進程間互斥問題wait(s)signal(s)P1P2P3臨界區wait(s)wait(s)signal(s)signal(s)1）s－1＝1進入臨界資源2）s－1＝0進入臨界資源3）s－1＝－1P3阻塞4）s＋1＝0

喚醒P35）s＋1＝1

釋放資源6）s＋1＝2釋放資源例如，系統中有2臺打印機，三個進程使用打印機。系統設置一個資源信號量s，初值＝2。P1(){….S1;//語句S1….}2.利用信號量實現前趨關系P2(){….S2;//語句2….}希望S1S2，只需使進程P1和P2共享一個公用信號量S=0，將signal(S)放在語句S1后，將wait(S)放在語句S2前。P1(){….S1;//語句S1signal(S);….}P2(){….wait(S);S2;//語句2….}前驅關系：S1→S2和S1→S3。有三個進程P1、P2、P3，P1中有程序段S1，P2中有程序段S2，P3中有程序段S3，在它們并發執行時，希望S1先執行，然后S2、S3才執行，S1→S2、S1→S3。解決辦法：設置兩個信號量mutex1、mutex2，分別用來標志前驅關系S1→S2、S1→S3。semaphoremutex1,mutex2；mutex1.value=mutex2.value=0;P1(){….S1;signal(mutex1);signal(mutex2);….}P2(){….wait(mutex1);S2;….}P3(){….wait(mutex2);S3;….}前驅關系：S1→S2→S3，進程P1、P2、P3。semaphoremutex1,mutex2；mutex1.value=mutex2.value=0;P1(){….S1;signal(mutex1);….}P2(){….wait(mutex1);S2;signal(mutex2);….}P3(){….wait(mutex2);S3;….}前驅關系：S1→S3和S2→S3，進程P1、P2、P3。semaphoremutex1,mutex2；mutex1.value=mutex2.value=0;P1(){….S1;signal(mutex1);….}P2(){….S2;signal(mutex2);….}P3(){….wait(mutex1);wait(mutex2);S3;….}P1(){S1;signal(a);signal(b);}P2(){wait(a);S2;signal(c);signal(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(){semaphorea,b,c,d,e,f,g;a.value:=0;b.value=0;…….cobeginp1();p2();p3();p4();p5();p6();coend}進程P1、P2如下所示，欲實現的前驅關系如圖中虛線所示。P1(){….S1;….S3;….}P2(){….S2;….S4;….}semaphorea,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;….}進程P1、P2如下所示，欲實現的前驅關系如圖中虛線所示，其中S1最初開始執行。P1(){

while(1){….S1;….}}semaphorea,b;a.value=0;b.value=1;P2(){

while(1){….S2;….}}P1(){while(1){….

wait(b);S1;

signal(a);….}}P2(){while(1){….

wait(a);S2;

signal(b);….}}解題步驟一分析題中各進程間的制約關系；解題步驟二按上面的分析結果設置相應的信號量（包括信號量的名字、個數和初值及物理含義僅限同步問題）注意：對于互斥問題，一般只設1個信號量，且設初值為1；而對于同步問題，合作進程間需要收發幾條消息就相應設置幾個信號量，初值為0或一個整數。利用信號量解決進程的同步和互斥解題步驟三把wait、signal操作加到進程代碼的適當處一般地，wait,signal操作總是配對出現的，

但具體描述互斥時，wait,signal操作出現在同一進程中（且分別緊挨在臨界區前后）；

而具體描述進程同步時，wait,signal操作常出現在不同的進程中，且一進