进程同步与互斥 例题.

Presentation on theme: "进程同步与互斥 例题."— Presentation transcript:

1 进程同步与互斥 例题

2 进程同步 进程同步： 解题步骤： 并发进程之间相互合作，完成一项工作，它们之间有一定的时序关系。 确定进程的个数及每个进程的工作；
确定关键工作步（需要控制的）； 确定信号量表示的含义（开始或结束）； 写出伪代码。

3 进程的同步 例1：请用信号量机制描述下列并发进程的同步关系。 S P1 P2 P3 P4 F

4 进程的同步 解法一：信号量表示进程能否开始。
设信号量m1、m2、m3、m4分别表示进程P1、P2、P3、P4能否开始执行，其初值m1为1，其余均为0。 semaphore m1=1,m2=m3=m4=0 ; cobegin p1() // P2() // P3() // P4() coend 思考： 哪个信号量可以省略？ m1 p1() { P(m1) ； 执行p1； V(m2) ； V(m3)； } p2() { P(m2) ； 执行p2； V(m4) ； } p3() { P(m3) ； 执行p3； V(m4) ； } p4() { P(m4) ； P(m4)； 执行p4； }

5 进程的同步 解法二：信号量表示进程是否结束。 设信号量m1、m2、m3、m4分别表示进程P1、P2、P3、P4是否结束，其初值均为0。
semaphore m1=m2=m3=m4=0 ; cobegin p1() // P2() // P3() // P4() coend 思考： 哪个信号量可以省略？ m4 p1() { 执行p1； V(m1) ； V(m1)； } p2() { P(m1) ； 执行p2； V(m2) ； } p3() { P(m1) ； 执行p3； V(m3) ； } p4() { P(m2) ； P(m3)； 执行p4； V(m4)； }

6 进程的同步 练习：请用信号量机制描述下列并发进程的同步关系。 S P1 P2 P4 P3 P5 P6 P7 F

7 进程的同步 例2：公共汽车中的司机和售票员。 司机 P1 售票员 P2
while (true) while (true) { { 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； } }

8 进程的同步 设信号量m1表示司机进程P1能否启动汽车，初值为0，m2表示售票员进程p2能否开门，初值为0。
semaphore m1=0,m2＝0 ; cobegin p1() // p2() coend p1() { while(1) P(m1); 启动汽车； 正常行驶； 到站停车； V(m2); } p2() { while(1) 关门； V(m1); 售票； Ｐ(m2); 　　　开门； }

9 进程的同步 例3-1：吃水果。 父亲 儿子 父亲 P1 儿子 P2
父亲 儿子 父亲 P 儿子 P2 while (true) while (true) { { 洗水果； 取水果； 放水果； 吃水果； } }

10 进程的同步 分析：父亲先放水果，儿子再吃水果；儿子取完水果，父亲再放水果，这两个进程是一个同步关系。
解法：设信号量m1表示父亲能否放水果，m2表示儿子能否取水果。其初值m1=1,m2=0。 semaphore m1=1,m2=0； cobegin p1()//p2() coend 思考： 假设盘子能放n个水果，如何修改同步关系？ p2() { while(1) P(m2) ； 取水果； V(m1)； 吃水果； } p1() { while(1) 洗水果； P(m1) ； 放水果； V(m2) ； }

11 进程的同步 例3-2：吃水果。 儿子 父亲 女儿 父亲 P1 儿子 P2 女儿 P3
苹果 桔子 父亲 女儿 父亲 P 儿子 P 女儿 P3 while (true) while (true) while(true) { { { 洗水果； 取桔子； 取苹果； 放水果； 吃桔子； 吃苹果； } } }

12 进程的同步 分析：父亲先放水果，儿子女儿再吃水果；儿子女儿取完水果，父亲再放水果，这三个进程是一个同步关系。
解法：设信号量m1表示父亲能否放水果，m2表示儿子能否取桔子，m3表示女儿能否取苹果。 semaphore m1=1,m2=0,m3=0； cobegin p1() // p2() // p3() coend p1() { while(1) 洗水果； P(m1) ； 放水果； if (是桔子) V(m2) ； else V(m3)； } p2() { while(1) P(m2) ； 取桔子； V(m1)； 吃桔子； } p3() { while(1) P(m3) ； 取苹果； V(m1)； 吃苹果； }

13 进程的同步 例4：打印文件。 打印机 磁盘 P1 P2 P3 while (true) while (true) while(true)
缓冲1 缓冲2 磁盘 打印机 P P P3 while (true) while (true) while(true) { { { 从磁盘取文件； 从缓冲1取文件； 从缓冲2取文件； 放入缓冲1； 放入缓冲2； 打印文件； } } }

14 进程的同步 分析：P1做完，P2才能做，P2做完，P3才能做。这三个进程是一个同步关系。
解法一：设信号量m1表示P1能否把文件放入缓冲1，m2表示P2能否从缓冲1取文件，m3表示P2能否把文件放入缓冲2，m4表示P3能否从缓冲2取文件。 semaphore m1=1,m2=0,m3=1,m4=0； cobegin p1() // p2() // p3() coend 思考： 1.缓冲1可以存放n个文件，缓冲2可以存放 m个文件，如何修改同步关系？ 2.如果P2改为如下形式，会有何影响？ semaphore m1=n,m2=0,m3=m,m4=0； p2() { while(1) P(m2) ； 从缓冲1取文件； V(m1)； P(m3); 放入缓冲2； V(m4)； } p3() { while(1) P(m4) ； 从缓冲2取文件； V(m3)； 打印文件； } p1() { while(1) 从磁盘读文件； P(m1) ； 放入缓冲1； V(m2) ； } P(m2) ； P(m3); 从缓冲1取文件； 放入缓冲2； V(m1)； V(m4)； 进程的并发性不如修改前

15 进程的同步 分析：P1做完，P2才能做，P2做完，P3才能做。这三个进程是一个同步关系。
解法二：设信号量m1表示P1是否把文件放入缓冲1，m2表示P2是否从缓冲1取完文件，m3表示P2是否把文件放入缓冲2，m4表示P3是否从缓冲2取完文件。 semaphore m1=0,m2=1,m3=0,m4=1； cobegin p1() // p2() // p3() coend p3() { while(1) P(m3) ； 从缓冲2取文件； V(m4)； 打印文件； } p1() { while(1) 从磁盘读文件； P(m2) ； 放入缓冲1； V(m1) ； } p2() { while(1) P(m1) ； 从缓冲1取文件； V(m2)； P(m4); 放入缓冲2； V(m3)； }

16 进程的同步 小结 进程同步有一定的时序关系。 信号量表示进程的关键工作是否可以开始或已经结束。
信号量的个数与进程的个数一致，有时可以省略部分信号量。 对同一个信号量的PV操作不在一个进程中。 表示开始：P自己，V别人 表示结束：P别人，V自己

17 进程互斥 进程互斥： 解题步骤： 并发进程之间相互竞争临界资源的排他性关系。 确定临界资源及个数； 确定进程的关键工作步（使用临界资源的）；
确定信号量的初值； 写出伪代码。

18 进程的互斥 例1：过独木桥。 P1 P2 P P2 { { 由西向东过独木桥； 由东向西过独木桥； } }

19 进程的互斥 分析：进程P1、P2因竞争独木桥这个资源而成为互斥关系。 设：信号量m表示独木桥资源，初值为1表示资源可用。
semaphore m=1; cobegin p1() // p2() coend p1() { P(m) ； 通过独木桥； V(m) ； } p2() { P(m) ； 通过独木桥； V(m)； }

20 进程的互斥 练习：过十字路口（单道）。 P1 P2 P3 P4 { { { { 通过路口； 通过路口； 通过路口； 通过路口；
{ { { { 通过路口； 通过路口； 通过路口； 通过路口； } } } }

21 进程的互斥 分析：进程P1、P2、P3、P4因竞争十字路口这个资源而成为互斥关系。 设：信号量m表示十字路口资源，初值为1表示资源可用。
semaphore m=1; cobegin p1() // p2() //p3() // p4() coend p1() { P(m) ； 通过路口； V(m) ； } p2() { P(m) ； 通过路口； V(m)； } p3() { P(m) ； 通过路口； V(m) ； } p4() { P(m) ； 通过路口； V(m)； }

22 进程的互斥 练习2：过十字路口（双道）。 P1 P2 P3 P4 { { { { 通过路口； 通过路口； 通过路口； 通过路口；
{ { { { 通过路口； 通过路口； 通过路口； 通过路口； } } } }

23 进程的互斥 例2：读写问题。某数据库有一个写进程、多个读进程，它们之间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数据库进行操作。读进程之间不互斥，可以同时读数据库。请用信号量及PV操作描述这一组进程的工作过程。（读者-写者问题） 写 者 数据库 读 者 写者 读者 { { 写数据库； 读数据库； } }

24 进程的互斥 分析：写进程writer、读进程reader因竞争数据库这个资源而成为互斥关系。因为写进程执行时，不能执行其他读写进程，所以还必须设置一个计数器统计读进程的个数。如果是第一个读进程，就与写进程竞争数据库。如果是最后一个读进程，就释放数据库。因计数器是一个临界资源，所以多个读进程对计数器的操作又是互斥操作。 设：信号量rmutex表示数据库资源，初值为1表示资源可用；wmutex表示计数器count资源，初值为1表示可用。 semaphore rmutex=1，wmutex=1; cobegin reader() // writer() coend 思考： 1、第一读者问题 仅当无读者等待时，才允许写者执行 2、第二读者问题 在读者与作者同时申请资源的时候， 写者优先

25 进程的互斥 例3：哲学家就餐问题。有5位哲学家围着一个圆桌在讨论问题和进餐，在讨论时每人手中什么都不拿，当需要进餐时，每人需要一双筷子。餐桌上的布置如图所示，共有5根筷子，每把刀或叉供相邻的两个人使用。 哲学家 { 进餐； 讨论问题； }

26 进程的互斥 1、请用信号量及PV操作说明5位哲学家的就餐过程。
设：5个互斥信号量semaphore chopstick[5]，其初值均为“1”， semaphore chopstick[5]={1}; cobegin pa() // pb() //pc() // pd() coend 问题： 5位哲学家同时拿起左（右）手的餐 具，再拿右（左）手的餐具，显然易 出现死锁！ pi() //i=0-4 { while(1) P(chopstick[i]);        P(chopstick[(i+1) mod 5]);   进餐; V(chopstick[i]);                             V(chopstick[(i+1) mod 5]);    讨论问题; }

27 进程的互斥 2、请用信号量及PV操作设计无死锁的哲学家就餐过程。
思路1：只允许4位哲学家同时拿筷子。此时必然有一个哲学家能拿到2根筷子，可设置一初值为4的资源信号量，如4张椅子，哲学家进餐之前必须先拿到椅子才能拿筷子。进餐后，不但要释放筷子，还有椅子。 semaphore chopstick[5]={1}; semaphore chair=4; pi() //i=0-4 { while(1) { P(chair); P(chopstick[i]);        P(chopstick[(i+1) mod 5]);   进餐; V(chopstick[i]);                             V(chopstick[(i+1) mod 5]);  V(chair);   讨论问题; } 问题： 椅子这种资源信号量可以减少个数。 极端的情况是chair初值为1，即只有 一把椅子，那么每次只允许一个哲学 家进餐，但是效率低!

28 进程的互斥 思路2：只有哲学家同时能够拿起左右两边的筷子的时候，才允许拿筷子。
a)让拿两边筷子的动作变成一个原子操作？所谓的“AND”信号量; b) 不被打断即可….信号量mutex互斥保护。 semaphore chopstick[5]={1}; semaphore mutex=1; //桌边配备一名服务员，服务员负责拿筷子。服务员拿完左右两边的筷子就可以去帮助其他人服务。 pi() //i=0-4 { while(1) { P(mutex); P(chopstick[i]);        P(chopstick[(i+1) mod 5]);  V(mutex);    进餐; V(chopstick[i]);                             V(chopstick[(i+1) mod 5]);  讨论问题; } 问题： 假设0号哲学家正在用餐，此时1号和2号哲学 家饥饿了，两者同时招呼服务员。最终服务 员为1号服务，但因被0号哲学家占用的1号筷 子未释放，因此1号哲学家无法就餐，但他也 没有释放服务员。本来2号哲学家有机会吃饭 的，但因为没有招呼到服务员，因此必须等 待。因此会导致较差饥饿效应！

29 进程的互斥 Challenge：请用信号量及PV操作设计无死锁和饥饿的哲学家就餐过程。
思路1：服务员只有在确认左右两边哲学家都没就餐时才会帮该哲学家拿筷子，否则该哲学家释放服务员。不使用筷子信号量，而是为每个哲学家设置一个状态位，该状态位可以为THINKING或EATING状态。状态位必须被互斥访问。 思路2：服务员轮询式的绕圈服务，类似于令牌环的思想 问题： 1、都属于“服务生解法”， 如何去除类似服务员的角色？ 2、需要增加何种机制？

30 进程的互斥 思路3：规定奇数号哲学家先拿起其左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，1，2号哲学家竞争1号筷子，3，4号哲学家竞争3号筷子，即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总有某一个哲学家能获得两支筷子而进餐。semaphore chopstick[5]={1}; 问题： 资源分级解法：为资源（这里是餐叉）分 配一个偏序或者分级的关系，并约定所有 资源都按照这种顺序获取，按相反顺序释 放，而且保证不会有两个无关资源同时被 同一项工作所需要。 深入：Chandy, K.M.; Misra, J. (1984).  The Drinking Philosophers Problem. ACM Transactions on Programming Languages and Systems. pi() //i=0-4 { while(1) { P(chopstick[(i+(i+1) mod 2) mod 5]); P(chopstick[(i+(i mod 2)) mod 5]); 进餐; V(chopstick[(i+(i+1) mod 2) mod 5]); V(chopstick[(i+(i mod 2)) mod 5]); 讨论问题; }

31 进程的互斥 思路3：另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。 解法：规定奇数号哲学家先拿起其左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，1，2号哲学家竞争1号筷子，3，4号哲学家竞争3号筷子，即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总有某一个哲学家能获得两支筷子而进餐。semaphore chopstick[5]={1}; 问题： 该思路的一些变种：任意一位哲学 家与其他哲学家反方向申请筷子.先 拿筷子的三位哲学家与后面两位哲 学家反方向申请筷子。有何缺点？ pi() //i=0-4 { while(1) { P(chopstick[(i+(i+1) mod 2) mod 5]); P(chopstick[(i+(i mod 2)) mod 5]); 进餐; V(chopstick[(i+(i+1) mod 2) mod 5]); V(chopstick[(i+(i mod 2)) mod 5]); 讨论问题; }

32 进程的互斥 例4：连续过独木桥。在USTC和AHU之间有一条弯曲的小路，其中从S到T有一段路每次只允许一辆自行车通过。但是，其中有一个小的安全岛M（同时允许两辆自行车停留），可以供两辆自行车错车时使用，如图所示。试设计一个算法以确保来往自行车的顺利通过。 toAHU { 通过TL； 上安全岛M； 通过KS; } toUSTC { 通过KS; 上安全岛M； 通过TL； }

33 进程的互斥 小结 进程互斥：进程之间要竞争临界资源。 信号量表示临界资源是否可用，或临界资源的数量。 信号量的个数与临界资源的个数一致。
对同一个信号量的PV操作要在同一个进程中完成。 P操作：进入临界区前 V操作：离开临界区后

34 进程的同步与互斥 解题步骤： 确定各个进程的工作步； 确定进程的哪些工作是同步关系，哪些工作是互斥关系； 确定信号量含义及初值；
同步：有时序关系的 互斥：竞争临界资源的 确定信号量含义及初值； 写出伪代码。

35 进程的同步与互斥 例1：生产消费问题。设有一个具有N个信息元素的环形缓冲区（如图所示），A进程顺序地把信息写进缓冲区，B进程依次从缓冲区中读出信息，请用PV操作描述A、B进程的同步。（生产者-消费者问题） 进程A { 写数据； } 进程B { 读数据； }

36 进程的同步与互斥 分析：这是一个具有多个缓冲空间的生产者消费者问题，也是一个同步加互斥的问题。A、B 两个进程对缓冲区的访问必须互斥。并且当缓冲区满时，A进程不能写入，必须等待；当缓冲区空时，B进程不能读，必须等待，读写进程之间又是同步问题。 设：3个信号量：互斥信号量S = 1（表示对缓冲区的互斥使用）；同步信号量Sw（代表缓冲区是否有空闲，即写进程能否写）、Sr（代表缓冲区是否有数据，即读进程能否读），假设初始时缓冲区没有任何数据，则Sw = N，Sr = 0。设一个数组array表示缓冲区，两个整型变量in、out表示写入和读出的位置。其工作流程如图所示。 #define N 10; int array[N]，in=0，out=0; semaphore S=1，Sw=N，Sr=0; cobegin PA() // PB() coend

37 进程的同步与互斥 例2：理发师理发。理发师理发问题。有一个理发师、一把理发椅和n把等候理发顾客坐的椅子。如果没有顾客，则理发师在理发椅上睡觉；当一个顾客到来时，必须唤醒理发师，进行理发；当理发师正在理发，又有顾客来到时，如果有空椅子，顾客就可以坐下来等候，如果没有空椅子，他就离开。请为理发师和顾客各编一个程序表述他们的行为。 barber { 给顾客理发； } customer { 坐下等候； 理发； }

38 进程的同步与互斥 分析：本题涉及两个进程：理发师和顾客。当有顾客时理发师就可以理发，理完发后，从等候的顾客中选一位顾客继续理发。当理发师正在理发时，顾客要等待，若没有座位就离开，顾客与理发师的工作是同步关系。有多少顾客在等候，需设计一个计数器来记录，顾客和理发师对计数器的操作是互斥的。所以，这是一个同步加互斥的问题。 设：3个信号量：S1表示理发师是否可以开始理发，即是否有顾客；S2表示顾客是否可以被理发，即是否有理发师；S3是对计数器waiting的互斥操作；waiting表示等待顾客的人数。其工作流程如图所示。 #define CHAIR 10; semaphore S1=0，S2=0，S3=1; int waiting=0; cobegin barber() // customer() coend

39 进程同步与互斥的综合例题 例3：单行隧道问题。对一个单行的隧道进行模拟，为了避免死锁，必须防止汽车同时从两端进入隧道。如果一次只允许一辆车通过隧道，两个方向按车辆到达的先后顺序依次通过，请用pv操作设计一个算法实现这个控制。 P1() { 通过隧道； } P2() { 通过隧道； }

40 进程同步与互斥的综合例题 分析：本题涉及两个进程：P1和P2。隧道是一个临界资源，一次只能被一辆车占有，可以把它看作互斥问题。
设：一个互斥信号量sd=1，表示隧道是否可用。 semaphore sd=1; cobegin P1() // P2() coend 问题： 两个方向车辆通过隧道的交换比较平凡， 系统效率不高 P1() { P(sd); 通过隧道； V(sd); } P2() { P(sd); 通过隧道； V(sd); }

41 进程同步与互斥的综合例题 分析：为了提高效率，把问题改为：一旦一辆车进入，则同一方向的车可以立即跟进。写出用信号量解决此问题的代码，不考虑“饥饿”的情况。(按照读者-写者问题处理) 设：3个信号量：c表示计数器，m表示对临界资源计数器的控制，sd表示对临界资源隧道的控制，即隧道是否可用。 semaphore m=1,sd=1; int c=0; cobegin P1() // P2() coend 问题： 若P1过隧道，则后续车辆可以跟进； 若p2过隧道，一次只能过一辆； P1不会产生“饥饿”的现象，而p2会产生“饥饿”的现象。 P1() { P(m); /* m1控制计数器c1 */ if (c== 0 ) P(sd); /*p1第一辆车通过时占有隧道*/ c=c+1; V(m); 通过隧道； P(m); c=c-1; if(c==0) V(sd); /*p1最后一辆车通过后释放隧道 */ } P2() { P(sd); 通过隧道； V(sd); }

42 进程同步与互斥的综合例题 分析：解决p2“饥饿”现象的方法：再设一个信号量k，让p1、p2排队，可以做到p1方向比p2方向晚来的车辆被k阻止。 semaphore m=1,sd=1,k=1; int c=0; cobegin P1() // P2() coend P1() { P(k); /* 与P2一起排队 */ P(m); /* m1控制计数器c */ if (c== 0 ) P(sd); /*P1第一辆车通过时占有隧道*/ c=c+1; V(m); V(k); 通过隧道； P(m); c=c-1; if(c==0) V(sd); /*P1最后一辆车通过后释放隧道 */ } 问题： 若P1过隧道，则后续车辆可以跟进； 若p2过隧道，一次只能过一辆 。 P2() { P(k); P(sd); 通过隧道； V(sd); V(k); }

43 进程同步与互斥的综合例题 分析：解决p2可以过多辆车的方法：按照读者-读者问题处理。即：p1为读者，p2为读者，但两个读者不能同时读 。
Semaphore m1=m2=1,sd=1; int c1=c2=0; //c1、c2为计数器，m1、m2为互斥信号量 cobegin P1() // P2() coend 问题： 若P1过隧道，则后续车辆可以跟进，有可能使p2“饥饿” 若P2过隧道，则后续车辆也可以跟进，有可能使p1“饥饿” P1() { P(m1); if (c1== 0 ) P(sd); c1=c1+1; V(m1); 通过隧道； c1=c1-1; if(c1==0) V(sd); } P2() { P(m2); if (c2== 0 ) P(sd); c2=c2+1; V(m2); 通过隧道； c2=c2-1; if(c2==0) V(sd); }

44 进程同步与互斥的综合例题 P2() P1() { P(k2); { P(k1); P(m2); P(m1);
假设：问题改为：一旦一辆车进入，则同一方向的车可以立即跟进，隧道最多只能过4辆车，如何修改算法？ Semaphore m1=m2=1,sd=1,k1=4,k2=4 ; int c1=c2=0; //c1、c2为计数器，m1、m2为互斥信号量 cobegin //k1、k2为控制各自方向上通过的车辆数 P1() // P2() coend 问题： 是p1优先或p2优先的方法。 p1后续车辆可以跟进，p2后续车辆也能跟进。 P1会产生“饥饿”的现象，p2也会产生“饥饿”的现象。 P1() { P(k1); P(m1); if (c1== 0 ) P(sd); c1=c1+1; V(m1); 通过隧道； c1=c1-1; if(c1==0) V(sd); V(k1); } P2() { P(k2); P(m2); if (c2== 0 ) P(sd); c2=c2+1; V(m2); 通过隧道； c2=c2-1; if(c2==0) V(sd); V(k2); }

45 进程同步与互斥的综合例题 解决p1、p2“饥饿”现象的方法是：一方每过n（如4）辆车后，就允许对方也过n辆。
Semaphore m1=m2=1,sd=1,k1=4,k2=4; int c1=c2=0, n1=0,n2=0 ; //n1、n2为计数器 cobegin //k1、k2为控制各自方向上通过的车辆数 P1() // P2() coend P2() { P(k2); P(m2); if (c2== 0 ) P(sd); c2++; k1=0; V(m2); 通过隧道； c2=c2-1; if(c2==0) { V(sd); // 让对方过4车 k1=4; } V(m2); V(k2); P1() { P(k1); P(m1); if (c1== 0 ) P(sd); c1++; k2=0; V(m1); 通过隧道； c1=c1-1; if(c1==0) { V(sd); // 让对方过4车 k2=4; } V(m1);} 问题： k1,k2为semaphore类型，无法直接赋值操作； Set/reset置操作?合理 如何协调？

46 进程的同步与互斥 使用PV操作的规则： ① 分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。
② 对于互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，互斥信号量的个数只与临界资源的种类有关。通常，有几类临界资源就设置几个互斥信号量，且初值为1，代表临界资源可用。 ③ 对于同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。 ④ 在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但是，它们分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒。必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作。但是，V操作的顺序没有严格要求。

47 2011年考研45题 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下： process 顾客i { 从取号机获取一个号码； 等待叫号； 获取服务； } process 营业员 { while (TRUE) 叫号； 为客户服务； }

48 解答：semaphore seets = 10, //有10个座位的资源信号量
请添加必要的信号量和P,V（或wait()，signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。 解答：semaphore seets = 10, //有10个座位的资源信号量 semaphore mutex = 1, //取号机互斥信号量 semaphore haveCustom = 0; //顾客与营业员同步，无顾客时营业员休息 process 顾客{ P(seets); //等空位 P(mutex); //申请使用取号机 从取号机上取号； V(mutex); //取号完毕 V(haveCustom); //通知营业员有 新顾客到来 等待营业员叫号； V(seets); //离开座位 接受服务；} process 营业员 { while(True) P(haveCustom); //没有顾客则休息 叫号； 为顾客服务； }