第2章信号量概念和互斥

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

2、录型信号量结构：记录型信号量结构： typedef struct int value; 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，结果，结果小于或等于零小于或等于零，则从该信号的，则从该信号的 等待队列中等待队列中唤醒一等待进程唤醒一等待进程，然后再返回原进程继，然后再返回原进程继 续执行或转进程调度。续执行或转进程调度。 m

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

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

6、0时，时，S表示可使用资源数，表示可使用资源数， S=0时，表示已无资源可用，或表示不允许进程再进。时，表示已无资源可用，或表示不允许进程再进。 S0时，时，|s|表示等待使用资源的进程个数。表示等待使用资源的进程个数。 mxh 互斥应用描述步骤如下互斥应用描述步骤如下 1. 定义互斥信号量定义互斥信号量 2. 进程过程描述进程过程描述 临界区前后用临界区前后用wait、signal 3. 主程序描述主程序描述 并发进程调用放在并发进程调用放在cobegin和和coend之间之间 mxh void processin() int R1 ; R1:=count ; R1:=R1+1 ; coun

7、t:=R1; void processout() int R2 ; R2:=count ; R2:=R2-1 ; count:=R2; main() cobegin processin() ; processout() ; coend Wait(s) ; Wait(s) ; signal(s) ; signal(s) ; int count=n； semaphore s; s.value=1; 例例1：游艺场例子：游艺场例子 mxh 有一座东西方向的独木桥有一座东西方向的独木桥，用用wait, signal操作实操作实 现：现： （1）每次只允许一个人过桥；）每次只允许一个人过桥； （2）当独

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

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

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

11、用计数变量互斥) MX=1 (西向东使用计数变量互斥西向东使用计数变量互斥) 设整型变量：设整型变量： CD=0 (东向西的已上桥人数东向西的已上桥人数) CX=0 (西向东的已上桥人数西向东的已上桥人数) mxh 从东向西：从东向西： 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)

12、 CX=CX-1 IF (CX=0) signal(MUTEX) signal(MX) mxh 信号量分为：信号量分为：互斥信号量互斥信号量和和资源信号量资源信号量。 互斥信号量互斥信号量用于申请或归还资源的用于申请或归还资源的使用权使用权，常初常初 始为始为1； 资源信号量资源信号量用于申请或归还资源，可以常用于申请或归还资源，可以常初始为初始为 大于大于1的正整数的正整数，表示系统中某类资源的可用个，表示系统中某类资源的可用个 数。数。 Wait操作用于申请资源（或使用权），操作用于申请资源（或使用权），进程执进程执 行行wait原语时，可能会阻塞自己。原语时，可能会阻塞自己。 signa

13、l操作用于释放资源（或归还使用权），操作用于释放资源（或归还使用权），进进 程执行程执行signal原语时，会唤醒一个阻塞进程。原语时，会唤醒一个阻塞进程。 信号量的类型信号量的类型 mxh 用用P P、V V操作解决进程间互斥问题操作解决进程间互斥问题 wait(s) signal(s) wait(s) wait(s) signal(s) signal(s) 例如，系统中有例如，系统中有2 2台台打印机，三个进程使用打印机。系统设置打印机，三个进程使用打印机。系统设置 一个一个资源信号量资源信号量s s，初值初值2 2。 mxh P1 () . S1; /语句语句S1 . 2. 利用信号量实

14、现前趋关系利用信号量实现前趋关系 P2 () . S2; /语句语句2 . 希望希望 S1 S2，只需使进程，只需使进程P1和和P2共享一个公用信号量共享一个公用信号量S=0， 将将signal(S)放在语句放在语句S1后，将后，将wait(S)放在语句放在语句S2前。前。 P1 () . S1; /语句语句S1 signal(S); . P2 () . wait(S); S2; /语句语句2 . mxh 前驱关系：前驱关系：S1S2和和S1S3。有三个进程。有三个进程P1、 P2、P3，P1中有程序段中有程序段S1，P2中有程序段中有程序段S2，P3 中有程序段中有程序段S3，在它们并发执行

15、时，希望，在它们并发执行时，希望S1先执行先执行 ，然后，然后S2、S3才执行，才执行，S1S2、S1S3。 解决办法：设置两个信号量解决办法：设置两个信号量mutex1、mutex2， 分别用来标志前驱关系分别用来标志前驱关系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 前驱关系：前驱关系：S1S2S

16、3，进程，进程P1、P2、P3。 semaphore mutex1,mutex2； mutex1.value=mutex2.value=0; P1 () . S1; signal(mutex1) ; . P2 () . wait(mutex1); 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

17、 () . S2; signal(mutex2); . P3() . wait(mutex1); wait(mutex2); S3; . mxh 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( ) semaphore a,b,c,d,e

18、,f,g; a.value:=0; b.value=0;. cobegin p1( ); p2( ); p3( ); p4( ); p5( ); p6( ); coend S 4 S 5 S 3 S 1 S 6 S 2 进程P1、P2如下所示，欲实现的前驱关系如图中虚线所示。 P1 () . S1; . S3; . P2 () . 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; signa

19、l(b); . wait(c); S4; . 进程进程P1P1、P2P2如下所示，欲实现的前驱关系如图中虚线所如下所示，欲实现的前驱关系如图中虚线所 示，其中示，其中S1S1最初开始执行。最初开始执行。 P1 () while(1) . S1; . semaphore a,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); . mxh 解题步骤一解题步骤一 分析题中各进程间的制约关系；分析

20、题中各进程间的制约关系； 解题步骤二解题步骤二 按上面的分析结果按上面的分析结果设置相应的信号量设置相应的信号量（包括信（包括信 号量的名字、个数和初值及物理含义号量的名字、个数和初值及物理含义仅限仅限 同步问题同步问题） 注意：对于互斥问题，一般只设注意：对于互斥问题，一般只设1 1个信个信 号量，且设初值为号量，且设初值为1 1；而对于同步问题，合；而对于同步问题，合 作进程间需要收发几条消息就相应设置几作进程间需要收发几条消息就相应设置几 个信号量，初值为个信号量，初值为0 0或一个整数。或一个整数。 利用信号量解决进程的同步和互斥利用信号量解决进程的同步和互斥 mxh 解题步骤三解题步

21、骤三 把把waitwait、signalsignal操作加到进程代码的适当处操作加到进程代码的适当处 一般地，一般地，wait, signalwait, signal操作总是操作总是配对出现配对出现的，的， 但但具体描述互斥具体描述互斥时，时，wait, signalwait, signal操作出现在同操作出现在同 一进程中（且分别紧挨在临界区前后）；一进程中（且分别紧挨在临界区前后）； 而而具体描述进程同步具体描述进程同步时，时，wait,signalwait,signal操作常出操作常出 现在不同的进程中，且一进程发送消息时用现在不同的进程中，且一进程发送消息时用 signal(s)sig

22、nal(s)，而它的合作进程接收此消息时用，而它的合作进程接收此消息时用 wait(s)wait(s) 利用信号量解决进程的同步和互斥利用信号量解决进程的同步和互斥 mxh 进程简单同步进程简单同步 共享缓冲区的进程的同步共享缓冲区的进程的同步 计算进程计算进程cpcp，负责不断地计算数据并送入，负责不断地计算数据并送入缓缓 冲区（一个）冲区（一个）中中 打印进程打印进程pppp，负责不断地从，负责不断地从缓冲区（一个）缓冲区（一个） 中取出数据去打印中取出数据去打印 第三个例子第三个例子 mxh cp进程进程 计算计算 pp进程进程 打印打印 4752 cp进程进程 计算计算 pp进程进程 打印打印 取数打印