第2章信號量概念和互斥

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

while(1){……

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

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

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

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

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

臨界區(qū)i

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

R1+1→R1

R1→count

count→R2

R2+2→R2

R1→countwait(s)Signal(s)

count→R1wait(s)Signal(s)

進(jìn)程PIN

進(jìn)程POUT

臨界區(qū)

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

并發(fā)進(jìn)程調(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：游藝場例子

有一座東西方向的獨(dú)木橋，用wait,signal操作實(shí)現(xiàn)：

（1）每次只允許一個(gè)人過橋；

（2）當(dāng)獨(dú)木橋上有行人時(shí)，同方向的行人可以同時(shí)過橋，相反方向的人必須等待。例2：獨(dú)木橋（1）每次只允許一個(gè)人過橋；（1）解

設(shè)信號量MUTEX=1

wait(MUTEX)

過橋

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

同向的最后1人釋放過橋權(quán)signal()分析：1.東西方向互斥的信號量，MUTEX=12.統(tǒng)計(jì)同方向的人數(shù)的變量，CountD=03.對計(jì)數(shù)變量的互斥訪問的信號量，MD=1（2）當(dāng)獨(dú)木橋上有行人時(shí)，同方向的行人可以同時(shí)過橋，相反方向的人必須等待。同向的第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）當(dāng)獨(dú)木橋上有行人時(shí)，同方向的行人可以同時(shí)過橋，相反方向的人必須等待。(2)解:

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

MD=1

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

MX=1

(西向東使用計(jì)數(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)中某類資源的可用個(gè)數(shù)。Wait操作用于申請資源（或使用權(quán)），進(jìn)程執(zhí)行wait原語時(shí)，可能會阻塞自己。signal操作用于釋放資源（或歸還使用權(quán)），進(jìn)程執(zhí)行signal原語時(shí)，會喚醒一個(gè)阻塞進(jìn)程。信號量的類型用P、V操作解決進(jìn)程間互斥問題wait(s)signal(s)P1P2P3臨界區(qū)wait(s)wait(s)signal(s)signal(s)1）s－1＝1進(jìn)入臨界資源2）s－1＝0進(jìn)入臨界資源3）s－1＝－1P3阻塞4）s＋1＝0

喚醒P35）s＋1＝1

釋放資源6）s＋1＝2釋放資源例如，系統(tǒng)中有2臺打印機(jī)，三個(gè)進(jìn)程使用打印機(jī)。系統(tǒng)設(shè)置一個(gè)資源信號量s，初值＝2。P1(){….S1;//語句S1….}2.利用信號量實(shí)現(xiàn)前趨關(guān)系P2(){….S2;//語句2….}希望S1S2，只需使進(jìn)程P1和P2共享一個(gè)公用信號量S=0，將signal(S)放在語句S1后，將wait(S)放在語句S2前。P1(){….S1;//語句S1signal(S);….}P2(){….wait(S);S2;//語句2….}前驅(qū)關(guān)系：S1→S2和S1→S3。有三個(gè)進(jìn)程P1、P2、P3，P1中有程序段S1，P2中有程序段S2，P3中有程序段S3，在它們并發(fā)執(zhí)行時(shí)，希望S1先執(zhí)行，然后S2、S3才執(zhí)行，S1→S2、S1→S3。解決辦法：設(shè)置兩個(gè)信號量mutex1、mutex2，分別用來標(biāo)志前驅(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，進(jìn)程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，進(jìn)程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}進(jìn)程P1、P2如下所示，欲實(shí)現(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;….}進(jìn)程P1、P2如下所示，欲實(shí)現(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);….}}解題步驟一分析題中各進(jìn)程間的制約關(guān)系；解題步驟二按上面的分析結(jié)果設(shè)置相應(yīng)的信號量（包括信號量的名字、個(gè)數(shù)和初值及物理含義僅限同步問題）注意：對于互斥問題，一般只設(shè)1個(gè)信號量，且設(shè)初值為1；而對于同步問題，合作進(jìn)程間需要收發(fā)幾條消息就相應(yīng)設(shè)置幾個(gè)信號量，初值為0或一個(gè)整數(shù)。利用信號量解決進(jìn)程的同步和互斥解題步驟三把wait、signal操作加到進(jìn)程代碼的適當(dāng)處一般地，wait,signal操作總是配對出現(xiàn)的，

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

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