信号量机制-课堂练习

1、用wait,signal操作解决进程的同步和互斥问题，绝大部分题目可以按以下步骤解决：根据题目要求将每个进程的执行过程一步一步描述出来；分析每个进程每一步的执行条件，将条件一一记录；比较各个条件，将同一条件归为一个，若条件可以归结为一种资源，设置一个信号量表示；注意：这里是做题，不是实现系统，所以若某个条件题目中没有加以说明或限制，则删除；设置信号量初值：若信号量是代表某种资源，则为系统初始时的可使用的资源数或可使用资源的进程数，若为互斥则为“1”；重新分析每个进程的每个步骤：若该步骤有执行条件涉及信号量A，则在该步骤语句前加入wait(A)；若该步骤有执行后某个信号量B会增值，则在该步骤语句

2、后加入signal(B)；注意：若某个步骤前同时有几个wait操作，则一般同步信号量在前，互斥信号量在后；题目已经做完，最后检查各个进程是否能按题目要求并发执行，若可以，停止；若不可以，检查上述过程，查找错误。例1 有一个生产者和一个消费者共享容量为n的缓冲器(n均大于1)，生产者把生产的物品存入缓冲器，而消费者从缓冲器中取出物品去消费。要求用wait,signal操作对生产者和消费者进行正确管理。第一步 根据题目要求将每个进程的执行过程一步一步描述出来：生产者进程 L1: 生产一件产品；产品放入缓冲；goto L1；消费者进程 L2: 从缓冲中区走产品；消费一件产品；goto L2；第二步

3、分析每个进程每一步的执行条件，将条件一一记录：生产者进程：生产一件产品的条件是有生产产品的原料，在题目中不曾提及，所以该条件不考虑，认为这一步骤没有限制条件；产品放入缓冲条件是要有产品、缓冲，由于前一步骤已经生产出产品，所以这一步骤执行是肯定有产品，这一步骤的限制条件是有缓冲；消费者进程：从缓冲中取走产品条件是缓冲中有产品和，这一步骤的限制条件是缓冲中的产品；消费产品的条件是应该是已获得产品，由于前一步骤已经获得产品，所以这一步骤执行是肯定有产品的，所以这一步骤没有限制条件；第三步 比较各个条件，将同一条件归为一个，设置一个信号量表示；根据第二步分析，本题中有四个限制条件：一个是缓冲，定义信号

4、量empty；一个是产品，定义信号量full；第四步 设置信号量初值：empty，full是资源数量，系统初始状态应该是缓冲均空，无产品，所以empty=n，full=0。第五步 重新分析每个进程的每个步骤，加入wait,signal操作：生产者进程：生产一件产品，无限制条件，且对上述四个信号量无影响；产品放入缓冲条件是缓冲，所以这条语句前加上wait(empty)，这条语句执行完后，应该缓冲中产品会增加一个，所以这条语句后应加入signal(full)；消费者进程：从缓冲中取走产品条件是缓冲中有产品和无消费者从缓冲中取产品，所以这条语句前加上wait(full)，这条语句执行完后，缓冲会增加

5、一个，所以这条语句后应加入signal(S1)；消费产品无限制条件，且对上述四个信号量无影响。这样生产者和消费者进程的过程修改为：生产者进程 L1: 生产一件产品； wait(empty);产品放入缓冲；signal(full);goto L1；消费者进程 L2: wait(full);从缓冲中区走产品；signal(empty);消费一件产品；goto L2；用一个数组B描述缓冲，k指示放产品的位置，t指示取产品的位置，则完整的生产者消费者算法描述如下：semaphore empty=n,full=0;item buffern;int in=out=0;void producer() whi

6、le (1) produce an item in nextp; . wait(empty); bufferin=nextp; in=(in+1) mod n; signal(full); void consumer()while (1) . wait(full); nextc=bufferout; out=(out+1) mod n; signal(empty); . consume the item in nextc; main()cobegin producer();consumer(); 第六步 检查：其中wait(S1)和signal(S1)之间的程序段是各生产者的相关临界区，保证了

7、生产者放产品的互斥；wait(S2)和signal(S2)之间的程序段是各消费者的相关临界区，保证了消费者的互斥；wait(empty)保证了有缓冲才可放产品，无缓冲时生产者等待；wait(full)保证了缓冲中有产品才可取产品，无产品时消费者等待；signal(empty)让消费者通知系统释放一个缓冲，有生产者等待缓冲时可将其唤醒；signal(full)让通知生产者系统增加了一个产品，有消费者等待产品时可将其唤醒。符合题目要求，题目完成。例1改 有m个生产者和r个消费者共享容量为n的缓冲器(m，r，n均大于1)，每个生产者都要把各自生产的物品存入缓冲器，而每个消费者也都要从缓冲器中取出物品

8、去消费。要求用wait,signal操作对这些生产者和消费者进行正确管理。在这个问题中生产者与消费者之间应该同步。由于没有限定生产者生产的物品供哪个消费者取用，也没有限制消费者只能取用哪些物品，因此，生产者只要测试到有缓冲器中尚未放满物品就可把生产的物品存入，消费者只要测试到缓冲器中有物品就可取出。下面是实现同步机制的过程。第一步 根据题目要求将每个进程的执行过程一步一步描述出来：生产者进程 L1: 生产一件产品；产品放入缓冲；goto L1；消费者进程 L2: 从缓冲中区走产品；消费一件产品；goto L2；第二步 分析每个进程每一步的执行条件，将条件一一记录：生产者进程：生产一件产品的条件

9、是有生产产品的原料，在题目中不曾提及，所以该条件不考虑，认为这一步骤没有限制条件；产品放入缓冲条件是要有产品、缓冲和无生产者向缓冲中放产品，由于前一步骤已经生产出产品，所以这一步骤执行是肯定有产品，这一步骤的限制条件是有缓冲和无生产者向缓冲中放产品；消费者进程：从缓冲中取走产品条件是缓冲中有产品和无消费者从缓冲中取产品，这一步骤的限制条件是缓冲中的产品和无消费者从缓冲中取产品；消费产品的条件是应该是已获得产品，由于前一步骤已经获得产品，所以这一步骤执行是肯定有产品的，所以这一步骤没有限制条件；第三步 比较各个条件，将同一条件归为一个，设置一个信号量表示；根据第二步分析，本题中有四个限制条件：一

10、个是缓冲，定义信号量empty；一个是无生产者向缓冲中放产品，定义信号量mutex1；一个是产品，定义信号量full；一个是无消费者从缓冲中取产品，定义信号量mutex2。第四步 设置信号量初值：mutex1，mutex2是互斥信号量，每次只能由一个生产者（或消费者）向缓冲中放产品（取产品），所以初值均为“1”；empty，full是资源数量，系统初始状态应该是缓冲均空，无产品，所以empty=n，full=0。第五步 重新分析每个进程的每个步骤，加入wait,signal操作：生产者进程：生产一件产品，无限制条件，且对上述四个信号量无影响；产品放入缓冲条件是缓冲和无生产者向缓冲中放产品，所以

11、这条语句前加上wait(empty)、wait(mutex1)，这条语句执行完后，应该释放互斥信号量mutex1和缓冲中产品会增加一个，所以这条语句后应加入signal(mutex1)、signal(full)；消费者进程：从缓冲中取走产品条件是缓冲中有产品和无消费者从缓冲中取产品，所以这条语句前加上wait(full)、wait(mutex2)，这条语句执行完后，应该释放互斥信号量mutex2和缓冲中产品少了一个，缓冲会增加一个，所以这条语句后应加入signal(mutex1)、signal(empty)；消费产品无限制条件，且对上述四个信号量无影响。这样生产者和消费者进程的过程修改为：生产

12、者进程 L1: 生产一件产品； wait(empty); wait(mutex1);产品放入缓冲；signal(mutex1);signal(full);goto L1；消费者进程 L2: wait(full); wait(mutex2);从缓冲中区走产品；signal(mutex2);signal(empty);消费一件产品；goto L2；用一个数组B描述缓冲，k指示放产品的位置，t指示取产品的位置，则完整的生产者消费者算法描述如下：semaphore mutex=1,empty=n,full=0;item buffern;int in=out=0;void producer() whil

13、e (1) produce an item in nextp; . wait(empty); wait(mutex); bufferin=nextp; in=(in+1) mod n; signal(mutex); signal(full); void consumer()while (1) . wait(full); wait(mutex); nextc=bufferout; out=(out+1) mod n; signal(mutex); signal(empty); . consume the item in nextc; main()cobegin producer();consum

14、er(); 第六步 检查：其中wait(mutex1)和signal(mutex1)之间的程序段是各生产者的相关临界区，保证了生产者放产品的互斥；wait(mutex2)和signal(mutex2)之间的程序段是各消费者的相关临界区，保证了消费者的互斥；wait(empty)保证了有缓冲才可放产品，无缓冲时生产者等待；wait(full)保证了缓冲中有产品才可取产品，无产品时消费者等待；signal(empty)让消费者通知系统释放一个缓冲，有生产者等待缓冲时可将其唤醒；signal(full)让通知生产者系统增加了一个产品，有消费者等待产品时可将其唤醒。符合题目要求，题目完成。例2 现有四

15、个进程R1、R2、W1、W2，它们共享可以存放一个数的缓冲器B。进程R1每次把来自键盘的一个数存入缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。为防止数据的丢失和重复打印，问怎样用wait,signal操作来协调这四个进程的并发执行。第一步 根据题目要求将每个进程的执行过程一步一步描述出来：进程R1：Ll: 接收来自键盘的数;x=接收的数;B=x; -数据放入缓冲 goto L1;进程R2：L2: 从磁盘上读一个数;y=读入的数;B=y; -数据放入缓冲 goto L2;进程W1: L3: k=B; -从缓冲中取数据打印k中数;goto L3

16、进程W2: L4：j=B; -从缓冲中取中数据 打印j中数;goto L4第二步 分析每个进程每一步的执行条件，将条件一一记录：进程R1：接收来自键盘的数：执行条件要有键盘，题目中无要求，所以不加考虑，无限制条件；x=接收的数：x为进程R1内部变量，无需限制条件，此步骤无限制条件；B=x;：数据放入缓冲需要数据和缓冲，数据前面步骤一生成，所以限制条件为有空缓冲； 进程R2（与进程R1同理）：从磁盘上读一个数：无限制条件；y=读入的数：无限制条件；B=y; ：限制条件为有空缓冲；进程W1:k=B;：从缓冲中取数据需要缓冲中有R1输入数据，所以限制条件为缓冲中有R1输入的数据；打印k中数;：执行条

17、件要有打印设备，题目中无要求，所以不加考虑，无限制条件；进程W2（与进程W1同理）：j=B;：限制条件为缓冲中有R2输入的数据；打印j中数;：无限制条件。第三步 比较各个条件，将同一条件归为一个，设置一个信号量表示；根据第二步分析，本题中有三个限制条件，需要定义三个信号量：S：表示空缓冲器B。 S1：表示缓冲器中是否存有进程R1读入的数。S2：表示缓冲器中是否存有进程R2读入的数。第四步 设置信号量初值：系统初始状态，无数据读入，缓冲为空，所以S的初值为1，S1和S2的初值为0；第五步 重新分析每个进程的每个步骤，加入wait,signal操作：进程R1：接收来自键盘的数：无限制条件，执行后对

18、上述三个信号量无增值作用；x=接收的数：无限制条件，执行后对上述三个信号量无增值作用；B=x;：限制条件为有空缓冲，语句前加入wait(S)，执行后缓冲中有进程R1读入的数，对S1有增值作用，语句后加入signal(S1); 进程R2（与进程R1同理）：从磁盘上读一个数：无限制条件，执行后对上述三个信号量无增值作用；y=读入的数：无限制条件，执行后对上述三个信号量无增值作用；B=y; ：限制条件为有空缓冲，语句前加入wait(S)，执行后缓冲中有进程R1读入的数，对S2有增值作用，语句后加入signal(S2);进程W1:k=B;：限制条件为缓冲中有R1输入的数据，语句前加入wait(S1)，

19、执行后归还缓冲，对S有增值作用，语句后加入signal(S)；打印k中数;：无限制条件，执行后对上述三个信号量无增值作用；进程W2（与进程W1同理）：j=B;：限制条件为缓冲中有R2输入的数据，语句前加入wait(S2)，执行后归还缓冲，对S有增值作用，语句后加入signal(S)；打印j中数;：无限制条件，执行后对上述三个信号量无增值作用。四个进程可如下描述：semaphore S=1,S1=S2=0;buffer B;void R1（）int x;while(1)接收来自键盘的数;x=接收的数;wait(S);B=x;signal(S1); void R2()int y;while(1)

20、从磁盘上读一个数;y=接收的数;wait(S);B=y;signal(S2); void W1()int k;while(1) wait(Sl);k=B;signal(S);打印k中数; void W2()int j;while(1)wait(S2);j=B;signal(S);打印j中数; main() cobegin R1(); R2(); W1(); W2(); 第六步 检查：在这里，进程R1和进程R2在向缓冲器B中存数之前调用了wait(S)，这个wait(S)起两个作用：由于S的初值为1，所以wait(S)限制了每次至多只有一个进程可以向缓冲器中存入一个数，起到了互斥地向缓冲器中存数

21、的作用；由于当缓冲器中有数且尚未被取走时S的值为0，当缓冲器中数被取走后S的值又为1，因此wait(S)起到了测试允许存入一个新数的消息是否到达的同步作用。进程W1和进程W2把需要的数取走后，都调用signal(S)发出可以存放一个新数的消息。可见，在这个问题中信号量S既被作为互斥的信号量，又被作为同步的信号量。例 假定有三个进程R、W1、W2共享一个缓冲器B,B中每次只能存放1个数。进程R每次启动输入设备读一个整数且把它存放到缓冲器B中。若存放到缓冲器中的是奇数，则由进程W1，将其取出打印；若存放到缓冲器中的是偶数，则由进程W2将其取出打印。同时规定进程R仅当缓冲器中无数时或缓冲器中的数已被

22、取出打印后才能再存放一个数；进程W1和进程W2对存入缓冲器的数不能重复打印，也不能从空的缓冲器中取数。要求用wait,signal操作管理这三个并发进程，使它们能正确地同步工作。第一步 根据题目要求将每个进程的执行过程一步一步描述出来：进程R：Ll: 从输入设备上读一个数;x=接收的数;B=x; -数据放入缓冲 goto L1;进程W1: L2: y=B; -从缓冲中取奇数打印y中数;goto L2进程W2: L3：z=B; -从缓冲中取中偶数 打印z中数;goto L3第二步 分析每个进程每一步的执行条件，将条件一一记录：进程R：从输入设备上读一个数：执行条件要有输入设备，题目中无要求，所以

23、不加考虑，无限制条件；x=接收的数：x为进程R内部变量，无需限制条件，此步骤无限制条件；B=x;：数据放入缓冲需要数据和缓冲，数据前面步骤一生成，所以限制条件为有空缓冲；进程W1:y=B;：从缓冲中取奇数，限制条件为缓冲中有R输入的奇数；打印y中数;：执行条件要有打印设备，题目中无要求，所以不加考虑，无限制条件；进程W2（与进程W1同理）：z=B;：限制条件为缓冲中有R输入的偶数；打印z中数：无限制条件；第三步 比较各个条件，将同一条件归为一个，设置一个信号量表示；根据第二步分析，本题中有三个限制条件，需要定义三个信号量：S：表示空缓冲器B。 SO：表示缓冲器中是否存有进程R读入的奇数。SE：

24、表示缓冲器中是否存有进程R读入的偶数。第四步 设置信号量初值：系统初始状态，无数据读入，缓冲为空，所以S的初值为1，SO和SE的初值为0；第五步 重新分析每个进程的每个步骤，加入wait,signal操作：进程R：从输入设备上读一个数：无限制条件，执行后对上述三个信号量无增值作用；x=接收的数：无限制条件，执行后对上述三个信号量无增值作用；B=x;：限制条件为有空缓冲，语句前加入wait(S)，执行后，若读入的数为奇数，对SO有增值作用，语句后加入signal(SO)，若读入的数为偶数，对SE有增值作用，语句后加入signal(SE)；进程W1:y=B;：限制条件为缓冲中有R输入的奇数，语句前

25、加入wait(SO)，执行后归还缓冲，对S有增值作用，语句后加入signal(S)；打印y中数;：无限制条件，执行后对上述三个信号量无增值作用；进程W2（与进程W1同理）：z=B;：限制条件为缓冲中有R输入的偶数，语句前加入wait(SE)，执行后归还缓冲，对S有增值作用，语句后加入signal(S)；打印z中数;：无限制条件，执行后对上述三个信号量无增值作用。三个进程可如下描述：semaphore S=1,SO=SE=0;buffer B;void R1（）int x;while(1)从输入设备上读一个数;x=接收的数;wait(S);B=x;if B=奇数 then signal(SO);

26、else signal(SE); void W1()int y;while(1) wait(SE);y=B;signal(S);打印y中数; void W2()int z;while(1) wait(SO);z=B;signal(S);打印z中数 ; main() cobegin R(); W1(); W2(); 第六步 检查：wait(S)保证了进程R只能向缓冲中放入一个整数，若数据没有取走，则只能等待；wait(SO)保证进程W1只能取走奇数，若无奇数则等待；wait(SE)保证进程W2只能取走偶数，若无偶数则等待；if B=奇数 then signal(S);else signal(SE

27、);保证了存入奇数时唤醒W1，存入偶数时唤醒W；signal(S)可归还缓冲，可唤醒进程R。练习： 今有3个并发进程R，M，P，它们共享一个缓冲器B。进程R负责从输入设备读信息，每读出一个记录后把它存放在缓冲器B中。进程M在缓冲器B中加工进程R存入的记录。进程P把加工后的记录打印输出。缓冲器B中每次只能存放一个记录，当记录被加工输出后，缓冲器B中又可存放一个新记录。请用PV操作为同步机制写出它们并发执行时能正确工作的程序。Semaphore S1=1,S2=S3=0; void R（）int x; while(1)从输入设备上读一个数;x=接收的数;wait(S1);B=x;signal(S2

28、); void M()while(1) wait(S2);加工B中数据；signal(S3); void P()int z; while(1) wait(S3);z=B;signal(S1);打印z中数; Main()cobegin R(); M(); P();2考虑三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷，做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计一个同步算法来描述他们的活动。设smokerA拥有烟草，需要纸和火柴 设纸和火柴为信号量A设smokerB拥有纸 ，需要烟草和火柴 设