第2章信號量概念和互斥

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.記錄型信號量記錄型信號量結(jié)構(gòu)：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后仍大于或等于零，則進程繼續(xù)執(zhí)行；(3)若s.value減1后小于零，則該進程被阻塞后進入與該信號相對應(yīng)的隊列中，然后轉(zhuǎn)進程調(diào)度。signal(s)操作描述：signal(semaphore*s){s.value++;if(s.value<=0)wakeup(s.list);}signal原語的操作主要動作是：(1)s.value加1；(2)若s.value加1后，結(jié)果大于零，進程繼續(xù)執(zhí)行；(3)若s.value加1，結(jié)果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉(zhuǎn)進程調(diào)度。Wait和signal原語的物理意義每執(zhí)行一次wait操作，意味著請求分配一個單位的資源，描述為s.value=s.value-1;當s.value<0表示已無資源，請求該資源的進程將被阻塞。|s.value|表示等待該信號量的等待進程數(shù)。每執(zhí)行一次signal操作，意味著釋放一個單位的資源，描述為s.value=s.value+1;若s.value<=0表示仍有被阻塞進程。將被阻進程隊列中的第一個進程喚醒插入就緒隊列中?；コ鈫栴}中對信號量mutex必須設(shè)置一次初值，初值必須為1。wait、signal原語操作應(yīng)該分別緊靠臨界區(qū)的頭部和尾部。wait、signal原語操作必須成對出現(xiàn)，而且它們同處于同一個進程中。wait、signal原語不能次序錯誤、重復(fù)或遺漏進程互斥模型n個進程共享一個信號量mutex,并初始化為1。每個進程Pi的組織結(jié)構(gòu)如下：

while(1){……

}wait(mutex)臨界區(qū)(CS)

signal(mutex)剩余區(qū)進程互斥模型用信號量實現(xiàn)進程互斥

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

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

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

臨界區(qū)i

臨界區(qū)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

臨界區(qū)

臨界區(qū)用P、V操作解決進程間互斥問題wait(mutex)signal(mutex)P1P2P3臨界區(qū)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例如，系統(tǒng)中有一臺打印機，三個進程使用打印機。系統(tǒng)設(shè)置一個互斥信號量mutex，初值＝1。對于互斥當僅有兩個并發(fā)進程共享臨界資源時，即n=2時，互斥信號量s.value僅能?。?1，0，1三個值。其中：s.value=1，表示無進程進入臨界區(qū)s.value=0，表示已有一個進程進入臨界區(qū)s.value=-1，表示已有一個進程正在等待進入臨界區(qū)當用s來實現(xiàn)n個進程的互斥時，n>2,互斥信號量s.value僅能取-(n-1)到1。Wait和signal原語的物理意義每執(zhí)行一次wait操作，意味著請求分配一個單位的資源，描述為s.value=s.value-1;當s.value<0表示已無資源，請求該資源的進程將被阻塞。|s.value|表示等待該信號量的等待進程數(shù)。每執(zhí)行一次signal操作，意味著釋放一個單位的資源，描述為s.value=s.value+1;若s.value<=0表示仍有被阻塞進程。將被阻進程隊列中的第一個進程喚醒插入就緒隊列中。原語的物理意義S>0時，S表示可使用資源數(shù)，S=0時，表示已無資源可用，或表示不允許進程再進。S<0時，|s|表示等待使用資源的進程個數(shù)?；コ鈶?yīng)用描述步驟如下1.定義互斥信號量2.進程過程描述臨界區(qū)前后用wait、signal3.主程序描述

并發(fā)進程調(diào)用放在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操作實現(xiàn)：

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

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

設(shè)信號量MUTEX=1

wait(MUTEX)

過橋

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

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

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

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

MD=1

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

MX=1

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

設(shè)整型變量：CD=0

(東向西的已上橋人數(shù))

CX=0

(西向東的已上橋人數(shù))

從東向西：

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)

信號量分為：互斥信號量和資源信號量?；コ庑盘柫坑糜谏暾埢驓w還資源的使用權(quán)，常初始為1；資源信號量用于申請或歸還資源，可以常初始為大于1的正整數(shù)，表示系統(tǒng)中某類資源的可用個數(shù)。Wait操作用于申請資源（或使用權(quán)），進程執(zhí)行wait原語時，可能會阻塞自己。signal操作用于釋放資源（或歸還使用權(quán)），進程執(zhí)行signal原語時，會喚醒一個阻塞進程。信號量的類型用P、V操作解決進程間互斥問題wait(s)signal(s)P1P2P3臨界區(qū)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釋放資源例如，系統(tǒng)中有2臺打印機，三個進程使用打印機。系統(tǒng)設(shè)置一個資源信號量s，初值＝2。P1(){….S1;//語句S1….}2.利用信號量實現(xiàn)前趨關(guān)系P2(){….S2;//語句2….}希望S1S2，只需使進程P1和P2共享一個公用信號量S=0，將signal(S)放在語句S1后，將wait(S)放在語句S2前。P1(){….S1;//語句S1signal(S);….}P2(){….wait(S);S2;//語句2….}前驅(qū)關(guān)系：S1→S2和S1→S3。有三個進程P1、P2、P3，P1中有程序段S1，P2中有程序段S2，P3中有程序段S3，在它們并發(fā)執(zhí)行時，希望S1先執(zhí)行，然后S2、S3才執(zhí)行，S1→S2、S1→S3。解決辦法：設(shè)置兩個信號量mutex1、mutex2，分別用來標志前驅(qū)關(guān)系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;….}前驅(qū)關(guān)系：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;….}前驅(qū)關(guān)系：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如下所示，欲實現(xiàn)的前驅(qū)關(guān)系如圖中虛線所示。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如下所示，欲實現(xiàn)的前驅(qū)關(guān)系如圖中虛線所示，其中S1最初開始執(zhí)行。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);….}}解題步驟一分析題中各進程間的制約關(guān)系；解題步驟二按上面的分析結(jié)果設(shè)置相應(yīng)的信號量（包括信號量的名字、個數(shù)和初值及物理含義僅限同步問題）注意：對于互斥問題，一般只設(shè)1個信號量，且設(shè)初值為1；而對于同步問題，合作進程間需要收發(fā)幾條消息就相應(yīng)設(shè)置幾個信號量，初值為0或一個整數(shù)。利用信號量解決進程的同步和互斥解題步驟三把wait、signal操作加到進程代碼的適當處一般地，wait,signal操作總是配對出現(xiàn)的，

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

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