第2章信号量概念和互斥

1、mxh2.4.3 信号量机制信号量机制 1. 整型信号量整型信号量 最初由最初由Dijkstra把整型信号量定义为一个整型量，除初把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的始化外，仅能通过两个标准的原子操作原子操作(Atomic Operation) wait(S)和和signal(S)来访问。这两个操作一直被分别称为来访问。这两个操作一直被分别称为P、V操作操作。 wait和和signal操作可描述为：操作可描述为： wait(S): while (S0) ; S-; signal(S): while (S0) ; S+;mxh2.2.记录型信号量记录型信号量 记录型信号量

2、结构：记录型信号量结构：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后仍大于或等于零，则进程继续执行；后仍大于或等于零，则进程继续执行；(3) 若若s.value减减1后小于零后小于零，则该，则该

3、进程被阻塞进程被阻塞后进入与后进入与该信号相对应的队列中，然后转进程调度。该信号相对应的队列中，然后转进程调度。mxh 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，结果，结果小于或等于零小于或等于零，则从该信号的，则从该信号的等待队列中等待队列中唤醒一等待进程唤醒一等待进

4、程，然后再返回原进程继，然后再返回原进程继续执行或转进程调度。续执行或转进程调度。mxhWait和和signal原语的物理意义原语的物理意义 每执行一次每执行一次wait操作，意味着请求操作，意味着请求分配一个单位的资源分配一个单位的资源，描述为，描述为s.value=s.value-1; 当当s.value0表示已无资源表示已无资源，请求该资源的进程将被阻塞。，请求该资源的进程将被阻塞。|s.value|表示等待该信表示等待该信号量的等待进程数。号量的等待进程数。 每执行一次每执行一次signal操作，意味着操作，意味着释放一个单位的资源释放一个单位的资源，描述为描述为s.value=s.v

5、alue+1;若若s.value2, 互斥信号量互斥信号量s.value仅仅能能取取 -(n-1) 到到 1。mxhWait和和signal原语的物理意义原语的物理意义 每执行一次每执行一次wait操作，意味着请求操作，意味着请求分配一个单位的资源分配一个单位的资源，描述为，描述为s.value=s.value-1; 当当s.value0表示已无资源表示已无资源，请求该资源的进程将被阻塞。，请求该资源的进程将被阻塞。|s.value|表示等待该信表示等待该信号量的等待进程数。号量的等待进程数。 每执行一次每执行一次signal操作，意味着操作，意味着释放一个单位的资源释放一个单位的资源，描述为

6、描述为s.value=s.value+1;若若s.value0时，时，S表示可使用资源数，表示可使用资源数， S=0时，表示已无资源可用，或表示不允许进程再进。时，表示已无资源可用，或表示不允许进程再进。 S0时，时，|s|表示等待使用资源的进程个数。表示等待使用资源的进程个数。mxh互斥应用描述步骤如下互斥应用描述步骤如下 1. 定义互斥信号量定义互斥信号量 2. 进程过程描述进程过程描述 临界区前后用临界区前后用wait、signal 3. 主程序描述主程序描述 并发进程调用放在并发进程调用放在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 有一座东西方向的独木桥有一座东西方向的独木桥，用用wait, signal操作实操作实现：现：（1）每次只允许一个人过桥；）

8、每次只允许一个人过桥；（2）当独木桥上有行人时，同方向的行人可以同）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。时过桥，相反方向的人必须等待。例例2：独木桥：独木桥mxh（1）每次只允许一个人过桥；）每次只允许一个人过桥；（1）解）解设信号量设信号量 MUTEX=1wait (MUTEX) 过桥过桥signal (MUTEX)mxh（2）当独木桥上有行人时，同方向的行人可）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。以同时过桥，相反方向的人必须等待。同同向的向的第第1人申请人申请过桥权过桥权wait()，后面过去，不用，后面过去，不用申请申请同方

9、向同方向过桥过桥同向的同向的最后最后1人释放人释放过桥过桥权权signal()分析：分析：1. 东西方向互斥东西方向互斥的信的信号量，号量，MUTEX=12. 统计统计同方向的同方向的人数人数的变量，的变量，CountD=03. 对对计数变量的互斥计数变量的互斥访问的信号量，访问的信号量，MD=1mxh（2）当独木桥上有行人时，同方向的行人可）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。以同时过桥，相反方向的人必须等待。同同向的向的第第1人申请人申请过桥权过桥权wait(MUTEX)，后面过去，后面过去，不用申请，不用申请同方向同方向过桥过桥同向的同向的最后最后1人释放

10、人释放过桥过桥权权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）当独木桥上有行人时，同方向的行人可）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。以同时过桥，相反方向的人必须等待。(2)解解:设信号量：设信号量： MUTEX=1 (东西方互斥东西方互斥); MD=1 (东向西使用计数变量互斥东向西使用计数变量互斥) MX=1 (西向东使用计数变量互斥西向东使用

11、计数变量互斥)设整型变量：设整型变量： CD=0 (东向西的已上桥人数东向西的已上桥人数) CX=0 (西向东的已上桥人数西向东的已上桥人数)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、量分为：互斥信号量互斥信号量和和资源信号量资源信号量。互斥信号量互斥信号量用于申请或归还资源的用于申请或归还资源的使用权使用权，常初常初始为始为1；资源信号量资源信号量用于申请或归还资源，可以常用于申请或归还资源，可以常初始为初始为大于大于1的正整数的正整数，表示系统中某类资源的可用个，表示系统中某类资源的可用个数。数。Wait操作用于申请资源（或使用权），操作用于申请资源（或使用权），进程执进程执行行wait原语时，可能会阻塞自己。原语时，可能会阻塞自己。signal操作用于释放资源（或归还使用权），操作用于释放资源（或归还使用权），进进程执行程执行signal原语时，会唤醒一个阻塞进程。原

13、语时，会唤醒一个阻塞进程。信号量的类型信号量的类型mxh用用P P、V V操作解决进程间互斥问题操作解决进程间互斥问题wait(s)signal(s)wait(s)wait(s)signal(s)signal(s)例如，系统中有例如，系统中有2 2台台打印机，三个进程使用打印机。系统设置打印机，三个进程使用打印机。系统设置一个一个资源信号量资源信号量s s，初值初值2 2。mxhP1 () .S1; /语句语句S1.2. 利用信号量实现前趋关系利用信号量实现前趋关系 P2 () .S2; /语句语句2.希望希望 S1 S2，只需使进程，只需使进程P1和和P2共享一个公用信号量共享一个公用信号量

14、S=0，将将signal(S)放在语句放在语句S1后，将后，将wait(S)放在语句放在语句S2前。前。P1 () .S1; /语句语句S1signal(S);.P2 () .wait(S);S2; /语句语句2.mxh 前驱关系：前驱关系：S1S2和和S1S3。有三个进程。有三个进程P1、P2、P3，P1中有程序段中有程序段S1，P2中有程序段中有程序段S2，P3中有程序段中有程序段S3，在它们并发执行时，希望，在它们并发执行时，希望S1先执行先执行，然后，然后S2、S3才执行，才执行，S1S2、S1S3。 解决办法：设置两个信号量解决办法：设置两个信号量mutex1、mutex2，分别用来

15、标志前驱关系分别用来标志前驱关系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前驱关系：前驱关系：S1S2S3，进程，进程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前驱关系：前驱关系：S1S3和和S2S3，进程，进程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进程P1、P2如下所示，欲实现的前驱关系如图中虚线所示。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;.进程进程P1P1、P2P2如下所示，欲实现的前驱关系如图中虚线所如下所示，欲实现的前驱关系如图中虚线所示，其中示，其中S1S1最初开始执行。最初开始执行。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 解题步骤一解题步骤一分析题中各进程间的制约关系；分析题中各进程间的制约关系； 解题步骤二解题步骤二按上面的分析结果按上面的分析结果设置相应的信号量设置相应的信号量（包括信（包括信号量的名字、个数和初值及物理含义号量的名字、个数和初值及物理含义仅限同仅限同步问题步问题） 注意：对于互斥问题，一般只设注意：对于互斥问题，一般只设1 1个信个信号量，且设初值为号量，且设初值为1 1；而对于同步问题，合；而对于同步问题，合作进

20、程间需要收发几条消息就相应设置几作进程间需要收发几条消息就相应设置几个信号量，初值为个信号量，初值为0 0或一个整数。或一个整数。利用信号量解决进程的同步和互斥利用信号量解决进程的同步和互斥mxh 解题步骤三解题步骤三 把把waitwait、signalsignal操作加到进程代码的适当处操作加到进程代码的适当处 一般地，一般地，wait, signalwait, signal操作总是操作总是配对出现配对出现的，的， 但但具体描述互斥具体描述互斥时，时，wait, signalwait, signal操作出现在同操作出现在同一进程中（且分别紧挨在临界区前后）；一进程中（且分别紧挨在临界区前后）

21、； 而而具体描述进程同步具体描述进程同步时，时，wait,signalwait,signal操作常出操作常出现在不同的进程中，且一进程发送消息时用现在不同的进程中，且一进程发送消息时用signal(s)signal(s)，而它的合作进程接收此消息时用，而它的合作进程接收此消息时用wait(s)wait(s)利用信号量解决进程的同步和互斥利用信号量解决进程的同步和互斥mxh进程简单同步进程简单同步 共享缓冲区的进程的同步共享缓冲区的进程的同步计算进程计算进程cpcp，负责不断地计算数据并送入，负责不断地计算数据并送入缓缓冲区（一个）冲区（一个）中中打印进程打印进程pppp，负责不断地从，负责不断地从缓冲区（一个）缓冲区（一个）中取出数据去打印中取出数据去打印第三个例子第三个例子mxhcp进程进程计算计算pp进程进程打印打印4752cp进程进程计算计算pp进程进程打印打印取