第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.记录型信号量记录型信号量结构：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操作常出现在不同的进程中，且一进